Cryptographic Multilinear Maps and Bilinear Maps in Cryptography

1. CRYPTOGRAPHIC MULTILINEAR MAPS: APPLICATIONS, CONSTRUCTION, CRYPTANALYSIS Diamant Symposium, Doorn Netherlands Craig Gentry, IBM Joint with Sanjam Garg (UCLA) and Shai Halevi (IBM)

2. (Weil and Tate Pairings) Cryptographic Bi linear Maps

3. Bilinear Maps in Cryptography Cryptographic bilinear map Groups G 1 , G 2 , G T of order l with canonical generators g 1 , g 2 , g T and a bilinear map e : G 1 G 2 G T where e (g 1 a ,g 2 b ) = g T ab for all a,b 2 Z/ l Z. At least, discrete log problems in G 1 ,G 2 are hard. Given g 1 , g 1 a for random a 2 [ l ], output a. Symmetric bilinear map: G 1 = G 2 . (Call these G.) Instantiation: Weil or Tate pairings over elliptic curves.

4. Bilinear Maps: Hard Problems Bilinear Diffie-Hellman: Given g, g a , g b , g c 2 G and g 2 G T , distinguish whether g = e(g,g) abc . A tripartite extension of classical Diffie-Hellman problem: Given g, g a , g b , g 2 G, distinguish whether g = g ab . Easy Application: Tripartite key agreement [Joux00]: Alice, Bob, Carol generate a,b,c and broadcast g a , g b , g c . They each separately compute the key K = e(g,g) abc .

5. Other Apps of Bilinear Maps: IBE Identity-Based Encryption [Boneh-Franklin 01] Setup(1 ): Let H : {0,1} * G be a hash function that maps IDs to G. Authority generates secret a. MSK = a and MPK = g a . KeyGen(MSK,ID): Set g ID = H(ID) 2 G. SK ID = g ID a . Encrypt(MPK,ID,m): Generate random c. Set K=e(g a ,g ID ) c . Send CT = (g c , SymEnc K (m)). Decrypt(SK ID ,CT): Compute K = e(SK ID ,g c ).

6. Other Apps of Bilinear Maps: Predicate Encryption Predicate Encryption: a generalization of IBE. Setup(1 , predicate function F): Authority generates MSK,MPK. KeyGen(MSK, x 2 {0,1} s ): Authority uses MSK to generate key SK x for string x. (x could represent users attributes) Encrypt(MPK,y 2 {0,1} t , m): Encrypter generates ciphertext C y for string y. (y could represent an access policy) Decrypt(SK x ,C y ): Decrypt works (recovers m) iff F(x,y)=1. Predicate Encryption schemes using bilinear maps are weak . They can only enforce simple predicates computable by low-depth circuits.

7. Definition/Functionality and Applications Cryptographic Multilinear Maps

8. Multilinear Maps: Definition/Functionality Cryptographic n-multilinear map (for groups) Groups G 1 , , G n of order l with generators g 1 , , g n Family of maps: e i,k : G i G k G i+k for i+k n, where e i,k (g i a ,g k b ) = g i+k ab for all a,b 2 Z/ l Z. At least, the discrete log problems in {G i } are hard. Notation Simplification: e(g j 1 , , g j t ) = g j 1 +...+ j t .

9. Multilinear Maps over Sets Cryptographic n-multilinear map (for sets) Finite ring R and sets E i for all i 2 [n]: level-i encodings Each set E i is partitioned into E i (a) for a 2 R: level-i encodings of a. Sampling: It should be efficient to sample a level-0 encoding such that the distribution over R is uniform. Equality testing: It should be efficient to distinguish whether two encodings encode the same thing at the same level. Note: In the group setting, there is only one level-i encoding of a namely, g i a . Note: In the group setting, a level-0 encoding is just a number in [ l ]. Note: In the group setting, equality testing is trivial, since the encodings are literally the same.

10. Multilinear Maps over Sets (contd) Cryptographic n-multilinear map (for sets) Addition/Subtraction: There are ops + and such that: For every i 2 [n], every a 1 , a 2 2 R, every u 1 2 E i (a 1 ) , u 2 2 E i (a 2 ) : We have u 1 +u 2 2 E i (a 1 +a 2 ) and u 1 -u 2 2 E i (a 1 -a 2 ) . Multiplication: There is an op such that: For every i+k n, every a 1 , a 2 2 R, every u 1 2 E i (a 1 ) , u 2 2 E k (a 2 ) : We have u 1 u 2 2 E i+k (a 1 a 2 ) . At least, the discrete log problems in {S j } are hard. Given level-j encoding of a, hard to compute level-0 encoding of a. Analogous to multiplication and division within a group. Analogous to the multilinear map function for groups

11. Multilinear Maps: Hard Problems n-Multilinear DH (for sets): Given level-1 encodings of 1, a 1 , , a n+1 , and level-n encoding u, distinguish whether u encodes a 1 a n+1 . n-Multilinear DH (for groups): Given g 1 , g 1 a 1 ,, g 1 a n+1 2 G 1 , and g 2 G n , distinguish whether g = g n a 1 a n+1 . Easy Application: (n+1)-partite key agreement [Boneh- Silverberg 03]: Party i generates level-0 encoding of a i , and broadcasts level-1 encoding of a i . Each party separately computes K = e(g 1 , , g 1 ) a 1 a n+1 .

12. Big Application: Predicate Encryption for Circuits Let F(x,y) be an arbitrarily complex boolean predicate function, computable in time T f . There is a boolean circuit C(x,y) of size O(T f log T f ) that computes F. Circuits have (say) AND, OR, and NOT gates Using a O(|C|)-linear map, we can construct a predicate encryption scheme for F whose performance is O(|C|) group operations. [Garg-Gentry-Halevi-2012, Sahai-Waters-2012]

13. Multilinear Maps: Do They Exist? Boneh and Silverberg say its unlikely cryptographic m-maps can be constructed from abelian varieties: We also give evidence that such maps might have to either come from outside the realm of algebraic geometry, or occur as unnatural computable maps arising from geometry.

14. Focusing on NTRU and Homomorphic Encryption Whirlwind Tour of Lattice Crypto

15. Lattices, and Hard Problems 0 A lattice is just an additive subgroup of R n .

16. Lattices, and Hard Problems 0 v 2 v 1 v 1 v 2 In other words, any rank-n lattice L consists of all integer linear combinations of a rank-n set of basis vectors.

17. Lattices, and Hard Problems 0 v 2 v 1 v 1 v 2 Given some basis of L, it may be hard to find a good basis of L, to solve the (approximate) shortest/closest vector problems.

18. Lattice Reduction [Lenstra,Lenstra,Lov sz 82]: Given a rank-n lattice L, the LLL algorithm runs in time poly(n) and outputs a 2 n -approximation of the shortest vector in L. [Schnorr93]: Roughly, it 2 k -approximates SVP in 2 n/k time.

19. NTRU [HPS98] Parameters: Integers N, p, q with p q, gcd(p,q)=1. (Example: N=257, q=127, p=3.) Polynomial rings R = Z[x]/(x N -1), R p = R/pR, and R q = R/qR. Secret key sk: Polynomials f, g 2 R, where: f and g are small. Their coefficients are q. f = 1 mod p and g = 0 mod p. Public key pk: Set h g/f 2 R q . Encrypt(pk, m 2 R p with coefficients in (-p/2,p/2)): Sample random small r from R. Ciphertext c m + rh. Decrypt(sk, c): Set e fc = fm+rg. Output m (e mod p).

20. f 0 f 1 f N-1 c 0 c 1 c N-1 f 0 f 1 f N-1 g 0 g 1 g N-1 1 0 0 h 0 h 1 h N-1 0 1 0 h N-1 h 0 h N-2 0 0 1 h 1 h 2 h 0 0 0 0 q 0 0 0 0 0 0 q 0 0 0 0 0 0 q NTRU: Where are the Lattices? h = g/f 2 R q f(x) h(x) - q c(x) = g(x) mod (x N -1)

21. NTRU Security NTRU can be broken via lattice reduction (eventually) NTRU is semantically secure if ratios g/f 2 R q of small elements are hard to distinguish from random elements of R q .

22. NTRU Parameters: Integers N, p, q with p q, gcd(p,q)=1. (Example: N=257, q=127, p=3.) Polynomial rings R = Z[x]/(x N -1), R p = R/pR, and R q = R/qR. Secret key sk: Polynomials f, g 2 R, where: f and g are small. Their coefficients are q. f = 1 mod p and g = 0 mod p. Public key pk: Set h g/f 2 R q . Encrypt(pk, m 2 R p with coefficients in (-p/2,p/2)): Sample random small r from R. Ciphertext c m + rh. Decrypt(sk, c): Set e fc = fm+rg. Output m (e mod p).

23. NTRU Parameters: Integers N, p, q with p q, gcd(p,q)=1. (Example: N=512, q=127, p=3.) Polynomial rings R = Z[x]/( N (x) ), R p = R/pR, and R q = R/qR. Secret key sk: Polynomials f, g 2 R, where: f and g are small. Their coefficients are q. f = 1 mod p and g = 0 mod p. Public key pk: Set h g/f 2 R q . Encrypt(pk, m 2 R p with coefficients in (-p/2,p/2)): Sample random small r from R. Ciphertext c m + rh. Decrypt(sk, c): Set e fc = fm+rg. Output m (e mod p).

24. NTRU Parameters: Integers N, q. Small p 2 R, with ideal I = (p) relative prime to (q). (Example: N=512, q=127) Polynomial rings R = Z[x]/( N (x)), R p = R/I, and R q = R/qR. Secret key sk: Polynomials f, g 2 R, where: f and g are small. Their coefficients are q. f 2 1+I and g 2 I. (g is a small multiple of p.) Public key pk: Set h g/f 2 R q . Encrypt(pk, m 2 R p with small coefficients ): Sample random small r from R. Ciphertext c m + rh. Decrypt(sk, c): Set e fc = fm+rg. Output m (e mod I).

25. NTRU Parameters: Integers N, q. Small p 2 R, with ideal I = (p) relative prime to (q). (Example: N=512, q=127) Polynomial rings R = Z[x]/( N (x)), R p = R/I, and R q = R/qR. Secret key sk: Polynomials f, g 2 R, where: f and g are small. Their coefficients are q. f 2 1+I and g 2 I. (g is a small multiple of p.) Public key pk: Set h 0 g/f 2 R q and h 1 f/f 2 R q . Encrypt(pk, m 2 R p with small coefficients): Sample random small r from R. Ciphertext c mh 1 + rh 0 . Decrypt(sk, c): Set e fc = fm+rg. Output m (e mod I).

26. NTRU Parameters: Integers N, q. Small p 2 R, with ideal I = (p) relative prime to (q). (Example: N=512, q=127) Polynomial rings R = Z[x]/( N (x)), R p = R/I, and R q = R/qR. Secret key sk: Random z 2 R q . Polynomials f, g 2 R, where: f and g are small. Their coefficients are q. f 2 1+I and g 2 I. (g is a small multiple of p.) Public key pk: Set h 0 g/z 2 R q and h 1 f/z 2 R q . Encrypt(pk, m 2 R p with small coefficients): Sample random small r from R. Ciphertext c mh 1 + rh 0 . Decrypt(sk, c): Set e zc = fm+rg. Output m (e mod I).

27. NTRU NTRU Summary A ciphertext that encrypts m 2 R p has the form e/z 2 R q , where e is small (coefficients q) and e 2 m+I. To decrypt, multiply z to get e. Then reduce e mod I. The public key contains encryptions of 0 and 1 (h 0 and h 1 ). To encrypt m, multiply m with h 1 and add random encryption of 0.

28. NTRU: Additive Homomorphism Given: Ciphertexts c 1 , c 2 that encrypt m 1 , m 2 2 R p . c i = e i /z 2 R q where e i is small and e i = m i mod p. Claim: Set c = c 1 +c 2 2 R q and m = m 1 +m 2 2 R p . Then c encrypts m. c = (e 1 +e 2 )/z where e 1 +e 2 =m mod p and e 1 +e 2 is sort of small. It works if |e i | q.

29. NTRU: Multiplicative Homomorphism Given: Ciphertexts c 1 , c 2 that encrypt m 1 , m 2 2 R p . c i = e i /z 2 R q where e i is small and e i = m i mod p. Claim: Set c = c 1 c 2 2 R q and m = m 1 m 2 2 R p . Then c encrypts m under z 2 (rather than under z). c = (e 1 e 2 )/z 2 where e 1 e 2 =m mod p and e 1 e 2 is sort of small. It works if |e i | q.

30. NTRU: Any Homogeneous Polynomial Given: Ciphertexts c 1 , , c t encrypting m 1 ,, m t . c i = e i /z 2 R q where e i is small and e i = m i mod p. Claim: Let f be a degree-d homogeneous poly. Set c = f(c 1 , , c t ) 2 R q and m = f(m 1 , , m t ) 2 R p . Then c encrypts m under z d . c = f(e 1 , , e t )/z d where f(e 1 , , e t )=m mod p and f(e 1 , , e t ) is sort of small. It works if |e i | q 1/d .

31. Homomorphic Encryption Alice Server (Cloud) (Input: data x, key k) I want 1) the cloud to process my data 2) even though it is encrypted. Enc k [ f (x) ] Enc k (x) function f f (x) Run Eval[ f, Enc k (x) ] = Enc k [f(x)] The special sauce! For security parameter k, Evals running should be Time(f) poly( ) This could be encrypted too. Delegation: Should cost less for Alice to encrypt x and decrypt f(x) than to compute f(x) herself.

32. Homomorphic Encryption from NTRU Homorphic NTRU Summary A level-d encryption of m 2 R p has the form e/z d 2 R q , where e is small (coefficients q) and e 2 m+I. Given level-1 encryptions c 1 , , c t of m 1 , , m t , we can homomorphically compute a level-d encryption of f(m 1 , , m t ) for any degree-d polynomial f, if the initial e i s are small enough. The noise i.e., size of the numerator grows exp. with degree. Noise control techniques: bootstrapping [Gen09], modulus reduction [BV12,BGV12]. Big open problem: Fast reusable way to contain the noise.

33. (Similar to NTRU-Based HE, but with Equality Testing) Noisy Multilinear Maps

34. Adding an Equality Test Given level-d encodings c 1 = e 1 /z d and c 2 = e 2 /z d , how do we test whether they encode the same m? Fact: If they encode same thing, then e 1 -e 2 2 I. Moreover, (e 1 -e 2 )/p is a small polynomial. Zero-Testing parameter: a ZT = b z d /p for somewhat small b Multiply the zero-testing parameter with (c 1 -c 2 ). a ZT (c 1 -c 2 ) = b(e 1 -e 2 )/p has coefficients < q. If c 1 and c 2 encode different things, the denominator p ensures that the result does not have small coefficients.

35. Example Application: (n+1)-partite DH Parameters: Rings R = Z[x]/( N (x)), R p = R/I, and R q = R/qR, where p is small and I = (p) relative prime to (q). We dont give out p. Level-1 encodings h 0 , h 1 of 0 and 1. h i = e i /z, where e i = i mod I and is small. Party i samples a random level-0 encoding a i . Samples small a i 2 R via Gaussian distribution The coset of a i in R p will be statistically uniform. Party i sends level-1 encoding of a i : a i h 1 +r i h 0 2 R q . Each party computes level-n encoding of a 1 a n+1 . Note: Noisiness of encoding is exponential in n.

36. Example Application: (n+1)-partite DH Each party i has a level-n e i /z n encoding of a 1 a n+1 . Party i sets K i = a zt (e i /z n ), and key K i = MSBs(K i ). Claim: Each party computes the same key. K i K j = a zt (e i -e j )/z n = b(e i -e j )/p But e i , e j are small and both are in a 1 a n+1 +I. So, (e i -e j )/p is some small polynomial E ij . K i K j = b E ij , small. So, K i -K j have the same most significant bits, with high probability.

37. Big Application: Predicate Encryption for Arbitrarily Complex Functions Our noisy n-multilinear map permits predicate encryption for circuits of size up to n-1. Noisiness of encodings grows exponentially with n, but that is ok.

38. For example, can an eavesdropper trivially generate a level-n encoding of a (n+1)-partite Diffie-Hellman key? Cryptanalysis: Trivial Attacks

39. Trivial Attacks Eavesdropper in (n+1)-partite DH gets: Parameters: Level-1 encodings h 0 , h 1 of 0 and 1. h i = e i /z, where e i = i mod I and is small. Zero-testing parameter: a zt = bz n /p. Party is constribution: level-1 encoding c i /z of a i . Weighting of variables Set w(e i ) = w(z) = w(p) = w(c i ) = 1 and w(b) = 1-n. w(e i /z) = 0. Weight of all terms above is 0.

40. Trivial Attacks Straight-line program (SLP) Only allowed to (iteratively) add, subtract, multiply, or divide pairs of elements that it has already computed. A SLP that is given weight 0 terms can only compute more weight 0 terms. The DH key is of the form K = e/z n , where e 2 a 1 a n+1 +I. The key cannot be expressed as a weight 0 term.

41. Algebraic and Lattice Attacks Cryptanalysis: Nontrivial Attacks

42. Attack Landscape All attacks on NTRU apply to our n-linear maps. Additional attacks: The principal ideal I = (p) is not hidden. Recall a zt = bz n /p, h 0 = e 0 /z and h 1 = e 1 /z with e 0 = c 0 p. The terms a zt h 0 i h 1 n-i = b c 0 i p i-1 e 1 n-I likely generate the ideal I. An attacker that finds a good basis of I can break our scheme. There are better attacks on principal ideal lattices than on general ideal lattices. (But still inefficient.)

43. Using a Good Basis of I Player is DH contribution: a level-1 encoding of a i . Easy to compute a i s coset of I. (Notice: this is different from finding a small representative of a i s coset, a level- 0 encoding of a i .) Compute level-(n-1) encodings of 1 and a i : e/z n-1 , e/z n-1 . Multiply each of them with a zt and h 0 = c 0 p/z. We get bec 0 and bec 0 . Compute bec 0 /bec 0 = e/e in R p to get a i s coset. Spoofing Player i: If we have a good basis of I, player is coset gives a level-0 encoding of a i . The attacker can spoof player i.

44. Dimension-Halving for Principal Ideal Lattices [GS02]: Given a basis of I = ( u ) for u (x) 2 R and u s relative norm u (x) (x) in the index-2 subfield Q( N + N -1 ), we can compute u(x) in poly-time. Corollary: Set v(x) = u (x)/ (x). We can compute v(x) given a basis of J = (v). We know v(x)s relative norm equal 1.

45. Dimension-Halving for Principal Ideal Lattices Attack given a basis of I = ( u ): First, compute v(x) = u (x)/ (x). Given a basis { u (x)r i (x)} of I, multiply by 1+1/v(x) to get a basis {( u (x)+ (x))r i (x)} of K = ( u (x)+ (x)) over R. Intersect Ks lattice with subring R = Z[ N + N -1 ] to get a basis {( u (x)+ (x))s i (x) : s i (x) 2 R} of K over R. Apply lattice reduction to lattice { u (x)s i (x) : s i (x) 2 R}, which has half the usual dimension.

46. Summary We have a noisy cryptographic multilinear map that can be used to construct, for example, predicate encryption for arbitrarily complex circuits. Construction is similar to NTRU-based homomorphic encryption, but with an equality-testing parameter. Security is based on somewhat stronger computational assumptions than NTRU. But more cryptanalysis needs to be done! And more applications need to be found!

47. ? Thank You! Questions? ? TIME EXPIRED

48. Getting rid of principal ideals? Maybe present attacks and then say we can use general ideals.

49. Obfuscation: I give the cloud an encrypted program E(P). For any input x, cloud can compute E(P)(x) = P(x). Cloud learns nothing about P, except {x i ,P(x i )}. Barak et al: On the (Im)possibility of Obfuscating Programs Difference between obfuscation and FHE: In FHE, cloud computes E(P(x)), and it cant decrypt to get P(x). Obfuscation

50. Other Apps of Bilinear Maps: ABE Attribute-Based Encryption for Simple Functions [Sahai-Waters 05]: a generalization of IBE. Setup(1 ): Authority generates MSK, MPK. KeyGen(MSK, attr 2 {0,1} s ): Authority uses MSK to generate a key SK attr for user who has attributes attr. Encrypt(MPK,policy 2 {0,1} s , m): Generate ciphertext CT that can only be decrypted by SK attr s such that attr satisfies policy. Decrypt(SK attr ,policy,CT): Decrypt if attr satisfies policy. ABE schemes using bilinear maps are weak . They can only enforce simple policies that can be described by low-depth circuits.

51. Predicate Encryption for Circuits: Sketch of Sahai-Waters Construction Picture of Yao garbled circuit Mention that Yao GC is a predicate encryption scheme, except that it doesnt offer any resistance against collusions, which is a serious shortcoming in typical multi-user settings.

52. Predicate Encryption for Circuits: Sketch of Sahai-Waters Construction Now describe Sahai Waters as a gate-by-gate garbling, where the value for 1 is a function of the encrypters randomness s, and randomness rw for the wire that is embedded in the users key.

53. Semantic Security of NTRU