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

Dual-Input Branching Programs

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

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