TY - GEN
T1 - Secure obfuscation in a weak multilinear map model
AU - Garg, Sanjam
AU - Miles, Eric
AU - Mukherjee, Pratyay
AU - Sahai, Amit
AU - Srinivasan, Akshayaram
AU - Zhandry, Mark
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2016.
PY - 2016
Y1 - 2016
N2 - All known candidate indistinguishability obfuscation (iO) schemes rely on candidate multilinear maps. Until recently, the strongest proofs of security available for iO candidates were in a generic model that only allows “honest” use of the multilinear map. Most notably, in this model the zero-test procedure only reveals whether an encoded element is 0, and nothing more. However, this model is inadequate: there have been several attacks on multilinear maps that exploit extra information revealed by the zero-test procedure. In particular, Miles, Sahai and Zhandry (Crypto’16) recently gave a polynomial-time attack on several iO candidates when instantiated with the multilinear maps of Garg, Gentry, and Halevi (Eurocrypt’ 13), and also proposed a new “weak multilinear map model” that captures all known polynomial-time attacks on GGH13. In this work, we give a new iO candidate which can be seen as a small modification or generalization of the original candidate of Garg, Gentry, Halevi, Raykova, Sahai, and Waters (FOCS’13). We prove its security in the weak multilinear map model, thus giving the first iO candidate that is provably secure against all known polynomial-time attacks on GGH13. The proof of security relies on a new assumption about the hardness of computing annihilating polynomials, and we show that this assumption is implied by the existence of pseudorandom functions in NC1.
AB - All known candidate indistinguishability obfuscation (iO) schemes rely on candidate multilinear maps. Until recently, the strongest proofs of security available for iO candidates were in a generic model that only allows “honest” use of the multilinear map. Most notably, in this model the zero-test procedure only reveals whether an encoded element is 0, and nothing more. However, this model is inadequate: there have been several attacks on multilinear maps that exploit extra information revealed by the zero-test procedure. In particular, Miles, Sahai and Zhandry (Crypto’16) recently gave a polynomial-time attack on several iO candidates when instantiated with the multilinear maps of Garg, Gentry, and Halevi (Eurocrypt’ 13), and also proposed a new “weak multilinear map model” that captures all known polynomial-time attacks on GGH13. In this work, we give a new iO candidate which can be seen as a small modification or generalization of the original candidate of Garg, Gentry, Halevi, Raykova, Sahai, and Waters (FOCS’13). We prove its security in the weak multilinear map model, thus giving the first iO candidate that is provably secure against all known polynomial-time attacks on GGH13. The proof of security relies on a new assumption about the hardness of computing annihilating polynomials, and we show that this assumption is implied by the existence of pseudorandom functions in NC1.
UR - http://www.scopus.com/inward/record.url?scp=84994860468&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84994860468&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-53644-5_10
DO - 10.1007/978-3-662-53644-5_10
M3 - Conference contribution
AN - SCOPUS:84994860468
SN - 9783662536438
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 241
EP - 268
BT - Theory of Cryptography - 14th International Conference, TCC 2016-B, Proceedings
A2 - Smith, Adam
A2 - Hirt, Martin
PB - Springer Verlag
T2 - 14th International Conference on Theory of Cryptography, TCC 2016-B
Y2 - 31 October 2016 through 3 November 2016
ER -