How to avoid obfuscation using witness PRFS

Mark Zhandry

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

25 Scopus citations


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
EditorsEyal Kushilevitz, Tal Malkin
PublisherSpringer Verlag
Number of pages28
ISBN (Print)9783662490983
StatePublished - 2016
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)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other13th International Conference on Theory of Cryptography, TCC 2016
CityTel Aviv

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


  • Multilinear maps
  • Multiparty key exchange
  • Witness PRFs


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

Cite this