Learning With Errors
Recover or distinguish a noisy linear system.
Sparse secret · dual reductions
Fixed Hamming weight sparse secrets with q, error width, weight and reduction parameters specified
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEALEurocrypt 2017SourceBibTeX / detailsdual sparse secret relative improvement FHE regime | 18 May 2017 | Scaled-dual log₂ cost ≈ [2L/(2L+1)] · (unscaled-dual log₂ cost), in the stated sparse-FHE regime | Depends on the chosen dual-lattice solver. | PublishedSource checked |
| — | On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEALEurocrypt 2017SourceBibTeX / detailssparse secret dimension reduction relative improvement | 18 May 2017 | O(2h · C(n/2,α,q)); more generally O(ph,d−1·C(n−n/d,α,q)) | Space of the reduced-dimension solver C. | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Fixed Hamming weight sparse secrets with q, error width, weight and reduction parameters specified
- Computation
- Classical
- Rigor
- Heuristic / model-dependent
- Instances
- Uniform random LWE samples; explicit parameter contract
- Cost scale
- Parameter-dependent time and space expressions
- Parameter
- n, q, error width, secret distribution, sample budget and attack parameters
- Description
- Historical LWE bounds and cost models with parameters retained. Entries without a common fixed asymptotic scale are listed without a numerical rank.
- Comparison rules
- Specify q(n), error distribution and width convention, secret distribution, available samples, search versus decision objective, success criterion and lattice/algebraic assumptions. Formula-only entries have null coefficients. A concrete instance estimate is not an exponent c in 2^{cn}.
- Tags
- sparse secret, dual, small secret, parameterized