常量噪声下带辅助输入的 LPN 公钥密码

Dodis, Kalai and Lovett (STOC 2009) initiated the study of the Learning Parity with Noise (LPN) problem with (static) exponentially hard-to-invert auxiliary input. In particular, they showed that under a new assumption (called Learning Subspace with Noise) the above is quasi-polynomially hard in the high (polynomially close to uniform) noise regime. Based on the “sampling from subspace” technique by Yu (eprint 2009/467) and Goldwasser et al. (ITCS 2010), standard LPN can work in a mode (reducible to itself) where the constant-noise LPN (by sampling its matrix from a random subspace) is robust against sub-exponentially hard-to-invert auxiliary input with comparable security to the underlying LPN. Under constant-noise LPN with certain sub-exponential hardness (i.e., 2^ω(^n1/2)) for secret size n), a variant of the LPN with security on poly-logarithmic entropy sources is obtained, which in turn implies CPA/CCA secure public-key encryption (PKE) schemes and oblivious transfer (OT) protocols. Prior to this, basing PKE and OT on constant-noise LPN had been an open problem since Alekhnovich’s work (FOCS 2003).