Paper 2022/712

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

Hanlin Liu, Shanghai Jiao Tong University
Xiao Wang, Northwestern University
Kang Yang, State Key Laboratory of Cryptology
Yu Yu, Shanghai Jiao Tong University, Shanghai Qizhi Institute
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.

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
2023-02-18: last of 4 revisions
2022-06-04: received
See all versions
Short URL
https://ia.cr/2022/712
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2022/712}},
      url = {https://eprint.iacr.org/2022/712}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.