ID Privacy-Preserving Data Mining Lindell 20) 1),30) 1 3 semi-honest malicious 3 n t < n/2 15) semi-honest malicious semi-honest malicious mali

Size: px

Start display at page:

Download "ID Privacy-Preserving Data Mining Lindell 20) 1),30) 1 3 semi-honest malicious 3 n t < n/2 15) semi-honest malicious semi-honest malicious mali"

ゆめじとこたに
6 years ago
Views:

1 Vol. 52 No (Sep. 2011) semi-honest malicious CPU Intel Core2 Quad 3.0 GHz RAM 4GB µ 3 Privacy-Preserving Data Mining A Lightweight Three-party Secure Function Evaluation with Error Detection and Its Experimental Result Koji Chida, 1 Dai Ikarashi, 1 Koki Hamada 1 and Katsumi Takahashi 1 We propose a three-party secure function evaluation protocol with lightweight error detection and show the experimental result. Assuming that there exists honest majority, the proposed protocol obtains the outcome of arithmetic and/or logic operations from three-shared values without disclosing the original value in the semi-honest model and can detect the error if the outcome is manipulated by a malicious party faster than the existing schemes. The implementation system, which consists of a PC with Intel Core2 Quad 3.0 GHz and 4 GB RAM, can compute the multiplication of two 32 bits integers about 1.6 microseconds. Moreover we consider Privacy-Preserving Data Mining as an application of the three-party secure function evaluation protocol ) 37) 39) 3),5) 11),25),28),31) Secure Computation Secure Function Evaluation2 3) 5) 10),14),34) 36) 1 ID ID 1 NTT NTT Information Sharing Platform Laboratories 1 6) 7) 18) 2674 c 2011 Information Processing Society of Japan

2 ID Privacy-Preserving Data Mining Lindell 20) 1),30) 1 3 semi-honest malicious 3 n t < n/2 15) semi-honest malicious semi-honest malicious malicious 3) n 4 Reed-Solomon 12) n 3 1 Privacy-Preserving Data Analysis Privacy-Preserving Data Utilization n =3 malicious semi-honest Yao 32),33).Yao 2 2 Oblivious Transfer 17) MIX-net 19) Secure Circuit Evaluation 13) Yao 2 22) 2 29) 29) 2 Z/mZ m 1 3),5) 8),23) 2),9),21),24) 4) Sharemind 28) 3 semi-honest 4)

3 Z/mZ 2 m 3) 5) m =2 32 P i i =0,...,n 1 a Z/mZ P i a a = n 1 ai ai Z/mZ i=0 a 0,...,a n 1 n 1 Z/mZ P i a, b Z/mZ a i, b i d i = a i + b i n 1 i=0 di = a + b d 0,...,d n 1 n 1 Z/mZ d i a + b P i a c P i ac ca i 4) 4) P i a = n 1 ai, i=0 b = n 1 bi ai,bi Z/mZ i=0 n 1 ab = a ib i + a jb k (1) i=0 j k α, β Z/mZ a jb k = (a j + α)(b k + β)+a j(b k + β)+(a j + α)b k + αβ n =3 (1) a 0b 1 P i x P i(x) P i x [x] i P 0, P 1 P 0, P 1, P 2 P 0(a 0), P 1(b 1) P 0([a 0b 1] 0), P 1([a 0b 1] 1), P 2([a 0b 1] 2) (1) P 2 α, β Z/mZ P 0, P 1 [a 0b 1] 2 := αβ (2) P 0, P 1 a 0 + α, b 1 + β P 1, P 0 (3) P 0, P 1 [a 0b 1] 0 := (a 0 + α)(b 1 + β)+a 0(b 1 + β), [a 0b 1] 1 := (a 0 + α)b 1 (1) ajb j k k P i [ab] i = a ib i + [ajb j k k] i 3. n =3 malicious semi-honest semi-honest malicious 9) a Z/mZ P i [a] i =(a i,a i+1) i ± 1 3 i =2 a i+1 = a 0 a P i [a] i Share Share P i Share 2-out-of-3 a Z/mZ P i([a] i) (1) a 0,a 1 Z/mZ (2) a 2 := a a 0 a 1 (3) i =0, 1, 2 [a] i := (a i,a i+1) P i a = a 0 + a 1 + a 2 2 [a] i a [a] i a 2-out-of-3 Dec

4 Dec 2-out-of-3 Mul a, b ab P i([a] i) a or (1) P i (α i,β i):=(a i,a i+1) (2) i =0, 1, 2 β i α i+1 β i, α i+1 (3) a = α 0 + α 1 + α Add/Sub CoMul Add/Sub a, b a ± b P i([a] i, [b] i) P i([a ± b] i) P i [a ± b] i := (a i ± b i,a i+1 ± b i+1) CoMul a c ac P i([a] i), c P i([ca] i) P i [ca] i := (ca i,ca i+1) 3.3 3) 4) Mul P i([a] i, [b] i) P i([ab] i) (1) P 0 r 1,r 2,c 0 Z/mZ c 1 := (a 0 + a 1)(b 0 + b 1) r 1 r 2 c 0 P 1, P 2 (r 1,c 1), (r 2,c 0) [ab] 0 := (c 0,c 1) (2) P 1, P 2 y := a 1b 2 + a 2b 1 + r 1, z := a 2b 0 + a 0b 2 + r 2 P 2, P 1 (3) P 1, P 2 c 2 := y + z + a 2b 2 [ab] 1 := (c 1,c 2), [ab] 2 := (c 2,c 0) c 0 + c 1 + c 2 =(a 0 + a 1)(b 0 + b 1) r 1 r 2 + y + z + a 2b 2 =(a 0 + a 1)(b 0 + b 1)+a 1b 2 + a 2b 1 + a 2b 0 + a 0b 2 + a 2b 2 =(a 0 + a 1 + a 2)(b 0 + b 1 + b 2) = ab c 0, c 1, c 2 2 Z/mZ c 0, c 1, c 2 ab 3.4 Not a {0, 1} a ā := 1 a P i([a] i) P i([ā] i) P 0 [ā] 0 := (1 a 0, a 1) P 1 [ā] 1 := ( a 1, a 2) P 2 [ā] 2 := ( a 2, 1 a 0) a, b {0, 1} a b = ab

5 a b = a + b ab a b = a + b 2ab a, b {0, 1} Add/Sub CoMul Mul x [x] :=([x] 0, [x] 1, [x] 2) And([a], [b]) := Mul([a], [b]) Or([a], [b]) := Sub(Add([a], [b]), Mul([a], [b])) Xor([a], [b]) := Sub(Add([a], [b]), CoMul(Mul([a], [b]), 2)) semi-honest P i Share Mul malicious Share Mul Share EqTest EqTest P i([a] i) true/false (1) P i α i+1 := a i+1 P i+1 (2) P i α i = a i 1 0 (3) P i 1 true false EqTest (2) P i EqTest EqTest Dec Dec Dec Mul P 1, P 2 P 1, P 2 P 0 s [a], [b] [ab] [sa], [b] [sab] P 1, P 2 [ab], [sab] s s P 0 P 1, P 2 P 1, P 2 Verif [c] Mul([a], [b]) P i([a] i, [b] i, [c] i) P 0 c = ab true/false (1) P 1, P 2 s Z/mZ (2) P 1, P 2 (Share(sa 1), Share(sa 2)), Share(sa 0) P i (d i,d i+1) :=((sa 0) i +(sa 1) i +(sa 2) i, (sa 0) i+1 +(sa 1) i+1 +(sa 2) i+1) d := sa (3) Mul([d], [b]) P i e := db = sab (e i,e i+1) (4) P 1, P 2 f := sc 1 + sc 2 e 1 e 2, g := sc 0 e 0 f + g =0 true false Verif f + g = s(c 0 + c 1 + c 2) (e 0 + e 1 + e 2)=sc sab =0 true P 1, P 2 g, f Verif 1 n =3 12) Verif m 5 m 32 12) 1,024 Verif 3

6 ) Verif a Z/mZ a =(a k 1 a 0) 2 a i a 2 (a k 1 a 0) 2 a 2 k a a i a 2 i +1 2 m 9) 2 m 9) 9) BitShare P i([b] i)or b (1) P i b i {0, 1}, b i,0,b i,1 Z/mZ b i,2 := b i b i,0 b i,1 P i+1, P i 1 (b i,0,b i,1,b i,2), (b i,i 1,b i,i) (2) P i P i 1 (b i 1,0,b i 1,1,b i 1,2) b i 1,0 + b i 1,1 + b i 1,2 {0, 1} (3) P i b j 0 j 2 [b j] i =(b j,i,b j,i+1) EqTest (4) Xor(Xor([b 0], [b 1]), [b 2]) P i [b] i BitShare b 0, b 1, b 2 b := b 0 b 1 b 2 {0, 1} 9) a = k 1 i=0 2i a i [a] =Add( Add(Add([a 0], CoMul([a 1], 2)), CoMul([a 2], 2 2 )), CoMul([a k 1 ], 2 k 1 )) perfect secrecy 27) 4.1. S S S D F s S d D Pr(S = s F (S) =d) =Pr(S = s) S F (S) 15) 16) 4.2. j n x j f j(x 1,...,x n) VIEW j(x 1,...,x n) semi-honest semi-honest S x = {x 1,...,x n}, I = {i 1,...,i I } {1,...,n} S(I, x I,f I( x )) VIEW I( x ) x I = {x i1,...,x i I }, f I =(f i1,...,f i I ), VIEW I =(VIEW i1,...,view i I ) I 2

7 I I = {i 1,...,i t} {1,...,N} semi-honest I semi-honest S x = {x 1,...,x N } S(I, x I,f I( x )) VIEW I( x ) I {1,...,n} VIEW I( x ) semi-honest I Proof. S 4.2 semi-honest Share Dec Add/Sub CoMul Mul Not And Or Xor semi-honest Share Dec Add/Sub CoMul Mul Not And Or Xor semi-honest Proof. P 0, P 1, P 2 3 VIEW VIEW VIEW Add/Sub CoMul Not VIEW Dec VIEW And Mul Or Xor Add/Sub CoMul Mul Share Mul Share Mul VIEW V σ, V μ V σ : Z/mZ [(Z/mZ) 2 ] [(Z/mZ) 2 ] [(Z/mZ) 2 ] a ((R x,r y), (R y,a R x R y), (a R x R y,r x)) V μ :(Z/mZ) 6 {Ø} [(Z/mZ) 3 ] [(Z/mZ) 3 ] (a 0,a 1,a 2,b 0,b 1,b 2) (Ø, (R 1, (a 0 + a 1)(b 0 + b 1) R 1 R 2 R 0, (a a 0 a 1)b 0 + a 0(b b 0 b 1)+R 2), (R 2,R 0,a 1(b b 0 b 1)+(a a 0 a 1)b 1 + R 1)) R x, R y, R 0, R 1, R 2 Ø Ω [ Ω ] Ω 1 P 0, P 1, P 2 VIEW VIEW 0,VIEW 1,VIEW V σ, V μ 4.1. a, a 0,a 1,a 2,b 0,b 1,b 2 Z/mZ V0 σ (a), V1 σ (a), V2 σ (a), V μ 0 (a0, a 1,a 2,b 0,b 1,b 2), V μ 1 (a0,a1,a2,b0,b1,b2), V μ 2 (a0,a1,a2,b0,b1,b2) Vi σ, V μ i V σ, V μ VIEW i Proof. R x, R y, R 0, R 1, R 2 V σ i R x, R y V μ 0 V μ i R 0, R 1, R 2 Share Mul VIEW VIEW VIEW VIEW P 0 VIEW P 0 VIEW Share a k P 0 VIEW Share VIEW (R x,1,r y,1,...,r x,k,r y,k ) R x,1,...,r y,k P 0 VIEW P 1, P 2 Share Mul VIEW

8 (1) Share P 1, P 2 a VIEW 1,VIEW 2 (2) i VIEW 1,VIEW 2 i +1 i VIEW VIEW i 1,VIEW i 2 A i R v 1, v 2 v 1(A, R) =VIEW i 1, v 2(A, R) =VIEW i 2 i +1 A R VIEW VIEW i+1 1,VIEW i+1 2 (I) i +1 a(a, R) VIEW i+1 1 =(v 1(A, R),V1 σ (a(a, R))) VIEW i+1 2 =(v 2(A, R),V2 σ (a(a, R))) (II) i +1 a 0(A, R), a 1(A, R), a 2(A, R), b 0(A, R), b 1(A, R), b 2(A, R) VIEW i+1 1 =(v 1(A, R),V μ 1 (a0(a, R),a1(A, R),a2(A, R),b0(A, R),b1(A, R),b2(A, R))) VIEW i+1 2 =(v 2(A, R),V μ 2 (a0(a, R),a1(A, R),a2(A, R),b0(A, R),b1(A, R),b2(A, R))) VIEW i+1 1 =(v 1(A, R),V1 σ (a(a, R))) 3 v Y D v d 1 D v, d 2 (Z/mZ) 2 Pr(VIEW i+1 1 =(d 1,d 2)) Pr(VIEW i+1 1 =(d 1,d 2)) = Pr((v(A, R),V1 σ (a(a, R))) = (d 1,d 2)) =Pr(v(A, R) =d 1)Pr(V1 σ (a(a, R)) = d 2 v(a, R) =d 1) = 1 D Pr(V 1 σ (a(a, R)) = d 2 (A, R) v 1 ({d 1})) v = 1 Pr(V1 σ (a(a, R)) = d 2 (A, R) =r) D v r v 1 ({d 1 }) = 1 D v = 1 m 2 D v r v 1 ({d 1 }) Pr(V σ 1 (a(r)) = d 2) Share Mul VIEW 1,VIEW Verif BitShare 4.2. m Mul P 1, P 2 P 0 P 1 P 2 Verif (m 1)/m false Proof. P 1, P 2 f + g 0 P 0 s( c 0 + c 1 + c 2) ẽ 0 +ẽ 1 +ẽ 2 (mod m) (2) c i, e j c i, ẽ j 0 i, j 2 Δc = c ( c 0 + c 1 + c 2), Δe = sc (ẽ 0 +ẽ 1 +ẽ 2) (2) s(c Δc) sc Δe (mod m) sδc Δe (mod m) (3) m Δc mod m =0 Δe mod m =0 Δc, Δe 0 Δc mod m 0 P 0 s Δe (3) 1/m Δe mod m m P 0, P 1, P 2 2 BitShare EqTest Xor BitShare P i (m 1)/m 0 1 Proof. P 1, P 2 BitShare EqTest Xor BitShare BitShare (1) P 0 P 1 P 2 (b 0,0,b 0,1,b 0,2), (b 0,2,b 0,0) (2) (3) b 0 := b 0,0 + b 0,1 + b 0,2 {0, 1}, b 0,0 = b 0,0, b 0,2 = b 0,2 (3) j =0 P i [b 0] i =(b j,i,b j,i+1)

9 j =1, 2 P 1, P 2 P i b j = b j,0 + b j,1 + b j,2 {0, 1} [b j] i =(b j,i,b j,i+1) BitShare (4) Xor 4.2 (m 1)/m b 0 b 1 b 2 b 0,b 1,b 2 {0, 1} BitShare P i (m 1)/m Share Dec Add/Sub CoMul = m 2 Mul Verif m 32 m = 4,294,967,291 3 n n Mul Verif 6 m 22 m 1 28 m 1 Table 1 Test environment. PC 1 CPU Intel Core2 Quad 3.0 GHz RAM 4GB OS Debian C++ g m n = 1,000, , FTTH Fiber To The Home FWA P-P Fixed Wireless Access Point to Point 6. 3 semi-honest malicious Table 2 2 Mul Verif Running time of three-party secure multiplication with error detection (Mul and Verif). n 1, , , ,000, Fig. 1 1 System configuration consisting of two data holders and a third party.

10 Fig. 2 2 System configuration consisting of two data holders and an analyst ) 1) Horizontally Partitioned Data Vertically Partitioned Data EM K-NN Fig. 3 3 System configuration consisting of three data holders semi-honest malicious 3 n =3 PC μ 4 Fig. 4 System configuration consisting of many data holders and three third parties ) Aggarwal, C.C. and Yu, P.S.: Privacy-Preserving Data Mining: Models and Algorithms, ISBN , Springer-Verlag (July 2009). 2) Algesheimer, J., Camenisch, J. and Shoup, V.: Efficient computation modulo a shared secret with application to the generation of shared safe-prime products, CRYPTO 2002, LNCS 2442, pp , Springer-Verlag (2002). 3) Ben-Or, M., Goldwasser, S. and Wigderson, A.: Completeness theorems for noncryptographic fault-tolerant distributed computation, STOC 88, pp.1 10, ACM

11 Press (1988). 4) Bogdanov, D., Laur, S. and Willemson, J.: Sharemind: A framework for fast privacy-preserving computations, ESORICS 2008, LNCS 5283, pp (2008). 5) Chaum, D., Crepeau, C. and Damgård, I.: Multiparty unconditionally secure protocols, STOC 88, pp.11 19, ACM Press (1988). 6) 3 CSS2010 (2010). 7) 3 48 CSEC (2010). 8) Cramer, R., Damgård, I. and Nielsen, J.B.: Multiparty computation from threshold homomorphic encryption, EUROCRYPT 2001, LNCS 2045, pp , Springer- Verlag (2001). 9) Damgård, I., Fitzi, M., Kiltz, E., Nielsen, J.B. and Toft, T.: Unconditionally secure constant-rounds multi-party computation for equality, comparison bits and exponentiation, TCC 2006, LNCS 3876, pp , Springer-Verlag (2006). 10) Electronic Health Information Laboratory KnowledgeBase, available from (accessed ). 11) FairplayMP, available from fairplaymp.html (accessed ). 12) Feldman, P.: A practical scheme for non-interactive verifiable secret sharing, FOCS 87, pp , IEEE Press (1987). 13) Gentry, C.: Fully homomorphic encryption using ideal lattices, STOC 09, pp , ACM Press (2009). 14) Geographic Privacy-aware Knowledge Discovery and Delivery, available from (accessed ). 15) Goldreich, O.: Secure Multi-Party Computation (Final (incomplete) Draft, Version 1.4), Working Draft, June 1998, revised October 27 (2002). 16) Goldreich, O.: Foundations of Cryptography, Vol.2, Cambridge University Press (2004). 17) Goldreich, O., Micali, S. and Wigderson, A.: How to play any mental game, or a completeness theorem for protocols with honest majority, STOC 87, pp , ACM Press (1987). 18) 3 50 CSEC (2010). 19) Jakobsson, M. and Juels, A.: Mix and match: Secure function evaluation via ciphertexts, ASIACRYPT 2000, LNCS 1976, pp , Springer-Verlag (2000). 20) Lindell, Y. and Pinkas, B.: Privacy preserving data mining, CRYPTO 2000, LNCS 1880, pp.36 54, Springer-Verlag (2000). 21) Nishide, T. and Ohta, K.: Multiparty computation for interval, equality, and comparison without bit-decomposition protocol, PKC 2007, LNCS 4450, pp , Springer-Verlag (2007). 22) Pinkas, B., Schneider, T., Smart, N.P. and Williams, S.C.: Secure two-party computation is practical, ASIACRYPT 2009, LNCS 5912, pp , Springer-Verlag (2009). 23) Schoenmakers, B. and Tuyls, P.: Practical two-party computation based on the conditional gate, ASIACRYPT 2004, LNCS 3329, pp , Springer-Verlag (2004). 24) Schoenmakers, B. and Tuyls, P.: Efficient binary conversion for Paillier encrypted values, EUROCRYPT 2006, LNCS 4004, pp , Springer-Verlag (2006). 25) SecureSCM Project, available from (accessed ). 26) Shamir, A.: How to share a secret, Comm. ACM, Vol.22, No.22, pp (1979). 27) Shannon, C.E.: Communication theory of secrecy system, ACM Trans. Knowledge Discovery from Data, Vol.28, No.4, pp (1949). 28) Sharemind, available from (accessed ). 29) 2 CSS2009 (2009). 30) Vaidya, J., Clifton, C.W. and Zhu, Y.M.: Privacy Preserving Data Mining, ISBN , Springer-Verlag (Nov. 2005). 31) VIFF, the Virtual Ideal Functionality Framework, available from 32) Yao, A.C.: Protocols for secure computations, FOCS 82, pp , IEEE Press (1982). 33) Yao, A.C.: How to generate and exchange secrets, FOCS 86, pp , IEEE Press (1986). 34) ) policy/ daikoukai/igvp/index/ )G METI/ html ) idc idc TM Inter idc ( ), cloud.html

12 ) 2010 ( ), ) S.T.E.P ( ), release/1371/ stepbunsansutore-jisa-bisuteikyoukaishi%282%29.pdf ( ) ( ) 12 NTT 13 SCIS NTT NTT

[I486S] 暗号プロトコル理論

[I486S] 暗号プロトコル理論 [I486S] 2018 5 1 (JAIST) 2018 5 1 1 / 22 : I486S I URL:https://wwwjaistacjp/~fujisaki/i486S (Tuesdays) 5 17:10 18:50 4/17, 4/24, 5/1, 5/15, 5/22, 5/29, 6/5, 6/19, 6/26, 7/3, 7/10, 7/17, 7/24, 7/31 (JAIST)