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

Dual-Input Branching Programs

CLT13

Single-Input Branching Programs

STANDING Dual-Input Branching Programs

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

BROKEN Direct

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