TY - GEN
T1 - Cryptography with auxiliary input and trapdoor from constant-noise LPN
AU - Yu, Yu
AU - Zhang, Jiang
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2016.
PY - 2016
Y1 - 2016
N2 - 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. Inspired by the “sampling from subspace” technique by Yu (eprint 2009/467) and Goldwasser et al. (ITCS 2010), we show that standard LPN can work in a mode (reducible to itself) where the constantnoise 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. Plugging this into the framework of [DKL09], we obtain the same applications as considered in [DKL09] (i.e., CPA/CCA secure symmetric encryption schemes, average-case obfuscators, reusable and robust extractors) with resilience to a more general class of leakages, improved efficiency and better security under standard assumptions. As a main contribution, under constant-noise LPN with certain subexponential hardness (i.e., 2ω(n1/2) for secret size n) we obtain a variant of the LPN with security on poly-logarithmic entropy sources, 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).
AB - 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. Inspired by the “sampling from subspace” technique by Yu (eprint 2009/467) and Goldwasser et al. (ITCS 2010), we show that standard LPN can work in a mode (reducible to itself) where the constantnoise 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. Plugging this into the framework of [DKL09], we obtain the same applications as considered in [DKL09] (i.e., CPA/CCA secure symmetric encryption schemes, average-case obfuscators, reusable and robust extractors) with resilience to a more general class of leakages, improved efficiency and better security under standard assumptions. As a main contribution, under constant-noise LPN with certain subexponential hardness (i.e., 2ω(n1/2) for secret size n) we obtain a variant of the LPN with security on poly-logarithmic entropy sources, 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).
UR - https://www.scopus.com/pages/publications/84979608924
U2 - 10.1007/978-3-662-53018-4_9
DO - 10.1007/978-3-662-53018-4_9
M3 - 会议稿件
AN - SCOPUS:84979608924
SN - 9783662530177
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 241
EP - 243
BT - Advances in Cryptology - 36th Annual International Cryptology Conference, CRYPTO 2016, Proceedings
A2 - Robshaw, Matthew
A2 - Katz, Jonathan
PB - Springer Verlag
T2 - 36th Annual International Cryptology Conference, CRYPTO 2016
Y2 - 14 August 2016 through 18 August 2016
ER -