How to avoid obfuscation using witness PRFS

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

17 Scopus citations

Abstract

We propose a new cryptographic primitive called witness pseudorandom functions (witness PRFs). Witness PRFs are related to witness encryption, but appear strictly stronger: we show that witness PRFs can be used for applications such as multi-party key exchange without trusted setup, polynomially-many hardcore bits for any one-way function, and several others that were previously only possible using obfuscation. Thus we improve the minimal assumptions required for these applications. Moreover, current candidate obfuscators are far from practical and typically rely on unnatural hardness assumptions about multilinear maps. We give a construction of witness PRFs from multilinear maps that is simpler and much more efficient than current obfuscation candidates, thus bringing several applications of obfuscation closer to practice. Our construction relies on new but very natural hardness assumptions about the underlying maps that appear to be resistant to a recent line of attacks.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 3th International Conference, TCC 2016-A, Proceedings
EditorsTal Malkin, Eyal Kushilevitz
PublisherSpringer Verlag
Pages421-448
Number of pages28
ISBN (Print)9783662490983
DOIs
StatePublished - Jan 1 2016
Externally publishedYes
Event13th International Conference on Theory of Cryptography, TCC 2016 - Tel Aviv, Israel
Duration: Jan 10 2016Jan 13 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9563
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other13th International Conference on Theory of Cryptography, TCC 2016
CountryIsrael
CityTel Aviv
Period1/10/161/13/16

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Multilinear maps
  • Multiparty key exchange
  • Witness PRFs

Fingerprint Dive into the research topics of 'How to avoid obfuscation using witness PRFS'. Together they form a unique fingerprint.

  • Cite this

    Zhandry, M. (2016). How to avoid obfuscation using witness PRFS. In T. Malkin, & E. Kushilevitz (Eds.), Theory of Cryptography - 3th International Conference, TCC 2016-A, Proceedings (pp. 421-448). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9563). Springer Verlag. https://doi.org/10.1007/978-3-662-49099-0_16