Cryptology ePrint Archive: Report 2022/275
Concrete Analysis of Approximate Ideal-SIVP to Decision Ring-LWE Reduction
Neal Koblitz and Subhabrata Samajder and 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.
Category / Keywords: public-key cryptography / ideal lattices, shortest vector problem, ring learning with errors, concrete analysis
Date: received 1 Mar 2022, last revised 19 Apr 2022
Contact author: koblitz at uw edu, subhabrata at iiitd ac in, palash at isical ac in, subha_r at isical ac in
Available format(s): PDF | BibTeX Citation
Version: 20220419:113801 (All versions of this report)
Short URL: ia.cr/2022/275
[ Cryptology ePrint archive ]