4b_12.dvi

Size: px

Start display at page:

Download "4b_12.dvi"

れいなみやのじょう
5 years ago
Views:

1 Analysis of Answering Method with Probability Conversion for Internet Research Atsushi TAGAMI, Chikara SASAKI, Teruyuki HASEGAWA, Shigehiro ANO, and Yoichi TOMIURA /. [] IPTV Securecy Anonymity 2 SSL KDDI KDDI R&D Laboratories Inc., Fujimino-shi, Japan Kyushu University, Fukuoka-shi, Japan [2], [3] RR Randomized response thechniques [4] [5], [6] x {0, } v x 0 B Vol. J92 B No. 4 pp c

2 2009/4 Vol. J92 B No x v Electronic Voting Scheme Homomorphism [2] MIX-net [3] Item Count [7] RR Randomized Response Thecnique [4] q yes/no q yes/no yes yes no 3. RR [8] PRAM Post RAndomization Method [9], [0] RR RR r

3 0/ Fig. 0/-answer function. x ( {0, }) v x v x v x x v V 0 V f 0(v) V v V f (v) V v f 0(v) 0 f (v) 0 0 σ 2 E[V ; f 0( )] = 0 () E[V ; f ( )] = (2) Var[V ; f 0( )]=Var[V ; f ( )] = σ 2 (3) 0/ V n V n = V i (4) n i n V i i V i V j (i j) m m m + n 0 ( V n = m ) n V i + V i (5) n i= i=m+ m/n = r n () (2) m P n P V i, V i 0 (6) m n m i= i=m+ P P V n n {m +(n m) 0} = m n (7) V n m/n r n r V n 3. 2 σ 2 0/ () (2) (3) m Vi i= N(m, m σ 2 ) n Vi i=m+ N(0, (n m) σ 2 ) N(μ, σ 2 ) μ σ 2 V n ( N n (m +0), ( m σ 2 +(n m) σ 2)) n 2 ( ) N r, σ2 n (8) Z z α/2 P ( z α/2 X z α/2 )= α (9) z α/2 V n r σ2 /n z α/2 (0) r 00 ( α)% ] σ [V n 2 zα/2 n, V n + z σ 2 α/2 n () 73

4 2009/4 Vol. J92 B No. 4 (m/n) ±δ σ 2 ( ) 2 σ 2 δ = n (2) z α/2 (2) σ 2 V n 00 ( α)% ±δ / σ 2 (2) 0/ v v v x v x v V = v x (Bayes decision rule) x =arg max f X V (x v) x {0,} =arg max x {0,} f X(x)f V X (v x) (3) f X V (x v) V = v X = x f V X (v x) X = x V = v f V X (v 0) = f 0(v) f V X (v ) = f (v) f X(x) X D 0 D D e D 0 = {v V f X(0)f 0(v) >f X()f (v)} D = {v V f X(0)f 0(v) <f X()f (v)} (4) D e = {v V f X(0)f 0(v) =f X()f (v)} V = {v R f V (v) > 0)} V V V (3) x v D 0 0 v D v D e ξ (0 ξ ) V = v Error(v) Error(v) f X() f (v) f V (v) = f X(0) f 0(v) f V (v) fx(0) f0(v) ξ f V (v) fx() f(v) +( ξ) f V (v) : v D 0 : v D : v D e f V (v) =f X() f (v)+f X(0) f 0(v). (5) f X() f X(0) = f X() = 0.5 v x Error(v) = 2 min (f0(v),f(v)) f V (v) (6) f X() 6. 3 Anonymity E[Error(V )] V Anonymity =E[Error(V )] = min(f 0(v),f (v)) f V (v) 2 f V (v) v { } = f (v)+ f 0(v)+ f 0(v) (7) 2 v D 0 v D v D e V Anonymity =E[Error(V )] 732

5 = min(f 0(v),f (v)) f V (v) dv 2 f V (v) [ = ] f (v)dv + f 0(v)dv + f 0(v)dv 2 D 0 D D e (8) 4. 2 () (2) (3) 0/ 0/ { f 0(v) : N(0,σ 2 ) f (v) : N(,σ 2 ) 0/ q : v = a f 0(v) = q : v = b q : v = a f (v) = q : v = b 0 <q<0.5 2 f 0 f () (2) a b a = q 2q, b = q 2q f 0 f σ 2 q 0 <q<0.5 q( q) ( 2q) 2 = σ2 (9) RR yes/no a/b RR 0/ (8) 0/ Anonymity = 0.5 f 0(v)dv (20) (7) 0/ 2 Fig. 2 Error probability variance. Anonymity = q (2) n =0,000 α =0.05 δ =0.0 0/ σ 2 z 0.05/2.96 (2) σ / (20) 0.6 0/ (9) (2) 0.5 0/ 0/ (7) (8) v 2 0/ (6) v v = v =0 f(y) f(y) = { p : y =0 p : y = f(y) = { p : y = a p : y = b 2 a b 2q = q 0 f 0 q = q 0 f 0 f 733

6 2009/4 Vol. J92 B No. 4 x σ 2 0/ Error(v) v 0/ 0/ f R D = {y R f(y) > 0} E f [Y k ; D] E f [Y k ; D] = y k f(y) y D E f [; D] = y D f(y) f E f [Y k ; D] D R E f [Y k ; D] = y k f(y) dy D E f [; D] = f(y) dy D f R D R E f [; D] =S<, E f [Y 2 ; D] < a E f [Y ; D] =as, E f [Y 2 ; D] a 2 S {y R f(y) > 0} = {a} Jensen [] 5. 2 σ 2 0/ Error(v) ( > 0) v V Error(v) = (22) 0/ (f 0,f ) m : v = m 2 m f 0(v) = m : v = m 2 m f (v) =f 0( v) m = σ 2 (23) m (5) (6) f X() = f X(0) = 0.5 Error(v) Error(v) = min(f0(v),f(v)) f 0(v)+f (v) (24) f X() = f X(0) = 0.5 D 0 = {v V f 0(v) >f (v)}, D = {v V f 0(v) <f (v)}, D e = {v V f 0(v) =f (v)} (24) v D 0 (,f 0(v) >f (v)) f (v) Error(v) = f < 0(v)+f (v) 2, v D (,f 0(v) <f (v)) f 0(v) Error(v) = f < 0(v)+f (v) 2, (25) v D e (,f 0(v) =f (v)) Error(v) = 2 v D e v D 0 D Error(v) (22) E f [; D e]=e f0 [; D e]=0 E f [; D e]=e f0 [; D e]= v V f 0(v) =f (v) 0/ () (2) (25) v D 0 Error(v) 734

7 f (v) = f0(v) (22) f X() = f X(0) = <<0.5 f (v) = f0(v) : v D0, f 0(v) = (26) f(v) : v D E f0 [; D e]=e f [; D e]=0 (27) (26) E f [V k ; D 0]= E f 0 [V k ; D 0] (28) E f0 [V k ; D ]= E f [V k ; D ] (29) f 0 =E f0 [; D 0]+E f0 [; D ]+E f0 [; D e] (27) (29) =E f0 [; D 0]+ E f [; D ] f (27) (28) = E f 0 [; D 0]+E f [; D ] E f0 [; D 0]=E f [; D ]= (30) 5. 2 {E f [; D 0]+E f0 [; D ]+E f0 [; D e]} (27) (28) (29) (30) Anonimity = 2 {E f 0 [; D 0]+E f [; D ]} = f 0 () (3) 0=E f0 [V ; D 0]+E f0 [V ; D ]+E f0 [V ; D e], σ 2 =E f0 [V 2 ; D 0]+E f0 [V 2 ; D ]+E f0 [V 2 ; D e] (27) (29) 0=E f0 [V ; D 0]+ E f [V ; D ], (3) σ 2 =E f0 [V 2 ; D 0]+ E f [V 2 ; D ] (32) (3) (32) (30) a 0 a 0=a 0()+a (33) σ 2 a 2 0 ()+a 2 (34) f (2) (3) =a 0 + a () (35) σ 2 + a a 2 () (36) (33) (35) a 0 a a 0 = 2, a = 2 (37) (34) (36) 2 ( 2) 2 σ 2 </ σ 2 m m = 2 2 (38) +4σ 2 (34) (36) / 735

8 2009/4 Vol. J92 B No σ 2 v Error(v) (39) 0/ σ 2 0/ (f 0,f ) L : v =/2 Δ M : v =/2 f 0(v) = L /() : v =/2+Δ f (v) =f 0( v) L = ( + 4σ 2 )( 2) 2, M = ( + 4σ 2 )( 2) 2, Δ= 2 ( + 4σ2 )( 2) ( Anonymity = 2σ 2 ) (40) +4σ 2 2 f X() = f X(0) = 0.5 /2 (39) 0/ 0 <</2 (39) f (v) f0(v) : v D0 (4) f 0(v) f(v) : v D (42) 2 f(v) f0(v) :v D0 2 g(v) = f 0(v) : v D e 2 f0(v) f(v) :v D 2 h(v) = (f0(v) f(v)) : v D0 2 0 : v D e (f(v) f0(v)) : v D 2 g h f 0 f h(v)+g(v) : v D 0 f 0(v) = g(v) : v D e (43) h(v)+g(v) : v D h(v)+g(v) : v D0 f (v) = g(v) : v D e (44) h(v)+g(v) : v D E f0 [V k ; D e]=e g[v k ; D e], E f0 [V k ; D ]= E h[v k ; D ]+E g[v k ; D ] g h (4) (42) </2 v g(v) 0, v (D 0 D ) h(v) > 0, v D e h(v) =0, (45) f 0 f (43) (44) E h [; D 0]+ E h[; D ]+E g[; V] =, E h[; D 0]+E h [; D ]+E g[; V] = E h [; D 0]=E h [; D ] L + M = (46) E h [; D 0]=E h [; D ]=L, E g[; V] =M (47) A =2 Anonimity (43) 736

9 (44) (47) A =E f [; D 0]+E f0 [; D ]+E f0 [; D e] = {E h[; D 0]+E h [; D ]} +E g[; D 0]+E g[; D ]+E g[; D e] = 2 L + M (48) (46) (48) L M L = ()( A) 2 M = A 2 2 f 0 () (3) (49) 0=E f0 [V ; D 0]+E f0 [V ; D ]+E f0 [V ; D e], σ 2 =E f0 [V 2 ; D 0]+E f0 [V 2 ; D ]+E f0 [V 2 ; D e] (43) (44) 0=E h [V ; D 0]+ E h[v ; D ]+E g[v ; V], σ 2 =E h [V 2 ; D 0]+ E h[v 2 ; D ]+E g[v 2 ; V] (45) g h D 0 D D e (47) a 0 a a e 0=a 0L + al + aem (50) σ 2 a 2 0 L + a2 L + a 2 e M (5) f (2) (3) = a0l + al + aem (52) σ 2 + a02 L + a 2 L + a 2 e M (53) (50) (52) (49) a 0 a a 0 = A 2 A ae (54) A a = A 2 A ae + (55) A (54) (55) (5) A ( σ 2 +2a 2 a e2 + σ 2 e ) () 2 (56) A 0(a e) (54) (55) (53) A ( a e) 2 + σ 2 ( σ 2 +2( a e) 2 ) () 2 (57) A (a e) A max a e min(a 0(a e),a (a e)) (45) M L M 0 L >0 (49) 2 A< (56) (57) A 0(a e) < A (a e) < A 0(a e) 2, A (a e) 2 2 ( 2) 2 σ 2 0 <</ σ 2 A 0(a e) A (a e) a e A 0(a e) A (a e) max a e min(a 0(a e),a (a e)) = A 0(/2) ( = 4σ 2 2 ) +4σ 2 2 (58) (58) A m A = A m a e =/2 (49) (54) (55) L = ( + 4σ 2 )( 2) 2 737

10 2009/4 Vol. J92 B No. 4 M = ( + 4σ 2 )( 2) 2 a 0 = 2 2 ( + 4σ2 )( 2) a = ( + 4σ2 )( 2) A = A m g h (5) (53) a 0 D 0 a D a e =/2 D e { g(v) = M : v =/2, L : v = a 0, h(v) = L : v = a, (43) (44) / 95% α =0.05 δ =0.0, 0.05 (2) (23) 0.4 δ =0.05 0, Error(v) 4 Anonymity (2) (40) n =0 4, , 0 5, % α =0.05 δ =0.0, / 0/ (40) 4 Error(v) v x f X(0) = f X() = 0.5 x x Fig. 3 3 Anonymity v.s. number of sample. 4 Fig. 4 Anonymity v.s. lower bound of error(v). 738

11 v x min(f X(0),f X()) x = 0. v v v v 5. () (2) (3) 0/ 3 σ 2 0/ Error(v) ( > 0) v V Error(v) = p = f X() 0/ (f 0,f ) ()(p 0 ) : v = p ( 2)p 0 p 0 f 0(v) = (p ) ()p : v = ( 2)p 0 p 0 : otherwise (p 0 ) : v = p ( 2)p p 0 f (v) = ()(p ) ()p : v = ( 2)p p 0 : otherwise p 0 = p = 2 p( p)σ2 4 σ 2 + p 2 p =max(p,p 0). 5 Fig. 5 With known prior probability. 2 p( p)σ2 (59) 4 σ 2 + p 2 5 (59) 95% α =0.05 δ =0.0 f X() = 0.3, 0.4 min(f X(0),f X()) 0/ (3) 7. 0/ 0/ σ 2 0/ 0/ 739

2009/4 Vol. J92 B No. 4 n 0 4 n =0 4 40% 95% ±0.05 [] Everybody Votes Channel, http://www.nintendo.com/customer/wii/en na/ channelseverybodyvotes.jsp [2] P.

Sako, An efficient scheme for proving shuffle, Crypto 200, pp.368 387, California, Aug. 200. [4] S.L. Warner, Randomized response: A survey technique for eliminating evasive answer bias, J.

Tomiura, Analysis of answering method with probability conversion for Internet research, Fifth Annual IEEE Consumer Communications & Networking Conference, NV, Jan. 2008. [6] A. Tagami, C. Sasaki, T.

12 2009/4 Vol. J92 B No. 4 n 0 4 n =0 4 40% 95% ±0.05 [] Everybody Votes Channel, na/ channelseverybodyvotes.jsp [2] P. Paillier, Public-key cryptosystems based on composite degree residuosity classes, Proc. EUROCRYPT 99, pp , Czech Republic, May 999. [3] J. Furukawa and K. Sako, An efficient scheme for proving shuffle, Crypto 200, pp , California, Aug [4] S.L. Warner, Randomized response: A survey technique for eliminating evasive answer bias, J. American Statistical Association, vol.60, no.309, pp.63 69, March 965. [5] A. Tagami, C. Sasaki, T. Hasegawa, S. Ano, and Y. Tomiura, Analysis of answering method with probability conversion for Internet research, Fifth Annual IEEE Consumer Communications & Networking Conference, NV, Jan [6] A. Tagami, C. Sasaki, T. Hasegawa, S. Ano, and Y. Tomiura, Optimization of the answering method with probability conversion, Workshop on Heuristic Methods for the Design, Deployment, and Reliability of Network and Network Applications, Finland, July [7] J. Droitcour, R. Caspor, M. Hubbard, T. Parsley, W. Vissher, and T. Ezzati, The item count technique as a method of indirect questioning: A review of its development and a case study application, in Measurement Errors in Surveys, pp.85 20, John Wiley & Sons, New York, 99. [8] W. Du and Z. Zhan, Using randomized response techniques for privacy-preserving data mining, 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp , Washington DC, Aug [9] P.L. Kooiman, L. Willenborg, and J. Gouweleeuw, PRAM: A method for disclosure limitation of microdata, Technical Report, Statistics Netherlands, 997. [0] J. Gouweleeuw, P. Kooiman, Willenborg, and P. Wolf, Post randomization for statistical disclosure control: Theory and implementation, J. Official Statistics, vol.4, pp , 998. [] KDD KDDI IP 6 KDDI QoS KDDI IP 5 KDD KDDI IP 5 KDDATM IP KDDI IP Pacling2005 Best Paper Award FIT

9_18.dvi

9_18.dvi Vol. 49 No. 9 3180 3190 (Sep. 2008) 1, 2 3 1 1 1, 2 4 5 6 1 MRC 1 23 MRC Development and Applications of Multiple Risk Communicator Ryoichi Sasaki, 1, 2 Yuu Hidaka, 3 Takashi Moriya, 1 Katsuhiro Taniyama,