# Are Graded Encoding Scheme 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.

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

## Graded Encoding Schemes

### GGH13

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 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.

#### BROKEN Key Exchange

Polynomial-time attack in EC:HuJia16.

### CLT13

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 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.

#### BROKEN Key Exchange

Polynomial-time attack in EC:CHLRS15.

### GGH15

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 Key Exchange

Polynomial-time attack in EPRINT:Coron15 for GGH15.

## Indistinguishability Obfuscation

### GGH13

#### Single-Input Branching Programs

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

#### Dual-Input Branching Programs

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

### CLT13

#### Single-Input Branching Programs

All constructions were fixed in EPRINT:FerRasSah16. Previously constructions of

were broken by EPRINT:CorLeeLepTib16 and C:CGHLMMRST15.

#### STANDING Dual-Input Branching Programs

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

#### BROKEN Direct

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

### GGH15

#### BROKEN Branching Programs

- FOCS:GGHRSW13 is broken in subexponential-time (classical) and quantum polynomial-time attack in EPRINT:CheGenHal16 This attack reveals a basis for the ideal generated by g and therefore we consider this a valid break

# Bibliography

- [EPRINT:AJNSY16] Prabhanjan Ananth, Aayush Jain, Moni Naor, Amit Sahai & Eylon Yogev, Universal Obfuscation and Witness Encryption: Boosting Correctness and Combining Security,
*IACR Cryptology ePrint Archive*,**2016**, 281 (2016). link. - [EC:GarGenHal13] Garg, Gentry & Halevi, Candidate Multilinear Maps from Ideal Lattices, 1-17, in in: EUROCRYPT, edited by Johansson & Nguyen, (2013)
- [EPRINT:AlbBaiDuc16] Martin Albrecht, Shi Bai & Léo Ducas, A subfield lattice attack on overstretched NTRU assumptions: Cryptanalysis of some FHE and Graded Encoding Schemes,
*IACR Cryptology ePrint Archive*,**2016**, (2016). link. - [EPRINT:CheJeoLee16] Jung Hee Cheon, Jinhyuck Jeong & Changmin Lee, An Algorithm for NTRU Problems and Cryptanalysis of the GGH Multilinear Map without an encoding of zero,
*IACR Cryptology ePrint Archive*,**2016**, (2016). link. - [EC:LanSteSte14] Adeline Langlois, Damien Stehlé & Ron Steinfeld, GGHLite: More Efficient Multilinear Maps from Ideal Lattices, 239-256, in in: EUROCRYPT, edited by Phong Nguyen & Elisabeth Oswald, (2014)
- [AC:ACLL15] Albrecht, Cocis, Laguillaumie & Langlois, Implementing candidate graded encoding schemes from ideal lattices, 752-775, in in: ASIACRYPT, edited by Iwata & Cheon, Springer (2015)
- [EC:HuJia16] Yupu Hu & Huiwen Jia, Cryptanalysis of GGH Map, 537-565, in in: Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I, edited by Marc Fischlin & Jean-S\'ebastien Coron, Springer (2016)
- [C:CorLepTib13] Jean-Sébastien Coron, Tancrède Lepoint & Mehdi Tibouchi, Practical Multilinear Maps over the Integers, 476-493, in in: CRYPTO, edited by Ran Canetti & Juan Garay, (2013)
- [C:CorLepTib15] Jean-Sébastien Coron, Tancrède Lepoint & Mehdi Tibouchi, New Multilinear Maps Over the Integers, 267-286, in in: CRYPTO, edited by Rosario Gennaro & Matthew Robshaw, (2015)
- [EC:CHLRS15] Jung Hee Cheon, Kyoohyung Han, Changmin Lee, Hansol Ryu & Damien Stehlé, Cryptanaxlysis of the Multilinear Map over the Integers, 3-12, in in: EUROCRYPT, edited by Elisabeth Oswald & Marc Fischlin, (2015)
- [EPRINT:MinFou15] Brice Minaud & Pierre-Alain Fouque, Cryptanalysis of the New Multilinear Map over the Integers,
*IACR Cryptology ePrint Archive*,**2015**, (2015). link. - [EPRINT:CheLeeRyu15] Jung Hee Cheon, Changmin Lee & Hansol Ryu, Cryptanalysis of the New CLT Multilinear Maps,
*IACR Cryptology ePrint Archive*,**2015**, 934 (2015). link. - [TCC:GenGorHal15] Craig Gentry, Sergey Gorbunov & Shai Halevi, Graph-Induced Multilinear Maps from Lattices, 498-527, in in: TCC, edited by Yevgeniy Dodis & Jesper Buus Nielsen, Springer (2015)
- [EPRINT:Coron15] Jean-Sébastien Coron, Moon Sung Lee, Tancrède Lepoint & Mehdi Tibouchi, Cryptanalysis of GGH15 Multilinear Maps,
*IACR Cryptology ePrint Archive*,**2015**, (2015). link. - [EC:BGKPS14] Boaz Barak, Sanjam Garg, Yael Tauman Kalai, Omer Paneth & Amit Sahai, Protecting Obfuscation against Algebraic Attacks, 221-238, in in: EUROCRYPT, edited by Phong Nguyen & Elisabeth Oswald, Springer (2014)
- [EPRINT:MilSahZha16] Miles, Sahai & Zhandry, Annihilation Attacks for Multilinear Maps: Cryptanalysis of Indistinguishability Obfuscation over GGH13,
*IACR Cryptology ePrint Archive*,**2016**, (2016). link. - [EPRINT:AGIS14] Prabhanjan Ananth, Divya Gupta, Yuval Ishai & Amit Sahai, Optimizing Obfuscation: Avoiding Barrington's Theorem,
*IACR Cryptology ePrint Archive*,**2014**, (2014). link. - [TCC:BraRot14] Zvika Brakerski & Guy Rothblum, Virtual Black-Box Obfuscation for All Circuits via Generic Graded Encoding, 1-25, in in: Theory of Cryptography - 11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24-26, 2014. Proceedings, edited by Yehuda Lindell, Springer (2014)
- [EPRINT:BMSZ15] Saikrishna Badrinarayanan, Eric Miles, Amit Sahai & Mark Zhandry, Post-Zeroizing Obfuscation: The case of Evasive Circuits,
*IACR Cryptology ePrint Archive*,**2015**, 167 (2015). link. - [C:PasSetTel14] Rafael Pass, Karn Seth & Sidharth Telang, Indistinguishability Obfuscation from Semantically-Secure Multilinear Encodings, 500-517, in in: Advances in Cryptology - CRYPTO 2014 - 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I, edited by Juan Garay & Rosario Gennaro, Springer (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: FOCS, edited by IEEE Computer Society (2013)
- [EPRINT:CheGenHal16] Yilei Chen, Craig Gentry & Shai Halevi, Cryptanalyses of Candidate Branching Program Obfuscators, , , (2016). link.
- [EPRINT:FerRasSah16] Rex Fernando, Peter Rasmussen & Amit Sahai, Preventing CLT Zeroizing Attacks on Obfuscation, , , (2016). link.
- [EPRINT:GMMSSZ16] Sanjam Garg, Eric Miles, Pratyay Mukherjee, Amit Sahai, Akshayaram Srinivasan & Mark Zhandry, Secure Obfuscation in a Weak Multilinear Map Model, , , (2016). link.
- [EPRINT:CorLeeLepTib16] Jean-Sébastien Coron, Moon Sung Lee, Tancrède Lepoint & Mehdi Tibouchi, Zeroizing Attacks on Indistinguishability Obfuscation over CLT13, , , (2016). link.
- [C:CGHLMMRST15] 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: Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part I, edited by Rosario Gennaro & Matthew Robshaw, Springer (2015)
- [EC:Zimmerman15] Joe Zimmerman, How to Obfuscate Programs Directly, 439-467, in in: EUROCRYPT, edited by Elisabeth Oswald & Marc Fischlin, Springer (2015)
- [TCC:AppBra15] Benny Applebaum & Zvika Brakerski, Obfuscating Circuits via Composite-Order Graded Encoding, 528-556, in in: TCC, edited by Yevgeniy Dodis & Jesper Buus Nielsen, Springer (2015)