Introduction

Regarding the concern on the current complex situation toward to construct secure obfuscation, we summarize the current security status of recent constructions of iO. We particularly focus on obfuscations based on multilinear map (Mmap) here, since some of them have been attacked by recent several attacks while the other of them have been survived.

We remark that some parts of the previous survey by Albrecht and Davidson [link] informed some parts of this survey.

Last update: 22, April, 2020

Note: In 18, August, 2020, Jain, Lin and Sahai claimed to construct iO from well-founded assumptions. See [link].

Contributors

Minki Hhan (Seoul National University), hhan_@snu.ac.kr

Jiseung Kim (Seoul National University), tory154@snu.ac.kr

Wonhee Cho (Seoul National University), wony0404@snu.ac.kr

If you find any error or out-of-date information, please let us know by sending e-mail or any other method.

Indistinguishability Obfuscation: current states

We put three different state "STANDING", "BROKEN" for each constructions. STANDING means there is no known attack (except trivial exponential time attacks) and BROKEN says that there is/are attack(s).

For broken obfuscations we usually put ":quantum", ":param" and ":bpclass" for noting the type of attacks. In particular, BROKEN:bpclass states that there are attacks for certain class of branching programs, e.g. input-partitionable or constant-input-repitition. Note that BROKEN:bpclass does not imply the iO candidate fails to obfuscate all circuits since there are many methods to transform circuits to BPs. In particular, [Bar86], [AGIS14], [CVW18] gives such methods, and [FRS17] gives a way to avoid the certain BP class that are broken already. (More precisely, it gives a way to avoid input-partitionable BPs)

We also remark that we do not include the direct attack on multilinear maps (or other applications of it) for avoiding confusion.

(For example, we exclude the seminal zeroizing attack [CHRLS15] on [CLT13]; while it completely breaks key exchange protocol based on [CLT13], it does not break iO schemes.)

[GGH13]-based constructions

BP Constructions

[GGHRSW13] BROKEN:bpclass by [CGH17] and BROKEN:param by [CHKL18a]

[BR14], [PST14], [AGIS14], [MSW14], [BGKPS14], [BMSZ16] BROKEN:bpclass by [MSZ16], [ADGM17] and BROKEN:param by [CHKL18a]

[GMMSSZ16] BROKEN:quantum by [Pel18] and BROKEN:param by [CHKL18a]

[FRS17] + others BROKEN:param by [CHKL18a] (but there is no formal statement in literature)

Direct Constructions

[AB15], [Zim15], [DGG+16] BROKEN:quantum by [Pel18]

Attacks

[MSZ16], [ADGM17], [CGH17], [Pel18], [CHKL18a]

[CLT13]-based constructions

Single-input BPs

[GGHRSW13] BROKEN:bpclass by [CGH+15]

[BR14], [MSW14], [AGIS14], [PST14], [BMSZ16], [GMMSSZ16] BROKEN:bpclass by [CLLT17]

[FRS17] + others: STANDING

Dual-input BPs

No known attacks for this type of BPs.

[BGKPS14], [BMSZ16] STANDING. In particular, provably secure in weak CLT13 model [MZ18]

Direct Constructions

[AB15], [Zim15] BROKEN:bpclass by [CGH+15]

Attacks

[CGH+15], [CLLT17]

[GGH15]-based constructions

[GGHRSW13] BROKEN:bpclass by [CVW18] rank attack for constant input-repetition, and BROKEN:quantum by [CGH17]

[HHSS17] BROKEN by left kernel attack [CHKL18b], subtraction attack [CVW18]

[CVW18] BROKEN:param by statistical zeroizing attack [CCHKL19]

[BGMZ18] STANDING. In particular this construction is provable secure under weak (algebraic) GGH15 model. But statistical zeroizing attack [CCHKL19] is applicable to some parameters and shows the security in algebraic GGH15 model is not enough to achieve ideal security of obfuscation.

[CHVW19] STANDING. In particular, provably secure in new weak GGH15 model that encompass both statistical and algebraic zeroizing attack.

Attacks

[CGH17], [CVW18], [CHKL18b], [CCHKL19]

Recommendation: [Yilei Chen's talk] gives a wonderful introduction to the status of GGH15-based obfuscation

Implementations

5Gen

5Gen-C

[HHSS17]

Other Constructions

Disclaimer (22. April. 2020): We do not scrutinize the papers related to these topics. In particular, we do not include the current state of low degree prgs over R (and other variants) and related attacks here.

To see the current status of these topics, see lattice seminar held in Simon institute: [Link].

Toward Removing Mmaps from iO

All of the following papers are unknown to be secure with any choice of concrete multilinear maps.

[Lin16]

[LV16]

[Lin17]

[LT17]

[Arg19]: In particular, this candidate does NOT use Mmap. Based on Noise linear FE.

[ALMS19]

[AJLMS19] = [LM18] + [AJS18]

[AP20]

[JLS19]

iO from Other Primitives

[GJ18]: based on tensor product

[BDGM20]: iO from split FHE

Impossibility of Various Obfuscations

References

Mmaps and attacks:

[GGH13] Garg, Sanjam, Craig Gentry, and Shai Halevi. Candidate multilinear maps from ideal lattices. (Eurocrypt 2013)

[CLT13] Coron, Jean-Sébastien, Tancrede Lepoint, and Mehdi Tibouchi. Practical multilinear maps over the integers. (Crypto 2013)

[GGH15] Gentry, Craig, Sergey Gorbunov, and Shai Halevi. Graph-induced multilinear maps from lattices. (TCC 2015)

[CHLRS15] Jung Hee Cheon, Kyoohyung Han, Changmin Lee, Hansol Ryu, Damien Stehlé. Cryptanalysis of the multilinear map over the integers. (Eurocrypt 2015)

IO based on Mmaps:

[GGHRSW13] Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. (FOCS 2013, SICOMP 2016)

[BR14] Zvika Brakerski and Guy N Rothblum. Virtual black-box obfuscation for all circuits via generic graded encoding. (TCC 2014)

[PST14] Rafael Pass, Karn Seth, and Sidharth Telang. Indistinguishability obfuscation from semantically-secure multilinear encodings. (Crypto 2014)

[AGIS14] Prabhanjan Ananth, Divya Gupta, Yuval Ishai, and Amit Sahai. Optimizing obfuscation: Avoiding barrington’s theorem. (CCS 2014)

[MSW14] Eric Miles, Amit Sahai, and Mor Weiss. Protecting obfuscation against arithmetic attacks. (eprint 2014/878)

[BGKPS14] Boaz Barak, Sanjam Garg, Yael Tauman Kalai, Omer Paneth, and Amit Sahai. Protecting obfuscation against algebraic attacks. (Eurocrypt 2014)

[AB15] Benny Applebaum and Zvika Brakerski. Obfuscating circuits via composite-order graded encoding. (TCC 2015)

[Zim15] Joe Zimmerman. How to obfuscate programs directly. (Eurocrypt 2015)

[CGH+15] Jean-S´ebastien Coron, Craig Gentry, Shai Halevi, Tancr`ede Lepoint, Hemanta K. Maji, Eric Miles, Mariana Raykova, Amit Sahai, and Mehdi Tibouchi. Zeroizing without low-level zeroes: New MMAP attacks and their limitations. (Crypto 2015)

[BMSZ16] Saikrishna Badrinarayanan, Eric Miles, Amit Sahai, and Mark Zhandry. Post-zeroizing obfuscation: New mathematical tools, and the case of evasive circuits. (Eurocrypt 2016)

[DGG+16] Nico Döttling, Sanjam Garg, Divya Gupta, Peihan Miao, Pratyay Mukherjee. Obfuscation from low loise multilinear maps. (eprint 2016, Indocrypt 2018)

[GMMSSZ16] Sanjam Garg, Eric Miles, Pratyay Mukherjee, Amit Sahai, Akshayaram Srinivasan, and Mark Zhandry. Secure obfuscation in a weak multilinear map model. (TCC 2016)

[MSZ16] Eric Miles, Amit Sahai, and Mark Zhandry. Annihilation attacks for multilinear maps: Cryptanalysis of indistinguishability obfuscation over GGH13. (Crypto 2016)

[FRS17] Rex Fernando, Peter M. R. Rasmussen, and Amit Sahai. Preventing CLT attacks on obfuscation with linear overhead. (Asiacrypt 2017)

[ADGM17] Daniel Apon, Nico Dottling, Sanjam Garg, and Pratyay Mukherjee. Cryptanalysis ¨ of indistinguishability obfuscations of circuits over GGH13. (ICALP 2017)

[CGH17] Yilei Chen, Craig Gentry, and Shai Halevi. Cryptanalyses of candidate branching program obfuscators. (Eurocrypt 2017)

[CLLT17] Jean-Sebastien Coron, Moon Sung Lee, Tancr ´ ede Lepoint, and Mehdi Tibouchi. Zeroizing attacks on indistinguishability obfuscation over CLT13. (PKC 2017)

[HHSS17] Shai Halevi, Tzipora Halevi, Victor Shoup, and Noah Stephens-Davidowitz. Implementing BP-obfuscation using graph-induced encoding. (CCS 2017)

[Pel18] Alice Pellet-Mary. Quantum attacks against indistinguishablility obfuscators proved secure in the weak multilinear map model. (Crypto 2018)

[CHKL18a] Jung Hee Cheon, Minki Hhan, Jiseung Kim, and Changmin Lee. Cryptanalyses of branching program obfuscations over GGH13 multilinear map from the NTRU problem. (Crypto 2018)

[CVW18] Yilei Chen, Vinod Vaikuntanathan, and Hoeteck Wee. Ggh15 beyond permutation branching programs: Proofs, attacks, and candidates. (Crypto 2018)

[BGMZ18] James Bartusek, Jiaxin Guan, Fermi Ma, and Mark Zhandry. Return of ggh15: Provable security against zeroizing attacks. (TCC 2018)

[CHKL18b] Jung Hee Cheon, Minki Hhan, Jiseung Kim, and Changmin Lee. Cryptanalysis on the HHSS obfuscation arising from absence of safeguards. (ACCESS 2018)

[CHVW19] Yilei Chen, Minki Hhan, Vinod Vaikuntanathan, and Hoeteck Wee. Matrix PRFs: Constructions, Attacks, and Applications to Obfuscation. (TCC 2019)

[CCHKL19] Jung Hee Cheon, Wonhee Cho, Minki Hhan, Jiseung Kim, Changmin Lee. Statistical zeroizing attack: Cryptanalysis of candidates of bp obfuscation over ggh15 multilinear map . (Crypto 2019)

iO (toward) without mmaps:

[Lin16] Huijia Lin. Indistinguishability obfuscation from constant-degree graded encoding schemes. (Eurocrypt 2016)

[LV16] Huijia Lin and Vinod Vaikuntanathan. Indistinguishability obfuscation from ddh like assumptions on constant-degree graded encodings. (FOCS 2016)

[Lin17] Huijia Lin. Indistinguishability obfuscation from sxdh on 5-linear maps and locality-5 prgs. (Crypto 2017)

[LT17] Huijia Lin and Stefano Tessaro. Indistinguishability obfuscation from trilinear maps and block-wise local prgs. (Crypto 2017)

[LM18] Huijia Lin and Christian Matt. Pseudo Flawed-Smudging Generators and Their Applications to Indistinguishability Obfuscation. (eprint 2018/646)

[AJS18] Prabhanjan Ananth, Aayush Jain, and Amit Sahai. Indistinguishability Obfuscation Without Multilinear Maps: iO from LWE, Bilinear Maps, and Weak Pseudorandomness. (eprint 2018/615)

[GJ18]Craig Gentry, Charanjit S. Jutla. Obfuscation Using Tensor Products. (eprint 2018/756)

[Arg19] Shweta Agrawal. Indistinguishability Obfuscation Without Multilinear Maps: New methods for Bootstrapping and Instantiation. (Eurocrypt 2019)

[ALMS19] Aayush Jain, Huijia Lin, Christian Matt, and Amit Sahai. How to Leverage Hardness of Constant-Degree Expanding Polynomials over R to build iO. (Eurocrypt 2019)

[AJLMS19] Prabhanjan Ananth, Aayush Jain, Huijia Lin, Christian Matt, Amit Sahai, Indistinguishability Obfuscation Without Multilinear Maps: New Paradigms via Low Degree Weak Pseudorandomness and Security Amplification. (Crypto 2019), Merged version of [LM18] and [AJS18]

[AP20] Shweta Agrawal and Alice Pallet-Mary, Indistinguishability Obfuscation Without Maps: Attacks and Fixes for Noisy Linear FE. (Eurocrypt 2020)

[BDGM20] Zvika Brakerski, Nico Döttling, Sanjam Garg, Giulio Malavolta. Candidate iO from Homomorphic Encryption Schemes. (Eurocrypt 2020)

[JLS19] Aayush Jain, Huijia Lin, Amit Sahai. Simplifying Constructions and Assumptions for iO. (eprint 2019/1252)