On the Tightness Gap Analysis of Reductions of some Lattice problems to the Learning with Error problem

Abstract

Lattice-based cryptography is a highly regarded contender for post-quantum standard- ization by NIST. NIST has already chosen “CRYSTALS-KYBER” a lattice-based public-key encryption and key-establishment algorithm and “CRYSTALS-DILITHIUM”, a lattice-based digital signature algorithm. The current lattice-based schemes are based on Oded Regev’s original construction, which sparked significant interest in the cryptographic community due to its post-quantum security and the equivalence between worst-case and average-case hardness. Oded Regev’s cryptographic scheme is built upon a problem called “Learning with Error” (LWE), which is a generalization of the “Learning Parity with Noise” (LPN) problem. This scheme is straightforward to implement and has gained attention for its simplicity. Previ- ously, Mikolas Ajtai demonstrated the worst-case to average-case equivalence for a set of hard lattice problems. Regev’s seminal paper demonstrated that the security of LWE-based cryptosystems could rely on the hardness of worst-case lattice problems. While this result is theoretically groundbreaking, the reduction from hard lattice problems to LWE is not tightly bound, which limits its practical applicability. The tightness of a reduction is a critical factor often underestimated. The tightness gap of a reduction quantifies the concreteness of the reduction, and a tight reduction is valuable for translating theoretical hardness guarantees into practical scenarios. Cryptography, as a field, prioritizes practical applicability. Non-tight reductions lead to less efficient systems but they have practical applications. Regev’s work has prompted numerous follow-up studies. One significant effort aimed to make the reduction classical, as the original reduction was quantum-based. Additionally, subsequent research has focused on enhancing the efficiency of LWE-based cryptosystems by utilizing various algebraic variants of lattices, such as ideal and module lattices. We thoroughly investigate these major reductions to unveil their true significance in terms of reduction tightness. Furthermore, we conduct a concrete security analysis of these reductions and identify several areas for improvement.