Paper 2022/1750

Faster Dual Lattice Attacks by Using Coding Theory

Kevin Carrier, ETIS Laboratory, CY Cergy-Paris University
Yixin Shen, Royal Holloway, University of London
Jean-Pierre Tillich
Abstract

We present a faster dual lattice attack on the Learning with Errors (LWE) problem, based on ideas from coding theory. Basically, it consists of revisiting the most recent dual attack of \cite{Matzov22} and replacing modulus switching by a decoding algorithm. This replacement achieves a reduction from small LWE to plain LWE with a very significant reduction of the secret dimension. We also replace the enumeration part of this attack by betting that the secret is zero on the part where we want to enumerate it and iterate this bet over other choices of the enumeration part. We estimate the complexity of this attack by making the optimistic, but realistic guess that we can use polar codes for this decoding task. We show that under this assumption the best attacks on Kyber and Saber can be improved by 1 and 6 bits.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Lattice dual attacks codes
Contact author(s)
kevin carrier @ ensea fr
yixin shen @ rhul ac uk
jean-pierre tillich @ inria fr
History
2022-12-27: approved
2022-12-20: received
See all versions
Short URL
https://ia.cr/2022/1750
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1750,
      author = {Kevin Carrier and Yixin Shen and Jean-Pierre Tillich},
      title = {Faster Dual Lattice Attacks by Using Coding Theory},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1750},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1750}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.