Source-linked AI summary
A New Algebraic Algorithm for LWE
Luca Campa, Massimo Fumiani, Arnab Roy
TL;DR
Search-LWE lacks an algebraic solver whose complexity analysis avoids semi-regularity and degree-of-regularity assumptions. This paper introduces a diagonalization- and S-polynomial-based algorithm with direct complexity bounds, achieving polynomial improvement over prior Gröbner-basis methods while requiring q ≥ 3d for high success probability. Its success-probability analysis for d > 2 still relies on Assumption 7.2, whose high-probability validity remains unproved.
Problem
Existing Gröbner-basis analyses for algebraic Search-LWE attacks rely on semi-regularity assumptions and degree-of-regularity estimates.
Method
The algorithm combines diagonalization and S-polynomial generation with a direct complexity analysis in LWE parameters.
Results
The algorithm achieves polynomially lower complexity than prior algebraic attacks and requires only q ≥ 3d for high success probability.
Takeaways & Limitations
The method improves both computational complexity and the range of practical field sizes covered by the success guarantee.
Takeaways & Limitations
For d > 2, the success-probability bound relies on Assumption 7.2, whose high-probability validity remains an open question.
Abstract
from arXiv · showhide
The Learning With Errors (LWE) problem, introduced by Regev in 2005, is central to modern cryptography and post-quantum security. The algorithms to solve the search version of the problem, Search-LWE, can be broadly categorised into algebraic, combinatorial and lattice-based. In this work we propose a new algebraic algorithm for the Search-LWE problem. At a high level, the algorithm combines linear-algebraic techniques with S-polynomial-based methods from Groebner basis computation. We provide a direct complexity analysis of our algorithm, avoiding semi-regularity assumptions and complexity bounds derived from the degree of regularity. Our algorithm achieves a polynomial improvement in complexity over prior results that use Groebner basis methods to solve Search-LWE.
1 Introduction
LWE is a central cryptographic problem with algebraic, combinatorial, and lattice-based solution approaches. This work proposes a new algebraic Search-LWE attack that combines diagonalization with S-polynomial techniques, directly analyzes complexity, and improves polynomially over prior Gröbner-basis methods.
- Search-LWE asks to recover the secret vector from noisy linear samples over a finite field.
- Existing LWE solvers include algebraic, combinatorial, and lattice-based algorithms, with lattice-based methods described as the most efficient.
- The proposed attack combines diagonalization and S-polynomial generation instead of directly applying Gröbner-basis methods.
- The complexity analysis avoids semi-regularity assumptions and degree-of-regularity estimates by expressing bounds directly in LWE parameters.
- A polynomial improvement is obtained over existing algebraic attacks, including a factor of approximately n(d!) compared with the method in.
- The algorithm requires only q ≥ 3d for high success probability, unlike the larger field-size condition required by.
2 Preliminaries
The preliminaries define total degree and degree decomposition for multivariate polynomials, then introduce leading terms, S-polynomials, and Gröbner-basis methods.
- Polynomial degree: The total degree of a monomial x^α is |α|, defined as the sum of its exponents.The notation is given by |α| := Σ_i=1^n α_i.
- Polynomial degree: A polynomial f of total degree d is decomposed into homogeneous components f(d), f(d−1), through f(0).Each f(k) contains the monomials of f having total degree exactly k.
- Monomial order: For a fixed monomial order, LM(f) and LT(f) denote the leading monomial and leading term of f.These definitions establish the notation used for Gröbner-basis computations.
- Gröbner bases: The S-polynomial of two polynomials is defined using the least common multiple of their leading monomials.The passage identifies S-polynomials as fundamental to the Gröbner basis method.
- Gröbner bases: The Gröbner basis method is presented as a technique for solving systems of polynomials.The text refers readers elsewhere for a complete introduction.
3 An Overview of Our Algorithm
The algorithm converts LWE-derived polynomials into a diagonalized system, repeatedly generates and reduces S-polynomials, and diagonalizes lower-degree systems until linear equations reveal the secret.
- Initialization: The LWE polynomial system is represented by a coefficient matrix whose rows are ordered by total-degree monomials.
- Initialization: Initial diagonalization produces monic, distinct leading terms of degree d while retaining lower-degree terms in a dense block.
- Iteration: Each iteration generates selected S-polynomials from the current diagonalized system and reduces them using scalar linear combinations.
- Iteration: The reduced S-polynomials have degree d−1 initially, and subsequent diagonalization covers the monomials of the next lower degree.
- Termination: The procedure recursively decreases degree through d−1 iterations, ending with linear polynomials x_j−s_j that reveal the secret.
- Visualization: Figure 1 represents degree-indexed row blocks, dense lower-degree terms, and the Sgen, Sred, and Diag steps of one iteration.
4 Algorithm and Correctness
Algorithm 1 recursively generates and reduces S-polynomials, diagonalizing the resulting systems until degree 1 reveals the secret. Its correctness follows from preserving the secret as a common zero and finite termination.
- Algorithm: Algorithm 1 iteratively constructs S-polynomial sets, reduces them using the current diagonal system, and diagonalizes each resulting coefficient matrix.The three sets at iteration i are P_i, Q_i, and D_i, with equal cardinality.
- S-polynomial generation: Admissible pairs connect leading monomials whose exponent vectors differ by exchanging one unit between two coordinates, enabling the required S-polynomial generation.When n > d, the construction provides sufficiently many distinct pairs.
- S-polynomial reduction: The generated S-polynomials cancel their highest-degree terms and are reduced entirely through linear combinations, avoiding polynomial division.The cancellation occurs because the multiplied leading monomials are identical.
- S-polynomial reduction: The reduction is equivalent to block Gaussian elimination, producing the Schur complement C − BA as the coefficient matrix of the reduced system.The identity block isolates the leading monomials of the current diagonal system.
- Correctness: The secret remains a common zero throughout all iterations, and the algorithm terminates finitely with equations x_i − s_i that uniquely determine s.At the final iteration, the polynomials are linear, monic, and degree 1.
5 Computational Complexity
The paper directly analyzes the field-multiplication costs of Sgen, Sred, and Diag, then sums them to obtain the total complexity of Algorithm 1. The analysis uses asymptotic bounds under d < n.
- Cost model: The complexity analysis counts field multiplications for Sgen, Sred, and Diag; field additions have the same asymptotic order.The three procedure costs are analyzed across their respective iterations.
- Asymptotic bounds: Lemma 5.1 bounds finite sums of binomial-type terms, allowing lower-degree contributions to be absorbed into the dominant asymptotic term.The bound applies when h < n and c ≥ 1.
- Sred: Sred is dominated by rectangular matrix multiplication because the reduction computes the Schur complement C − BA and requires no matrix inversion.The subsequent matrix subtraction is asymptotically negligible.
- Diag: Diag reduces coefficient matrices to RREF using fast matrix multiplication, with rectangular r × c reduction bounded by O(r^(ω−1)c).Here 2 ≤ ω < 3 is the matrix-multiplication exponent.
- Total complexity: The total complexity C_tot is obtained by summing the asymptotic costs of Sgen, Sred, and Diag.The correctness of Algorithm 1 is established separately.
- Special cases: For BinaryError-LWE, setting d = 2 gives n(n + 1)/2 samples and the specialized complexity stated for Algorithm 1.The binary-secret variant adds square-free constraints and has a separate sample and complexity bound.
6 Success Probability for BinaryError-LWE
For BinaryError-LWE, Algorithm 1 succeeds when the sampled coefficient matrix has full rank. The analysis bounds failure by grouping quadratic forms according to rank and their vanishing fractions.
- Success condition: For d = 2, Algorithm 1 diagonalizes the homogeneous degree-2 LWE system, and success occurs when its coefficient matrix C has full rank.The rows of C are determined by the uniform sample vectors.
- Failure characterization: A nonzero kernel vector of C corresponds to a nonzero quadratic form that vanishes on every sampled vector.This converts rank failure into a vanishing-event probability.
- Rank analysis: The vanishing fraction of a quadratic form depends on its rank, allowing the failure probability to be grouped and summed over rank classes.For odd rank, the stated vanishing count is exact; even-rank forms receive an upper bound.
- Success bound: The full-rank bound yields Pr[rank C = N] ≥ 1 − 2q^-1.This is the stated success guarantee for the d = 2 case.
- Consequences: For n ≥ 13, the bound is independent of n, and the success probability approaches 1 as q grows.The paper also states that small moduli can already yield high-probability success.
7 Success Probability for LWE (d > 2)
For d > 2, the paper bounds Algorithm 1’s success probability by analyzing linear independence of Veronese images in the first iteration and modeling later iterations separately. The resulting guarantees require Assumption 7.2 and apply for q ≥ 3d, with an overall bound stated for q ≥ 4d.
- Overall strategy: Algorithm 1 succeeds only when all d iterations succeed, so the analysis separates the structured first iteration from subsequent iterations.The initial system inherits structure from LWE, whereas Sgen and Sred mix coefficients afterward and destroy the Veronese structure.
- First iteration: The first iteration diagonalizes a degree-d coefficient matrix by requiring the Veronese images νd(a1), …, νd(aN) to be linearly independent.The degree-d Veronese map sends each sample to the vector of all degree-d monomials evaluated at that sample.
- First iteration: The dependence probability is converted into counting common zeros of a linear system of degree-d polynomials, then bounded using Bézout’s inequality and Assumption 7.2.The analysis proceeds one sample at a time and bounds the density of points whose Veronese image lies in the span of previous images.
- Assumption 7.2: Assumption 7.2 requires rℓ = min(n − 1, N − ℓ) selected homogeneous polynomials to form a regular sequence, ensuring the expected dimension drop needed for Bézout bounds.The assumption is weaker than requiring all of Wℓ to be regular, because only rℓ polynomials are selected.
- Limitations: Assumption 7.2 can fail on degenerate configurations such as d + 1 samples lying on one projective line, although experiments indicate it holds with high probability.Formally proving that the assumption holds with high probability is identified as an open question.
- First iteration: The first-iteration lower bound is pℓ ≤ (d/q)^j, while Theorem 7.5 applies for d > 2, n ≥ d^2 + 1, and q ≥ 3d under Assumption 7.2.Theorem 7.5 bounds the probability that the degree-d Veronese images are linearly independent.
- Subsequent iterations: For later iterations, the paper models the coefficient matrices as having independent uniform rows; this heuristic yields a success bound consistent with experiments but leaves more precise stochastic modeling open.The correctness of Algorithm 1 does not depend on this modeling technique, and empirical success probabilities exceed the theoretical bound.
8 Conclusions
The paper presents a probabilistic algebraic algorithm for LWE that improves polynomially over existing algebraic methods and extends to RSD. Its conclusions identify unresolved questions about success-probability assumptions and sample reduction.
- Conclusions: The proposed probabilistic algebraic algorithm achieves a polynomial improvement in time complexity over existing algebraic algorithms for LWE and also applies to RSD.The RSD extension uses an algebraic modelling in which RSD becomes an overdetermined low-degree polynomial system with structure similar to bounded-error LWE.
- Conclusions: Assumption 7.2 is needed to bound success probability for d > 2, although experiments indicate that it holds with high probability.The paper leaves open whether this probability can be precisely estimated or bounded without the assumption.
- Conclusions: The S-polynomial generation technique produces substantially more candidate pairs than the algorithm uses.This motivates asking whether the sample size can be reduced while preserving the complexity improvement.
A Next combination in Gray code order
Algorithm 5 adapts Gray-code generation for multiset combinations to traverse a Hamiltonian path through tuples and generate admissible pairs efficiently.
- A Next combination in Gray code order: Algorithm 5 defines a Successor procedure that returns the next tuple in Gray-code order, equivalently the next vertex on the corresponding Hamiltonian path.The construction adapts general Gray-code principles for multiset combinations to this setting.
- A Next combination in Gray code order: The Gray-code traversal generates admissible pairs directly while preserving the efficiency of the underlying construction.The implementation uses stack labels and tail computation to simulate recursion and construct the next tuple.
B Solving LWE with Binary Secrets
The BinarySecret-LWE adaptation adds square constraints to the polynomial system, replaces general monomial counts with square-free counts, and retains the algorithm’s dominant asymptotic complexity structure.
- B Solving LWE with Binary Secrets: BinarySecret-LWE imposes x_i^2 − x_i = 0 for every secret coordinate, so the system uses square-free monomials.The error distribution remains unchanged, and the equations are reduced modulo the ideal generated by these relations.
- B Solving LWE with Binary Secrets: Algorithm 5 supplies the next n-tuple combination in Gray-code order through the Successor and ComputeTail procedures.Its implementation uses simulated recursive calls, stack state, and next/prev scan directions.
- B Solving LWE with Binary Secrets: The square-free setting counts monomials by degree using square-free equivalents rather than the general monomial count.The core algorithm remains unchanged under this substitution.
- B Solving LWE with Binary Secrets: The resulting bounds remain functionally identical asymptotically because the general and square-free counts share the same dominant term O(n^i/i!).The minimum sample requirement for initializing the matrix is also addressed in this setting.
- B Solving LWE with Binary Secrets: Figure 3 illustrates monomial connections and the directed Hamiltonian path used to extract admissible pairs.The graph is shown for n = 4 variables and degree d = 3.
- B Solving LWE with Binary Secrets: The modified main procedures have explicit complexity evaluations, and combining them yields the overall BinarySecret-LWE complexity.The supplied passages state this result without displaying the complete bound.
- B Solving LWE with Binary Secrets: The initial system must contain enough distinct square-free polynomials to form the required number of pairs.The proposition derives the condition by requiring at least twice the number of required pairs.
C.1 Regular sequence
A regular sequence is defined for homogeneous polynomials over a field by requiring each polynomial to be a non-zero-divisor modulo the ideal generated by its predecessors.
- C.1 Regular sequence: A sequence of homogeneous polynomials is regular when each polynomial is a non-zero-divisor in the quotient by its predecessors.The definition uses the implication g f_i ∈ ⟨f_1, ..., f_{i−1}⟩ ⇒ g ∈ ⟨f_1, ..., f_{i−1}⟩.
- C.1 Regular sequence: For the first polynomial, the preceding ideal is defined to be the zero ideal.This is the convention ⟨f_1, ..., f_0⟩ = {0}.
C.2 Degree of regularity
This section introduces the degree of regularity and attributes its introduction to Bardet, Faugère, and Salvy.
- The degree of regularity was introduced by Bardet, Faugère, and Salvy.
- For a zero-dimensional ideal I generated by a homogeneous polynomial system, the degree of regularity is defined over a field K.
- The definition considers a system F of m homogeneous polynomials in n variables with m > n and degree d > 0.