On cryptography with auxiliary input

Yevgeniy Dodis, Yael Tauman Kalai, Shachar Lovett

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We study the question of designing cryptographic schemes which are secure even if an arbitrary function f(sk) of thesecret key is leaked, as long as the secret key sk is still (exponentially)hard to compute from this auxiliary input. Thissetting of auxiliary input is more general than the more traditionalsetting, which assumes that some of information about the secret key sk may be leaked, but sk still hashigh min-entropy left. In particular, we deal with situationswhere f(sk) information-theoretically determines the entire secret key sk. As our main result, we construct CPA/CCA secure symmetric encryption schemes that remain secure with exponentially hard-to-invert auxiliary input. We give several applications of such schemes. We construct an average-case obfuscator for the class of point functions, which remains secure with exponentially hard-to-invert auxiliary input, and is reusable. We construct a reusable and robust extractor that remains secure with exponentially hard-to-invert auxiliary input. Our results rely on a new cryptographic assumption, Learning Subspace-with-Noise (LSN), which is related to the well known Learning Parity-with-Noise (LPN) assumption.

Original languageEnglish (US)
Title of host publicationSTOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing
Pages621-630
Number of pages10
DOIs
StatePublished - 2009
Event41st Annual ACM Symposium on Theory of Computing, STOC '09 - Bethesda, MD, United States
Duration: May 31 2009Jun 2 2009

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other41st Annual ACM Symposium on Theory of Computing, STOC '09
CountryUnited States
CityBethesda, MD
Period5/31/096/2/09

Keywords

  • Auxiliary information
  • Code obfuscation
  • Encryption schemes
  • Error-correcting codes
  • Learning parity with noise
  • Randomness extractors

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'On cryptography with auxiliary input'. Together they form a unique fingerprint.

Cite this