Achieving IND-CCA2 Security and Squared-Exponential Decryption Failure Rate for Low-Noise LPN-Based Public-Key Encryption

Abstract

The Learning Parity with Noise (LPN) problem is a foundational assumption for constructingbsimple and efficient post-quantum cryptographic primitives. While LPN-based Public-Key Encryption (PKE) schemes exist, achieving high-level security like Indistinguishability under Adaptive ChosenCiphertext Attack (IND-CCA2) simultaneously with a low Decryption Failure Rate (DFR) has been a persistent challenge. This paper presents a construction of an LPN-based PKE scheme that is proven IND-CCA2 secure in the standard model under the Decisional LPN (D-LPN) assumption. Critically, we introduce a modified decryption mechanism that significantly reduces the DFR, achieving a squaredexponential rate 2^(-Θ(k^2)), where k is the security parameter. This rate is a vast improvement over the linear-exponential rate, 2-Ɵ(k), of previous schemes in the low-noise regime, as identified by Xu et al. (2021). The resulting PKE scheme is highly practical and competitive for resource-constrained environments.