# Are Graded Encoding Schemes broken yet?

## Table of Contents

## Introduction

A quick overview of attacks on Graded Encoding Schemes. If you find anything wrong, misleading or outdated, please let us know. Note that you can check the last modification date of this website by consulting the corresponding GitHub repository.

We split the attacks into those directly on graded encoding schemes and those that affect indistinguishability obfuscation (iO) constructions. We consider an iO construction broken, if it is broken for **any** circuit. In contrast, Appendix A of EPRINT:AJNSY16 — which partly informed this page — takes a much more optimistic view.

### Contributing

If you wish to contribute/correct a mistake, feel free to send a pull request to malb/malb.github.io.

#### Contributors

- Martin Albrecht
- Alex Davidson

## Concrete Graded Encoding Schemes

### GGH13 paper

We describe plausible lattice-based constructions with properties that approximate the sought-after multilinear maps in hard-discrete-logarithm groups, and show an example application of such multi-linear maps that can be realized using our approximation. The security of our constructions relies on seemingly hard problems in ideal lattices, which can be viewed as extensions of the assumed hardness of the NTRU function. – EC:GarGenHal13

#### BROKEN MDDH hardness

Polynomial-time attack in EC:HuJia16.

#### BROKEN General

Subexponential classical and quantum polynomial time attack without encodings of zero or using the zero-testing parameter in EPRINT:AlbBaiDuc16 for large levels of multilinearity κ. Polynomial-time attack without low-level encodings of zero for large levels of multilinearity κ in EPRINT:CheJeoLee16.

#### BROKEN Follow-Up Constructions

Attacks on GGH13 also apply to these follow-up constructions, which reduce parameter sizes.

### CLT13 paper

Extending bilinear elliptic curve pairings to multilinear maps is a long-standing open problem. The first plausible construction of such multilinear maps has recently been described by Garg, Gentry and Halevi, based on ideal lattices. In this paper we describe a different construction that works over the integers instead of ideal lattices, similar to the DGHV fully homomorphic encryption scheme. We also describe a different technique for proving the full randomization of encodings: instead of Gaussian linear sums, we apply the classical leftover hash lemma over a quotient lattice. We show that our construction is relatively practical: for reasonable security parameters a one-round 7-party Diffie-Hellman key exchange requires less than 40 seconds per party. Moreover, in contrast with previous work, multilinear analogues of useful, base group assumptions like DLIN appear to hold in our setting. — C:CorLepTib13

#### BROKEN MDDH hardness

Polynomial-time attack in EC:CHLRS15.

#### BROKEN Follow-Up Construction

C:CorLepTib15 was put forward in response to the attack in EC:CHLRS15, but was broken in polynomial time for all applications in EPRINT:MinFou15 and EPRINT:CheLeeRyu15.

### GGH15 paper

Graded multilinear encodings have found extensive applications in cryptography ranging from non-interactive key exchange protocols, to broadcast and attribute-based encryption, and even to software obfuscation. Despite seemingly unlimited applicability, essentially only two candidate constructions are known (GGH and CLT). In this work, we describe a new graphinduced multilinear encoding scheme from lattices. In a graph-induced multilinear encoding scheme the arithmetic operations that are allowed are restricted through an explicitly defined directed graph (somewhat similar to the “asymmetric variant” of previous schemes). Our construction encodes Learning With Errors (LWE) samples in short square matrices of higher dimensions. Addition and multiplication of the encodings corresponds naturally to addition and multiplication of the LWE secrets. — TCC:GenGorHal15

#### BROKEN MDDH hardness

Polynomial-time attack in C:CLLT16 for GGH15.

### MZ17 paper

We devise the first weak multilinear map model for CLT13 multilinear maps (Coron et al., CRYPTO 2013) that captures all known classical polynomial-time attacks on the maps. We then show important applications of our model. First, we show that in our model, several existing obfuscation and order-revealing encryption schemes, when instantiated with CLT13 maps, are secure against known attacks under a mild algebraic complexity assumption used in prior work. These are schemes that are actually being implemented for experimentation. However, until our work, they had no rigorous justification for security. Next, we turn to building constant degree multilinear maps on top of CLT13 for which there are no known attacks . Precisely, we prove that our scheme achieves the ideal security notion for multilinear maps in our weak CLT13 model, under a much stronger variant of the algebraic complexity assumption used above. Our multilinear maps do not achieve the full functionality of multilinear maps as envisioned by Boneh and Silverberg (Contemporary Mathematics, 2003), but do allow for re-randomization and for encoding arbitrary plaintext elements

#### STANDING MDDH hardness

Not proven to be hard, no attacks as of yet.

#### STANDING CLT13 zeroizing attacks

Zeroizing attacks on CLT13 are not possible (in idealised model) based on the hardness of the 'Vector-input Branching Program Unannihilatibility Assumption'.

## Indistinguishability Obfuscation

### GGH13

#### Single-Input Branching Programs

- EC:BGKPS14 is broken in polynomial time in C:MilSahZha16.
- EPRINT:AGIS14 is broken in polynomial time in C:MilSahZha16.
- TCC:BraRot14 is broken in polynomial time in C:MilSahZha16.
- EPRINT:BMSZ15 is broken in polynomial time in C:MilSahZha16.
- C:PasSetTel14 is broken in polynomial time in C:MilSahZha16.
- FOCS:GGHRSW13 break in EC:CheGenHal17 but
**repaired**in EPRINT:FerRasSah16 - EPRINT:GMMSSZ16 break in EC:CheGenHal17 but
**repaired**in EPRINT:FerRasSah16

#### Dual-Input Branching Programs

- EC:BGKPS14 is broken in polynomial time in C:MilSahZha16.
- EPRINT:AGIS14 is broken in polynomial time in C:MilSahZha16.
- TCC:BraRot14 is broken in polynomial time in C:MilSahZha16.
- EPRINT:BMSZ15 is broken in polynomial time in C:MilSahZha16.
- C:PasSetTel14 is broken in polynomial time in C:MilSahZha16.
- TCC:GMMSSZ16 is
**standing**.

### CLT13

#### Single-Input Branching Programs

All constructions were fixed in EPRINT:FerRasSah16.

Previously constructions of

were broken by PKC:CLLT17 and C:CGHLMM15.

#### STANDING Dual-Input Branching Programs

All dual-input constructions are currently standing and were unaffected by previous attacks in PKC:CLLT17.

#### BROKEN Direct

- EC:Zimmerman15 broken in polynomial time in C:CGHLMM15.
- TCC:AppBra15 broken in polynomial time in C:CGHLMM15.

### GGH15

#### BROKEN Branching Programs

- FOCS:GGHRSW13 is broken in subexponential-time (classical) and quantum polynomial-time attack in EC:CheGenHal17 The "subexponential-time classical or quantum polynomial-time" part is used to recover the small multiplicative bundling scalars from the (possibly big representatives of the) ideals, to conduct the final mixed-input attack. The first few steps that are used to recover these ideals take classical polynomial time.

### MZ17

No known constructions of obfuscators

# Bibliography

- [EPRINT:AJNSY16] Prabhanjan Ananth, Aayush Jain, Moni Naor, , Amit Sahai & Eylon Yogev, Universal Obfuscation and Witness Encryption: Boosting Correctness and Combining Security, , , (2016).
- [EC:GarGenHal13] Sanjam Garg, Craig Gentry & Shai Halevi, Candidate Multilinear Maps from Ideal Lattices, 1-17, in in: EUROCRYPT~2013, edited by Thomas Johansson & Phong Nguyen, Springer, Heidelberg (2013)
- [EC:HuJia16] Yupu Hu & Huiwen Jia, Cryptanalysis of GGH Map, 537-565, in in: EUROCRYPT~2016, Part~I, edited by Marc Fischlin & Jean-S\'ebastien Coron, Springer, Heidelberg (2016)
- [EPRINT:AlbBaiDuc16] Martin Albrecht, Shi Bai & L\'eo Ducas, A subfield lattice attack on overstretched NTRU assumptions: Cryptanalysis of some FHE and Graded Encoding Schemes, , , (2016).
- [EPRINT:CheJeoLee16] Jung Hee Cheon, Jinhyuck Jeong & Changmin Lee, An Algorithm for NTRU Problems and Cryptanalysis of the GGH Multilinear Map without a Low Level Encoding of Zero, , , (2016).
- [EC:LanSteSte14] Adeline Langlois, Damien Stehl\'e, & Ron Steinfeld, GGHLite: More Efficient Multilinear Maps from Ideal Lattices, 239-256, in in: EUROCRYPT~2014, edited by Phong Nguyen & Elisabeth Oswald, Springer, Heidelberg (2014)
- [AC:ACLL15] Martin Albrecht, Catalin Cocis, , Fabien Laguillaumie & Adeline Langlois, Implementing Candidate Graded Encoding Schemes from Ideal Lattices, 752-775, in in: ASIACRYPT~2015, Part~II, edited by Tetsu Iwata & Jung Hee Cheon, Springer, Heidelberg (2015)
- [C:CorLepTib13] Jean-S\'ebastien Coron, Tancr\`ede Lepoint, & Mehdi Tibouchi, Practical Multilinear Maps over the Integers, 476-493, in in: CRYPTO~2013, Part~I, edited by Ran Canetti & Juan Garay, Springer, Heidelberg (2013)
- [EC:CHLRS15] Jung Hee Cheon, Kyoohyung Han, Changmin Lee, , Hansol Ryu & Damien Stehl\'e, Cryptanalysis of the Multilinear Map over the Integers, 3-12, in in: EUROCRYPT~2015, Part~I, edited by Elisabeth Oswald & Marc Fischlin, Springer, Heidelberg (2015)
- [C:CorLepTib15] Jean-S\'ebastien Coron, Tancr\`ede Lepoint, & Mehdi Tibouchi, New Multilinear Maps Over the Integers, 267-286, in in: CRYPTO~2015, Part~I, edited by Rosario Gennaro & Matthew Robshaw, Springer, Heidelberg (2015)
- [EPRINT:MinFou15] Brice Minaud & Pierre-Alain Fouque, Cryptanalysis of the New Multilinear Map over the Integers, , , (2015).
- [EPRINT:CheLeeRyu15] Jung Hee Cheon, Changmin Lee & Hansol Ryu, Cryptanalysis of the New CLT Multilinear Maps, , , (2015).
- [TCC:GenGorHal15] Craig Gentry, Sergey Gorbunov & Shai Halevi, Graph-Induced Multilinear Maps from Lattices, 498-527, in in: TCC~2015, Part~II, edited by Yevgeniy Dodis & Jesper Buus Nielsen, Springer, Heidelberg (2015)
- [C:CLLT16] Jean-S\'ebastien Coron, Moon Sung Lee, , Tancr\`ede Lepoint & Mehdi Tibouchi, Cryptanalysis of GGH15 Multilinear Maps, 607-628, in in: CRYPTO~2016, Part~II, edited by Matthew Robshaw & Jonathan Katz, Springer, Heidelberg (2016)
- [EC:BGKPS14] Boaz Barak, Sanjam Garg, Yael Tauman Kalai, , Omer Paneth & Amit Sahai, Protecting Obfuscation against Algebraic Attacks, 221-238, in in: EUROCRYPT~2014, edited by Phong Nguyen & Elisabeth Oswald, Springer, Heidelberg (2014)
- [C:MilSahZha16] Eric Miles, Amit Sahai & Mark Zhandry, Annihilation Attacks for Multilinear Maps: Cryptanalysis of Indistinguishability Obfuscation over GGH13, 629-658, in in: CRYPTO~2016, Part~II, edited by Matthew Robshaw & Jonathan Katz, Springer, Heidelberg (2016)
- [EPRINT:AGIS14] Prabhanjan Ananth, Divya Gupta, Yuval Ishai, & Amit Sahai, Optimizing Obfuscation: Avoiding Barrington's Theorem, , , (2014).
- [TCC:BraRot14] Zvika Brakerski & Guy Rothblum, Virtual Black-Box Obfuscation for All Circuits via Generic Graded Encoding, 1-25, in in: TCC~2014, edited by Yehuda Lindell, Springer, Heidelberg (2014)
- [EPRINT:BMSZ15] Saikrishna Badrinarayanan, Eric Miles, , Amit Sahai & Mark Zhandry, Post-Zeroizing Obfuscation: The case of Evasive Circuits, , , (2015).
- [C:PasSetTel14] Rafael Pass, Karn Seth & Sidharth Telang, Indistinguishability Obfuscation from Semantically-Secure Multilinear Encodings, 500-517, in in: CRYPTO~2014, Part~I, edited by Juan Garay & Rosario Gennaro, Springer, Heidelberg (2014)
- [FOCS:GGHRSW13] Sanjam Garg, Craig Gentry, Shai Halevi, , Mariana Raykova, Amit Sahai & Brent Waters, Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits, 40-49, in in: 54th FOCS, edited by IEEE Computer Society Press (2013)
- [EC:CheGenHal17] Yilei Chen, Craig Gentry & Shai Halevi, Cryptanalyses of Candidate Branching Program Obfuscators, 278-307, in in: EUROCRYPT~2017, Part~II, edited by Jean-S\'ebastien Coron & Jesper Buus Nielsen, Springer, Heidelberg (2017)
- [EPRINT:FerRasSah16] Rex Fernando, Peter Rasmussen, & Amit Sahai, Preventing CLT Attacks on Obfuscation with Linear Overhead, , , (2016).
- [EPRINT:GMMSSZ16] Sanjam Garg, Eric Miles, Pratyay Mukherjee, , Amit Sahai, Akshayaram Srinivasan, & Mark Zhandry, Secure Obfuscation in a Weak Multilinear Map Model, , , (2016).
- [TCC:GMMSSZ16] Sanjam Garg, Eric Miles, Pratyay Mukherjee, , Amit Sahai, Akshayaram Srinivasan, & Mark Zhandry, Secure Obfuscation in a Weak Multilinear Map Model, 241-268, in in: TCC~2016-B, Part~II, edited by Martin Hirt & Adam Smith, Springer, Heidelberg (2016)
- [PKC:CLLT17] Jean-S\'ebastien Coron, Moon Sung Lee, , Tancr\`ede Lepoint & Mehdi Tibouchi, Zeroizing Attacks on Indistinguishability Obfuscation over CLT13, 41-58, in in: PKC~2017, Part~I, edited by Serge Fehr, Springer, Heidelberg (2017)
- [C:CGHLMM15] Jean-S\'ebastien Coron, Craig Gentry, , Shai Halevi, Tancr\`ede Lepoint, , Hemanta Maji, Eric Miles, Mariana Raykova, , Amit Sahai & Mehdi Tibouchi, Zeroizing Without Low-Level Zeroes: New MMAP Attacks and their Limitations, 247-266, in in: CRYPTO~2015, Part~I, edited by Rosario Gennaro & Matthew Robshaw, Springer, Heidelberg (2015)
- [EC:Zimmerman15] Joe Zimmerman, How to Obfuscate Programs Directly, 439-467, in in: EUROCRYPT~2015, Part~II, edited by Elisabeth Oswald & Marc Fischlin, Springer, Heidelberg (2015)
- [TCC:AppBra15] Benny Applebaum & Zvika Brakerski, Obfuscating Circuits via Composite-Order Graded Encoding, 528-556, in in: TCC~2015, Part~II, edited by Yevgeniy Dodis & Jesper Buus Nielsen, Springer, Heidelberg (2015)