Report

Secure Evaluation of Multivariate Polynomials 1 MATTHEW FRANKLIN PAYMAN MOHASSEL UC DAVIS U OF CALGARY Oblivious Transfer 2 x0 b x1 xb = x0 (1-b) + x1 b + (1-b)br Secure Matrix Multiplication 3 b11 b12 b13 a 11 a 12 a 13 b 21 b 22 b 23 a 21 a 22 a 23 b 31 b 32 b 33 a 31 a 32 a 33 cij = bi1 a1j + bi2a2j + bi3a3j • Building block for secure linear algebra [KMWF`07] • Solving ``shared” linear systems, … DNF/CNF Formulas 4 (a1 a2) (~a1 a3) . . . r (1 – a1) (1 - a2) + r a1 (1-a3) + . . . Check polynomial [(1-a1) a1 + (1-a2) a2 + (1-a3) a3 + … ] r (a1 a2) … (~a1 a3) . . . Predicate evaluation TRUE = 0 False = random Conditional OT 5 Retrieve a data item if condition met (Oblivious Transfer) + (Predicate Evaluation) If predicate True return a data item If predicate False return a random value Reduced to polynomial evaluation Evaluating Multivariate Polynomials 6 X ( x1 , x 2 , , x n ) F n Y ( y1 , y 2 , , y n ) F 2 2 f ( X , Y ) ax 1 y 2 bx 1 x 3 y 3 n Secure Two-Party Computation 7 Y X f(X,Y) Security : Simulation of the Real protocol in an Ideal world Security Definition (Semi-honest) 8 Ideal World TTP y x f(x,y) f(x,y) y x Alice Bob Security Definition (Malicious) 9 Ideal World TTP anything Cheat = 0 y f(x,y) f(x,y) y x malicious honest Security Definition (Malicious) 10 Ideal World TTP y anything Cheat = 1 Send “corrupt” y f(x,y) x malicious honest Security Definition 11 Simulation-based security For any adversary A in the real protocol There is a simulator S in the ideal world (O IDEAL , S Alice ,O IDEAL , S Bob c ) (O REAL , A Alice ,O REAL , A Bob ) General Constructions 12 Boolean circuits [Yao`86, MF`06, LP`07, …] Arithmetic circuits [CDN`00, IPS`09,…] Comm/comp proportional to circuit size Degree-3 multivariate polynomial in n variables O(n3) comm. Input size is only O(n) Can we do better? Homomorphic Encryption 13 Public-Key Encryption Additive Epk(a) +h Epk(b) = Epk(a+b) [Pai`99, DJ`01, …] Multiplicative Epk(a) xh Epk(b) = Epk(ab) [ElGamal`84, …] More powerful 2-DNF formulas [BGN`05] Fully homomorphic [Gentry`09, …] Via Full Homomorphism 14 X ( x1 , x 2 , , x n ) F Y ( y1 , y 2 , , y n ) F n pk Epk(y1) , … , Epk(yn) Epk (f(X,Y)) Communication: O(n) ciphertexts (pk, sk) n Problem Solved? 15 Fully homomorphic encryption Not practical at this stage We still have to deal with “malicious behavior” Semi-honest Poly 16 Additively homomorphic Let P(X,Y) be degree 3 P(X,Y) = Pa(X,Y) + Pb(X,Y) monomials in Pa are degree < 2 in xi monomials in Pb are degree < 2 in yi X (pkb , skb) Epk_a(y1) , … , Epk_a(yn) Epk_b(x1) , … , Epk_b(xn) Epk_b (Pa(X,Y)) Epk_a (Pb(X,Y)) (pka , ska) Y 17 Comm: O(n) ciphertexts Using more efficient encryption schemes Only additive homomorphism is needed Only secure against semi-honest adversaries How to defend against malicious adversaries? And keep communication low Preventing Malicious Behavior 18 P ( X ,Y ) X 1 ( x1,1 , x 2 ,1 , , x n ,1 ) . . . . . . X k ( x1, k , x 2 , k , , x n , k ) P1 ( X , Y ) P ( X 1 , Y1 ) . . . Pk ( X , Y ) P ( X k , Y k ) X ( x1 , x 2 , , x n ) F Si (1) = xi,1 Si(2) = xi,2 . . . Si(k) = xi,k RS decoding Si(0) = xi P ( X ,Y ) n High Level Description 19 1) Semihonest-Poly for P1(X1, Y1) . . . k) Semihonest-Poly for Pk(Xk, Yk) C b {1,..., k } Reveal/verify the secrets for protocols in Cb C a {1,..., k } Reveal/verify the secrets for protocols in Ca Combine results and decode the output The Intuition 20 Cut-and-Choose Majority of unopened protocols are performed honestly |Ca|+ |Cb| > t1 Reed-Solomon Decoding Number of errors in the “Output Codeword” is small Efficient and unambiguous decoding Secret Sharing The number of opened shares is less than a threshold |Ca|+ |Cb| < t2 No information about the inputs is revealed |Ca|+ |Cb| = 2k/5 [DMRY`09] Similar techniques for the set intersection problem Better Amortized Efficiency 21 Evaluating (X1, Y1), … , (Xd, … , Yd) at polynomial P Batch evaluation e.g. useful for linear algebra Run d instances of the protocol in parallel Parallel composition (possible with small modifications) O(dkn) communication Encode d inputs using one polynomial Share-packing techniques [FK`92] O(k+d)n ) communication! Secure Linear Algebra 22 [KMWF`07, MW`08] Solving joint linear systems, joint rank/determinant computation Reduced to secure matrix multiplication Secure matrix multiplication Evaluation of O(n2) polynomials (n x n matrix) O(kn2) communication Secure linear algebra O(sn1/s) matrix multiplication O(s) round, O(kn2 + sn2+1/s) comm. Security parameter only multiplied by the smaller factor Working Over a Finite Field 23 Goldwasser-Micali encryption [GM`82] Works for GF(2) For RS codes, we need |F| = O(k) Extend GM to encrypt/decrypt over GF(2s) E(a1) , …, E(as) where ai in GF(2) Homomorphic properties? Addition: component-wise addition Plaintext-ciphertext multiplication (enc. poly) x (pub. Poly) mod (pub poly) Details in the paper Working Over a Finite Field 24 Paillier’s encryption [Pai`99] Works over ZN where N = pq “RS decoding” and “inversion” of elements? If inversion or RS decoding fail Then we can factor N Safe to pretend we work over a finite field Useful for other MPC protocols Other alternative is (variant of) ElGamal: gm hr Inefficient decryption, but sufficient for some applications Other Extensions 25 Higher degree polynomials Protocols extend to degree-t polynomials O(n└(t/2)┘) communication Security against “covert” adversaries Between malicious and semi-honest security Better efficiency Multiparty setting Using techniques from [IPS`08] Not as efficient as our two-party protocol Open Questions 26 • Degree t>3 protocols are not optimal • Can we design protocols with O(n) communication • Security against malicious adversaries • More powerful homomorphic encryption schemes • Evaluating 2-DNF formulas [BGN`05] • Defending against malicious behavior? • Similar techniques do NOT seem to work • Efficient semihonest-to-malicious compilers • ZK compilers not efficient • Ours is only optimal for low-degree polynomials • How about other functions Thank You! 27