Paper 2014/301

How to Avoid Obfuscation Using Witness PRFs

Mark Zhandry

Abstract

We propose a new cryptographic primitive called \emph{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 trsuted setup, polynomially-many hardcore bits for any one-way function, and several others that were previously only possible using obfuscation. 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.

Note: Mostly typo fixes.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Multilinear mapsobfuscation
Contact author(s)
mzhandry @ stanford edu
History
2015-03-08: last of 3 revisions
2014-04-30: received
See all versions
Short URL
https://ia.cr/2014/301
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/301,
      author = {Mark Zhandry},
      title = {How to Avoid Obfuscation Using Witness PRFs},
      howpublished = {Cryptology ePrint Archive, Paper 2014/301},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/301}},
      url = {https://eprint.iacr.org/2014/301}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.