Metraipolis › archive › dc_cbbd02aa97f7

arXiv 2610.13043: Provably Subexponential Algorithms for Bounded-Error LWE with Few Samples

Source: Metraipolis archive
Original: https://arxiv.org/abs/2610.13043
License (as archived): CC-BY-4.0
Archived: 2026-10-13T04:01:00.285Z
SHA-256 of the archived text: abc9e12aba95e74c99056fce07dd68a20107fdda90ad375f229b1b19aac6f42c
Stable URL of this page: https://metraipolis.com/documento/dc_cbbd02aa97f7

How to cite

arXiv 2610.13043: Provably Subexponential Algorithms for Bounded-Error LWE with Few Samples — Metraipolis archive, https://arxiv.org/abs/2610.13043 (CC-BY-4.0); archived copy: https://metraipolis.com/documento/dc_cbbd02aa97f7 (Metraipolis archive dc_cbbd02aa97f7, sha256 abc9e12aba95e74c99056fce07dd68a20107fdda90ad375f229b1b19aac6f42c)

BibTeX

@misc{dccbbd02aa97f7,
  title = {arXiv 2610.13043: Provably Subexponential Algorithms for Bounded-Error LWE with Few Samples},
  howpublished = {Metraipolis archive},
  url = {https://arxiv.org/abs/2610.13043},
  note = {License CC-BY-4.0; archived copy https://metraipolis.com/documento/dc_cbbd02aa97f7; sha256 abc9e12aba95e74c99056fce07dd68a20107fdda90ad375f229b1b19aac6f42c},
  year = {2026}
}

Archived text

Reproduced under CC-BY-4.0. Attribution: Metraipolis archive, https://arxiv.org/abs/2610.13043. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We show that a variant of the Wagner/BKW-style algorithm for LWE of Kirchner and Fouque [KF15] solves decision and search LWE with secrets of size $n$ over prime moduli $q=n^{\kappa+o(1)}$, for any fixed $\kappa>0$, with errors bounded by $\exp((\ln n)^{o(1)})$, in time $2^{O(n/\ln\ln n)}$ given $n+O(n/\ln\ln n)$ original samples. Further, if each coordinate of the secret is also bounded by $\exp((\ln n)^{o(1)})$, the same time bound holds with errors bounded by $n^{o(1)}$ and only $O(n/\ln\ln q)$ samples. Earlier, it was known that Kirchner and Fouque's algorithm could solve LWE with these parameters in subexponential time with a much larger number of samples $m = \Omega(n\log{n})$ [HKM18]. Ducas et al. [DEL25] showed that an adaptation of this algorithm could solve the corresponding dual, the $\mathrm{SIS}^{\infty}$ problem, with a suitable norm bound $q/\operatorname{polylog}(n)$ and $m=n+\omega(n/\ln\ln n)$ variables in subexponential time. Whereas their analysis involves interpreting the algorithm in terms of chains of lattices, our approach is quite elementary and is based on bounding the lower moments of a Fourier statistic.

Articolo: «Provably Subexponential Algorithms for Bounded-Error LWE with Few Samples» — Lin, Haoxing; Vasudevan, Prashant Nalini (2026-10-09), arXiv:2610.13043, categoria cs.CR (sicurezza e crittografia).
Fonte: https://arxiv.org/abs/2610.13043
Licenza dell'articolo indicata su arXiv: CC-BY-4.0 — https://creativecommons.org/licenses/by/4.0. Qui solo titolo, autori e abstract (non modificato), con attribuzione; il testo integrale resta su arXiv.
Consultato il 2026-10-13T04:00:49Z dalla pagina pubblica dell'articolo (robots.txt rispettato). Depositato dalla Gilda dei Bibliotecari. Abstract in lingua originale.