2 (NTT ) ( )

Size: px
Start display at page:

Download "2 (NTT ) ( ) 2008 3"

Transcription

1 No

2 2 (NTT ) ( )

3 NTT i

4 (Semantic Security ) (Indistinguishability ) (Non Malleability ) (Non Malleability ) RSA-OAEP Diffie-Hellman ElGamal Cramer-Shoup Cramer-Shoup Cramer-Shoup ii

5 / (Universal Composability: UC) Ephemeral Diffie-Hellman Static Diffie-Hellman Blake-Johnson-Menezes DH MQV Canetti-Krawczyk Security model session HMQV Extended Canetti-Krawczyk security model CMQV iii

6 (Universal Composability) 1

7 RSA : RSA RSA n = pq (p, q : ) p, q (G, E, D) G : - 1 n n (e, d) 1 n G (e, d) E : - M e C (M, e) E C D : - C d M (C, d) D M n n = bit G

8 - : 2 (OW:One Wayness) - C M (IND:Indistinguishability) - C - (NM:Non Malleability) - M C = E(m) R R(M, M ) C = E(M ). C, C M, M R : A B 1 A 1000 m = 1000 c = E(m) B A c 1000 c m = 1001 c = E(m ) A 1 m m (CPA:Chosen Plaintext Attack) C C M m c D 3

9 - (CCA:Chosen Ciphertext Attack) C C C ( C {c 1,..., c n }) (c 1,..., c n ) (m 1,..., m n ) D C CCA CCA1 C CCA CCA2 2 CCA SSL OW IND NM CPA OW-CPA IND-CPA NM-CPA \ \ CCA1 OW-CCA1 IND-CCA1 NM-CCA1 \ \ CCA2 OW-CCA2 IND-CCA2 NM-CCA2 1: 9 OW-CPA NM- CCA2 OW<IND<NM CPA<CCA1<CCA2 IND-CCA2 NM- CCA2 IND-CCA2 4

10 1976 :Diffie,Hellman (Diffie-Hellman ) [11] 1978 :Rivest,Shamir,Adleman (RSA ) [27] 1979 :Rabin (OW-CPA) [25] 1982 :Goldwasser,Micali (IND-CPA) [15] 1990 :Naor,Yung (IND-CCA1) [24] 1990 :Rackoff,Simons (IND-CCA2) [26] 1992 :Dolev,Dwork,Naor (NM-CCA) [10] 1998 :Bellare,Desai,Pointcheval,Rogaway (IND-CCA2=NM-CCA2 ) [1] (Semantic Security ) A B f, h {X n } n N (Semantic Security) Pr[A(pk, E pk (X n ), h(x n )) = f(x n )] < Pr[B(pk, h(x n )) = f(x n )] + ɛ(n) pk, E pk (X n ) X n pk, h(x n ), f(x n ) X n, n, ɛ (negligible) ( c, N, n > N, ɛ(n) < 1 n ) B A c f, h f 1bit, h 1bit bit 1bit (Indistinguishability ) 2 m 0, m 1 2 uniform Indistinguishability 5

11 pk b m 0, m 1 E C b {0, 1} C E pk (m b ) Pr[b = b ] < ɛ(n) 1: Indistinguishability (semantically secure) h(x n ) f(x n ) h(x n ) f(x n ) - (indistinguishability) - (Semantic Security) (Indistinguishability) Indistinguishability 2 Indistinguishability : GM(Goldwasser-Micali) [15] : n = pq, a Z n : p, q a QNR n : a b 2 a (mod n) b ) Jacobi = 1 ( a n 6

12 1bit m {0, 1} Z n uniform r (r U Z n ) c = r 2 a m m = 0 c = r 2 m = 1 c = r 2 a c p, q c p := c mod p c q := ( cp ) ( cp ) c mod q p = 1 m = 0 p = 1 m = 1 GM Z n IND-CPA n, a 0, 1 E C = r 2 a b b R {0, 1} b Indistinguishability GM bit bit GM IND-CPA GM c = r 2 a b c a bit NM (Non Malleability ) Non Malleability(NM) 2 1 Dolev,Dwork,Naor 1992 [?] c 1 R R(D(c 1 ), D(c 2 )) c 2 Pr[A(c 1 ) (R, c 2 ) R(D(c 1 ), D(c 2 ))] Pr[A(c 1 ) (R, c 2 ) R(m, D(c 2 ))] < 1 k c m c 1 c 2 c 2 c 2 7

13 3.3.5 (Non Malleability ) 1 NM Bellare,Sahai 1999 [6] Indistinguishability 2 E D pk m 0, m 1 C E b {0, 1} C E pk (m b ) c 1,..., c n D(c 1 ),..., D(c n ) D b Pr[b = b ] < ɛ(n) 2: Non Malleability NM 1 (c 1,..., c n n ) CCA (BDPR 98) - (BS 99) - Bellare,Sahai 8

14 IND NM (1 ) CCA2 IND NM IND-CCA2 NM-CCA2 Bellare,Desai,Pointcheval,Rogaway (IND-CCA2) (G, S, V ) G : - 1 n (pk, sk) 1 n G (pk, sk) S : - m sk σ (m, sk) S σ V : - σ pk 1 or 0 / (σ, pk) V 1 or

15 (EUF:Existentially Unforgeable) - (CMA:Chosen Message Attack) - 3 EUF-CMA EUF-CMA [16] pk m i ) σ i = S sk (m i ) (m, σ) Pr[(m, σ) : valid] < ɛ(n) 3: EUF-CMA RSA-OAEP RSA-OAEP RSA-OAEP 1994 Bellare,Rogaway random oracle model RSA NM-CCA2 [5] [13] RSA- OAEP 10

16 m r G(r) G s H(S) H s RSA C = (s t) e mod n t 4: RSA-OAEP RSA-OAEP m 0 k 1. k r G G(r) (G(r) 0 ) 2. 0 G(r) s 3. H s H(s) 4. r H(s) t 5. s t RSA C (DES 2 feistel ) 1. RSA s t 2. H s H(s) 3. H(s) t r 4. G r G(r) 11

17 5. G(r) s 0 parity check) m reject -RSA-OAEP G, H SHA-1,SHA-2,SHA- 3 RSA-OAEP random oracle model RSA- IND-CCA2 [13] -Random oracle model random oracle model input:1000 bit { }} { output:100 bit { }} { : random oracle model 5.2 Diffie-Hellman Deffie-Hellman 1976 DH 12

18 [11] DH ElGamal Diffie-Hellman 2 A B 1. G p G g G 2. A a U Z p g a B 3. B b U Z p g b A 4. A SK A = (g b ) a 5. B SK B = (g a ) b  ˆB a U Z q g a g b b U Z q SK A = (g b ) a SK B = (g a ) b 6: DH Diffie-Hellman (g, g a, g b ) g ab CDH (Computational Diffie-Hellman) DH (g, g a, g b, g ab ) (g, g a, g b, g c ) (c ab) DDH (Decisional Diffie-Hellman) DH DH 5.3 ElGamal ElGamal Diffie-Hellman [12] Setup: G; p g: G (A = g a, a) (G, g, A) Enc: m G b U Z p (C 1, C 2 ) = (g b, A b m) 13

19 Dec: a C 2 /C1 a = m ElGamal DDH IND-CPA 5.4 (IF:Integer Factorization) (DL:Discrete Logalithm) IF IF DL DL RSA CDH QR DDH RSA ElGamal random oracle RSA-OAEP IND-CCA2 DHIES PSEC 1: 5.5 Cramer-Shoup Cramer-Shoup Cramer-Shoup 1998 random oracle IND-CCA2 [9] Cramer-Shoup Setup: (x 1, x 2, y 1, y 2, z 1, z 2 ) Z 6 p p G, Ĝ g G, ĝ Ĝ e = g x1ĝ x 2, f = g y1ĝ y 2, h = g z1ĝ z 2 hk (g, ĝ, hk, e, f, h) Enc: m G E1: u U Z p E2: a g u E3: â ĝ u 14

20 E4: c h u m E5: HF hk v HF hk (a, â, c) E6: d e u f uv (a, â, c, d) Dec: (x 1, x 2, y 1, y 2, z 1, z 2 ) D1: D2: a, â, c G D3: HF hk v HF hk (a, â, c) D4: d = a x1+y1v â x2+y2v D5: m c (a z1â z 2 ) 1 : (x 1, x 2, y 1, y 2, z 1, z 2 ) : (g, ĝ, hk, e = g x1ĝx 2, f = g y1ĝy 2, h = g z1ĝz 2 ) Encrypt E1: u U Z p E2: a g u E3: â ĝ u E4: c h u m E5: v HF hk (a, â, c) E6: d e u f uv (a, â, c, d) Decrypt D1: Check the form D2: a, â, c? G D3: v HF hk (a, â, c) D4: d =? a x1+y1v â x2+y2v D5: m c (a z1 â z2 ) 1 7: Cramer-Shoup Cramer-Shoup g, ĝ ĝ = g ω ω e = g x1 ĝ x2 = g x1+ωx2 = g γ γ γ = x 1 + ωx 2 (mod p) x 2 = γ x 1 ω (mod p) 15

21 (x 1, x 2 ) p x 1 Z p p E6 D4 d = e u f uv = (g x1 ĝ x2 ) u (g y1 ĝ y2 ) uv = g u(x 1+y 1 v) 1 ĝ u(x2+y2v) = a x 1+y 1 v 1 a x 2+y 2 v 2 a = g u, â = ĝ u d = (g u ) x 1+y 1 v (ĝ u ) x 2+y 2 v ĝ, d, e, f g log g ĝ = ω log g d = u 1 x 1 + u x 2 + (u 1 y 1 + u y 2 )v log g e = x 1 + ωx 2 log g f = y 1 + ωy 2 x 1 log g e 1 ω 0 0 log g f = ω x 2 log g d u ωu uv ωu y 1 v u = u u u a 1 a 2 D4 a â y Cramer-Shoup Cramer-Shoup standard model DDH HF target collision resistant (TCR) IND-CCA2 H = (H h ) h h Target Collision Resistant (TCR) (H, h, x) H h (x) = H h (y) y (y x) Collision Resistant (CR) (H, h) 16

22 H h (x) = H h (y) (x, y) (y x) Cramer-Shoup traditional security proof (1998 reduction 2 traditional security proof traditional security proof simulator reduction IND-CCA2 Cramer-Shoup DDH 1/2 simulator simulator DDH tuple (g, ĝ, a, â) log g a = logĝ â simulator (x 1, x 2, y 1, y 2, z 1, z 2 ) Z 6 p (e = gx1ĝx 2, f = g y1ĝy 2, h = g z1ĝz 2 ) (g, ĝ, hk, e, f, h) IND-CCA2 decryption oracle simulator DDH tuple: (g, ĝ, a, â) If log g a = logĝ â output 1 Simulator log g a logĝ â output 0 SK (x 1, x 2, y 1, y 2, z 1 z 2 ) Z p e = g x1 ĝ x2, f = g y1 ĝ y2, h = g z1 ĝ z2 PK (g, ĝ, hk, e, f, h) (g, ĝ, hk, e, f, h) decryption oracle ) Adv SK b m 0, m 1 (a, â, c, d) If b = b then output 1 else output 0 b U {0, 1} c a z1â z2 m b v HF hk (a, â, c) d a x 1+y 1vâ x 2+y 2 v 8: Cramer-Shoup traditional security proof 17

23 m 0, m 1 simulator DDH tuple b U {0, 1}, c a z1 â z2 m b, v HF hk (a, â, c), d a x1+y1v â x2+y2v (a, â, c, d) decryption oracle ( (a, â, c, d) ) simulator m 0, m 1 guess b simulator b = b DDH tuple log g a = logĝ â b b DDH tuple log g a logĝ â Cramer-Shoup Cramer-Shoup Cramer-Shoup IND-CCA2 (Game 0 ) negligible IND-CCA2 advantage 0 Game 0 advantage Game negligible Game 0 Game 1 Game n DO ) PK b Adv EO b Adv 0 = Pr[b = b ] 1 2 < n i=1 ε i Adv ε 1 = Pr[b = b ] 1 2 Adv 1 ε n = 0 2 εn 9: Cramer-Shoup 18

24 Game 0: Game 0 Cramer-Shoup IND-CCA2 Adv Encryption oracle(eo), Decryption oracle(do) DO c Encryption oracle Decryption oracle D1: Check the form D2: a, â, c? G D3: v HF hk (a, â, c) D4: d =? a x1+y1v â x2+y2v D5: m c (a z1 â z2 ) 1 ) (g, ĝ, hk, d, f, h) Adv b (m 0, m 1 ) (a, â, c, d ) b U {0, 1} E1: u U Z p E2: a g u E3: â ĝ u E4: c h u m b E5: v HF hk (a, â, c) E6: d e u f uv 10: Game 0 Game 1: Game 1 Game 0 E4 E6 E4: c h u m b c (a ) z1 (â ) z2 m b E6: d e u f uv d (a ) x 1+y 1 v (â ) x 2+y 2 v conceptual change u (x 1, x 2, y 1, y 2.z 1, z 2 ) Decryption oracle D1: Check the form D2: a, â, c? G D3: v HF hk (a, â, c) D4: d? = a x 1+y 1vâ x 2+y 2 v D5: m c (a z1â z 2 ) 1 (g, ĝ, hk, d, f, h) ) b b U {0, 1} E1: u U Z p (m 0, m 1 ) E2: a g u Adv E3: â ĝ u (a, â, c, d ) Encryption oracle E4 : c (a ) z 1 (â ) z2 m b E5: v HF hk (a, â, c) E6 : d (a ) x 1+y 1 v (â ) x 2+y 2 v 11: Game 1 19

25 Game 2: Game 2 Game 1 E3 E3: â ĝ u â ĝû, û U Z p \ {u} DDH tuple (log g a = logĝ â) non DDH tuple (log g a logĝ â) DDH advantage negligible Decryption oracle D1: Check the form D2: a, â, c? G D3: v HF hk (a, â, c) D4: d? = a x1+y1v â x2+y2v D5: m c (a z1 â z2 ) 1 (g, ĝ, hk, d, f, h) ) b b U {0, 1} Encryption oracle E1: u U Z p (m 0, m 1 ) E2: a g u Adv E3 : â (a, â, c, d ) ĝû, û U Z p E4 : c (a ) z1 (â ) z2 m b E5: v HF hk (a, â, c) E6 : d (a ) x1+y1v (â ) x2+y2v 12: Game 2 Game 3: Game 3 Game 2 D4 D5 D4: d =? a x 1+y 1vâ x 2+y 2 v â =? a w, d =? a x+yv, v =? v ( e = g x, f = g y, h = g z, ĝ = g w ) D5: m c (a z1â z 2 ) 1 m c(a z ) 1 a, â Decryption oracle D1: Check the form D2: a, â, c? G D3: v HF hk (a, â, c) D4 : â? = a w, d? = a x+yv, v? = v D5 : m (c z ) 1 (g, ĝ, hk, d, f, h) ) b b U {0, 1} Encryption oracle E1: u U Z p (m 0, m 1 ) E2: a g u Adv E3 : â (a, â, c, d ) ĝû, û U Z p E4 : c (a ) z1 (â ) z2 m b E5: v HF hk (a, â, c) E6 : d (a ) x1+y1v (â ) x2+y2v 13: Game 3 20

26 D4 decryption oracle q DO q DO p negligible TCR ( ) Game 4: Game 4 Game 3 E4 E4: c (a ) z 1 (â ) z2 m b c g r, r U Z p Game 3 z 1, z 2 ( h = g z1 ĝ z2 z 1, z 2 Traditional Security Proof ) E4 c z 1, z 2 r Decryption oracle D1: Check the form D2: a, â, c? G D3: v HF hk (a, â, c) D4 : â? = a w, d? = a x+yv, v? = v D5 : m (c z ) 1 (g, ĝ, hk, d, f, h) ) b b U {0, 1} Encryption oracle E1: u U Z p (m 0, m 1 ) E2: a g u Adv E3 : â (a, â, c, d ) ĝû, û U Z p E4 : c g r, r U Z p E5: v HF hk (a, â, c) E6 : d (a ) x 1+y 1 v (â ) x 2+y 2 v 14: Game 4 Game 4 m 0 m 1 advantage 0 advantage negligible Game 0 advantage 0 negligible Cramer-Shoup DDH TCR IND-CCA2 ( ) TCR a = g u, â = ĝ u decryption oracle a = g t, â = ĝ t a â 21

27 a = g u â = ĝ u a = g t â = ĝ t e = g x1ĝx 2 f = g y1ĝy 2 d = (a ) x 1+y 1 v (â ) x 2+y 2 v d = a x 1+y 1 v â x 2+y 2 v ĝ = g ω e, f, d, d g log g e = x 1 + ωx 2 log g f = y 1 + ωy 2 log g d = u(x 1 + v y 1 ) + u ω(x 2 + v y 2 ) log g d = t(x 1 + vy 1 ) + tω(x 2 + vy 2 ) 4 log g e 1 ω 0 0 x 1 log g f log g d = ω x 2 u ωu uv ωu v y 1 log g d t ωt tv ωtv 4 4 A A = ω 2 (u u )(t t )(v v) 0 A d 1/p 0 v v TCR 5.1. Event1, Event2 Event1 F = Event2 F = Pr[Event1] Pr[Event2] Pr[F ] y X n, Y n 3 : X n = Y n α, Pr[X n α] = Pr[Y n α] : α {0,1} Pr[X n α] = Pr[Y n α] < ɛ 22

28 : D Pr[D(X n ) = 1] Pr[D(Y n ) = 1] < ɛ X n Y n α α 15: 2 X n, Y n 2 U V (statistically indistinguishable) {X n } n N, {Y n } n N l(n)bit (l(n) n ) (statistical distance) δ(x n, Y n ) = Pr[X n α] Pr[Y n α] 1 2 < ɛ(n) α {0,1} l(n) negligible (computational indistingushability) D Pr[D(x) 1 x R X n ] Pr[D(y) 1 y R Y n ] < ɛ(n) DDH 6.2 ( ) r G G(r) G(r) R G(r) G(r) H(G(r)) r H(r) R H(R) G(r) H(G(r)) H(R) 23

29 H(G(r)) = H(r) = r) << G(r) CH(G(r)) = H(R) = R = G(r) G(r) R ( ). A B D Pr[D(A) = 1] Pr[D(B) = 1] < ε 100bit G 1000bit 100bit 1000bit Blum,Micali 1982 next bit test next bit test r 0 1 next bit test Yao : 1984 Goldreich,Goldwasser,Micali n bit 2n bit 2n bit 2 n bit n 24

30 bit 2n bit n bit 1 0 n { }} { : r G 2n { }} { r G r 0 r 1 G r 10 r 11 r 100 G r r : 7 / Alice x 1 {0, 1} Bob x 2 {0, 1} Carol x 3 {0, 1} f(x 1, x 2, x 3 ) = x 1 + x 2 + x 3 n t (Correctness): n t f(x 1,, x n ) (Security): t n t 25

31 1987 Goldreich,Micali,Wigderson ( ) f t < n t [18] 1988 Ben-Or,Goldwasser,Wigderson f t < 3 n t [?] 7.1 ( 1 Goldreich-Micali-Wigderson 1987)). f t < n 7.2 ( 2 Ben-Or-Goldwasser-Wigderson 1988)). f t (< n 3 ) NP NP 18: 26

32 8 b {0, 1} ( ) b ( ) : b : 2 Alice 1 0 Bob Bob ( ) Alice Bob Bob Alice 1 Bob 0 ( ) 9 Alice Bob 10 (OT:Oblivious Transfer) Alice Bob 2 m 0, m 1 Bob b {0, 1} m b Alice Bob Bob 27

33 : 2 ( : ) : (view) 1985 view. 19: 11.2 (ZKIP: Zero Knowledge Interactive Proof) P V P V V ( / / )- 3 (P, V ) ( / / )- V (PPT ) M V x V View V (x) M V (x) V, M V, x, M V (x) View V (x) 28

34 P V. 20: L (P, V ) 3 1. : x L Pr[(P, V )(x) ] 1 2. : x L Pr[(P, V )(x) ] 0 3. ( ) : V, M V, x L, y ( ), View V (x, y) M V (x, y) 1 0 V 1 V 1 M V : P n = pq n x (x = y 2 (mod n)) V ZKIP 1. P r U Z n a = r 2 (mod n) V (commit ) 2. V e U {0, 1} e P (challenge ) 3. P b = y e r (mod n) b V (response ) 4. V b 2 = x e a (mod n) n V abort V P 29

35 P (x, n) V r U Z n a = r 2 (mod n) commit e U {0, 1} challenge b = y e r (mod n) response b 2 =? x e a (mod n) 21: 11.3 / 1 V 1 M V V ( ), M V ( TM), View V (x, y) M V (x, y) over (x, y) L {0, 1} V M V V 1 M V M ( ), V, x L, M V (x) View V (x) : (P, V ) e = 0 b = r e = 1 b = yr 30

36 x L, Pr[(P, V )(x) ] = 1 : V P ( ) e = 0 b 2 = a (mod n) e = 1 b 2 = xa (mod n) 2 ( ) b 2 x = (mod n) b x x L, P, Pr[( P, V )(x) ] < 1/2 n ( ) P Ṽ ( ) V M Ṽ (Ṽ ) (1) Ṽ e U {0, 1} guess (2) b U Z n a = b2 /x e (3) Ṽ Ṽ a (4) Ṽ e e = e b e e (1) (Ṽ ) Ṽ n 2 n x L QRn, ViewṼ (x) = M Ṽ (x) 31

37 1 guess n Ṽ n e 1/2 n guess 1/2 n 3move 11.4 Goldwasser,Micali,Wigderson 1986 NP ( PSPACE) [17] Naor 1986 Håstad,Impagliazzo,Levin,Luby 1990 [19] CO-NP NP PSPACE CO-NP NP CO-NPC P NPC 22: 32

38 (CO-)NPC (CO-)NP (CO-)NPC (CO-)NP NPC (sequential composition) (parallel composition) concurrent (Concurrent ) 12 (Universal Composability: UC) (Universal Composability UC) UC 2001 Canetti [7] UC ( ) π F ( A ) S ( ) ( ) Z UC A, S, s.t. Z 1: F KE K KE A B A B session F KE 1 session s (A, B, s) F KE (A, B, s) session 33

39 P 1 P2 P3 P 4 S P 1 π P 2 P 3 P 4 A F 23: OK F KE session key SK U {0, 1} n A B SK session key random Alice Bob 2: F ZK K ZK P V F KE P session s x w (P, V, x, w, s) F ZK V (P, V, x) F ZK F ZK x w R (P, V, x, R(x, w), s) OK F ZK V (P, V, x, R(x, w), s) V x R(x, w) = 1 V R(x, w) π F 34

40 K KE K ZK (A,B,s) F KE (A,B,s) A K K B OK (A,B,s) Adv (P,V,x,w,s) F ZK P (A,B,x,w,R(x, w),s) (P,V,x) V OK (A,B,x,w,R(x, w),s) Adv 24: π ρ F ρ F F ρ π ρ F F π π F ρ F F F F ρ pi F π ρ ρ F ρ ρ = ρ π π π ρ π π π ρ π π π ρ π π π 25: 2001 Canneti UC 35

41 (The Universal Composition Theorem) ρ π A ρ F A Z ρ F ρ π ρ π ρ F UC : A, A, Z, Z ρ F ρ π (ρ F, A ) (ρ π, A) UC UC 3 2 UC 2 UC Setup CRS(Common Reference String) UC IND-CCA2 UC EUF-CMA UC Alice Bob 2 Alice Bob session key session key Authenticated Key Exchange Diffie-Hellman Ephemeral Diffie-Hellman Ephemeral Diffie-Hellman 5.2 [11] 2 Â ˆB 36

42 1. G p G g G 2.  x U Z p X g x (Â, ˆB, X) ˆB U 3. ˆB y Zp Y g y (Â, ˆB, Y )  4.  session key SK A Y x 5. ˆB session key SKB X y  x U Z q SK A = Y x Â, ˆB, X = g x ˆB, Â, Y = gy ˆB y U Z q SK B = X y 26: Ephemeral DH Diffie-Hellman (g, g a, g b ) g ab CDH (Computational Diffie-Hellman) (g, g a, g b, g ab ) (g, g a, g b, g c ) (c ab) DDH (Decisional Diffie-Hellman) X Y Diffie-Hellman Diffie-Hellman Man-in-the Middle Attack (MIM Attack) Diffie-Hellman 1.  x U Z p X g x (Â, ˆB, X) B 2. Ĉ (Â, ˆB, X) ˆB z U Z p Z g z (Â, ˆB, Z) ˆB U 3. ˆB y Zp Y g y ( ˆB, Â, Y )  4. Ĉ ( ˆB, Â, Y )  w U Z p W g w (Â, ˆB, W )  5.  SK A W x ˆB SK B SK A Xz SK B Y z Z b Ĉ 37

43 Â Ĉ ˆB Â, ˆB, X = g x Â, ˆB, Z = g z x U Z z U Z q q w U y U Z q Z q ˆB, Â, W = gw ˆB, Â, Y = gy SK A = W x SK A = Xw SK B = Y z SK B = Z y 27: Ephemeral DH MIM Attack Alice Bob DH session key (AKE: Authenticated Key Exchange) 1. Public-key infrastructure(pki)-based AKE. Authentication for messages/parties is ensured by PKI. 2. Password@based AKE(PAKE) Authetication for messages/parties is ensured by password Static Diffie-Hellman PKI-AKE Static Diffie-Hellman Static Diffie-Hellman Ephemeral Diffie-Hellman / 2 Â, ˆB 1. Â a U Z p A g a U 2. ˆB b Zp B g b 3. Â cert(a) (Â, cert(a)) ˆB 4. ˆB ( ˆB, cert(b)) Â 5. Â session key SK A B a 38

44 6. ˆB session key SKB A b :A = g a :a  :B = g b :b ˆB SK A = A b Â, cert(a) ˆB, cert(b) SK B = B a 28: Static DH  ˆB session key session key session key session key session key known key security session key session key Static Diffie-Hellman session key H(counter, g ab ) Forward secrecy session session key Forward secrecy Forward secrecy counter Static Diffie-Hellman session key Blake-Johnson-Menezes Ephemeral DH Static DH Blake- Willson, Johnson, Menezes BJM [3] 39

45 / session key 1.  a U Z p A g a U 2. ˆB b Zp B g b 3.  x U Z p X g x (Â, ˆB, X) ˆB U 4. ˆB y Zp Y g y (Â, ˆB, Y )  5.  H session key SK A H(Y x, B a ) 6. ˆB session key SKB H(X y, A b ) :A = g a :a  :B = g b :b ˆB x U Z q Â, ˆB, X = g x ˆB, Â, Y = gy y U Z q SK A = H(Y x, B a ) SK B = H(X y, A b ) 29: BJM BJM Ephemeral DH g ab g xy BJM Known key security 1.  1 session x U Z p X g x (Â, ˆB, X) ˆB 2.  2 session x U Zp X g x (Â, ˆB, X ) ˆB 3. Ĉ  1 session (Â, ˆB, X ) 40

46 4. Ĉ  2 session (Â, ˆB, X) 5.  1 session session key SK A (X ) x 2 session session key SK A (X)x :A = g a :a  Ĉ  Ĉ Â, ˆB, X = x U Z g x q ˆB, Â, X SK A = H(B a, (X ) x ) x U Z q SK A = H(B a, (X) x ) Â, ˆB, X = g x ˆB, Â, X 30: BJM Known Key Attack  session session key session key session key BJM Known key Security MAC MAC(Message Authentication Code) k m MAC σ = MAC k (m) MAC (m, σ = MAC k (m)) k (m, σ = MAC k (m )) MAC BJM 1.  a U Z p A g a U 2. ˆB b Zp B g b 3.  x U Z p X g x (Â, ˆB, X) ˆB U 4. ˆB y Zp Y g y H k 1 H(X y, A b ) MAC h MAC k1 ( ˆB, Â, Y, X) (Â, ˆB, Y, h)  41

47 5.  k 1 H(X y, A b ) h = MAC k 1 ( ˆB, Â, Y, X) h MAC k (Â, ˆB, 1 X, Y ) (Â, ˆB, h ) ˆB session key SK A H(Y x, B a ) 6. ˆB h = MACk1 (Â, ˆB, X, Y ) session key SK B H(X y, A b ) :A = g a :a :B = g b :b  x U Z q Â, ˆB, X = g x ˆB y U Z q ˆB, Â, Y = gy, h = MAC k1 ( ˆB, Â, Y, X) h = MAC k (Â, ˆB, 1 X, Y ) SK A = H(Y x, B a ) SK B = H(X y, A b ) 31: MAC BJM MAC k = H(g xy, g ab ) g ab k MAC Key Compromise Impersonation (KCI) Attack Alice Alice Alice KCI resistance Alice Bob ( Bob ) Alice session key Alice X = g x MAC H(g xy, g ab ) Alice a B a = g ab 42

48 z U Z q Z g z MAC k H(X z, B a ) Alice MAC session key DH MAC Alice X = g x Alice Alice Bob Y g y 1. Â Sig A V er A 2. ˆB SigB V er B 3. Â x U Z q X g x σ A = Sign A (X) (Â, ˆB, X, σ A ) ˆB U 4. ˆB y Zq Y g y σ B = Sign B (Y ) ( ˆB, Â, Y, σ B) Â 5. Â session keysk A Y x 6. ˆB session keyskb X y :V er A :Sig A Â x U Z q SK A = g x Â, ˆB, X = g x, σ A = Sign A (X) ˆB, Â, Y = gy, σ B = Sign B (Y ) :V er B :Sig B ˆB y U Z q SK B = g y 32: DH 43

49 Alice ( ) Bob Bob KCI attack session key x, y Known key security Forward secrecy No Resistance for Leakage of Ephemeral Private Key (RLE) session x y x y session key RLE MQV 1995 Menezes,Qu,Vanstone MQV MQV 1. Â a U Z q A = g a U 2. ˆB b Zq B = g b 3. Â x U Z q X g x (Â, ˆB, X) ˆB U 4. ˆB y Zq Y g y ( ˆB, Â, Y ) Â 5. Â X lbit d Y lbit e σ A (Y B e ) x+ad key derivation hash KDF session key SK A KDF(σ A ) 6. Â σ B (Y A d ) y+be session key SK B KDF(σ B ) 13.2 Canetti-Krawczyk Security model 1993 Bellare,Rogaway [4] 2001 Canetti,Krawczyk [8] 2007 Lamacchia,Lauter,Mitchagin [21] Canetti,Krawczyk 44

50 :A = g a :a  :B = g b :b ˆB x R Z q Â, ˆB, X = g x ˆB, Â, Y = gy y R Z q SK A = KDF((Y B e ) x+da ) SK B = KDF((XA d ) y+eb ) (d : X l bit) (e : Y l bit) 33: MQV session owner owner peer session owner peer session key owner Alice session peer Bob session 2 2 session Matching session query State reveal query : session (session ) Session key query : session session key Party corrupt query : 45

51 session Test query query 1 Test query session (Test session ) session key SK challenger b U {0, 1} b = 1 SK b = 0 random test session guess b b = b test session session matching session 3 query 1bit test session session key guess advantage Pr[b = b] 1/2 negligible Canetti-Krawczyk security model query Canetti-Krawczyk security model session key Known key security Forward secrecy KCI attack session ehemeral test session matching session query 13.3 HMQV HMQV 2005 Krawczyk [20] MQV HMQV Canetti-Krawczyk security model CDH random oracle model KCI attack wpfs session ehemeral Gap Diffie-Hellman KEA1 random oracle model HMQV 1. Â a U Z q A g a 46

52 U 2. ˆB b Zq B g b 3.  x U Z q X g x (Â, ˆB, X) ˆB U 4. ˆB y Zq Y g y ( ˆB, Â, Y )  5.  H d H(X, ˆB), e H(Y, Â) σ A (Y B e ) x+ad H session key SK A H(σ A ) 6.  σ B (Y A d ) y+be session key SK B H(σ B ) :A = g a :a  :B = g b :b ˆB x R Z q Â, ˆB, X = g x ˆB, Â, Y = gy y R Z q SK A = H((Y B e ) x+da ) SK B = H((XA d ) y+eb ) (d = H(X, ˆB)) (e = H(Y, Â)) 34: HMQV 13.4 Extended Canetti-Krawczyk security model HMQV Canetti-Krawczyk security model LaMacchia,Lauter,Mityagin security model [21] security model Canetti-Krawczyk security model Extended CK (eck) security model query Ephemeral key reveal query : session (session ) Static key reveal query : 47

53 Session key query : session session key Test session matching session query 1. test session Session key reveal query test session Ephemeral key reveal query test session owner Static key reveal query 2. test session matching session matching session Session key reveal query matching session Session state reveal query test session peer Static key reveal query 3. test session matching session test session peer Static key reveal query eck security model Caneeti-Krawczyk security model wpfs KCI RLE 13.5 CMQV CMQV HMQV 2007 Ustaoglu eck security model CMQV session eck security model CMQV 1. Â a U Z q A = g a U 2. ˆB b Zq B = g b 3. Â x U Z q H 1 x H( x, b) X g x (Â, ˆB, X) ˆB x U 4. ˆB ỹ Zq H 1 y H(ỹ, b) Y g y ( ˆB, Â, Y ) Â y 5. Â H 2 d H 2 (X, ˆB), e H 2 (Y, Â) σ A (Y B e ) x+ad H session key SK A H(σ A, X, Y, Â, ˆB) 48

54 6. ˆB σb (Y A d ) y+be session key SK B H(σ B, X, Y, Â, ˆB) :A = g a :a  :B = g b :b ˆB x R Z q x = H 1 ( x, a) Â, ˆB, X = g x ˆB, Â, Y = gy ỹ R Z q y = H 1 (ỹ, b) SK A = H((Y B e ) x+da ) SK B = H((XA d ) y+eb ) (d = H 2 (X, ˆB)) (e = H 2 (Y, Â)) 35: CMQV CMQV ephemeral key reveal query x ỹ x y session X x eck security model [1] M. Bellare, A. Desai, D. Pointcheval and P. Rogaway, Relations Among Notions of Security for Public-Key Encryption Schemes, Advances in Cryptology CRYPTO 98, volume 1462 of LNCS, pages 26-45, [2] M. Ben-Or, S. Goldwasser, A. Wigderson, Completeness Theorems for Non- Cryptographic Fault-Tolerant Distributed Computation(Extended Abstract), In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 1-10, [3] S. Blake-Wilson, D. Johnson and A. Menezes, Key exchange protocols and their security analysis, In 6th IMA International Conference on Cryptography and Coding, volume 1355 of LNCS, pages 30-45,

55 [4] M. Bellare and P. Rogaway, Entity Authentication and Key Distribution, Advances in Cryptology - CRYPTO 93, volume 773 of LNCS, pages , [5] M. Bellare and P. Rogaway, Optimal Asymmetric Encryption Advances in Cryptology - EUROCRYPT 94, volume 950 of LNCS, pages , [6] M. Bellare and A. Sahai, Non-malleable Encryption: Equivalence between Two Notions, and an Indistinguishability-Based Characterization, Advances in Cryptology - CRYPTO 99, volume 1666 of LNCS, pages , [7] R. Canetti, Universally Composable Security: A New Paradigm for Cryptographic Protocols, In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, pages , [8] R. Canetti and H. Krawczyk, Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels, Advances in Cryptology - EUROCRYPT 01 volume 2045 of LNCS, pages , [9] R. Cramer and V. Shoup, A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack, Advances in Cryptology - CRYPTO 98, volume 1462 of LNCS, pages 13-25, [10] D. Dolev, C. Dwork and M. Naor, Non-Malleable Cryptography, In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages , [11] W. Diffie and M. Hellman, New Directions in Cryptography, In IEEE Transactions on Information Theory, volume IT-22(6), pages , [12] T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, Advances in Cryptology CRYPTO 84, volume 196 of LNCS, pages 10-18, [13] E. Fujisaki, T. Okamoto, D. Pointcheval and J. Stern, RSA-OAEP Is Secure under the RSA Assumption, In Journal of Cryptology, volume 17 number 2, pages ,2004. [14] O. Goldreich, S. Goldwasser and S. Micali, How to Construct Random Functions (Extended Abstract), In Proceedings of the 25th Annual Symposium on Foundations of Computer Science, pages ,

56 [15] S. Goldwasser and S. Micali, Probabilistic Encryption and How to Play Mental Poker Keeping Secret All Partial Information, In Proceedings of the 14th Annual ACM Symposium on Theory of Computing, pages , [16] S. Goldwasser, S. Micali and R. L. Rivest, A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks, In SIAM Journal on Computing, volume 17 number 2, pages , [17] O. Goldreich, S. Micali nad A. Wigderson, How to Prove all NP-Statements in Zero-Knowledge, and a Methodology of Cryptographic Protocol Design, Advances in Cryptology - CRYPTO 86, volume 263 of LNCS, pages , [18] O. Goldreich, S. Micali nad A. Wigderson, How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority, In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pages , [19] J. Håstad, R. Impagliazzo, L. A. Levin and M Luby, A Pseudorandom Generator from any One-way Function, In SIAM Journal of Computing, volume 28 number 4, pages , [20] H. Krawczyk, HMQV: A High-Performance Secure Diffie-Hellman Protocol, Advances in Cryptology - CRYPTO 05, volume 3621 of LNCS, pages , [21] B. A. LaMacchia, K. Lauter and A. Mityagin, Stronger Security of Authenticated Key Exchange, In Proceedings of the First International Conference of Provable Security, volume 4784 of LNCS, pages 1-16, [22] A. Menezes, P. C. Oorschot, S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, [23] A. Menezes, M. Qu and S. Vanstone, Some new key agreement protocols providing implicit authentication, In 2nd Workshop on Selected Areas in Cryptography, pages 22-32, [24] M. Naor and M. Yung, Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks, In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pages ,

57 [25] M. O. Rabin, Digitalized signatures and publickey functions as intractable as factorization, MIT/LCS/TR-212, MIT Laboratory for Computer Science, [26] C. Rackoff and D. R. Simon, Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack, In Proceedings of CRYPTO 1991, volume 576 of LNCS, pages , [27] R. Rivest, A. Shamir, and L. Adleman, A Method for Obtaining Digital Signatures and Public Key Cryptosystems, Communications of the ACM, volume 21 number 2, pages , [28] B. Ustaoglu, Obtaining a secure and efficient key agreement protocol from (H)MQV and NAXOS, In Designs, Codes and Cryptography,volume 46 number 3, pages ,

/ ( ) 1 1.1 323 206 23 ( 23 529 529 323 206 ) 23 1.2 33 1.3 323 61 61 3721 3721 323 168 168 323 23 61 61 23 1403 323 111 111 168 206 323 47 111 323 47 2 23 2 2.1 34 2 2.2 2 a, b N a b N a b (mod N) mod

More information

21 Key Exchange method for portable terminal with direct input by user

21 Key Exchange method for portable terminal with direct input by user 21 Key Exchange method for portable terminal with direct input by user 1110251 2011 3 17 Diffie-Hellman,..,,,,.,, 2.,.,..,,.,, Diffie-Hellman, i Abstract Key Exchange method for portable terminal with

More information

( )

( ) NAIST-IS-MT0851100 2010 2 4 ( ) CR CR CR 1980 90 CR Kerberos SSH CR CR CR CR CR CR,,, ID, NAIST-IS- MT0851100, 2010 2 4. i On the Key Management Policy of Challenge Response Authentication Schemes Toshiya

More information

(Requirements in communication) (efficiently) (Information Theory) (certainly) (Coding Theory) (safely) (Cryptography) I 1

(Requirements in communication) (efficiently) (Information Theory) (certainly) (Coding Theory) (safely) (Cryptography) I 1 (Requirements in communication) (efficiently) (Information Theory) (certainly) (oding Theory) (safely) (ryptography) I 1 (Requirements in communication) (efficiently) (Information Theory) (certainly) (oding

More information

Block cipher

Block cipher 18 12 9 1 2 1.1............................... 2 1.2.................. 2 1.3................................. 4 1.4 Block cipher............................. 4 1.5 Stream cipher............................

More information

[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)

More information

Vol.59 No (Sep. 2018) 1,a) , CPU CPU CPU CPU CASS 2 CASS General Constructions of Computer-aided Security Sch

Vol.59 No (Sep. 2018) 1,a) , CPU CPU CPU CPU CASS 2 CASS General Constructions of Computer-aided Security Sch 1,a) 1 1 2 3 1 2017 12 11, 2018 6 8 CPU CPU CPU CPU CASS 2 CASS General Constructions of Computer-aided Security Schemes Yasuyoshi Jinno 1,a) Takashi Tsuchiya 1 Tetsushi Ohki 1 Kenta Takahashi 2 Wakaha

More information

<4D F736F F D20838A B F955C8E8682A982E796DA8E9F914F5F A815B FD B A5F E646F63>

<4D F736F F D20838A B F955C8E8682A982E796DA8E9F914F5F A815B FD B A5F E646F63> 2008 年度版リストガイド ( メッセージ認証コード ) 平成 21 年 3 月 独立行政法人情報通信研究機構独立行政法人情報処理推進機構 1 1 1.1............................. 1 1.1.1............................ 1 1.1.2....................... 1 1.1.3...........................

More information

ICカードに利用される暗号アルゴリズムの安全性について:ENV仕様の実装上の問題点を中心に

ICカードに利用される暗号アルゴリズムの安全性について:ENV仕様の実装上の問題点を中心に IC IC IC ICIC EMVEMV IC EMVIC EMV ICEMVRSAkey TDES TDES-MAC E-mail: masataka.suzuki@boj.or.jp NTTE-mail: kanda.masayuki@lab.ntt.co.jp IC IC IC IC EMV JCCA ICJCCA ICEMV EMVIC EMV EMV EMVEMVCo EMV EMV EMVICIC

More information

28 SAS-X Proposal of Multi Device Authenticable Password Management System using SAS-X 1195074 2017 2 3 SAS-X Web ID/ ID/ Web SAS-2 SAS-X i Abstract Proposal of Multi Device Authenticable Password Management

More information

30 2018.4.25 30 1 nuida@mist.i.u-tokyo.ac.jp 2018 4 11 2018 4 25 30 2018.4.25 1 1 2 8 3 21 4 28 5 37 6 43 7 47 8 52 30 2018.4.25 1 1 Z Z 0 Z >0 Q, R, C a, b a b a = bc c 0 a b b a b a a, b, c a b b c a

More information

ISO/IEC 9798プロトコルの安全性評価

ISO/IEC 9798プロトコルの安全性評価 ISO/IEC 9798 2011 2 4 ISO/IEC 9798-2 (Mechanisms using symmetric encipherment algorithms), ISO/IEC 9798-3 (Mechanisms using digital signature techniques), ISO/IEC 9798-4 (Mechanisms using a cryptographic

More information

1 2 1.1............................................ 3 1.2.................................... 7 1.3........................................... 9 1.4..

1 2 1.1............................................ 3 1.2.................................... 7 1.3........................................... 9 1.4.. 2010 8 3 ( ) 1 2 1.1............................................ 3 1.2.................................... 7 1.3........................................... 9 1.4........................................

More information

04.™ƒ”R/’Ô”�/’Xfl©

04.™ƒ”R/’Ô”�/’Xfl© Digicashecash PC IC AI LicenseCoin License Pk A L Pk A W Rc C Coin License Okamoto and Ohta Okamoto and Ohta IC Digicashecash TTP Trusted Third Party TTP TTP TTP TTP: Trusted Third Party TTPTTP TTP TTP

More information

特集_03-07.Q3C

特集_03-07.Q3C 3-7 Error Detection and Authentication in Quantum Key Distribution YAMAMURA Akihiro and ISHIZUKA Hirokazu Detecting errors in a raw key and authenticating a private key are crucial for quantum key distribution

More information

<4D F736F F D20838A B F955C8E8682A982E796DA8E9F914F E718F9096BC816A5F E646F63>

<4D F736F F D20838A B F955C8E8682A982E796DA8E9F914F E718F9096BC816A5F E646F63> 2008 年度版リストガイド ( 電子署名 ) 平成 21 年 3 月 独立行政法人情報通信研究機構独立行政法人情報処理推進機構 1 1 1.1............................. 1 1.1.1............................ 1 1.1.2....................... 1 1.1.3...........................

More information

( 9 1 ) 1 2 1.1................................... 2 1.2................................................. 3 1.3............................................... 4 1.4...........................................

More information

Proposal of addition of new cipher suites to TLS to support Camellia, EPOC, and PSEC Shiho Moriai NTT Laboratories th

Proposal of addition of new cipher suites to TLS to support Camellia, EPOC, and PSEC Shiho Moriai NTT Laboratories th Proposal of addition of new cipher suites to TLS to support Camellia, EPOC, and PSEC Shiho Moriai shiho@isl.ntt.co.jp NTT Laboratories 128-bit Block Cipher Camellia Kazumaro Aoki * Tetsuya Ichikawa Masayuki

More information

., ( [22]) ( ),.,,., 90 ( [38]),. ( [12]).,,..,.,,. 2,. 3,. 4,.,,. [20], [31],,. ([21], [34], [36], [49] ),,.,.,. 2

., ( [22]) ( ),.,,., 90 ( [38]),. ( [12]).,,..,.,,. 2,. 3,. 4,.,,. [20], [31],,. ([21], [34], [36], [49] ),,.,.,. 2 A.Takemura@e.u-toyo.ac.jp 2000 2 Abstract.,.,,. (2000 2 ), 1. 1.,..,,.,,., 4. 1,, http://www.e.u-tokyo.ac.jp/~takemura/em-survey.html. 1 ., ( [22]) ( ),.,,., 90 ( [38]),. ( [12]).,,..,.,,. 2,. 3,. 4,.,,.

More information

RSA署名方式の安全性を巡る研究動向について

RSA署名方式の安全性を巡る研究動向について RSA RSA RSA RSA RSA RSA PSSRSA PSS RSARSA PSS RSA PSS RSARSA-PSS E-mail:mayumi.saitou@boj.or.jp RSARSA PKCS ISO ISO IPS ANS X RSARSA RSA RSA RSA RSA RSA RSA bit RSA RSA PSS RSA PSS RSA ISO PKCSVer RSA

More information

Wi-Fi Wi-Fi Wi-Fi Wi-Fi SAS SAS-2 Wi-Fi i

Wi-Fi Wi-Fi Wi-Fi Wi-Fi SAS SAS-2 Wi-Fi i 26 A Study on Secure Remote Control Methods 1175078 2015 2 27 Wi-Fi Wi-Fi Wi-Fi Wi-Fi SAS SAS-2 Wi-Fi i Abstract A Study on Secure Remote Control Methods SHINGAI, Tatsuro In recent years, communication

More information

°Å¹æ¥Ï¥Ã¥·¥å´Ø¿ô

°Å¹æ¥Ï¥Ã¥·¥å´Ø¿ô 1 / 37 (Cryptographic Hash Functions) H : {0, 1} {0, 1} l (Unkeyed hash function) (MDC: Manipulation Detection Code) (Keyed hash function) (MAC: Message Authentication Code) 2 / 37 OAEP (One-wayness) (Preimage

More information

#2 (IISEC)

#2 (IISEC) #2 (IISEC) 2007 10 6 E Y 2 = F (X) E(F p ) E : Y 2 = F (X) = X 3 + AX + B, A, B F p E(F p ) = {(x, y) F 2 p y2 = F (x)} {P } P : E(F p ) E F p - Given: E/F p : EC, P E(F p ), Q P Find: x Z/NZ s.t. Q =

More information

2011 Future University Hakodate 2011 System Information Science Practice Group Report Project Name Visualization of Code-Breaking Group Name Implemati

2011 Future University Hakodate 2011 System Information Science Practice Group Report Project Name Visualization of Code-Breaking Group Name Implemati 2011 Future University Hakodate 2011 System Information Science Practice Group Report Project Name Group Name Implemation Group /Project No. 13-C /Project Leader 1009087 Takahiro Okubo /Group Leader 1009087

More information

特集セキュリティ基盤技術/紛失通信プロトコルの考察193 特集 ネットワークセキュリティ特集 4-3 紛失通信プロトコルの考察 4-3 A Survey on Oblivious Transfer Protocols Le Trieu Phong Le Trieu Phong 要旨 本論文では 公開

特集セキュリティ基盤技術/紛失通信プロトコルの考察193 特集 ネットワークセキュリティ特集 4-3 紛失通信プロトコルの考察 4-3 A Survey on Oblivious Transfer Protocols Le Trieu Phong Le Trieu Phong 要旨 本論文では 公開 セキュリティ基盤技術/紛失通信プロトコルの考察193 ネットワークセキュリティ 4-3 紛失通信プロトコルの考察 4-3 A Survey on Oblivious Transfer Protocols Le Trieu Phong Le Trieu Phong 要旨 本論文では 公開鍵による暗号化スキームから紛失通信 (OT) プロトコルを構築することに関する考 察を行う 送信者と受信者の双方が誠実であることを想定した単純な

More information

untitled

untitled API API Part 1 10API 25 10API Part2 Copyright (c) 2004 NPO Page 2 Copyright (C) 2004 NPO JNSA 1 API API Wassenaar API Copyright (c) 2004 NPO Page 4 Copyright (C) 2004 NPO JNSA 2 56 512512 112 IC 1 I II

More information

2011 Future University Hakodate 2011 System Information Science Practice Group Report Project Name Visualization of Code-Breaking RSA Group Name RSA C

2011 Future University Hakodate 2011 System Information Science Practice Group Report Project Name Visualization of Code-Breaking RSA Group Name RSA C 2011 Future University Hakodate 2011 System Information Science Practice Group Report Project Name RSA Group Name RSA Code Elliptic Curve Cryptograrhy Group /Project No. 13-B /Project Leader 1009087 Takahiro

More information

x, y x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = 15 xy (x y) (x + y) xy (x y) (x y) ( x 2 + xy + y 2) = 15 (x y)

x, y x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = 15 xy (x y) (x + y) xy (x y) (x y) ( x 2 + xy + y 2) = 15 (x y) x, y x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = 15 1 1977 x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = 15 xy (x y) (x + y) xy (x y) (x y) ( x 2 + xy + y 2) = 15 (x y) ( x 2 y + xy 2 x 2 2xy y 2) = 15 (x y) (x + y) (xy

More information

Literacy 2 Mathematica Mathematica 3 Hiroshi Toyoizumi Univ. of Aizu REFERENCES [1] C.P Williams [2] [3] 1 Literacy 2 Mathematica Ma

Literacy 2 Mathematica Mathematica 3 Hiroshi Toyoizumi Univ. of Aizu REFERENCES [1] C.P Williams [2] [3] 1 Literacy 2 Mathematica Ma Mathematica 3 Hiroshi Toyoizumi Univ. of Aizu toyo@u-aizu.ac.jp REFERENCES [1] C.P Williams [2] [3] 1 Mathematica Mathematica 2 1 PKIPublic Key Infrustructure 3 4 2 5 6 3 RSA 3Ronald RivestAdi ShamirLeonald

More information

CryptoGame201712

CryptoGame201712 2017.12.22 9 (CRISMATH 2017) n l l 2 n A B n l à l à l à A \ B (, ) (, ) (, ) (, ) 3 n n n l n l A \ B ( -1, -1 ) ( -10, 0 ) ( 0, -10 ) ( -3, -3 ) 4 n l vs pk b m 0, m 1 b R {0,1} c c = Enc pk (m b ) n

More information

03.›F“ª/‚SŒÊŁÏ“X*

03.›F“ª/‚SŒÊŁÏ“X* RSA RSA RSA GemplusCoron Naccache Stern Coron-Naccache-SternRSA ISO/IEC IC RSA Coron RSA ISO/IEC Coron-Naccache-Stern ISO/IEC JTC1/SC RSA RSARSA RSA IC GemplusCoron Naccache Stern RSA Coron-Naccache-SternCNS

More information

クラウドストレージサービスにおける安全なキー ワード検索 How to Keyword-search securely in Cloud Storage Service 黒澤 馨 Kaoru KUROSAWA アブストラクト クラウドストレージサービスは既に商用化されており グーグル アマゾンなど多

クラウドストレージサービスにおける安全なキー ワード検索 How to Keyword-search securely in Cloud Storage Service 黒澤 馨 Kaoru KUROSAWA アブストラクト クラウドストレージサービスは既に商用化されており グーグル アマゾンなど多 クラウドストレージサービスにおける安全なキー ワード検索 How to Keyword-search securely in Cloud torage ervice 黒澤 馨 Kaoru KUROAWA アブストラクト クラウドストレージサービスは既に商用化されており グーグル アマゾンなど多くの IT 企業によってサー ビスが提供されている 各ファイルは暗号化した上で保存した方が安全であるが その反面

More information

Vol. 46 No ) 4),5) (1) (2) 5) 6) 7) (3) (4) 8) 11) 12),13) 1 14) 17) 18) 19) 20) 2 2

Vol. 46 No ) 4),5) (1) (2) 5) 6) 7) (3) (4) 8) 11) 12),13) 1 14) 17) 18) 19) 20) 2 2 Vol. 46 No. 1 Jan. 2005 Proof-Carrying Code Proof Hiding in Interactive Proof-carrying Code and Its Applications Yasuyuki Tsukada Proof-carrying code (PCC) is a promising new mechanism that can protect

More information

2008 (2008/09/30) 1 ISBN 7 1.1 ISBN................................ 7 1.2.......................... 8 1.3................................ 9 1.4 ISBN.............................. 12 2 13 2.1.....................

More information

(check matrices and minimum distances) H : a check matrix of C the minimum distance d = (the minimum # of column vectors of H which are linearly depen

(check matrices and minimum distances) H : a check matrix of C the minimum distance d = (the minimum # of column vectors of H which are linearly depen Hamming (Hamming codes) c 1 # of the lines in F q c through the origin n = qc 1 q 1 Choose a direction vector h i for each line. No two vectors are colinear. A linearly dependent system of h i s consists

More information

Vol.57 No (Dec. 2016) CHAP 1,a) , CHAP 1 CHAP CHAP CHAP 2 Proposal and Evaluation of Methods for Mounting Protocol of M

Vol.57 No (Dec. 2016) CHAP 1,a) , CHAP 1 CHAP CHAP CHAP 2 Proposal and Evaluation of Methods for Mounting Protocol of M CHAP 1,a) 2016 3 10, 2016 9 6 CHAP 1 CHAP CHAP CHAP 2 Proposal and Evaluation of Methods for Mounting Protocol of Multi-factor Authentication over CHAP Only Masaki Inamura 1,a) Received: March 10, 2016,

More information

7,, i

7,, i 23 Research of the authentication method on the two dimensional code 1145111 2012 2 13 7,, i Abstract Research of the authentication method on the two dimensional code Karita Koichiro Recently, the two

More information

論理学入門 講義ノート email: mitsu@abelardfletkeioacjp Copyright c 1995 by the author ll right reserved 1 1 3 2 5 3 7 31 7 32 9 33 13 4 29 41 33 42 38 5 45 51 45 52 47 3 1 19 [ 1] Begin at the beginning [ 2] [

More information

1 UTF Youtube ( ) / 30

1 UTF Youtube ( ) / 30 2011 11 16 ( ) 2011 11 16 1 / 30 1 UTF 10 2 2 16 2 2 0 3 Youtube ( ) 2011 11 16 2 / 30 4 5 ad bc = 0 6 7 (a, b, a x + b y) (c, d, c x + d y) (1, x), (2, y) ( ) 2011 11 16 3 / 30 8 2 01001110 10100011 (

More information

Microsoft PowerPoint - 暗号技術の発展.pptx

Microsoft PowerPoint - 暗号技術の発展.pptx 08 年 度 特 別 講 義 X 暗 号 技 術 の 発 展 古 典 暗 号 からIDベース 暗 号 まで 08.09.01 有 田 正 剛 1 k 1,k 2 : 鍵 E : 暗 号 化 アルゴリズム D : 復 号 アルゴリズム 暗 号 k 1 m k 2 送 信 者 c 受 信 者 c E k1 (m) m D k2 (c) m Eve? 2 目 次 1. 古 典 暗 号 2. ブロック 暗

More information

x = a 1 f (a r, a + r) f(a) r a f f(a) 2 2. (a, b) 2 f (a, b) r f(a, b) r (a, b) f f(a, b)

x = a 1 f (a r, a + r) f(a) r a f f(a) 2 2. (a, b) 2 f (a, b) r f(a, b) r (a, b) f f(a, b) 2011 I 2 II III 17, 18, 19 7 7 1 2 2 2 1 2 1 1 1.1.............................. 2 1.2 : 1.................... 4 1.2.1 2............................... 5 1.3 : 2.................... 5 1.3.1 2.....................................

More information

Test 1

Test 1 PowerBuilder Engineering, Information Technology and Solutions Group ... 3 PBCrypto... 3 PowerBuilder Exception JCE Exceptions... 4 PBCrypto... 4 PBCrypto API... 5 CreateRSAKeyPair... 5 DecryptCipherTextUsingBlockCipher...

More information

2 ( ) i

2 ( ) i 25 Study on Rating System in Multi-player Games with Imperfect Information 1165069 2014 2 28 2 ( ) i ii Abstract Study on Rating System in Multi-player Games with Imperfect Information Shigehiko MORITA

More information

°Å¹æµ»½Ñ¤Î¿ôÍý¤È¤·¤¯¤ß --- ¥á¡¼¥ë¤Ç¤¸¤ã¤ó¤±¤ó¡©¤¹¤ëÊýË¡ ---

°Å¹æµ»½Ñ¤Î¿ôÍý¤È¤·¤¯¤ß  --- ¥á¡¼¥ë¤Ç¤¸¤ã¤ó¤±¤ó¡©¤¹¤ëÊýË¡ --- .... 1 22 9 17 1 / 44 1 (9/17) 2 (10/22) P2P 3 (11/12) 2 / 44 ogawa is.uec.ac.jp http://www.quest.is.uec.ac.jp/ogawa/ http://www.is.uec.ac.jp/ 3 / 44 ARPANet (1969) 4 / 44 M. Blum ( ), Coin Flipping by

More information

:00-16:10

:00-16:10 3 3 2007 8 10 13:00-16:10 2 Diffie-Hellman (1976) K K p:, b [1, p 1] Given: p: prime, b [1, p 1], s.t. {b i i [0, p 2]} = {1,..., p 1} a {b i i [0, p 2]} Find: x [0, p 2] s.t. a b x mod p Ind b a := x

More information

paper.dvi

paper.dvi 28 Confined Decoding System for Medical Data Distributed by Secret Sharing Scheme and Its Security Evaluation 1195046 2017 3 6 DMAT i Abstract Confined Decoding System for Medical Data Distributed by Secret

More information

n PSMT(Perfectly Secure Message Transmission) PSMT

n PSMT(Perfectly Secure Message Transmission) PSMT 23 n jail 200802991 1 1 5 1.1.................................... 5 2 n 7 2.1 PSMT(Perfectly Secure Message Transmission)............ 8 2.1.1 PSMT................. 8 2.1.2 PSMT...........................

More information

(4) ω t(x) = 1 ω min Ω ( (I C (y))) min 0 < ω < C A C = 1 (5) ω (5) t transmission map tmap 1 4(a) 2. 3 2. 2 t 4(a) t tmap RGB 2 (a) RGB (A), (B), (C)

(4) ω t(x) = 1 ω min Ω ( (I C (y))) min 0 < ω < C A C = 1 (5) ω (5) t transmission map tmap 1 4(a) 2. 3 2. 2 t 4(a) t tmap RGB 2 (a) RGB (A), (B), (C) (MIRU2011) 2011 7 890 0065 1 21 40 105-6691 1 1 1 731 3194 3 4 1 338 8570 255 346 8524 1836 1 E-mail: {fukumoto,kawasaki}@ibe.kagoshima-u.ac.jp, ryo-f@hiroshima-cu.ac.jp, fukuda@cv.ics.saitama-u.ac.jp,

More information

Abstract Gale-Shapley 2 (1) 2 (2) (1)

Abstract Gale-Shapley 2 (1) 2 (2) (1) ( ) 2011 3 Abstract Gale-Shapley 2 (1) 2 (2) (1) 1 1 1.1........................................... 1 1.2......................................... 2 2 4 2.1................................... 4 2.1.1 Gale-Shapley..........................

More information

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

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 Vol. 52 No. 9 2674 2685 (Sep. 2011) 3 1 1 1 1 1 3 3 semi-honest malicious CPU Intel Core2 Quad 3.0 GHz RAM 4GB 1 32 1 1.6 µ 3 Privacy-Preserving Data Mining A Lightweight Three-party Secure Function Evaluation

More information

IMES DISCUSSION PAPER SERIES Discuss ssion Paper No. 97-J-11 INSTITUTE FOR MONETARY AND ECONOMIC STUDIES BANK OF JAPAN 100-91 203 IMES Discuss ssion Paper Series 97-J-11 1997 7 JEL : L86, Z00 * ** (E-mail:

More information

日本感性工学会論文誌

日本感性工学会論文誌 pp.343-351 2013 Changes in Three Attributes of Color by Reproduction of Memorized Colors Hiroaki MIYAKE, Takeshi KINOSHITA and Atsushi OSA Graduate School of Science and Engineering, Yamaguchi University,

More information

#include #include #include int gcd( int a, int b) { if ( b == 0 ) return a; else { int c = a % b; return gcd( b, c); } /* if */ } int main() { int a = 60; int b = 45; int

More information

,.,. NP,., ,.,,.,.,,, (PCA)...,,. Tipping and Bishop (1999) PCA. (PPCA)., (Ilin and Raiko, 2010). PPCA EM., , tatsukaw

,.,. NP,., ,.,,.,.,,, (PCA)...,,. Tipping and Bishop (1999) PCA. (PPCA)., (Ilin and Raiko, 2010). PPCA EM., , tatsukaw ,.,. NP,.,. 1 1.1.,.,,.,.,,,. 2. 1.1.1 (PCA)...,,. Tipping and Bishop (1999) PCA. (PPCA)., (Ilin and Raiko, 2010). PPCA EM., 152-8552 2-12-1, tatsukawa.m.aa@m.titech.ac.jp, 190-8562 10-3, mirai@ism.ac.jp

More information

one way two way (talk back) (... ) C.E.Shannon 1948 A Mathematical theory of communication. 1 ( ) 0 ( ) 1

one way two way (talk back) (... ) C.E.Shannon 1948 A Mathematical theory of communication. 1 ( ) 0 ( ) 1 1 1.1 1.2 one way two way (talk back) (... ) 1.3 0 C.E.Shannon 1948 A Mathematical theory of communication. 1 ( ) 0 ( ) 1 ( (coding theory)) 2 2.1 (convolution code) (block code), 3 3.1 Q q Q n Q n 1 Q

More information

IPSEC-VPN IPsec(Security Architecture for Internet Protocol) IP SA(Security Association, ) SA IKE IKE 1 1 ISAKMP SA( ) IKE 2 2 IPSec SA( 1 ) IPs

IPSEC-VPN IPsec(Security Architecture for Internet Protocol) IP SA(Security Association, ) SA IKE IKE 1 1 ISAKMP SA( ) IKE 2 2 IPSec SA( 1 ) IPs IPSEC VPN IPSEC-VPN IPsec(Security Architecture for Internet Protocol) IP SA(Security Association, ) SA IKE 1 2 2 IKE 1 1 ISAKMP SA( ) IKE 2 2 IPSec SA( 1 ) IPsec SA IKE Initiator Responder IPsec-VPN ISAKMP

More information

ICカード利用システムにおいて新たに顕現化したPre-play attackとその対策

ICカード利用システムにおいて新たに顕現化したPre-play attackとその対策 IC Pre-play attack IC IC IC EMV EMV 1 IC IC Pre-play attack ATM Pre-play attack Pre-play attack IC EMV Pre-play attack... E-mail: hidemitsu.izawa@boj.or.jp E-mail: katsuhisa.hirokawa@boj.or.jp / /2015.10

More information

2014 x n 1 : : :

2014 x n 1 : : : 2014 x n 1 : : 2015 1 30 : 5510113 1 x n 1 n x 2 1 = (x 1)(x+1) x 3 1 = (x 1)(x 2 +x+1) x 4 1 = (x 1)(x + 1)(x 2 + 1) x 5 1 = (x 1)(x 4 + x 3 + x 2 + x + 1) 1, 1,0 n = 105 2 1 n x n 1 Maple 1, 1,0 n 2

More information

<4D F736F F D F81798E518D6C8E9197BF33817A88C38D868B5A8F70834B D31292E646F63>

<4D F736F F D F81798E518D6C8E9197BF33817A88C38D868B5A8F70834B D31292E646F63> 参考資料 3 CRYPTREC 暗号技術ガイドライン (SHA-1) 2014 年 3 月 独立行政法人情報通信研究機構独立行政法人情報処理推進機構 目次 1. 本書の位置付け... 1 1.1. 本書の目的... 1 1.2. 本書の構成... 1 1.3. 注意事項... 1 2. ハッシュ関数 SHA-1 の利用について... 2 2.1. 推奨されない利用範囲... 2 2.2. 許容される利用範囲...

More information

II Time-stamp: <05/09/30 17:14:06 waki> ii

II Time-stamp: <05/09/30 17:14:06 waki> ii II waki@cc.hirosaki-u.ac.jp 18 1 30 II Time-stamp: ii 1 1 1.1.................................................. 1 1.2................................................... 3 1.3..................................................

More information

I, II 1, A = A 4 : 6 = max{ A, } A A 10 10%

I, II 1, A = A 4 : 6 = max{ A, } A A 10 10% 1 2006.4.17. A 3-312 tel: 092-726-4774, e-mail: hara@math.kyushu-u.ac.jp, http://www.math.kyushu-u.ac.jp/ hara/lectures/lectures-j.html Office hours: B A I ɛ-δ ɛ-δ 1. 2. A 1. 1. 2. 3. 4. 5. 2. ɛ-δ 1. ɛ-n

More information

katagaitai workshop winter

katagaitai workshop winter katagaitai workshop 2018 winter 0CTF Finals: Authentication & Secrecy Shiho Midorikawa Shiho Midorikawa katagaitai workshop winter March 18, 2018 1 / 142 Introduction Introduction Shiho Midorikawa katagaitai

More information

1

1 VM Secure Processor for Protecting VM and its Application to Authentication 26 2 6 48-126444 1 OS OS TPM Trusted Boot TPM Trusted Boot OS TPM Trusted Boot OS OS OS OS OS OS VM VM 2 1 1 2 3 2.1 DRM...................................

More information

guideline_1_0.dvi

guideline_1_0.dvi Version 1.0 ( 22 5 ) cflkanta Matsuura Laboratory 2010, all rights reserved. I 3 1 3 2 3 3 4 II 8 4 8 5 9 5.1......................... 9 5.2......................... 10 5.3......................... 10

More information

Gray [6] cross tabulation CUBE, ROLL UP Johnson [7] pivoting SQL 3. SuperSQL SuperSQL SuperSQL SQL [1] [2] SQL SELECT GENERATE <media> <TFE> GENER- AT

Gray [6] cross tabulation CUBE, ROLL UP Johnson [7] pivoting SQL 3. SuperSQL SuperSQL SuperSQL SQL [1] [2] SQL SELECT GENERATE <media> <TFE> GENER- AT DEIM Forum 2017 E3-1 SuperSQL 223 8522 3 14 1 E-mail: {tabata,goto}@db.ics.keio.ac.jp, toyama@ics.keio.ac.jp,,,, SuperSQL SuperSQL, SuperSQL. SuperSQL 1. SuperSQL, Cross table, SQL,. 1 1 2 4. 1 SuperSQL

More information

光学

光学 Fundamentals of Projector-Camera Systems and Their Calibration Methods Takayuki OKATANI To make the images projected by projector s appear as desired, it is e ective and sometimes an only choice to capture

More information

λ(t) (t) t ( ) (Mean Time to Failure) MTTF = 0 R(t)dt = /λ 00 (MTTF) MTTF λ = 00 MTTF= /λ MTTF= 0 2 (0 9 ) =0 7 () MTTF=

λ(t) (t) t ( ) (Mean Time to Failure) MTTF = 0 R(t)dt = /λ 00 (MTTF) MTTF λ = 00 MTTF= /λ MTTF= 0 2 (0 9 ) =0 7 () MTTF= 2003 7..2 R(t) t R(0) =, R( ) =0 λ(t) t R(t) λ(t) = R(t) dr(t) t, R(t) = exp ( λ(t)dt) dt 0 λ(t) (t) t ( ) 0 9 0 0 300 (Mean Time to Failure) MTTF = 0 R(t)dt = /λ 00 (MTTF) 00 000 MTTF λ = 00 MTTF= /λ

More information

1 DHT Fig. 1 Example of DHT 2 Successor Fig. 2 Example of Successor 2.1 Distributed Hash Table key key value O(1) DHT DHT 1 DHT 1 ID key ID IP value D

1 DHT Fig. 1 Example of DHT 2 Successor Fig. 2 Example of Successor 2.1 Distributed Hash Table key key value O(1) DHT DHT 1 DHT 1 ID key ID IP value D P2P 1,a) 1 1 Peer-to-Peer P2P P2P P2P Chord P2P Chord Consideration for Efficient Construction of Distributed Hash Trees on P2P Systems Taihei Higuchi 1,a) Masakazu Soshi 1 Tomoyuki Asaeda 1 Abstract:

More information

Computational Semantics 1 category specificity Warrington (1975); Warrington & Shallice (1979, 1984) 2 basic level superiority 3 super-ordinate catego

Computational Semantics 1 category specificity Warrington (1975); Warrington & Shallice (1979, 1984) 2 basic level superiority 3 super-ordinate catego Computational Semantics 1 category specificity Warrington (1975); Warrington & Shallice (1979, 1984) 2 basic level superiority 3 super-ordinate category preservation 1 / 13 analogy by vector space Figure

More information

セアラの暗号

セアラの暗号 1 Cayley-Purser 1 Sarah Flannery 16 1 [1] [1] [1]314 www.cayley-purser.ie http://cryptome.org/flannery-cp.htm [2] Cryptography: An Investigation of a New Algorithm vs. the RSA(1999 RSA 1999 9 11 2 (17

More information

ii

ii I05-010 : 19 1 ii k + 1 2 DS 198 20 32 1 1 iii ii iv v vi 1 1 2 2 3 3 3.1.................................... 3 3.2............................. 4 3.3.............................. 6 3.4.......................................

More information

インターネット概論 第07回(2004/11/12) 「SFC-CNSの現状」

インターネット概論 第07回(2004/11/12) 「SFC-CNSの現状」 / / / : AES 128bit) 196bit 256bit 128bit) 10 12 14 196bit) 12 12 14 256bit) 14 14 14 (n, e) (n, d) M M : 2 ( 101 5) [e ] [e ] n = p * q (p q ) (n) = (p-1)(q-1) gcd( (n), e) = 1; 1 < e < (n) d = e^-1

More information

25 11M15133 0.40 0.44 n O(n 2 ) O(n) 0.33 0.52 O(n) 0.36 0.52 O(n) 2 0.48 0.52

25 11M15133 0.40 0.44 n O(n 2 ) O(n) 0.33 0.52 O(n) 0.36 0.52 O(n) 2 0.48 0.52 26 1 11M15133 25 11M15133 0.40 0.44 n O(n 2 ) O(n) 0.33 0.52 O(n) 0.36 0.52 O(n) 2 0.48 0.52 1 2 2 4 2.1.............................. 4 2.2.................................. 5 2.2.1...........................

More information

通信プロトコルの認証技術

通信プロトコルの認証技術 PKI IPsec/SSL IETF (http://www.netcocoon.com) 2004.12.9 IPsec ESP,AH,IPComp DOI:SA IKE SA ISAKMP IKE ESP IKE AH DOI Oakley ISAKMP IPComp SKEME IPsec IPv4TCP + IPv6TCP + IPv4 AH TCP + IPv6 AH + TCP IPv4

More information

(Visual Secret Sharing Scheme) VSSS VSSS 3 i

(Visual Secret Sharing Scheme) VSSS VSSS 3 i 13 A Visual Secret Sharing Scheme for Continuous Color Images 10066 14 8 (Visual Secret Sharing Scheme) VSSS VSSS 3 i Abstract A Visual Secret Sharing Scheme for Continuous Color Images Tomoe Ogawa The

More information

IPSJ SIG Technical Report Secret Tap Secret Tap Secret Flick 1 An Examination of Icon-based User Authentication Method Using Flick Input for

IPSJ SIG Technical Report Secret Tap Secret Tap Secret Flick 1 An Examination of Icon-based User Authentication Method Using Flick Input for 1 2 3 3 1 Secret Tap Secret Tap Secret Flick 1 An Examination of Icon-based User Authentication Method Using Flick Input for Mobile Terminals Kaoru Wasai 1 Fumio Sugai 2 Yosihiro Kita 3 Mi RangPark 3 Naonobu

More information

YMS-VPN1_User_Manual

YMS-VPN1_User_Manual YAMAHA VPN YMS-VPN1 2007 12 YAMAHA VPN YMS-VPN1 YMS-VPN1 RT Windows PC IPsec VPN 2000-2002 SSH Communications Security Corp 2004-2007 SafeNet Inc. 2004-2007 dit Co., Ltd. 2006-2007 YAMAHA CORPORATION MicrosoftWindows

More information

THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS TECHNICAL REPORT OF IEICE {s-kasihr, wakamiya,

THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS TECHNICAL REPORT OF IEICE {s-kasihr, wakamiya, THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS TECHNICAL REPORT OF IEICE. 565-0871 1 5 E-mail: {s-kasihr, wakamiya, murata}@ist.osaka-u.ac.jp PC 70% Design, implementation, and evaluation

More information

.1 z = e x +xy y z y 1 1 x 0 1 z x y α β γ z = αx + βy + γ (.1) ax + by + cz = d (.1') a, b, c, d x-y-z (a, b, c). x-y-z 3 (0,

.1 z = e x +xy y z y 1 1 x 0 1 z x y α β γ z = αx + βy + γ (.1) ax + by + cz = d (.1') a, b, c, d x-y-z (a, b, c). x-y-z 3 (0, .1.1 Y K L Y = K 1 3 L 3 L K K (K + ) 1 1 3 L 3 K 3 L 3 K 0 (K + K) 1 3 L 3 K 1 3 L 3 lim K 0 K = L (K + K) 1 3 K 1 3 3 lim K 0 K = 1 3 K 3 L 3 z = f(x, y) x y z x-y-z.1 z = e x +xy y 3 x-y ( ) z 0 f(x,

More information

( [1]) (1) ( ) 1: ( ) 2 2.1,,, X Y f X Y (a mapping, a map) X ( ) x Y f(x) X Y, f X Y f : X Y, X f Y f : X Y X Y f f 1 : X 1 Y 1 f 2 : X 2 Y 2 2 (X 1

( [1]) (1) ( ) 1: ( ) 2 2.1,,, X Y f X Y (a mapping, a map) X ( ) x Y f(x) X Y, f X Y f : X Y, X f Y f : X Y X Y f f 1 : X 1 Y 1 f 2 : X 2 Y 2 2 (X 1 2013 5 11, 2014 11 29 WWW ( ) ( ) (2014/7/6) 1 (a mapping, a map) (function) ( ) ( ) 1.1 ( ) X = {,, }, Y = {, } f( ) =, f( ) =, f( ) = f : X Y 1.1 ( ) (1) ( ) ( 1 ) (2) 1 function 1 ( [1]) (1) ( ) 1:

More information

電子マネー・システムにおけるセキュリティ対策:リスク管理に焦点を当てて

電子マネー・システムにおけるセキュリティ対策:リスク管理に焦点を当てて 1999 IC IC 2008 2 5 10 E-mail: masataka.suzuki@boj.or.jp E-mail: hirokawa@imes.boj.or.jp E-mail: une@imes.boj.or.jp //2008.8 39 1. 1990 2007 1 IC 1 1 20072006 2007 1 Edy Edy IC 2007 2 22 IC PASMO IC 2008

More information

Web Basic Web SAS-2 Web SAS-2 i

Web Basic Web SAS-2 Web SAS-2 i 19 Development of moving image delivery system for elementary school 1080337 2008 3 10 Web Basic Web SAS-2 Web SAS-2 i Abstract Development of moving image delivery system for elementary school Ayuko INOUE

More information

system02.dvi

system02.dvi 2003 2 2003 4 24 13:15-14:45 : IP DNS SSH SCP 1 HTTP 2 FTP TelnetGopher HTTP HTTP 2 IP 2.1 IP PC1 1 IPv4 IP 8 4 32 192.168.6.18 42 (2 32 ) IP IP LAN LAN LAN ABC 3 (Table 1) 2.2 LAN Table 1 10.0.0.010.255.255.255

More information

untitled

untitled IT E- IT http://www.ipa.go.jp/security/ CERT/CC http://www.cert.org/stats/#alerts IPA IPA 2004 52,151 IT 2003 12 Yahoo 451 40 2002 4 18 IT 1/14 2.1 DoS(Denial of Access) IDS(Intrusion Detection System)

More information

,,,,., C Java,,.,,.,., ,,.,, i

,,,,., C Java,,.,,.,., ,,.,, i 24 Development of the programming s learning tool for children be derived from maze 1130353 2013 3 1 ,,,,., C Java,,.,,.,., 1 6 1 2.,,.,, i Abstract Development of the programming s learning tool for children

More information

JST CREST at JST CREST 1

JST CREST at JST CREST 1 JST CREST at JST CREST 1 NP 2 3 I F q : q F q [x 1,..., x k ]: F q x 1,..., x k : k p = (p 1,..., p k ) T F k q : n c = (c 1,..., c n ) T F n q T : x 1,..., x k n E(x) F q [x 1,..., x k ] n : p c c = E(p)

More information

IP Management Within Universities: Experiences in the US

IP Management Within Universities: Experiences in the US yuko.harayama@most.tohoku.ac.jp 17/3/2004 1 Ref. Sandelin TLO expertise Ref. AUTM 17/3/2004 2 Ref. Heller & Eisenberg, 1998 The scientific commons is becoming privatized! (Ref. Nelson, 2003) 17/3/2004

More information

i HTTP Basi

i HTTP Basi 2006 Web page Access Control based on Broadcast Encryption Scheme 5ADRM034 i 1 1 1.1................................. 1 1.2.................................... 1 2 2 2.1......................................

More information

1 1 1 1 1 1 2 f z 2 C 1, C 2 f 2 C 1, C 2 f(c 2 ) C 2 f(c 1 ) z C 1 f f(z) xy uv ( u v ) = ( a b c d ) ( x y ) + ( p q ) (p + b, q + d) 1 (p + a, q + c) 1 (p, q) 1 1 (b, d) (a, c) 2 3 2 3 a = d, c = b

More information

平成 19 年度 ( 第 29 回 ) 数学入門公開講座テキスト ( 京都大学数理解析研究所, 平成 19 ~8 年月 72 月日開催 30 日 ) 1 PCF (Programming language for Computable Functions) PCF adequacy adequacy

平成 19 年度 ( 第 29 回 ) 数学入門公開講座テキスト ( 京都大学数理解析研究所, 平成 19 ~8 年月 72 月日開催 30 日 ) 1 PCF (Programming language for Computable Functions) PCF adequacy adequacy 1 PCF (Programming language for Computable Functions) PCF adequacy adequacy 2 N X Y X Y f (x) f x f x y z (( f x) y) z = (( f (x))(y))(z) X Y x e X Y λx. e x x 2 + x + 1 λx. x 2 + x + 1 3 PCF 3.1 PCF PCF

More information

25 II :30 16:00 (1),. Do not open this problem booklet until the start of the examination is announced. (2) 3.. Answer the following 3 proble

25 II :30 16:00 (1),. Do not open this problem booklet until the start of the examination is announced. (2) 3.. Answer the following 3 proble 25 II 25 2 6 13:30 16:00 (1),. Do not open this problem boolet until the start of the examination is announced. (2) 3.. Answer the following 3 problems. Use the designated answer sheet for each problem.

More information

30 2014.08 2 1985 Koblitz Miller 2.1 0 field Fp p prime field Fp E Fp Fp Hasse Weil 2.2 Fp 2 P Q R R P Q O P O R Q Q O R P P xp, yp Q xq, yq yp yq R=O

30 2014.08 2 1985 Koblitz Miller 2.1 0 field Fp p prime field Fp E Fp Fp Hasse Weil 2.2 Fp 2 P Q R R P Q O P O R Q Q O R P P xp, yp Q xq, yq yp yq R=O An Internet Vote Using the Elliptic Curve Cryptosystem TAKABAYASHI Shigeki Nowadays various changes are taking place in the society by the spread of the Internet, and we will vote by the Internet using

More information

/02/ /09/ /05/ /02/ CA /11/09 OCSP SubjectAltName /12/02 SECOM Passport for Web SR

/02/ /09/ /05/ /02/ CA /11/09 OCSP SubjectAltName /12/02 SECOM Passport for Web SR for Web SR Certificate Policy Version 2.50 2017 5 23 1.00 2008/02/25 1.10 2008/09/19 1.20 2009/05/13 5 1.30 2012/02/15 5.6 CA 1.40 2012/11/09 OCSP SubjectAltName 2.00 2013/12/02 SECOM Passport for Web

More information

ASF-01

ASF-01 暗号モジュール試験及び認証制度 (JCMVP) 承認されたセキュリティ機能に関する仕様 平成 26 年 4 月 1 日独立行政法人情報処理推進機構 ASF-01 A p p r o v e d S e c u r i t y F u n c t i o n s 目次 1. 目的... 1 2. 承認されたセキュリティ機能... 1 公開鍵... 1 共通鍵... 3 ハッシュ... 4 メッセージ認証...

More information

A Japanese Word Dependency Corpus ÆüËܸì¤Îñ¸ì·¸¤ê¼õ¤±¥³¡¼¥Ñ¥¹

A Japanese Word Dependency Corpus   ÆüËܸì¤Îñ¸ì·¸¤ê¼õ¤±¥³¡¼¥Ñ¥¹ A Japanese Word Dependency Corpus 2015 3 18 Special thanks to NTT CS, 1 /27 Bunsetsu? What is it? ( ) Cf. CoNLL Multilingual Dependency Parsing [Buchholz+ 2006] (, Penn Treebank [Marcus 93]) 2 /27 1. 2.

More information

( )

( ) 18 10 01 ( ) 1 2018 4 1.1 2018............................... 4 1.2 2018......................... 5 2 2017 7 2.1 2017............................... 7 2.2 2017......................... 8 3 2016 9 3.1 2016...............................

More information

Title 疑似乱数生成器の安全性とモンテカルロ法 ( 確率数値解析に於ける諸問題,VI) Author(s) 杉田, 洋 Citation 数理解析研究所講究録 (2004), 1351: Issue Date URL

Title 疑似乱数生成器の安全性とモンテカルロ法 ( 確率数値解析に於ける諸問題,VI) Author(s) 杉田, 洋 Citation 数理解析研究所講究録 (2004), 1351: Issue Date URL Title 疑似乱数生成器の安全性とモンテカルロ法 ( 確率数値解析に於ける諸問題,VI) Author(s) 杉田, 洋 Citation 数理解析研究所講究録 (2004), 1351: 33-40 Issue Date 2004-01 URL http://hdlhandlenet/2433/64973 Right Type Departmental Bulletin Paper Textversion

More information

ESIGN-TSH 1.0 NTT

ESIGN-TSH 1.0 NTT ESIGN-TSH 10 NTT 2002 5 23 1 3 2 4 3 4 31 (I2BSP) 4 32 (BS2IP) 6 33 (BS2OSP) 6 34 (OS2BSP) 7 35 (I2OSP) 7 36 (OS2IP) 8 4 8 41 ESIGN 8 42 ESIGN 9 5 9 51 KGP-ESIGN-TSH 9 52 SP-ESIGN-TSH 9 53 VP-ESIGN-TSH

More information

楕円曲線暗号と RSA 暗号の安全性比較

楕円曲線暗号と RSA 暗号の安全性比較 RSA, RSA RSA 7 NIST SP-7 Neal Koblitz Victor Miller ECDLP (Elliptic Curve Discrete Logarithm Problem) RSA Blu-ray AACS (Advanced Access Control System) DTCP (Digital Transmission Content Protection) RSA

More information

量子暗号通信の仕組みと開発動向

量子暗号通信の仕組みと開発動向 RSA AES 1 BB84Y-00 E-mail: hitoshi.gotou-1@boj.or.jp //2009.10 107 1. 2008 10 9 20 km 1.02 Mbps 100 km 10.1 kbps 1 Gbps 10 Gbps VPN 7 km 2. 1 3 2 1 2 108 /2009.10 1 2 2 109 2 ID IC KEELOQ 1 1 EUROCRYPT2008

More information