[Resource Topic] 2022/712: The Hardness of LPN over Any Integer Ring and Field for PCG Applications

Welcome to the resource topic for 2022/712

The Hardness of LPN over Any Integer Ring and Field for PCG Applications

Authors: Hanlin Liu, Xiao Wang, Kang Yang, and Yu Yu


The learning parity with noise (LPN) assumption has been widely studied and used in cryptography. It was recently brought to new prosperity since Boyle et al. (CCS 2018), putting LPN to a central role in designing secure multi-party computation, zero-knowledge proofs, private set intersection, and many other protocols. Although most classical LPN cryptanalysis focuses on binary field \mathbb{F}_2, recent protocols often require LPN over larger finite fields or integer rings, which are much less studied. In this paper, we thoroughly studied the concrete security of LPN problems in these settings and how it affects the protocol design. 1. We are the first to study the security of LPN over a ring \mathbb{Z}_{2^\lambda}. Although existing protocols based on LPN over integer rings use parameters as if they are over finite fields, we found an attack that effectively reduces the weight of a noise by half compared to LPN over fields. Consequently, prior works that use LPN over integer rings overestimate up to 40 bits of security. 2. We provide a complete picture of the hardness of LPN over integer rings by showing: 1) the equivalence between its search and decisional versions; 2) an efficient reduction from LPN over \mathbb{F}_{2} to LPN over \mathbb{Z}_{2^\lambda}; and 3) generalization of our results to any integer ring. 3. For LPN over finite fields, we found that prior analysis ignored some important differences between classical LPN cryptanalysis and the new settings, leading to overly conservative parameters. We show that even after bringing all classical LPN cryptanalysis to the setting over finite fields, much less weight of noises is needed for the same level of security. To improve the use of LPN assumptions for a wide range of cryptographic protocols, we provide, and plan to open source, a script that estimates the concrete security of LPN over arbitrary integer rings and finite fields.

ePrint: https://eprint.iacr.org/2022/712

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .