Paper 2020/440

Sublattice Attack on Poly-LWE with Wide Error Distributions

Hao Chen

Abstract

The fundamental problem in lattice-based cryptography is the hardness of the Ring-LWE, which has been based on the conjectured hardness of approximating ideal-SIVP or ideal-SVP. Though it is now widely conjectured both are hard in classical and quantum computation model” there is no sufficient attacks proposed and considered. In this paper we propose the subset quadruple attack on general structured LWE problems over any ring endowed with a positive definite inner product and an error distribution. Hence from the view of subset quadruple attacks, the error distributions of feasible non-negligible subset quadruples should be calculated to test the hardness. Sublattice pair with an ideal attack is a special case of subset quadruple attack. A lower bound for the Gaussian error distribution is proved to construct suitable feasible non-negligible sublattices. From the sublattice pair with an ideal attack we prove that the decision Poly-LWE over ${\bf Z}[x]/(x^n-p_n)$ with certain special inner products and arbitrary polynomially bounded widths of Gaussian error distributions can be solved with the polynomial time for the sufficiently large polynomially bounded modulus parameters $p_n$.\\ Keywords: Poly-LWE, Ring-LWE, Wide Error distribution, Subset quadruple attack, Sublattice pair with an ideal.

Note: Subset attacks proposed, the hardness of some Poly-LWE tested.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Lattice cryptographyRing-LWE
Contact author(s)
haochen @ jnu edu cn
chenhao @ fudan edu cn
History
2021-12-16: last of 20 revisions
2020-04-19: received
See all versions
Short URL
https://ia.cr/2020/440
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/440,
      author = {Hao Chen},
      title = {Sublattice Attack on Poly-{LWE} with Wide Error Distributions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/440},
      year = {2020},
      url = {https://eprint.iacr.org/2020/440}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.