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

Size: px

Start display at page:

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

いとはかんざとばる
7 years ago
Views:

1 [I486S] (JAIST) / 22

2 : I486S I URL: (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) / 22

3 R Cramer, I Damgaard, and J Nielsen: Secure Multiparty Computation and Secret Sharing, Cambridge University Press (ISBN ) R Cramer, I Damgaard, J Nielsen: Multiparty computation, Introduction Ben-Or, S Goldwasser and A Wigderson: Completeness Theorems for Non-Cyptographic Fault-Tolerant Distributed Computation, in STOC88, pp 1 10 R Cramer, I Damgaard and U Maurer: General Secure Multi-party Computation from any Linear Secret-Sharing Scheme, in EUROCRYPT2000, pp R Cramer, I Damgaard and Y Ishai: Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation, in TCC2005, pp A Yao: Protocols for secure computations, in FOCS82, pp Y Lindell and B Pinkas: A Proof of Security of Yao s Protocol for Two-Party Computation, Journal of Cryptology, volume 22(2), pp , 2009 (JAIST) / 22

4 1 Shamir 2 Reed-Solomon 3 Shamir SS 4 (JAIST) / 22

5 Shamir (Shamir SS) Shamir SS = (Share, Recon, Γ t+1,n ) Share(s): a 0 := s K t f (X ) = t i=0 a ix i f (X ) R K[X ] such that deg(f ) = t, and a 0 = s [s] = (f (α 1 ),, f (α n )) α i K Recon(S Q ) (S Q = {f (α i ) i Q st Q Γ t+1,n }): s s = λ i,q f (α i ) where λ i,q = ( αj ) α j α i i Q j Q\{i} Reconstruction vector (λ 1,Q,, λ #Q,Q ) S Q (α 1,, α n) (JAIST) / 22

6 Shamir f, g K[X ] (deg(f ), deg(g) t) [αf (0) + βg(0)] = α[f (0)] + β[g(0)] where α, β K f (X ) = a 0 + a 1 X + a t X t g(x ) = b 0 + b 1 X + b t X t h(x ) αf (X ) + βg(x ) deg(h) t [h(0)] = (h(α 1 ),, h(α n )) = (αf (α 1 ) + βg(α 1 ),, αf (α n ) + βg(α n )) = α[f (0)] + β[g(0)] (JAIST) / 22

7 1 Shamir 2 Reed-Solomon 3 Shamir SS 4 (JAIST) / 22

8 Reed-Solomon (n, t + 1)- n t + 1 K = F q q α 1,, α n K (α i α j for i j) Reed-Solomon (RS) f K[X ], deg(f ) t (f (α 1 ),, f (α n )) (n, t + 1)-Reed-Solomon ie, C RS = {(f (α 1 ),, f (α n )) f K[X ] st deg(f ) t} (n, t + 1)-RS (n, t + 1)- (JAIST) / 22

9 C c, c C, a, b K = ac + bc C c, c τ e, e c + e c + e τ (τ-error correcting) d τ < d 2 v K n : w H (v) # of {v i 0 for v = (v 1,, v n)} v w : d H (v, w) w H (v w) : d = min{d H (c, c ) c, c C st c c } (JAIST) / 22

10 RS- Theorem 1 (n, t + 1)-Reed-Solomon n t (n, t + 1)- τ < n t 2 τ Proof RS f = (f (α 1 ),, f (α n)) f C RS f (x) = 0 t deg(f ) t t + 1 f 0 f (x) = 0 t w H (f ) n t d = n t w H (e) < n t e e C RS c, c C RS, e, e (w H (e), w H (e ) < n t) = c + e c + e (JAIST) / 22

11 RS- f = (f (α 1),, f (α n)) where deg(f ) t and n 3t + 1 ˆf = (y 1,, y n) = f + e where W H (e) t Goal: ˆf f Welch/Berlekamp Algorithm Q(X, Y ) f 0 (X ) f 1 (X )Y Q(α i, y i ) = 0 for i = 1,, n deg(f 0 ) 2t and deg(f 1 ) t f 1 (0) = 1 f 0 (X ), f 1 (X ) f (X ) = f 0(X ) f 1 (X ) W H (e) t n 3t + 1 f 0, f 1 f (X ) = f 0(X ) f 1 (X ) (JAIST) / 22

12 RS- 15 f 0, f 1 y i = f (α i ) + e i e i 0 t f 0, f 1 B = {i e i 0} #B t i B k(x ) = (X α i) i B ( α i) f 0 (X ) = k(x )f (X ), f 1 (X ) = k(x ) f 1 (0) = 1, deg(f 0 ) 2t, deg(f 1 ) t i = 1,, n ) Q(α i, y i ) = f 0 (α i ) f 1 (α i )y i = k(α i ) (f (α i ) y i = 0 f 0, f 1 (JAIST) / 22

13 RS- f 0(X ) = a 0 + a 1X + + a 2tX 2t f 1(X ) = 1 + b 1X + + b tx t Q(α i, y i ) = f 0(α i ) f 1(α i )y i = 0 for i = 1,, n 3t = 1 α 1 α 2t 1 y 1 y 1 α 1 y 1 α t 1 1 α n α 2t n y 1 y n α n y n α t n a 0 a 2t 1 b 1 b t (JAIST) / 22

14 RS- ˆQ(X ) = Q(X, f (X )) deg( ˆQ) 2t W H (e) t y i = f (α i ) n t n t (α i ) ˆQ(α i ) = 0 n 3t + 1 deg( ˆQ) 2t < n t deg( ˆQ) 0 f 0 (X ) f 1 (X )f (X ) 0 f (X ) = f 0(X ) f 1 (X ) (JAIST) / 22

15 1 Shamir 2 Reed-Solomon 3 Shamir SS 4 (JAIST) / 22

16 Shamir SS [a], [b]: a, b K P 1,, P n addition [a] + [b] = [a + b] f, g a, b t f 0 = a, g 0 = b f (X ) = f 0 + f 1 X + + f t X t, and g(x ) = g 0 + g 1 X + + g t X t h(x ) = f (X ) + g(x ) h(0) = a + b deg(h) = t [a + b] = (h(α 1 ),, h(α n )) h(α i ) = f (α i ) + g(α i ) P i [a + b] (JAIST) / 22

17 Shamir SS [a] t, [b] t: a, b K P 1,, P n (t + 1, n) multiplication [a] t [b] t = [ab] 2t [a] [b] P i [a] t t + 1 a f, g a, b t f 0 = a, g 0 = b f (X ) = f 0 + f 1X + + f tx t, and g(x ) = g 0 + g 1X + + g tx t h(x ) = f (X )g(x ) h(0) = ab deg(h) = 2t [ab] 2t = (f (α 1)g(α 1),, f (α n)g(α n)) P 1,, P n ab 2t + 1 ab (JAIST) / 22

18 Shamir SS multiplication Lagrange n [ab] = [h(0)] = [ λ i,n h(α i )] = i=1 n λ i,n [h(α i )] i=1 (λ 1,n,, λ n,n) {α 1,, α n} h(x ) = f (X )g(x ) h(α i ) = f (α i )g(α i ) [a], [b] [ab] P i f (α i )g(α i ) (t + 1, n)- [f (α i )g(α i )] [ab] (JAIST) / 22

19 Shamir SS Input: [a], [b] Output: [ab] [a], [b] a, b P 1,,, P n P i c i = a i b i P i c i P 1,, P n [c 1 ],, [c n ] P i c 1,i,, c i,i,, c n,i [c 1 ],, [c n ] i = 1,, n λ i,n = j i α i α j α i P i d i = j=1 λ j,nc j,i [ab] = (d 1,, d n ) [ab] (JAIST) / 22

20 1 Shamir 2 Reed-Solomon 3 Shamir SS 4 (JAIST) / 22

21 (Secret Sharing) SS = (Share, Recon, Γ t+1,n) Share s K K n share [s] (s 1,, s n) Share : s K [s] = (s 1,, s n) K n Γ t+1,n {Q {1,, n} #Q t + 1} Recon [s] t S Q = {s i i Q} Q Γ t+1,n s SS = (Share, Recon, Γ t+1,n) (Perfect Reconstructability) s K, [s] Share(s), Q Γ t+1,n S Q Recon(S Q ) = s (Perfect Privacy) s K, [s] Share(s), T Γ t+1,n S T H(s) = H(s S T ) s S T (JAIST) / 22

22 (Linear Secret Sharing) SS = (Share, Recon, Γ t+1,n ) Linearlity SS (Linearlity) s, s, a, b K, [s] Share(s), [s ] Share(s ) [as + bs ] = a[s] + b[s ] a[s] (a s 1,, a s n ), [s] + [s ] (s 1 + s 1,, s n + s n) P 1,, P n s, s [s],[s ] P i as i + bs i a, b (as 1 + bs 1,, as n + bs n) as + bs [a s + b s ] (JAIST) / 22