Paper 2016/514
Cryptography with Auxiliary Input and Trapdoor from Constant-Noise LPN
Yu Yu and Jiang Zhang
Abstract
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 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. 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 sub-exponential hardness (i.e.,
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A minor revision of an IACR publication in CRYPTO 2016
- Keywords
- Cryptography with Auxiliary InputLearning Parity with NoisePost-quantum CryptographyPublic-Key Encryption
- Contact author(s)
- yuyuathk @ gmail com
- History
- 2016-05-30: revised
- 2016-05-29: received
- See all versions
- Short URL
- https://ia.cr/2016/514
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2016/514, author = {Yu Yu and Jiang Zhang}, title = {Cryptography with Auxiliary Input and Trapdoor from Constant-Noise {LPN}}, howpublished = {Cryptology {ePrint} Archive, Paper 2016/514}, year = {2016}, url = {https://eprint.iacr.org/2016/514} }