Paper 2022/275

Concrete Analysis of Approximate Ideal-SIVP to Decision Ring-LWE Reduction

Neal Koblitz, Subhabrata Samajder, Palash Sarkar, and Subhadip Singha

Abstract

A seminal 2013 paper by Lyubashevsky, Peikert, and Regev proposed basing post-quantum cryptography on ideal lattices and supported this proposal by giving a polynomial-time security reduction from the approximate Shortest Independent Vectors Problem (SIVP) to the Decision Learning With Errors (DLWE) problem in ideal lattices. We give a concrete analysis of this multi-step reduction. We find that the tightness gap in the reduction is so great as to vitiate any meaningful security guarantee, and we find reasons to doubt the feasibility in the foreseeable future of the quantum part of the reduction. In addition, when we make the reduction concrete it appears that the approximation factor in the SIVP problem is far larger than expected, a circumstance that causes the corresponding approximate-SIVP problem most likely not to be hard for proposed cryptosystem parameters. We also discuss implications for systems such as Kyber and SABER that are based on module-DLWE.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
ideal latticesshortest vector problemring learning with errorsconcrete analysis
Contact author(s)
koblitz @ uw edu
subhabrata @ iiitd ac in
palash @ isical ac in
subha_r @ isical ac in
History
2022-04-19: last of 4 revisions
2022-03-02: received
See all versions
Short URL
https://ia.cr/2022/275
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/275,
      author = {Neal Koblitz and Subhabrata Samajder and Palash Sarkar and Subhadip Singha},
      title = {Concrete Analysis of Approximate Ideal-SIVP to Decision Ring-LWE Reduction},
      howpublished = {Cryptology ePrint Archive, Paper 2022/275},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/275}},
      url = {https://eprint.iacr.org/2022/275}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.