CRYPTREC-EX-2603-2016

Cryptographic Multilinear Maps
A Status Report
Mehdi Tibouchi
NTT Secure Platform Laboratories
January 2017

Executive Summary
A few years ago, Garg, Gentry and Halevi (EUROCRYPT 2013) proposed the first candidate
construction of cryptographic multilinear maps, a primitive first envisioned a decade earlier
by Boneh and Silverberg (Contemp. Math. 2003) as a higher-dimensional generalization ofbilinear pairings on elliptic curves.
Boneh and Silverberg themselves had pointed out several interesting applications ofmultilinear maps, such as one-round multiparty key agreement, verifiable pseudorandomfunctions and efficient broadcast encryption. Furthermore, following the construction ofGarg et al., a flurry of new research uncovered even more far-reaching applications, including
long-awaited primitives like attribute-based encryption for all circuits and general functional
encryption, fruitful new ideas like witness encryption, and the startlingly powerful notionof indistinguishability obfuscation.
However, the candidate construction of Garg et al. was not provably secure. As aresult, part of the new research focused on clarifying its security, and on exploring alternate
techniques to achieve multilinear maps.
This document aims at giving a bird’s eye view of the main results so far, in termsof new definitions, candidate constructions and major applications, and to summarize
known attacks against existing schemes, discussing their current status as far as security isconcerned.
This is a very active and rapidly evolving area of research, so we cannot even comeclose to an exhaustive survey of existing literature, and although we have strived to take
into account some of the most recent published results as of late 2016, significant shifts in
our understanding of multilinear maps in the near future are not only impossible to ruleout but even likely to occur. Indeed, it has happened on several occasions already that a
newly proposed scheme has been broken, fixed and broken again within the span of a few
weeks.
With those caveats, here are some notable takeaways from the state of the art at thispoint in time:• There are three main constructions proposed for multilinear maps: the original
one from Garg, Gentry and Halevi (GGH13), a variant “over the integers” due to3

4

EXECUTIVE SUMMARY
Coron, Lepoint and Tibouchi (CLT13), and a “graph-induced” construction by Gentry,
Gorbunov and Halevi (GGH15).
• Although these constructions are conceptually inspired by fully homomorphic encryption schemes that can be proved secure under well-understood hardness assumptions,the multilinear map schemes themselves have no proof of security. (Note that thesame is true for bilinear pairings as well).
• Over each of the three constructions, there exists a polynomial time attack against thebasic Diffie–Hellman key multiparty exchange protocol. In fact, the conceptual counterpartof the CDH assumption fails to hold. As a result, most of the (stronger) assumptions
used to prove the existence of more interesting cryptographic notions like witness
encryption and indistinguishability obfuscation also fail to hold.
• However, this does not necessarily translate to a direct attack against the actual
instantiations of the primitives themselves. For indistinguishability obfuscation, inparticular, attacks are known against some instantiations, but countermeasures havebeen proposed to circumvent them. Thus, there are constructions of indistinguishability
obfuscation over GGH13, CLT13 and GGH15 against which no attack is known at thepresent time. Whether this will continue to hold is difficult to predict.
• Theoretically speaking, and assuming standard cryptographic hardness assumptions,
it is known that indistinguishability obfuscation and secure functional encryption are
essentially equivalent, and imply the existence of secure n-linear maps for polynomiallylarge n (both in the original sense of Boneh and Silverberg and in the sense of gradedencodings, as introduced by Garg et al.). This means that any alternate method toconstruct indistinguishability obfuscation or functional encryption would indirectly
yield secure multilinear maps. Unfortunately, no such method is known at present.
• Conversely, it has also been shown that 5-linear maps for which the (subexponential) DDH assumption holds are sufficient to obtain indistinguishability obfuscation.
This means that one can bootstrap constant-degree multilinear maps to arbitrary
polynomial degree, and also that we seem to be tantalizingly close to achieving
indistinguishability obfuscation (and hence everything else) from bilinear pairings, aprimitive that we are much more confident does exist. Closing the gap from degree 5
to degree 2, however, appears to be an elusive problem.
• There is no prospect of achieving practical levels of efficiency for any of the primitives
considered in this document in the foreseeable future.

Contents
Executive Summary

3

1 Introduction
1.1 From Diffie–Hellman to multilinear maps . . . . . . . . . . . . . . . . . . .
1.2 Multilinear maps from geometry? . . . . . . . . . . . . . . . . . . . . . . .
1.3 Fully homomorphic encryption and graded encoding schemes . . . . . . .
1.4 Some applications of multilinear maps . . . . . . . . . . . . . . . . . . . . .
1.5 Attacks against multilinear map constructions . . . . . . . . . . . . . . . .

7
7
8
10
12
15

2 Definitions and Constructions
2.1 Multilinear maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Graded encoding schemes . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Security definitions: the example of Diffie–Hellman key exchange . . . . . .
2.4 A concrete instantiation: the CLT13 graded encoding scheme . . . . . . .
2.5 GGH15 and the graph-induced approach . . . . . . . . . . . . . . . . . . .

17
17
18
20
22
26

3 Overview of Known Attacks
3.1 Zeroizing attacks: breaking Diffie–Hellman key exchange over GGH13 and
CLT13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Graph-induced cryptanalysis: breaking GGH15 key exchange . . . . . . . .
3.3 Attacks on obfuscation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

4 Conclusions and Perspectives
4.1 Status of multilinear map-based primitives . . . . . . . . . . . . . . . . . .
4.2 Future prospects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43
43
44

Bibliography

45

5

31
34
39

Chapter 1

Introduction
1.1

From Diffie–Hellman to multilinear maps

“We stand today on the brink of a revolution in cryptography,” wrote Diffie and Hellmanin their seminal New Directions paper from 1976 [DH76], which introduced the main ideasof public-key cryptography. In particular, they described the well-known key exchange
protocol which bears their name: Alice and Bob can derive a common secret by exchanging
messages publicly on an insecure channel. To do so, they agree on a group G (say a cyclic
subgroup of large prime order q in the multiplicative group F∗p of a finite field Fp ) and agenerator g of G. Then Alice and Bob choose random exponents a, b ∈ {0, . . . , q − 1}, andcompute the group elements
A = g a and B = g b
respectively. Alice sends A to Bob and Bob B to Alice, and they can then both computethe common group element g ab = Ab = B a . However, the problem of distinguishing g abfrom a random element of G given g, g a and g b is believed to be hard (for the group
G mentioned above, and many other groups like suitably chosen elliptic curves). As aresult, an eavesdropper learns no information about the common secret by intercepting thecommunication between the two parties.
As we well know, that idea, and the corresponding Decisional Diffie–Hellman (DDH)
hardness assumption, proved extremely fruitful. It can be used to construct semanticallysecure homomorphic encryption [ElG85], digital signatures [Sch91], efficient pseudorandomfunctions [NR04], CCA-secure encryption [CS03] and more. And it is cited as one of themain reason for Diffie and Hellman’s Turing award.
Nevertheless, some cryptographic primitives cannot be constructed from DDH. For
example, Papakonstantinou et al. were able to obtain a black-box separation result [PRV12]
between DDH and identity-based encryption (IBE). To construct IBE, a more powerfulsetting is necessary, and that setting emerged in the early 2000s, bringing about what would
be fair to call a second “revolution in cryptography”: the era of bilinear pairings.
The existence of efficiently computable bilinear pairings between certain families of
elliptic curve groups was first understood as a cryptanalytic liability [MVO93], but Joux
7

8

CHAPTER 1. INTRODUCTION

noticed that it could be used constructively to generalize Diffie–Hellman key exchange tothree parties in one round [Jou04]. Indeed, if G is a cyclic group of prime order q endowedwith a symmetric non degenerate bilinear pairing e : G × G → GT , Alice, Bob and Charlie
can use it to derive a common secret as follows. They choose a, b, c ∈ {0, . . . , q − 1} at
random and compute
A = g a , B = g b and C = g c
respectively, for some agreed upon generator g. They can then all compute the commonvaluee(g, g)abc = e(A, B)c = e(B, C)a = e(C, A)b
but an eavesdropper seeing A, B and C cannot distinguish that value from a random
element of GT , assuming the hardness of the decisional bilinear Diffie–Hellman (DBDH)
problem, which is believed to be hard over well-constructed pairing-friendly elliptic curves.
Using this new bilinear structure, Boneh and Franklin were then able to construct thefirst IBE scheme [BF03], opening up the path to numerous new cryptographic notions,
including public-key encryption with keyword search [BDOP04], attribute-based encryption(for boolean formulas) [GPSW06a] and homomorphic encryption for quadratic polynomials [BGN05]. It also led to more efficient constructions of previous primitives such as
signatures [BLS04], group signatures [BBS04], non-interactive zero-knowledge proofs [GS08]
and more. In short, the possibility offered by bilinear pairings to carry out not only linear
operations in the exponent of group elements but also one level of multiplication proved tobe particularly fecund. It also earned Joux, Boneh and Franklin the 2013 Gödel prize.
Soon after the cryptographic community realized the power of bilinear maps, Bonehand Silverberg [BS03] asked the natural question of whether this development could be
pursued further, in such a way that several levels of multiplications could be carried out inthe exponent of group elements. This would be possible using what they called cryptographic
multilinear maps.

1.2

Multilinear maps from geometry?

For cyclic groups G and GT of prime order q, a map e : Gn → GT is said to be a (symmetric)
n-linear map (or just a multilinear map when n is omitted) if for any a1 , . . . , an ∈ Z and
g1 , . . . , gn ∈ G, we havee(g1a1 , . . . , gnan ) = e(g1 , . . . , gn )a1 ···an ,and furthermore e is non-degenerate in the sense that e(g, . . . , g) is a generator of GT for
any generator g of G. For such a structure to be of cryptographic interest, one needs to beable to compute efficiently with it (in the sense that e itself and the group operations on G
and GT are efficiently computable), and it needs to satisfy some notion of security—the
most basic of which would be to ask that the discrete logarithm problem in G be hard(which implies that it is hard in GT as well). This is in essence how Boneh and Silverberg
define cryptographic multilinear maps [BS03].

1.2. MULTILINEAR MAPS FROM GEOMETRY?

9

They observed that if one can construct such cryptographic multilinear maps (satisfying
slightly stronger security notions that the basic discrete log one), a number of interesting
cryptographic consequences follow, beyond what can be done with bilinear pairings. In
particular, using an n-linear maps, one can obtain a one-round Diffie–Hellman-like key
exchange protocol between n + 1 parties, as a direct generalization of Joux’s protocol.
Indeed, if users U0 , . . . , Un want to derive a common secret, they can simply pick random
exponents a0 , . . . , an , compute the group elements Ai = g ai ∈ G and broadcast them.
They are then able to compute the common value e(g, . . . , g)a0 ...an : user Uj can obtainit as e(Aj+1 , . . . , An , A0 , . . . , Aj−1 )aj . However, under the obvious generalization of thedecisional Diffie–Hellman assumption, that value is indistinguishable from a random elementof GT given only the Ai ’s, making the protocol secure against eavesdroppers.
Other applications mentioned by Boneh and Silverberg include efficient unique signatures and broadcast encryption with short keys and optimal communication complexity. It
turns out that multilinear maps also imply much stronger cryptographic notions, including
indistinguishability obfuscation (see §1.4 below).
So do these multilinear maps exist? The question is especially natural in view of thefact that bilinear pairings on elliptic curves are a special case of a type of multilinear
structure that exists on very large classes of algebraic geometric objects. Roughly speaking,a geometric object (say a project algebraic variety) gives rises to certain groups called“cohomology groups,” together with multilinear maps between them known as cup-products.
An object of dimension d has cohomology groups of degrees 0 to 2d and degrees add up in
cup-products, so one could in principle construct a 2d-linear map from degree 1 to degree
2d from any d-dimensional object; in fact, elliptic curve pairings are essentially of that form.
However, it is unclear in general how to compute on those groups efficiently (or what thesuitable analogue of pairing-friendly elliptic curves would be).
Boneh and Silverberg carried out a detailed analysis of the most direct generalization of
elliptic curves to higher dimensions, namely abelian varieties. As for elliptic curves, their setof points is endowed with an efficiently computable group law, and that group is isomorphic
to degree 1 cohomology, so that one can actually compute inside that cohomology. This
makes it possible to define multilinear maps in various ways. Unfortunately, Boneh andSilverberg found that, unlike what happens with elliptic curves, the target group of thosemultilinear maps does not appear to lend itself to efficient arithmetic operations: what one
gets is essentially a higher tensor power of the multiplicative group. For example, over thefinite field Fp , the target group is essentially F∗p , except that g a is represented as the tuple(g a1 , . . . , g ad ) ∈ (F∗p )d for any (a1 , . . . , ad ) such that a = a1 · · · ad . Clearly, one cannot evenefficiently decide equality in that group without breaking the computational Diffie–Hellman
problem.
More generally, their paper shows that, under widely believed assumptions, it is impossible to construct n-linear maps from geometry whose target group is F∗p itself (as opposed toa higher tensor power, say) for any n > 2. This does not entirely rule out multilinear maps
from geometry (e.g. one could still conceivably have multilinear maps whose target groupwould lie in an elliptic curve or some other group with efficient arithmetic), but makes it
implausible enough that the problem has only been revisited on a handful of occasions

10

CHAPTER 1. INTRODUCTION

since then [RH09]. In any case, after Boneh and Silverberg’s paper, constructing multilinear
maps was considered intractable for at least a decade.

1.3

Fully homomorphic encryption and graded encoding
schemes

New ideas to tackle the problem of obtaining multilinear maps only came about after a third“revolution” swept the world of cryptography, mainly from the mid-2000s onwards: latticebased cryptography, ultimately leading to the construction by Gentry of a fully-homomorphic
encryption scheme [Gen09], which solved a major, 30-year old open problem [RAD78].
Before Gentry, some encryption schemes like those of ElGamal and Paillier [ElG85,
Pai99] had made it possible to carry out either additions or multiplications on ciphertexts.
The pairing-based scheme of Boneh, Goh and Nissim [BGN05] supported arbitrarily many
additions and one level of multiplications. In contrast, fully-homomorphic encryption (FHE)
makes it possible to carry out both additions and multiplications on ciphertexts, arbitrarily
many times (and as a result, any efficient function can be evaluated homomorphically on
ciphertexts).
A few years later, this led to the intuition that FHE ciphertexts behave a bit like theexponents of group elements in a multilinear map. More precisely, they behave similarly tothe exponents of group elements in what Garg, Gentry and Halevi call a graded encoding
scheme [GGH13a]. Roughly speaking, such a scheme is a family of efficient cyclic groups
G0 , . . . , Gn of the same prime order q together with efficient non-degenerate bilinear pairingse : Gi × Gj → Gi+j whenever i + j ≤ n. In other words, if we fix a family of generators gi
of the Gi ’s in such a way that gi+j = e(gi , gj ), we can add exponents within a given groupGi :gia · gib = gia+b
and multiply exponents from two groups Gi , Gj as long as i + j ≤ n:a·be(gia , gjb ) = gi+j.

This makes g1a somewhat similar to an “FHE encryption” of a.
Of course, there are a number of differences. First, FHE ciphertexts should be randomized. This is not a serious difficulty: one can allow for randomized representationsof group elements as well, and such representations are in fact permitted in Garg et al.’s
definition of a graded encoding scheme. However, one should still make it possible to test
the equality of two (randomized representations of) group elements in Gn , say; this cannot
be done publicly in an FHE scheme, as it would break semantic security. Nevertheless, thismay be doable once some limited information about the FHE secret key is made public.
Finally, a third difference is that one should not be able to invert the bilinear pairings, so
the representations of gia and gja cannot be of the same form when i 6= j. This can be dealt
with by introducing some secret multiplicative factor in ciphertexts that will appear at thepower i in the ciphertext corresponding to an element of Gi .

1.3. FULLY HOMOMORPHIC ENCRYPTION AND GRADED ENCODING SCHEMES

11

These intuitive ideas essentially describe how Garg, Gentry and Halevi’s GGH13
multilinear maps [GGH13a] are obtained based on (the large message space, somewhat
homomorphic variant of) Gentry’s FHE scheme [Gen09].
More precisely, Gentry’s scheme is defined over the cyclotomic ring R = Z[x]/(xm + 1)
for some m, with respect to a certain principal ideal I = hgi with small generator g. The
plaintext space consists of small elements in R/I (say polynomials with 0/1 coefficients)
and a message m is encrypted as c = m + r · g mod q ∈ Rq = R/qR for some small noiser. In contrast, a GGH13 encoding of m at level i is of the form:
ci =

m+r·g
mod q,
zi

where z is a secret masking element, and one can see that linear operations at a given level
as well as multiplications between levels work as expected (as long as the noise values r
remain appropriately small). Equality tests at level n are carried out using a zero-testing
parameter pzt of the form:
pzt = h · zn · g−1 mod q
where h is small: the idea is that pzt · cn ≡ h · (mg−1 + r) mod q will be small if and only
if m = 0, allowing to test for equality to zero, and then usual equality by linearity.
For Gentry’s scheme to be secure, the generator g of I has to be kept secret, although a“bad” basis of I consisting of large vectors can be published. Since pzt depends on g, we
can see that the zero-testing parameters reveals some information about the FHE secret key
as expected. This partial key leakage, which is inherent to the conceptual construction ofmultilinear maps from FHE, is the reason why we are not able to prove the scheme secure
even though the FHE scheme itself has a proof of security.
Soon after Garg et al. published their candidate construction, another FHE-inspired
construction was described by Coron, Lepoint and Tibouchi [CLT13a], related this time to
the FHE scheme “over the integers” of van Dijk et al. [vDGHV10] (or more precisely, on
the batch variant due to Cheon et al. [CCK+ 13]). The main ingredients of the construction
are essentially the same as those of [GGH13a], although a number of technical details aredifferent.
Later on, variants of those two constructions were proposed to address certain technicalissues, although with limited success [LSS14, CLT15]. In addition, a substantially different
construction (GGH15) was introduced by Gentry, Gorbunov and Halevi [GGH15], inspiredby the LWE-based FHE scheme of Gentry, Sahai and Waters [GSW13]. The functionality
achieved in GGH15 differs syntactically from that of GGH13 and CLT13: instead of being
arranged in a graded structure, the “groups” containing the encodings correspond to edges
on a directed acyclic graph, and two encodings can be multiplied together if and only iftheir associated edges are adjacent. It is not immediately obvious how to use that primitive
to construct the same cryptographic objects as with standard multilinear maps, but Gentry
et al. showed how it can be done in a number of specific instances, including multiparty
key exchange and obfuscation.

12

1.4

CHAPTER 1. INTRODUCTION

Some applications of multilinear maps

Multiparty Diffie–Hellman key exchange. As we have mentioned, the most direct
application of n-linear maps is a one-round protocol for (n + 1)-way Diffie–Hellman key
exchange. This protocol can also be instantiated in the graded encoding scheme setting of Garg
et al. [GGH13a]. Note however that since encodings are randomized, to derive a commonshared key, the parties need to be able to extract some deterministic value depending only on
the underlying “group element” that randomized encoding represent. This procedure is anextension of the zero-testing algorithm alluded to above, and is part of the formal definitionof a graded encoding scheme. See §2.2 for details, and §2.3 for a formal description of themultiparty Diffie–Hellman key exchange protocol over graded encoding schemes.
Attribute-based encryption for circuits. One of the great successes of pairing-based
cryptography is the realization of the notion of attribute-based encryption (ABE) [SW05,
GPSW06a]. In a (ciphertext-policy) ABE scheme, users have secret keys associated withcertain sets of attributes, and messages are encrypted with respect to policies which are
Boolean functions of the attributes. Thus, a user with attributes x and y can decrypt
ciphertexts associated with the policy x ∧ y, or the policy x ∨ z, but not the policy x ∧ z. A
major challenge in constructing ABE is the requirement that the scheme should achieve
collusion-resistance: if Alice has the attributes x, y and Bob has the attributes y, z, they should
not be able to decrypt a ciphertext with policy x ∧ z even when colluding together.
There are constructions of ABE based on bilinear pairings that support policies represented by arbitrary Boolean formulas of the attributes, or more generally by span programs [GPSW06b], but techniques based on pairings have so far failed to achieve ABE for
arbitrary polynomial-size Boolean circuits. One seems to encounter a fundamental limitationof bilinearity when trying to obtain collusion-resistance for arbitrary circuits, due to a classof attack known as backtracking [GGH+ 13c, §1].
On the other hand, over multilinear maps, relatively direct generalizations of the classicalpairing-based constructions of ABE yield ABE for all circuits right away, as shown by Garg
et al. [GGH+ 13c, GGHZ14]. Later on, Gorbunov, Vaikuntanathan and Wee were able
to construct attribute-based encryption for circuits from standard lattice assumptions aswell [GVW13], but the problem of a pairing-based realization remains open.
Witness encryption. Shortly after the first multilinear map candidate GGH13 was proposed, Garg, Gentry, Sahai and Waters introduced the intriguing and powerful new notionof witness encryption, and showed how it can be realized from multilinear maps [GGSW13]. A
witness encryption scheme is defined with respect to a certain NP language L, and consistsof two efficient algorithms: Encrypt(1λ , x, m) takes as input a security parameter, a string
x and a message m, and outputs a ciphertext c; Decrypt(c, w) takes as input a ciphertext
c and a string w, and outputs either a message m0 or ⊥. Correctness states that if x is
an instance of L and w is a witness of x ∈ L, then Decrypt(Encrypt(1λ , x, m), w) outputs
the same message m with probability 1. Soundness security states that the encryptions ofdistinct messages with respect to a string x ∈/ L are indistinguishable.

1.4. SOME APPLICATIONS OF MULTILINEAR MAPS

13

In other words, witness encryption makes it possible to encrypt messages with respect
to an instance x of the language L, and one can decrypt a ciphertext if one knows a witness
to the fact that x ∈ L. Security does not imply that knowing a witness is necessary to
decrypt in general. But depending on the language L, it may be the case that instances andnon-instances are computationally indistinguishable without a witness (consider e.g. thelanguage of Diffie–Hellman pairs over a DDH group), and soundness then implies a formof semantic security with respect to adversary who do not know the witness.
Witness encryption is a powerful notion; it implies strong forms of identity-based
encryption, and even ABE for all circuits in an essentially black-box way [GGSW13]. The
original instantiation was based on a hardness assumption that mimicked the construction
very closely, but constructions based on less ad hoc assumptions were later proposed aswell [GLW14, AJN+ 16].
Functional encryption. The notion of functional encryption is a far-reaching generalizationof ABE introduced by Boneh, Sahai and Waters [BSW11]. In a functional encryption scheme
defined with respect to a functionality F : K×X → {0, 1}∗ , a user secret key skk is associatedwith an element k the set K, and if a ciphertext c is an encryption of x ∈ X, the decryption
algorithm applied to skk and c returns F (k, x). For example, ciphertext-policy ABE is the
special case when elements k of K are sets of attributes, elements of X consist of a pair(m, f ) of a message and a predicate, and the functionality F (k, x) evaluates to m if f (k) istrue and to ⊥ otherwise.
A number of special cases of functional encryption have been described in the context
of pairing-based cryptography, such as predicate encryption for inner-products [KSW08,
OT09], spatial encryption [Ham11] and functional encryption for inner-product functionalities [ABDP15, BJK15], but they tend to be limited to functionalities that are “bilinear” insome sense.1
In contrast, one of the first results to emerge as a consequence of multilinear maps wasa construction of functional encryption for all circuits [GGH+ 13b]. That construction isin fact based on the indistinguishability obfuscator proposed in the same paper (see below),
so it relies on multilinear maps only in an indirect way in some sense. However, otherinstantiations based directly on multilinear maps (i.e. without obfuscation) have later been
described, starting with the scheme of Garg, Gentry, Halevi and Zhandry [GGHZ16].
Indistinguishability obfuscation. Perhaps the most impressive result that followed the
GGH13 multilinear map candidate was the description by Garg et al. [GGH+ 13b] of a
possible construction of indistinguishability obfuscation for all circuits. Program obfuscation,roughly speaking, aims at making it possible to publish programs whose functionality
depends on some secrets in such a way that even the source code of the program will notreveal those secrets. They are, in some sense, hidden in plain sight.
1

More general notions have also been achieved over lattices, such as leveled predicate encryption forcircuits [GVW15], and even some strong forms of functional encryption for circuits with a single-bit output [GKP+ 13]. Those notions, however, are weaker than the functional encryption schemes achieved frommultilinear maps.

14

CHAPTER 1. INTRODUCTION

Strong forms of obfuscation can be achieved for very limited classes of functionalities
using standard cryptographic techniques. For example, one can publish the source code ofa program that checks if its input is equal to a secret password (a so-called “point function”)
without revealing that password: simply put in the program the image of the password
under some one-way function. But being able to do the same with much more generalclasses of function is immensely powerful: for example, it allows to convert any symmetrickey encryption scheme to public-key (just publish as “public key” the obfuscated encryption
algorithm with an embedded symmetric key).
Unfortunately, as part of their study of various notions of obfuscation, Barak et al.
found that the most natural notion of program obfuscation (“black-box obfuscation”) is
in fact impossible to achieve for general programs [BGI+ 01, BGI+ 10]. However, they also
introduced weaker notions for which they could not obtain an impossibility result, including
indistinguishability obfuscation, which Goldwasser and Rothblum later showed to be, in a
precise technical sense, the best possible obfuscation [GR07].
An indistinguishability obfuscator O for a class C of circuits is a circuit transformation
which is functionality-preserving (i.e. for a circuit C ∈ C , O(C) is another circuit which
agrees with C on all inputs) and guarantees that for two circuits C1 , C2 ∈ C that arefunctionally equivalent (i.e. agree on all inputs), then O(C1 ) and O(C2 ) are computationallyindistinguishable. Note that it is not immediately clear what that notion could be usefulfor: for example, since point functions associated with distinct passwords are inequivalent,
there is no guarantee that applying an indistinguishability obfuscator to such a function
will hide the password.
Nevertheless, most readers of Barak et al. and Goldwasser–Rothblum would probably
have assumed that an impossibility result for indistinguishability obfuscation to be a lot
more likely than an instantiation, so Garg et al.’s construction [GGH+ 13b] came as a great
surprise. Moreover, their paper demonstrated that the notion is in fact actually extremely
powerful, since it was sufficient to achieve the long-awaited construction of functional
encryption. Following their work, a number of papers, such as [SW14], developed more
systematic techniques to use indistinguishability obfuscation, and it is now understood tobe powerful enough to construct, in the words of Bitansky and Vaikuntanathan, “almost
any known cryptographic object.” [BV15]
Relations between some of these notions. It is interesting to note that the more powerful notions described above, namely functional encryption and indistinguishability obfuscation, turn out to be essentially equivalent, and also equivalent to multilinear maps.
More precisely, as we have said, indistinguishability obfuscation (together with somestandard primitives like PRFs) implies (compact, multibit) functional encryption for all
circuits [GGH+ 13b], even with adaptive security [Wat15] (and in fact, there is a genericconversion from selective to adaptive security [ABSV15]). Conversely, (compact, multibit)
functional encryption for all circuits is sufficient to achieve indistinguishability obfuscation [AJ15, BV15]. In fact, recent candidate constructions of indistinguishability obfuscationsuch as [LV16, Lin16, AS16] have used some form of functional encryption as an intermediate building block.

1.5. ATTACKS AGAINST MULTILINEAR MAP CONSTRUCTIONS

15

In addition, it is now known that if n-linear maps satisfying certain DDH-like security
notions exist for some sufficiently large constant n (the current record is n = 5, obtainedby Lin in [Lin16] and Ananth and Sahai in [AS16]), then indistinguishability obfuscation/function encryption exist as well. And conversely, Albrecht et al. have shown thatindistinguishability obfuscation (again together with standard primitives like homomorphic
encryption and NIZK) is enough to construct multilinear maps [AFH+ 16].
This means that constructing multilinear maps, functional encryption and indistinguishability obfuscation are equivalent goals, and future constructions could be obtained
from any of those primitives.

1.5

Attacks against multilinear map constructions

If secure, we have seen that candidate constructions of multilinear maps have very interesting
consequences in cryptography (and we have only touched upon a few among many). The
actual security picture is far from clear, however.
Indeed, attacks have been demonstrated against all constructions so far, and we describe
a number of them in details in Chapter 3. The current situation is that, due to a longseries of attacks [CHL+ 15, CLT14, CGH+ 15, CFL+ 16, HJ16, CLLT16a], multiparty Diffie–
Hellman key exchange is broken over all of the proposed candidates. In addition, a numberof attacks have been demonstrated against several constructions of indistinguishability
obfuscation [MSZ16a, CGH16, ADGM16, CLLT17], but not all schemes are broken yet.
We can also mention that GGH13 and CLT13 are both broken in classical subexponential
time and quantum polynomial time. In the case of CLT13, it is because it relies on thehardness of factoring. In the case of GGH13, it is a consequence of recent progress on thecryptanalysis of some ideal lattice assumptions in the presence of very small noise [ABD16].

Chapter 2

Definitions and Constructions
2.1

Multilinear maps

2.1.1

The Boneh–Silverberg setting

Boneh and Silverberg introduced the notion of multilinear maps in a cryptographic setting [BS03]. The definition they adopted for their purposes was touched upon in §1.2. We
recall it more formally below.
Definition 1. Let G and GT be cyclic groups (denoted additively), and e : Gκ → GT a mapping
for some integer κ ≥ 1. We say that e is a κ-linear map (or simply a multilinear map) when thefollowing conditions hold:
1. G and GT are of the same prime order;
2. for any a1 , . . . , aκ ∈ Z and g1 , . . . , gκ ∈ G, we havee(a1 · g, . . . , aκ · g) = a1 · · · aκ · e(g, . . . , g);
3. if g is a generator of G, then e(g, . . . , g) is a generator of GT .

2.1.2

Efficient algorithms

Boneh and Silverberg called a multilinear map as above a cryptographic multilinear map when
the groups G and GT admit efficient group operations, when the map e itself is efficiently
computable, and when the scheme satisfies some notion of security like the hardness of
discrete logarithms in G. Since efficiency and security are asymptotic notions, they can
only make sense with respect to some instance generation algorithm.
Following [GGH12], one can capture these notions (minus the security, which can be
definitely independently by a suitable game) by saying that a multilinear map scheme is a tupleof algorithms (InstGen, add, neg, EncTest, map) for instance generation, group operations,membership testing and multilinear pairing, which can be described as follows.
17

18

CHAPTER 2. DEFINITIONS AND CONSTRUCTIONS

Instance generation. InstGen(1λ , 1κ ) is an efficient randomized algorithm that takes as
input the security parameter λ and the multilinearity degree κ, and outputs a description of
the groups G and GT , their order q, a description of the multilinear map e : Gκ → GT , anda string g ∈ {0, 1}∗ encoding a generator of G. The tuple (G, GT , q, e) is denoted by pp.
Membership testing. EncTest(pp, b, x) is an efficient, deterministic algorithm that takes
as input the parameters pp, a bit b and a string x ∈ {0, 1}∗ and decides whether x is avalid representation of an element of G (resp. GT ) when b = 0 (resp. b = 1). It is assumed
that representations are unique, so we simply denote validity by membership: x ∈ G(resp. x ∈ GT ).
Group operations. add(pp, b, x, y) is efficient, deterministic, and returns x + y when b = 0
and x and y are both elements of G (resp. b = 1 and x, y ∈ GT ). Note that this is sufficientto efficiently compute a · x for a ∈ Zq by double-and-add. Similarly, neg(pp, b, x) computes−x.
Multilinear map. map(pp, x1 , . . . , xκ ) is efficient, deterministic, and returns the target
group element e(x1 , . . . , xκ ) ∈ GT .

2.1.3

Symmetry vs. asymmetry

The multilinear maps describe above are symmetric in the sense that all the source groupare the same (or equivalently, are efficiently isomorphic). It is straightforward to extend thedefinition to multilinear maps of the form e : G1 ×· · ·×Gκ → GT where the groups Gi are allof the same prime order, but there does not necessarily exist efficient isomorphisms between
them. That setting occurs frequently with elliptic curves (for type II and type III pairings in
the sense of [GPS08]), and has been described for multilinear maps by Rothblum [Rot13].

2.2

Graded encoding schemes

As discussed in §1.3, the functionality achieved by constructions such as [GGH13a] and[CLT13a] differ from the Boneh–Silverberg definition above in at least two important aspects:• contrary to the Boneh–Silverberg setting where elements of the source group are
combined in one go to form an element of the target group, encodings are arranged
in several levels, and one can pair elements at level i and level j to obtain an element
at level i + j, and so on several times;• a single “exponent” can be represented at a given level by many different encodings.
The corresponding notion is captured by the definition of a graded encoding system, andits algorithmic description, as presented below.

2.2.1

Graded encoding system

We recall the formal definition of a κ-graded encoding system from [GGH13a]. For simplicity
we only consider the symmetric case below. See [GGH12, Appendix A] for the description

192.2. GRADED ENCODING SCHEMES

of a more general framework that can handle asymmetric multilinear maps and gradings
with respect to more complicated monoids.
(α)

Definition 2. A κ-graded encoding system for a ring R is a system of sets S = {Sv{0, 1}∗ : v ∈ N, α ∈ R}, with the following properties:(α)

1. For every v ∈ N, the sets {Sv∈: α ∈ R} are disjoint.

2. There are binary operations + and − (on {0, 1}∗ ) such that for every α1 , α2 ∈ R, every
(a )
(a )
(α +α )v ∈ N, and every u1 ∈ Sv 1 and u2 ∈ Sv 2 , it holds that u1 + u2 ∈ Sv 1 2 and(α −α )
u1 − u2 ∈ Sv 1 2 where α1 + α2 and α1 − α2 are addition and subtraction in R.
3. There is an associative binary operation × (on {0, 1}∗ ) such that for every α1 , α2 ∈ R,
(α )
(α )
every v1 , v2 with 0 ≤ v1 + v2 ≤ κ, and every u1 ∈ Sv1 1 and u2 ∈ Sv2 2 , it holds that
(α1 ·α2 )u1 × u2 ∈ Sv1 +v
where α1 · α2 is multiplication in R.
2

2.2.2

Efficient procedures

We also recall the definition of the procedures for manipulating encodings. As previously
we consider only the symmetric case.
Instance generation. The randomized InstGen(1λ , 1κ ) takes as inputs the parameters λand κ, and outputs (pp, pzt ), where pp is a description of a κ-Graded Encoding System as
above, and pzt is a zero-test parameter.
(α)

Ring sampler. The randomized samp(pp) outputs a “level-zero encoding” a ∈ S0 for anearly uniform element α ∈R R. Note that the encoding a does not need to be uniform in(α)
S0 .
Encoding. The (possibly randomized) enc(pp, i, a) takes as input a level-zero encoding(α)(α)
a ∈ S0 for some α ∈ R and a level i ≤ κ, and outputs a level-i encoding u ∈ Si for thesame α.
Rerandomization. The randomized reRand(pp, i, u) re-randomizes encodings relative to(α)
the same level i. Specifically, given an encoding u ∈ Sv , it outputs another encoding(α)(α)
u0 ∈ Sv . Moreover for any two u1 , u2 ∈ Sv , the output distributions of reRand(pp, i, u1 )and reRand(pp, i, u2 ) are nearly the same.
(α )Addition and negation. Given pp and two encodings relative to the same level, u1 ∈ Si 1(α )(α +α )(−α )and u2 ∈ Si 2 , we have add(pp, u1 , u2 ) ∈ Si 1 2 and neg(pp, u1 ) ∈ Si 1 . Below wewrite u1 + u2 and −u1 as a shorthand for applying these procedures.
(α )

(α )

Multiplication. For u1 ∈ Si 1 and u2 ∈ Sj 2 , we have mul(pp, u1 , u2 ) = u1 × u2 ∈(α ·α2 )

Si+j1

.
(0)

Zero-testing. The procedure isZero(pp, pzt , u) outputs 1 if u ∈ Sκ and 0 otherwise.
Extraction. The procedure extracts a random function of ring elements from their level-κ
encoding. Namely ext(pp, pzt , u) outputs s ∈ {0, 1}λ , such that:

20

CHAPTER 2. DEFINITIONS AND CONSTRUCTIONS(α)

1. For any α ∈ R and u1 , u2 ∈ Sκ , ext(pp, pzt , u1 ) = ext(pp, pzt , u2 ).
(α)

2. The distribution {ext(pp, pzt , u) : α ∈R R, u ∈ Sκ } is nearly uniform over {0, 1}λ .

2.2.3

Approximate graded encodings

As pointed out in [GGH13a], actual constructions only achieve a slightly relaxed definitionof isZero and ext, where isZero can still output 1 even for some non-zero encoding u withnegligible probability, and ext can extract different outputs when applied to encodings ofthe same elements, also with negligible probability. See [GGH12, §2.2.2 and A.2] for thecorresponding definitions.

2.3

Security definitions: the example of Diffie–Hellman key
exchange

The sheer number of subtly or wildly different hardness assumptions used for security
proofs in the field of pairing-based cryptography has been the object of many comments, forbetter or worse [Boy08, KM10]. Unsurprisingly, the more convoluted setting of multilinear
maps and graded encoding schemes has seen the use of an even broader range of potential
hard problems (see e.g. the discussion in [LV16, §1] for a discussion of the particular caseof obfuscation candidates). It seems difficult, at this stage, to point to a particular security
definition that could be singled out as the correct desirable security goal when trying toconstruct multilinear maps.
Nevertheless, one simple security definition has been emphasized in a number of
construction papers, including [GGH13a, CLT13a, LSS14, CLT15], namely the gradedencoding analogue of the decisional Diffie–Hellman assumption. Since it is so common, werecall it here, and add a few comments afterwards discussing the place of that assumption
within the literature.

2.3.1

The graded decisional Diffie–Hellman problem

In their original paper [GGH13a], Garg et al. introduced the graded decisional Diffie–Hellman
assumption (GDDH) as a security goal for graded encoding scheme. It is defined asfollows (this is the definition from [LSS14], which looks slightly different from the one
in [GGH13a, CLT13a], but is easily seen to be equivalent as long as reRand behavescorrectly).
Consider the following procedure, parametrized by λ and κ:
1. Run InstGen(1λ , 1κ ) to obtain (pp, pzt ).
2. Sample aj ← samp(pp) for 0 ≤ j ≤ κ.
3. Compute uj ← reRand(pp, 1, enc(pp, 1, aj )) for 0 ≤ j ≤ κ.
4. Sample b ← samp(pp).

2.3. SECURITY DEFINITIONS: THE EXAMPLE OF KEY EXCHANGE

21

Q
5. Compute the product encoding u∗ = a0 · κj=1 ui of the uj ’s by repeated applicationof the mul procedure (encoding at level κ).
6. Set v (0) = reRand(pp, κ, u∗ ).
7. Set v (1) = reRand(pp, κ, enc(pp, κ, b)).
8. Pick a bit β uniformly at random and set v ← v (β) .
The GDDH assumption asserts that an efficient adversary receiving as input the values(p∗, pzt , u0 , . . . , uκ , v) can only guess the bit β with an advantage negligible in the security
parameter λ.
Clearly, the GDDH assumption implies that the N -party key exchange protocol defined
below is passively secure.
Setup(1λ , 1N ). Output (pp, pzt ) ← InstGen(1λ , 1κ ) as the public parameter, with κ = N −1.
Publish(pp, i). Each party i samples a random ci ← samp(pp) as a secret value, andpublishes as the public value the corresponding level-1 encoding, computed as c0i ←reRand(pp, 1, enc(pp, 1, ci )).
Q
KeyGen(pp, pzt , i, ci , {c0j }j6=i ). Each party i computes c̃i = ci · j6=i c0j , and uses theextraction routine to locally compute the common secret s ← ext(pp, pzt , c̃i ).

2.3.2

Discussion

The GDDH assumption does capture the security of multiparty key exchange (almost
tautologically so!), but may not otherwise be a particularly useful security definition. The
hardness assumptions under which more interesting primitives like witness encryption (e.g.
in [GGSW13]) and indistinguishability obfuscation (e.g. in [PST14]) have been shown toexist are usually considerably more intricate, and not much has been done over multilinear
maps with Diffie–Hellman-like assumptions. As a recent result counter to that trend, albeit
in the Boneh–Silverberg setting rather than over graded encoding schemes, one can mention
the surprising construction by Lin of indistinguishability obfuscation from (subexponential)
DDH over 5-linear maps [Lin16].
Another issue with the GDDH assumption is that, unfortunately, proposed multilinear
candidates have turned out not to satisfy it: as we will see in the next chapter, attacks
have been found against multiparty Diffie–Hellman over the graded encoding schemes
from [GGH13a, CLT13a] and their variants! This is of course considered a serious problem.
A silver lining, however, is that GDDH is not as basic a problem as it sounds.
Indeed, one particular feature of the multiparty Diffie–Hellman scheme as describedabove is that it relies on the possibility for all users to publicly generate and rerandomize
their own encodings. In contrast, in many other schemes, including witness encryption
and indistinguishability obfuscation, the ability to generate encodings of new values isonly used by the same user that generates the system parameters. In those settings, itis thus possible to require secret information in enc and reRand, whereas only arithmetic

22

CHAPTER 2. DEFINITIONS AND CONSTRUCTIONS

operations and zero-testing/extraction remain public procedures. This leads to the definitionof what Albrecht et al. call secret-key graded encoding schemes [ACLL15], which tend to bemuch more difficult to attack than Diffie–Hellman key exchange. Nevertheless, attacks haveindeed been found in that setting as well (e.g. against constructions of indistinguishability
obfuscation [CGH+ 15, MSZ16a, CLLT17]), as we will see in the next chapter.

2.4

A concrete instantiation: the CLT13 graded encoding
scheme

The graded encoding schemes from [GGH13a] and [CLT13a] are very similar to each other,
but a thorough presentation of GGH13 requires somewhat more background material,
especially on algebraic number theory and Gaussian sampling on lattices. Therefore, forsimplicity’s sake, we only give a complete description of the CLT13 scheme. We refer backto §1.3 above for a conceptual-level description of GGH13, and to §2.4.3 below for a shortrundown of the main differences between GGH13 and CLT13.

2.4.1

The shape of CLT13 encodings

In the “integer-based” scheme of [CLT13a], a level-k encoding of a short integer vectorm = (mi ) ∈ Zn is an integer c such that for all 1 ≤ i ≤ n:c≡ri · gi + mizk(mod pi )(2.1)

where the ri ’s are ρ-bit random integers (specific to the encoding c), with the following
secret parameters: the pi ’s are η-bit prime integers, the gi ’s are
Qnα-bit primes, and thedenominator z is a random (invertible) integer modulo x0 = i=1 pi . The integer c istherefore well-defined modulo x0 , where x0 is made public. Since the pi ’s must remain
secret, the user cannot encode the vectors m ∈ Zn by CRT directly from (2.1); instead one
includes in the public parameters a set of ` level-0 encodings x0j of random vectors aj ∈ Zn ,and the user can generate a random level-0 encoding by computing a random subset sumof those x0j ’s.
From (2.1) we see that each integer mi is actually defined modulo gi . Therefore, the
CLT13 scheme encodes vectors m from the ring R = Zg1 × · · · × Zgn .

2.4.2

Detailed description of CLT13

System parameters. The main parameters are the security parameter λ and the required
multilinearity level κ ≤ poly(λ). Based on λ and κ, we choose the vector dimension n, thebit-size η of the primes pi , the bit-size α of the primes gi , the maximum bit-size ρ of therandomness used in encodings, and various other parameters that will be specified later; theconstraints that these parameters must satisfy are described in the next section. For integers
z, p we denote the reduction of z modulo p by (z mod p) or [z]p with −p/2 < [z]p ≤ p/2.

2.4. A CONCRETE INSTANTIATION: THE CLT13 GRADED ENCODING SCHEME

23

Instance generation. (pp, pzt ) ← InstGen(1λQ, 1κ ). This algorithm generates n secretrandom η-bit primes pi and computes x0 = ni=1 pi . It then generates a random invertible integer z modulo x0 , n random α-bit prime integers gi , and a secret matrix
A = (aij ) ∈ Zn×` , where each component aij is randomly generated in [0, gi ) ∩ Z. It
also generates an integer y, three sets of integers {xj }τj=1 , {x0j }`j=1 and {Πj }nj=1 , a zerotesting vector pzt , and a seed s for a strong randomness extractor; the shape of theseelements is detailed below in the respective algorithms where
 they intervene. The parameters pp = n, η, α, ρ, β, τ, `, y, {xj }τj=1 , {x0j }`j=1 , {Πj }nj=1 , s and pzt are finally output andmade public.
Sampling level-zero encodings. c ← samp(pp). Recall that the parameters pp containa set of ` integers x0j , where each x0j encodes at level-0 the column vector aj ∈ Zn of thesecret matrix A = (aij ) ∈ Zn×` . More precisely, the integers x0j are generated by Chineseremaindering, subject to the condition that:0x0j ≡ rij
· gi + aij(mod pi ) for 1 ≤ j ≤ `,(2.2)

0 ’s are randomly generated in (−2ρ , 2ρ ) ∩ Z.
where the rij
Using those values x0j , the randomized sampling algorithm samp(pp) works as follows:
it samples a random binary vector b = (bj ) ∈ {0, 1}` and outputs the level-0 encoding

c=

`
X

bj · x0j mod x0 .

j=1

From Equation (2.2), this gives c ≡the output c is a level-0 encoding:P`0
j=1 rij bjc ≡ ri · gi + miP`(mod pi ). As required,(mod pi )(2.3)· gi +

j=1 aij bj

of some vector m = A · b ∈ Zn which is a random subset-sum of the column vectors aj .
The sizes of the reductions [c]pi are then well controlled for all i:|ri · gi + mi | ≤ ` · 2ρ+α .
A left-over hash lemma argument ensures that m will be statistically close to uniform
over R = Zg1 × · · · × Zgn for suitably chosen parameters. See [CLT13a] for details.
Encodings at higher levels. ck ← enc(pp, k, c). To allow encoding at higher levels, alevel-one random encoding of the vector 1 was published as part of the public parameters
pp. That value is an integer y is generated in such a way that:y≡ri · gi + 1z

for random integers ri ∈ (−2ρ , 2ρ ) ∩ Z.

(mod pi )24

CHAPTER 2. DEFINITIONS AND CONSTRUCTIONSGiven a level-0 encoding c of m ∈ Zn as given by (2.3), a level-1 encoding of the samem can be obtained by computing c1 = c · y mod x0 . Indeed, we then have:
(1)

c1 ≡
(1)

ri

· gi + miz(mod pi )

(2.4)

(1)

for some integers ri , and we get |ri · gi + mi | ≤ ` · 22(ρ+α) for all i. More generally togenerate a level-k encoding we compute ck = c0 · y k mod x0 .
Note however that this element should not be published as is, since it would then be
possible to go back to the lower-level encoding c by simply dividing by y, thus inverting themultilinear map. Instead the level-1 encoding c1 should first be re-randomized into a newlevel-1 encoding c01 for the same vector m, but whose distribution is otherwise independentof the original c. This is done with the following algorithm.
Rerandomization. c0 ← reRand(pp, k, c). To allow rerandomization of encodings at levelk = 1, the public parameters pp contain a set of n integers Πj which are all level-1 random
encodings of zero:$ij · giΠj ≡(mod pi ) for 1 ≤ j ≤ n.
z
The matrix Π = ($ij ) ∈ Zn×n is a diagonally dominant matrix generated as follows: thenon-diagonal entries are randomly and independently generated in (−2ρ , 2ρ ) ∩ Z, while thediagonal entries are randomly generated in (n2ρ , n2ρ + 2ρ ) ∩ Z.
The parameters pp also contain a set of τ integers xj , each one of which is a level-1
random encoding of zero:xj ≡rij · giz(mod pi ) for 1 ≤ j ≤ τ ,and where the column vectors of the matrix (rij ) ∈ Zn×τ are randomly and independently
generated in the half-open parallelepiped spanned by the columns of the previous matrix
Π. This somewhat complicated choice is made to ensure a proper rerandomization.
Given a level-1 encoding c1 as given by (2.4), the procedure reRand rerandomizes it byadding a random subset-sum of the xj ’s and a linear combination of the Πj ’s:
c01 = c1 +

τ
X
j=1

bj · xj +nXb0j · Πj mod x0

(2.5)

j=1

where bj ← {0, 1}, and b0j ← [0, 2µ ) ∩ Z. One of the main technical difficulties of theconstruction of [CLT13a] is the proof that the distribution of c01 is nearly independent of
the input c1 (aside from the fact that both encodings correspond to the same vector m).
This is shown using a “left-over hash lemma over lattices”. We refer to the original paperfor details.
Adding and multiplying encodings. It is clear that one can homomorphically add
encodings. Moreover the product of κ level-1 encodings ui can be interpreted as an

2.4. A CONCRETE INSTANTIATION: THE CLT13 GRADED ENCODING SCHEME

25

encoding of the product. Namely, given level-one encodings uj of vectors mj ∈ Zn for1 ≤ j ≤ κ, with uj ≡ (rij · gi + mij )/z (mod pi ), the productu=κY

uj mod x0

j=1

satisfies:

κ
Q

u≡

ri · gi +(rij · gi + mij )

j=1

≡

zκ

Q
κ


mij mod gi

j=1zκ(mod pi )for some ri ∈ Z. This is a level-κ encodingQκ of the vector m obtained by componentwise
product of the vectors mj , as long as j=1 (rij · gi + mij ) < pi for all i. When computing
the product of κ level-1 encodings from reRand and one level-0 encoding from samp as inmultiparty Diffie–Hellman key exchange, one can easily check that |ri | ≤ (4n2 2µ+ρ+α )κ · ` ·2ρ+1 for all i.
?

Zero testing. isZero(pp, pzt , uκ ) = 0/1. Zero testing of top level encodings is carried out
with the parameter pzt obtained as follows as part of instance generation. First, an integer
matrix H = (hij ) ∈ Zn×n is randomly generated in such a way that H is invertible over
Z and both kHT k∞ ≤ 2β and k(H−1 )T k∞ ≤ 2β , for some parameter β; here k · k∞ is
the operator norm on n × n matrices with respect to the `∞ norm on Rn . A techniquefor generating such an H is presented in the appendix of [CLT13b]. Then, pzt ∈ Zn is
computed as:nX Y(pzt )j =hij · z κ · gi−1 mod pi ·pi0 mod x0 .
(2.6)
i=1

i0 6=iTo determine whether a level-κ encoding c is an encoding of zero or not, one computes
the vector ω = c · pzt mod x0 and tests whether kωk∞ is small: isZero(pp, pzt , c) returns 1
if kωk < x0 · 2−ν and 0 otherwise, for some parameter ν.
The authors of [CLT13a] show that suitable choices of β and ν can ensure that thiszero-testing procedure is then correct for all encodings c whose noise coefficients areappropriately bounded.
Extraction. sk ← ext(pp, pzt , c). To extract a random value depending only on the vector
m encoded in a level-κ encoding c, one proceeds as follows: multiply it by the zero-testing
parameter pzt modulo x0 , collect the ν most significant bits of each of the n components of
the resulting vector, and apply a strong randomness extractor (using the seed s from pp).
More formally:
ext(pp, pzt , c) = Extracts msbsν (c · pzt mod x0 )where msbsν extracts the ν most significant bits of the result. If two encodings c and c0
encode the same m ∈ Zn , one can show (using the precise result establishing the correctnessof zero-testing) that k(c − c0 ) · pzt mod x0 k∞ < x0 · 2−ν−λ , and therefore we expect thatω = c · pzt mod x0 and ω 0 = c0 · pzt mod x0 agree on their ν most significant bits, andtherefore extract to the same value. And conversely if the encoded values are distinct. We
refer to [CLT13a] for the nitty-gritty details.

26

2.4.3

CHAPTER 2. DEFINITIONS AND CONSTRUCTIONS

Differences with GGH13

Recall from §1.3 that the graded encoding scheme from [GGH13a] is defined over the
cyclotomic ring R = Z[x]/(xm + 1), with respect to a certain principal ideal I = hgi withsecret, small generator g. A vector m ∈ R with small coefficients is encoded at level k by
an element of the form:
m+r·g
ck =
mod q,
zk
where z is the secret masking element. This is essentially the same as (2.1) above.
A crucial difference, however, is the shape of the zero-testing parameter. In GGH13, it
is simply of the form:
pzt = h · zκ · g−1 mod qwith h small. Indeed, multiplying a level-κ encoding cκ of m gives:
pzt · cκ ≡ h · (mg−1 + r) mod q
which is small when m = 0, but large otherwise since g−1 is expected to be of full size
modulo q.
Adopting a similar zero-testing element pzt = hz κ /g mod x0 in the CLT13 setting,however, does not work. This is because multiplying that value with a level-κ encodingcκ yields an integer modulo x0 whose reductions modulo all of the prime factors pi of x0
are small. But since those prime factors must be kept secret, there is no way of checking
that directly. This is the reason whyQthe vector pzt in CLT13 has the different shape (2.6),
involving extra factors of the form j6=i pj .
Other differences between the GGH13 and CLT13 constructions mainly reside in thetechnical details of how various properties of the schemes (such as correct sampling andrerandomization) are proved in both settings. And of course, they have different properties
in terms of security.

2.5

GGH15 and the graph-induced approach

As mentioned in §1.3, the third main construction of multilinear maps after [GGH13a]and [CLT13a] is due to Gorbunov, Gentry and Halevi [GGH15] and differs substantiallyfrom the previous constructions even in syntactic terms. The primitive that the authors
achieve is not a graded-encoding scheme, but what they call a graph-induced encoding scheme.
In what follows, we recall the definition of that primitive, and give a description of thescheme they propose.

2.5.1

Graph-induced encoding scheme

The primitive constructed in [GGH15] is parametrized by a certain directed acyclic graph,and encodings are associated to edges (or more precisely, paths of edges) on that graph.
Encodings on the same path can be combined linearly, and multiplication is permitted
between encodings if and only if their associated paths are adjacent. These properties

2.5. GGH15 AND THE GRAPH-INDUCED APPROACH

27

are captured by saying that a graph-induced encoding scheme is a tuple (PrmGen, InstGen,
Sample, Enc, add, neg, mult, ZeroTest, Extract) of efficient algorithms described as follows.
These procedures are subject to some technical correctness conditions for which we refer
to [GGH15]; the paper also discusses possible variants that we do not address in thisdocument.
Parameter generation. PrmGen(1λ , G) takes as inputs the security parameter λ and theunderlying directed graph G, and outputs the global system parameters gp, including inparticular the graph G, a description of the plaintext ring R, and a distribution χ over R
from which plaintexts are sampled.
Instance generation. InstGen(gp) takes as inputs the system parameters and outputs thesecret and public parameters sp, pp.
Ring sampler. The randomized Sample(pp) algorithm outputs an element of the plaintext
ring R sampled according to the distribution χ.
v and a ring
Encoding. Enc(sp, p, α) takes as input the secret parameters, a path p = uelement α ∈ R in the range of Sample, and outputs an encoding up of α according to thepath p.
Addition, negation and multiplication. The arithmetic procedures add(pp, up , u0p ),neg(pp, up ) and mult(pp, up , u0p0 ) are deterministic and take as input the public parameters together with some encodings.
Negation takes an encoding up of some α ∈ R with respect to a path p, and returns
an encoding of −α relative to the same path p. Addition takes encodings up , u0p of someα, α0 ∈ R with respect to the same path p, and returns an encoding of α + α0 relative to p.
Finally, multiplication takes encodings up , u0p0 of α, α0 ∈ R with respect to paths p, p0 which
are consecutive (i.e. p = uv and p0 = vw), and returns an encoding of α · α0 withrespect to the composed path uw.
Zero-testing. The procedure ZeroTest(pp, u) is deterministic, and decides whether a given
encoding u is an encoding of 0 or not.
Extraction. The procedure Extract(pp, u) is deterministic, and returns a λ-bit string
depending only on the underlying plaintext α of the encoding u.

2.5.2

The GGH15 instantiation

We now describe the candidate graph-induced encoding scheme proposed by Gentry et
al. in [GGH15]. Their paper actually describes several variants; we focus here on thecommutative, ring based version, which is the one they use to achieve multiparty Diffie–
Hellman key exchange.
That scheme is defined over the cyclotomic ring R = Z[x]/(xn + 1). Plaintexts are small
elements s in that ring, sampled according to a Gaussian distribution χ. Public parametersconsist in particular of row vectors Av ∈ Rqm (where Rq = R/qR) associated to the vertices
v of the underlying graph. An encoding of s associated with a path u
v in the graph ism×mthen a matrix D ∈ Rwith small coefficients such that:
Au · D = s · Av + E(mod q)28

CHAPTER 2. DEFINITIONS AND CONSTRUCTIONS

for some small error vector E ∈ Rm . Such encodings D can be generated given some secret
trapdoor information generated along with the public vectors Av , using classical latticetechniques [GPV08, MP12]. Formally speaking, the graph-induced encoding procedures
can thus be described as follows.
Parameter generation. PrmGen(1λ , G) computes the system parameters gp, which consistof the graph G, the description of the cyclotomic ring R, the vector dimension m, themodulus q, the plaintext Gaussian distribution χ, a dispersion parameter σ used in trapdoor
sampling, and the number of most significant bits t used for zero-testing and extraction.
Instance generation. InstGen(gp) uses the trapdoor sampling algorithm of Micciancio
and Peikert [MP12] to generate the vectors Av for all vertices v in the underlying graph
G, together with the corresponding trapdoor information τv . The algorithm also samples
a seed and some extra information for randomness extraction. The vectors Av and theextraction information form the public parameters pp, whereas the trapdoors τv form thesecret parameters sp.
Ring sampler. The randomized Sample(pp) simply samples an element s ∈ R according
to the Gaussian distribution χ.
v,
Encoding. Enc(sp, p, s): to sample an encoding for s ∈ R along the path p = u
this algorithm first samples an error vector E ∈ Rm according to χm , and computes
V = s · Av + E. It then uses the trapdoor information τu and the Micciancio–Peikert
algorithm [MP12] to obtain a small matrix D ∈ Rqm×m such that D · Au = V over Rq . Thismatrix D is the required encoding.
Addition, negation and multiplication. Addition, negation and multiplication are thecorresponding operations directly on matrices. It is easy to see that they behave as expected.
Indeed, in the case of addition, if D1 and D2 are encodings of s1 , s2 relative to the same
path uv, so we can write:
A u · D 1 = s 1 · A v + E1

(mod q)A u · D 2 = s 2 · A v + E2

(mod q)we obtain:
Au · (D1 + D2 ) = (s1 + s2 ) · Av + E1 + E2

(mod q).

Similarly, two encodings D1 and D2 relative to path uv and vto get an encoding relative to path u
w. Namely given:
A u · D 1 = s 1 · A v + E1

(mod q)

A v · D2 = s 2 · A w + E 2(mod q)w can be multiplied

we obtain by multiplying the matrix encodings D1 and D2 :Au · D1 · D2 = (s1 · Av + E1 ) · D2

(mod q)= s1 · s2 · Aw + s1 · E2 + E1 · D2
= s1 · s2 · Aw + E

0(mod q)(mod q)2.5. GGH15 AND THE GRAPH-INDUCED APPROACH

29

for some new error vector E0 . Since s1 , E1 , E2 and D2 have small coefficients, E0 still has
small coefficients (compared to q), and therefore the product D1 · D2 is an encoding ofs1 · s2 for the path uw.
Zero-testing. The procedure ZeroTest(pp, D), for an encoding D relative to the pathuv, returns true if and only if kAu · Dk < q/2t+1 . The justification of that procedureis that Au · D = s · Av + E is small for s = 0, but not otherwise (because the matrix Av
itself is not small).
Extraction. The correctness of zero-testing shows that the t most significant bits of D
depend only on the underlying plaintext s. Therefore, we can carry out the extraction
procedure by applying a randomness extractor to those t bits.

Chapter 3

Overview of Known Attacks
3.1

Zeroizing attacks: breaking Diffie–Hellman key exchangeover GGH13 and CLT13

3.1.1

Notation and attack goals

The GGH13 and CLT13 schemes share a very similar structure; here we summarize thecommon features that are used in the attacks:• Each encoding is “associated” with the vector of small integers in the numerator. For
GGH13 this is a 1-vector consisting of a single algebraic integer,and for CLT13 this isa vector of n integers in Z. Below we write informally u ∼ (a1 , . . . , an ) to denote thefact that the encoding u is associated with the vector of ai ’s. Roughly speaking, thegoal of the attacks is to recover the vector (aj )j from the encoding u. Recovering thisvector (even if not in full) is usually considered a break of the scheme.
• An encoding of zero is associated with a vector divisible by the gj ’s, namely u ∼ (gj rj )jfor some rj ’s.
• Addition and multiplication of encodings acts entry-wise on the vector of integers in
the numerator. Importantly, the addition and multiplication of these vectors is done
over the integers, with no modular reduction. This is because a wrap-around in these
operations is an error condition, and so the parameters are always set to ensure thatit does not happen.
• If u ∼ (gj rj )j is an encodingof zero at the top level, then applying the zero-test to uPyields the integer w = j rj ρj , where the rj ’s are the multipliers from the numerator
vector and the ρj ’s are system parameters independent of u.
In other words, applying the zero-test to an encoding of zero yields the inner-product of
the associated vector (without the gj ’s) with a fixed secret vector. (In GGH13 thisQ is the1-vector (h), in CLT13 the vector is (p∗j hj )j , where we denote p∗j = x0 /pj = i6=j pi ).
Importantly, here too the inner product is over the integers, with no modular reduction.
31

32

3.1.2

CHAPTER 3. OVERVIEW OF KNOWN ATTACKS

Weak-DL attack on GGH13 and the Hu–Jia attack

The first published attack against the GGH13 scheme appears in the original paper itself[GGH13a]. It considers the following setting. Suppose one gets a level-t encoding of zerou0 ∼ (gr) and many other level-(κ − t) encodings um ∼ (am ). Multiplying u0 by any of
the um ’s yields a top-level encoding of zero u0 um ∼ (gram ), and applying the zero-testyields the algebraic integer wm = hram . Note that this almost recovers the numerators
am ’s; indeed we have them up to the common factor h0 = hr.
If we also knew the ideal Ig = gR that defines the plaintext space, then being able torecover the numerator up to a constant is enough to break many hardness assumptions.
For example, given an encoded matrix we could compute its determinant (modulo Ig ) up
to a constant, which would tell us whether or not the encoded matrix has full rank.
Typically, however, the ideal Ig is not explicitly given. Even in that case, however, Garg
et al. described how it can be recovered in certain cases using GCD computations. Roughly,
we can use GCD to identify and remove the common factor h0 , thereby getting the am ’s
themselves, except that these are all algebraic integers so we only have GCD in terms of
their ideals. Recovering the ideal Ia = aR is not always useful, e.g., if Ia and Ig are co-prime
then knowing Ia does not tell us anything about our plaintext coset a + Ig . However ifsome of the ui ’s are themselves encodings of zero, namely ai = gri , then given enoughideals Iai = gri R we could again use GCD calculations to recover the ideal Ig itself, andthen use that knowledge to attack the non-zero encodings among the ui ’s. This attack wascalled a “weak discrete-log attack” in [GGH13a]. It is easily seen to break the multilinear
analogue of assumptions like subgroup membership: see [GGH13a, §4.2].

3.1.3

The zeroizing attack of Cheon et al.

In [CHL+ 15], Cheon, Han, Lee, Ryu and Stehlé describe a major extension of the GGH13
zeroizing attack, which can be used to completely break multiparty Diffie–Hellman key
agreement over CLT13, and more generally any CLT13-based scheme in which a similarfamily of low-level encodings of zero are available. The attack recovers the factorization ofx0 , and then all secret information.
To mount the zeroizing attack of Cheon et al. [CHL+ 15], one needs three sets ofencoded inputs, which we denote by A = {Ai : i = 1, . . . , n}, B = {B0 , B1 }, andC = {Cj : j = 1, . . . , n} (with n the dimension of the numerator vectors). The A’s are
all random encoding of zeros, the B’s are the target of the attack, and the C’s are justhelper encodings of random vectors. The levels of these encodings are such that multiplying
Ai · Bσ · Cj yields a top-level encoding of zero for any i, σ, j. Below we denote the numerator
vectors associated with these encodings by
Ai ∼ (g1 ri,1 , . . . , gn ri,n ), Bσ ∼ (bσ,1 , . . . , bσ,n ), and Cj ∼ (cj,1 , . . . , cj,n ).
Multiplying Ai · Bσ · Cj yields a top-level encoding of zero, associated with the vector
Ai · Bσ · Cj ∼ (g1 ri,1 bσ,1 cj,1 , . . . , gn ri,n bσ,n cj,nP). Applying the zero-test we get a four-wiseinner product, yielding the integer wσ [i, j] = nk=1 ρk ri,k bσ,k cj,k . We can write this four-wise33

3.1. ZEROIZING ATTACKS: BREAKING GGH13 AND CLT13 KEY EXCHANGE
inner product in matrix form as
wσ [i, j] = (ri,1 . . . ri,n ) × 

ρ1 bσ,1cj,1
  ..  ×  . ,..

.
ρn bσ,ncj,nand denote the vector on the left by ai , the matrix in the middle by Bσ0 , and the vector on
the right by cj . For a fixed σ, let i, j range over 1, . . . , n. This yields an n × n matrix of
integers Wσ = [wσ [i, j]]i,j = A0 × Bσ0 × C 0 , where A0 has the ai ’s for rows and C 0 has the cj ’s
for columns. Since the ri,k ’s, bσ,k ’s, cj,k ’s and ρk ’s are all random (small) quantities, thenwith high probability the matrices are all invertible (over the rationals). Having computed
the matrices Wσ , the attacker now sets
W = W0 × W1−1 = (A0 B00 C 0 ) × (A0 B10 , C 0 )−1 = A0 × (B00 × B10−1) × A0−1.

Observe now that B ∗ = B00 × B10 −1 is a diagonal matrix with b0,j /b1,j on the diagonal,
and thus the eigenvalues of B ∗ are all the ratios b0,j /b1,j . And since W and B ∗ are similar
matrices, then also the eigenvalues of W are the b0,j /b1,j ’s. Hence once it computes W ,the attacker can find its eigenvalues (over the rationals) and obtain all the ratios b0,j /b1,j .
These ratios may be enough by themselves to break some hardness assumptions, but for
CLT13 it is possible to use them to factor x0 , thereby getting a complete break. Specifically,
since each ratio is rational it can be written as u/v = b0,j /b1,j with u, v co-prime integers.
Recalling now that B0 , B1 are two encodings at the same level (say, level t) with numerator
vectors (b0,1 , . . . , b0,n ) and (b1,1 , . . . , b1,n ), respectively, we get thatuB1 − vB0 = [CRT (ub1,1 − vb0,1 , . . . , ub1,n − vb0,n ) /z t ]x0 .
This means that the j-th CRT component is ub1,j − vb0,j = 0, and with high probability
the others are not, so we get gcd(x0 , uB1 − vB0 ) = pj .

3.1.4

The attack of Hu and Jia

The attack of Cheon et al. [CHL+ 15] relies crucially on the fact that CLT13 is defined overthe integers, and on the fact that finding the factorization of x0 suffices to break the scheme.
These aspects have no counterpart in GGH13 setting, and therefore the attack does not
apply (although it does apply to a matrix variant of GGH13: see [CGH+ 15]).
However, it turns out that the GGH13 version of multiparty Diffie–Hellman key exchange
is also insecure. This was shown by Hu and Jia [HJ16], using another attack that expands
upon the weak-DL attack above. One can sum up the attack as follows.
An eavesdropper in Diffie–Hellman key exchange sees encodings ui = ei y+ρi0 x0 +ρi1 x1 ,0 ≤ i ≤ κ, where x0 , x0 , y are level-1 encodings of 0, 0, 1 respectively, and the ei and ρij
are small.
The secret derived byQ
Qthe parties is obtained from the most significant bits of
pzt · ui , or equivalently h/g · ei .
The first step of Hu and Jia’s attack is the weak-DL computation. Applying zero-testing
to ui · x0 · y κ−2 , one gets:
vi = pzt · ui · x0 · y κ−2 mod q = ei b0 h + ξi g

34

CHAPTER 3. OVERVIEW OF KNOWN ATTACKS

for some small ξi (without modular reduction). Similarly, applying zero-testing to x0 · y κ−1 ,one obtains:˜ṽ = pzt · x0 · y κ−1 mod q = b0 h + ξgagain without modular reduction. As a result, ṽ −1 · vi ≡ ei (mod Ig ), where Ig is theprincipal ideal generated by g, as above. If we denote by wi a representative of ṽ −1 ·vi mod Ig ,then the product:
κ
κ
Y
Y
η :=
wi ≡
ei (mod Ig ).
i=0

i=0

Q
Thus, there exists some ζ0 ∈ R such that η = ei + ζg. This element ζ, however, is not apriori small, so we cannot directly solve the problem by taking the most significant bits of
η. Instead, Hu and Jia introduce some auxiliary zero-test values as follows:
Xi = pzt · x1 xi y κ−2

mod q = h(1 + ag)κ−2 b1 bi g

Y = pzt · x1 y κ−1 mod q = h(1 + ag)κ−1 b1 g.
Q
Then Y · η is congruent to Y · ei modulo
b1 g, and since X1 is a multiple of b1 g, η 0 =QY · η mod X0 is also congruent to Y · ei modulo b1 g. Thus:Y
y/x1 · η 0 mod q = pzt · y κ ·ei + ζ 0 · (1 + ag) mod q
Qfor some small ζ 0 . Thus, we have computed h/g · ei + small error mod q, which breaks
the Diffie–Hellman key exchange as required.

3.1.5

Other zeroizing attacks

Following the attack of Cheon et al. [CHL+ 15], several papers attempted to modify the
CLT13 construction in order to protect against the attack. However, the modified variants
turned out to be vulnerable to extensions of the same attack.
This includes in particular the “immunization technique” suggested by Boneh, Wu
and Zimmerman [BWZ14] and the countermeasure proposed by Garg, Gentry, Halevi
and Zhandry in [GGHZ14, §7], both of which can be broken by essentially extending thedimension of the matrices involved in Cheon et al.’s attack by a small factor, as describedin [CLT14, CGH+ 15]. This also includes the CLT15 graded encoded scheme, proposed byCoron, Lepoint and Tibouchi in [CLT15], which was broken soon after it was published by
Cheon, Fouque, Lee, Minaud and Ryu [CFL+ 16], again using a simple extension of Cheonet al.’s attack.

3.2

Graph-induced cryptanalysis: breaking GGH15 key
exchange

Diffie–Hellman key exchange is also insecure over GGH15 multilinear maps. The protocol
was broken by Coron, Lee, Lepoint and Tibouchi [CLLT16a], both in the basic case andwhen additional security defenses are implemented. Their attack also breaks the graphinduced variant of GGH13. We give a description of the basic attack below.

3.2. GRAPH-INDUCED CRYPTANALYSIS: BREAKING GGH15 KEY EXCHANGE

3.2.1

35

GGH15-based multiparty Diffie–Hellman

We first recall the structure of the multiparty Diffie–Hellman key exchange protocol over
GGH15 [GGH15]. We consider the protocol with k users. As illustrated in Figure 3.1 fork = 3 users, each user i for 1 ≤ i ≤ k has a directed path of vectors Ai,1 , . . . , Ai,k+1 , allsharing the same end-point A0 = Ai,k+1 . The i-th user will use the resulting chain to
extract the session key. Each user i has a secret exponent si . Each secret exponent si will
be encoded in each of the k chains; the encoding of si on the j-th chain for j 6= i will be
published, while the encoding of si on the i-th chain will be kept private by user i. Therefore
on the i-th chain only user i will be able to compute the session key. The exponents si
are encoded in a “round robin” fashion; namely the i-th secret si is encoded on the chainof user j at edge ` = i + j − 1, with index arithmetic modulo k. Only the vectors Ai,1
for 1 ≤ i ≤ k are made public to enable extraction of the session-key; the others are kept
private.
A1,1s1 , (D1,1 )A1,2s2 , D1,2

A1,3

s3 ,

D1

,3

A2,1

s3 , D2,1

A2,2

s1 , D2,2

A2,3

s2 , (D2,3 )sA3,1s2 , D3,1

A3,2

s3 , (D3,2 )

D 3,3
1,

A0

A3,3

Figure 3.1: Graph of a key agreement between 3 parties for GGH15. The vertices containrandom vectors Aij , and encodings are represented on the edges. Each party is represented
by a different color, keeps the encoding in parenthesis secret and publishes the two otherencodings.

3.2.2

The attack of Coron et al.

In [CLLT16a], Coron et al. show how an eavesdropper can recover the secret key derived
by the parties in the previous protocol in polynomial time. The attack proceeds in two
steps:
1. As a first step, the attacker will express one secret exponent s1 as a linear combination of the other secret exponents t1,` , using a variant of the attack of Cheon etal. [CHL+ 15]. However this does not immediately break the protocol, because thecoefficients of the linear combination are not small.
2. In the second step, which can be seen as a generalization of the techniques of Hu
and Jia [HJ16], the attacker will compute an equivalent of the private encoding of36

CHAPTER 3. OVERVIEW OF KNOWN ATTACKS
User 1 from the previous linear combination, by correcting the error due to the largecoefficients. This breaks the key-exchange protocol.

We now describe the first step in the particular case of 3 users, which illustrates the mainideas of the attack while avoiding some technical complications. We refer to [CLLT16a] forthe whole details. In the 3-user case, we have the following relations:
A1,1 · D1,1 = s1 · A1,2 + F1,1 (mod q)
A1,2 · D1,2 = s2 · A1,3 + F1,2 (mod q)
A1,3 · D1,3 = s3 · A0 + F1,3 (mod q)

A1,1 · C1,1,` = t1,` · A1,2 + E1,1,` (mod q)
A1,2 · C1,2,` = t2,` · A1,3 + E1,2,` (mod q)
A1,3 · C1,3,` = t3,` · A0 + E1,3,` (mod q)

A2,1 · D2,1 = s3 · A2,2 + F2,1 (mod q)
A2,2 · D2,2 = s1 · A2,3 + F2,2 (mod q)
A2,3 · D2,3 = s2 · A0 + F2,3 (mod q)

A2,1 · C2,1,` = t3,` · A2,2 + E2,1,` (mod q)
A2,2 · C2,2,` = t1,` · A2,3 + E2,2,` (mod q)
A2,3 · C2,3,` = t2,` · A0 + E2,3,` (mod q)

A3,1 · D3,1 = s2 · A3,2 + F3,1 (mod q)
A3,2 · D3,2 = s3 · A3,3 + F3,2 (mod q)
A3,3 · D3,3 = s1 · A0 + F3,3 (mod q)

A3,1 · C3,1,` = t2,` · A3,2 + E3,1,` (mod q)
A3,2 · C3,2,` = t3,` · A3,3 + E3,2,` (mod q)
A3,3 · C3,3,` = t1,` · A0 + E3,3,` (mod q)

where all encodings Ci,j,` and Di,j are public, except D1,1 which is private on Row 1, D2,3
is private on Row 2, and D3,2 is private on Row 3. The corresponding graph is illustrated
in Figure 3.1. Note that on each row we have used the same index ` for t1,` , t2,` and t3,` ,but on a given row one can obviously compute product of encodings for different indices.
In the first step of the attack, we show that we can express s1 as a linear combinationsof the t1,` ’s. For this we consider the rows 2 and 3, for which the encodings D2,2 and D3,3
corresponding to s1 are public. In the remaining of the attack, we always consider a fixedindex ` = 1 for the encodings corresponding to t3,` , and for simplicity we write t3 := t3,1 ,C1,3 := C1,3,1 , C2,1 := C2,1,1 and C3,2 := C3,2,1 .
Since we always work with the same t3 , on Row 2 we define the product encodingsĈ2,2,` := C2,1 · C2,2,` , and on Row 3 we define the product encodings Ĉ3,2,` := C3,1,` · C3,2 ;recall that we use a fixed index for t3 . Therefore we can write:
A2,1 · Ĉ2,2,` = t1,` · t3 · A2,3 + Ê2,2,`
A2,3 · C2,3,` = t2,` · A0 + E2,3,`(3.1)(mod q)A3,1 · Ĉ3,2,` = t2,` · t3 · A3,3 + Ê3,2,`
A3,3 · C3,3,` = t1,` · A0 + E3,3,`(mod q)(mod q)(mod q)for some small error vectors Ê2,2,` and Ê3,2,` .
For simplicity of notations, we first consider a fixed index i for the encodings corresponding to t1,i , and we write t1 := t1,i , Ĉ2,2 := Ĉ2,2,i and C3,3 := C3,3,i . Similarly weconsider a fixed index j for the encodings corresponding to t2,j and we write t2 := t2,j ,C2,3 := C2,3,j and Ĉ3,2 := Ĉ3,2,j . We use similar notations for the corresponding error
vectors.
All previous equations hold modulo q only. To get a result over R instead of only
modulo q, we compute the difference between two rows, for the same product of secret3.2. GRAPH-INDUCED CRYPTANALYSIS: BREAKING GGH15 KEY EXCHANGE

37

exponents. More precisely, we compute:(3.2)

ω = A2,1 · Ĉ2,2 · C2,3 − A3,1 · Ĉ3,2 · C3,3
= t1 · t3 · t2 · A0 + t1 · t3 · E2,3 + Ê2,2 · C2,3
− t2 · t3 · t1 · A0 − t2 · t3 · E3,3 − Ê3,2 · C3,3
= t1 · t3 · E2,3 + Ê2,2 · C2,3 − t2 · t3 · E3,3 − Ê3,2 · C3,3 .

(3.3)

Namely the latter equation holds over R (and not only modulo q) because all the termsin (3.3) have small coefficients; namely the only term t1 · t2 · t3 · A0 with large coefficientsmodulo q is canceled when doing the subtraction.
We have that ω is a vector of dimension m. Now an important step is to restrict ourselvesto the first component of ω. Namely in order to apply the same technique as in Cheon etal.’s attack, we would like to express ω as the product of two vectors, where the left vector
corresponds to User 1 and the right vector corresponds to User 2. However due to the“round-robin” fashion of exponent encodings, for this we would need to swap the productÊ3,2 · C3,3 appearing in (3.3), since Ê3,2 corresponds to User 2 while C3,3 corresponds toUser 1; this cannot be done if we consider the full vector ω. By restricting ourselves to thefirst component of ω, the product Ê3,2 · C3,3 becomes a simple scalar product that can beswapped; namely the scalar product of Ê3,2 by the first column vector C03,3 of the matrix
C3,3 . We obtain the scalar:ω = t1 · t3 · E2,3 + Ê2,2 · C02,3 − t2 · t3 · E3,3 − C03,3 · Ê3,2
where C02,3 and C03,3 are the first column vectors of C2,3 and C3,3 respectively, both ofdimension m; similarly E2,3 and E3,3 are the first components of E2,3 and E3,3 respectively.
We can now write ω as the scalar product of 2 vectors, the left one corresponding only
to User 1, and the right one corresponding only to User 2:hω = t1

Ê2,2

E3,3



t3 · E2,3i  C0
2,3 
C03,3 · 
 −t2 · t3  .
−Ê3,2

Note that the two vectors in the product have dimension 2m + 2.
As in the attack of Cheon et al. [CHL+ 15], we can now extend ω to a matrix byconsidering many left row vectors and many right column vectors. However instead of asquare matrix as in Cheon et al.’s attack, we consider a rectangular matrix with 2m + 3
rows and 2m + 2 columns. In (3.2), this is done by considering 2m + 3 public encodingsĈ2,2,i and C3,3,i corresponding to User 1, and similarly 2m + 2 encodings C2,3,j and Ĉ3,2,jcorresponding to User 2, for 1 ≤ i ≤ 2m + 3 and 1 ≤ j ≤ 2m + 2. More precisely wecompute as previously over R the following matrix elements, restricting ourselves to thefirst component:(W)ij = A2,1 · Ĉ2,2,i · C02,3,j − A3,1 · Ĉ3,2,j · C03,3,i

(3.4)

38

CHAPTER 3. OVERVIEW OF KNOWN ATTACKS

and as previously we can write:h(W)ij = t1,iÊ2,2,i
t3 · E2,3,ji  C0
2,3,j C03,3,i ·  −t2,j · t3  .
−Ê3,2,jE3,3,iWe obtain a (2m + 3) × (2m + 2) matrix W with:


 

...


W=
t1,i

Ê2,2,iE3,3,i .
.
C03,3,i 
· .

...
{z
A

|

} |

t3 · E2,3,jC02,3,j−t2,j · t3
−Ê3,2,j
{z
B


.. 
. 

}

where the matrix A has 2m + 3 rows vectors, each of dimension 2m + 2, and the matrix B
has 2m + 2 column vectors, each of dimension 2m + 2; hence B is a square matrix.
By doing linear algebra, we can find a vector u over R of dimension 2m + 3 such thatu · W = 0, which gives:(u · A) · B = 0 .
Heuristically with good probability the matrix B is invertible, which implies:u · A = 0.
Since the first column of the matrix A is the column vector given by the t1,i ’s, such vector
u gives a linear relation among the secret exponents t1,i .
Moreover, since the encodings D2,2 and D3,3 corresponding to s1 are public, we can
express s1 as a linear combination of the t1,i ’s, over R. Namely we can define as previously
the product encoding D̂2,2 := C2,1 · D2,2 , with:
A2,1 · D̂2,2 = s1 · t3 · A2,3 + F̂2,2(mod q)for some small error vector F̂2,2 , and we can now compute the same (W)ij as in (3.4) but
with D̂2,2 and D03,3 instead of Ĉ2,2,i and C03,3,i , where D03,3 is the first column of D3,3 . Moreprecisely, we compute for all 1 ≤ j ≤ 2m + 2:
ωj = A2,1 · D̂2,2 · C02,3,j − A3,1 · Ĉ3,2,j · D03,3
which gives as previously:hωj = s1

F̂2,2

F3,3



t3 · E2,3,ji  C0
2,3,j D03,3 · 
 −t2,j · t3  .
−Ê3,2,j39

3.3. ATTACKS ON OBFUSCATIONThis implies that we can replace any row vector [t1,i Ê2,2,i E3,3,i C03,3,i ] in the matrix A by
the row vector:[s1 F̂2,2 F3,3 D03,3 ](3.5)
where D03,3 is the first column of D3,3 , and F3,3 is the first component of F3,3 . Using theprevious technique, we can therefore obtain a linear relation between s1 and the t1,i ’s over
R. More precisely, with overwhelming probability, such a relation can be put in the form:µ · s1 =2m+2X

λi · t1,i

(3.6)

i=1

with µ ∈ Z and λ1 , . . . , λ2m+2 ∈ R. Indeed, we obtain such a relation by computing thekernel of the matrix analogous to W above in echelon form over the fraction field of R,
which gives the kernel of the corresponding matrix A (assuming that B is invertible). Unlessa minor of that matrix vanishes, which happens with only negligible probability, this gives
a relation where the coefficient of s1 is 1 and the other coefficients are in the fraction field
R ⊗Z Q of R. By clearing denominators, we get an expression of the form (3.6).
Then, by considering exactly one additional t1,i (say t1,2m+3 ) and carrying out the same
computations with indices i = 2, . . . , 2m + 3 instead of i = 1, . . . , 2m + 2, we get a second
relation:2m+3X
ν · s1 =λ0i · t1,i .
i=2

If the integers µ and ν are relatively prime, which happens with significant probability, we
can apply Bézout’s identity to obtain a linear relation in R where the coefficient of s1 is 1:
s1 =

2m+3
X

αi · t1,i ,

(3.7)

i=1

which completes this first attack step and our description.

3.3

Attacks on obfuscation

We conclude this chapter by a short discussion of proposed attacks against constructions ofindistinguishability obfuscation. Since a precise description of the constructions themselves
exceeds the scope of this document, we simply give a very rough idea of what the attacks
can achieve and of their limitations, without any attempt to provide technical details, forwhich we refer to the corresponding papers.

3.3.1

Attacks against obfuscation over CLT13

Candidate constructions of indistinguishability obfuscation from multilinear maps (aside
from more recent techniques via functional encryption) can be broadly divided into two
types: one the one hand, obfuscation for branching programs, that rely on Barrington’s

40

CHAPTER 3. OVERVIEW OF KNOWN ATTACKS

theorem to obfuscate circuits, and on the other hand, circuit-obfuscation constructions, thatwork directly on circuits. Limited attacks exist on both types of schemes when instantiatedover CLT13.
Attacks on branching program obfuscation. Recall that a branching program is acollection of pairs Ai,0 , Ai,1 , 1 ≤ i ≤ t, of d × d square matrices together with some input
assignment function inp : {1, . . . , t} → {1, . . . , n}. It computes the Boolean function on n
inputs bits given by:(Q
1 if ti=1 Ai,xinp(i) = Id
f (x1 , . . . , xn ) =.
0 otherwise
Roughly speaking, branching program obfuscation candidates such as the one described by
Garg et al. in [GGH+ 13b] work by taking such a branching program, randomizing it using
Kilian’s technique, increasing the dimension of the matrices with some diagonal padding,and then encoding the expanded randomized matrices element-wise using a multilinear
map.
In [CGH+ 15], Coron et al. showed that such a construction provides the necessary data
to apply the attack of Cheon et al. [CHL+ 15] in the particular case when the branching
program has a decomposable structure, i.e. when the successive matrices can be divided into
three groups, each depending on a different subset of input bits. This attack does not apply
to actual obfuscation candidates, however, because the branching programs produced byBarrigton’s theorem never have the required decomposable structure.
However, Coron, Lee, Lepoint and Tibouchi [CLLT16b, CLLT17] later showed how
to dramatically expand the scope of this attack, and make it practically relevant to an
actual obfuscation candidates when applied to a large class of functions. The key idea of
their attack is the observation that the order of matrices in a branching program can berearranged in an essentially arbitrary way by taking tensor products, at the cost of increasing
the dimension. This can be used to force branching programs into a decomposition suitable
to apply the previous attack, at least if the blow-up in matrix dimension is not too large.
As a result, they were able to break the original candidate obfuscator from [GGH+ 13b]when instantiated over CLT13 multilinear maps, as well as the so-called single-input versionsof many subsequent candidate obfuscators, including [MSW14, AGIS14, PST14, BGK+ 14,
BMSZ16], again over CLT13. A surprising feature of the attack of [CLLT16b, CLLT17] isthat, assuming the existence of certain classes of pseudorandom functions computed bybranching programs of short length, it can also break the obfuscator described in [GMM+ 16],
which is proved secure in the weak multilinear map model, a model that was believed tocapture all known classes of attacks on multilinear map constructions.
The attack of [CLLT16b, CLLT17] can only target functions satisfying a property called
input-partionability, however. And soon after the attack was made public, Fernando,
Rasmussen and Sahai proposed a generic countermeasure to protect against all attacks ofthat nature [FRS16]. It works by adding to the input of all functions a “signature structure”
that prevents input-partionability.

3.3. ATTACKS ON OBFUSCATION

41

Attacks on circuit-obfuscation. Coron et al. [CGH+ 15] also showed that the attackof Cheon et al. can be extended to partially break the circuit-obfuscation schemes ofZimmerman [Zim15] and Applebaum–Brakerski [AB15]. More precisely, the two papers
present a “simple” scheme (which is essentially the same in both papers) and more advanced
variants (which differ between the two papers). Coron et al. target the simple scheme, andshow that an attack similar to Cheon at al.’s can be applied to that scheme when obfuscating
simple enough circuits, such as point functions.
Note that this simple scheme uses so-called “composite-order” multilinear maps, whichcannot be instantiated over GGH13, so a CLT13-based instantiation is the only possible
concrete instantiation of that scheme known so far, and it is partially broken. However, themore advanced versions are not shown to be vulnerable.

3.3.2

Attacks against obfuscation over GGH13 and GGH15

Setting aside obfuscation candidates relying on composite order multilinear maps (whichcannot be instantiated over GGH13), the first attack against indistinguishability obfuscators over GGH13 was the annihilation attack introduced by Miles, Sahai and Zhandry
in [MSZ16a]. It is conceptually different from zeroizing attacks.
The attack targets a family of obfuscator that Miles et al. describe axiomatically, and that
captures in particular the constructions from [MSW14, AGIS14, PST14, BGK+ 14, BMSZ16].
One way of describing the general idea of the attack is to note that the zero-testing values
ωi arising from the evaluation
P a given branching program are ring elements that can be
expressed as polynomials j fij (r1 , . . . , r` )g j on the error factors rk involved in encodings.
And for a different but functionally equivalent branching program, one will find polynomials
fij0 6= fij in general. One can then for instance distinguish between two different but
functionally equivalent branching programs by finding a polynomial relation Q between thefi,0 ’s (i.e. Q(f1,0 , . . . , fm,0 ) = 0). Indeed, such a relation will ensure that Q(ω1 , . . . , ωm ) isalways in the ideal Ig for the first branching program, whereas this will typically happen
with only negligible probability for the second branching program, for which the polynomial
relation does not hold.
The attack of [MSZ16a] even applies to the dual-input versions of the schemes mentioned
above over GGH13. However, several subsequent multilinear map constructions have been
proved to be secure against this class of attack [GMS16, MSZ16b].
More recently, several extensions of the attack of [MSZ16a] have been proposed. Chen,
Gentry and Halevi [CGH16] show how to break the original obfuscation candidate ofGarg et al. [GGH+ 13b] over GGH13 using annihilation attacks. They also combine theannihilation technique with the attack of [CLLT16a] to break the construction of obfuscation
over GGH15 multilinear maps [GGH15]. Like [CLLT17], however, these attacks are limited
to input partitionable functions, and can thus be thwarted using the techniques of [FRS16].
One can also mention the work of Apon et al. [ADGM16], which introduces an efficiently
testable condition for breaking obfuscation over GGH13 using annihilation attacks, anduses it to attack a larger class of branching programs than [MSZ16a]. The constructions
that are provably secure against annihilation attacks [GMS16, MSZ16b] remain unaffected,
however.

Chapter 4

Conclusions and Perspectives
4.1

Status of multilinear map-based primitives

We present a snapshot of the current security status of major primitives based on multilinear
maps at the time of this writing. The situation is likely to evolve rapidly, however. For an
up-to-date overview of current results, we refer the reader to Martin Albrecht’s excellent
resource entitled “Are Graded Encoding Schemes Broken Yet?” [Alb16].
Multiparty Diffie–Hellman key exchange. Over all proposed multilinear map candidates, multiparty Diffie–Hellman key exchange is broken. Over CLT13 multilinear maps,
it was broken by Cheon et al. [CHL+ 15], and later attempts to protect against the attack [BWZ14, GGHZ14, CLT15] were also broken by extensions of that attack [CLT14,
CGH+ 15, CFL+ 16]. Over GGH13 multilinear maps, it was broken by Hu and Jia [HJ16],
and that attack also applies to the optimized versions proposed in [LSS14, ACLL15]. Finally,
over GGH15 multilinear maps, it was broken by Coron et al. [CLLT16a].
Indistinguishability obfuscation. Attacks have been demonstrated against some candidate constructions of indistinguishability obfuscation over each of GGH13, CLT13 andGGH15, but not everything is broken. More precisely, the annihilation attack of Miles, Sahai
and Zhandry [MSZ16a] and its extensions [CGH16, ADGM16] broke almost all indistinguishability obfuscators over GGH13 existing at the time, but later on, constructions were
proposed that are provably secure against it [GMS16, MSZ16b]. The zeroizing attack ofCoron et al. [CLLT16b, CLLT17] broke almost all indistinguishability obfuscators over
CLT13 existing at the time in the single-input setting. However, dual-input constructions areunaffected. Moreover, the attack only affects input-partitionable functionalities, and can thus
be thwarted using the generic countermeasure of Fernando, Rasmussen and Sahai [FRS16].
Finally, Chen, Gentry and Halevi [CGH16] obtained an attack indistinguishability obfuscation over GGH15 [GGH15]. However, this attack also applies to input-partitionable
functionalities only, and is thus thwarted by [FRS16].
43

44

CHAPTER 4. CONCLUSIONS AND PERSPECTIVES

Other primitives. No specific cryptanalytic work so far has examined the security of othermultilinear map-based primitives like witness encryption. However, a reasonable expectationis that constructions relying on secret-key graded encodings, like witness encryption, arelikely to behave similarly to indistinguishability obfuscation, whereas constructions relying
on public-key encodings, like some constructions of ABE, are likely to fall prey to the samekind of attacks as Diffie–Hellman key exchange.
Note also that indistinguishability obfuscation is sufficient to obtain provably secure
multilinear maps [AFH+ 16], so theoretically speaking, as long as indistinguishability obfuscation exists, everything, including multiparty Diffie–Hellman, can be instantiated securely.
Of course, the efficiency of such a giant pyramid construction is guaranteed to be atrocious.

4.2

Future prospects

As we have seen, the whole multilinear map edifice is standing on shaky ground, and its
security situation is quite precarious. Further progress on the cryptanalytic side is likely, andcould easily bring about the unravelling of the last few remaining candidate constructionsof indistinguishability obfuscation. And even if one believes that those schemes will stay
secure, it is fair to say that the current situation, in which we have to rely on multilinear map
constructions that were found to not even satisfy their original, basic security definition, is
unsatisfactory. Progress is also being made on the construction side, however, and it could
ultimately yield to much more solid foundations. This could come from several directions.
Indistinguishability obfuscation. The conditions needed to obtain indistinguishability
obfuscation are becoming less and less stringent. Although early candidate constructions
required multilinear maps with polynomially large degrees satisfying very strong security
assumptions, this has recently been reduced to conservative assumptions over n-linear maps
for n as low as 5 [Lin16, AS16]. If n could be reduced further, one might eventually be able
to dispense with multilinear maps altogether and obtain everything from pairings.
Functional encryption. Compact functional encryption for relatively limited classes offunctions would also suffice to obtain indistinguishability obfuscation and hence everythingelse. And current techniques are not very far off from achieving it from LWE [GKP+ 13,
GVW15].
New multilinear maps. Since low-degree multilinear maps are now known to suffice forindistinguishability obfuscation, and hence essentially all applications, geometry-based
techniques, which were originally ruled out by Boneh and Silverberg, might be usefully
revisited, as has been done on a few occasions [RH09].
In any event, the field of multilinear maps can certainly expect many interesting developments in the months and years to come.

Bibliography[AB15]

Benny Applebaum and Zvika Brakerski. Obfuscating circuits via compositeorder graded encoding. In Yevgeniy Dodis and Jesper Buus Nielsen, editors,
TCC 2015, Part II, volume 9015 of LNCS, pages 528–556, Warsaw, Poland,
March 23–25, 2015. Springer, Heidelberg, Germany.

[ABD16]

Martin R. Albrecht, Shi Bai, and Léo Ducas. A subfield lattice attack on overstretched NTRU assumptions - cryptanalysis of some FHE and graded encoding
schemes. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016,
Part I, volume 9814 of LNCS, pages 153–178, Santa Barbara, CA, USA, August 14–18, 2016. Springer, Heidelberg, Germany.

[ABDP15]

Michel Abdalla, Florian Bourse, Angelo De Caro, and David Pointcheval.
Simple functional encryption schemes for inner products. In Jonathan Katz,
editor, PKC 2015, volume 9020 of LNCS, pages 733–751, Gaithersburg, MD,
USA, March 30 – April 1, 2015. Springer, Heidelberg, Germany.

[ABSV15]

Prabhanjan Ananth, Zvika Brakerski, Gil Segev, and Vinod Vaikuntanathan.
From selective to adaptive security in functional encryption. In Rosario
Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part II, volume9216 of LNCS, pages 657–677, Santa Barbara, CA, USA, August 16–20, 2015.
Springer, Heidelberg, Germany.

[ACLL15]

Martin R. Albrecht, Catalin Cocis, Fabien Laguillaumie, and Adeline Langlois.
Implementing candidate graded encoding schemes from ideal lattices. In Tetsu
Iwata and Jung Hee Cheon, editors, ASIACRYPT 2015, Part II, volume 9453 of
LNCS, pages 752–775, Auckland, New Zealand, November 30 – December 3,
2015. Springer, Heidelberg, Germany.

[ADGM16] Daniel Apon, Nico Döttling, Sanjam Garg, and Pratyay Mukherjee. Cryptanalysis of indistinguishability obfuscations of circuits over GGH13. Cryptology
ePrint Archive, Report 2016/1003, 2016. http://eprint.iacr.org/2016/
1003.
45

46

BIBLIOGRAPHY[AFH+ 16]

Martin R. Albrecht, Pooya Farshim, Dennis Hofheinz, Enrique Larraia, andKenneth G. Paterson. Multilinear maps from obfuscation. In Eyal Kushilevitz
and Tal Malkin, editors, TCC 2016-A, Part I, volume 9562 of LNCS, pages 446–
473, Tel Aviv, Israel, January 10–13, 2016. Springer, Heidelberg, Germany.

[AGIS14]Prabhanjan Vijendra Ananth, Divya Gupta, Yuval Ishai, and Amit Sahai.
Optimizing obfuscation: Avoiding Barrington’s theorem. In Gail-Joon Ahn,
Moti Yung, and Ninghui Li, editors, ACM CCS 14, pages 646–658, Scottsdale,
AZ, USA, November 3–7, 2014. ACM Press.

[AJ15]

Prabhanjan Ananth and Abhishek Jain. Indistinguishability obfuscation fromcompact functional encryption. In Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part I, volume 9215 of LNCS, pages 308–326,
Santa Barbara, CA, USA, August 16–20, 2015. Springer, Heidelberg, Germany.

[AJN+ 16]

Prabhanjan Ananth, Aayush Jain, Moni Naor, Amit Sahai, and Eylon Yogev.
Universal constructions and robust combiners for indistinguishability obfuscation and witness encryption. In Matthew Robshaw and Jonathan Katz, editors,
CRYPTO 2016, Part II, volume 9815 of LNCS, pages 491–520, Santa Barbara,
CA, USA, August 14–18, 2016. Springer, Heidelberg, Germany.

[Alb16]

Martin Albrecht. Are graded encoding schemes broken yet? Regularly updated
webpage, 2016. http://malb.io/are-graded-encoding-schemes-brokenyet.html.

[AS16]

Prabhanjan Ananth and Amit Sahai. Projective arithmetic functional encryption and indistinguishability obfuscation from degree-5 multilinear maps.
Cryptology ePrint Archive, Report 2016/1097, 2016. http://eprint.iacr.
org/2016/1097.

[BBS04]Dan Boneh, Xavier Boyen, and Hovav Shacham. Short group signatures. In
Matthew Franklin, editor, CRYPTO 2004, volume 3152 of LNCS, pages 41–55,
Santa Barbara, CA, USA, August 15–19, 2004. Springer, Heidelberg, Germany.

[BDOP04]

Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, and Giuseppe Persiano.
Public key encryption with keyword search. In Christian Cachin and Jan
Camenisch, editors, EUROCRYPT 2004, volume 3027 of LNCS, pages 506–522,
Interlaken, Switzerland, May 2–6, 2004. Springer, Heidelberg, Germany.

[BF03]Dan Boneh and Matthew K. Franklin. Identity based encryption from the Weilpairing. SIAM Journal on Computing, 32(3):586–615, 2003.

[BGI+ 01]

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai,
Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs.
In Joe Kilian, editor, CRYPTO 2001, volume 2139 of LNCS, pages 1–18, Santa
Barbara, CA, USA, August 19–23, 2001. Springer, Heidelberg, Germany.

BIBLIOGRAPHY

47[BGI+ 10]

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai,
Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs.
Journal of the ACM, 59(2):6:1–6:48, 2010.

[BGK+ 14]

Boaz Barak, Sanjam Garg, Yael Tauman Kalai, Omer Paneth, and Amit Sahai.
Protecting obfuscation against algebraic attacks. In Phong Q. Nguyen andElisabeth Oswald, editors, EUROCRYPT 2014, volume 8441 of LNCS, pages
221–238, Copenhagen, Denmark, May 11–15, 2014. Springer, Heidelberg,
Germany.

[BGN05]

Dan Boneh, Eu-Jin Goh, and Kobbi Nissim. Evaluating 2-DNF formulas on
ciphertexts. In Joe Kilian, editor, TCC 2005, volume 3378 of LNCS, pages
325–341, Cambridge, MA, USA, February 10–12, 2005. Springer, Heidelberg,
Germany.

[BJK15]Allison Bishop, Abhishek Jain, and Lucas Kowalczyk. Function-hiding inner product encryption. In Tetsu Iwata and Jung Hee Cheon, editors, ASIACRYPT 2015, Part I, volume 9452 of LNCS, pages 470–491, Auckland, New
Zealand, November 30 – December 3, 2015. Springer, Heidelberg, Germany.

[BLS04]Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the Weilpairing. Journal of Cryptology, 17(4):297–319, September 2004.

[BMSZ16]

Saikrishna Badrinarayanan, Eric Miles, Amit Sahai, and Mark Zhandry. Postzeroizing obfuscation: New mathematical tools, and the case of evasive circuits.
In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, PartII, volume 9666 of LNCS, pages 764–791, Vienna, Austria, May 8–12, 2016.
Springer, Heidelberg, Germany.

[Boy08]

Xavier Boyen. The uber-assumption family (invited talk). In Steven D. Galbraith and Kenneth G. Paterson, editors, PAIRING 2008, volume 5209 of
LNCS, pages 39–56, Egham, UK, September 1–3, 2008. Springer, Heidelberg,
Germany.

[BS03]Dan Boneh and Alice Silverberg. Applications of multilinear forms to cryptography. Contemporary Mathematics, 324:71–90, 2003.

[BSW11]Dan Boneh, Amit Sahai, and Brent Waters. Functional encryption: Definitions
and challenges. In Yuval Ishai, editor, TCC 2011, volume 6597 of LNCS, pages
253–273, Providence, RI, USA, March 28–30, 2011. Springer, Heidelberg,
Germany.

[BV15]

Nir Bitansky and Vinod Vaikuntanathan. Indistinguishability obfuscation fromfunctional encryption. In Venkatesan Guruswami, editor, 56th FOCS, pages
171–190, Berkeley, CA, USA, October 17–20, 2015. IEEE Computer Society
Press.

48

BIBLIOGRAPHY[BWZ14]Dan Boneh, David J. Wu, and Joe Zimmerman. Immunizing multilinear maps
against zeroizing attacks. Cryptology ePrint Archive, Report 2014/930, 2014.
http://eprint.iacr.org/2014/930.

[CCK+ 13]

Jung Hee Cheon, Jean-Sébastien Coron, Jinsu Kim, Moon Sung Lee, Tancrède
Lepoint, Mehdi Tibouchi, and Aaram Yun. Batch fully homomorphic encryption over the integers. In Thomas Johansson and Phong Q. Nguyen, editors,
EUROCRYPT 2013, volume 7881 of LNCS, pages 315–335, Athens, Greece,
May 26–30, 2013. Springer, Heidelberg, Germany.

[CFL+ 16]

Jung Hee Cheon, Pierre-Alain Fouque, Changmin Lee, Brice Minaud, andHansol Ryu. Cryptanalysis of the new CLT multilinear map over the integers.
In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, PartI, volume 9665 of LNCS, pages 509–536, Vienna, Austria, May 8–12, 2016.
Springer, Heidelberg, Germany.

[CGH+ 15]

Jean-Sébastien Coron, Craig Gentry, Shai Halevi, Tancrède Lepoint, Hemanta K. Maji, Eric Miles, Mariana Raykova, Amit Sahai, and Mehdi Tibouchi.
Zeroizing without low-level zeroes: New MMAP attacks and their limitations.
In Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part I,
volume 9215 of LNCS, pages 247–266, Santa Barbara, CA, USA, August 16–20,
2015. Springer, Heidelberg, Germany.

[CGH16]

Yilei Chen, Craig Gentry, and Shai Halevi. Cryptanalyses of candidate branching program obfuscators. Cryptology ePrint Archive, Report 2016/998, 2016.
http://eprint.iacr.org/2016/998.

[CHL+ 15]

Jung Hee Cheon, Kyoohyung Han, Changmin Lee, Hansol Ryu, and Damien
Stehlé. Cryptanalysis of the multilinear map over the integers. In Elisabeth
Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part I, volume 9056 of
LNCS, pages 3–12, Sofia, Bulgaria, April 26–30, 2015. Springer, Heidelberg,
Germany.

[CLLT16a] Jean-Sébastien Coron, Moon Sung Lee, Tancrède Lepoint, and Mehdi Tibouchi.
Cryptanalysis of GGH15 multilinear maps. In Matthew Robshaw and Jonathan
Katz, editors, CRYPTO 2016, Part II, volume 9815 of LNCS, pages 607–628,
Santa Barbara, CA, USA, August 14–18, 2016. Springer, Heidelberg, Germany.
[CLLT16b] Jean-Sébastien Coron, Moon Sung Lee, Tancrède Lepoint, and Mehdi Tibouchi.
Zeroizing attacks on indistinguishability obfuscation over CLT13. Cryptology
ePrint Archive, Report 2016/1011, 2016. http://eprint.iacr.org/2016/
1011.
[CLLT17]

Jean-Sébastien Coron, Moon Sung Lee, Tancrède Lepoint, and Mehdi Tibouchi.
Zeroizing attacks on indistinguishability obfuscation over CLT13. In PKC 2017,
LNCS. Springer, Heidelberg, Germany, 2017. To appear.

BIBLIOGRAPHY

49[CLT13a]Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi. Practicalmultilinear maps over the integers. In Ran Canetti and Juan A. Garay, editors,
CRYPTO 2013, Part I, volume 8042 of LNCS, pages 476–493, Santa Barbara,
CA, USA, August 18–22, 2013. Springer, Heidelberg, Germany.

[CLT13b]Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi. Practical multilinear maps over the integers. Cryptology ePrint Archive, Report 2013/183,
2013. http://eprint.iacr.org/2013/183.

[CLT14]Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi. Cryptanalysisof two candidate fixes of multilinear maps over the integers. Cryptology ePrint
Archive, Report 2014/975, 2014. http://eprint.iacr.org/2014/975.

[CLT15]Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi. New multilinear
maps over the integers. In Rosario Gennaro and Matthew J. B. Robshaw,
editors, CRYPTO 2015, Part I, volume 9215 of LNCS, pages 267–286, Santa
Barbara, CA, USA, August 16–20, 2015. Springer, Heidelberg, Germany.

[CS03]

Ronald Cramer and Victor Shoup. Design and analysis of practical public-key
encryption schemes secure against adaptive chosen ciphertext attack. SIAM
Journal on Computing, 33(1):167–226, 2003.

[DH76]

Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE
Transactions on Information Theory, 22(6):644–654, 1976.

[ElG85]

Taher ElGamal. A public key cryptosystem and a signature scheme based on
discrete logarithms. IEEE Transactions on Information Theory, 31:469–472, 1985.

[FRS16]

Rex Fernando, Peter M. R. Rasmussen, and Amit Sahai. Preventing CLT
zeroizing attacks on obfuscation. Cryptology ePrint Archive, Report 2016/1070,
2016. http://eprint.iacr.org/2016/1070.

[Gen09]Craig Gentry. Fully homomorphic encryption using ideal lattices. In Michael
Mitzenmacher, editor, 41st ACM STOC, pages 169–178, Bethesda, MD, USA,May 31 – June 2, 2009. ACM Press.

[GGH12]

Sanjam Garg, Craig Gentry, and Shai Halevi. Candidate multilinear maps
from ideal lattices. Cryptology ePrint Archive, Report 2012/610, 2012. http://eprint.iacr.org/2012/610.

[GGH13a]Sanjam Garg, Craig Gentry, and Shai Halevi. Candidate multilinear maps
from ideal lattices. In Thomas Johansson and Phong Q. Nguyen, editors,
EUROCRYPT 2013, volume 7881 of LNCS, pages 1–17, Athens, Greece, May 26–
30, 2013. Springer, Heidelberg, Germany.

[GGH+ 13b] Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai,
and Brent Waters. Candidate indistinguishability obfuscation and functional

50

BIBLIOGRAPHY
encryption for all circuits. In 54th FOCS, pages 40–49, Berkeley, CA, USA,
October 26–29, 2013. IEEE Computer Society Press.

[GGH+ 13c] Sanjam Garg, Craig Gentry, Shai Halevi, Amit Sahai, and Brent Waters.
Attribute-based encryption for circuits from multilinear maps. In Ran Canetti
and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, pages
479–499, Santa Barbara, CA, USA, August 18–22, 2013. Springer, Heidelberg,
Germany.
[GGH15]

Craig Gentry, Sergey Gorbunov, and Shai Halevi. Graph-induced multilinear
maps from lattices. In Yevgeniy Dodis and Jesper Buus Nielsen, editors,
TCC 2015, Part II, volume 9015 of LNCS, pages 498–527, Warsaw, Poland,
March 23–25, 2015. Springer, Heidelberg, Germany.

[GGHZ14]

Sanjam Garg, Craig Gentry, Shai Halevi, and Mark Zhandry. Fully secure
attribute based encryption from multilinear maps. Cryptology ePrint Archive,
Report 2014/622, 2014. http://eprint.iacr.org/2014/622.

[GGHZ16]

Sanjam Garg, Craig Gentry, Shai Halevi, and Mark Zhandry. Functional
encryption without obfuscation. In Eyal Kushilevitz and Tal Malkin, editors,
TCC 2016-A, Part II, volume 9563 of LNCS, pages 480–511, Tel Aviv, Israel,
January 10–13, 2016. Springer, Heidelberg, Germany.

[GGSW13] Sanjam Garg, Craig Gentry, Amit Sahai, and Brent Waters. Witness encryption
and its applications. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum,
editors, 45th ACM STOC, pages 467–476, Palo Alto, CA, USA, June 1–4, 2013.
ACM Press.
[GKP+ 13]

Shafi Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan,and Nickolai Zeldovich. Reusable garbled circuits and succinct functional
encryption. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors,
45th ACM STOC, pages 555–564, Palo Alto, CA, USA, June 1–4, 2013. ACM
Press.

[GLW14]

Craig Gentry, Allison B. Lewko, and Brent Waters. Witness encryption frominstance independent assumptions. In Juan A. Garay and Rosario Gennaro,
editors, CRYPTO 2014, Part I, volume 8616 of LNCS, pages 426–443, Santa
Barbara, CA, USA, August 17–21, 2014. Springer, Heidelberg, Germany.

[GMM+ 16] Sanjam Garg, Eric Miles, Pratyay Mukherjee, Amit Sahai, Akshayaram Srinivasan, and Mark Zhandry. Secure obfuscation in a weak multilinear map
model. In Martin Hirt and Adam D. Smith, editors, TCC 2016-B, Part II, volume
9986 of LNCS, pages 241–268, Beijing, China, October 31 – November 3, 2016.
Springer, Heidelberg, Germany.

BIBLIOGRAPHY

51[GMS16]

Sanjam Garg, Pratyay Mukherjee, and Akshayaram Srinivasan. Obfuscation
without the vulnerabilities of multilinear maps. Cryptology ePrint Archive,
Report 2016/390, 2016. http://eprint.iacr.org/2016/390.

[GPS08]

Steven D. Galbraith, Kenneth G. Paterson, and Nigel P. Smart. Pairings forcryptographers. Discrete Applied Mathematics, 156(16):3113–3121, 2008.

[GPSW06a] Vipul Goyal, Omkant Pandey, Amit Sahai, and Brent Waters. Attribute-based
encryption for fine-grained access control of encrypted data. In Ari Juels,
Rebecca N. Wright, and Sabrina De Capitani di Vimercati, editors, ACM CCS
06, pages 89–98, Alexandria, Virginia, USA, October 30 – November 3, 2006.
ACM Press. Available as Cryptology ePrint Archive Report 2006/309.
[GPSW06b] Vipul Goyal, Omkant Pandey, Amit Sahai, and Brent Waters. Attribute-based
encryption for fine-grained access control of encrypted data. Cryptology ePrint
Archive, Report 2006/309, 2006. http://eprint.iacr.org/2006/309.
[GPV08]Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hardlattices and new cryptographic constructions. In Richard E. Ladner andCynthia Dwork, editors, 40th ACM STOC, pages 197–206, Victoria, British
Columbia, Canada, May 17–20, 2008. ACM Press.

[GR07]

Shafi Goldwasser and Guy N. Rothblum. On best-possible obfuscation. In
Salil P. Vadhan, editor, TCC 2007, volume 4392 of LNCS, pages 194–213,
Amsterdam, The Netherlands, February 21–24, 2007. Springer, Heidelberg,
Germany.

[GS08]

Jens Groth and Amit Sahai. Efficient non-interactive proof systems for bilinear
groups. In Nigel P. Smart, editor, EUROCRYPT 2008, volume 4965 of LNCS,
pages 415–432, Istanbul, Turkey, April 13–17, 2008. Springer, Heidelberg,
Germany.

[GSW13]

Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic encryption fromlearning with errors: Conceptually-simpler, asymptotically-faster, attributebased. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part I,
volume 8042 of LNCS, pages 75–92, Santa Barbara, CA, USA, August 18–22,
2013. Springer, Heidelberg, Germany.

[GVW13]Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. Attribute-based
encryption for circuits. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, 45th ACM STOC, pages 545–554, Palo Alto, CA, USA, June 1–4,
2013. ACM Press.

[GVW15]Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. Predicate encryption for circuits from LWE. In Rosario Gennaro and Matthew J. B. Robshaw,
editors, CRYPTO 2015, Part II, volume 9216 of LNCS, pages 503–523, Santa
Barbara, CA, USA, August 16–20, 2015. Springer, Heidelberg, Germany.

52

BIBLIOGRAPHY[Ham11]

Mike Hamburg. Spatial encryption. Cryptology ePrint Archive, Report
2011/389, 2011. http://eprint.iacr.org/2011/389.

[HJ16]

Yupu Hu and Huiwen Jia. Cryptanalysis of GGH map. In Marc Fischlin
and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part I, volume 9665 of
LNCS, pages 537–565, Vienna, Austria, May 8–12, 2016. Springer, Heidelberg,
Germany.

[Jou04]

Antoine Joux. A one round protocol for tripartite Diffie-Hellman. Journal of
Cryptology, 17(4):263–276, September 2004.

[KM10]

Neal Koblitz and Alfred Menezes. The brave new world of bodacious assumptions in cryptography. Notices of the American Mathematical Society, 57:357–365,
2010.

[KSW08]Jonathan Katz, Amit Sahai, and Brent Waters. Predicate encryption supporting
disjunctions, polynomial equations, and inner products. In Nigel P. Smart,
editor, EUROCRYPT 2008, volume 4965 of LNCS, pages 146–162, Istanbul,
Turkey, April 13–17, 2008. Springer, Heidelberg, Germany.

[Lin16]

Huijia Lin. Indistinguishability obfuscation from DDH on 5-linear maps
and locality-5 PRGs. Cryptology ePrint Archive, Report 2016/1096, 2016.
http://eprint.iacr.org/2016/1096.

[LSS14]

Adeline Langlois, Damien Stehlé, and Ron Steinfeld. GGHLite: More efficient
multilinear maps from ideal lattices. In Phong Q. Nguyen and Elisabeth
Oswald, editors, EUROCRYPT 2014, volume 8441 of LNCS, pages 239–256,
Copenhagen, Denmark, May 11–15, 2014. Springer, Heidelberg, Germany.

[LV16]

Huijia Lin and Vinod Vaikuntanathan. Indistinguishability obfuscation from
DDH-like assumptions on constant-degree graded encodings. In Irit Dinur,
editor, 57th FOCS, pages 11–20, New Brunswick, NJ, USA, October 9–11, 2016.
IEEE Computer Society Press.

[MP12]

Daniele Micciancio and Chris Peikert. Trapdoors for lattices: Simpler, tighter,faster, smaller. In David Pointcheval and Thomas Johansson, editors, EUROCRYPT 2012, volume 7237 of LNCS, pages 700–718, Cambridge, UK, April 15–
19, 2012. Springer, Heidelberg, Germany.

[MSW14]Eric Miles, Amit Sahai, and Mor Weiss. Protecting obfuscation against
arithmetic attacks. Cryptology ePrint Archive, Report 2014/878, 2014.
http://eprint.iacr.org/2014/878.

[MSZ16a]Eric Miles, Amit Sahai, and Mark Zhandry. Annihilation attacks for multilinear
maps: Cryptanalysis of indistinguishability obfuscation over GGH13. In
Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part II, volume9815 of LNCS, pages 629–658, Santa Barbara, CA, USA, August 14–18, 2016.
Springer, Heidelberg, Germany.

BIBLIOGRAPHY

53[MSZ16b]

Eric Miles, Amit Sahai, and Mark Zhandry. Secure obfuscation in a weakmultilinear map model: A simple construction secure against all known attacks.
Cryptology ePrint Archive, Report 2016/588, 2016. http://eprint.iacr.
org/2016/588.

[MVO93]

Alfred Menezes, Scott A. Vanstone, and Tatsuaki Okamoto. Reducing elliptic
curve logarithms to logarithms in a finite field. IEEE Transactions on Information
Theory, 39:1639–1646, 1993.

[NR04]

Moni Naor and Omer Reingold. Number-theoretic constructions of efficientpseudo-random functions. Journal of the ACM, 51(2):231–262, 2004.

[OT09]

Tatsuaki Okamoto and Katsuyuki Takashima. Hierarchical predicate encryption for inner-products. In Mitsuru Matsui, editor, ASIACRYPT 2009, volume
5912 of LNCS, pages 214–231, Tokyo, Japan, December 6–10, 2009. Springer,
Heidelberg, Germany.

[Pai99]

Pascal Paillier. Public-key cryptosystems based on composite degree residuosity
classes. In Jacques Stern, editor, EUROCRYPT’99, volume 1592 of LNCS,
pages 223–238, Prague, Czech Republic, May 2–6, 1999. Springer, Heidelberg,
Germany.

[PRV12]Periklis A. Papakonstantinou, Charles W. Rackoff, and Yevgeniy Vahlis. How
powerful are the DDH hard groups? Cryptology ePrint Archive, Report
2012/653, 2012. http://eprint.iacr.org/2012/653.

[PST14]

Rafael Pass, Karn Seth, and Sidharth Telang. Indistinguishability obfuscationfrom semantically-secure multilinear encodings. In Juan A. Garay and Rosario
Gennaro, editors, CRYPTO 2014, Part I, volume 8616 of LNCS, pages 500–517,
Santa Barbara, CA, USA, August 17–21, 2014. Springer, Heidelberg, Germany.

[RAD78]

Ron L. Rivest, Leonard M. Adleman, and Michael L. Dertouzos. On databanks and privacy homomorphisms. In Richard A. DeMillo, editor, Foundationsof Secure Computation, pages 169–180. Academic Press, 1978.

[RH09]

Wayne Raskind and Ming-Deh Huang. A multilinear generalization of theTate pairing. Talk at the Fq9 conference, University College Dublin, July 2009.
https://maths.ucd.ie/~gmg/Fq9Talks/Raskind.pdf.

[Rot13]

Ron Rothblum. On the circular security of bit-encryption. In Amit Sahai, editor,
TCC 2013, volume 7785 of LNCS, pages 579–598, Tokyo, Japan, March 3–6,
2013. Springer, Heidelberg, Germany.

[Sch91]

Claus-Peter Schnorr. Efficient signature generation by smart cards. Journal of
Cryptology, 4(3):161–174, 1991.

54

BIBLIOGRAPHY[SW05]

Amit Sahai and Brent R. Waters. Fuzzy identity-based encryption. In Ronald
Cramer, editor, EUROCRYPT 2005, volume 3494 of LNCS, pages 457–473,
Aarhus, Denmark, May 22–26, 2005. Springer, Heidelberg, Germany.

[SW14]

Amit Sahai and Brent Waters. How to use indistinguishability obfuscation:
deniable encryption, and more. In David B. Shmoys, editor, 46th ACM STOC,
pages 475–484, New York, NY, USA, May 31 – June 3, 2014. ACM Press.

[vDGHV10] Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. Fully
homomorphic encryption over the integers. In Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, pages 24–43, French Riviera, May 30 –June 3, 2010. Springer, Heidelberg, Germany.
[Wat15]

Brent Waters. A punctured programming approach to adaptively securefunctional encryption. In Rosario Gennaro and Matthew J. B. Robshaw,
editors, CRYPTO 2015, Part II, volume 9216 of LNCS, pages 678–697, Santa
Barbara, CA, USA, August 16–20, 2015. Springer, Heidelberg, Germany.

[Zim15]

Joe Zimmerman. How to obfuscate programs directly. In Elisabeth Oswald andMarc Fischlin, editors, EUROCRYPT 2015, Part II, volume 9057 of LNCS, pages
439–467, Sofia, Bulgaria, April 26–30, 2015. Springer, Heidelberg, Germany.