Title: Rotation-invariant web bases from hourglass plabic graphs and symmetrized six-vertex configurations
|
Title: Concrete analysis of a few aspects of lattice-based cryptography
Abstract: A seminal 2013 paper by Lyubashevsky, Peikert, and Regev proposed using ideal lattices as a foundation for post-quantum cryptography, supported by a polynomial-time security reduction from the approximate Shortest Independent Vectors Problem (SIVP) to the Decision Learning With Errors (DLWE) problem in ideal lattices. In our concrete analysis of this multi-step reduction, we find that the reduction’s tightness gap is so significant that it undermines any meaningful security guarantees. Additionally, we have concerns about the feasibility of the quantum aspect of the reduction in the near future. Moreover, when making the reduction concrete, the approximation factor for the SIVP problem turns out to be much larger than anticipated, suggesting that the approximate SIVP problem may not be hard for the proposed cryptosystem parameters. |