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

Size: px

Start display at page:

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

ぜんすけよせ
4 years ago
Views:

1 1,a) , 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 Ogata 3 Masakatsu Nishigaki 1 Received: December 11, 2017, Accepted: June 8, 2018 Abstract: CPU performance has been increasing continually. To resist attacks in such a technological environment, we must increase the entropy of secrets. However, the progress of CPU performance benefits not only attackers but also legitimate users. Security schemes specifically designed to enhance legitimate users security by exploiting CPU performance have been proposed. In this paper, we call such schemes computeraided security schemes, or CASS, and classify them into two types in terms of the aiding mechanism. We propose general constructions and provide security proofs of CASS for one type. We discuss the feasibility of CASS. Keywords: cryptology, computer-aided security, general construction, symmetric key encryption, message authentication code, public key encryption, digital signature, user authentication 1. 1 Shizuoka University, Hamamatsu, Shizuoka , Japan 2 Hitachi Ltd., Yokohama, Kanagawa , Japan 3 Tokyo Institute of Technology, Meguro, Tokyo , Japan a) yasu @gmail.com CPU c 2018 Information Processing Society of Japan 1557

2 PUF [1] [2] PUF CPU CASS bcrypt [3] PBKDF2 [4] [7] f s short s long f(s short ) CASS f L [5], [6] f [6] f(s short ) s short L CASS log 2 L [6] CASS [7] CASS s short r s short r = s long s short s short r s short r r s short r h(h(s short r)) s short r CASS CASS [7] CASS CASS [7] CASS CASS &C&R CASS CASS CASS CASS 2. CASS s long k s long k = 128 [8] CASS k u <k s short CASS s short s long s short CASS s long s long = s short r 2 s short s short r s short s long s short r CASS [7] r s short c 2018 Information Processing Society of Japan 1558

3 3. CASS C&R CASS Π SKE 3 (Gen, Enc, Dec) Gen 1 k k s long Enc s long m {0, 1} l(k) c l(k) k {0, 1} l(k) l(k) Enc Dec s long c m Dec k s long Gen(1 k ) m Dec(s long, Enc(s long,m)) = m Π SKE IND-P2-C2 [9] IND-P2-C2 Gen(1 k ) s long m i c j c i = Enc(s long,m i ) m j = Dec(s long,c j ) (m 0,m 1 ) b c b = Enc(s long,m b ) b b = b Pr[b = b ] 1/2 ΠSKE Π SKE 3 (Ĝen, Ênc, Dec) & Ĝen 1 k str {0, 1} ku s short {0, 1} ku hint Ĝen str s short k u s short s short k u CASS & str Ênc s long s short m hint c = Ênc(s short,m,hint) Dec sshort c hint m = Dec(sshort,c,hint) k str (s short, hint) Ĝen(1 k, str) m Dec(s short, Ênc(s short,m,hint), hint) =m 1 Π SKE Π SKE (Gen, Enc, Dec) (Ĝen, Ênc, Dec) Ĝen s short hint hint IND-P2-C2 Ĝen(1 k, str) (s short, hint) hint m i c j c i = Ênc(s short,m i, hint) m j = Dec(sshort,c j, hint) (m 0,m 1 ) b c b = Ênc(s short,m b, hint) b b = b Π SKE =(Gen, Enc, Dec) ΠSKE =(Ĝen, Ênc, Dec) s short Ĝen & Ĝen(1 k, str) 1 k s long = Gen(1 k ) N m 0,...,m N 1 c 0 = Enc(s long,m 0 ),...,c N 1 = Enc(s long,m N 1 ) N (s short, hint) s long = s short r s short = str = k u hint =((m 0,c 0 ),...,(m N 1,c N 1 )) Ênc(s short,m,hint) Dec((s short r), c 0 )=m 0,...,Dec((s short r),c N 1 )=m N 1 r s long = s short r s long m c = Enc(s long,m) Dec(sshort,c,hint) Ênc s short hint s long c m = Dec(s long,c) N s long =(s short r),m 0,...,m N 1 Dec((s short r ), Enc((s short r),m 0 )) = m 0. Dec((s short r ), Enc((s short r),m N 1 )) = m N 1 r r δ(n) ΠSKE 1 δ(n) c 2018 Information Processing Society of Japan 1559

4 r δ(n) N N (1 δ(n)) r N Π SKE Π SKE δ = 2 (Nl(k) k+ku) N r r m Pr[Dec((s short r ), Enc((s short r),m)) = m] =1/2 l(k) δ(n) δ(n) = Pr[ r ( r) i {0,...,N 1} : Dec((s short r ), Enc((s short r),m i )) = m i ] =1 Pr[ r ( r) i {0,...,N 1} : Dec((s short r ), Enc((s short r),m i )) m i ] ( ( 1 =1 1 2 l(k) ( 1 1 2k ku 2 Nl(k) =2 Nl(k)+k ku = δ ) N ) 2 k ku 1 ) ( 2 k k u 1 2Nl(k) l(k) =k = 128 k u = 102 δ<2 128 N =2 Π SKE N δ(n) s short Ĝen s long Π SKE ΠSKE Π SKE Π SKE ΠSKE Theorem 1. Π SKE IND-P2-C2 ΠSKE IND-P2-C2 ΠSKE q IND-P2-C2 A Π SKE q + N IND-P2-C2 B ) Proof. B ΠSKE IND-P2-C2 ε A A 1/2 ± ε Π SKE IND-P2-C2 Π SKE IND-P2-C2 ΠSKE IND-P2-C2 hint ΠSKE IND-P2-C2 Π SKE IND-P2-C2 B A hint A B A A B A hint A N Gen(1 k ) s long B A hint N m 0,...,m N 1 m 0,...,m N 1 c 0 = Enc(s long,m 0 ),...,c N 1 = Enc(s long,m N 1 ) B B ((m 0,c 0 ),...,(m N 1,c N 1 )) hint A B A A B m i c j B m i m i c i = Enc(s long,m i ) A c i B c j m j = Dec(s long,c j ) A A (m 0,m 1 ) B B (m 0,m 1 ) b c b = Enc(s long,m b ) B B A c b A b B b Π SKE (1 δ(n)) r A ΠSKE IND-P2-C2 A 1/2 ± ε b = b b δ(n) A Π SKE IND-P2-C2 A b = b b B Π SKE IND-P2-C2 Pr[r ]Pr[b = b r ] +Pr[r ]Pr[b = b r ] =(1 δ(n)) Pr[b = b r ] + δ(n)pr[b = b r ] A 1/2+ε 0 <ε<1/2 b = b b c 2018 Information Processing Society of Japan 1560

5 Pr[B Π SKE IND-P2-C2 ] =1/2+ε δ(n)(1/2+ε) 1/2+ε δ(n) (1 δ(n)) Pr[b = b r ] + δ(n) 0=(1 δ(n))(1/2+ε) (1/2+ε 1 ) B ε δ(n) A 1/2 ε 0 <ε<1/2 b = b b B ε δ(n) B ε δ(n) Q.E.D. Π SKE ΠSKE Π Mac 3 (Gen, Mac, Ver ) Gen 1 k k s long Mac s long m {0, 1} t {0, 1} l {0, 1} Mac Ver s long m t b b =1 b =0 Ver *1 k s long Gen(1 k ) m Ver (s long,m,mac(s long,m)) = 1 Π Mac EUF-CMA EUF-CMA Gen(1 k ) s long m i t i = Mac(s long,m i ) m t Ver (s long,m,t )=1 ΠMac Π Mac 3 (Ĝen, Mac, Ver ) & Ĝen 1 k str {0, 1} ku *1 Mac Ver Mac s short {0, 1} ku hint Mac slong s short m hint t = Mac(sshort,m,hint) Ver sshort m t hint b b =1 b =0 k str (s short, hint) Ĝen(1 k, str) m Ver (sshort,m, Mac(sshort,m,hint), hint) =1 1 Π Mac Π Mac ΠSKE (Gen, Mac, Ver ) (Ĝen, Mac, Ver ) hint Π MAC =(Gen, Mac, Ver ) ΠMAC =(Ĝen, Mac, Ver ) & Ĝen(1 k, str) 1 k s long = Gen(1 k ) N m 0,...,m N 1 t 0 = Mac(s long,m 0 ),...,t N 1 = Mac(s long,m N 1 ) (s short, hint) s long = s short r s short = str = k u hint = ((m 0,t 0 ),..., (m N 1,t N 1 )) Mac(sshort,m,hint) Ver ((s short r), m 0,t 0 )=1,...,Ver ((s short r),m N 1,t N 1 )=1 r s long = s short r s long m t = Mac(s long,m) Ver (sshort,m,t,hint) Mac sshort hint s long s long m t b = Ver (s long,m,t) N Ver ((s short r ),m i,t i )=1 i {0,...,N 1} r r δ(n) r N Π Mac MAC CBC-MAC HMAC Ver Mac Π MAC Pr[Mac((s short r ),m i )=Mac(s long,m i )]=1/2 l c 2018 Information Processing Society of Japan 1561

6 δ(n) = 2 l N+(k ku) l N k k u N l = 256 k = 128 CBC-MAC k u = 102 δ <2 k N =1 N δ(n) Π MAC N =1 δ(1) δ(1) Π MAC ΠMAC Π MAC Π MAC Π MAC Theorem 2. Π MAC EUF-CMA ΠMAC EUF-CMA ΠMAC q EUF-CMA A Π MAC q + N EUF-CMA B Proof. Theorem 1 Theorem 1 IND-P2-C2 EUF-CMA A ΠMAC EUF-CMA ε 1 δ(n) r r r Ver ((s short r),m 0,t 0 ) 1,...,Ver ((s short r),m N 1, t N 1 ) 1 1 B A ΠMAC EUF-CMA B Π MAC EUF-CMA ε B (1 δ(n))ε >ε δ(n) Π MAC EUF-CMA Q.E.D. Π MAC ΠMAC Π PKE 3 (Gen, Enc, Dec) Gen 1 k k sk pk Gen r k l (k) Gen(1 k ; r) Enc pk m c Dec sk c m k (sk, pk) Gen(1 k ; r) m Dec(sk, Enc(pk,m)) = m Π PKE IND-CCA2 [10] IND-CCA2 IND-P2-C2 Gen(1 k ; r) (sk, pk) pk RSA [11] sk p q (p 1)(q 1) e p q PRG [12] Π PKE PRG Π PRG PKE Π PRG PKE 3 (Gen PRG, Enc, Dec) Gen PRG 1 k (sk, pk) =Gen(1 k ; PRG(seed )) seed Gen PRG k Π PKE ΠPKE PRG Gen PRG (sk, pk) Π PKE RSA 2,048 [8] s long = s short r s short c 2018 Information Processing Society of Japan 1562

7 r ΠPKE ΠPKE PRG PRG s long PRG ΠPKE ΠPKE PRG 3 (Ĝen, Ênc, Dec) & Ĝen 1 k str {0, 1} ku s short {0, 1} ku hint pk Ênc Enc Dec sshort c hint m k str (s short, hint, pk) Ĝen(1 k, str) m Dec(sshort, Ênc(pk,m), hint) =m 1 Π PKE ΠPKE PRG CASS (Gen PRG, Enc, Dec) (Ĝen, Ênc, Dec) hint ΠPKE PRG = (Gen PRG, Enc, Dec) ΠPKE = (Ĝen, Ênc, Dec) & Ĝen(1 k, str) k s long (pk, sk) =Gen PRG (1 k ; s long ) (s short, hint, pk) s long = s short r s short = str = k u hint = pk (s short, pk) Ênc(pk,m) c = Enc(pk,m) Dec(sshort,c,hint) Gen PRG (1 k ; s short r) = pk r s long = s short r sk c m = Dec(sk,c) r r Gen PRG (1 k ; s short r) = (pk, sk) Gen PRG (1 k ; s short r) = (pk, sk ) & r r sk sk Π PKE sk sk ΠPKE RSA-OAEP hint s long h(s long ) h(s long )=h(s short r) r r CASS ΠPKE Π PKE 2 1 Π PKE ΠPKE PRG PRG Π PKE 2 ΠPKE PRG ΠPKE ΠPKE PRG Π PKE PRG Π PRG PKE ΠPRG PKE ΠPKE Π PKE Π PKE PRG Π PKE Π PKE ΠPKE PRG PRG Π PKE PRG b b =0 r b =1 seed r = PRG(seed ) r b b = b Pr[b = b ] 1/2 Theorem 3. Π PKE IND-CCA2 PRG ΠPKE PRG IND-CCA2 Π PKE IND-CCA2 Π PRG PKE IND- CCA2 A PRG B Proof. A Π PKE IND-CCA2 A ΠPKE PRG IND-CCA2 A Π PKE IND-CCA2 γ (1/2 ± γ) Π PRG PKE IND-CCA2 ζ (1/2 ± ζ) Π PKE IND-CCA2 ΠPKE PRG IND-CCA2 PRG B A 2 PRG (ζ γ)/2 PRG b b =0 r b =1 seed r = PRG(seed ) B r B r Gen (sk, pk) B (sk, pk) A IND-CCA2 c 2018 Information Processing Society of Japan 1563

8 A IND-CCA2 B r b =0 A IND-CCA2 B r b =1 b =0 B b =0 A Π PKE IND-CCA2 1 (1/2 ± γ) b =1 B b =1 A ΠPKE PRG IND-CCA2 1/2 ± ζ B (1 ± γ ± ζ)/2 PRG (ζ γ)/2 Q.E.D. Π PKE PRG ΠPKE PRG ΠPKE PRG ΠPKE ΠPKE PRG Theorem 4. ΠPKE PRG IND-CCA2 ΠPKE IND-CCA2 ΠPKE q IND-CCA2 A ΠPKE PRG q IND-CCA2 B Proof. ΠPKE hint = pk Theorem 1 2 ΠPKE PRG IND-CCA2 ΠPKE IND-CCA2 B hint pk A B A A A ΠPKE IND-CCA2 ε A 1/2 ± ε seed seed (pk, sk) Gen PRG (1 k ; seed ) B pk B pk A B A A B c i B c i c i m i = Dec(sk,c i ) A m i A (m 0,m 1 ) B B (m 0,m 1 ) b c b = Enc(pk,m b ) B B A c b A b B b A ΠPKE IND-CCA2 A 1/2 ± ε b = b B 1/2 ± ε Π PRG PKE IND-CCA2 ε Q.E.D. ΠPKE PRG ΠPKE Π DS 3 (Gen, Sig, Ver ) Gen 1 k k sk pk Gen r k l (k) Gen(1 k ; r) Sig sk m σ Ver pk m σ b b =1 b =0 k (sk, pk) Gen(1 k ; r) m Ver (pk,m,sig(sk,m)) = 1 Π DS EUF-CMA [13] EUF-CMA MAC EUF-CMA Gen(1 k ; r) (sk, pk) pk Π DS PRG ΠDS PRG ΠDS PRG 3 (Gen PRG, Sig, Ver ) Gen PRG 1 k (sk, pk) = Gen(1 k ; PRG(seed )) seed Gen PRG k Π DS ΠDS PRG Gen PRG (sk, pk) Π DS PRG ΠDS ΠDS PRG 3 (Ĝen, Ŝig, Ver ) & Ĝen 1 k str {0, 1} ku s short {0, 1} ku hint pk Ŝig s short m hint σ Ver c 2018 Information Processing Society of Japan 1564

9 Ver k str (s short, hint, pk) Ĝen(1 k, str) m Ver (pk,m,ŝig(s short,m,hint)) = 1 1 Π DS Π DS PRG CASS (Gen PRG, Sig, Ver ) (Ĝen, Ŝig, Ver ) hint Π PRG DS =(Gen PRG, Sig, Ver ) ΠDS =(Ĝen, Ŝig, Ver ) & Ĝen(1 k, str) k s long (pk, sk) =Gen PRG (1 k ; s long ) (s short, hint, pk) s long = s short r s short = str = k u hint = pk (s short, pk) Ŝig(s short,m,hint) Gen PRG (1 k ; s short r)=pk r s long = s short r sk m σ = Sig(sk,m) Ver (pk,m,σ) pk m σ b = Ver (pk,m,σ) r r Gen PRG (1 k ; s short r) = (pk, sk) Gen PRG (1 k ; s short r )=(pk, sk ) & r r sk sk Π DS sk sk ΠDS Π PRG DS hint h(s long ) Π PKE ΠDS 2 Π DS ΠDS PRG ΠDS Theorem 5. Π DS EUF-CMA PRG Π DS PRG EUF-CMA Π DS EUF-CMA Π DS PRG EUF-CMA A PRG B Proof. Theorem 3 IND-CCA2 EUF- CMA Q.E.D. Π DS PRG Π DS PRG Theorem 6. EUF-CMA ΠDS EUF-CMA ΠDS q EUF-CMA A Π PRG DS Π PRG DS q EUF-CMA B Proof. Theorem 4 Thereom 4 IND-CCA2 EUF-CMA A ΠDS EUF-CMA ε B A ΠDS EUF-CMA B ε Π PRG DS EUF-CMA Q.E.D. ΠDS PRG ΠDS 3.5 C R C&R Π CRUA 5 (Gen, Enr, CG, C 2R, Ver ) Gen 1 k k k s long Enr s long VI CG 1 k C C 2R s long C R Ver C R VI b b =1 b =0 k s long Gen(1 k ) C CG(1 k ) Ver (C, C 2R(s long,c), Enr(s long )) = 1 Π CRUA concurrent man-in-the-middle attack IMP-CMIM [16], [20] Gen(1 k ) s long Enr(s long ) VI VI c 2018 Information Processing Society of Japan 1565

10 P j *2 P j s long C j P j P j R j = C 2R(s long,c j) C C P j C R Ver (C,R, VI )=1 C&R ΠCRUA Π CRUA 5 (Ĝen, Ênr, ĈG,Ĉ2R, Ver ) & Ĝen 1 k str {0, 1} ku s long {0, 1} k s short {0, 1} ku hint Ênr Enr ĈG CG Ĉ 2R s short C hint R Ver Ver k str (s long,s short, hint) Ĝen(1 k, str) C ĈG(1 k ) Ver (C, Ĉ 2R(sshort,C,hint), Ênr(s long )) = 1 1 Π CRUA Π CRUA CASS (Gen, Enr, CG, C 2R, Ver ) (Ĝen, Ênr, ĈG,Ĉ2R, Ver ) hint Π CRUA = (Gen, Enr, CG, C 2R, Ver ) Π CRUA =(Ĝen, Ênr, ĈG,Ĉ2R, Ver ) & Ĝen(1 k, str) 1 k s long = Gen(1 k ) CG 1 k N C 0,...,C N 1 R 0 = C 2R(s long,c 0 ),...,R N 1 = C 2R(s long,c N 1 ) (s long,s short, hint) s long = s short r s short = str = k u hint =((C 0,R 0 ),...,(C N 1,R N 1 )) Ênr(s long ) Enr s long VI ĈG(1 k ) CG 1 k C C 2R(sshort,C,hint) Ver (C 0,R 0, Enr(s short r)) = 1,...,Ver (C N 1,R N 1, *2 concurrent left-concurrency Enr(s short r)) = 1 r s long = s short r s long C R = C 2R(s long,c) Ver (C, R, VI ) Ver C R VI b N MAC Ver (C i,r i, Enr(s short r )) = 1 i {0,...,N 1} r r δ(n) r N Π CRUA Π CRUA h VI = h(s long ) R = h(h(s long ),C) Ver N =1 δ(1) δ(1) δ(n) C&R Π CRUA Π CRUA ΠCRUA Π CRUA Π CRUA ΠCRUA Theorem 7. Π CRUA IMP-CMIM ΠCRUA IMP-CMIM ΠCRUA q IMP-CMIM A Π CRUA q + N IMP-CMIM B Proof. Theorem 1 2 Theorem1 2 IND-P2-C2 EUF-CMA IMP-CMIM A ΠCRUA IMP-CMIM ε A P 0,...,P q 1 B P 0,...,P q 1+N B Enr(Gen(1 k )) VI B A hint c 2018 Information Processing Society of Japan 1566

11 N CG(1 k ) C 0,...,C N 1 C 0,...,C N 1 P q,...,p q 1+N P q,...,p q 1+N R 0 = C 2R(s long,c 0 ),...,R N 1 = C 2R(s long,c N 1 ) B B ((C 0,R 0 ),...,(C N 1,R N 1 )) hint VI A B A A B C i P j B P j A C = CG(1 k ) B B A C A R B R 1 δ(n) r r r Ver (C 0,R 0, Enr(S short r )) 1,...,Ver (C N 1,R N 1, Enr(s short r )) 1 1 B A ΠCRUA IMP-CMIM B Π CRUA IMP-CMIM ε B (1 δ(n))ε >ε δ(n) Π CRUA IMP-CMIM π CRUA man-in-the-middle attack concurrent attack [14] ΠCRUA 4. CASS CASS s long s short r CPU s long r s short r s long s short CASS s short r 26 s short 102 [15] s short 102 s long = s short r r r 1 CASS s short [17] S S f G (x) f I (x) Kullback-Leibler [18] D(f G f I ) S OK /NG 2 β α β 1 α 1 β D(f G f I )=(1 β)log 2 α + β log 2 β 1 D(f G f I )= log 2 α [19] α = D(f G f I )= α 102 s short CPU s long r s short r 1 s long CASS CASS PUF [1] Gassend, B., Clarke, D., Dijk, M. and Devadas, S.: Silicon physical random functions, 9th ACM Conference c 2018 Information Processing Society of Japan 1567

on Computer and Communications Security, pp.148 160 (2002). [2] Juels, A. and Wattenberg, M.: A fuzzy commitment scheme, 6th ACM Conference on Computer and Communications Security, pp.28 36 (1999).

: Recommendation for Password-Based Key Derivation Part 1: Storage Applications, NIST Special Publication, 800-132 (2010). [5] Kelsey, J., Schneier, B., Hall, C. and Wagner, D.

Information Theory, Vol.51, No.9, pp.3292 3297 (2005). [7] Vol.55, No.9, pp.2072 2080 (2014). [8] Barker, E. and Roginsky, A.

: Characterization of Security Notions for Probabilistic Private-Key Encryption, Journal of Cryptology, Vol.19, No.1, pp.67 95 (2006). [10] Ra

12 on Computer and Communications Security, pp (2002). [2] Juels, A. and Wattenberg, M.: A fuzzy commitment scheme, 6th ACM Conference on Computer and Communications Security, pp (1999). [3] Proves, N. and Mazieres, D.: A Future-Adaptable Password Scheme, USENIX Annual Technical Conference (1999). [4] Turan, M.S., Barker, E., Burr, W. and Chen, L.: Recommendation for Password-Based Key Derivation Part 1: Storage Applications, NIST Special Publication, (2010). [5] Kelsey, J., Schneier, B., Hall, C. and Wagner, D.: Secure Applications of Low-Entropy Keys, 1997 Information Security Workshop, pp (1997). [6] Yao, F.F. and Yin, Y.L.: Design and Analysis of Password-Based Key Derivation Functions, IEEE Trans. Information Theory, Vol.51, No.9, pp (2005). [7] Vol.55, No.9, pp (2014). [8] Barker, E. and Roginsky, A.: Transitions: Recommendation for Transitioning the Use of Cryptographic Algorithms and Key Lengths, NIST Special Publication, A Revision 1 (2015). [9] Katz, J. and Yung, M.: Characterization of Security Notions for Probabilistic Private-Key Encryption, Journal of Cryptology, Vol.19, No.1, pp (2006). [10] Rackoff, C. and Simon, D.R.: Non-interactive zeroknowledge proof of knowledge and chosen ciphertext attack, Proc. Advances in Cryptology CRYPTO 91, Vol.576, pp (1991). [11] Rivest, R.L., Shamir, A. and Adleman, L.: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Comm. ACM, Vol.21, No.2, pp (1978). [12] Yao, A.C.: Theory and Applications of Trapdoor Functions, 23rd Annual Symposium on Foundations of Computer Science, pp (1982). [13] Goldwasser, S., Micali, S. and Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, Vol.17, No.2, pp (1988). [14] Bellare, M. and Palacio, A.: GQ and Schnorr Identification Schemes, Proofs of Security against Impersonation under Active and Concurrent Attacks, Advances in Cryptology CRYPTO 2002, pp (2002). [15] Fujita, M., Yamada, M., Arimura, S., Ikeya, Y. and Nishigaki, M.: An Attempt to Memorize Strong Passwords while Playing Games, Network-Based Information Systems, pp (2015). [16] Gennaro, R.: Multi-trapdoor Commitments and Their Applications to Proofs of Knowledge Secure Under Concurrent Man-in-the-Middle Attacks, Advances in Cryptology CRYPTO 2004, pp (2004). [17] Takahashi, K. and Murakami, T.: A Measure of Information Gained through Biometric Systems, Elsevier Image and Vision Computing, Vol.32, No.12, pp (2014). [18] Kullback, S. and Leibler, R.A.: On Information and Sufficiency, The Annuals of Mathematical Statistics, Vol.22, No.1, pp (1951). [19] Murakami, T., Ohki, T. and Takahashi, K.: Optimal sequential fusion for multibiometric cryptosystems, Vol.32, pp (2016). [20] Anada, H. and Arita, S.: Identification Schemes of Proofs of Ability Secure against Concurrent Man-in-the- Middle Attacks, International Conference on Provable Security, ProveSec 2010, pp (2010) SISAP Best paper 2012 IEEE BTAS Best reviewed paper c 2018 Information Processing Society of Japan 1568

13 PD c 2018 Information Processing Society of Japan 1569

( )

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