TY - GEN
T1 - How to avoid obfuscation using witness PRFS
AU - Zhandry, Mark
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2016.
PY - 2016
Y1 - 2016
N2 - 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.
AB - 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.
KW - Multilinear maps
KW - Multiparty key exchange
KW - Witness PRFs
UR - http://www.scopus.com/inward/record.url?scp=84954185814&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84954185814&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-49099-0_16
DO - 10.1007/978-3-662-49099-0_16
M3 - Conference contribution
AN - SCOPUS:84954185814
SN - 9783662490983
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 421
EP - 448
BT - Theory of Cryptography - 3th International Conference, TCC 2016-A, Proceedings
A2 - Kushilevitz, Eyal
A2 - Malkin, Tal
PB - Springer Verlag
T2 - 13th International Conference on Theory of Cryptography, TCC 2016
Y2 - 10 January 2016 through 13 January 2016
ER -