PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Paul Kirchner, Pierre-Alain Fouque

arXiv:1506.02717v4cs.CRcs.DScs.LG

TL;DR

BKW-style LWE solving combines samples, but combinations reduce the noise bias, making short combinations important. The paper introduces a quantization step that generalizes modulus switching and reports improved LWE complexity alongside subexponential algorithms for related lattice, BinaryLWE, and subset-sum problems.

  • Problem

    Combining LWE samples to cancel their vector components reduces noise bias, so the number of samples combined must be kept small.

    Source: §3.1 · p. 6

  • Method

    The paper improves BKW with a quantization step that generalizes and fine-tunes modulus switching.

    Source: §1 · p. 2, §3.1 · p. 6

  • Results

    The algorithm yields subexponential solutions for bounded-coordinate BDD, GapSVP, and UniqueSVP, subset sum at density o(1), and BinaryLWE in 2^((ln 2/2+o(1))n/log log n).

    Source: §1 · p. 2

  • Takeaways & Limitations

    The subset-sum result applies to the TCC 2010 cryptosystem, whose parameters can be solved in subexponential time.

    Source: §1 · p. 2

    Constant-factor reductions in quantization distance complicate the proof without improving the leading complexity term; error-correcting codes may help at small moduli.

    Source: §3.2 · p. 6

Abstract

from arXiv · show

In this paper, we study the Learning With Errors problem and its binary variant, where secrets and errors are binary or taken in a small interval. We introduce a new variant of the Blum, Kalai and Wasserman algorithm, relying on a quantization step that generalizes and fine-tunes modulus switching. In general this new technique yields a significant gain in the constant in front of the exponent in the overall complexity. We illustrate this by solving p within 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 time complexity of $2^{74}$ with $2^{60}$ samples for the same parameters. We then introduce variants of BDD, GapSVP and UniqueSVP, where the target point is required to lie in the fundamental parallelepiped, and show how the previous algorithm is able to solve these variants in subexponential time. Moreover, we also show how the previous algorithm can be used to solve the BinaryLWE problem with n samples in subexponential time $2^{(\ln 2/2+o(1))n/\log \log n}$. This analysis does not require any heuristic assumption, contrary to other algebraic approaches; instead, it uses a variant of an idea by Lyubashevsky to generate many samples from a small number of samples. This makes it possible to asymptotically and heuristically break the NTRU cryptosystem in subexponential time (without contradicting its security assumption). We are also able to solve subset sum problems in subexponential time for density $o(1)$, which is of independent interest: for such density, the previous best algorithm requires exponential time. As a direct application, we can solve in subexponential time the parameters of a cryptosystem based on this problem proposed at TCC 2010.

1 Introduction

The introduction presents a quantization-based BKW improvement for LWE and applies it to lattice problems, BinaryLWE, NTRU, and subset sum. The work addresses prior BKW bottlenecks and reports subexponential algorithms for several of these settings.

1 Introduction

  • BKW reduces sample dimension at the cost of bias, while prior FFT improvements target its second stage and leave the first-stage bottleneck unchanged.The introduction also frames LWE as important to cryptography, with cryptosystems including fully homomorphic encryption proven secure under its hardness.Source: §1 · pp. 1–2
  • The new quantization step generalizes modulus switching, lowers the constant in LWE’s exponential complexity, avoids Gaussian-noise and unproven-independence requirements, and handles larger noise.Earlier FFT improvements to BKW left its first step unchanged, so the overall asymptotic complexity did not improve.Source: §1 · p. 2
  • Small-bound variants of BDD, GapSVP, and UniqueSVP require the target lattice point’s basis coordinates to have bounded infinity norm and admit subexponential algorithms.When parameters are chosen so the point lies in the fundamental parallelepiped, these variants arise as special cases.Source: §1 · p. 2
  • For subset sum, the algorithm runs in subexponential time at density o(1), including 2^((ln 2/2+o(1))n/log log n) at density O(1/log n).The passage contrasts this with exponential-time lattice-reduction techniques for density o(1) and applies the result to the TCC 2010 cryptosystem.Source: §1 · p. 2
  • BinaryLWE with reasonable noise is solvable in 2^((ln 2/2+o(1))n/log log n), instead of 2^Ω(n), including secrets up to size 2^log^o(1) n.The passage also describes heuristic subexponential recovery of NTRU secret polynomials, while noting that the large hidden o(1) term precludes practical attacks on recommended parameters.Source: §1 · p. 2

2 Preliminaries

The preliminaries establish LWE and lattice notation, define the noise and bias framework, and state tools used by the algorithms. They also present secret-error switching and low-dimensional procedures for distinguishing LWE or recovering its secret.

2 Preliminaries

  • A distribution with bias b can be distinguished from uniform with constant probability using Ω(1/b²) samples, and the bias of a sum of two independent variables is the product of their biases.The bias of a Gaussian distribution with mean 0 and standard deviation qα is exp(−2π²α²).Source: §2 · p. 3
  • The paper’s nonstandard LWE definition uses a noise distribution and distortion parameter, extending the Gaussian case while simplifying the analysis.For Gaussian noise, the stated bias is exp(-2π^2α^2).Source: §2 · p. 3
  • LWE samples pair a uniform vector with a noisy inner product; Decision-LWE distinguishes these samples from uniform, while Search-LWE recovers the secret.The paper also uses discrete Gaussian distributions and defines lattice quantities including successive minima and the smoothing parameter.Source: §2 · p. 3
  • The generalized BDD, GapSVP, and UniqueSVP problems bound the target lattice vector’s basis coordinates by B; setting B = 2^n recovers usual definitions for a reduced input matrix.The definitions specify bounded-coordinate target or short-vector conditions.Source: §2 · pp. 3–4

2.1 Secret-Error Switching

  • Secret-error switching converts an oracle for rounded-error secrets into one for arbitrary secrets, using O(n log log q) additional samples and negligible failure probability.The transformation makes the error vector the new secret, then recovers the original secret from the oracle output.Source: §2.1 · p. 4
  • For prime q, switching loses n+k samples with failure probability bounded by q^(-1-k).The theorem’s general sample overhead is O(n log log q).Source: §2.1 · p. 4

2.2 Low dimension algorithms

  • At dimension zero, Decision-LWE is solvable with advantage 1-2^-Ω(k) using m = k/b^2 samples and O(m) time.For secret recovery, FindSecret uses more than (8n log q+k)/b^2 samples and runs in O(m+n log^2(q)q^n) time, failing with probability at most 2^-Ω(k).Source: §2.2 · p. 5

3 Main algorithm

This section develops an improved BKW algorithm using coordinate-dependent quantization and analyzes its complexity for LWE settings with different secret and error conditions. It also describes practical improvements and experiments, and extends the analysis to an L2-norm secret condition and a relaxation on modulus divisibility.

3.1 Rationale

  • BKW’s rounding error grows more when early reductions are combined repeatedly, so the algorithm uses progressively coarser approximations and longer blocks in later steps.The proposed general view balances the resulting costs and retains modulus switching’s core ideas.Source: §3.1 · p. 6

3.2 Quantization

  • The quantizer assigns centers to points so matching samples can be subtracted, using a coordinate-dependent constant rather than modulus switching’s single constant.The paper notes that a more complex quantizer can reduce average distance by a constant factor for large moduli, without improving the leading complexity term.Source: §3.2 · p. 6

3.3 Main Algorithm

  • Theorem 4 gives Solve time 2^(n/2+o(n))/ln(1+log β/log B) when secrets are bounded by B and the stated parameter conditions hold.The theorem assumes B ≥ 2, max(β, log(q)) = 2^o(n/log n), β = ω(1), and ϵ ≤ 1/β^4.Source: §3.3 · p. 9
  • For Gaussian errors with q = n^d, β = n^c, c > 1/2, and ϵ ≤ n^−4c, the algorithm finds a solution in time 2^(n/(1/d+2 ln(d/(1/2+d−c))−o(1))).The corollary derives this bound using a secret-bounding step and repeated runs.Source: §3.3 · p. 10

3.4 Some Practical Improvements

  • Heuristic practical improvements can select smaller-norm differences among samples sharing a quantization center, sacrificing independence but yielding a constant-factor gain in final bias without changing the exponent factor.The authors model coordinates as Gaussian to predict norm reductions and report the model is imperfect, especially in early iterations.Source: §3.4 · pp. 10–11
  • Practical optimizations significantly improve performance without changing asymptotic complexity; for binary secrets, combining reduction and quantization can exploit secret-error switches across independent tries.This may allow constant success probability with very limited data, possibly linear in n.Source: §3.4 · p. 11

3.5 Experimentation

  • 2^28 samples recovered the binary secret in 13 hours; the previous BKW result claimed 2^74 time with 2^60 samples, while BKZ-40 plus enumeration solved the same problem in two minutes.The experiment used n = 128, q = n^2, and Gaussian errors with α = 1/(√(n/π) log^2 n); the implementation computed 9 · 10^13 norms and used a naive quantizer.Source: §3.5 · p. 11
  • The Regev-parameter analysis reports asymptotic complexity 2^(0.93n+o(n)), rather than 2^(n+o(n)).The table distinguishes reasonable, pessimistic, and optimistic quantizer and reduction-factor assumptions.Source: Table 1 · p. 12, §3.5 · p. 12

3.6 Extension to the norm L2

  • Rejection sampling transforms sample-vector coordinates into small discrete Gaussians, removing the coordinate-wise secret condition, though it applies only to some moduli and takes more time.The passage says the asymptotic complexity remains the same.Source: §3.6 · p. 13
  • Under the stated bounds on ||s||, B, β, and ε, Decision-LWE can be solved in time 2^((n/2+o(n))/ln(1+log β/log B)); if Bβ ≤ q, the result holds without the divisibility condition.The theorem requires B ≥ 2, max(β, log(q)) = 2^o(n/log n), β = ω(1), and ε ≤ 1/β^4.Source: §3.6 · p. 14

4 Applications to Lattice Problems

The section reduces bounded-distance decoding to LWE solving, then uses that capability to address UniqueSVP and GapSVP variants. Under stated conditions, the reductions yield polynomial- or subexponential-time algorithms.

4.1 Variant of Bounding Distance Decoding

  • The BDD-to-LWE reduction recovers the closest lattice point under the stated distance and error conditions, with failure probability bounded as a function of t and m.The distance condition includes ||v|| ≤ (1 − 1/n)λ1/β/t, and the result uses n² calls to the LWE oracle.Source: §4.1 · p. 16
  • BDD can be solved in time 2^(n/2+o(n))/ln(1 + log β/log B) when β = ω(1), β = 2^o(n/log n), and log B = O(log β).The section first gives a reduction from bounded-distance decoding to LWE solving.Source: §4 · p. 14, §4.1 · p. 16

4.2 UniqueSVP

  • The UniqueSVP reduction uses BDD on a sublattice and tries each coordinate and residue, requiring np calls to BDD.The constructed sublattice has first minimum at least λ2(Λ).Source: §4.2 · p. 17

4.3 GapSVP

  • A general GapSVP reduction uses O(dn/ϵ/ξ(1 − d²)^−n/2) calls to the BDD oracle.The algorithm tests whether BDD returns the sampled point and distinguishes λ1 ≤ 1 from λ1 ≥ β/d.Source: §4.3 · p. 17
  • 2^(n+o(n))/ln ln n time suffices to solve any GapSVP variant covered by Corollary 4.The result is stated for the parameters in Corollary 4.Source: §4.3 · p. 19

5 Other applications

The section applies the paper’s BDD and sample-expansion techniques to low-density subset sum and LWE variants, and to NTRU. It gives subexponential-time results for these applications under stated conditions.

5.1 Low density subset-sum problem

  • For density d = o(1) and d = ω(log n/n), subset sum is solvable with negligible failure probability in time 2^(n/2+o(n))/ln(1/d).For the Lyubashevsky et al. cryptosystem, the paper gives a subexponential-time result under its stated density condition.Source: §5.1 · p. 20

5.2 Sample Expander and application to LWE with binary errors

  • The sample-expander theorem converts an attack on LWE with error ⟨s, y⟩ + ⟨e, x⟩ into either uniform-secret Decision-LWE or a solver for Small-LWE.The alternative small-instance problems constrain the norms of the secret and error, as defined for Small-DecisionLWE and Small-SearchLWE.Source: §5.2 · p. 20

Sample Expander

  • The sample-expander reduction generalizes and improves Döttling’s reduction, and the section gives reductions connecting Decision-LWE and Knapsack-LWE.The two problems are equivalent up to an advantage loss of q^(-n-1).Source: Sample Expander · p. 21

Applications

  • For NTRU, previous algorithms heuristically recover f and g, with coefficients bounded by 1, from h = f/g mod (X^n − 1, q), using hg = 0 with error bounded by 1, in time 2^((n/2+o(1))/ln ln q).Source: Applications · p. 23
  • Search-LWE with at least n log q + r samples, Gaussian noise α = n^−c, and q = n^d is solvable under the stated failure-probability bound.The paper also gives a subexponential-time result for Small-DecisionLWE under the conditions in Corollary 6.Source: Applications · p. 23

A LWE in Small Dimension

For one-dimensional LWE, the algorithm uses Fourier analysis to approximate the secret, then iteratively refines that approximation. The Fourier stage identifies a value within q/R of the secret.

A LWE in Small Dimension

  • The Fourier transform computes experimental bias across candidate secrets and selects the candidate with the largest bias.The candidate values are regularly spaced so their bias can be computed in one Fourier transform.Source: A LWE in Small Dimension · p. 26
  • The Fourier stage determines an x satisfying |s − x| < q/R.The analysis contrasts the bias for |s − x| ≤ q/R/4 with the smaller upper bound when |s − x| ≥ q/R.Source: A LWE in Small Dimension · p. 26
  • Repeating the refinement with increasing R values recovers the final coordinate, and repeating it n − 1 times recovers the whole secret.The paper identifies DSA security and recovery of Diffie-Hellman most significant bits as settings where small dimension is interesting.Source: A LWE in Small Dimension · pp. 25–26

B Solving LWE with Lattice Reduction

This appendix reviews lattice-reduction methods and the heuristic BKZ model used in the paper’s analysis.

B Solving LWE with Lattice Reduction

  • Lattice reduction seeks a basis containing short vectors, and the described best algorithm uses polynomially many shortest-vector-oracle calls.The approximation factor is expressed using the Hermite constant and lattice volume.Source: B Solving LWE with Lattice Reduction · p. 26
  • The paper models BKZ heuristically using lengths of orthogonalized basis vectors and the Gaussian heuristic.In this model, the oracle call has time 2^((c+o(1))d), with c depending on the algorithm and whether heuristics or quantum computation are used.Source: B Solving LWE with Lattice Reduction · pp. 26–27
  • The Gaussian-heuristic estimate relates the lattice parameter to dimension and volume as approximately d^(n/2d) V^(1/n).The displayed expression is the stated approximation for the shortest-vector scale.Source: B Solving LWE with Lattice Reduction · p. 26

B.1 Primal algorithm

The primal algorithm uses a heuristic Babai-decoding condition to analyze lattice-based solving, with running time depending on the noise and modulus parameters. It also gives parameter regimes for subexponential or polynomial time and applies the method to subset sum.

B.1 Primal algorithm

  • Babai decoding works with high probability under the heuristic condition d^−(n+m)/2/dV^(1/(n+m)) ≥ αq√log n.The orthogonalized error coordinates are assumed independent Gaussians with standard deviation αq.Source: §B.1 · p. 27
  • For α = n^−a and q = n^b, the running time is 2^(2cb/a^2+o(1))n.This follows from the stated relation d/n = 2b/a^2 + o(1).Source: §B.1 · p. 27
  • For binary secret and error, the complexity is 2^(2c/b+o(1))n when q = n^b.The passage gives this result by treating qα as O(1).Source: §B.1 · p. 27
  • The method is polynomial time when log2 α = Ω(log q log log log q / log log q), and subexponential when log2 α = ω(log log q).These regimes follow from the stated choice of d in terms of q and α.Source: §B.1 · p. 27
  • 2^(c+o(1))nd log(nd)n^O(1) is the stated complexity for solving subset sum with density d using the same algorithm and lattice setup.The analysis applies the same heuristics as in subsection 5.1.Source: §B.1 · p. 27

B.2 Dual algorithm

The dual algorithm uses lattice reduction to combine samples into sums that cancel on many coordinates, then applies FindSecret to the remaining coordinates. Its running-time improvements come with an exponential-sample requirement, though the passage gives ways to mitigate that cost.

B.2 Dual algorithm

  • The attack uses lattice reduction to find sample sums that vanish on most coordinates, then runs FindSecret on the remaining coordinates.It selects n truncated samples forming an invertible matrix A and m others forming B, and seeks a nonzero short lattice vector.Source: §B.2 · p. 27
  • The constructed sums vanish on n coordinates and yield a lower-dimensional sample with bias e^−||v||^2α^2.The passage relates the short-vector length to the selected sample count and lattice parameters.Source: §B.2 · p. 27
  • For the stated parameterization, the analysis gives d/n = 8b/(1 + 2a)^2 + o(1).This comes from setting 8n log q log d/d = O(d/α^2).Source: §B.2 · p. 27
  • 2^(2cb/(1/2+b)^2+o(1))n is the stated complexity when the errors are binary.The analysis applies the same formula with α = Θ(1/q).Source: §B.2 · p. 28
  • The algorithm is asymptotically faster than the previous one but requires exponentially many samples.The passage suggests finding many short vectors in one lattice, or using a sample-preserving search-to-decision reduction, to mitigate this disadvantage.Source: §B.2 · p. 28

B.3 Graphical Comparison between lattice algorithms and BKW

The graphical comparison maps noise and modulus parameters to regions and complexity contours for BKW and lattice algorithms. It marks where other attack families are more efficient or subexponential.

B.3 Graphical Comparison between lattice algorithms and BKW

  • The horizontal axis is noise standard deviation, α = n^x, and the vertical axis is modulus, q = n^y.Source: §B.3 · p. 28
  • The upper-right region delimited by the black line favors the dual attack with heuristic classical SVP over BKW; below the black lines, Gröbner basis algorithms are subexponential.Above the red line, a quantum reduction with hard lattice problems applies.Source: §B.3 · p. 28
  • Rainbow contours show the best complexity among BKW and the dual attack, with 2^(k+o(1))n curves for k from 0 to 5 in increments of 0.3.Compare contour levels across the parameter plane.Source: §B.3 · p. 28

C LPN

The section treats LPN as the q = 2 case of LWE with Bernoulli error and gives algorithms for decision and search variants. It states subexponential decision complexity near half noise and a separate search bound for p ≤ 1/4.

C LPN

  • A LPN distribution is an LWE distribution with q = 2 and Bernoulli error parameter p.Source: C LPN · p. 29
  • For p = 1/2 − 2^−n^o(1), Decision-LPN has complexity 2^((n+o(n))/log n).Source: C LPN · p. 29
  • For p ≤ 1/4, Search-LPN is solved in time O(n^4(1 − p)^−n) with negligible probability of failure.Source: C LPN · p. 29
  • At p = (1 + o(1))/ln(n) ≤ 1/4, the stated complexity is O(n^4 exp(n(p + p^2))) = 2^((1+o(1))n/log n), and the threshold between the two algorithms is (1 + o(1))/ln n.For p = 1/√n, the passage gives O(n^4 exp(√n)).Source: C LPN · p. 30
Loading 1506.02717v4…