Hanlin Liu
Shanghai Qi Zhi Institute

Xiao Wang
Northwestern University

Kang Yang
State Key Laboratory of Cryptology

Yu Yu
Shanghai Jiao Tong University

Keywords:

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 F2) and noise distributions.

- 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.

- We analyze the security of LPN over a ring ZZ_2^λ. 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 ZZ_2^λ overestimate up to 40 bits of security.

- 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 F2 to LPN over ZZ_2^λ; 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.