English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper, we study the Learning With Errors problem and its binaryvariant, where secrets and errors are binary or taken in a small interval. Weintroduce a new variant of the Blum, Kalai and Wasserman algorithm, relying ona quantization step that generalizes and fine-tunes modulus switching. Ingeneral this new technique yields a significant gain in the constant in frontof the exponent in the overall complexity. We illustrate this by solving pwithin half a day a LWE instance with dimension n = 128, modulus $q = n^2$,Gaussian noise $\alpha = 1/(\sqrt{n/\pi} \log^2 n)$ and binary secret, using$2^{28}$ samples, while the previous best result based on BKW claims a timecomplexity of $2^{74}$ with $2^{60}$ samples for the same parameters. We thenintroduce variants of BDD, GapSVP and UniqueSVP, where the target point isrequired to lie in the fundamental parallelepiped, and show how the previousalgorithm is able to solve these variants in subexponential time. Moreover, wealso show how the previous algorithm can be used to solve the BinaryLWE problemwith n samples in subexponential time $2^{(\ln 2/2+o(1))n/\log \log n}$. Thisanalysis does not require any heuristic assumption, contrary to other algebraicapproaches; instead, it uses a variant of an idea by Lyubashevsky to generatemany samples from a small number of samples. This makes it possible toasymptotically and heuristically break the NTRU cryptosystem in subexponentialtime (without contradicting its security assumption). We are also able to solvesubset sum problems in subexponential time for density $o(1)$, which is ofindependent interest: for such density, the previous best algorithm requiresexponential time. As a direct application, we can solve in subexponential timethe parameters of a cryptosystem based on this problem proposed at TCC 2010.

An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices