セッション鍵システム、セッション鍵提供方法、ならびに、プログラム
【課題】小さいパスワードを共有することで、証明者があるグループの一員であることをその証明者が実際に誰なのかを明かすことなく証明するセッション鍵システム等を提供する。
【解決手段】パスワードpw[1]，…，pw[n]を知るサーバ装置１５１に対して、パスワードpw[i]を知る端末装置１３１は、生成元g、乱数x、ハッシュ関数Fを用いて、gxを指定する1-out-of-n紛失通信を行い、サーバ装置１５１は、乱数yおよびpw[1]，…，pw[n]を参照して、端末装置でgygF(pw[i])の情報だけが得られるような1-out-of-n紛失通信の応答を端末装置１３１に返し、サーバ装置１５１は、(gx)yによりセッション鍵を得て、端末装置１３１は、応答からgygF(pw[i])を得て、((gygF(pw[i]))/gF(pw[i]))xによりセッション鍵を得る。
【解決手段】パスワードpw[1]，…，pw[n]を知るサーバ装置１５１に対して、パスワードpw[i]を知る端末装置１３１は、生成元g、乱数x、ハッシュ関数Fを用いて、gxを指定する1-out-of-n紛失通信を行い、サーバ装置１５１は、乱数yおよびpw[1]，…，pw[n]を参照して、端末装置でgygF(pw[i])の情報だけが得られるような1-out-of-n紛失通信の応答を端末装置１３１に返し、サーバ装置１５１は、(gx)yによりセッション鍵を得て、端末装置１３１は、応答からgygF(pw[i])を得て、((gygF(pw[i]))/gF(pw[i]))xによりセッション鍵を得る。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、セッション鍵システム、セッション鍵提供方法、ならびに、プログラムに関する。
【背景技術】
【０００２】
従来から、セッション鍵を用いることによって、電子認証や電子署名を行う技術が広く提供されている。このような技術は、以下の文献に開示されている。
【非特許文献１】C.H.Lee，X.Deng and H.Zhu，Design and Security Analysis of Anonymous Group Identification Protocols，PKC02，LNCS 2274，Springer-Verlag，pp.188-198，２００２年
【非特許文献２】W.G.Tzeng，Efficient 1-out-of-n Oblivious Transfer Schemes，PKC02，LNCS 2274，Sprinter-Verlag，pp.159-171，２００２年
【非特許文献３】C.K.Chu and W.G.Tzeng，Efficient k-out-of-n Oblivious Transfer Schemes with Adaptive and NOn-Adaptive Queries，PKC05，LNCS 3386，Sprinver-Verlag，pp.172-183，２００５年
【０００３】
ここで、[非特許文献１]では、検証者に対して、証明者がグループの一員であることを、その証明者が実際に誰なのかを明かすことなく、証明する匿名認証スキームが提案されている。
【０００４】
この技術では公開鍵暗号を利用するため、比較的長いランダムなビット列を公開鍵と秘密鍵として保有しなければならない。
【０００５】
一方、[非特許文献２][非特許文献３]では、紛失通信（Oblivious Transfer；ＯＴ）プロトコルの効率の良い実装例が開示されている。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
したがって、あらかじめ用意され管理されている辞書に含まれるような小さい低エントロピー鍵（パスワード）のみを共有するような、簡易な匿名認証スキームに対する要望は大きい。
【０００７】
本発明は、以上のような課題を解決するためになされたもので、小さいパスワードを共有することで、証明者があるグループの一員であることを、その証明者が実際に誰なのかを明かすことなく、検証者に対して証明するのに好適な、セッション鍵システム、セッション鍵提供方法、および、これらをコンピュータにおいて実現するためのプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
以上の目的を達成するため、本発明の原理にしたがって、下記の発明を開示する。
【０００９】
本発明の第１の観点に係るセッション鍵システムは、素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数Fと、を、端末装置とサーバ装置とで共有し、サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、端末装置には、当該n個のパスワードのうち、i番目のパスワードpw[i]が保有されるセッション鍵システムであって、以下のように構成する。
【００１０】
まず、端末装置は、端末選択部、端末第１計算部を備える。
【００１１】
ここで、当該i番目のパスワードpw[i]に対して、端末選択部は、体Zpの元からxを一様にランダムに選択し、端末第１計算部は、選択されたxからgxを計算する。
【００１２】
一方、サーバ装置は、サーバ選択部、サーバ第１計算部を備える。
【００１３】
ここで、サーバ選択部は、体Zpの元からyを一様にランダムに選択する。
【００１４】
一方、サーバ第１計算部は、選択されたyから、j = 1，…，nについて、
α[j] = gygF(pw[j])
を計算する。
【００１５】
さらに、端末装置は、端末第１送信部をさらに備える。
【００１６】
ここで、端末第１送信部は、計算されたgxを指定する1-out-of-n紛失通信問い合わせをサーバ装置に送信する。
【００１７】
そして、サーバ装置は、サーバ第１受信部、サーバ鍵生成部、サーバ送信部をさらに備える。
【００１８】
ここで、サーバ第１受信部は、端末装置から送信された1-out-of-n紛失通信問い合わせを受信する。
【００１９】
一方、サーバ鍵生成部は、受信された1-out-of-n紛失通信問い合わせに指定されるgxと、選択されたyと、から、
gxy = (gx)y
をサーバ側セッション鍵として生成する。
【００２０】
さらに、サーバ送信部は、計算されたα[j] (j = 1，…，n)から、i番目のパスワードpw[i]を持つユーザがgygF(pw[i])の情報のみを得られるような1-out-of-n紛失通信応答を生成して端末装置に送信する。
【００２１】
一方、端末装置は、端末受信部、端末鍵生成部をさらに備える。
【００２２】
ここで、端末受信部は、サーバ装置から送信された1-out-of-n紛失通信応答を受信する。
【００２３】
一方、端末鍵生成部は、受信された1-out-of-n紛失通信応答から、gygF(pw[i])の情報を得て、
gxy = (gygF(pw[i])/gF(pw[i]))x
を端末側セッション鍵として生成する。
【００２４】
本発明のその他の観点に係るセッション鍵システムは、素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数F，G，H0，H1，H2と、を、端末装置とサーバ装置とで共有し、サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、端末装置には、当該n個のパスワードのうち、i番目のパスワードpw[i]が保有されるセッション鍵システムであって、以下のように構成する。
【００２５】
まず、端末装置は、端末選択部、端末第１計算部、端末第１送信部を備える。
【００２６】
ここで、端末選択部は、当該i番目のパスワードpw[i]に対して、体Zpの元からx，rを一様にランダムに選択する。
【００２７】
一方、端末第１計算部は、選択されたx，rから、
X = gx；
Q(i) = grhG(i,pw[i])
を計算する。
【００２８】
さらに、端末第１送信部は、計算されたXと、計算されたQ(i)と、を、組
(X,Q(i))
としてサーバ装置に送信する。
【００２９】
一方、サーバ装置は、サーバ第１受信部、サーバ選択部、サーバ第１計算部、サーバ第１認証子生成部、サーバ鍵生成部、サーバ送信部を備える。
【００３０】
ここで、サーバ第１受信部は、端末装置から送信された組
(X,Q(i))
を受信する。
【００３１】
一方、サーバ選択部は、体Zpの元からy，k[1]，…，k[n]を一様にランダムに選択する。
【００３２】
さらに、サーバ第１計算部は、受信された(X,Q(i))と、選択されたy，k[1]，…，k[n]と、から、
Y = gy
と、j = 1，…，nについて、
α[j] = YgF(pw[j])；
β[j] = H0((Q(i)/hG(j,pw[j]))k[j],j) xor α[j]
と、
A(Q(i)) = (β[1]，…，β[n]，gk[1]，…，gk[n])；
KS = Xy
と、を計算する。
【００３３】
さらに、サーバ第１認証子生成部は、サーバ側認証子AuthSを、
AuthS = H2(X,A(Q(i)),Y,KS)
のように生成する。
【００３４】
そして、サーバ鍵生成部は、サーバ側セッション鍵skSを、
skS = H1(X,A(Q(i)),Y,KS)
のように生成する。
【００３５】
一方、サーバ送信部は、計算されたA(Q(i))と、生成されたサーバ側認証子AuthSと、を組
(A(Q(i)),AuthS)
として、端末装置に送信する。
【００３６】
一方、端末装置は、端末受信部、端末第２計算部、端末第１認証子生成部、端末鍵生成部をさらに備える。
【００３７】
ここで、端末受信部は、i番目のパスワードpw[i]に対して、
【００３８】
サーバ装置から送信された組
(A(Q(i)),AuthS)
を受信する。
【００３９】
一方、端末第２計算部は、受信されたA(Q(i)) = (β[1]，…，β[n]，gk[1]，…，gk[n])から、
α[i] = β[i] xor H0((gk[i])r,i)；
Y = α[i]/gF(pw[i])；
KC = Yx；
を計算する。
【００４０】
さらに、端末第１認証子生成部は、受信されたA(Q(i))と、計算されたY，KCと、から、端末側認証子AuthCを、
AuthC = H2(X,A(Q(i)),Y,KC)
のように生成する。
【００４１】
一方、端末鍵生成部は、受信されたAuthSと、生成されたAuthCと、が、一致する場合、端末側セッション鍵skCを、
skC = H1(X,A(Q(i)),Y,KC)
のように生成する。
【００４２】
また、本発明のセッション鍵システムは、端末装置と、サーバ装置と、は、ハッシュ関数H3をさらに共有し、以下のように構成することができる。
【００４３】
まず、端末装置は、端末第２認証子生成部、端末第２送信部をさらに備える。
【００４４】
ここで、端末第２認証子生成部は、端末受信部により受信されたA(Q(i))と、端末第２計算部により計算されたY，KCと、から、端末側第２認証子AuthC'を、
AuthC' = H3(X,A(Q(i)),Y,KC)
のように生成する。
【００４５】
一方、端末第２送信部は、生成されたAuthC'を、サーバ装置に送信する。
【００４６】
そして、サーバ装置は、サーバ第２受信部、サーバ第２認証子生成部をさらに備える。
【００４７】
ここで、サーバ第２受信部は、端末装置から送信されたAuthC'を受信する。
【００４８】
一方、サーバ第２認証子生成部は、サーバ第１計算部により計算されたA(Q(i))，Y，KSから、サーバ側第２認証子AuthS'を、
AuthS' = H3(X,A(Q(i)),Y,KS)
のように生成する。
【００４９】
さらに、サーバ装置が備えるサーバ鍵生成部が、サーバ側セッション鍵skSを生成するのは、受信されたAuthC'と、生成されたAuthS'と、が、一致する場合である。
【００５０】
本発明のその他の観点に係るセッション鍵システムは、素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数F，G，H0，H1，H2と、を、端末装置とサーバ装置とで共有し、サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、端末装置には、当該n個のパスワードのうち、pw[1]，…，pw[k]が保有されるセッション鍵システムであって、以下のように構成する。
【００５１】
まず、端末装置は、端末選択部、端末第１計算部、端末第１送信部を備える。
【００５２】
ここで、端末選択部は、体Zpの元からx，γ[1]，…，γ[k]，a[1]，…，a[k]，w[k+1]，…，w[n]を一様にランダムに選択する。
【００５３】
一方、端末第１計算部は、選択されたx，γ[1]，…，γ[k]，a[1]，…，a[k]，w[k+1]，…，w[n]から、
X = gx
と、i = 1，…，kについて
w[i] = hγ[i]G(i,pw[i])；
A[i] = w[i]ga[i]
とを計算する。
【００５４】
さらに、端末第１送信部は、計算されたX，A[1]，…，A[k]，w[1]，…，w[n]を、サーバ装置に送信する。
【００５５】
一方、サーバ装置は、サーバ第１受信部、サーバ選択部、サーバ第１認証子生成部、サーバ送信部、サーバ鍵生成部を備える。
【００５６】
ここで、サーバ第１受信部は、端末装置から送信されたX，A[1]，…，A[k]，w[1]，…，w[n]を受信する。
【００５７】
一方、サーバ選択部は、体Zpの元からy，z，b[1]，…，b[k]を一様にランダムに選択する。
【００５８】
さらに、サーバ第１計算部は、f(x) = y + b[1]x + … b[k]xkとしたときに、
Y[1] = gf(1)，…，Y[n] = gf(n)；
Z = gz；
D[1] = A[1]z，…，D[k] = A[k]z；
を計算し、j = 1，…，nに対して、
α[j] = Y[j]gF(pw[j]) xor H0(w[i]z)；
KS = Xyを
を計算する。
【００５９】
さらに、サーバ第１認証子生成部は、サーバ側認証子AuthSを、
AuthS = H2(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KS)
のように生成する。
【００６０】
そして、サーバ送信部は、計算されたZ，D[1]，…，D[k]，α[1]，…，α[n]と、生成されたAuthSと、を、端末装置に送信する。
【００６１】
一方、サーバ鍵生成部は、サーバ側セッション鍵skSを、
skS = H1(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，Ks)
のように生成する。
【００６２】
一方、端末装置は、端末受信部、端末第２計算部、端末第１認証子生成部、端末鍵生成部をさらに備える。
【００６３】
ここで、端末受信部は、サーバ装置から送信されたZ，D[1]，…，D[k]，α[1]，…，α[n]，AuthSを受信する。
【００６４】
一方、端末第２計算部は、i = 1，…，kについて、
λ[i] = Π1≦j≦k，j≠i j/(j-i)
としたときに、
Y[i] = (α[i] xor H0(D[i]/Za[i]))/gF(pw[i])
を計算し、
Y = Y[1]λ[1]…Y[k]λ[k]；
KC = Yx
を計算する。
【００６５】
さらに、端末第１認証子生成部は、計算されたX，Y，KCと、受信されたZ，D[1]，…，D[k]，α[1]，…，α[n]と、から、端末側認証子AuthCを、
AuthC = H2(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KC)
のように生成する。
【００６６】
そして、端末鍵生成部は、受信されたAuthSと、生成されたAuthCと、が、一致する場合、端末側セッション鍵skCを、
skC = H1(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KC)
のように生成する。
【００６７】
また、本発明のセッション鍵システムにおいて、端末装置は、k台の機器を備え、i = 1，…，kについて、パスワードpw[i]はi番目の機器に保有され、γ[i]，a[i]の取得およびw[i]，A[i]，w[i]の計算は、i番目の機器が、j (j≠i)番目の機器とは独立に行うように構成することができる。
【００６８】
本発明のその他の観点に係るセッション鍵提供方法は、素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数Fと、を、端末装置とサーバ装置とで共有し、サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、端末装置には、当該n個のパスワードのうち、i番目のパスワードpw[i]が保有されるセッション鍵提供方法であって、以下のように構成する。
【００６９】
まず、端末装置において、端末選択工程、端末第１計算工程が実行される。
【００７０】
ここで、当該i番目のパスワードpw[i]に対して、端末選択工程では、体Zpの元からxを一様にランダムに選択する。
【００７１】
一方、端末第１計算工程では、選択されたxからgxを計算する。
【００７２】
一方、サーバ装置において、サーバ選択工程、サーバ第１計算工程が実行される。
【００７３】
ここで、サーバ選択工程では、体Zpの元からyを一様にランダムに選択する。
【００７４】
一方、サーバ第１計算工程では、選択されたyから、j = 1，…，nについて、
α[j] = gygF(pw[j])
を計算する。
【００７５】
さらに、端末装置において、端末第１送信工程が実行される。
【００７６】
ここで、端末第１送信工程では、計算されたgxを指定する1-out-of-n紛失通信問い合わせをサーバ装置に送信する。
【００７７】
そして、サーバ装置において、サーバ第１受信工程、サーバ鍵生成工程、サーバ送信工程がさらに実行される。
【００７８】
ここで、サーバ第１受信工程では、端末装置から送信された1-out-of-n紛失通信問い合わせを受信する。
【００７９】
一方、サーバ鍵生成工程では、受信された1-out-of-n紛失通信問い合わせに指定されるgxと、選択されたyと、から、
gxy = (gx)y
をサーバ側セッション鍵として生成する。
【００８０】
さらに、サーバ送信工程では、計算されたα[j] (j = 1，…，n)から、i番目のパスワードpw[i]を持つユーザがgygF(pw[i])の情報のみを得られるような1-out-of-n紛失通信応答を生成して端末装置に送信する。
【００８１】
一方、端末装置において、端末受信工程、端末鍵生成工程がさらに実行される。
【００８２】
ここで、端末受信工程では、サーバ装置から送信された1-out-of-n紛失通信応答を受信する。
【００８３】
一方、端末鍵生成工程では、受信された1-out-of-n紛失通信応答から、gygF(pw[i])の情報を得て、
gxy = (gygF(pw[i])/gF(pw[i]))x
を端末側セッション鍵として生成する。
【００８４】
本発明のその他の観点に係るセッション鍵提供方法は、素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数F，G，H0，H1，H2と、を、端末装置とサーバ装置とで共有し、サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、端末装置には、当該n個のパスワードのうち、i番目のパスワードpw[i]が保有されるセッション鍵提供方法であって、以下のように構成する。
【００８５】
まず、端末装置において、端末選択工程、端末第１計算工程、端末第１送信工程が実行される。
【００８６】
ここで、端末選択工程では、当該i番目のパスワードpw[i]に対して、体Zpの元からx，rを一様にランダムに選択する。
【００８７】
一方、端末第１計算工程では、選択されたx，rから、
X = gx；
Q(i) = grhG(i,pw[i])
を計算する。
【００８８】
さらに、端末第１送信工程では、計算されたXと、計算されたQ(i)と、を、組
(X,Q(i))
としてサーバ装置に送信する。
【００８９】
一方、サーバ装置において、サーバ第１受信工程、サーバ選択工程、サーバ第１計算工程、サーバ第１認証子生成工程、サーバ鍵生成工程、サーバ送信工程が実行される。
【００９０】
ここで、サーバ第１受信工程では、端末装置から送信された組
(X,Q(i))
を受信する。
【００９１】
一方、サーバ選択工程では、体Zpの元からy，k[1]，…，k[n]を一様にランダムに選択する。
【００９２】
さらに、サーバ第１計算工程では、受信された(X,Q(i))と、選択されたy，k[1]，…，k[n]と、から、
Y = gy
と、j = 1，…，nについて、
α[j] = YgF(pw[j])；
β[j] = H0((Q(i)/hG(j,pw[j]))k[j],j) xor α[j]
と、
A(Q(i)) = (β[1]，…，β[n]，gk[1]，…，gk[n])；
KS = Xy
と、を計算する。
【００９３】
さらに、サーバ第１認証子生成工程では、サーバ側認証子AuthSを、
AuthS = H2(X,A(Q(i)),Y,KS)
のように生成する。
【００９４】
そして、サーバ鍵生成工程では、サーバ側セッション鍵skSを、
skS = H1(X,A(Q(i)),Y,KS)
のように生成する。
【００９５】
一方、サーバ送信工程では、計算されたA(Q(i))と、生成されたサーバ側認証子AuthSと、を組
(A(Q(i)),AuthS)
として、端末装置に送信する。
【００９６】
一方、端末装置において、端末受信工程、端末第２計算工程、端末第１認証子生成工程、端末鍵生成工程がさらに実行される。
【００９７】
ここで、端末受信工程では、i番目のパスワードpw[i]に対して、
【００９８】
サーバ装置から送信された組
(A(Q(i)),AuthS)
を受信する。
【００９９】
一方、端末第２計算工程では、受信されたA(Q(i)) = (β[1]，…，β[n]，gk[1]，…，gk[n])から、
α[i] = β[i] xor H0((gk[i])r,i)；
Y = α[i]/gF(pw[i])；
KC = Yx；
を計算する。
【０１００】
さらに、端末第１認証子生成工程では、受信されたA(Q(i))と、計算されたY，KCと、から、端末側認証子AuthCを、
AuthC = H2(X,A(Q(i)),Y,KC)
のように生成する。
【０１０１】
一方、端末鍵生成工程では、受信されたAuthSと、生成されたAuthCと、が、一致する場合、端末側セッション鍵skCを、
skC = H1(X,A(Q(i)),Y,KC)
のように生成する。
【０１０２】
また、本発明のセッション鍵提供方法では、端末装置と、サーバ装置と、は、ハッシュ関数H3をさらに共有し、以下のように構成することができる。
【０１０３】
まず、端末装置において、端末第２認証子生成工程、端末第２送信工程がさらに実行される。
【０１０４】
ここで、端末第２認証子生成工程では、端末受信部により受信されたA(Q(i))と、端末第２計算部により計算されたY，KCと、から、端末側第２認証子AuthC'を、
AuthC' = H3(X,A(Q(i)),Y,KC)
のように生成する。
【０１０５】
一方、端末第２送信工程では、生成されたAuthC'を、サーバ装置に送信する。
【０１０６】
そして、サーバ装置において、サーバ第２受信工程、サーバ第２認証子生成工程がさらに実行される。
【０１０７】
ここで、サーバ第２受信工程では、端末装置から送信されたAuthC'を受信する。
【０１０８】
一方、サーバ第２認証子生成工程では、サーバ第１計算部により計算されたA(Q(i))，Y，KSから、サーバ側第２認証子AuthS'を、
AuthS' = H3(X,A(Q(i)),Y,KS)
のように生成する。
【０１０９】
さらに、サーバ鍵生成工程において、サーバ側セッション鍵skSを生成するのは、受信されたAuthC'と、生成されたAuthS'と、が、一致する場合である。
【０１１０】
本発明のその他の観点に係るセッション鍵提供方法は、素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数F，G，H0，H1，H2と、を、端末装置とサーバ装置とで共有し、サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、端末装置には、当該n個のパスワードのうち、pw[1]，…，pw[k]が保有されるセッション鍵提供方法であって、以下のように構成する。
【０１１１】
まず、端末装置において、端末選択工程、端末第１計算工程、端末第１送信工程が実行される。
【０１１２】
ここで、端末選択工程では、体Zpの元からx，γ[1]，…，γ[k]，a[1]，…，a[k]，w[k+1]，…，w[n]を一様にランダムに選択する。
【０１１３】
一方、端末第１計算工程では、選択されたx，γ[1]，…，γ[k]，a[1]，…，a[k]，w[k+1]，…，w[n]から、
X = gx
と、i = 1，…，kについて
w[i] = hγ[i]G(i,pw[i])；
A[i] = w[i]ga[i]
とを計算する。
【０１１４】
さらに、端末第１送信工程では、計算されたX，A[1]，…，A[k]，w[1]，…，w[n]を、サーバ装置に送信する。
【０１１５】
一方、サーバ装置において、サーバ第１受信工程、サーバ選択工程、サーバ第１認証子生成工程、サーバ送信工程、サーバ鍵生成工程が実行される。
【０１１６】
ここで、サーバ第１受信工程では、端末装置から送信されたX，A[1]，…，A[k]，w[1]，…，w[n]を受信する。
【０１１７】
一方、サーバ選択工程では、体Zpの元からy，z，b[1]，…，b[k]を一様にランダムに選択する
【０１１８】
さらに、サーバ第１計算工程では、f(x) = y + b[1]x + … b[k]xkとしたときに、
Y[1] = gf(1)，…，Y[n] = gf(n)；
Z = gz；
D[1] = A[1]z，…，D[k] = A[k]z；
【０１１９】
を計算し、j = 1，…，nに対して、
α[j] = Y[j]gF(pw[j]) xor H0(w[i]z)；
KS = Xyを
を計算する。
【０１２０】
さらに、サーバ第１認証子生成工程では、サーバ側認証子AuthSを、
AuthS = H2(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KS)
のように生成する。
【０１２１】
そして、サーバ送信工程では、計算されたZ，D[1]，…，D[k]，α[1]，…，α[n]と、生成されたAuthSと、を、端末装置に送信する。
【０１２２】
一方、サーバ鍵生成工程では、サーバ側セッション鍵skSを、
skS = H1(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，Ks)
のように生成する。
【０１２３】
一方、端末装置において、端末受信工程、端末第２計算工程、端末第１認証子生成工程、端末鍵生成工程がさらに実行される。
【０１２４】
ここで、端末受信工程では、サーバ装置から送信されたZ，D[1]，…，D[k]，α[1]，…，α[n]，AuthSを受信する。
【０１２５】
一方、端末第２計算工程では、i = 1，…，kについて、
λ[i] = Π1≦j≦k，j≠i j/(j-i)
としたときに、
Y[i] = (α[i] xor H0(D[i]/Za[i]))/gF(pw[i])
を計算し、
Y = Y[1]λ[1]…Y[k]λ[k]；
KC = Yx
を計算する。
【０１２６】
さらに、端末第１認証子生成工程では、計算されたX，Y，KCと、受信されたZ，D[1]，…，D[k]，α[1]，…，α[n]と、から、端末側認証子AuthCを、
AuthC = H2(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KC)
のように生成する。
【０１２７】
そして、端末鍵生成工程では、受信されたAuthSと、生成されたAuthCと、が、一致する場合、端末側セッション鍵skCを、
skC = H1(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KC)
のように生成する。
【０１２８】
本発明の他の観点に係るプログラムは、各種のコンピュータを、上記のセッション鍵システムの端末装置が備える各部として機能させるように構成する。
【０１２９】
本発明の他の観点に係るプログラムは、各種のコンピュータを、上記のセッション鍵システムのサーバ装置が備える各部として機能させるように構成する。
【０１３０】
本発明のプログラムを、少なくとも２つのコンピュータのそれぞれに実行させることにより、本発明のセッション鍵システム、および、セッション鍵提供方法を実現することができる。
【０１３１】
また、当該コンピュータとは独立して、本発明のプログラムを記録した情報記録媒体を配布、販売することができる。また、本発明のプログラムを、インターネット等のコンピュータ通信網を介して伝送し、配布、販売することができる。
【０１３２】
特に、当該コンピュータがＤＳＰ（Digital Signal Processor）やＦＰＧＡ（Field Programmable Gate Array）などのプログラム可能な電子回路を有する場合には、本発明の情報記録媒体に記録されたプログラムを無線にて当該コンピュータに伝送し、当該コンピュータ内のＤＳＰやＦＰＧＡにこれを実行させて、本発明の無線通信端末とすることができる。
【発明の効果】
【０１３３】
本発明によれば、小さいパスワードを共有することで、証明者があるグループの一員であることを、その証明者が実際に誰なのかを明かすことなく、検証者に対して証明するのに好適な、セッション鍵システム、セッション鍵提供方法、および、これらをコンピュータにおいて実現するためのプログラムを提供することができる。
【発明を実施するための最良の形態】
【０１３４】
以下に本発明の一実施形態を説明する。なお、以下に説明する実施形態は説明のためのものであり、本発明の範囲を制限するものではない。したがって、当業者であればこれらの各要素もしくは全要素をこれと均等なものに置換した実施形態を採用することが可能であるが、これらの実施形態も本発明の範囲に含まれる。
【実施例１】
【０１３５】
図１は、本発明のセッション鍵システムの最も基本的な実施形態に係る説明図である。以下、本図を参照して説明する。
【０１３６】
セッション鍵システム１０１は、１台以上の端末装置１３１と、１台のサーバ装置１５１と、両者を通信可能に接続するインターネット等のコンピュータ通信用の通信網１７１と、を備える。
【０１３７】
ここで、セッション鍵システム１０１は、素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数Fと、を、端末装置１３１とサーバ装置１５１とで共有する。
【０１３８】
GGの位数pがLビットのビット列で表現できる素数であるとすると、GGのすべての要素はLビットのビット列で表現できる。また、GGの演算は乗算として表現される。
【０１３９】
g，hはGGの生成元であり、これに対して繰り返し上記の演算を適用することにより、GGのすべての元が現れることになる。
【０１４０】
また、本発明で利用するハッシュ関数は、任意の長さのビット列を、長さLのビット列に変換するもので、いわゆるランダムオラクルである。
【０１４１】
また、サーバ装置１５１には、n個のパスワードpw[1]，…，pw[n]が保有される。すなわち、サーバ装置１５１では、n人のユーザのパスワードを保持していることになる。サーバ装置１５１におけるパスワードの辞書の典型的なサイズはおおよそ230程度であり、実際には、この中からn個の有効なパスワードが選択される。
【０１４２】
一方、端末装置１３１には、当該n個のパスワードのうち、i番目のパスワードpw[i]が保有される。
【０１４３】
すなわち、ユーザは、自分のパスワードを任意の端末装置１３１で使用することとなる。このパスワードをpw[i]としても、一般性を失わない。
【０１４４】
さて、端末装置１３１は、ユーザが何らかの形で与えたパスワードpw[i]に対して、処理を開始する。体Zpの元からxを一様にランダムに選択し、選択されたxからgxを計算する。
【０１４５】
サーバ装置１５１は、体Zpの元からyを一様にランダムに選択し、選択されたyから、j = 1，…，nについて、
α[j] = gygF(pw[j])
を計算する。
【０１４６】
さらに、端末装置１３１は、計算されたgxを指定する1-out-of-n紛失通信問い合わせをサーバ装置１５１に送信する。
【０１４７】
1-out-of-n紛失通信については、[非特許文献２][非特許文献３]に開示される効率の良い技術を採用することができ、詳細については後述する。ただし、他の紛失送信技術を適用することもでき、そのような実施態様も、本発明の範囲に含まれる。
【０１４８】
さて、サーバ装置１５１は、端末装置１３１から送信された1-out-of-n紛失通信問い合わせを受信し、受信された1-out-of-n紛失通信問い合わせに指定されるgxと、選択されたyと、から、
gxy = (gx)y
をサーバ側セッション鍵として生成する。
【０１４９】
さらに、計算されたα[j] (j = 1，…，n)から、i番目のパスワードpw[i]を持つユーザがgygF(pw[i])の情報のみを得られるような1-out-of-n紛失通信応答を生成して端末装置１３１に送信する。
【０１５０】
一方、端末装置１３１は、サーバ装置１５１から送信された1-out-of-n紛失通信応答を受信して、1-out-of-n紛失通信応答から、gygF(pw[i])の情報を得て、
gxy = (gygF(pw[i])/gF(pw[i]))x
を端末側セッション鍵として生成する。
【０１５１】
このように、本技術では、与えられた元g，gx，gyからgxyを効率良く求める計算Diffie-Hellman問題に帰着される。したがって、本技術の安全性は、計算Diffie-Hellman問題を効率良く求めるアルゴリズムが存在しない、という、現在技術界で同意されている仮定の下で、補償されることになる。
【０１５２】
以下、さらに詳細に、本技術について説明する。
【０１５３】
以下の例では、ハッシュ関数として、Fのほか、G，H0，H1，H2，H3を端末装置１３１とサーバ装置１５１とで共有する。典型的なハッシュ関数は１引数であるが、これらのハッシュ関数は任意の個数の引数をとることができる。この場合、任意の個数の引数を何らかの形で１つのビット列に変換し（たとえば、メモリ内でのデータ構造は、単なるビット列に還元できる。）、その１つのビット列に対してハッシュ関数を適用する、と考えることになる。
【０１５４】
図２は、端末装置１３１の概要構成を示す説明図である。以下、本図を参照して説明する。
【０１５５】
端末装置１３１は、端末選択部２０１、端末第１計算部２０２、端末第１送信部２０３、端末受信部２０４、端末第２計算部２０５、端末第１認証子生成部２０６、端末鍵生成部２０７を備える。
【０１５６】
なお、本図には、端末第２認証子生成部２０８、端末第２送信部２０９も図示してあるが、これらは、[実施例２]で必要となる要素である。
【０１５７】
図３は、端末装置１３１において実行される端末処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【０１５８】
まず、端末装置１３１の端末選択部２０１は、当該i番目のパスワードpw[i]に対して、体Zpの元からx，rを一様にランダムに選択する（ステップＳ３０１）。
【０１５９】
一方、端末第１計算部２０２は、選択されたx，rから、
X = gx；
Q(i) = grhG(i,pw[i])
を計算する（ステップＳ３０２）。
【０１６０】
さらに、端末第１送信部２０３は、計算されたXと、計算されたQ(i)と、を、組
(X,Q(i))
としてサーバ装置１５１に送信する（ステップＳ３０３）。
【０１６１】
図４は、サーバ装置１５１の概要構成を示す説明図である。以下、本図を参照して説明する。
【０１６２】
一方、サーバ装置１５１は、サーバ第１受信部４０１、サーバ選択部４０２、サーバ第１計算部４０３、サーバ第１認証子生成部４０４、サーバ鍵生成部４０５、サーバ送信部４０６を備える。
【０１６３】
なお、本図には、サーバ第２受信部４０７、サーバ第２認証子生成部４０８も図示してあるが、これらは、[実施例２]で必要となる要素である。
【０１６４】
図５は、サーバ装置１５１にて実行されるサーバ処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【０１６５】
サーバ装置１５１において、サーバ第１受信部４０１は、端末装置１３１から送信された組
(X,Q(i))
を受信する（ステップＳ５０１）。
【０１６６】
ついで、サーバ選択部４０２は、体Zpの元からy，k[1]，…，k[n]を一様にランダムに選択する（ステップＳ５０２）。
【０１６７】
さらに、サーバ第１計算部４０３は、受信された(X,Q(i))と、選択されたy，k[1]，…，k[n]と、から、
Y = gy
と、j = 1，…，nについて、
α[j] = YgF(pw[j])；
β[j] = H0((Q(i)/hG(j,pw[j]))k[j],j) xor α[j]
と、
A(Q(i)) = (β[1]，…，β[n]，gk[1]，…，gk[n])；
KS = Xy
と、を計算する（ステップＳ５０３）。
【０１６８】
さらに、サーバ第１認証子生成部４０４は、サーバ側認証子AuthSを、
AuthS = H2(X,A(Q(i)),Y,KS)
のように生成する（ステップＳ５０４）。
【０１６９】
そして、サーバ鍵生成部４０５は、サーバ側セッション鍵skSを、
skS = H1(X,A(Q(i)),Y,KS)
のように生成する（ステップＳ５０５）。
【０１７０】
一方、サーバ送信部４０６は、計算されたA(Q(i))と、生成されたサーバ側認証子AuthSと、を組
(A(Q(i)),AuthS)
として、端末装置１３１に送信して（ステップＳ５０６）、本処理を終了する。
【０１７１】
さて、端末装置１３１に戻り、端末受信部２０４は、i番目のパスワードpw[i]に対して、サーバ装置１５１から送信された組
(A(Q(i)),AuthS)
を受信する（ステップＳ３０４）。
【０１７２】
ついで、端末第２計算部２０５は、受信されたA(Q(i)) = (β[1]，…，β[n]，gk[1]，…，gk[n])から、
α[i] = β[i] xor H0((gk[i])r,i)；
Y = α[i]/gF(pw[i])；
KC = Yx；
を計算する（ステップＳ３０５）。
【０１７３】
さらに、端末第１認証子生成部２０６は、受信されたA(Q(i))と、計算されたY，KCと、から、端末側認証子AuthCを、
AuthC = H2(X,A(Q(i)),Y,KC)
のように生成する（ステップＳ３０６）。
【０１７４】
一方、端末鍵生成部２０７は、受信されたAuthSと、生成されたAuthCと、が、一致するか否かを判定し（ステップＳ３０７）一致する場合（ステップＳ３０７；Ｙｅｓ）、端末側セッション鍵skCを、
skC = H1(X,A(Q(i)),Y,KC)
のように生成して（ステップＳ３０８）、本処理を終了する。
【０１７５】
一致しない場合（ステップＳ３０７；Ｎｏ）、セッション鍵の提供が受けられなかった旨を報告して（ステップＳ３０９）、本処理を終了する。
【０１７６】
このようにして、サーバ装置１５１と端末装置１３１とで、skS = skCを共有することができる一方で、端末装置１３１で利用したパスワードpw[i]そのものは、サーバ装置１５１に直接渡されることがなく、匿名性を保つことができる。
【０１７７】
なお、端末装置１３１を使用しうるユーザの識別符号の集合（pw[1]を持つユーザの識別符号C[1]、…、pw[n]を持つユーザの識別符号C[n]）や、サーバ装置１５１の識別符号を、適宜通信の際に送受し、ハッシュ関数の計算においてこれらの識別符号も参照することとしても良い。
【０１７８】
たとえば、端末装置１３１からサーバ装置１５１へ送付される組に、C[1]，…，C[n]の情報を含めることとし、サーバ側認証子AuthSサーバ側セッション鍵skSの計算で、C[1]，…，C[n]，Sの情報を勘案することとする。
【０１７９】
そして、サーバ装置１５１から端末装置１３１へ送付される組に、Sの情報を含めることとし、端末側認証子AuthC端末側セッション鍵skCの計算で、C[1]，…，C[n]，Sの情報を勘案することとするのである。
【０１８０】
以下の実施例についても、同様である。
【実施例２】
【０１８１】
本実施例では、サーバ装置１５１で、端末装置１３１を使用しているユーザの正当性を認証する。
【０１８２】
図６は、図３に示す端末処理が成功裏に終了した後に、端末装置１３１にて実行される処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【０１８３】
端末装置１３１において、ステップＳ３０８の後、端末第２認証子生成部２０８は、端末受信部２０４により受信されたA(Q(i))と、端末第２計算部２０５により計算されたY，KCと、から、端末側第２認証子AuthC'を、
AuthC' = H3(X,A(Q(i)),Y,KC)
のように生成する（ステップＳ６０１）。
【０１８４】
一方、端末第２送信部２０９は、生成されたAuthC'を、サーバ装置１５１に送信して（ステップＳ６０２）、本処理を終了する。
【０１８５】
図７は、図５に示すサーバ処理の制御の流れの一部を変形して本実施例に係るものとしたフローチャートである。以下、本図を参照して説明する。
【０１８６】
サーバ装置は、AuthSを生成した後（ステップＳ５０４）、ステップＳ５０５は実行せずに、組(A(Q(i)),AuthS)を端末装置１３１に送信してから（ステップＳ５０６）、以下の処理を開始する。
【０１８７】
すなわち、サーバ第２受信部４０７は、端末装置１３１から送信されたAuthC'を受信する（ステップＳ７０１）。
【０１８８】
ついで、サーバ第２認証子生成部４０８は、サーバ第１計算部４０３により計算されたA(Q(i))，Y，KSから、サーバ側第２認証子AuthS'を、
AuthS' = H3(X,A(Q(i)),Y,KS)
のように生成する（ステップＳ７０２）。
【０１８９】
さらに、受信されたAuthC'と、生成されたAuthS'と、が、一致するか否かを判定し（ステップＳ７０３）、一致する場合（ステップＳ７０３；Ｙｅｓ）、サーバ鍵生成部４０５が、サーバ側セッション鍵skSを生成して（ステップＳ５０５）、本処理を終了する。
【０１９０】
一致しない場合（ステップＳ７０３；Ｎｏ）、ユーザの正当性の認証に失敗した旨を報告して（ステップＳ７０４）、本処理を終了する。
【実施例３】
【０１９１】
上記の[実施例１][実施例２]は、いずれも、1-out-of-n紛失通信に相当するものであったが、本実施例は、k-out-of-n紛失通信に相当するものである。すなわち、全ユーザがn人でいる場合に、その中のk人がサーバとセッション鍵を共有するためのものである。
【０１９２】
この場合、k人のユーザが使用する端末装置１３１は、典型的には異なる機械であるが、理解を容易にするため、以下では、これらをまとめて１つの端末装置１３１として説明し、必要に応じて、個々の機械で行う処理と、これらを統合してまとめて行う処理と、を説明することとする。
【０１９３】
また、制御のおおまかな流れや各部の処理については、上記の[実施例１]と同様であるので、適宜説明を省略する。
【０１９４】
本実施例のセッション鍵システム１０１では、サーバ装置１５１には、n個のパスワードpw[1]，…，pw[n]が保有され、端末装置１３１には、当該n個のパスワードのうち、少なくともpw[1]，…，pw[k]が公開される。
（１） まず、端末装置１３１において、端末選択部２０１は、体Zpの元からx，γ[1]，…，γ[k]，a[1]，…，a[k]，w[k+1]，…，w[n]を一様にランダムに選択する。
【０１９５】
次に、端末装置１３１において、端末第１計算部２０２は、選択されたx，γ[1]，…，γ[k]，a[1]，…，a[k]，w[k+1]，…，w[n]から、
X = gx
と、i = 1，…，kについて
w[i] = hγ[i]G(i,pw[i])；
A[i] = w[i]ga[i]
とを計算する。
【０１９６】
さらに、端末装置１３１において、端末第１送信部２０３は、計算されたX，A[1]，…，A[k]，w[1]，…，w[n]を、サーバ装置１５１に送信する。
【０１９７】
典型的には、Xの計算は、いずれか１台の機械が行い、w[i]，A[i]の計算は、それぞれのユーザの機械が行う。これにより、各人のパスワードが他人に漏曳することはない。そして、いずれかの１台（典型的にはXを計算した１台）に結果を集めてからサーバ装置１５１に送信する。
（２） 次に、サーバ装置１５１において、サーバ第１受信部４０１は、端末装置１３１から送信されたX，A[1]，…，A[k]，w[1]，…，w[n]を受信する。
【０１９８】
ついで、サーバ装置１５１において、サーバ選択部４０２は、体Zpの元からy，z，b[1]，…，b[k]を一様にランダムに選択する。
【０１９９】
さらに、サーバ装置１５１において、サーバ第１計算部４０３は、f(x) = y + b[1]x + … b[k]xkとしたときに、
Y[1] = gf(1)，…，Y[n] = gf(n)；
Z = gz；
D[1] = A[1]z，…，D[k] = A[k]z；
【０２００】
を計算し、j = 1，…，nに対して、
α[j] = Y[j]gF(pw[j]) xor H0(w[i]z)；
KS = Xyを
を計算する。
【０２０１】
そして、サーバ装置１５１において、サーバ第１認証子生成部４０４は、サーバ側認証子AuthSを、
AuthS = H2(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KS)
のように生成する。
【０２０２】
次に、サーバ装置１５１において、サーバ送信部４０６は、計算されたZ，D[1]，…，D[k]，α[1]，…，α[n]と、生成されたAuthSと、を、端末装置１３１に送信する。
【０２０３】
典型的には、Z，D[1]，…，D[k]，α[1]，…，α[n]，AuthSが送信される端末装置１３１は、ユーザが利用するすべての機械であるが、１台がとりまとめて受信し、各機械に分配することとしても良い。
【０２０４】
さらに、サーバ装置１５１において、サーバ鍵生成部４０５は、サーバ側セッション鍵skSを、
skS = H1(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，Ks)
のように生成する。
（３） そして、端末装置１３１において、端末受信部２０４は、サーバ装置１５１から送信されたZ，D[1]，…，D[k]，α[1]，…，α[n]，AuthSを受信する。これらは、ユーザが使用する機械に分配されるのが典型的である。
【０２０５】
ついで、端末装置１３１において、端末第２計算部２０５は、i = 1，…，kについて、
λ[i] = Π1≦j≦k，j≠i j/(j-i)
としたときに、
Y[i] = (α[i] xor H0(D[i]/Za[i]))/gF(pw[i])
を計算し、
Y = Y[1]λ[1]…Y[k]λ[k]；
KC = Yx
を計算する。
【０２０６】
さらに、端末装置１３１において、端末第１認証子生成部２０６は、計算されたX，Y，KCと、受信されたZ，D[1]，…，D[k]，α[1]，…，α[n]と、から、端末側認証子AuthCを、
AuthC = H2(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KC)
のように生成する。
【０２０７】
Y[i]の計算は、それぞれのユーザが利用する機械で行うこととすれば、パスワードが漏れることはない。そして、計算されたX，Y[1]，…，Y[k]は、それぞれのユーザが利用する機械で共有することとするのである。
【０２０８】
そして、端末装置１３１において、端末鍵生成部２０７は、受信されたAuthSと、生成されたAuthCと、が、一致する場合、端末側セッション鍵skCを、
skC = H1(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KC)
のように生成する。
【０２０９】
上記のように、個々のパスワード以外の情報は、共有したり、独立に計算できるので、skCの計算も個々の機械で独立して計算することができる。
【０２１０】
このように、k人のユーザが集まることによって、秘密鍵となるセッション鍵を共有し、かつ、匿名を保ちながらパスワードを利用して認証を行うことができる。また、k人未満のユーザが集まっても、セッション鍵共有を行うことはできない。
【０２１１】
上述した通り、k人のユーザが使用する端末装置１３１は、典型的には異なる機械である。そこで、これらを仮にi = 1，…，k番目の機器としたとき、i番目の機器はパスワードpw[i]を保有することとし、他のパスワードpw[j] (j≠i)は知らないようにすることができる。
【０２１２】
γ[i]，a[i]のランダム選択やw[i]，A[i]，Y[i]の計算は、i番目の機器のみで独立に行うことができるため、pw[i]を他のj (j≠i)番目の機器に知られずにすむ。
【０２１３】
また、x，w[k+1]，…，w[n]のランダムな選択や、Xの計算は、k台の機器のいずれかが代表として行うこととすれば良い。w[i]，A[i]の情報は、この代表がとりまとめてサーバ装置１５１に送ることとする。また、それぞれの機器が計算したY[i]は、代表に集められ、YやKCの計算は代表が行うこととする。
【０２１４】
このような、k台の機器の群を、上記の説明では、「１台の端末装置１３１」として表現している。
【産業上の利用可能性】
【０２１５】
以上説明したように、本発明によれば、小さいパスワードを共有することで、証明者があるグループの一員であることを、その証明者が実際に誰なのかを明かすことなく、検証者に対して証明するのに好適な、セッション鍵システム、セッション鍵提供方法、および、これらをコンピュータにおいて実現するためのプログラムを提供することができる。
【図面の簡単な説明】
【０２１６】
【図１】本発明のセッション鍵システムの最も基本的な実施形態に係る説明図である。
【図２】端末装置の概要構成を示す説明図である。
【図３】端末装置において実行される端末処理の制御の流れを示すフローチャートである。
【図４】サーバ装置の概要構成を示す説明図である。
【図５】サーバ装置にて実行されるサーバ処理の制御の流れを示すフローチャートである。
【図６】端末処理が成功裏に終了した後に端末装置にて実行される処理の制御の流れを示すフローチャートである。
【図７】図５に示すサーバ処理の制御の流れの一部を変形したフローチャートである。
【符号の説明】
【０２１７】
１０１ セッション鍵システム
１３１ 端末装置
１５１ サーバ装置
１７１ 通信網
２０１ 端末選択部
２０２ 端末第１計算部
２０３ 端末第１送信部
２０４ 端末受信部
２０５ 端末第２計算部
２０６ 端末第１認証子生成部
２０７ 端末鍵生成部
２０８ 端末第２認証子生成部
２０９ 端末第２送信部
４０１ サーバ第１受信部
４０２ サーバ選択部
４０３ サーバ第１計算部
４０４ サーバ第１認証子生成部
４０５ サーバ鍵生成部
４０６ サーバ送信部
４０７ サーバ第２受信部
４０８ サーバ第２認証子生成部
【技術分野】
【０００１】
本発明は、セッション鍵システム、セッション鍵提供方法、ならびに、プログラムに関する。
【背景技術】
【０００２】
従来から、セッション鍵を用いることによって、電子認証や電子署名を行う技術が広く提供されている。このような技術は、以下の文献に開示されている。
【非特許文献１】C.H.Lee，X.Deng and H.Zhu，Design and Security Analysis of Anonymous Group Identification Protocols，PKC02，LNCS 2274，Springer-Verlag，pp.188-198，２００２年
【非特許文献２】W.G.Tzeng，Efficient 1-out-of-n Oblivious Transfer Schemes，PKC02，LNCS 2274，Sprinter-Verlag，pp.159-171，２００２年
【非特許文献３】C.K.Chu and W.G.Tzeng，Efficient k-out-of-n Oblivious Transfer Schemes with Adaptive and NOn-Adaptive Queries，PKC05，LNCS 3386，Sprinver-Verlag，pp.172-183，２００５年
【０００３】
ここで、[非特許文献１]では、検証者に対して、証明者がグループの一員であることを、その証明者が実際に誰なのかを明かすことなく、証明する匿名認証スキームが提案されている。
【０００４】
この技術では公開鍵暗号を利用するため、比較的長いランダムなビット列を公開鍵と秘密鍵として保有しなければならない。
【０００５】
一方、[非特許文献２][非特許文献３]では、紛失通信（Oblivious Transfer；ＯＴ）プロトコルの効率の良い実装例が開示されている。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
したがって、あらかじめ用意され管理されている辞書に含まれるような小さい低エントロピー鍵（パスワード）のみを共有するような、簡易な匿名認証スキームに対する要望は大きい。
【０００７】
本発明は、以上のような課題を解決するためになされたもので、小さいパスワードを共有することで、証明者があるグループの一員であることを、その証明者が実際に誰なのかを明かすことなく、検証者に対して証明するのに好適な、セッション鍵システム、セッション鍵提供方法、および、これらをコンピュータにおいて実現するためのプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
以上の目的を達成するため、本発明の原理にしたがって、下記の発明を開示する。
【０００９】
本発明の第１の観点に係るセッション鍵システムは、素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数Fと、を、端末装置とサーバ装置とで共有し、サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、端末装置には、当該n個のパスワードのうち、i番目のパスワードpw[i]が保有されるセッション鍵システムであって、以下のように構成する。
【００１０】
まず、端末装置は、端末選択部、端末第１計算部を備える。
【００１１】
ここで、当該i番目のパスワードpw[i]に対して、端末選択部は、体Zpの元からxを一様にランダムに選択し、端末第１計算部は、選択されたxからgxを計算する。
【００１２】
一方、サーバ装置は、サーバ選択部、サーバ第１計算部を備える。
【００１３】
ここで、サーバ選択部は、体Zpの元からyを一様にランダムに選択する。
【００１４】
一方、サーバ第１計算部は、選択されたyから、j = 1，…，nについて、
α[j] = gygF(pw[j])
を計算する。
【００１５】
さらに、端末装置は、端末第１送信部をさらに備える。
【００１６】
ここで、端末第１送信部は、計算されたgxを指定する1-out-of-n紛失通信問い合わせをサーバ装置に送信する。
【００１７】
そして、サーバ装置は、サーバ第１受信部、サーバ鍵生成部、サーバ送信部をさらに備える。
【００１８】
ここで、サーバ第１受信部は、端末装置から送信された1-out-of-n紛失通信問い合わせを受信する。
【００１９】
一方、サーバ鍵生成部は、受信された1-out-of-n紛失通信問い合わせに指定されるgxと、選択されたyと、から、
gxy = (gx)y
をサーバ側セッション鍵として生成する。
【００２０】
さらに、サーバ送信部は、計算されたα[j] (j = 1，…，n)から、i番目のパスワードpw[i]を持つユーザがgygF(pw[i])の情報のみを得られるような1-out-of-n紛失通信応答を生成して端末装置に送信する。
【００２１】
一方、端末装置は、端末受信部、端末鍵生成部をさらに備える。
【００２２】
ここで、端末受信部は、サーバ装置から送信された1-out-of-n紛失通信応答を受信する。
【００２３】
一方、端末鍵生成部は、受信された1-out-of-n紛失通信応答から、gygF(pw[i])の情報を得て、
gxy = (gygF(pw[i])/gF(pw[i]))x
を端末側セッション鍵として生成する。
【００２４】
本発明のその他の観点に係るセッション鍵システムは、素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数F，G，H0，H1，H2と、を、端末装置とサーバ装置とで共有し、サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、端末装置には、当該n個のパスワードのうち、i番目のパスワードpw[i]が保有されるセッション鍵システムであって、以下のように構成する。
【００２５】
まず、端末装置は、端末選択部、端末第１計算部、端末第１送信部を備える。
【００２６】
ここで、端末選択部は、当該i番目のパスワードpw[i]に対して、体Zpの元からx，rを一様にランダムに選択する。
【００２７】
一方、端末第１計算部は、選択されたx，rから、
X = gx；
Q(i) = grhG(i,pw[i])
を計算する。
【００２８】
さらに、端末第１送信部は、計算されたXと、計算されたQ(i)と、を、組
(X,Q(i))
としてサーバ装置に送信する。
【００２９】
一方、サーバ装置は、サーバ第１受信部、サーバ選択部、サーバ第１計算部、サーバ第１認証子生成部、サーバ鍵生成部、サーバ送信部を備える。
【００３０】
ここで、サーバ第１受信部は、端末装置から送信された組
(X,Q(i))
を受信する。
【００３１】
一方、サーバ選択部は、体Zpの元からy，k[1]，…，k[n]を一様にランダムに選択する。
【００３２】
さらに、サーバ第１計算部は、受信された(X,Q(i))と、選択されたy，k[1]，…，k[n]と、から、
Y = gy
と、j = 1，…，nについて、
α[j] = YgF(pw[j])；
β[j] = H0((Q(i)/hG(j,pw[j]))k[j],j) xor α[j]
と、
A(Q(i)) = (β[1]，…，β[n]，gk[1]，…，gk[n])；
KS = Xy
と、を計算する。
【００３３】
さらに、サーバ第１認証子生成部は、サーバ側認証子AuthSを、
AuthS = H2(X,A(Q(i)),Y,KS)
のように生成する。
【００３４】
そして、サーバ鍵生成部は、サーバ側セッション鍵skSを、
skS = H1(X,A(Q(i)),Y,KS)
のように生成する。
【００３５】
一方、サーバ送信部は、計算されたA(Q(i))と、生成されたサーバ側認証子AuthSと、を組
(A(Q(i)),AuthS)
として、端末装置に送信する。
【００３６】
一方、端末装置は、端末受信部、端末第２計算部、端末第１認証子生成部、端末鍵生成部をさらに備える。
【００３７】
ここで、端末受信部は、i番目のパスワードpw[i]に対して、
【００３８】
サーバ装置から送信された組
(A(Q(i)),AuthS)
を受信する。
【００３９】
一方、端末第２計算部は、受信されたA(Q(i)) = (β[1]，…，β[n]，gk[1]，…，gk[n])から、
α[i] = β[i] xor H0((gk[i])r,i)；
Y = α[i]/gF(pw[i])；
KC = Yx；
を計算する。
【００４０】
さらに、端末第１認証子生成部は、受信されたA(Q(i))と、計算されたY，KCと、から、端末側認証子AuthCを、
AuthC = H2(X,A(Q(i)),Y,KC)
のように生成する。
【００４１】
一方、端末鍵生成部は、受信されたAuthSと、生成されたAuthCと、が、一致する場合、端末側セッション鍵skCを、
skC = H1(X,A(Q(i)),Y,KC)
のように生成する。
【００４２】
また、本発明のセッション鍵システムは、端末装置と、サーバ装置と、は、ハッシュ関数H3をさらに共有し、以下のように構成することができる。
【００４３】
まず、端末装置は、端末第２認証子生成部、端末第２送信部をさらに備える。
【００４４】
ここで、端末第２認証子生成部は、端末受信部により受信されたA(Q(i))と、端末第２計算部により計算されたY，KCと、から、端末側第２認証子AuthC'を、
AuthC' = H3(X,A(Q(i)),Y,KC)
のように生成する。
【００４５】
一方、端末第２送信部は、生成されたAuthC'を、サーバ装置に送信する。
【００４６】
そして、サーバ装置は、サーバ第２受信部、サーバ第２認証子生成部をさらに備える。
【００４７】
ここで、サーバ第２受信部は、端末装置から送信されたAuthC'を受信する。
【００４８】
一方、サーバ第２認証子生成部は、サーバ第１計算部により計算されたA(Q(i))，Y，KSから、サーバ側第２認証子AuthS'を、
AuthS' = H3(X,A(Q(i)),Y,KS)
のように生成する。
【００４９】
さらに、サーバ装置が備えるサーバ鍵生成部が、サーバ側セッション鍵skSを生成するのは、受信されたAuthC'と、生成されたAuthS'と、が、一致する場合である。
【００５０】
本発明のその他の観点に係るセッション鍵システムは、素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数F，G，H0，H1，H2と、を、端末装置とサーバ装置とで共有し、サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、端末装置には、当該n個のパスワードのうち、pw[1]，…，pw[k]が保有されるセッション鍵システムであって、以下のように構成する。
【００５１】
まず、端末装置は、端末選択部、端末第１計算部、端末第１送信部を備える。
【００５２】
ここで、端末選択部は、体Zpの元からx，γ[1]，…，γ[k]，a[1]，…，a[k]，w[k+1]，…，w[n]を一様にランダムに選択する。
【００５３】
一方、端末第１計算部は、選択されたx，γ[1]，…，γ[k]，a[1]，…，a[k]，w[k+1]，…，w[n]から、
X = gx
と、i = 1，…，kについて
w[i] = hγ[i]G(i,pw[i])；
A[i] = w[i]ga[i]
とを計算する。
【００５４】
さらに、端末第１送信部は、計算されたX，A[1]，…，A[k]，w[1]，…，w[n]を、サーバ装置に送信する。
【００５５】
一方、サーバ装置は、サーバ第１受信部、サーバ選択部、サーバ第１認証子生成部、サーバ送信部、サーバ鍵生成部を備える。
【００５６】
ここで、サーバ第１受信部は、端末装置から送信されたX，A[1]，…，A[k]，w[1]，…，w[n]を受信する。
【００５７】
一方、サーバ選択部は、体Zpの元からy，z，b[1]，…，b[k]を一様にランダムに選択する。
【００５８】
さらに、サーバ第１計算部は、f(x) = y + b[1]x + … b[k]xkとしたときに、
Y[1] = gf(1)，…，Y[n] = gf(n)；
Z = gz；
D[1] = A[1]z，…，D[k] = A[k]z；
を計算し、j = 1，…，nに対して、
α[j] = Y[j]gF(pw[j]) xor H0(w[i]z)；
KS = Xyを
を計算する。
【００５９】
さらに、サーバ第１認証子生成部は、サーバ側認証子AuthSを、
AuthS = H2(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KS)
のように生成する。
【００６０】
そして、サーバ送信部は、計算されたZ，D[1]，…，D[k]，α[1]，…，α[n]と、生成されたAuthSと、を、端末装置に送信する。
【００６１】
一方、サーバ鍵生成部は、サーバ側セッション鍵skSを、
skS = H1(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，Ks)
のように生成する。
【００６２】
一方、端末装置は、端末受信部、端末第２計算部、端末第１認証子生成部、端末鍵生成部をさらに備える。
【００６３】
ここで、端末受信部は、サーバ装置から送信されたZ，D[1]，…，D[k]，α[1]，…，α[n]，AuthSを受信する。
【００６４】
一方、端末第２計算部は、i = 1，…，kについて、
λ[i] = Π1≦j≦k，j≠i j/(j-i)
としたときに、
Y[i] = (α[i] xor H0(D[i]/Za[i]))/gF(pw[i])
を計算し、
Y = Y[1]λ[1]…Y[k]λ[k]；
KC = Yx
を計算する。
【００６５】
さらに、端末第１認証子生成部は、計算されたX，Y，KCと、受信されたZ，D[1]，…，D[k]，α[1]，…，α[n]と、から、端末側認証子AuthCを、
AuthC = H2(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KC)
のように生成する。
【００６６】
そして、端末鍵生成部は、受信されたAuthSと、生成されたAuthCと、が、一致する場合、端末側セッション鍵skCを、
skC = H1(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KC)
のように生成する。
【００６７】
また、本発明のセッション鍵システムにおいて、端末装置は、k台の機器を備え、i = 1，…，kについて、パスワードpw[i]はi番目の機器に保有され、γ[i]，a[i]の取得およびw[i]，A[i]，w[i]の計算は、i番目の機器が、j (j≠i)番目の機器とは独立に行うように構成することができる。
【００６８】
本発明のその他の観点に係るセッション鍵提供方法は、素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数Fと、を、端末装置とサーバ装置とで共有し、サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、端末装置には、当該n個のパスワードのうち、i番目のパスワードpw[i]が保有されるセッション鍵提供方法であって、以下のように構成する。
【００６９】
まず、端末装置において、端末選択工程、端末第１計算工程が実行される。
【００７０】
ここで、当該i番目のパスワードpw[i]に対して、端末選択工程では、体Zpの元からxを一様にランダムに選択する。
【００７１】
一方、端末第１計算工程では、選択されたxからgxを計算する。
【００７２】
一方、サーバ装置において、サーバ選択工程、サーバ第１計算工程が実行される。
【００７３】
ここで、サーバ選択工程では、体Zpの元からyを一様にランダムに選択する。
【００７４】
一方、サーバ第１計算工程では、選択されたyから、j = 1，…，nについて、
α[j] = gygF(pw[j])
を計算する。
【００７５】
さらに、端末装置において、端末第１送信工程が実行される。
【００７６】
ここで、端末第１送信工程では、計算されたgxを指定する1-out-of-n紛失通信問い合わせをサーバ装置に送信する。
【００７７】
そして、サーバ装置において、サーバ第１受信工程、サーバ鍵生成工程、サーバ送信工程がさらに実行される。
【００７８】
ここで、サーバ第１受信工程では、端末装置から送信された1-out-of-n紛失通信問い合わせを受信する。
【００７９】
一方、サーバ鍵生成工程では、受信された1-out-of-n紛失通信問い合わせに指定されるgxと、選択されたyと、から、
gxy = (gx)y
をサーバ側セッション鍵として生成する。
【００８０】
さらに、サーバ送信工程では、計算されたα[j] (j = 1，…，n)から、i番目のパスワードpw[i]を持つユーザがgygF(pw[i])の情報のみを得られるような1-out-of-n紛失通信応答を生成して端末装置に送信する。
【００８１】
一方、端末装置において、端末受信工程、端末鍵生成工程がさらに実行される。
【００８２】
ここで、端末受信工程では、サーバ装置から送信された1-out-of-n紛失通信応答を受信する。
【００８３】
一方、端末鍵生成工程では、受信された1-out-of-n紛失通信応答から、gygF(pw[i])の情報を得て、
gxy = (gygF(pw[i])/gF(pw[i]))x
を端末側セッション鍵として生成する。
【００８４】
本発明のその他の観点に係るセッション鍵提供方法は、素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数F，G，H0，H1，H2と、を、端末装置とサーバ装置とで共有し、サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、端末装置には、当該n個のパスワードのうち、i番目のパスワードpw[i]が保有されるセッション鍵提供方法であって、以下のように構成する。
【００８５】
まず、端末装置において、端末選択工程、端末第１計算工程、端末第１送信工程が実行される。
【００８６】
ここで、端末選択工程では、当該i番目のパスワードpw[i]に対して、体Zpの元からx，rを一様にランダムに選択する。
【００８７】
一方、端末第１計算工程では、選択されたx，rから、
X = gx；
Q(i) = grhG(i,pw[i])
を計算する。
【００８８】
さらに、端末第１送信工程では、計算されたXと、計算されたQ(i)と、を、組
(X,Q(i))
としてサーバ装置に送信する。
【００８９】
一方、サーバ装置において、サーバ第１受信工程、サーバ選択工程、サーバ第１計算工程、サーバ第１認証子生成工程、サーバ鍵生成工程、サーバ送信工程が実行される。
【００９０】
ここで、サーバ第１受信工程では、端末装置から送信された組
(X,Q(i))
を受信する。
【００９１】
一方、サーバ選択工程では、体Zpの元からy，k[1]，…，k[n]を一様にランダムに選択する。
【００９２】
さらに、サーバ第１計算工程では、受信された(X,Q(i))と、選択されたy，k[1]，…，k[n]と、から、
Y = gy
と、j = 1，…，nについて、
α[j] = YgF(pw[j])；
β[j] = H0((Q(i)/hG(j,pw[j]))k[j],j) xor α[j]
と、
A(Q(i)) = (β[1]，…，β[n]，gk[1]，…，gk[n])；
KS = Xy
と、を計算する。
【００９３】
さらに、サーバ第１認証子生成工程では、サーバ側認証子AuthSを、
AuthS = H2(X,A(Q(i)),Y,KS)
のように生成する。
【００９４】
そして、サーバ鍵生成工程では、サーバ側セッション鍵skSを、
skS = H1(X,A(Q(i)),Y,KS)
のように生成する。
【００９５】
一方、サーバ送信工程では、計算されたA(Q(i))と、生成されたサーバ側認証子AuthSと、を組
(A(Q(i)),AuthS)
として、端末装置に送信する。
【００９６】
一方、端末装置において、端末受信工程、端末第２計算工程、端末第１認証子生成工程、端末鍵生成工程がさらに実行される。
【００９７】
ここで、端末受信工程では、i番目のパスワードpw[i]に対して、
【００９８】
サーバ装置から送信された組
(A(Q(i)),AuthS)
を受信する。
【００９９】
一方、端末第２計算工程では、受信されたA(Q(i)) = (β[1]，…，β[n]，gk[1]，…，gk[n])から、
α[i] = β[i] xor H0((gk[i])r,i)；
Y = α[i]/gF(pw[i])；
KC = Yx；
を計算する。
【０１００】
さらに、端末第１認証子生成工程では、受信されたA(Q(i))と、計算されたY，KCと、から、端末側認証子AuthCを、
AuthC = H2(X,A(Q(i)),Y,KC)
のように生成する。
【０１０１】
一方、端末鍵生成工程では、受信されたAuthSと、生成されたAuthCと、が、一致する場合、端末側セッション鍵skCを、
skC = H1(X,A(Q(i)),Y,KC)
のように生成する。
【０１０２】
また、本発明のセッション鍵提供方法では、端末装置と、サーバ装置と、は、ハッシュ関数H3をさらに共有し、以下のように構成することができる。
【０１０３】
まず、端末装置において、端末第２認証子生成工程、端末第２送信工程がさらに実行される。
【０１０４】
ここで、端末第２認証子生成工程では、端末受信部により受信されたA(Q(i))と、端末第２計算部により計算されたY，KCと、から、端末側第２認証子AuthC'を、
AuthC' = H3(X,A(Q(i)),Y,KC)
のように生成する。
【０１０５】
一方、端末第２送信工程では、生成されたAuthC'を、サーバ装置に送信する。
【０１０６】
そして、サーバ装置において、サーバ第２受信工程、サーバ第２認証子生成工程がさらに実行される。
【０１０７】
ここで、サーバ第２受信工程では、端末装置から送信されたAuthC'を受信する。
【０１０８】
一方、サーバ第２認証子生成工程では、サーバ第１計算部により計算されたA(Q(i))，Y，KSから、サーバ側第２認証子AuthS'を、
AuthS' = H3(X,A(Q(i)),Y,KS)
のように生成する。
【０１０９】
さらに、サーバ鍵生成工程において、サーバ側セッション鍵skSを生成するのは、受信されたAuthC'と、生成されたAuthS'と、が、一致する場合である。
【０１１０】
本発明のその他の観点に係るセッション鍵提供方法は、素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数F，G，H0，H1，H2と、を、端末装置とサーバ装置とで共有し、サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、端末装置には、当該n個のパスワードのうち、pw[1]，…，pw[k]が保有されるセッション鍵提供方法であって、以下のように構成する。
【０１１１】
まず、端末装置において、端末選択工程、端末第１計算工程、端末第１送信工程が実行される。
【０１１２】
ここで、端末選択工程では、体Zpの元からx，γ[1]，…，γ[k]，a[1]，…，a[k]，w[k+1]，…，w[n]を一様にランダムに選択する。
【０１１３】
一方、端末第１計算工程では、選択されたx，γ[1]，…，γ[k]，a[1]，…，a[k]，w[k+1]，…，w[n]から、
X = gx
と、i = 1，…，kについて
w[i] = hγ[i]G(i,pw[i])；
A[i] = w[i]ga[i]
とを計算する。
【０１１４】
さらに、端末第１送信工程では、計算されたX，A[1]，…，A[k]，w[1]，…，w[n]を、サーバ装置に送信する。
【０１１５】
一方、サーバ装置において、サーバ第１受信工程、サーバ選択工程、サーバ第１認証子生成工程、サーバ送信工程、サーバ鍵生成工程が実行される。
【０１１６】
ここで、サーバ第１受信工程では、端末装置から送信されたX，A[1]，…，A[k]，w[1]，…，w[n]を受信する。
【０１１７】
一方、サーバ選択工程では、体Zpの元からy，z，b[1]，…，b[k]を一様にランダムに選択する
【０１１８】
さらに、サーバ第１計算工程では、f(x) = y + b[1]x + … b[k]xkとしたときに、
Y[1] = gf(1)，…，Y[n] = gf(n)；
Z = gz；
D[1] = A[1]z，…，D[k] = A[k]z；
【０１１９】
を計算し、j = 1，…，nに対して、
α[j] = Y[j]gF(pw[j]) xor H0(w[i]z)；
KS = Xyを
を計算する。
【０１２０】
さらに、サーバ第１認証子生成工程では、サーバ側認証子AuthSを、
AuthS = H2(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KS)
のように生成する。
【０１２１】
そして、サーバ送信工程では、計算されたZ，D[1]，…，D[k]，α[1]，…，α[n]と、生成されたAuthSと、を、端末装置に送信する。
【０１２２】
一方、サーバ鍵生成工程では、サーバ側セッション鍵skSを、
skS = H1(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，Ks)
のように生成する。
【０１２３】
一方、端末装置において、端末受信工程、端末第２計算工程、端末第１認証子生成工程、端末鍵生成工程がさらに実行される。
【０１２４】
ここで、端末受信工程では、サーバ装置から送信されたZ，D[1]，…，D[k]，α[1]，…，α[n]，AuthSを受信する。
【０１２５】
一方、端末第２計算工程では、i = 1，…，kについて、
λ[i] = Π1≦j≦k，j≠i j/(j-i)
としたときに、
Y[i] = (α[i] xor H0(D[i]/Za[i]))/gF(pw[i])
を計算し、
Y = Y[1]λ[1]…Y[k]λ[k]；
KC = Yx
を計算する。
【０１２６】
さらに、端末第１認証子生成工程では、計算されたX，Y，KCと、受信されたZ，D[1]，…，D[k]，α[1]，…，α[n]と、から、端末側認証子AuthCを、
AuthC = H2(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KC)
のように生成する。
【０１２７】
そして、端末鍵生成工程では、受信されたAuthSと、生成されたAuthCと、が、一致する場合、端末側セッション鍵skCを、
skC = H1(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KC)
のように生成する。
【０１２８】
本発明の他の観点に係るプログラムは、各種のコンピュータを、上記のセッション鍵システムの端末装置が備える各部として機能させるように構成する。
【０１２９】
本発明の他の観点に係るプログラムは、各種のコンピュータを、上記のセッション鍵システムのサーバ装置が備える各部として機能させるように構成する。
【０１３０】
本発明のプログラムを、少なくとも２つのコンピュータのそれぞれに実行させることにより、本発明のセッション鍵システム、および、セッション鍵提供方法を実現することができる。
【０１３１】
また、当該コンピュータとは独立して、本発明のプログラムを記録した情報記録媒体を配布、販売することができる。また、本発明のプログラムを、インターネット等のコンピュータ通信網を介して伝送し、配布、販売することができる。
【０１３２】
特に、当該コンピュータがＤＳＰ（Digital Signal Processor）やＦＰＧＡ（Field Programmable Gate Array）などのプログラム可能な電子回路を有する場合には、本発明の情報記録媒体に記録されたプログラムを無線にて当該コンピュータに伝送し、当該コンピュータ内のＤＳＰやＦＰＧＡにこれを実行させて、本発明の無線通信端末とすることができる。
【発明の効果】
【０１３３】
本発明によれば、小さいパスワードを共有することで、証明者があるグループの一員であることを、その証明者が実際に誰なのかを明かすことなく、検証者に対して証明するのに好適な、セッション鍵システム、セッション鍵提供方法、および、これらをコンピュータにおいて実現するためのプログラムを提供することができる。
【発明を実施するための最良の形態】
【０１３４】
以下に本発明の一実施形態を説明する。なお、以下に説明する実施形態は説明のためのものであり、本発明の範囲を制限するものではない。したがって、当業者であればこれらの各要素もしくは全要素をこれと均等なものに置換した実施形態を採用することが可能であるが、これらの実施形態も本発明の範囲に含まれる。
【実施例１】
【０１３５】
図１は、本発明のセッション鍵システムの最も基本的な実施形態に係る説明図である。以下、本図を参照して説明する。
【０１３６】
セッション鍵システム１０１は、１台以上の端末装置１３１と、１台のサーバ装置１５１と、両者を通信可能に接続するインターネット等のコンピュータ通信用の通信網１７１と、を備える。
【０１３７】
ここで、セッション鍵システム１０１は、素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数Fと、を、端末装置１３１とサーバ装置１５１とで共有する。
【０１３８】
GGの位数pがLビットのビット列で表現できる素数であるとすると、GGのすべての要素はLビットのビット列で表現できる。また、GGの演算は乗算として表現される。
【０１３９】
g，hはGGの生成元であり、これに対して繰り返し上記の演算を適用することにより、GGのすべての元が現れることになる。
【０１４０】
また、本発明で利用するハッシュ関数は、任意の長さのビット列を、長さLのビット列に変換するもので、いわゆるランダムオラクルである。
【０１４１】
また、サーバ装置１５１には、n個のパスワードpw[1]，…，pw[n]が保有される。すなわち、サーバ装置１５１では、n人のユーザのパスワードを保持していることになる。サーバ装置１５１におけるパスワードの辞書の典型的なサイズはおおよそ230程度であり、実際には、この中からn個の有効なパスワードが選択される。
【０１４２】
一方、端末装置１３１には、当該n個のパスワードのうち、i番目のパスワードpw[i]が保有される。
【０１４３】
すなわち、ユーザは、自分のパスワードを任意の端末装置１３１で使用することとなる。このパスワードをpw[i]としても、一般性を失わない。
【０１４４】
さて、端末装置１３１は、ユーザが何らかの形で与えたパスワードpw[i]に対して、処理を開始する。体Zpの元からxを一様にランダムに選択し、選択されたxからgxを計算する。
【０１４５】
サーバ装置１５１は、体Zpの元からyを一様にランダムに選択し、選択されたyから、j = 1，…，nについて、
α[j] = gygF(pw[j])
を計算する。
【０１４６】
さらに、端末装置１３１は、計算されたgxを指定する1-out-of-n紛失通信問い合わせをサーバ装置１５１に送信する。
【０１４７】
1-out-of-n紛失通信については、[非特許文献２][非特許文献３]に開示される効率の良い技術を採用することができ、詳細については後述する。ただし、他の紛失送信技術を適用することもでき、そのような実施態様も、本発明の範囲に含まれる。
【０１４８】
さて、サーバ装置１５１は、端末装置１３１から送信された1-out-of-n紛失通信問い合わせを受信し、受信された1-out-of-n紛失通信問い合わせに指定されるgxと、選択されたyと、から、
gxy = (gx)y
をサーバ側セッション鍵として生成する。
【０１４９】
さらに、計算されたα[j] (j = 1，…，n)から、i番目のパスワードpw[i]を持つユーザがgygF(pw[i])の情報のみを得られるような1-out-of-n紛失通信応答を生成して端末装置１３１に送信する。
【０１５０】
一方、端末装置１３１は、サーバ装置１５１から送信された1-out-of-n紛失通信応答を受信して、1-out-of-n紛失通信応答から、gygF(pw[i])の情報を得て、
gxy = (gygF(pw[i])/gF(pw[i]))x
を端末側セッション鍵として生成する。
【０１５１】
このように、本技術では、与えられた元g，gx，gyからgxyを効率良く求める計算Diffie-Hellman問題に帰着される。したがって、本技術の安全性は、計算Diffie-Hellman問題を効率良く求めるアルゴリズムが存在しない、という、現在技術界で同意されている仮定の下で、補償されることになる。
【０１５２】
以下、さらに詳細に、本技術について説明する。
【０１５３】
以下の例では、ハッシュ関数として、Fのほか、G，H0，H1，H2，H3を端末装置１３１とサーバ装置１５１とで共有する。典型的なハッシュ関数は１引数であるが、これらのハッシュ関数は任意の個数の引数をとることができる。この場合、任意の個数の引数を何らかの形で１つのビット列に変換し（たとえば、メモリ内でのデータ構造は、単なるビット列に還元できる。）、その１つのビット列に対してハッシュ関数を適用する、と考えることになる。
【０１５４】
図２は、端末装置１３１の概要構成を示す説明図である。以下、本図を参照して説明する。
【０１５５】
端末装置１３１は、端末選択部２０１、端末第１計算部２０２、端末第１送信部２０３、端末受信部２０４、端末第２計算部２０５、端末第１認証子生成部２０６、端末鍵生成部２０７を備える。
【０１５６】
なお、本図には、端末第２認証子生成部２０８、端末第２送信部２０９も図示してあるが、これらは、[実施例２]で必要となる要素である。
【０１５７】
図３は、端末装置１３１において実行される端末処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【０１５８】
まず、端末装置１３１の端末選択部２０１は、当該i番目のパスワードpw[i]に対して、体Zpの元からx，rを一様にランダムに選択する（ステップＳ３０１）。
【０１５９】
一方、端末第１計算部２０２は、選択されたx，rから、
X = gx；
Q(i) = grhG(i,pw[i])
を計算する（ステップＳ３０２）。
【０１６０】
さらに、端末第１送信部２０３は、計算されたXと、計算されたQ(i)と、を、組
(X,Q(i))
としてサーバ装置１５１に送信する（ステップＳ３０３）。
【０１６１】
図４は、サーバ装置１５１の概要構成を示す説明図である。以下、本図を参照して説明する。
【０１６２】
一方、サーバ装置１５１は、サーバ第１受信部４０１、サーバ選択部４０２、サーバ第１計算部４０３、サーバ第１認証子生成部４０４、サーバ鍵生成部４０５、サーバ送信部４０６を備える。
【０１６３】
なお、本図には、サーバ第２受信部４０７、サーバ第２認証子生成部４０８も図示してあるが、これらは、[実施例２]で必要となる要素である。
【０１６４】
図５は、サーバ装置１５１にて実行されるサーバ処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【０１６５】
サーバ装置１５１において、サーバ第１受信部４０１は、端末装置１３１から送信された組
(X,Q(i))
を受信する（ステップＳ５０１）。
【０１６６】
ついで、サーバ選択部４０２は、体Zpの元からy，k[1]，…，k[n]を一様にランダムに選択する（ステップＳ５０２）。
【０１６７】
さらに、サーバ第１計算部４０３は、受信された(X,Q(i))と、選択されたy，k[1]，…，k[n]と、から、
Y = gy
と、j = 1，…，nについて、
α[j] = YgF(pw[j])；
β[j] = H0((Q(i)/hG(j,pw[j]))k[j],j) xor α[j]
と、
A(Q(i)) = (β[1]，…，β[n]，gk[1]，…，gk[n])；
KS = Xy
と、を計算する（ステップＳ５０３）。
【０１６８】
さらに、サーバ第１認証子生成部４０４は、サーバ側認証子AuthSを、
AuthS = H2(X,A(Q(i)),Y,KS)
のように生成する（ステップＳ５０４）。
【０１６９】
そして、サーバ鍵生成部４０５は、サーバ側セッション鍵skSを、
skS = H1(X,A(Q(i)),Y,KS)
のように生成する（ステップＳ５０５）。
【０１７０】
一方、サーバ送信部４０６は、計算されたA(Q(i))と、生成されたサーバ側認証子AuthSと、を組
(A(Q(i)),AuthS)
として、端末装置１３１に送信して（ステップＳ５０６）、本処理を終了する。
【０１７１】
さて、端末装置１３１に戻り、端末受信部２０４は、i番目のパスワードpw[i]に対して、サーバ装置１５１から送信された組
(A(Q(i)),AuthS)
を受信する（ステップＳ３０４）。
【０１７２】
ついで、端末第２計算部２０５は、受信されたA(Q(i)) = (β[1]，…，β[n]，gk[1]，…，gk[n])から、
α[i] = β[i] xor H0((gk[i])r,i)；
Y = α[i]/gF(pw[i])；
KC = Yx；
を計算する（ステップＳ３０５）。
【０１７３】
さらに、端末第１認証子生成部２０６は、受信されたA(Q(i))と、計算されたY，KCと、から、端末側認証子AuthCを、
AuthC = H2(X,A(Q(i)),Y,KC)
のように生成する（ステップＳ３０６）。
【０１７４】
一方、端末鍵生成部２０７は、受信されたAuthSと、生成されたAuthCと、が、一致するか否かを判定し（ステップＳ３０７）一致する場合（ステップＳ３０７；Ｙｅｓ）、端末側セッション鍵skCを、
skC = H1(X,A(Q(i)),Y,KC)
のように生成して（ステップＳ３０８）、本処理を終了する。
【０１７５】
一致しない場合（ステップＳ３０７；Ｎｏ）、セッション鍵の提供が受けられなかった旨を報告して（ステップＳ３０９）、本処理を終了する。
【０１７６】
このようにして、サーバ装置１５１と端末装置１３１とで、skS = skCを共有することができる一方で、端末装置１３１で利用したパスワードpw[i]そのものは、サーバ装置１５１に直接渡されることがなく、匿名性を保つことができる。
【０１７７】
なお、端末装置１３１を使用しうるユーザの識別符号の集合（pw[1]を持つユーザの識別符号C[1]、…、pw[n]を持つユーザの識別符号C[n]）や、サーバ装置１５１の識別符号を、適宜通信の際に送受し、ハッシュ関数の計算においてこれらの識別符号も参照することとしても良い。
【０１７８】
たとえば、端末装置１３１からサーバ装置１５１へ送付される組に、C[1]，…，C[n]の情報を含めることとし、サーバ側認証子AuthSサーバ側セッション鍵skSの計算で、C[1]，…，C[n]，Sの情報を勘案することとする。
【０１７９】
そして、サーバ装置１５１から端末装置１３１へ送付される組に、Sの情報を含めることとし、端末側認証子AuthC端末側セッション鍵skCの計算で、C[1]，…，C[n]，Sの情報を勘案することとするのである。
【０１８０】
以下の実施例についても、同様である。
【実施例２】
【０１８１】
本実施例では、サーバ装置１５１で、端末装置１３１を使用しているユーザの正当性を認証する。
【０１８２】
図６は、図３に示す端末処理が成功裏に終了した後に、端末装置１３１にて実行される処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【０１８３】
端末装置１３１において、ステップＳ３０８の後、端末第２認証子生成部２０８は、端末受信部２０４により受信されたA(Q(i))と、端末第２計算部２０５により計算されたY，KCと、から、端末側第２認証子AuthC'を、
AuthC' = H3(X,A(Q(i)),Y,KC)
のように生成する（ステップＳ６０１）。
【０１８４】
一方、端末第２送信部２０９は、生成されたAuthC'を、サーバ装置１５１に送信して（ステップＳ６０２）、本処理を終了する。
【０１８５】
図７は、図５に示すサーバ処理の制御の流れの一部を変形して本実施例に係るものとしたフローチャートである。以下、本図を参照して説明する。
【０１８６】
サーバ装置は、AuthSを生成した後（ステップＳ５０４）、ステップＳ５０５は実行せずに、組(A(Q(i)),AuthS)を端末装置１３１に送信してから（ステップＳ５０６）、以下の処理を開始する。
【０１８７】
すなわち、サーバ第２受信部４０７は、端末装置１３１から送信されたAuthC'を受信する（ステップＳ７０１）。
【０１８８】
ついで、サーバ第２認証子生成部４０８は、サーバ第１計算部４０３により計算されたA(Q(i))，Y，KSから、サーバ側第２認証子AuthS'を、
AuthS' = H3(X,A(Q(i)),Y,KS)
のように生成する（ステップＳ７０２）。
【０１８９】
さらに、受信されたAuthC'と、生成されたAuthS'と、が、一致するか否かを判定し（ステップＳ７０３）、一致する場合（ステップＳ７０３；Ｙｅｓ）、サーバ鍵生成部４０５が、サーバ側セッション鍵skSを生成して（ステップＳ５０５）、本処理を終了する。
【０１９０】
一致しない場合（ステップＳ７０３；Ｎｏ）、ユーザの正当性の認証に失敗した旨を報告して（ステップＳ７０４）、本処理を終了する。
【実施例３】
【０１９１】
上記の[実施例１][実施例２]は、いずれも、1-out-of-n紛失通信に相当するものであったが、本実施例は、k-out-of-n紛失通信に相当するものである。すなわち、全ユーザがn人でいる場合に、その中のk人がサーバとセッション鍵を共有するためのものである。
【０１９２】
この場合、k人のユーザが使用する端末装置１３１は、典型的には異なる機械であるが、理解を容易にするため、以下では、これらをまとめて１つの端末装置１３１として説明し、必要に応じて、個々の機械で行う処理と、これらを統合してまとめて行う処理と、を説明することとする。
【０１９３】
また、制御のおおまかな流れや各部の処理については、上記の[実施例１]と同様であるので、適宜説明を省略する。
【０１９４】
本実施例のセッション鍵システム１０１では、サーバ装置１５１には、n個のパスワードpw[1]，…，pw[n]が保有され、端末装置１３１には、当該n個のパスワードのうち、少なくともpw[1]，…，pw[k]が公開される。
（１） まず、端末装置１３１において、端末選択部２０１は、体Zpの元からx，γ[1]，…，γ[k]，a[1]，…，a[k]，w[k+1]，…，w[n]を一様にランダムに選択する。
【０１９５】
次に、端末装置１３１において、端末第１計算部２０２は、選択されたx，γ[1]，…，γ[k]，a[1]，…，a[k]，w[k+1]，…，w[n]から、
X = gx
と、i = 1，…，kについて
w[i] = hγ[i]G(i,pw[i])；
A[i] = w[i]ga[i]
とを計算する。
【０１９６】
さらに、端末装置１３１において、端末第１送信部２０３は、計算されたX，A[1]，…，A[k]，w[1]，…，w[n]を、サーバ装置１５１に送信する。
【０１９７】
典型的には、Xの計算は、いずれか１台の機械が行い、w[i]，A[i]の計算は、それぞれのユーザの機械が行う。これにより、各人のパスワードが他人に漏曳することはない。そして、いずれかの１台（典型的にはXを計算した１台）に結果を集めてからサーバ装置１５１に送信する。
（２） 次に、サーバ装置１５１において、サーバ第１受信部４０１は、端末装置１３１から送信されたX，A[1]，…，A[k]，w[1]，…，w[n]を受信する。
【０１９８】
ついで、サーバ装置１５１において、サーバ選択部４０２は、体Zpの元からy，z，b[1]，…，b[k]を一様にランダムに選択する。
【０１９９】
さらに、サーバ装置１５１において、サーバ第１計算部４０３は、f(x) = y + b[1]x + … b[k]xkとしたときに、
Y[1] = gf(1)，…，Y[n] = gf(n)；
Z = gz；
D[1] = A[1]z，…，D[k] = A[k]z；
【０２００】
を計算し、j = 1，…，nに対して、
α[j] = Y[j]gF(pw[j]) xor H0(w[i]z)；
KS = Xyを
を計算する。
【０２０１】
そして、サーバ装置１５１において、サーバ第１認証子生成部４０４は、サーバ側認証子AuthSを、
AuthS = H2(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KS)
のように生成する。
【０２０２】
次に、サーバ装置１５１において、サーバ送信部４０６は、計算されたZ，D[1]，…，D[k]，α[1]，…，α[n]と、生成されたAuthSと、を、端末装置１３１に送信する。
【０２０３】
典型的には、Z，D[1]，…，D[k]，α[1]，…，α[n]，AuthSが送信される端末装置１３１は、ユーザが利用するすべての機械であるが、１台がとりまとめて受信し、各機械に分配することとしても良い。
【０２０４】
さらに、サーバ装置１５１において、サーバ鍵生成部４０５は、サーバ側セッション鍵skSを、
skS = H1(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，Ks)
のように生成する。
（３） そして、端末装置１３１において、端末受信部２０４は、サーバ装置１５１から送信されたZ，D[1]，…，D[k]，α[1]，…，α[n]，AuthSを受信する。これらは、ユーザが使用する機械に分配されるのが典型的である。
【０２０５】
ついで、端末装置１３１において、端末第２計算部２０５は、i = 1，…，kについて、
λ[i] = Π1≦j≦k，j≠i j/(j-i)
としたときに、
Y[i] = (α[i] xor H0(D[i]/Za[i]))/gF(pw[i])
を計算し、
Y = Y[1]λ[1]…Y[k]λ[k]；
KC = Yx
を計算する。
【０２０６】
さらに、端末装置１３１において、端末第１認証子生成部２０６は、計算されたX，Y，KCと、受信されたZ，D[1]，…，D[k]，α[1]，…，α[n]と、から、端末側認証子AuthCを、
AuthC = H2(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KC)
のように生成する。
【０２０７】
Y[i]の計算は、それぞれのユーザが利用する機械で行うこととすれば、パスワードが漏れることはない。そして、計算されたX，Y[1]，…，Y[k]は、それぞれのユーザが利用する機械で共有することとするのである。
【０２０８】
そして、端末装置１３１において、端末鍵生成部２０７は、受信されたAuthSと、生成されたAuthCと、が、一致する場合、端末側セッション鍵skCを、
skC = H1(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KC)
のように生成する。
【０２０９】
上記のように、個々のパスワード以外の情報は、共有したり、独立に計算できるので、skCの計算も個々の機械で独立して計算することができる。
【０２１０】
このように、k人のユーザが集まることによって、秘密鍵となるセッション鍵を共有し、かつ、匿名を保ちながらパスワードを利用して認証を行うことができる。また、k人未満のユーザが集まっても、セッション鍵共有を行うことはできない。
【０２１１】
上述した通り、k人のユーザが使用する端末装置１３１は、典型的には異なる機械である。そこで、これらを仮にi = 1，…，k番目の機器としたとき、i番目の機器はパスワードpw[i]を保有することとし、他のパスワードpw[j] (j≠i)は知らないようにすることができる。
【０２１２】
γ[i]，a[i]のランダム選択やw[i]，A[i]，Y[i]の計算は、i番目の機器のみで独立に行うことができるため、pw[i]を他のj (j≠i)番目の機器に知られずにすむ。
【０２１３】
また、x，w[k+1]，…，w[n]のランダムな選択や、Xの計算は、k台の機器のいずれかが代表として行うこととすれば良い。w[i]，A[i]の情報は、この代表がとりまとめてサーバ装置１５１に送ることとする。また、それぞれの機器が計算したY[i]は、代表に集められ、YやKCの計算は代表が行うこととする。
【０２１４】
このような、k台の機器の群を、上記の説明では、「１台の端末装置１３１」として表現している。
【産業上の利用可能性】
【０２１５】
以上説明したように、本発明によれば、小さいパスワードを共有することで、証明者があるグループの一員であることを、その証明者が実際に誰なのかを明かすことなく、検証者に対して証明するのに好適な、セッション鍵システム、セッション鍵提供方法、および、これらをコンピュータにおいて実現するためのプログラムを提供することができる。
【図面の簡単な説明】
【０２１６】
【図１】本発明のセッション鍵システムの最も基本的な実施形態に係る説明図である。
【図２】端末装置の概要構成を示す説明図である。
【図３】端末装置において実行される端末処理の制御の流れを示すフローチャートである。
【図４】サーバ装置の概要構成を示す説明図である。
【図５】サーバ装置にて実行されるサーバ処理の制御の流れを示すフローチャートである。
【図６】端末処理が成功裏に終了した後に端末装置にて実行される処理の制御の流れを示すフローチャートである。
【図７】図５に示すサーバ処理の制御の流れの一部を変形したフローチャートである。
【符号の説明】
【０２１７】
１０１ セッション鍵システム
１３１ 端末装置
１５１ サーバ装置
１７１ 通信網
２０１ 端末選択部
２０２ 端末第１計算部
２０３ 端末第１送信部
２０４ 端末受信部
２０５ 端末第２計算部
２０６ 端末第１認証子生成部
２０７ 端末鍵生成部
２０８ 端末第２認証子生成部
２０９ 端末第２送信部
４０１ サーバ第１受信部
４０２ サーバ選択部
４０３ サーバ第１計算部
４０４ サーバ第１認証子生成部
４０５ サーバ鍵生成部
４０６ サーバ送信部
４０７ サーバ第２受信部
４０８ サーバ第２認証子生成部
【特許請求の範囲】
【請求項１】
素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数Fと、を、端末装置とサーバ装置とで共有し、前記サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、前記端末装置には、当該n個のパスワードのうち、i番目のパスワードpw[i]が保有されるセッション鍵システムであって、
（ａ） 前記端末装置は、当該i番目のパスワードpw[i]に対して、
体Zpの元からxを一様にランダムに選択する端末選択部、
前記選択されたxからgxを計算する端末第１計算部
を備え、
（ｂ） 前記サーバ装置は、
体Zpの元からyを一様にランダムに選択するサーバ選択部、
前記選択されたyから、j = 1，…，nについて、
α[j] = gygF(pw[j])
を計算するサーバ第１計算部
を備え、
（ｃ） 前記端末装置は、
前記計算されたgxを指定する1-out-of-n紛失通信問い合わせを前記サーバ装置に送信する端末第１送信部
をさらに備え、
（ｄ） 前記サーバ装置は、
前記端末装置から送信された1-out-of-n紛失通信問い合わせを受信するサーバ第１受信部、
前記受信された1-out-of-n紛失通信問い合わせに指定されるgxと、前記選択されたyと、から、
gxy = (gx)y
をサーバ側セッション鍵として生成するサーバ鍵生成部、
前記計算されたα[j] (j = 1，…，n)から、i番目のパスワードpw[i]を持つユーザがgygF(pw[i])の情報のみを得られるような1-out-of-n紛失通信応答を生成して前記端末装置に送信するサーバ送信部
をさらに備え、
（ｄ）前記端末装置は、
前記サーバ装置から送信された1-out-of-n紛失通信応答を受信する端末受信部、
前記受信された1-out-of-n紛失通信応答から、gygF(pw[i])の情報を得て、
gxy = (gygF(pw[i])/gF(pw[i]))x
を端末側セッション鍵として生成する端末鍵生成部
をさらに備える
ことを特徴とするセッション鍵システム。
【請求項２】
素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数F，G，H0，H1，H2と、を、端末装置とサーバ装置とで共有し、前記サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、前記端末装置には、当該n個のパスワードのうち、i番目のパスワードpw[i]が保有されるセッション鍵システムであって、
（ａ） 前記端末装置は、当該i番目のパスワードpw[i]に対して、
体Zpの元からx，rを一様にランダムに選択する端末選択部、
前記選択されたx，rから、
X = gx；
Q(i) = grhG(i,pw[i])
を計算する端末第１計算部、
前記計算されたXと、前記計算されたQ(i)と、を、組
(X,Q(i))
としてサーバ装置に送信する端末第１送信部
を備え、
（ｂ） 前記サーバ装置は、
前記端末装置から送信された組
(X,Q(i))
を受信するサーバ第１受信部、
体Zpの元からy，k[1]，…，k[n]を一様にランダムに選択するサーバ選択部、
前記受信された(X,Q(i))と、前記選択されたy，k[1]，…，k[n]と、から、
Y = gy
と、j = 1，…，nについて、
α[j] = YgF(pw[j])；
β[j] = H0((Q(i)/hG(j,pw[j]))k[j],j) xor α[j]
と、
A(Q(i)) = (β[1]，…，β[n]，gk[1]，…，gk[n])；
KS = Xy
と、を計算するサーバ第１計算部、
サーバ側認証子AuthSを、
AuthS = H2(X,A(Q(i)),Y,KS)
のように生成するサーバ第１認証子生成部、
サーバ側セッション鍵skSを、
skS = H1(X,A(Q(i)),Y,KS)
のように生成するサーバ鍵生成部、
前記計算されたA(Q(i))と、前記生成されたサーバ側認証子AuthSと、を組
(A(Q(i)),AuthS)
として、前記端末装置に送信するサーバ送信部
を備え、
（ｃ） 前記端末装置は、i番目のパスワードpw[i]に対して、
前記サーバ装置から送信された組
(A(Q(i)),AuthS)
を受信する端末受信部、
前記受信されたA(Q(i)) = (β[1]，…，β[n]，gk[1]，…，gk[n])から、
α[i] = β[i] xor H0((gk[i])r,i)；
Y = α[i]/gF(pw[i])；
KC = Yx；
を計算する端末第２計算部、
前記受信されたA(Q(i))と、前記計算されたY，KCと、から、端末側認証子AuthCを、
AuthC = H2(X,A(Q(i)),Y,KC)
のように生成する端末第１認証子生成部、
前記受信されたAuthSと、前記生成されたAuthCと、が、一致する場合、端末側セッション鍵skCを、
skC = H1(X,A(Q(i)),Y,KC)
のように生成する端末鍵生成部
をさらに備える
ことを特徴とするセッション鍵システム。
【請求項３】
請求項１に記載のセッション鍵システムであって、前記端末装置と、前記サーバ装置と、は、ハッシュ関数H3をさらに共有し、
（ｄ） 前記端末装置は、
前記端末受信部により受信されたA(Q(i))と、前記端末第２計算部により計算されたY，KCと、から、端末側第２認証子AuthC'を、
AuthC' = H3(X,A(Q(i)),Y,KC)
のように生成する端末第２認証子生成部、
前記生成されたAuthC'を、前記サーバ装置に送信する端末第２送信部
をさらに備え、
（ｅ） 前記サーバ装置は、
前記端末装置から送信されたAuthC'を受信するサーバ第２受信部、
前記サーバ第１計算部により計算されたA(Q(i))，Y，KSから、サーバ側第２認証子AuthS'を、
AuthS' = H3(X,A(Q(i)),Y,KS)
のように生成するサーバ第２認証子生成部
をさらに備え、
前記サーバ装置が備えるサーバ鍵生成部が、サーバ側セッション鍵skSを生成するのは、前記受信されたAuthC'と、前記生成されたAuthS'と、が、一致する場合である
ことを特徴とするセッション鍵システム。
【請求項４】
素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数F，G，H0，H1，H2と、を、端末装置とサーバ装置とで共有し、サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、前記端末装置には、当該n個のパスワードのうち、pw[1]，…，pw[k]が保有されるセッション鍵システムであって、
（ａ）前記端末装置は、
体Zpの元からx，γ[1]，…，γ[k]，a[1]，…，a[k]，w[k+1]，…，w[n]を一様にランダムに選択する端末選択部、
前記選択されたx，γ[1]，…，γ[k]，a[1]，…，a[k]，w[k+1]，…，w[n]から、
X = gx
と、i = 1，…，kについて
w[i] = hγ[i]G(i,pw[i])；
と、i = 1，…，nについて
A[i] = w[i]ga[i]
とを計算する端末第１計算部、
前記計算されたX，A[1]，…，A[k]，w[1]，…，w[n]を、前記サーバ装置に送信する端末第１送信部
を備え、
（ｂ） 前記サーバ装置は、
前記端末装置から送信されたX，A[1]，…，A[k]，w[1]，…，w[n]を受信するサーバ第１受信部、
体Zpの元からy，z，b[1]，…，b[k]を一様にランダムに選択するサーバ選択部、
f(x) = y + b[1]x + … b[k]xkとしたときに、
Y[1] = gf(1)，…，Y[n] = gf(n)；
Z = gz；
D[1] = A[1]z，…，D[k] = A[k]z；
を計算し、j = 1，…，nに対して、
α[j] = Y[j]gF(pw[j]) xor H0(w[i]z)；
KS = Xyを
を計算するサーバ第１計算部、
サーバ側認証子AuthSを、
AuthS = H2(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KS)
のように生成するサーバ第１認証子生成部、
前記計算されたZ，D[1]，…，D[k]，α[1]，…，α[n]と、前記生成されたAuthSと、を、前記端末装置に送信するサーバ送信部、
サーバ側セッション鍵skSを、
skS = H1(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，Ks)
のように生成するサーバ鍵生成部、
を備え、
（ｃ） 前記端末装置は、
前記サーバ装置から送信されたZ，D[1]，…，D[k]，α[1]，…，α[n]，AuthSを受信する端末受信部、
i = 1，…，kについて、
λ[i] = Π1≦j≦k，j≠i j/(j-i)
としたときに、
Y[i] = (α[i] xor H0(D[i]/Za[i]))/gF(pw[i])
を計算し、
Y = Y[1]λ[1]…Y[k]λ[k]；
KC = Yx
を計算する端末第２計算部、
前記計算されたX，Y，KCと、前記受信されたZ，D[1]，…，D[k]，α[1]，…，α[n]と、から、端末側認証子AuthCを、
AuthC = H2(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KC)
のように生成する端末第１認証子生成部、
前記受信されたAuthSと、前記生成されたAuthCと、が、一致する場合、端末側セッション鍵skCを、
skC = H1(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KC)
のように生成する端末鍵生成部
をさらに備える
ことを特徴とするセッション鍵システム。
【請求項５】
素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数Fと、を、端末装置とサーバ装置とで共有し、前記サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、前記端末装置には、当該n個のパスワードのうち、i番目のパスワードpw[i]が保有されるセッション鍵提供方法であって、
（ａ） 前記端末装置が、当該i番目のパスワードpw[i]に対して、
体Zpの元からxを一様にランダムに選択する端末選択工程、
前記選択されたxからgxを計算する端末第１計算工程
を備え、
（ｂ） 前記サーバ装置が、
体Zpの元からyを一様にランダムに選択するサーバ選択工程
前記選択されたyから、j = 1，…，nについて、
α[j] = gygF(pw[j])
を計算するサーバ第１計算工程
を備え、
（ｃ） 前記端末装置が、
前記計算されたgxを指定する1-out-of-n紛失通信問い合わせを前記サーバ装置に送信する端末第１送信工程
をさらに備え、
（ｄ） 前記サーバ装置が、
前記端末装置から送信された1-out-of-n紛失通信問い合わせを受信するサーバ第１受信工程、
前記受信された1-out-of-n紛失通信問い合わせに指定されるgxと、前記選択されたyと、から、
gxy = (gx)y
をサーバ側セッション鍵として生成するサーバ鍵生成工程、
前記計算されたα[j] (j = 1，…，n)から、i番目のパスワードpw[i]を持つユーザがgygF(pw[i])の情報のみを得られるような1-out-of-n紛失通信応答を生成して前記端末装置に送信するサーバ送信工程
をさらに備え、
（ｄ）前記端末装置が、
前記サーバ装置から送信された1-out-of-n紛失通信応答を受信する端末受信工程
前記受信された1-out-of-n紛失通信応答から、gygF(pw[i])の情報を得て、
gxy = (gygF(pw[i])/gF(pw[i]))x
を端末側セッション鍵として生成する端末鍵生成工程
をさらに備える
ことを特徴とするセッション鍵提供方法。
【請求項６】
素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数F，G，H0，H1，H2と、を、端末装置とサーバ装置とで共有し、前記サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、前記端末装置には、当該n個のパスワードのうち、i番目のパスワードpw[i]が保有されるセッション鍵提供方法であって、
（ａ） 前記端末装置が、当該i番目のパスワードpw[i]に対して、
体Zpの元からx，rを一様にランダムに選択する端末選択工程、
前記選択されたx，rから、
X = gx；
Q(i) = grhG(i,pw[i])
を計算する端末第１計算工程、
前記計算されたXと、前記計算されたQ(i)と、を、組
(X,Q(i))
としてサーバ装置に送信する端末第１送信工程
を備え、
（ｂ） 前記サーバ装置が、
前記端末装置から送信された組
(X,Q(i))
を受信するサーバ第１受信工程、
体Zpの元からy，k[1]，…，k[n]を一様にランダムに選択するサーバ選択工程、
前記受信された(X,Q(i))と、前記選択されたy，k[1]，…，k[n]と、から、
Y = gy
と、j = 1，…，nについて、
α[j] = YgF(pw[j])；
β[j] = H0((Q(i)/hG(j,pw[j]))k[j],j) xor α[j]
と、
A(Q(i)) = (β[1]，…，β[n]，gk[1]，…，gk[n])；
KS = Xy
と、を計算するサーバ第１計算工程、
サーバ側認証子AuthSを、
AuthS = H2(X,A(Q(i)),Y,KS)
のように生成するサーバ第１認証子生成工程、
サーバ側セッション鍵skSを、
skS = H1(X,A(Q(i)),Y,KS)
のように生成するサーバ鍵生成工程、
前記計算されたA(Q(i))と、前記生成されたサーバ側認証子AuthSと、を組
(A(Q(i)),AuthS)
として、前記端末装置に送信するサーバ送信工程
を備え、
（ｃ） 前記端末装置が、i番目のパスワードpw[i]に対して、
前記サーバ装置から送信された組
(A(Q(i)),AuthS)
を受信する端末受信工程、
前記受信されたA(Q(i)) = (β[1]，…，β[n]，gk[1]，…，gk[n])から、
α[i] = β[i] xor H0((gk[i])r,i)；
Y = α[i]/gF(pw[i])；
KC = Yx；
を計算する端末第２計算工程、
前記受信されたA(Q(i))と、前記計算されたY，KCと、から、端末側認証子AuthCを、
AuthC = H2(X,A(Q(i)),Y,KC)
のように生成する端末第１認証子生成工程、
前記受信されたAuthSと、前記生成されたAuthCと、が、一致する場合、端末側セッション鍵skCを、
skC = H1(X,A(Q(i)),Y,KC)
のように生成する端末鍵生成工程
をさらに備える
ことを特徴とするセッション鍵地峡方法。
【請求項７】
請求項６に記載のセッション鍵提供方法であって、前記端末装置と、前記サーバ装置と、は、ハッシュ関数H3をさらに共有し、
（ｄ） 前記端末装置が、
前記端末受信工程にて受信されたA(Q(i))と、前記端末第２計算工程にて計算されたY，KCと、から、端末側第２認証子AuthC'を、
AuthC' = H3(X,A(Q(i)),Y,KC)
のように生成する端末第２認証子生成工程、
前記生成されたAuthC'を、前記サーバ装置に送信する端末第２送信工程
をさらに備え、
（ｅ） 前記サーバ装置が、
前記端末装置から送信されたAuthC'を受信するサーバ第２受信工程、
前記サーバ第１計算工程にて計算されたA(Q(i))，Y，KSから、サーバ側第２認証子AuthS'を、
AuthS' = H3(X,A(Q(i)),Y,KS)
のように生成するサーバ第２認証子生成工程
をさらに備え、
前記サーバ鍵生成工程にて、サーバ側セッション鍵skSを生成するのは、前記受信されたAuthC'と、前記生成されたAuthS'と、が、一致する場合である
ことを特徴とするセッション鍵提供方法。
【請求項８】
素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数F，G，H0，H1，H2と、を、端末装置とサーバ装置とで共有し、サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、前記端末装置には、当該n個のパスワードのうち、pw[1]，…，pw[k]が保有されるセッション鍵提供方法であって、
（ａ）前記端末装置が、
体Zpの元からx，γ[1]，…，γ[k]，a[1]，…，a[k]，w[k+1]，…，w[n]を一様にランダムに選択する端末選択工程、
前記選択されたx，γ[1]，…，γ[k]，a[1]，…，a[k]，w[k+1]，…，w[n]から、
X = gx
と、i = 1，…，kについて
w[i] = hγ[i]G(i,pw[i])；
A[i] = w[i]ga[i]
とを計算する端末第１計算工程、
前記計算されたX，A[1]，…，A[k]，w[1]，…，w[n]を、前記サーバ装置に送信する端末第１送信工程
を備え、
（ｂ） 前記サーバ装置が、
前記端末装置から送信されたX，A[1]，…，A[k]，w[1]，…，w[n]を受信するサーバ第１受信工程、
体Zpの元からy，z，b[1]，…，b[k]を一様にランダムに選択するサーバ選択工程、
f(x) = y + b[1]x + … b[k]xkとしたときに、
Y[1] = gf(1)，…，Y[n] = gf(n)；
Z = gz；
D[1] = A[1]z，…，D[k] = A[k]z；
を計算し、j = 1，…，nに対して、
α[j] = Y[j]gF(pw[j]) xor H0(w[i]z)；
KS = Xyを
を計算するサーバ第１計算工程、
サーバ側認証子AuthSを、
AuthS = H2(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KS)
のように生成するサーバ第１認証子生成工程、
前記計算されたZ，D[1]，…，D[k]，α[1]，…，α[n]と、前記生成されたAuthSと、を、前記端末装置に送信するサーバ送信工程、
サーバ側セッション鍵skSを、
skS = H1(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，Ks)
のように生成するサーバ鍵生成工程、
を備え、
（ｃ） 前記端末装置が、
前記サーバ装置から送信されたZ，D[1]，…，D[k]，α[1]，…，α[n]，AuthSを受信する端末受信工程、
i = 1，…，kについて、
λ[i] = Π1≦j≦k，j≠i j/(j-i)
としたときに、
Y[i] = (α[i] xor H0(D[i]/Za[i]))/gF(pw[i])
を計算し、
Y = Y[1]λ[1]…Y[k]λ[k]；
KC = Yx
を計算する端末第２計算工程、
前記計算されたX，Y，KCと、前記受信されたZ，D[1]，…，D[k]，α[1]，…，α[n]と、から、端末側認証子AuthCを、
AuthC = H2(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KC)
のように生成する端末第１認証子生成工程、
前記受信されたAuthSと、前記生成されたAuthCと、が、一致する場合、端末側セッション鍵skCを、
skC = H1(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KC)
のように生成する端末鍵生成工程
をさらに備える
ことを特徴とするセッション鍵提供方法。
【請求項９】
コンピュータを、請求項１から４のいずれか１項に記載のセッション鍵システムの端末装置が備える各部として機能させることを特徴とするプログラム。
【請求項１０】
コンピュータを、請求項１から４のいずれか１項に記載のセッション鍵システムのサーバ装置が備える各部として機能させることを特徴とするプログラム。
【請求項１１】
請求項４に記載のセッション鍵システムであって、
前記端末装置は、k台の機器を備え、
i = 1，…，kについて、パスワードpw[i]はi番目の機器に保有され、γ[i]，a[i]の取得およびw[i]，A[i]，w[i]の計算は、i番目の機器が、j (j≠i)番目の機器とは独立に行う
ことを特徴とするセッション鍵システム。
【請求項１】
素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数Fと、を、端末装置とサーバ装置とで共有し、前記サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、前記端末装置には、当該n個のパスワードのうち、i番目のパスワードpw[i]が保有されるセッション鍵システムであって、
（ａ） 前記端末装置は、当該i番目のパスワードpw[i]に対して、
体Zpの元からxを一様にランダムに選択する端末選択部、
前記選択されたxからgxを計算する端末第１計算部
を備え、
（ｂ） 前記サーバ装置は、
体Zpの元からyを一様にランダムに選択するサーバ選択部、
前記選択されたyから、j = 1，…，nについて、
α[j] = gygF(pw[j])
を計算するサーバ第１計算部
を備え、
（ｃ） 前記端末装置は、
前記計算されたgxを指定する1-out-of-n紛失通信問い合わせを前記サーバ装置に送信する端末第１送信部
をさらに備え、
（ｄ） 前記サーバ装置は、
前記端末装置から送信された1-out-of-n紛失通信問い合わせを受信するサーバ第１受信部、
前記受信された1-out-of-n紛失通信問い合わせに指定されるgxと、前記選択されたyと、から、
gxy = (gx)y
をサーバ側セッション鍵として生成するサーバ鍵生成部、
前記計算されたα[j] (j = 1，…，n)から、i番目のパスワードpw[i]を持つユーザがgygF(pw[i])の情報のみを得られるような1-out-of-n紛失通信応答を生成して前記端末装置に送信するサーバ送信部
をさらに備え、
（ｄ）前記端末装置は、
前記サーバ装置から送信された1-out-of-n紛失通信応答を受信する端末受信部、
前記受信された1-out-of-n紛失通信応答から、gygF(pw[i])の情報を得て、
gxy = (gygF(pw[i])/gF(pw[i]))x
を端末側セッション鍵として生成する端末鍵生成部
をさらに備える
ことを特徴とするセッション鍵システム。
【請求項２】
素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数F，G，H0，H1，H2と、を、端末装置とサーバ装置とで共有し、前記サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、前記端末装置には、当該n個のパスワードのうち、i番目のパスワードpw[i]が保有されるセッション鍵システムであって、
（ａ） 前記端末装置は、当該i番目のパスワードpw[i]に対して、
体Zpの元からx，rを一様にランダムに選択する端末選択部、
前記選択されたx，rから、
X = gx；
Q(i) = grhG(i,pw[i])
を計算する端末第１計算部、
前記計算されたXと、前記計算されたQ(i)と、を、組
(X,Q(i))
としてサーバ装置に送信する端末第１送信部
を備え、
（ｂ） 前記サーバ装置は、
前記端末装置から送信された組
(X,Q(i))
を受信するサーバ第１受信部、
体Zpの元からy，k[1]，…，k[n]を一様にランダムに選択するサーバ選択部、
前記受信された(X,Q(i))と、前記選択されたy，k[1]，…，k[n]と、から、
Y = gy
と、j = 1，…，nについて、
α[j] = YgF(pw[j])；
β[j] = H0((Q(i)/hG(j,pw[j]))k[j],j) xor α[j]
と、
A(Q(i)) = (β[1]，…，β[n]，gk[1]，…，gk[n])；
KS = Xy
と、を計算するサーバ第１計算部、
サーバ側認証子AuthSを、
AuthS = H2(X,A(Q(i)),Y,KS)
のように生成するサーバ第１認証子生成部、
サーバ側セッション鍵skSを、
skS = H1(X,A(Q(i)),Y,KS)
のように生成するサーバ鍵生成部、
前記計算されたA(Q(i))と、前記生成されたサーバ側認証子AuthSと、を組
(A(Q(i)),AuthS)
として、前記端末装置に送信するサーバ送信部
を備え、
（ｃ） 前記端末装置は、i番目のパスワードpw[i]に対して、
前記サーバ装置から送信された組
(A(Q(i)),AuthS)
を受信する端末受信部、
前記受信されたA(Q(i)) = (β[1]，…，β[n]，gk[1]，…，gk[n])から、
α[i] = β[i] xor H0((gk[i])r,i)；
Y = α[i]/gF(pw[i])；
KC = Yx；
を計算する端末第２計算部、
前記受信されたA(Q(i))と、前記計算されたY，KCと、から、端末側認証子AuthCを、
AuthC = H2(X,A(Q(i)),Y,KC)
のように生成する端末第１認証子生成部、
前記受信されたAuthSと、前記生成されたAuthCと、が、一致する場合、端末側セッション鍵skCを、
skC = H1(X,A(Q(i)),Y,KC)
のように生成する端末鍵生成部
をさらに備える
ことを特徴とするセッション鍵システム。
【請求項３】
請求項１に記載のセッション鍵システムであって、前記端末装置と、前記サーバ装置と、は、ハッシュ関数H3をさらに共有し、
（ｄ） 前記端末装置は、
前記端末受信部により受信されたA(Q(i))と、前記端末第２計算部により計算されたY，KCと、から、端末側第２認証子AuthC'を、
AuthC' = H3(X,A(Q(i)),Y,KC)
のように生成する端末第２認証子生成部、
前記生成されたAuthC'を、前記サーバ装置に送信する端末第２送信部
をさらに備え、
（ｅ） 前記サーバ装置は、
前記端末装置から送信されたAuthC'を受信するサーバ第２受信部、
前記サーバ第１計算部により計算されたA(Q(i))，Y，KSから、サーバ側第２認証子AuthS'を、
AuthS' = H3(X,A(Q(i)),Y,KS)
のように生成するサーバ第２認証子生成部
をさらに備え、
前記サーバ装置が備えるサーバ鍵生成部が、サーバ側セッション鍵skSを生成するのは、前記受信されたAuthC'と、前記生成されたAuthS'と、が、一致する場合である
ことを特徴とするセッション鍵システム。
【請求項４】
素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数F，G，H0，H1，H2と、を、端末装置とサーバ装置とで共有し、サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、前記端末装置には、当該n個のパスワードのうち、pw[1]，…，pw[k]が保有されるセッション鍵システムであって、
（ａ）前記端末装置は、
体Zpの元からx，γ[1]，…，γ[k]，a[1]，…，a[k]，w[k+1]，…，w[n]を一様にランダムに選択する端末選択部、
前記選択されたx，γ[1]，…，γ[k]，a[1]，…，a[k]，w[k+1]，…，w[n]から、
X = gx
と、i = 1，…，kについて
w[i] = hγ[i]G(i,pw[i])；
と、i = 1，…，nについて
A[i] = w[i]ga[i]
とを計算する端末第１計算部、
前記計算されたX，A[1]，…，A[k]，w[1]，…，w[n]を、前記サーバ装置に送信する端末第１送信部
を備え、
（ｂ） 前記サーバ装置は、
前記端末装置から送信されたX，A[1]，…，A[k]，w[1]，…，w[n]を受信するサーバ第１受信部、
体Zpの元からy，z，b[1]，…，b[k]を一様にランダムに選択するサーバ選択部、
f(x) = y + b[1]x + … b[k]xkとしたときに、
Y[1] = gf(1)，…，Y[n] = gf(n)；
Z = gz；
D[1] = A[1]z，…，D[k] = A[k]z；
を計算し、j = 1，…，nに対して、
α[j] = Y[j]gF(pw[j]) xor H0(w[i]z)；
KS = Xyを
を計算するサーバ第１計算部、
サーバ側認証子AuthSを、
AuthS = H2(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KS)
のように生成するサーバ第１認証子生成部、
前記計算されたZ，D[1]，…，D[k]，α[1]，…，α[n]と、前記生成されたAuthSと、を、前記端末装置に送信するサーバ送信部、
サーバ側セッション鍵skSを、
skS = H1(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，Ks)
のように生成するサーバ鍵生成部、
を備え、
（ｃ） 前記端末装置は、
前記サーバ装置から送信されたZ，D[1]，…，D[k]，α[1]，…，α[n]，AuthSを受信する端末受信部、
i = 1，…，kについて、
λ[i] = Π1≦j≦k，j≠i j/(j-i)
としたときに、
Y[i] = (α[i] xor H0(D[i]/Za[i]))/gF(pw[i])
を計算し、
Y = Y[1]λ[1]…Y[k]λ[k]；
KC = Yx
を計算する端末第２計算部、
前記計算されたX，Y，KCと、前記受信されたZ，D[1]，…，D[k]，α[1]，…，α[n]と、から、端末側認証子AuthCを、
AuthC = H2(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KC)
のように生成する端末第１認証子生成部、
前記受信されたAuthSと、前記生成されたAuthCと、が、一致する場合、端末側セッション鍵skCを、
skC = H1(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KC)
のように生成する端末鍵生成部
をさらに備える
ことを特徴とするセッション鍵システム。
【請求項５】
素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数Fと、を、端末装置とサーバ装置とで共有し、前記サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、前記端末装置には、当該n個のパスワードのうち、i番目のパスワードpw[i]が保有されるセッション鍵提供方法であって、
（ａ） 前記端末装置が、当該i番目のパスワードpw[i]に対して、
体Zpの元からxを一様にランダムに選択する端末選択工程、
前記選択されたxからgxを計算する端末第１計算工程
を備え、
（ｂ） 前記サーバ装置が、
体Zpの元からyを一様にランダムに選択するサーバ選択工程
前記選択されたyから、j = 1，…，nについて、
α[j] = gygF(pw[j])
を計算するサーバ第１計算工程
を備え、
（ｃ） 前記端末装置が、
前記計算されたgxを指定する1-out-of-n紛失通信問い合わせを前記サーバ装置に送信する端末第１送信工程
をさらに備え、
（ｄ） 前記サーバ装置が、
前記端末装置から送信された1-out-of-n紛失通信問い合わせを受信するサーバ第１受信工程、
前記受信された1-out-of-n紛失通信問い合わせに指定されるgxと、前記選択されたyと、から、
gxy = (gx)y
をサーバ側セッション鍵として生成するサーバ鍵生成工程、
前記計算されたα[j] (j = 1，…，n)から、i番目のパスワードpw[i]を持つユーザがgygF(pw[i])の情報のみを得られるような1-out-of-n紛失通信応答を生成して前記端末装置に送信するサーバ送信工程
をさらに備え、
（ｄ）前記端末装置が、
前記サーバ装置から送信された1-out-of-n紛失通信応答を受信する端末受信工程
前記受信された1-out-of-n紛失通信応答から、gygF(pw[i])の情報を得て、
gxy = (gygF(pw[i])/gF(pw[i]))x
を端末側セッション鍵として生成する端末鍵生成工程
をさらに備える
ことを特徴とするセッション鍵提供方法。
【請求項６】
素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数F，G，H0，H1，H2と、を、端末装置とサーバ装置とで共有し、前記サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、前記端末装置には、当該n個のパスワードのうち、i番目のパスワードpw[i]が保有されるセッション鍵提供方法であって、
（ａ） 前記端末装置が、当該i番目のパスワードpw[i]に対して、
体Zpの元からx，rを一様にランダムに選択する端末選択工程、
前記選択されたx，rから、
X = gx；
Q(i) = grhG(i,pw[i])
を計算する端末第１計算工程、
前記計算されたXと、前記計算されたQ(i)と、を、組
(X,Q(i))
としてサーバ装置に送信する端末第１送信工程
を備え、
（ｂ） 前記サーバ装置が、
前記端末装置から送信された組
(X,Q(i))
を受信するサーバ第１受信工程、
体Zpの元からy，k[1]，…，k[n]を一様にランダムに選択するサーバ選択工程、
前記受信された(X,Q(i))と、前記選択されたy，k[1]，…，k[n]と、から、
Y = gy
と、j = 1，…，nについて、
α[j] = YgF(pw[j])；
β[j] = H0((Q(i)/hG(j,pw[j]))k[j],j) xor α[j]
と、
A(Q(i)) = (β[1]，…，β[n]，gk[1]，…，gk[n])；
KS = Xy
と、を計算するサーバ第１計算工程、
サーバ側認証子AuthSを、
AuthS = H2(X,A(Q(i)),Y,KS)
のように生成するサーバ第１認証子生成工程、
サーバ側セッション鍵skSを、
skS = H1(X,A(Q(i)),Y,KS)
のように生成するサーバ鍵生成工程、
前記計算されたA(Q(i))と、前記生成されたサーバ側認証子AuthSと、を組
(A(Q(i)),AuthS)
として、前記端末装置に送信するサーバ送信工程
を備え、
（ｃ） 前記端末装置が、i番目のパスワードpw[i]に対して、
前記サーバ装置から送信された組
(A(Q(i)),AuthS)
を受信する端末受信工程、
前記受信されたA(Q(i)) = (β[1]，…，β[n]，gk[1]，…，gk[n])から、
α[i] = β[i] xor H0((gk[i])r,i)；
Y = α[i]/gF(pw[i])；
KC = Yx；
を計算する端末第２計算工程、
前記受信されたA(Q(i))と、前記計算されたY，KCと、から、端末側認証子AuthCを、
AuthC = H2(X,A(Q(i)),Y,KC)
のように生成する端末第１認証子生成工程、
前記受信されたAuthSと、前記生成されたAuthCと、が、一致する場合、端末側セッション鍵skCを、
skC = H1(X,A(Q(i)),Y,KC)
のように生成する端末鍵生成工程
をさらに備える
ことを特徴とするセッション鍵地峡方法。
【請求項７】
請求項６に記載のセッション鍵提供方法であって、前記端末装置と、前記サーバ装置と、は、ハッシュ関数H3をさらに共有し、
（ｄ） 前記端末装置が、
前記端末受信工程にて受信されたA(Q(i))と、前記端末第２計算工程にて計算されたY，KCと、から、端末側第２認証子AuthC'を、
AuthC' = H3(X,A(Q(i)),Y,KC)
のように生成する端末第２認証子生成工程、
前記生成されたAuthC'を、前記サーバ装置に送信する端末第２送信工程
をさらに備え、
（ｅ） 前記サーバ装置が、
前記端末装置から送信されたAuthC'を受信するサーバ第２受信工程、
前記サーバ第１計算工程にて計算されたA(Q(i))，Y，KSから、サーバ側第２認証子AuthS'を、
AuthS' = H3(X,A(Q(i)),Y,KS)
のように生成するサーバ第２認証子生成工程
をさらに備え、
前記サーバ鍵生成工程にて、サーバ側セッション鍵skSを生成するのは、前記受信されたAuthC'と、前記生成されたAuthS'と、が、一致する場合である
ことを特徴とするセッション鍵提供方法。
【請求項８】
素数pを法とする整数からなる体Zpと、当該素数pを位数とする有限巡回群（finite cyclic group）GGの生成元（generator）g，hと、ハッシュ関数F，G，H0，H1，H2と、を、端末装置とサーバ装置とで共有し、サーバ装置には、n個のパスワードpw[1]，…，pw[n]が保有され、前記端末装置には、当該n個のパスワードのうち、pw[1]，…，pw[k]が保有されるセッション鍵提供方法であって、
（ａ）前記端末装置が、
体Zpの元からx，γ[1]，…，γ[k]，a[1]，…，a[k]，w[k+1]，…，w[n]を一様にランダムに選択する端末選択工程、
前記選択されたx，γ[1]，…，γ[k]，a[1]，…，a[k]，w[k+1]，…，w[n]から、
X = gx
と、i = 1，…，kについて
w[i] = hγ[i]G(i,pw[i])；
A[i] = w[i]ga[i]
とを計算する端末第１計算工程、
前記計算されたX，A[1]，…，A[k]，w[1]，…，w[n]を、前記サーバ装置に送信する端末第１送信工程
を備え、
（ｂ） 前記サーバ装置が、
前記端末装置から送信されたX，A[1]，…，A[k]，w[1]，…，w[n]を受信するサーバ第１受信工程、
体Zpの元からy，z，b[1]，…，b[k]を一様にランダムに選択するサーバ選択工程、
f(x) = y + b[1]x + … b[k]xkとしたときに、
Y[1] = gf(1)，…，Y[n] = gf(n)；
Z = gz；
D[1] = A[1]z，…，D[k] = A[k]z；
を計算し、j = 1，…，nに対して、
α[j] = Y[j]gF(pw[j]) xor H0(w[i]z)；
KS = Xyを
を計算するサーバ第１計算工程、
サーバ側認証子AuthSを、
AuthS = H2(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KS)
のように生成するサーバ第１認証子生成工程、
前記計算されたZ，D[1]，…，D[k]，α[1]，…，α[n]と、前記生成されたAuthSと、を、前記端末装置に送信するサーバ送信工程、
サーバ側セッション鍵skSを、
skS = H1(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，Ks)
のように生成するサーバ鍵生成工程、
を備え、
（ｃ） 前記端末装置が、
前記サーバ装置から送信されたZ，D[1]，…，D[k]，α[1]，…，α[n]，AuthSを受信する端末受信工程、
i = 1，…，kについて、
λ[i] = Π1≦j≦k，j≠i j/(j-i)
としたときに、
Y[i] = (α[i] xor H0(D[i]/Za[i]))/gF(pw[i])
を計算し、
Y = Y[1]λ[1]…Y[k]λ[k]；
KC = Yx
を計算する端末第２計算工程、
前記計算されたX，Y，KCと、前記受信されたZ，D[1]，…，D[k]，α[1]，…，α[n]と、から、端末側認証子AuthCを、
AuthC = H2(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KC)
のように生成する端末第１認証子生成工程、
前記受信されたAuthSと、前記生成されたAuthCと、が、一致する場合、端末側セッション鍵skCを、
skC = H1(X，Z，D[1]，…，D[k]，α[1]，…，α[n]，Y，KC)
のように生成する端末鍵生成工程
をさらに備える
ことを特徴とするセッション鍵提供方法。
【請求項９】
コンピュータを、請求項１から４のいずれか１項に記載のセッション鍵システムの端末装置が備える各部として機能させることを特徴とするプログラム。
【請求項１０】
コンピュータを、請求項１から４のいずれか１項に記載のセッション鍵システムのサーバ装置が備える各部として機能させることを特徴とするプログラム。
【請求項１１】
請求項４に記載のセッション鍵システムであって、
前記端末装置は、k台の機器を備え、
i = 1，…，kについて、パスワードpw[i]はi番目の機器に保有され、γ[i]，a[i]の取得およびw[i]，A[i]，w[i]の計算は、i番目の機器が、j (j≠i)番目の機器とは独立に行う
ことを特徴とするセッション鍵システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２００７−１３４９９０（Ｐ２００７−１３４９９０Ａ）
【公開日】平成１９年５月３１日（２００７．５．３１）
【国際特許分類】
【出願番号】特願２００５−３２６３８５（Ｐ２００５−３２６３８５）
【出願日】平成１７年１１月１０日（２００５．１１．１０）
【出願人】（３０１０２２４７１）独立行政法人情報通信研究機構 (1,071)
【Ｆターム（参考）】
【公開日】平成１９年５月３１日（２００７．５．３１）
【国際特許分類】
【出願日】平成１７年１１月１０日（２００５．１１．１０）
【出願人】（３０１０２２４７１）独立行政法人情報通信研究機構 (1,071)
【Ｆターム（参考）】
[ Back to top ]