查看文章

The Learning Parity with Noise (LPN) problem has recently found many cryptographic applications such as authentication protocols, pseudorandom generators/functions and even asymmetric tasks including public-key encryption (PKE) schemes and oblivious transfer (OT) protocols. It however remains a long-standing open problem whether LPN implies collision resistant hash (CRH) functions. Inspired by the recent work of Applebaum et al. (ITCS 2017), we introduce a general construction of CRH from LPN for various parameter choices. We show that, just to mention a few notable ones, under any of the following hardness assumptions (for the two most common variants of LPN)

1. 1.
   constant-noise LPN is -hard for any constant ;
2. 2.
   constant-noise LPN is -hard given samples;
3. 3.
   low-noise LPN (of noise rate ) is -hard given samples.

there exists CRH functions with constant (or …