Cryptology City

[YZ16] Cryptography with Auxiliary Input and Trapdoor from Constant-Noise LPN

Authors: Yu Yu, Jiang Zhang | Venue: CRYPTO 2016 | Source

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., for secret size ) 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).

BibTeX

@Inproceedings{C:YuZha16,
  author = {Yu Yu and Jiang Zhang},
  title = {Cryptography with Auxiliary Input and Trapdoor from Constant-Noise {LPN}},
  pages = {214--243},
  editor = {Matthew Robshaw and Jonathan Katz},
  booktitle = {Advances in Cryptology -- {CRYPTO}~2016, Part~I},
  volume = {9814},
  series = {Lecture Notes in Computer Science},
  address = {Santa Barbara, CA, USA},
  month = {aug~14--18},
  publisher = {Springer Berlin Heidelberg, Germany},
  year = {2016},
  doi = {10.1007/978-3-662-53018-4_9},
}

Graph View

Backlinks