Paper 2022/712

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

Abstract

Learning parity with noise (LPN) has been widely studied and used in cryptography. It was recently brought to new prosperity since Boyle et al. (CCS'18), putting LPN to a central role in designing secure multi-party computation, zero-knowledge proofs, private set intersection, and many other protocols. In this paper, we thoroughly studied the concrete security of LPN problems in these settings. We found that many conclusions from classical LPN cryptanalysis do not apply to this new setting due to the low noise rates, extremely high dimensions, various types (in addition to $\mathbb{F}_2$) and noise distributions. 1. For LPN over field $\mathbb{F}_q$, we give a parameterized reduction from an exact noise distribution to a regular one that not only generalizes the recent result by Feneuil, Joux and Rivain (Crypto'22), but also significantly reduces the security loss by paying only an additive price in dimension and number of samples. 2. We analyze 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 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 $\mathbb{Z}_{2^\lambda}$ overestimate up to 40 bits of security. 3. 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. 4. For LPN over finite fields, we found that prior analysis ignored some important differences between classical LPN cryptanalysis and the new setting, leading to overly conservative parameters. We show that even after bringing all classical LPN cryptanalysis, including the latest SD $2.0$ analysis (Asiacrypt'22), 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 an open-sourced script that estimates the concrete security of LPN over integer rings and finite fields.