Paper 2022/712

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

Hanlin Liu, Shanghai Jiao Tong University, Shanghai Qi Zhi Institute
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 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
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},
      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.