## Concrete analysis of approximate ideal-SIVP to decision ring-LWE reduction

Neal Koblitz, Subhabrata Samajder, Palash Sarkar
and Subhadip Singha

*Advances in Mathematics of Communications*, 18 (2024), 1216-1258.

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.

Journal paper
ePrint
paper