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 security of LPN problems in this particular context. We found that some important aspects have long been ignored and 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 a field, we give a parameterized reduction from exact-noise LPN to regular-noise LPN. Compared to the recent result by Feneuil, Joux and Rivain (Crypto'22), we significantly reduce the security loss by paying only a small additive price in dimension and number of samples. 2. We analyze the security of LPN over a ring $\mathbb{Z}_{2^\lambda}$. Existing protocols based on LPN over integer rings use parameters as if they are over fields, but 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. Finally, we provide an all-in-one estimator tool for the bit security of LPN parameters in the context of PCG, incorporating the recent advanced attacks.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Learning parity with noiseinteger rings and fieldspseudorandom correlation generator
- Contact author(s)
-
hans1024 @ sjtu edu cn
wangxiao @ cs northwestern edu
yangk @ sklc org
yuyu @ yuyu hk - History
- 2024-02-26: last of 6 revisions
- 2022-06-04: received
- See all versions
- Short URL
- https://ia.cr/2022/712
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/712, author = {Hanlin Liu and Xiao Wang and Kang Yang and Yu Yu}, title = {The Hardness of {LPN} over Any Integer Ring and Field for {PCG} Applications}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/712}, year = {2022}, url = {https://eprint.iacr.org/2022/712} }