Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Multilinear maps, obfuscation

Date: received 29 Apr 2014, last revised 8 Mar 2015

Contact author: mzhandry at stanford edu

Available format(s): PDF | BibTeX Citation

Note: Mostly typo fixes.

Version: 20150308:185722 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]