Léo Ducas

Alice Pellet--Mary

On the Statistical Leak of the GGH13 Multilinear Map and some Variants

Keywords: Cryptanalysis, Multilinear Maps, Statistical Leaks, Ideal Lattices

At EUROCRYPT 2013, Garg, Gentry and Halevi proposed a candidate construction (later referred as GGH13) of cryptographic multilinear map (MMap). Despite weaknesses uncovered by Hu and Jia (EUROCRYPT 2016), this candidate is still used for designing obfuscators. The naive version of the GGH13 scheme was deemed susceptible to averaging attacks, i.e., it could suer from a statistical leak (yet no precise attack was described). A variant was therefore devised, but it remains heuristic. Recently, to obtain MMaps with low noise and modulus, two variants of this countermeasure were developed by Döttling et al. (EPRINT:2016/599). In this work, we propose a systematic study of this statistical leak for all these GGH13 variants. In particular, we conrm the weakness of the naive version of GGH13. We also show that, among the two variants proposed by Döttling et al., the so-called conservative method is not so eective: it leaks the same value as the unprotected method. Luckily, the leak is more noisy than in the unprotected method, making the straightforward attack unsuccessful. Additionally, we note that all the other methods also leak values correlated with secrets. As a conclusion, we propose yet another countermeasure, for which this leak is made unrelated to all secrets. On our way, we also make explicit and tighten the hidden exponents in the size of the parameters, as an eort to assess and improve the eciency of MMaps.

Introduction

Since their introduction in cryptographic constructions by [Jou00], cryptographic bilinear maps, as provided by pairings on elliptic curves, have enabled the construction of more and more advanced cryptographic protocols, starting with the seminal Identity-Based Encryption scheme of Boneh and Franklin [BF01]. More abstractly, a group equipped with an ecient bilinear map, and on which some discrete-logarithm like problems are hard (such as the bilinear-Die-Hellmann problem), provides foundation for a whole branch of cryptography. A natural open question is whether it can be generalized to degrees higher than 2 while ensuring hardness of generalizations of the Die-Hellmann problem. Such hypothetical objects are referred to as Cryptographic Multilinear Maps (or, for short, MMaps).

In 2013, Garg, Gentry and Halevi [GGH13] proposed a candidate construction for MMaps related to ideal-lattices, yet without a clearly identied underlying hard lattice problem. It diers from the pairing case in the sense that elements in the low-level groups have no canonical representation, and should exactly be. The next best guarantee is a precise understanding of what can be done from a cryptanalytic point of view, as initiated in [GGH13].

The analysis of the leak of [GGH13] focuses on the covariance of products of encodings of zero.

One can (informally) argue that this analysis captures all the information of the leak. Indeed, up to discretization, such a product is the product of several centered Gaussian distributions (non necessary spherical), and such a distribution is fully identied by its covariance. The countermeasure proposed in Section 6.4 of [GGH13] attempts to make this covariance proportional to the identity matrix (and therefore unrelated to all secrets) by sampling each element of the product according to a spherical distribution, that is a distribution whose covariance is proportional to the identity matrix. As we shall see, this attempt is unsuccessful, as one of the factor of the product (namely, the one related to the zero-testing parameter) is xed. Obtaining several independent multiples of it, with covariance proportional to the identity matrix, then reveals an approximation of this factor. Contributions. Our main contribution is to give a systematic study of the statistical leak in the GGH13 scheme and its variants, in a simple framework we dene. We rst suggest a common formalism that encompasses all the variants at hand, by parametrising the sampling procedure for encodings by an arbitrary covariance matrix. Following the nomenclature of [GGH13, DGG

+ 16],

except for the second one that had no clear name, we consider:

1. The simplistic method: the GGH MMap without countermeasure [GGH13, Sec. 4.1]. This method was only given for simplicity of exposition and was already highly suspected to be insecure;

2. The exponential method:

5 the GGH MMap with countermeasure [GGH13, Sec. 6.4];

3. The conservative method, proposed in [DGG + 16] which we partly revisit to tackle some of its limitations;

4. The aggressive method, proposed in [DGG + 16] we note that this method is specic to the iO construction of [DGG + 16], and is not applicable to all constructions over the GGH MMap.

In order to formalize our study of the leak, we propose a simple setting of the GGH multilinear map. Indeed, due to the attacks in presence of encodings of zero, the exact set-up for the analysis of the leak in [GGH13] is not relevant anymore. We adjust their setting to not provide low-level encodings of zero directly. Still, some relations between encodings are needed for the MMaps to be non-trivial; to ensure that those relations do not allow zeroizing attacks, we provide a security proof in the weak multilinear map model of [MSZ16, GMM + 16, DGG + 16]. For ease of exposure, we restrict ourselves to degree κ = 2, yet our analysis easily extends to higher degrees.

Using this framework, we are able to analyse a particular averaging attack against the GGH multilinear map. On the one hand, our analysis shows that Method 3 leads to the same leak as Method 1. We also prove that with Method 1, a polynomial-time attack can be mounted using the leak. Interestingly, it does not require the Gentry-Szydlo algorithm [GS02], unlike the approach discussed in [GGH13, Sec. 6.3.2 and Sec. 7.6]. Nevertheless, we did not manage to extend the attack to Method 3: while the same quantity is statistically leaked, the number of samples remains too low for the attack to go through completely. On the other hand, we show that the statistical leak of Method 4 is similar to the one of Method 2: perhaps surprisingly the aggressive method seems more secure than the conservative one. 5 The naming reects the fact that this method leads to a modulus q which is exponential in the number of so-called atoms.

Finally, having built a better understanding of which information is leaked, we devise a countermeasure that we deem more adequate than all the above: 5. The compensation method.

This method is arguably simpler, and provides better parameters. More importantly, applying the same leakage attack than above, one only obtains a distribution whose covariance is independent of all secrets. We wish to clarify that this is in no way a formal statement of zero-knowledgedness.

The statistical attacks considered in this work are set up in a minimalistic setting, and extensions could exist beyond this minimalistic setting. For example, one could explore what can be done by varying the zero-tested polynomial, or by keeping certain encodings xed between several successful zero-tests.

As a secondary contribution, we also make explicit and tighten many hidden constants present in the previous constructions, in an eort to evaluate and improve the eciency of GGH13-like MMaps.

Impact. This result may be useful in pursuit of an underlying hard problem on which one could based the GGH multilinear map. Indeed, we show here that it is possible to recover some information about secret elements, for all the previously proposed sampling methods. Hence, an underlying hard problem (or the security reduction) should capture this leak. This enables us to get a bit more insight into what could be (or could not be) an underlying hard problem for the GGH map. In that regard, nding such a hard underlying problem could be easier with our new method, since one specic leak has been sealed. Again, we do not claim that no other leaks exist.

Further, our analysis shows that the weak multilinear map model does not capture averaging attacks. This is not surprising, as the weak multilinear map model only allows to evaluate polynomials in the post-zero-test values, while we need to average on them for this attack. But proving that averaging cannot be achieved by evaluating polynomials is not so immediate. Interestingly, our results prove it. Indeed, using averaging techniques, we were able to mount a polynomial time attack against our setting when using the simplistic sampling method (Method 1), but we also proved that in the weak multilinear map model, no polynomial time attacks could be mounted.

This proves that the weak multilinear map model does not capture averaging attacks.

6

Finally, our new method severely decreases the length of encodings in the GGH13 multilinear map, which substentially contribute to their practical feasibility.

Outline of the article. In Section 2, we recall some mathematical background about cyclotomic number elds and statistics. We also describe the GGH multilinear map and precise the size of its parameters. In Section 3, we describe dierent sampling methods for the GGH multilinear map, which come from [GGH13] and [DGG + 16], using a common formalism so as to factor the later analysis. We describe our simple setting and analyse the leak in Section 4. The security proof of this simple setting in the weak multilinear map model is postponed in Appendix B. Finally, we discuss the design of sampling methods in Section 5, and propose a design we deem more rational.

Preliminaries

Mathematical Background

Rings. We denote by R the ring of integers Z[X]/(X n + 1) for some n which is a power of 2 and K = Q[X]/(X n + 1) its fraction eld. We denote by σ j : K → C, with 1 ≤ j ≤ n, the complex embeddings of K in C. We also denote K R = R[X]/(X n + 1) the topological closure of K. For x ∈ K R , we denote x i ∈ R its i-th coecient, so that x = n-1 i=0 x i X i . For g ∈ K (or even K R ) we denote gR the ideal generated by g: gR = {gx|x ∈ R}. The complex conjugation over R and K is denoted •. It is the automorphism of R sending X to X -1 . We denote S the subring of K R of symmetric elements, that is S = {x ∈ K R |x = x}. We set S + the subset of symmetric positive elements of S, dened by S + = {xx|x ∈ K R }. Alternatively, S is the completion of the real subeld of K, and S + is (the completion of ) the set of elements of K whose embeddings are all non-negative reals. Note that S + is closed under addition, multiplication, division, but not under subtraction. The elements of S + also admit one and exactly one square root (resp. k-th root) in S + , which we denote √

• (resp. k √ •) . Finally, we call xx ∈ S + the autocorrelation7 of x ∈ K R , and note it A(x). For Σ ∈ S + it holds that A( √ Σ) = Σ. We also dene equivalence over S + up to scaling by reals, and write x ∼ y for invertible elements x, y ∈ S + if x = αy for some positive real α > 0. Let q be a prime congruent to 1 modulo 2n. We denote by R q the quotient ring R/(qR). For x ∈ R, we denote by [x] q (or [x] when there is no ambiguity) the coset of the element x in R q . We will often lift back elements from R q to R, in which case we may implicitly mean that we choose the representative with coecients in the range [-q/2, q/2]. To avoid confusion, we will always note x -1 for the inversion in R q , and keep the fraction symbols 1/x and 1

x for inversion in K and K R .

Geometry. Because we work in the ring Z[X]/(X n + 1), the canonical geometry of the coecients embeddings is equivalent, up to scaling, to the geometry of the Minkowski embeddings. We stick with the former, following the literature on multilinear maps. More precisely, the inner product of two elements x, y ∈ K is dened by x, y = x i y i . The Euclidean norm (or 2 -norm) is dened by

x = x, x . The ∞ -norm is noted x ∞ = max |x i |.
We recall the following inequalities:

xy ≤ √ n • x • y (1) x ∞ ≤ x ≤ √ n • x ∞ (2) x 2 ≤ xx ∞ (3) x = x and x ∞ = x ∞ . (4)
Statistics. We denote by Pr[E] the probability of an event E. For a random variable x over K R , we denote by E[x] the expectation of x, and by V

[x] = E[xx] -E[x]E[x] its variance. It should be noted that V[x] ∈ S + for any random variable x over K R . A random variable x is said centered if E[x] = 0, and isotropic if V[x] ∼ 1.
We recall Hoeding's inequality.

Theorem 1 (Hoeding's inequality

). Let Y 1 , • • • , Y m be independent random variables in R
with the same mean µ ∈ R and such that |Y i | ≤ B for all i's. Then for all t > 0,

Pr 1 m m i=0 Y i -µ ≥ t < e -2mt 2 B 2 .
Hoeding's inequality, as given above, applies to random variables in R. In this article, we will be interested in random variables in R. We will then see our elements in R as vectors in R n and apply Hoeding's inequality coecient-wise.

Corollary 1 (Hoeding's inequality in R).

Let Y 1 , • • • , Y m be independent random variables in R with the same mean µ ∈ K R and such that Y i ∞ ≤ B for all i's. Let ε > 0, then Pr 1 m m i=0 Y i -µ ∞ ≥ B ln n -ln ε 2m < ε. Proof. For 1 ≤ i ≤ m and 0 ≤ j ≤ n -1, dene Y i,j
to be the j-th coecient of the variable Y i ∈ R and µ j to be the j-th coecient of µ. For a xed j, the variables Y i,j (where only i varies) are independent random variables in R of mean µ j . Moreover, as Y i ∞ ≤ B for all i's, the coecients Y i,j are also bounded by B. We can then apply Hoeding's inequality (Theorem 1) to them. We obtain Pr

1 m m i=0 Y i -µ ∞ ≥ B ln n -ln ε 2m = Pr ∃j : 1 m m i=0 Y i,j -µ j ∞ ≥ B ln n -ln ε 2m ≤ n-1 j=0 Pr 1 m m i=0 Y i,j -µ j ∞ ≥ B ln n -ln ε 2m < n-1 j=0 e -2mB 2 (ln n-ln ε) 2B 2 m = n-1 j=0 ε n = ε.
We used the union bound and Hoeding's inequality with t = B ln n-ln ε 2m .

Discrete Gaussians. For Σ ∈ S + and x 0 ∈ K R , we dene the Gaussian weight function on K R as

ρ √ Σ,x0 : x → exp - 1 2 x -x 0 √ Σ 2 .
For any shifted ideal I + c, I ⊂ K, c ∈ K R , we dene the discrete Gaussian distribution over I + c of parameter √ Σ, centered in x 0 by:

∀x ∈ I + c, D I+c, √ Σ,x0 (x) = ρ √ Σ,x0 (x) ρ √ Σ,x0 (I + c)
.

For concision, we write D I+c,

√ Σ instead of D I+c, √ Σ,0 and ρ √ Σ instead of ρ √ Σ,0 .
Theorem 2 (Reformulation of [GPV08, Thm 4.1.]). There exists a PPT algorithm that given

g ∈ R and a parameter Σ such that g/ √ Σ ≤ o(1/ √ log n), outputs x from a distribution negligibly close to D gR+c, √ Σ .
This reformulation simply relies on the identity D gR+c,

√ Σ = √ Σ σ •D (gR+c)/ √ Σ,σ .
We also recall that, above the smoothing parameter [MR04], a discrete Gaussian resembles the continuous Gaussian, in particular it is almost centered at 0, and of variance almost Σ.

Lemma 1. For any g ∈

K, Σ ∈ S + , c ∈ K R such that g/ √ Σ ≤ o(1/ √ log n), if x ← D gR+c, √ Σ , then E[x] ≤ ε • √ Σ and V[x] -Σ ≤ ε • Σ for some negligible function ε(n).
The proof of this result, using [MR04, Lemma 4.2], can be found in Appendix A.

The GGH13 multilinear map

We describe in this section the GGH13 multilinear map [GGH13], in its asymmetric setting. The GGH13 multilinear map encodes elements of a ring of integers R, modulo a secret small element g ∈ R. More concretely, an authority generates the following parameters:

• an integer n which is a power of 2 (serving as the security parameter).

• a (small) element g in R. We note I = gR the ideal generated by g in R.

• a (large) positive integer q such that q ≡ 1 mod 2n. Originally, q was chosen exponentially large in n [GGH13], but variants were proposed for polynomially sized q [LSS14, DGG + 16].

• invertible elements [z i ] ∈ R × q , for 1 ≤ i ≤ , chosen uniformly at random in R × q .
• a zero-testing parameter

[p zt ] = [hz * g -1 ] where [z * ] = [ 1≤i≤ z i ]
and h is a random element in R, generated according to a Gaussian distribution of standard deviation approximately √ q.

We detail in Section 2.2 the size of the parameters described above (we will chose them to ensure the correctness of the scheme). The elements n, q and p zt are public while the parameters h, g and the z i 's are kept secret.

Encoding of an element. The GGH13 multilinear map allows to encode cosets of the form a + I for some element a in R. Let v ∈ {0, 1} be a vector of size . An encoding of the coset a + I at level v is an element of R q of the form

u = (a + rg) • z -1 v where [z v ] = [ i,v[i]=1
z i ] and a + rg is a small element in the coset a + I. We call v the level of the encoding. We abuse notation by saying that u is an encoding of a (instead of an encoding of the coset a + I).

An encoding generated by the authority is called a fresh encoding, by opposition to encodings that are obtained by adding or multiplying other encodings. The precise distribution of a + rg for a fresh encoding will be a discrete Gaussian distribution over the coset a + I, but not necessarily a spherical one: a + rg ← D a+I,

√

Σv . The shape Σ v of this Gaussian is essentially what distinguishes the variants that we will discuss in Section 3.

Adding and multiplying encodings. If u 1 and u 2 are two encodings of elements a 1 and a 2 at the same level v then u 1 + u 2 is an encoding of a 1 + a 2 at level v.

If u 1 and u 2 are two encodings of elements a 1 and a 2 at levels v and w with v[i] • w[i] = 0 for all 1 ≤ i ≤ , then u 1 • u 2 is an encoding of a 1 • a 2 at level v + w (where the addition is the usual addition on vectors of size ).

Zero-testing. We denote by v * = (1, . . . , 1) the maximum level of an encoding. The zero testing parameter allows us to test if an encoding u at level v * is an encoding of zero, by computing

[w] = [u • p zt ].
If w is small compared to q (the literature usually requires its coecients to be less than q 3/4 ), then u is an encoding of zero. Otherwise, it is not.

Size of the parameters and correctness. We dene Q such that q = n Q and L such that = n L (the elements Q and L are not necessarily integers). The bounds below on the size of g and h come from [GGH13]. The secret generator g is sampled so that:

g = O(n), 1/g = O(n 2 ).
(5)

Remark. There seems to be some inconsistencies in [GGH13] about the size of g, which is on page 10 sampled with width σ = Õ( √ n), while on page 13 the width σ is set to √ nλ to ensure the smoothing condition σ ≥ η 2 -λ (Z n ) (where λ = O(n) denote the security parameter). Yet, according to [MR04, Lemma 3 The numerator c = a + rg of a fresh encoding of a + I at level v is sampled such that

.3], it holds that η 2 -λ (Z n ) ≤ O( √ λ + log n), so σ = O( √ n) is sucient,
c = Θ(n γ+η• v 1+νL ), (6)
where γ, η and ν are positive reals, and depend on the sampling method, such as the ones proposed in [DGG + 16] (depending on the method, η and ν may be zero). We describe later the dierent sampling methods and the values of γ, η and ν associated to each method. When we do not need to focus on the dependence on v 1 and L, we just call E := Θ(n γ+η• v 1 +νL ) the bound above.

For each sampling method described below, we choose this bound to be as small as possible under the specic constraints that will arise with the sampling method.

The mildly large element h is sampled so that h = Θ( √ nq).

(7)

Remark. In the second variant proposed in [GGH13, Section 6.4] to try to prevent averaging attacks, the authors generate h according to a non spherical Gaussian distribution. However, as h is sampled only once, its distribution does not matter for the attack we analyze in this article. This is why we only specify here the size of h, and not its distribution.

In the following, we will be interested in the case where we are provided with fresh encodings at a somewhat high level, and we can create encodings at maximum level v * by multiplying just a small number of fresh encodings (namely κ). This is what motivates the condition given here to ensure correctness of the zero-testing procedure. Correctness of zero-testing a homogeneous polynomial of degree κ, whose absolute sum of the coecients is bounded by n B and evaluated in fresh encodings,

is guaranteed if n B • h g κ i=1 c i ≤ q 3/4 . It is then sucient to have B + κ + 1 2 + Q + 1 2 + 2 + κ(γ + νL) + η ≤ 3 4 Q. ( 8
)
The term κ+1 2 appears from applying inequality (1) κ + 1 times. One should also note that κ i=1 v i 1 = v * 1 = , because we can only zero test at level v * (where v i is the level of encoding c i ). More compactly, correctness holds if:

B + 3 + κ(1/2 + γ + νL) + η ≤ Q/4. (9)
In our simple setting of the GGH multilinear map dened in Section 4.1, we will only query the zero-testing procedure on encodings of this form, with κ = 2 and B = log(m)/ log(n), for some constant m we will dene later. Hence, taking 4 + 2γ + 2νL + η + log(m)/ log(n) ≤ Q/4 will be sucient in our setting to ensure correctness of the zero-testing procedure.

Remark. We note that the bound q 3/4 for positive zero-tests is somewhat arbitrary and could very well be replaced by q/4, allowing to square-root the parameter q. Indeed, the probability of a false positive during zero-testing would remain as small as 2 -n . This would have a serious impact on concrete eciency and security.

Sampling methods

We describe in this section dierent sampling methods that can be used to generate the fresh encodings of the GGH multilinear map and we give the values of γ, η and ν that correspond to these methods. As said above, we will be interested in cases where (at least some of ) the fresh encodings have a somewhat high degree and we just have to multiply a constant number of them (say 2) to obtain an encoding at maximal level v * . We denote by A the set of atoms, that is the set of levels v ∈ {0, 1} at which we want to encode fresh encodings. In our simple setting of the GGH multilinear map (see Section 4.1 for a full description of our setting), we will chose A to be the set of levels v ∈ {0, 1} that have weight exactly 1 or -1, where the weight of v is the number of its non-zero coecients. For all v ∈ A, we denote by ṽ = v * -v the complement of v. We note that A is closed by complement.

In all the following sampling methods except the rst one, one chooses a representative z v ∈ R of [z v ] ∈ R q for all v ∈ A. This representative will not necessarily be the canonical one, with coecients in [-q/2, q/2]. Then, we will take

Σ v = σ 2 v z v zv , with σ v = Θ(n 2 1/z v ).
Using Inequalities (3) and (4), we can see that 1/

√ Σ v ≤ 1/σ v • n 1/4 • 1/z v .
Hence, with our choice of σ v and the fact that g

= O(n), we obtain g √ Σ v ≤ √ n • g • 1 √ Σ v = O 1 n 1/4 = o 1 √ log n .
We can therefore apply Theorem 2 to sample the numerators of fresh encodings at level v, according to a Gaussian distribution of parameter Σ v . Using tail-cut of Gaussian distributions, we have that if c is the numerator of a fresh encoding, then c ≤ n

√ Σ v ≤ n 1.5 σ v z v with
overwhelming probability. This means that we can take

E ≤ Θ(n 3.5 • 1/z v • z v ). (10)
Hence, in the following methods (except the simplistic one), we will focus on the size of 1/z v • z v to get a bound on the value of E.

Remark. Inequality (10) above is not tight. We could at least improve it to E ≤ Θ(n 3+ε • 1/z v • z v ) for any ε > 0, with the same reasoning. This ensures statistical closeness to the desired distribution up to exp(-n 2ε ). Considering that there are already classical attacks in time exp( Õ( + 17] to recover h from the ideal hR), one may just choose ε = 1/4.

√ n)) (namely, using [CDPR16, BEF

The simplistic method

The simplistic method consists in always choosing Σ v ∼ 1, independently of v and z v . This is done by applying Klein's algorithm [Kle00], and requires for correctness [GPV08, Thm 4

.1] that Σ v = σ 2 for a positive scalar σ ∈ R, where σ ≥ g • ω( √ log n). So by taking σ = Θ(n 1+ε ) with ε > 0, one may have E = Θ( √ nσ) = Θ(n 1.5+ε ), that is γ = 1.5 + ε and η = ν = 0.
This method was deemed subject to averaging attacks and hence less secure than the following one in [GGH13], but the authors claim that their attack attempts failed because all recovered elements were larger that √ q, and that averaging attacks would need super-polynomially many elements. 8 We explicit an attack, and will show that this attack is possible even for exponential q, as long as E κ remains polynomial: in other words, the presence of the mildly large factor h (of size √ q) can be circumvented.

The exponential method

We present here the countermeasure of [GGH13, Sec. 6.4], generalized to multi-dimensional universe,

as done in [DGG + 16, Sec. 2.1]. For 1 ≤ i ≤ , set z i to be the canonical representative of [z i ] in R
(with coecients in the range [-q/2, q/2]). Using rejection sampling when choosing z i , assume that z i • 1/z i ≤ Z; this is ecient for Z as small as n 5/2 using [DGG + 16], and can even be improved to Z = n 3/2 using Lemma 3 below and its corollary.

For

v in A, set z v = z vi i over R. Recall that Inequality (10) gives us: E ≤ Θ(n 3.5 1/z v • z v ). But we have z v ≤ n ( v 1-1)/2 i∈v z i and 1/z v ≤ n ( v 1 -1)/2 i∈v 1/z i . Hence we can take E = Θ(n 2.5+ v 1 • Z v 1 ) = Θ(n 2.5+2.5 v 1 ).
This means that we have γ = 2.5, η = 2.5 and ν = 0.

Correctness is guaranteed for q ≥ n Ω( ) (because η = 0), and because is much larger than the constant degree κ in [DGG + 16], this is not a satisfying solution, as we aim at decreasing q to polynomial. Two alternatives (conservative and aggressive) are therefore developed in [DGG + 16].

The conservative method [DGG + 16]

The rst alternative suggested is to do as above, but reducing the z v modulo q, that is, set z v to be the representative of [ z vi i ] with coecients in [-q/2, q/2]. One then ensures, by rejection of all the z i 's together, that z v • 1/z v ≤ n 2.5 for all v ∈ A. This leads to E = Θ(n 3.5 • n 2.5 ) = Θ(n 6 ) (i.e. γ = 6, η = ν = 0) and therefore allows correctness for q as small as n O(κ) , which is polynomial for constant degree κ.

Using [DGG + 16, Lemma 8] restated below, the authors conclude that this method is quite inecient because for the above bound to hold simultaneously for all v ∈ A with good probability requires increasing n together with . Indeed, using Lemma 2, we can bound the probability that one of the z v does not satisfy z v • 1/z v ≤ n 2.5 by 2|A|/n = 4 /n. So if we want this probability to be small (say less than 1/2) in order for the sampling procedure to be ecient, we should increase n with .

8 Recall that the original proposal was setting E and therefore q to be super-polynomial even for bounded degree because of the drowning technique for publicly sampling encodings. Since then, attacks using encodings of zero [HJ16,CGH + 15,MSZ16] have restricted encodings to be private, allowing polynomially large E.

Lemma 2 (Lemma 8 from [DGG + 16]). Let [z] be chosen uniformly at random in R q and z be its canonical representative in R (i.e. with coecients in [-q/2, q/2]). Then it holds that Pr 1/z ≥ n 2 /q ≤ 2/n.

In the following section, we revisit the conservative method by generalizing this lemma.

The conservative method revisited

In the following lemma, we introduce an extra degree of freedom c compared to the lemma of [DGG + 16], but also improve the upper bound from O(n 1-c ) to O(n 1-2c ).

Lemma 3. Let [z] be chosen uniformly at random in R q and z be its representative with coecients between -q/2 and q/2. Then, for any c ≥ 1, it holds that

Pr [z = 0 ∨ 1/z ≥ n c /q] ≤ 4/n 2c-1 .
Corollary 2. Let [z] be chosen uniformly at random in R × q and z be its representative with coecients between -q/2 and q/2. Then, for any c ≥ 1, it holds that

Pr [ 1/z ≥ n c /q] ≤ 8/n 2c-1 .
We can use this corollary to compute the probability that one of the z v does not satisfy 1/z v ≤ n c /q when the [z i ]'s are independent and chosen uniformly at random in R × q . Indeed, the [z v ]'s are uniform in R × q because they are product of uniform invertible elements, and, by union bound, we have

Pr [∃v ∈ A s.t. 1/z v > n c /q] ≤ v∈A Pr [ 1/z v > n c /q] ≤ 8|A| n 2c-1 .
If we want this probability to be less than 1/2, in order to re-sample all the z i 's only twice on average, we should take |A| ≤ n 2c-1 16 .

(11)

But we also have .5 . In order to minimize E, we wish to minimize c, under (11). By taking the minimal value of c that satises this constraint, and recalling that |A| = 2 , we obtain

z v ≤ √ n z v ∞ ≤ √ nq, hence 1/z v • z v ≤ n c+0
E = Θ(n 4.5+L/2 ).
This means that γ = 4.5, ν = 0.5 and η = 0. This conservative method revisited is the same as the original one, except that we improve on the encodings size bound E. 9 In the following, we will then only focus on the conservative method revisited and not on the original one. 9 We also change a bit the point of view by xing n rst and then obtaining an upper bound on (which will appear because ν = 0 in E), while the authors of [DGG + 16] rst x and then increase n consequently.

Proof (Proof of Lemma 3). The proof of this lemma uses the same ideas as the one of [SS13, Lemma 4.1], but here, the element z is sampled uniformly modulo q instead of according to a Gaussian distribution. Let [z] be chosen uniformly at random in R q and z be its representative with coecients between -q/2 and q/2. Recall that we denote σ j : K → C the complex embeddings of K in C, with 1 ≤ j ≤ n. We know that the size of z is related to the size of its embeddings. Hence, if we have an upper bound on the |σ j (1/z)|, we also have an upper bound on 1/z . Moreover, the σ j 's are morphisms, so σ j (1/z) = 1/σ j (z), and it suces to have a lower bound on |σ j (z)|.

Let j ∈ {1, • • • , n}, there exists a primitive 2n-th root of unity ζ such that

σ j (z) = n-1 i=0 a i ζ i ,
where the a i 's are the coecients of z, and so are sampled uniformly and independently between -q/2 and q/2. As ζ is a primitive 2 k -th root of unity for some k, there exists i 0 such that ζ i0 = I, where I is a complex square root of -1. So we can write

σ j (z) = a 0 + Ia i0 + z,
for some z ∈ C that is independent of a 0 and a i0 . Now, we have that

Pr |σ j (z)| < q n c = Pr a 0 + Ia i0 ∈ B(-z, q n c ) ≤ Vol(B(-z, q n c )) q 2 ≤ 4 n 2c ,
where B(-z, q/n c ) is the ball centered in -z of radius q/n c . A union bound yields that

Pr ∃j, |σ j (z)| < q n c ≤ n • 4 n 2c = 4 n 2c-1 . Which in turns implies Pr ∀j, σ j 1 z ≤ n c q ≥ 1 - 4 n 2c-1 .
To complete the proof, we use the fact that for cyclotomic elds of power-of-two order, we have 1/z ≤ max j (|σ j (1/z)|). This gives the desired result.

Proof (Proof of Corollary 2). First, note that sampling [z] uniformly in R × q is the same as sampling

[z] uniformly in R q and re-sampling it until [z] is invertible. We denote by U (R q ) (resp. U (R × q )) the uniform distribution in R q (resp. R × q ). We then have that

Pr [z]←U (R × q ) [ 1/z ≥ n c /q] = Pr [z]←U (Rq) [ 1/z ≥ n c /q | [z] ∈ R × q ].
But using the denition of conditional probabilities, we can rewrite

Pr [z]←U (Rq) [ 1/z ≥ n c /q | [z] ∈ R × q ] = Pr [z]←U (Rq) [[z] ∈ R × q and 1/z ≥ n c /q] Pr [z]←U (Rq) [[z] ∈ R × q ]
.

The numerator of this fraction is less than Pr [z]←U (Rq) [ 1/z ≥ n c /q], which is less than 4 n 2c-1 using Lemma 3. And at least half of the elements of R q are invertible (if q is prime, we can even say that the proportion of non invertible elements is at most n/q, because q ≡ 1 mod 2n). Hence,

Pr [z]←U (Rq) [[z] ∈ R × q ]
≥ 1/2 and we obtain the desired result

Pr [z]←U (R × q ) [ 1/z ≥ n c /q] ≤ 8 n 2c-1 .

The aggressive method

This aggressive method was proposed by Döttling et al. in [DGG + 16] in order to instantiate the GGH multilinear map for their obfuscator. This method cannot be used for any set of atoms A, as it relies on the fact that the levels at which we encode fresh encodings have a specic structure.

Indeed, for each v ∈ A, we have either

[z v ] = [z i ] for some i ∈ {1, • • • , } or [z v ] = [z * • z -1 i ].
Using this remark, the secret [z i ]'s are generated in the following way.

For i from 1 to do:

sample a uniformly random invertible element [z i ] in R q . Let z i be the representative of [z i ]
in R with coecients between -q/2 and q/2, and z i be the representative of [z -1 i ] in R with coecients between -q/2 and q/2. until both following conditions are satised, re-sample [z i ]:

1/z i ≤ n 3 /q (12) 1/ z i ≤ n/q. ( 13
)
if i = , we also re-sample [z i ] until this third condition is met 1/z * ≤ n/q, (14) where z * is the representative of [ 1≤i≤ z i ] with its coecients between -q/2 and q/2.

Remark. As we sample the [z i ]'s from i = 1 to , when we generate [z ] all other [z i ]'s are already xed, so we can dene [z * ].

Note that with this method, we re-sample each z i an expected constant number of times, independently of . Indeed, all [z i ]'s for i ≤ -1 are sampled independently. And the two conditions we want are satised except with probability at most 8 n for each condition (using Corollary 2 with [z i ] and [z -1 i ] that are uniform in R × q and with c = 3 or c = 1). So, applying a union bound, the probability that we have to re-sample [z i ] is at most 16 n , which is less than 1/2 if n ≥ 32. The idea is the same for [z ] except that we also want 1/z * to be small. But all [z i ] for i < are already xed, so [z * ] only depends on [z ] and is uniform in R × q . Hence this last condition is also satised except with probability 8 n from Corollary 2. And the probability that the three conditions are met for [z ] is at least 1/2 as long as n ≥ 48.

To conclude, if n ≥ 48, the procedure described above will sample each [z i ] at most twice in average, independently of the choice of . So we can choose arbitrarily large and the sampling procedure will take time O( ) • poly(n).

It remains to choose our representative z v ∈ R of [z v ] ∈ R q and to get a bound on 1/z v • z v for all v ∈ A, in order to get the value of E. We will show that z v • 1/z v ≤ n 4 for some choice of the representative z v we detail below.

First case. If v has weight 1, that is [z v ] = [z i ] for some i, then we take z v = z i . With our choice of [z i ], we have that 1/z v ≤ n 3 /q. And as z v has its coecients between -q/2 and q/2 we have that

z v ≤ √ nq and hence z v • 1/z v ≤ n 3.5 ≤ n 4 . Second case. If v has weight -1, then there exists i ∈ {1, • • • , } such that [z v ] = [z * • z -1 i ]. We choose as a representative of [z v ] the element z v = z * • z i ∈ R,
with z * and z i as above (with coecients between -q/2 and q/2). We then have

1/z v = 1/z * • 1/ z i ≤ √ n • 1/z * • 1/ z i ≤ n 2.5 /q 2 .
Further, we have that

z v = z * • z i ≤ √ n • √ nq • √ nq = n 1.5 q 2 . This nally gives us z v • 1/z v ≤ n 4 .
To conclude, this method gives us E = Θ(n 7.5 ).

This means that γ = 7.5 and both η and ν are zero.

Remark. For all methods with Σ v ∼ z v zv (i.e. all methods except the simplistic one), if c ← D I+a, √ Σv is sampled using a Gaussian distribution of standard deviation

√ Σ v , we can rewrite c = c * z v with c * ← D I+a
zv ,σv for some σ v ∈ R. Note that c * is now a following a spherical Gaussian distribution but its support depends on z v . In addition to this remark, one can observe that in all the methods described above, there exists a real σ such that σ v σ ṽ = σ for all v ∈ A (in fact, σ v only depends on the weight of v in all the methods above). This means that for every fresh encodings [c v z -1 v ] and [c ṽ z -1 ṽ ] at level v and ṽ generated independently, we have an element c * ∈ K, following an isotropic distribution 10 of variance σ 2 such that c v c ṽ = c * z v z ṽ in R. Again, we note that the support of c * depends on z v and z ṽ , but as σ is larger than the smoothing parameter, this has no inuence on the variance of c * (by Lemma 1).

A summary of the dierent values of γ, η and ν for the dierent sampling methods can be found in Table 1 (Section 4.3).

4 Averaging attack

Our simple setting of the GGH multilinear map

To study the leakage of the GGH multilinear map, we need to make reasonable assumptions on what is given to the adversary. It has been shown in [HJ16] that knowing low level encodings of zero for the GGH13 multilinear map leads to zeroizing attacks that completely break the scheme. So our setting should not provide any, yet we will provide enough information for some zero-tests to pass. To this end, we will prove our setting to be secure in the weak multilinear map model, which supposedly prevents zeroizing attacks. 10 c * is isotropic as it is the product of two independent isotropic Gaussian variables.

14 This setting is inspired by the use of multilinear maps in current candidate obfuscator constructions, and more precisely the low noise candidate obfuscator of [DGG + 16]. Yet, for easier analysis, we tailored this setting to the bare minimum. We will assume the degree of the multilinear map to be exactly κ = 2, and will provide the attacker with elements that pass zero-test under a known polynomial. The restriction κ = 2 can easily be lifted but it would make the exposition of the model and the analysis of the leak less readable.

More precisely, we x a number m > 1 of monomials, and consider the homogeneous degree-2 polynomial:

H(x 1 , y 1 , . . . , x m , y m ) = x i y i .

Recall that we chose the set of atoms A to be the set of levels v ∈ {0, 1} that have weight exactly 1 or -1, where the weight of v is the number of its non-zero coecients. For all v ∈ A, we let ṽ = v * -v (we say that ṽ is the complement of v). We assume that for each v ∈ A of weight 1, the authority reveals encodings u v,1 , . . . , u v,m at level v of random values a v,1 , . . . , a v,m modulo I, and encodings u ṽ,1 , . . . , u ṽ,m at level ṽ of random values a ṽ,1 , . . . , a ṽ,m modulo I, under the only constraint that H(a v,1 , a ṽ,1 , . . . , a v,m , a ṽ,m ) = 0 mod I.

We remark that generating almost uniform values a •,• under the constraint above is easily done, by choosing all but one of them at random, and setting the last one to

a ṽ,m = -a -1 v,m m-1 i=1
a v,i a ṽ,i mod I.

In

Analysis of the leaked value

We describe in this section the information we can recover using averaging attacks, depending on the sampling method. We will see that depending on the sampling method, we can recover an approximation of A(z * h/g), or an approximation of A(h/g) or even the exact value of A(h/g). In order to unify notation, we introduce the leak L, which will refer to A(z * h/g) or A(h/g) depending the method. We explain below what is the value of L for the dierent methods, and how we can recover an approximation of it. In the case of the simplistic method, we also explain how we can recover the exact value of L from its approximation and how to use it to create a zero-testing parameter at level 2v * .

Statistical leakage. Let v ∈ A be of weight 1. We denote by [u v ] the encoding [H(u v,1 , u ṽ,1 , . . . , u v,m , u ṽ,m )].

Recall that we have

[u i,v ] = [c i,v z -1 v ]
, where c i,v = a i,v + r i,v g for some r i,v ∈ R. So using the denition of H and the fact that [u v ] passes the zero test, we can rewrite

[u v p zt ] = [H(c v,1 , c ṽ,1 , . . . , c v,m , c ṽ,m )(z v z ṽ ) -1 • z * hg -1 ] = [H(c v,1 , c ṽ,1 , . . . , c v,m , c ṽ,m ) • hg -1 ] = H(c v,1 , c ṽ,1 , . . . , c v,m , c ṽ,m ) • h/g.
Note that the product of the last line is in R, as it is a product of small elements compared to q. Also, the rst term is a small multiple of g so we can divide by g. We denote by w v ∈ R the value above (i.e., the representative of [u v p zt ] with coecients in [-q/2, q/2]). The term h/g of the product is xed, but the rst factor H(c v,1 , c ṽ,1 , . . . , c v,m , c ṽ,m ) depends on v: we can average over it. We now analyze this rst factor, depending on the method we choose for generating the fresh encodings of the GGH map. We will denote by Y v the random variable H(c v,1 , c ṽ,1 , . . . , c v,m , c ṽ,m ).

By denition of the polynomial H, we know that Y v = c i,v c i,ṽ . Moreover, all the c i,v are independent when i or v vary. So the c i,v c i,ṽ are centered random variables of variance Σ v Σ ṽ (observe that the variance of a product of independent centered variables is the product of their variances) and Y v is a centered random variable of variance mΣ v Σ ṽ (recall that H is a sum of m monomials). We now consider several cases, depending on the choice of Σ v .

Case 1 (the simplistic method). In this case, we have Σ v = σ 2 for all v ∈ A, for some σ ∈ R. This means that the Y v are centered isotropic random variables with the same variance. Let us call µ := E[A(Y v )] = mσ 2 ∈ R + this variance. If we compute the empirical mean of the A(Y v ), this will converge to µ and we can bound the speed of convergence using Hoeding's inequality. Going back to the variables w v = Y v • h/g, we have that E [A(w v )] = µ • A(h/g) for some µ in R + . Furthermore, all the A(w v ), with v of weight 1, are independent variables with the same mean, so we can apply Hoeding's inequality.

Case 2 (the conservative method). In this case, we chose Σ v ∼ z v z ṽ . We do not know the variance of the Y v (because the z v are secret) but we will be able to circumvent this diculty, by averaging over the z v 's.

First, using the remark we made at the end of Section 3, we have that Y v = c i,v c i,ṽ = c * i,v z v z ṽ , with the c * i,v being independent centered isotropic random variables with the same variance σ 2 ∈ R + . Hence, we can rewrite Y v = X v z v z ṽ with X v a centered isotropic variable of variance mσ 2 (which is independent of v). Unlike the previous case, we now have some z v z ṽ that contribute in Y v . However, we will be able to remove them again by averaging. Indeed, even if all the z v satisfy [z v z ṽ ] = [z * ] in R q , this is not the case in R. For our analysis, let us treat the z v z ṽ as random variables in R, that are isotropic and independent when v varies. We will call µ z := E [A(z v z ṽ )] their variance. Recall that as the z v z ṽ are isotropic, µ z is in R + . While the independence assumption may be technically incorrect, experiments conrm that the empirical mean E [A(z v z ṽ )] does indeed converge to some µ z ∈ R + as the number of sample grows, and more precisely it seems to converge as Assuming that the X v are independent of the z v z ṽ , 12 we nally obtain

µ z • (1 + ε) where ε ∈ K R satises ε ∞ = Õ( 1/|A|),
E[A(Y v )] = E[A(X v )]E[A(z v z ṽ )] = mσ 2 µ z .
We denote by µ = mσ 2 µ z this value. As in the previous case, the variables A(w v ) are independent (when v has weight 1) and have the same mean

E [A(w v )] = µ • A(h/g), with µ ∈ R + .
Case 3 (the exponential and aggressive methods). In these methods, we can again write Y v = X v z v z ṽ with X v a centered isotropic variable of variance mσ 2 for some σ ∈ R + , independent of v. However, unlike the previous case, the z v z ṽ are not isotropic variables anymore and therefore the z's do not average-out.

In the exponential method, the identity z v z ṽ = z * holds over R (where z * = i z i ∈ R is a representative of [z * ]), hence, z v z ṽ is constant when v varies, and we have

E [A(w v )] = µ • A(hz * /g),
for some scalar µ ∈ R + .

In the aggressive method, we have z

v z ṽ = z * • z i •z i for some 1 ≤ i ≤ , with z * the representative of [z * ], z i the representative of [z i ] and z i the representative of [z -1 i ] with coecients in [-q/2, q/2].
The element z * is xed, but, as in the conservative case, we can see the z i • z i as isotropic variables. Assuming they are independent, we then have E [A(z v z ṽ )] = µ z A(z * ) for some scalar µ z ∈ R + . And we again have

E [A(w v )] = µ • A(hz * /g),
for some scalar µ ∈ R + .

Conclusion on the average. To conclude, we have argued that in all methods,

E [A(w v )] = µ • L
for some scalar µ ∈ R + , where the leaked variable L depends on the sampling method in the following way:

• L = A(h/g) for the simplistic and the conservative methods.

• L = A(hz * /g) for the exponential and the aggressive methods. Now, using the fact that the random variables A(w v ) are independent for dierent v ∈ A of weight 1, we can compute their empirical mean and Hoeding's inequality will allow us to bound the distance to the theoretical mean. In the following we assume that we know µ. 13 12 We can view the variables c * i,v as being independent of the variables zv because the standard deviation of the Gaussian distribution is larger than the smoothing parameter (see Lemma 1). 13 The value of the scalar µ can be obtained from the parameters of the multilinear maps. If we do not want to analyze the multilinear map, we can guess an approximation of µ with a suciently small relative error, by an exhaustive search.

Relative error of the leakage. Compute

W = 2 |A| v∈A v of weight 1 A(w v )
the empirical mean of the random variables A(w v ). This is an approximation of µ • L. We know that the coecients of the random variable w v are less than q, so the coecients of A(w v ) are less that nq 2 . By applying Hoeding's inequality in R (Corollary 1) with ε = 1/n, B = nq 2 and m = |A|/2,

we have that W -µ • L ∞ < nq 2 √ 2 ln n √ |A|
(except with probability at most 1/n). As the coecients of µL are of the order of nq 2 , we have a relative error δ < 2 ln n/|A| for each coecient of µL.

As µ is known, this means that we know L with a relative error at most 2 ln n/|A|.14 Unfortunately, we cannot directly recover the exact value of L because its coecients are not integers. When L = A(hz * /g), i.e. for the exponential and aggressive methods, we do not know how to use this approximation of L to recover the exact value of L.15 When L = A(h/g), i.e. for the simplistic and conservatives methods, we can circumvent this diculty. The idea is to transform our approximation of L into an approximation of an element r ∈ R, with coecients that are integers of logarithmic bit-size. Indeed, if we have an approximation of r with error less that 1/2 we can round its coecients and recover the exact value of r. And we can get such an approximation using a polynomial number of samples because the coecients we want to recover have logarithmic bit-size.

This is what we explain in next subsection. Unfortunately, we will see that for the conservative method, the number of samples we need to be able to round r to its exact value is not compatible with the constraint we had on |A| for being able to generate the z v .

From the leakage to a complete attack against the GGH map. In this section, we explain how we can recover the exact value of A(h/g), when L = A(h/g) and we have enough samples. We then show how we can use this exact value to construct a zero-testing parameter at level 2v * .

Recovering L exactly when L = A(h/g). In the following, we assume that we have an approximation of A(h/g) with relative error δ < 2 ln n/|A| and we want to recover the exact value of A(h/g). Let u be any encoding at level v * that passes the zero test (we can take u to be one of the [u v ] = [H(u v,1 , u ṽ,1 , . . . , u v,m , u ṽ,m )]). We have that [u•p zt ] = c•h/g ∈ R for some small multiple c of g. In particular, the coecients of c are somehow small16 and are integers. Using our approximation W of µ • A(h/g) with relative error δ plus the fact that we know µ and c • h/g, we can recover an approximation of A(c) with relative error at most δ • n 2 by computing A(c

• h/g) • µ • W -1 .
The coecients of A(c) are integers and are less than m 2 n 2 E 4 . Indeed, c = H(c v,1 , c ṽ,1 , . . . , c v,m , c ṽ,m ) for some v and we have c v,i ≤ E for all v's and i's. So we know that c ≤ mn 1/2 E 2 and we get the desired bound on A(c) ∞ . Hence, if we have an approximation of the coecients of A(c) with relative error at most 1 2m 2 n 2 E 4 , the absolute error is less that 1/2 and we can round the coecients to recover A(c) exactly. We can then recover A(h/g) exactly by computing A(c • h/g)/A(c).

Putting together the conditions we got on the parameters, we have δ < 2 ln n |A| and we want δ • n 2 < 1 2m 2 n 2 E 4 to be able to recover A(c). This is satised if

2 ln n |A| < 1 2m 2 n 4 E 4 , i.e., |A| > 8E 8 m 4 n 8 ln n.
To conclude, if |A| > 8E 8 m 4 n 8 ln n, we can recover A(g/h) ∈ K exactly. [START_REF] Biasse | Computing generator in cyclotomic integer rings[END_REF] In Section 4.3, we compare this constraint to the ones we had for the samplings methods. We will see that for the simplistic method, our constraints are compatible, so we can perform the attack. But this is not the case with the conservative method.

Using A(h/g) to create a zero testing parameter at a forbidden level. We present here a possible way of using the recovered value A(h/g). Note that in current obfuscation model (for instance the weak multilinear map model of [GMM + 16] or [DGG + 16]), recovering A(h/g) is already considered as a success for the attacker. Indeed, its denominator is a multiple of A(g) = gḡ so in particular we have recovered a multiple of g, which is considered as a success of the attacker in these models. 18 Moreover, even if we do not consider that recovering a multiple of g is bad news, we present here a way of using A(h/g) to create a zero-testing parameter at a higher level than v * (here we create a zero-testing parameter at level 2v * ). First, note that the complex conjugation • in R is compatible with R q . Indeed, let c, r ∈ R, we have c + qr = c + qr = c + qr (because • is R-linear). So c + qr ≡ c mod q and we can dene the operation • in R q by [r] = [r]. We will use this to construct our zero-testing parameter. Let again [u] be an encoding of zero at level v * and write

[u] = [c • (z * ) -1 ] where c is a small multiple of g. Compute p zt = [u • p 2 zt • p zt • A(h/g) -1 ] = c z * • (z * ) 2 h 2 g 2 • z * h g • gg hh = (z * ) 2 • (hc) g .
As hc is small compared to q, this gives us a zero-testing parameter at level 2v * .

Noise analysis of the leakage

We sum up in this section the leakage that we can obtain and with which precision, depending on the sampling methods presented in Section 3.

The simplistic method. In this method, we have L = A(h/g). Recall that in this case, we can recover the exact value of L if > 4E 8 m 4 n 8 ln n (using the fact that |A| = 2 ). But in this method, we had E = O(n 1.5+ε ), for any ε > 0. Hence, taking = Θ(n 20+8ε m 4 ln n) satises the conditions for generating the parameters plus our condition > 4E 8 m 4 n 8 ln n. To conclude, when using the simplistic method with some choice of the parameters, we can recover the exact value A(h/g) and use it to construct a forbidden zero-testing parameter at level 2v * . Note that recovering A(h/g) also means that we recovered a multiple of g. However, we proved that in the weak multilinear map model, no polynomial time attacker could recover a multiple of g. This proves that the averaging attack described above is not captured by the weak multilinear map model.

Remark. For this sampling method, as Σ v ∼ 1, we do not need to average over the v, so we could also have = 2 as long as we have enough samples for each v.

The exponential method. In this method, we have L = A(z * h/g). We can recover an approximation of µL with relative error at most 2 ln n |A| . We do not know if it is possible to recover L exactly.

The conservative method revisited. In this method, we have L = A(h/g), we can recover an approximation of µL with relative error at most 2 ln n |A| according to our heuristic analysis. While the independence condition between the A(z v z ṽ ) for applying Hoeding's bound may not be satised, we show that this rate of convergence seems correct in practice in Appendix C.

Recall that if

> 4E 8 m 4 n 8 ln n, then we can recover A(h/g) exactly. But for the sampling method to work, we need to take E = Θ(n 4.5 √

). Hence, the condition > 4E 8 m 4 n 8 ln n can be rewritten > Θ(n 44 4 m 4 ln n).

This condition cannot be satised, so we cannot have enough samples for our attack when using this sampling method. And all we get is an approximation of µA(h/g). Nevertheless, the only thing that prevents the full attack is the size of the parameters we have to chose in order to be able to generate the fresh encodings. This is far from the kind of protection that was intended.

The aggressive method. In this method, we have L = A(z * h/g). We can recover an approximation of µL with relative error at most 2 ln n |A| . We do not know if it is possible to recover L exactly.

Concusion

We give in Table 1 a summary of the parameters used for the dierent sampling methods, and of the resulting leakage. The column 'constraints' species possible constraints on the parameters or on the atoms set A, that arise when using this sampling method. Recall that due to the correctness bound (9), there is always a constraint on the modulus q, so we do not mention it in the column 'constraints'. This constraint on q can be obtained from the columns γ, η and ν, using the formula log q ≥ 4 log(n)(3 + κ/2 + κγ + κνL + η ) + 4 log(m).

We have seen that the leak obtained in the conservative method is the same as the one of the unprotected scheme (the simplistic method). However, in the case of the conservative method, the number of available samples is not sucient to complete the attack, as it is the case in the simplistic method. This limitation on the number of samples comes from some constraints in the sampling procedure and seems a bit accidental, we do not nd this version of the countermeasure fully satisfactory.

We can also question the security of the other methods (exponential and aggressive), which leak an approximation of A(hz * /g), related to secret values. More precisely, one could wonder whether this noisy leak could be combined with the knowledge of p zt = [hz * g -1 ] to mount an attack. As this problem does not look like any traditional (ideal) lattice problem, we fail to conclude beyond Sampling method

γ η ν leak L full attack? constraints Simplistic [GGH13] 1.5 + ε 0 0 A(h/g) yes none Exponential [GGH13] 2.5 2.5 0 A(z * h/g) no none Conservative [DGG + 16] 6 0 0 A(h/g) no n ≥ 4 Conservative (revisited)
4.5 0 0.5 A(h/g) no none Aggressive [DGG + 16] 7.5 0 0 A(z * h/g) no structure of A Compensation (Sec. 5) 1.5 + 1/κ + ε 0 0 1 no none Table 1. Summary of the leak analysis, depending on the sampling method. This includes our new method, sketched in Section 5. We recall that, according to correctness bound (9), modulus q must satisfy log q ≥ 4 log(n)(cste + κ/2 + κγ + κνL + η ) + 4 log(m).

reasonable doubt that it should be intractable. We would nd more rational to make the leak unrelated to secret parameters. In the following section, we propose such a design, which is simple, and leads to better parameters.

The compensation method

In this section, we propose a new sampling method which is designed so that the leak L that an attacker can recover by using the averaging attack described above, reveals no information about secret parameters of the GGH map. Nevertheless, we note that even if the attack described above does not apply directly to this method, other averaging attacks may be able to leak secret information. An idea could be to x some encodings and average over the others.

Discussion on design. We have seen that choosing dierent covariance parameters Σ v at dierent levels v can in fact make the leak worse, as the attacker can choose to average them out. We also remark that the parameters [z v ] can be publicly re-randomized without aecting anything else, in particular without aecting the covariance Σ v of the numerator of the encodings. Indeed, we can choose random invertible elements [ẑ i ] ∈ R × q , and apply the following transformation to all encodings e v at level v, as well as to the zero-testing parameter [p zt ]:

[e v ] → i∈v ẑ-1 i • [e v ], [p zt ] → i∈v ẑi [p zt ].
This means that the relation between the covariance Σ v and the denominators z v can be publicly undone while maintaining functionality.

The compensation method. We therefore proceed to set Σ v = Σ for all levels v, and to choose Σ independently of the z v . Doing so, we observe that the leak L will generically be:

L ∼ Σ κ • A(h/g). (15)
We then choose Σ ∼ A(g/h)

1/κ , ensuring L ∼ 1: the leak is made constant, unrelated to any secret.

We insist nevertheless that, as the previous methods, this method comes with no formal security argument. We also warned that we have not thoroughly explored more general leakage attacks, varying the zero-tested polynomials or keeping some encodings xed.

It remains to see how short one can eciently sample encodings following this choice. To get tighter bounds, we look at the conditioning number (or distortion) δ(

√ Σ) = max(σi( √ Σ)) min(σi( √ Σ))
, where σ i runs over all embeddings. One easily veries the following properties:

δ(A(x)) = δ(x) 2 (16) δ(x k ) = δ(x) |k| for any k ∈ R, (17)
δ(xy) ≤ δ(x)δ(y).

(18)

If a variable x ∈ K R has independent continuous Gaussian coecients of parameter 1, then its embeddings are (complex) Gaussian variables of parameter Θ( √ n), and it holds with constant probability that ∀i, Ω(1)

≤ |σ i (x)| ≤ O( n log n). (19)
Indeed, the right inequality follows from classic tail bounds on Gaussian. For the left inequality,

consider that |σ i (x)| ≥ max(| (σ i (x))|, | (σ i (x))|)
, where both the real and imaginary parts are independent Gaussian of parameter Θ( √ n): each part will be smaller than Θ(1) with probability at most 1/ √ 2n. By independence, |σ i (x)| ≤ Θ(1) holds with probability at most 1/2n for each i, and one may conclude by the union bound.

By scaling (and plausibly ignoring discreteness issues since g and h are sampled above the smoothing parameter of Z n ) we can therefore assume, using rejection sampling over h and g, that δ(g), δ(h) ≤ O( √ n log n) , and therefore δ(

√ Σ) = δ(A(g/h)) 1/2κ ≤ (δ(g)δ(h)) 1/κ ≤ O(n log n) 1/κ .
This allows to scale Σ so that:

• g/ √ Σ ≤ o(1/ √ log n)
, so that we can sample eciently via Theorem 2.

• E = √ n • g • δ( √ Σ) • ω( √ log n) = O(n 1.5+1/κ+ε
): the size of the numerators of the encodings is barely worse than in the simplistic method, and signicantly better than in all other methods.

A Proof of Lemma 1

We recall here Lemma 1 and provide a proof of it, using a result of [MR04].

Lemma 1. For any g ∈

K, Σ ∈ S + , c ∈ K R such that g/ √ Σ ≤ o(1/ √ log n), if x ← D gR+c, √ Σ , then E[x] ≤ ε • √ Σ and V[x] -Σ ≤ ε • Σ for some negligible function ε(n).
Proof. This result follows from [MR04, Lemma 4.2], that we recall here:

Lemma 4 (Lemma 4.2 from [MR04]). For any n-dimensional lattice Λ, point c ∈ R n , unit vector u, and reals 0 < ε < 1, s ≥ 2η ε (Λ),

E x←D Λ,s,c [ x -c, u ] ≤ √ 2π εs 1 -ε E x←D Λ,s,c [ x -c, u 2 ] -s 2 ≤ 2π εs 2 1 -ε
where η ε (Λ) is the smoothing parameter of the lattice Λ.19

We cannot use this lemma directly to prove our Lemma 1, as we have a standard deviation Σ ∈ S + that might not be a real and we are sampling in gR + c which is not a lattice. But we can easily see that D gR+c,

√ Σ = c + √ Σ • D Λ,1,-c √ Σ
, where Λ is the lattice gR √ Σ

. We can then apply

Lemma 4 to D Λ,1,-c √ Σ
(this is a Gaussian distribution over a lattice, with standard deviation a scalar). If we prove that

E[D Λ,1,-c √ Σ ] + c √ Σ ≤ negl(n) (20) V[D Λ,1,-c √ Σ ] -1 ≤ negl(n) (21)
then, using the properties of the mean and the variance, we will obtain the desired result of Lemma 1.

Let's apply Lemma 4 to the distribution D Λ,1,-c/ √ Σ . We have s = 1 in the lemma, which gives us the constraint η ε (Λ) ≤ 1/2. So to get the best possible bound in the lemma, we want to minimize ε under this constraint. We will use the following upper-bound on η ε (Λ)

(see for instance [MR04, Lemma 3.3]). η ε (Λ) ≤ log(2n(1 + 1/ε)) π λ n (Λ).
Recall that our lattice Λ is the ideal g

√ Σ R ⊂ K R , hence we have λ n (Λ) = g/ √ Σ = o(1/ √ log n)
by hypothesis. In order to get the best possible bound, we take ε such that

log(2n(1 + 1/ε)) π λ n (Λ) = 1/2.
Using the fact that λ n (Λ) = o(1/ √ log n), we obtain that ε ≤ 1 n c for any constant c, i.e. ε = negl(n). We can then apply Lemma 4 to obtain Inequalities (20) and (21) (using the fact that ε = negl(n) and s = 1 in the lemma). This achieves the proof of Lemma 1.

B Security proof of our setting of the GGH map in the weak multilinear map model

In this section, we rst recall what is the weak multilinear map model (mentioned rst in [MSZ16] and then used in [GMM + 16] and in [DGG + 16]). Then we prove that the setting we dened in Section 4.1 is secure in the weak multilinear map model, for some notion of security we dene here.

B.1

The weak multilinear map model Scalar multiplication. For any v ∈ {0, 1} , a ∈ R/gR and α ∈ R, we have α•(a, v) = (α•a, v).

The oracle M implements the following interfaces.

Initialization. The oracle rst initializes the parameters. It sets n to be a power of 2, denes R = Z[X]/(X n + 1) and samples g an element of R. The size of the parameters is the same as the one we described in Section 2.2. The oracle M then receives a set of r couples (a, v) to encode. It creates a table T in which it stores the couples (a, v) together with a handle h i it generates, which is independent of the encoded value a but reveals the level of the encoding v. Finally, the oracle outputs the handles h i , for 1 ≤ i ≤ r. The oracle M also creates a table T for post-zero-test values, that is empty for the moment. This interface has to be called before the other ones, and any attempt to call this procedure more than once will fail.

Operations on encodings. Given two handles h 1 , h 2 and an operation Denition 1 (Security of our setting). We say that our setting of the GGH multilinear map is secure in the weak multilinear map model if any polynomial time adversary has negligible probability to make the oracle output WIN, when the oracle is initialized with the elements a v,i dened in Section 4.1.

We will now prove that our simple setting dened in Section 4.1 is secure in the weak multilinear map model, for the denition of security given above. This proof does not depend on the sampling method chosen, as long as it has enough min-entropy. As all the sampling methods described in this article have enough min-entropy, our setting will be secure in the weak multilinear map model, independently of the sampling method chosen.

H ∞ (Y ) = -log(max s∈S Pr(Y = s)).
For multiple random variables Y 1 , • • • , Y k , we let p i (s 1 , • • • , s i-1 ) be the guessing probability of Y i conditioned on Y j = s j for j < i. Then, dene

p i = E X1,••• ,Xi-1 [p i (X 1 , • • • , X i-1 )] to be the expec- tation of the p i (s 1 , • • • , s i-1 ). Finally, we denote by p max (Y 1 , • • • , Y k ) = max i p i the maximum of the p i 's.
For the proof of our theorem, we will use the improved Schwartz-Zippel lemma of [MSZ16, Section 5.1]. The classical Schwartz-Zippel lemma needs independent and uniform random variables, while this version allows us to use random variables that might be correlated and non uniform, as long as they have enough min-entropy. The statement of the lemma is the following:

Lemma 5 (Improved Schwartz-Zippel lemma from [MSZ16]). Let F be a eld, k > 0 be an integer and P ∈ F[X 1 , • • • , X k ] be a polynomial of degree at most d. Let Y 1 , • • • , Y k be random variables in F (that might be correlated and non uniform). Then we have

Pr Y1,••• ,Y k [P (Y 1 , • • • , Y k ) = 0] ≤ d • p max (Y 1 , • • • , Y k ).

B.3 Security proof

The main idea of the security proof is to use Schwartz-Zippel lemma to show that, except with negligible probability, the adversary will never be able to create encodings that passes the zerotest, except for linear combinations of the ones that are made public in the setting. Then, it is easy to show that the adversary cannot use these encodings to create a multiple of g. This kind of proof was already used to prove security of obfuscators in the weak multilinear map model + 16, DGG + 16]. But as our setting is simpler than a candidate obfuscator, the proof will also be easier.

[GMM
First, we recall and precise how we generate the encodings in our simple setting of the GGH map.

Let D a be a distribution over the elements of R that are invertible modulo g, with min-entropy at least n when reduced modulo g (i.e., for all x ∈ (R/gR) × , we have Pr y←Da (y = x mod g) ≤ 2 -n ).

And let D r be a distribution over R with min-entropy at least n. 21 For all v ∈ A of weight 1, sample m elements a v,i ← D a independently (with 1 ≤ i ≤ m) and m -1 elements a ṽ,1 , • • • , a ṽ,m-1 ← D a independently. Then, sample r v ← D r and let

a ṽ,m = -a v,m m-1 i=1 a v,i a ṽ,i + r v g
where a v,m is an element in R such that a v,m a v,m = 1 mod g, i.e. a v,m is a representative of the inverse of a v,m modulo g (chosen arbitrarily). We will initialize the oracle M with these elements (a v,i , v), for v ∈ A.

With the notations above, we have that for all v ∈ A of weight 1,

H(a v,1 , a ṽ,1 , . . . , a v,m , a ṽ,m ) = m i=0 a v,i a ṽ,i = (r v + a v,m r v )g
for some r v that depends on the a v,i 's and a ṽ,j 's (with i ≤ m and j ≤ m -1) but not on r v . Hence, as r v has min-entropy at least n and R is an integral domain, we have

H(a v,1 , a ṽ,1 , . . . , a v,m , a ṽ,m ) = rv g (22)
for some rv with min-entropy at least n. Moreover, knowing the rw for w = v (w of weight 1) does not decrease this min-entropy (because r v is independent of the rw ). Hence, we have that p max ({r v } v∈A of weight 1 ) ≤ 2 -n .

(23) 21 In the GGH multilinear map, the distribution Da should be a Gaussian distribution (whose shape depends on the sampling method). This has no importance for our proof, so we make no assumption about it here.

Theorem 3. Assume we initialize the oracle M with the couples (a v,i , v) dened above, for v ∈ A and 1 ≤ i ≤ m. Then, for any PPT adversary A interacting with the oracle M, the probability that A manages to make M output WIN is negligible in n. In other words, our simple setting of the GGH multilinear map is secure in the weak multilinear map model (see Denition 1).

Remark. The conditions on the distributions D a and D r are satised by all the sampling methods described in this article. Hence, the theorem prove that our simple setting of the GGH multilinear map is secure in the weak multilinear map model, independently of the sampling method chosen (among the ones describes in this article).

Proof. For simplicity of notation, we will sometime index the elements of

A by v 1 , • • • , v 2 .
In this proof, we will merge the arithmetic queries on the encodings and the zero-testing queries by saying that the adversary A directly sends a polynomial p to the oracle. Then M performs the arithmetic operations on the encodings that correspond to the polynomial p (if they are relevant)

and apply the zero-testing procedure on the result.

The idea of the proof is to show that the only encodings that A can query that will pass the zero-testing procedure are linear combinations of elements of the form H(a v,1 , a ṽ,1 , . . . , a v,m , a ṽ,m ) (all other polynomials in the a v,i 's will fail to pass the zero test with high probability). Then, each zero-test on a H(a v,1 , a ṽ,1 , . . . , a v,m , a ṽ,m ) will result in a handle of a random element (because of the randomness contained in r v ), and all these elements will be independent. Hence the adversary has negligible probability of nding a polynomial that annihilate them. Lemma 6. Let P be a polynomial in the variables (X v,i ) {v∈A,1≤i≤m} generated by the attacker A

such that P (a v1,1 , • • • , a v1,m , a v2,1 , • • • , a a 2 ,m ) = 0 mod g. Then, with overwhelming probability, we have P (X v1,1 , • • • , X v1,m , X v2,1 , • • • , X v 2 ,m ) = v∈A v 1 =1 α v H(X v,1 , X ṽ,1 , • • • , X v,m , X ṽ,m )
for some scalars α v ∈ R.

This lemma means that the only encodings that will pass the zero test that the attacker can create are the H(u v,1 , u ṽ,1 , • • • , u v,m , u ṽ,m ) and linear combination of them. As zero-testing linear combinations of encodings that pass the zero test does not provide more information that what was revealed by zero-testing the original encodings, we will assume in the following that the adversary makes zero testing queries for H(u v,1 , u ṽ,1 , • • • , u v,m , u ṽ,m ) for all v ∈ A of weight 1, and that they are the only queries that pass the zero test.

Recall that the numerator of H

(u v,1 , u ṽ,1 , • • • , u v,m , u ṽ,m ) is of the form H(a v,1 , a ṽ,1 , • • • , a v,m
, a ṽ,m ) = rv g (see Equality 22). Hence, after all its zero-test queries, the attacker A gets handles to the values rv for all v ∈ A of weight 1. These are the only post-zero-test handles the attacker obtains. These handles map to random elements rv that may not be independent, but that have a lot of (con- ditioned) min-entropy. Hence, it is very unlikely that the attacker creates a non zero polynomial that annihilates these random values. More formally, let P be a polynomial of degree d = poly(n) queried by the attacker in the post-zero-test phase. Then, using using the improved Schwartz-Zippel lemma of [MSZ16] (Lemma 5) in K, we have that

Pr[P ({r v } v∈A of weight 1 ) = 0] ≤ d • 2 -n = negl(n)
using the fact that p max ({r v } v∈A of weight 1 ) ≤ 2 -n (see Inequality (23).

Hence, the attacker has negligible probability of creating a non zero polynomial P , of degree polynomial in n, that annihilates the post-zero-test handles. This concludes the proof of our theorem.

Proof (Proof of Lemma 6).

Step 1. First, let v ∈ A be of weight 1 and let P be a polynomial in the variables {X v,1 , X ṽ,1 , • • • , X v,m , X ṽ,m } (and not in all X w,i for w ∈ A and i ≤ m) such that P (a v,1 , a ṽ,1 , • • • , a v,m , a ṽ,m ) = 0 mod g. We will show that P = αH mod g for some α ∈ R/gR. Note that as we are only interested (for the moment) in equalities modulo g, we will assume that our polynomial P has coecients in R/gR (which is a eld as gR is a prime ideal). We will also see the a v,i as elements of R/gR.

Using the fact that the polynomial P (u v,1 , u ṽ,1 , • • • , u v,m , u ṽ,m ) is a valid encoding at level v * , we know that

P = P 1 (X v,1 , X ṽ,1 , • • • , X v,m ) + X ṽ,m P 2 (X v,1 , X v,2 , • • • , X v,m )
for some polynomials P 1 of degree 2 and P 2 of degree 1. We cannot apply the Schwartz-Zippel lemma to P because the variable a ṽ,m mod g is completely determined by the other variables that appears in the polynomial. So we rst introduce a new polynomial that does not depend on X ṽ,m before applying the Schwartz-Zippel lemma.

We dene the polynomial Q ∈

(R/gR)[X v,1 , X ṽ,1 , • • • , X v,m ] (note that X ṽ,m does not appear in Q) by Q(X v,1 , X ṽ,1 , • • • , X v,m ) =X v,m P 1 (X v,1 , X ṽ,1 , • • • , X v,m ) - m-1 i=1 X v,i X ṽ,i P 2 (X v,1 , X v,2 , • • • , X v,m ).
Using the fact that a ṽ,m = -a -1 v,m m-1 i=1 a v,i a ṽ,i mod g, we have that

Q(a v,1 , a ṽ,1 , • • • , a v,m ) = a v,m P (a v,1 , a ṽ,1 , • • • , a v,m , a ṽ,m ) = 0 mod g.
But the variables a v,1 , a ṽ,1 , • • • , a v,m are drown from D a independently with guessing probability at most 2 -n (even when reduced modulo g), and the degree of Q is at most 3. So using Schwartz-Zippel lemma (Lemma 5) in R/gR, we have that Q should be the zero polynomial, except with negligible probability. In the following, we will then assume that Q = 0. This means that we have the equality between polynomials P 1 = X -1 v,m m-1 i=1 X v,i X ṽ,i P 2 . Hence, we can re-write

P = P 2 X -1 v,m m-1 i=1 X v,i X ṽ,i + X ṽ,m = P 2 X -1 v,m • H(X v,1 , X ṽ,1 , • • • , X v,m
, X ṽ,m ).

As we know that P is a polynomial and X v,m does not divide H, this means that it divides P 2 . But P 2 is of degree 1, hence we conclude that P = αH mod g for some scalar α ∈ R.

Step 2 . Now, let P be a polynomial in all the variables X v,i for v ∈ A and i ≤ m such that P ((a v,i ) v∈A,i≤m ) = 0 mod g. We will prove by induction on (recall that is the number of v ∈ A of weight 1) that P (X v1,1 , • • • , X v1,m , X v2,1 , • • • , X v 2 ,m ) = v∈A of weight 1 α v H(X v,1 , X ṽ,1 , • • • , X v,m , X ṽ,m ) mod g.

The case

= 1 was already done above (this is exactly step 1). Assume then that > 1. Let v 1 ∈ A be of weight 1 and assume without loss of generality that v 2 = ṽ1 . We dene the polynomial P in the variables {X v1,i , X v2,j } i,j≤m to be the polynomial P where X vj ,i is evaluated at a vj ,i for all j ≥ 3 and i ≤ m, i.e., P (X v1,1 , X v1,2 , • • • , X v2,m ) = P (X v1,1 , • • • , X v2,m , a v3,1 , • • • , a v 2 ,m ).

By hypothesis, we have that P (a v1,1 , a v1,1 , • • • , a v2,m ) = 0 mod g. But by step 1, this means that P = αH mod g for some α ∈ R. Using the structure of the levels of the encodings, we then know that

P (X v1,1 , • • • , X v 2 ,m ) =αH(X v1,1 , • • • , X v2,m ) + m i=1 P i (X v3,1 , • • • , X v 2 ,m )X v1,i +T (X v3,1 , • • • , X v 2 ,m )
for some polynomials P i and T in R/gR such that P i (a v3,1 , • • • , a v 2 ,m ) = 0 and T (a v3,1 , • • • , a v 2 ,m ) = 0. By induction hypothesis, we then know that the polynomials P i ans T are linear combination of the polynomial H evaluated at dierent X v,i . But then, if P i is non zero, P i (u v3,1 , • • • , u v 2 ,m )u v1,i is an encoding at level v * + v 1 which is not an admissible level. Hence, we have that P i = 0 for all i and, by induction hypothesis on T , we obtain the desired result.

Step 3. We have proven that for all polynomial P that the adversary can query, which passes the zero test, then with overwhelming probability we have α v H(X v,1 , X ṽ,1 , • • • , X v,m , X ṽ,m )+gT with T = 0, one can recover a multiple of g. Indeed,

P (X v1,1 , • • • , X v 2 ,m ) = v∈A v 1=1 α v H(X v,1 , X ṽ,1 , • • • , X v,
in v∈A v 1=1 α v H(X v,1 , X ṽ,1 , • • • , X v,m
, X ṽ,m ), all monomials X v,i X ṽ,i have the same coecient α v when i varies and v is xed. This means that we can recover a multiple of g by computing the difference of two such coecient in our polynomial v∈A v 1=1

α v H(X v,1 , X ṽ,1 , • • • , X v,m , X ṽ,m ) + gT (at least one should be non zero if T = 0). Hence, if the adversary queries such a polynomials, it knows a multiple of g. But the handles output by the oracle reveal nothing about g and g is chosen with suciently many min-entropy, hence we will show that the adversary cannot create a multiple of g except with negligible probability.

The idea is that while the attacker performs zero-test queries for polynomials of the form

v∈A v 1 =1
α v H(X v,1 , X ṽ,1 , • • • , X v,m , X ṽ,m ) (without the term gT ) and queries that do not pass the zero-test, it does not learn enough information to obtain a multiple of g with non negligible probability. Hence, it cannot ask for a polynomial of the form v∈A v 1=1

α v H(X v,1 , X ṽ,1 , • • • , X v,m , X ṽ,m ) + gT with T = 0. Assume then that the attacker only queries polynomials of the form

v∈A v 1 =1
α v H(X v,1 , X ṽ,1 , • • • , X v,m , X ṽ,m ) and polynomials that do not pass the zero test. We prove that all other possible choices of g, except a negligible fraction of them, would have led to the same answers of the oracle. And hence, the adversary cannot guess the value of g except with negligible probability.

The queries on polynomials of the form v∈A v 1=1

α v H(X v,1 , X ṽ,1 , • • • , X ṽ,m ) do not leak any information because for all values of g, we know that they should pass the zero test (and the handle that is generated when a query passes the zero test is independent of the choice of g). The queries on polynomials that do not pass the zero test may leak some information, but this leak will be negligible compared to the entropy of g. Let c 1 , • • • , c k be the numerators of all encodings that the adversary queried and that did not pass the zero test. Then, any g that is not a divisor of c 1 c 2

• • • c k is at most log 2 (N (c 1 c 2 • • • c k ))
. This is polynomial in n. Indeed, the element c 1 c 2 • • • c k was computed by a polynomial-time attacker, so its coecients are bounded by 2 n c for some constant c (the attacker has to write this element with a polynomial number of bits). To conclude, there are only a polynomial number of bad g (i.e., a polynomial number of non invertible elements that divide c 1 c 2 • • • c k ). But there is an exponential number of possible g when we generate the parameters of our multilinear map. Hence, the attacker has negligible chance to be able to guess a multiple of g if it knows nothing about it. This achieves the proof of our Lemma 6.

C Experiments

In this section we provide experimental data conrming the heuristic analysis of our attack against the conservative method. More precisely, following this sampling method, we study the empirical mean of A(z v z ṽ ), and the rate of convergence. We computed 1 |A| v∈A A(z v z ṽ ) for several values of n, q and |A| and wrote it as µ z (1 + ε), with ε ∈ K R . We plotted ε ∞ as a function of |A| in log-log scale, see Figure 1.

We observe that 1 |A| v∈A A(z v z ṽ ) indeed converges to a constant µ z in R + . Furthermore, we observe a slope of about -1/2 in log-log scale, conrming that the convergence is as fast as what would be given by the Hoeding bound if the variables were indeed independent: ε ∞ = f (n)/ |A|. In fact, it even seems that the function f is decreasing rather than slowly increasing (Hoeding bound gives f (n) ≤ O( √ log n)). The modulus q seems to have no eect on the relative precision.

n = 64, q = 12289 n = 64, q = 1437697 n = 256, q = 12289 n = 256, q = 1437697 n = 1024, q = 12289 n = 1024, q = 1437697

  and we do have g ≤ O(n) with overwhelming probability by [MR04, Lemma 4.4].

  as predicted by the Hoeding bound (results of the experiments are plotted in Appendix C).

  (a, v) ± (b, v) = (a ± b, v). Multiplication. If v and w are such that v[i]w[i] = 0 for all i ∈ [ ], then we have (a, v)•(b, w) = (a • b, v + w).

Fig. 1 .

 1 Fig. 1. Relative precision ε ∞ of the empirical mean 1 |A| v∈A A(zvzṽ) = µz(1 + ε) (vertical axis) as a function of |A| (horizontal axis).

  The idea of the weak multilinear map model( [MSZ16], [GMM + 16], [DGG + 16]) is to limit the power of the attacker by not giving it the encoded values directly. Instead, an oracle M keeps a table with the encoded values and allows the attacker to perform only some operations on these encoded values. More formally, an encoded element is a couple (a, v), with a ∈ R/gR and v ∈ {0, 1} . Recall that we denote by v * the vector (1, 1, • • • , 1).We can perform the following arithmetic operations on the encoded elements: Addition/subtraction. For any v, we have

  • ∈ {+, -, •}, the oracle rst checks whether the handles h 1 and h 2 are in its table. If one of them is not in the table, then in returns ⊥. Otherwise, let (a 1 , v 1 ) and (a 2 , v 2 ) be the encoded elements associated to these handles.If • ∈ {+, -}, M checks whether v 1 = v 2 . Ifthis is not the case, M outputs ⊥. Otherwise, it creates a new entry in its table, with the encoded value (a 1 • a 2 , v 1 ) and a new handle h and it outputsh. If • = •, then M checks whether v 1 [i]v 2 [i] = 0 for all i ∈ [ ]. If this is not the case, it outputs ⊥, otherwise it creates a new entry in its table with the encoded value (a 1 • a b , v 1 + v 2 )and a new handle h and it outputs h. by an element of R. Given a handle h and an element α ∈ R, the oracle M rst checks whether h is in its table T . If it is not, M outputs ⊥. Otherwise, let (a, v) be the corresponding encoded value. The oracle creates a new entry in its table, with encoded value (αa, v) and a new handle h . Then it outputs h . Zero-test query. Given a handle h, the oracle M checks whether h is in its table. If not M outputs ⊥. Otherwise let(a, v) be the associated encoded value. If v = v * , then M outputs ⊥. Otherwise, the oracle checks whether a is a multiple of g. If it is, then M creates a new entry in its post-zerotest table T , with value a/g ∈ R and with a new handle h , then it outputs h . If a is not a multiple of g, then M outputs ⊥. -zero-test query. Given a polynomial p of degree polynomial in n, 20 and a bunch of handles h 1 , • • • , h t , the oracle checks whether all handles h i are in its post-zero-test table T . If it is not the case, or if p is the identically zero polynomial, it outputs ⊥. Otherwise, let r i be the value corresponding to the handle h i in T . The oracle computes p(r 1 , • • • , r t ). If this is a non zero multiple of g, then the adversary outputs WIN, otherwise it outputs ⊥.

	Multiplication PostThe adversary wins the game if it manages to have the oracle output WIN after a post-zero-test query.

  m , X ṽ,m ) + gT

	for	some	polynomial	T in R. It remains to show that T	= 0, except with
	negligible	probability.	Observe	that	given	a	polynomial	of	the	form
		v∈A
		v 1=1

  • • • c k would have given the same answers. So the number of bad choices of g is at most the number of divisors of c 1 c 2 • • • c k . But, denoting by N the algebraically norm of elements in K, we have that N (x) > 2 if x ∈ R is non invertible, and if x|y, then N (x)|N (y). Hence, the number of non invertible divisors of c 1 c 2

The precise component of the attack which is not captured by the weak multilinear map model is the rounding operation performed at the end.

In an algebraic context, this would be more naturally described as the norm of x relative to the maximal real subeld of K, yet for our purposes it is more adequate to use the vocabulary of statistics.

We postpone the proof in appendix as the idea is the same as in [GMM + 16,DGG+ 16], in a much simpler context (this is based on a generalized version of the Schwartz-Zippel lemma from [MSZ16]).

Again, if we do not know µ, we can guess an approximation of µ with relative error at most 2 ln n/|A| (so that it has no inuence on our approximation of L), with an exhaustive search.

Note that if we recover the exact value of A(hz * /g), then its denominator is a multiple of g and this is considered as a success of the attacker in the weak multilinear map model.

Recall that q may be exponentially large but we assumed that the numerator of a top level encoding remains polynomial in n.

Note that this bound does not depends on q but only on E. This is why our attack still works even if q is exponential in n, as long as E remains polynomial in n.

For this to be true, we need h and g to be co-prime. But as the ideal g is prime, this will be true unless h is a multiple of g. And the case where h is a multiple of g is not a problem, as we can easily recover multiples of h (and so multiples of g).

Note that we do not use the same denition for ρΣ,x 0 as the authors of [MR04], this is why we have some 2π that appears in the bound.

This restriction on the degree of p may seem a bit unnatural, but this is needed for the proof, and it was already used (and discussed) in [MSZ16].

Acknowledgments. The authors are grateful to Alex Davidson, Nico Döttling and Damien Stehlé for helpful discussions.

Supported by a Veni Innovational Research Grant from NWO under project number 639.021.645. Supported by an ERC Starting Grant ERC-2013-StG-335086-LATTAC. on the functionality front.