Zeroizing Attacks on Cryptographic Multilinear Maps: Overview and Applications

Cryptographic multilinear maps (MMAPs) enable computations on encoded secret data, offering similarities to fully homomorphic encryption (FHE) while providing distinct features. MMAPs find applications in identity-based encryption, non-interactive zero-knowledge proofs, and more. The evolution of MMAP constructions has seen responses to zeroizing attacks and continual advancements to enhance security and efficiency in cryptographic protocols.

• Cryptography
• Multilinear Maps
• Zeroizing Attacks
• Applications
• Security

lizandrah Follow

Uploaded on Oct 05, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. ZEROIZING ATTACKS ON CRYPTOGRAPHIC MULTILINEAR MAPS MARIANA RAYKOVA SRI AND YALE UNIVERSITY Joint work with Jean-S bastien Coron, Craig Gentry, Shai Halevi, Tancr de Lepoint, Hemata Maji, Eric Miles, Amit Sahai, Mehdi Tibouchi *thanks Eric Miles for some slides

2. CRYPTOGRAPHIC MULTILINEAR MAPS (MMAPS) Goal: compute on encoded data that is secret Not fully homomorphic encryption (FHE) Similarity: Encode values E(a) Evaluate polynomials p(x) over the encoded values E(p(a)) Difference: FHE: cannot learn anything about encoded values without secret key MMAPS: zero-test - reveal whether the encoded value is zero using public parameters (for some types of encodings) Introduced by Boneh, Silverberg 2003 Generalization of bilinear maps that would have far-reaching consequences in cryptography Compute beyond quadratic functions on the encoded data

3. MMAPS APPLICATIONS Bilinear maps: identity-based encryption (IBE), attribute-based encryption for formulas (ABE), predicate encryption (simple predicates), efficient non-interactive zero-knowledge proofs Multilinear maps [BS03]: one round n-way Diffie-Hellman Key exchange, unique signatures and verifiable pseudorandom functions, broadcast encryption with short keys and transmissions Last few years explosion of applications: functional encryption for all circuits, witness encryption, program obfuscation, We hope this ample motivation will eventually lead to an efficient construction for a cryptographic multilinear map. 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. [BS03]

4. ROAD OF MMAP CONSTRUCTIONS First generation [Garg-Gentry-Halevi 13] from ideal lattices [Coron-Lepoint-Tibouchi 13] from Chienese Remainder Theorem [Gentry-Gorbunov-Halevi 15] from standard lattices Second generation [Coron-Lepoint-Tibouchi 15] modification of [CLT13] in response to zeroizing attacks [CGHLMMRST15] [Gentry-Halevi-Lepoint 15] - modification of [GGH13] in response to zeroizing attack [GGH13], [CGHLMMRST15], [Hu-Jia-15] Lepoint-Sahai-Tibouchi [Cheon-Han-Lee-Rye-Stehl -14] [Boneh-Wu-Zimmerman-14] recent attack: Brakerski-Gentry-Halevi-

5. MMAP DEFINITION [BS03] Given groups G1 and G2 of the same prime order p, e: G1n G2 is a multilinear maps if e(ga1, , gan)= e(g, , g)a1* *an if g1, , gn G1 e is non-degenerate: if g is the generator of G1, then e(g, , g) is the generator of G2 Bilinear map when n = 2 Asymmetric setting: e : G1 Gk Gk+1 MMP = (InstGen, Encode, GroupOp, Mmap) InstGen: public param = (p, g1, , gk+1, G1, , Gk+1, e) Encode: unique encoding Encode(param, i, x) = gix GroupOp: add(gix, giy) = gix+y Mmap: e(g1a1, , gnan)= e(g1, , gn)a1 an

6. HARDNESS ASSUMPTIONS Discrete log is hard Pr[A(param, i, gir) = r : param InstGen; r Zp] < negl Hardness Assumption multilinear DDH assumption {ga1, , gan, gan+1,e(g, , g)a1 anan+1} {ga1, , gan, gan+1,e(g, , g)random}

7. GRADED ENCODINGS Randomized encoding algorithm: not unique encodings but sets of possible encodings k-graded encoding system: a ring R and a system of sets { Si(a) } such that { Si(a) :a R } are disjoint Addition: if u1 Si(a1) and u2 Si(a2), then u1+u2 Si(a1+a2) Multiplication: if u1 Si1(a1) and u2 Si2(a2), then u1 u2 Si1+i2(a1 a2) Zero-testing a procedure that allows to check whether u1 Sk(0) for a fixed zero-testing level k

8. GRADED ENCODINGS Instance Generation: generate secret param description of k-graded encoding system public pzt zero-testing parameter for level k Encoding given param, level i and a Routputs level-i encoding of a: ui Si(a) Addition and multiplication - u1 Si(a1), u2 Si(a2) , u3 Sj(a3) Addition of encodings at the same level: u1+u2 Si(a1+a2) Multiplication of any encodings: u1 u3 Si+j(a1 a3) Zero-testing given pzt and u, output 1 if u Sk(0) , and 0 otherwise Enables equality testing at level k

9. ATTACKS ON [CLT13]

10. [CLT13] MULTILINEAR MAPS pi: big primes gi: small primes System parameters Primes: p1, ..., pn g1, , gn (gi << pi for all i) Secret parameters Level parameter: z Zx0 Different encoding using different zi Zx0 Modulus: x0 = p1 . . pn Public parameter

11. [CLT13] ENCODING Plaintext space: m = (m1, ,mn) Zg1 Zg2 Zgn Encode: via Chinese remainder theorem (CRT) in Zx0 To encode message (m1, , mn) at level j i n compute ei = mi +rigi for random ri << pi CRT(e1,...,en) zj mod x0 Output more general level z1 zm

12. [CLT13] ARITHMETIC PROPERTIES Addition mi+rigi zj mod pi+m'i+r'igi mod pi=(mi+m'i)+(ri+r'i)gi mod pi zj zj Multiplication mod pi=mim'i+(rim'i+r'imi+rir'igi)gi mi+rigi zj mod pi*m'i+r'igi mod pi zk zj+k Bounded noise growth (mi + rigi)(m i + r igi) < pi for all i

13. [CLT13] ZERO TESTING Let pi = x0/ pi= j i pj for all i n Property for any e1, , en CRT(p1 . e1, , pn . en) = 1 i n pi ei mod x0 Zero-test parameter: random hi << pi for all i n k is zero test level pzt = CRT(p1 h1g1-1, , pn hngn-1) . zk mod x0 gi-1 are computed mod pi

14. HOW TO ZERO-TEST? Level-k encoding a = z-k . CRT(m1 + r1g1, , mn + rngn) mod x0 Zero-test parameter for level k pzt = zk . CRT(p1 h1g1-1, , pn hngn-1) mod x0 Zero-testing: check whether |a.pzt| is small a.pzt mod x0 = CRT(pi (higi-1mi + hiri))1 i n = 1 i n pi (higi-1mi + hiri ) mod x0 If a encodes 0, then the equality holds over the integers a.pzt= 1 i n pi hiri since |hiri| << pi If a does not encode 0, or it is not at the zero-testing level |a.pzt| x0

15. ATTACKS ON [CLT13] [CLT13] seemed immune to the weak DL attacks on [GGH13] Until [CHLRS15] gave the first attack on [CLT13] Based on zeroizing techniques: rely on low level 0-endoings Complete break: recovers private parameters [BWZ14] and [GGHZ14] proposed attempted fixes [CGHLMRST15] extend attacks on [CLT13] Attacks without low level 0s (appeared also in [BWZ14]) Attack on proposed fixes of [BWZ14] and [GGHZ14] Attacks on simplified versions of obfuscation constructions

16. [CHLRS15] ATTACK CRT(m1+r1g1,...,mn+rngn) zj n - # of primes pi; K- zero-testing level Ingredients: three sets of encodings {Ai}1 i n , {B0, B1}, {Ci}1 i n mod x0 Ai=CRT(g1ai,1,...,gnai,n) n encodings of 0 k z k+j+l = K Bi=CRT(bi,1,...,bi,n) two encodings target of the attack j z Every Ai1Bi2Ci3 is zero-test level encoding Ci=CRT(ci,1,...,ci,n) n encodings zl

17. [CHLRS15] ATTACK Simple example: n=2, K=3 A1=CRT(g1a1,1, g2a1,2) A2=CRT(g1a2,1, g2a2,2) z z B'=CRT(b'1,b'2) B=CRT(b1,b2) z z C1=CRT(c1,1, c1,2) C2=CRT(c2,1, c2,2) z z Multiply: A1. B . C1 = z-3 . CRT(g1a1,1b1c1,1, g1a1,2b1c1,2)

18. [CHLRS15] ATTACK Zero-test pzt = z3 . CRT(p1 h1g1-1, p2 h2g2-1) mod x0 A1. B . C1 = z-3 . CRT(g1a1,1b1c1,1, g1a2,1b2c2,1) Set W1,1 = pzt . A1. B . C1 mod x0 = p1 h1a1,1b1c1,1 + p2 h2a1,2b2c1,2 integers (without modular reduction) 1 The equality holds over the 2 c1,1 1b1 0 a1,1 a1,2 W1,1 = c1,2 0 2b2

19. [CHLRS15] ATTACK Use the rest of the sets A = {A1, A2} and C = {C1, C2} W1,2 = pzt . A1. B . C2 = 1a1,1b1c2,1+ 2a1,2b2c2,2 W2,1 = pzt . A2. B . C1 = 1a2,1b1c1,1+ 2a2,2b2c1,2 W2,2 = pzt . A2. B . C2 = 1a2,1b1c2,1+ 2a2,2b2c2,2 Set new matrix W1,1 W1,2 a1,1 a1,2 c1,1 c2,1 1b1 0 = W= W2,1 W2,2 a2,1 a2,2 c1,2 c2,2 0 2b2

20. [CHLRS15] ATTACK 1b1 0 C W= A 0 2b2 Compute similarly W using the sets {A1, A2}, {C1, C2} and B 1b 1 0 C W = A 0 2b 2 Compute over Q 1/ 1b1 0 (W )-1= C-1 A-1 0 1/ 2b2

21. [CHLRS15] ATTACK So far we computed W, (W )-1 Multiply W (W )-1 over Q b1/b 1 0 A-1 A W (W )-1= 0 b2/b 2 Recover b1/b 1 and b2/b 2 computing the eigenvalues Use the above values to factor x0

22. NO LOW LEVEL ZERO ENCODINGS ATTACK EXTENSION #1

23. ATTACK SETS Ingredients: three sets of encodings {Ai}1 i n , {B0, B1}, {Ci}1 i n Not necessarily encodings of 0 Ai=CRT(ai,1,...,ai,n) n encodings k z k+j+l = K Bi=CRT(bi,1,...,bi,n) two encodings target of the attack j z Every Ai1Bi2Ci3 is zero-test level encoding Ci=CRT(ci,1,...,ci,n) n encodings zl

24. NO LOW LEVEL ZERO ENCODINGS Each 3-wise product encodes 0 at the zero-testing level: Ai. B . Cj , Ai.B . Cj for all i, j g1 divides ai,1. b . cj,1 , ai,1.b . cj,1 for all i, j g2 divides ai,2. b . cj,2 , ai,2.b . cj,2 for all i, j a1,1 a1,2 c1,1 c2,1 1b1/g1 0 W= a2,1 a2,2 c1,2 c2,2 0 2b2/g2 Equalities hold over Q a1,1 a1,2 c1,1 c2,1 1b 1/g1 0 W = a2,1 a2,2 c1,2 c2,2 0 2b 2/g2

25. NO LOW LEVEL ZERO ENCODINGS 1b1/g1 0 C W = A 0 2b2/g2 1b 1/g1 0 (W )-1= A-1 C-1 0 2b 2/g2 b1/b 1 0 A-1 A W (W )-1= 0 b2/b 2 compute eigenvalues

26. MULTIPLE MONOMIALS ATTACK EXTENSION #2

27. [BWZ14] IMMUNIZATION OF [CLT13] Encoding (m1, m2) is (a, a ): , 1, 2, 3, 4 - random a is a [CLT13] encoding of (m1, m2, , 1) a is a [CLT13] encoding of ( 2, 3, , 4) Encodings can be added and multiplied Zero-testing parameters [CLT13] zero test parameter pzt tL: encoding of (1, 1, 1, 0) tR: encoding of (0, 0, 1, 0) Zero-testing (a, a ): pzt (tLa tRa )

28. MULTIPLE MONOMIALS Top level zero can be obtained only in the form a.b.c a .b .c Attack sets ai = CRT(ai,1, ai,2)/z ai 0 Ai = 0 a i a i = CRT(a i,1, a i,2)/z b1 0 b2 0 B = B = 0 b 1 0 b 2 ci = CRT(ci,1, ci,2)/z ci 0 Ci = 0 c i c i = CRT(c i,1, c i,2)/z

29. MULTIPLE MONOMIALS Wi,j = pzt((Ai B Cj). [tL, -tR]) 1b1,1/g1 ci,1 - 1b 1,1 /g1 c i,1 ai,1 ,a i,1 , ai,1 ,a i,1 Wi,j = ci,2 2b1,2 /g2 Increased dimension c i,2 - 2b 1,2 /g2 b1,1/b2,1 b 1,1/b 2,1 A-1 A W (W )-1= b1,2/b2,2 b 1,2/b 2,2

30. MATRIX ENCODINGS ATTACK EXTENSION #3

31. [GGHZ14] FIX FOR [CLT13] Encoding of a value m is CLT encoding of independent random value at level z CLT encoding of 0 at level z Enc($) Enc(0) Enc(0) Enc(0) Enc($) Enc(0) T T-1 mod x0 C= Enc(0) Enc(0) Enc(m) Secret matrix; uniformly random in Zx0d d CLT encoding of m at level z

32. [GGHZ14] FIX FOR [CLT13] Zero-test parameters s = [Enc($) Enc($) Enc(0) Enc(0) Enc($)] T-1 mod x0 t = pzt. T [Enc(0) Enc(0) Enc($) Enc($) Enc($)]T mod x0 CLT encodings at level 0 Whp small relative to x0 if C encodes 0 Zero-testing s C t mod x0 = (Enc($).Enc(m)+Enc(0)).pzt mod x0

33. MATRIX ENCODINGS Attack sets Ai = T Ai* T-1 i [nd] Bi = T Bi* T-1 i [0,1] Ci = T Ci* T-1 i [nd] Wi,j = s Ai B0 Cj t = s T Ai B0 Cj T-1 t cj ai

34. MATRIX ENCODINGS (B0 mod p1) (B1 mod p1)-1 A-1 A W (W )-1= (B0 mod p2) (B1 mod p2)-1 CharPoly(W (W )-1) = i CharPoly((B0 mod p1) (B1 mod p1)-1) Factor CharPoly(W (W )-1) and use Cayley-Hamilton theorem to recover the primes pi

35. ATTACK ON SIMPLIFIED [GGHRSW13] OBFUSCATION BRANCHING PROGRAM OBFUSCATION

36. (OBLIVIOUS) BRANCHING PROGRAMS [BARRINGTON86] BP of length m with n input bits is defined as (inp(1), A1,0, A1,1), (inp(2), A2,0, A2,1), , (inp(m), Am,0, Am,1) Ai,0, Ai,1 {0, 1}5 5 inp(x) : [m] [n] BP for F evaluates on input x = (x1, , xn) n F (x) = 1, if 0, otherwise. i=1 Ai,inp(i) = I

37. (OBLIVIOUS) BRANCHING PROGRAMS Example: BP of length 9 with 4-bit inputs A1, 0 A1, 1 A2, 0 A2, 1 A3, 0 A3, 1 A4, 0 A4, 1 A5, 0 A5, 1 A6, 0 A6, 1 A7, 0 A7, 1 A8, 0 A8, 1 A9, 0 A9, 1 0

38. (OBLIVIOUS) BRANCHING PROGRAMS Example: BP of length 9 with 4-bit inputs A1, 0 A1, 1 A2, 0 A2, 1 A3, 0 A3, 1 A4, 0 A4, 1 A5, 0 A5, 1 A6, 0 A6, 1 A7, 0 A7, 1 A8, 0 A8, 1 A9, 0 A9, 1 0 1

39. (OBLIVIOUS) BRANCHING PROGRAMS Example: BP of length 9 with 4-bit inputs A1, 0 A1, 1 A2, 0 A2, 1 A3, 0 A3, 1 A4, 0 A4, 1 A5, 0 A5, 1 A6, 0 A6, 1 A7, 0 A7, 1 A8, 0 A8, 1 A9, 0 A9, 1 0 1 1 0 Multiply the chosen 9 matrices. If the product is I, output 1. Otherwise, output 0.

40. BARRINGTONS THEOREM [B86] Every function computable by depth-d circuit is computable by a branching program of length 4d. Corollary: every function in NC1 has a polynomial- length branching program

41. RANDOMIZED BRANCHING PROGRAMS [KILIAN88] Randomized BP (RBP) construction of length m and input size n: BP: (inp(1), A1,0, A1,1), , (inp(m), Am,0, Am,1) Sample invertible matrices R0, , Rm {0, 1}5 5 Set Bi,0 = Ri-1 Am,0 Ri -1, Bi,1 = Ri-1 Am,1 Ri-1 Omitting several steps Hide matrices with multilinear maps B1,0 B2,0 B3,0 B4,0 B5,0 B6,0 B7,0 B8,0 B9,0 B1,1 B2,1 B3,1 B4,1 B5,1 B6,1 B7,1 B8,1 B9,1

42. ATTACK ON SIMPLIFIED OBFUSCATION There exist partitions on the input bits and the branching program Input bits: [l] = X Y Z BP positions: [L] = A B C inp(i) X i A; inp(i) Y i B; inp(i) Z i C B1,0 B2,0 B3,0 B4,0 B5,0 B6,0 B7,0 B8,0 B9,0 B8,1 B9,1 B3,1 B4,1 B6,1 B7,1 B1,1 B2,1 B5,1 B C A BP0 and BP1 where BPb = A(x) Bb(y) C(z) A(x) is a branching program over the positions of A depending on input x C(x) is a branching program over the positions of B depending on input y B0(z) and B1(z) are two different programs over the positions of B that depend on input z BP0 and BP1 compute the same constant function that outputs 1

43. ATTACK ON SIMPLIFIED OBFUSCATION Attack sets Matrix dimension w Ai = { i=1|A| Enc(Bi, inp(i))} x {0,1}|X| i [nw] MMAP parameter Bi = { i=|A|+1|A B| Enc(Bi, inp(i))} y {0,1}|Y| i {0,1} Ci = { i=|A B|+1|A B C| Enc(Bi, inp(i))} z {0,1}|Z| i [nw]

44. CONCLUSIONS Zeroizing attacks on [CLT13] break completely the scheme You do not need low level zero encodings for the attacks The attacks can be generalized to break the proposed fixes [BWZ14] and [GGHZ14] Obfuscation constructions are not broken We can attack only simplified obfuscation constructions [CLT15] new candidate fix of [CLT13] that does not suffer from our zeroing attacks

45. THANK YOU!