Paper 2026/1130

Reassessing the Security of LPN-C and its HHE-Oriented Variants

Abstract

The idea of Hybrid Homomorphic Encryption (HHE) is to reduce the computational cost of Fully Homomorphic Encryption (FHE) by encrypting bulk data symmetrically while only encrypting the short symmetric key homomorphically. Its efficiency depends on the multiplicative depth of the symmetric cipher's decryption circuit, motivating FHE-friendly designs. The Learning Parity with Noise (LPN) problem is a natural candidate for such designs, as it gives rise to simple encryption and decryption circuits over binary fields. In this context, Fouque, Hadjibeyli, and Kirchner proposed LPN-based symmetric encryption schemes based on the LPN-C cryptosystem of Gilbert et al. LPN-C is attractive for HHE while allowing parameter choices that bound decryption failures. However, the concrete security of LPN-C and its HHE-oriented variants remains poorly understood. We quantify how enforcing bounded noise via rejection sampling reduces the observed noise rate, an effect not captured in prior analyses. This yields immediate speedups for all attacks based on LPN instance solving. We then extend the Arora-Ge-style algebraic attacks to the bounded-noise setting and derive new bounds on the dimension of the induced linear spaces, refining and partially correcting earlier analyses. We show that some parameter regimes are more robust than previously estimated, while new algebraic strategies yield the best known attacks in others. Overall, our results improve our understanding of the concrete security of LPN-based symmetric encryption schemes, informing parameter selection for FHE-friendly variants.