(57)【特許請求の範囲】
【請求項１】
n≧3であり、2k-1≦nであり、k≦mであり、m≦nであり、a1,…,amは1以上n以下の相異なるm個の整数であり、(k,n)秘密分散はn個の分散値のうちk個以上あれば復元することができる秘密分散であり、[r(W)]1,…,[r(W)]nは復元すると乱数r(W)となる(k,n)秘密分散による分散値であり、[r(i)]1,…,[r(i)]n（i=1,…,n）は復元すると乱数r(i)となる(k,n)秘密分散による分散値であり、[0(W)]1,…,[0(W)]nは復元すると0となる(k,n)秘密分散による分散値であり、[0(a_i)]1,…,[0(a_i)]n（i=1,…,m）は復元すると0となる(k,n)秘密分散による分散値であり、
利用者装置、中間サーバ及びn台の認証サーバを含むマルチパーティセキュア認証システムであって、
上記利用者装置は、
入力されたパスワードw'をn個の分散値[w']1,…,[w']nに分散するパスワード分散部と、
i=1,…,nについて、上記利用者装置とi番目の上記認証サーバとの共通鍵を用いて、分散値[w']iを暗号化した暗号文EncUS_i([w']i)を得るパスワード分散値暗号化部と、
を含み、
上記中間サーバは、
i=1,…,nについて、上記利用者装置から受信した上記暗号文EncUS_i([w']i)をi番目の上記認証サーバへ送信するパスワード分散値転送部と、
i=1,…,mについて、上記中間サーバとai番目の上記認証サーバとの共通鍵を用いて、ai番目の上記認証サーバから受信した暗号文EncWS_a_i(qa_i(W))を復号して検証値qa_i(W)を得る中間サーバ検証値復号部と、
上記検証値qa_1(W),…,qa_m(W)の総和が0と等しいか否かを検証する中間サーバ検証部と、
を含み、
上記認証サーバは、
パスワードwをn個に分散した分散値[w]1,…,[w]nのうちi番目の分散値[w]i、i番目の上記分散値[r(W)]i、それぞれi番目の上記分散値[r(1)]i,…,[r(n)]iを記憶する分散値記憶部と、
上記利用者装置と当該認証サーバとの共通鍵を用いて、上記中間サーバから受信した上記暗号文EncUS_i([w']i)を復号して上記分散値[w']iを得るパスワード分散値復号部と、
λa_i(W)（i∈1,…,m）は次式を満たす定数であり、
【数３２】
0006040313.tif 000033
^λa_i(W)（i∈1,…,m）は次式を満たす定数であり、
【数３３】
0006040313.tif 000034
λa_i(j)（i∈1,…,m）は次式を満たす定数であり、
【数３４】
0006040313.tif 000035
^λa_i(j)（i∈1,…,m）は次式を満たす定数であり、
【数３５】
0006040313.tif 000036
次式により検証値qa_i(W)を求める中間サーバ検証値生成部と、
【数３６】
0006040313.tif 000037
上記中間サーバと当該認証サーバとの共通鍵を用いて、上記検証値qa_i(W)を暗号化した上記暗号文EncWS_a_i(qa_i(W))を得る中間サーバ検証値暗号化部と、
j=1,…,mについて、次式により検証値qa_i(a_j)を求める認証サーバ検証値生成部と、
【数３７】
0006040313.tif 000038
j=1,…,mについて、aj番目の上記認証サーバと当該認証サーバとの共通鍵を用いて、上記検証値qa_i(a_j)を暗号化した暗号文EncS_a_iS_a_j(qa_i(a_j))を得る認証サーバ検証値暗号化部と、
j=1,…,mについて、aj番目の上記認証サーバと当該認証サーバとの共通鍵を用いて、aj番目の上記認証サーバから受信した暗号文EncS_a_iS_a_j(qa_j(a_i))を復号して上記検証値qa_j(a_i)を得る認証サーバ検証値復号部と、
上記検証値qa_1(a_i),…,qa_m(a_i)の総和が0と等しいか否かを検証する認証サーバ検証部と、
を含むマルチパーティセキュア認証システム。
【請求項２】
請求項１に記載のマルチパーティセキュア認証システムであって、
上記認証サーバは、
乱数ta_iを生成する乱数生成部と、
上記利用者装置と当該認証サーバとの共通鍵を用いて、上記乱数ta_iを暗号化した暗号文EncUS_a_i(ta_i)を得る乱数暗号化部と、
上記中間サーバから受信した暗号文EncUS_a_i(ta_i,[w']a_i)を復号して得た乱数ta_iが、上記乱数生成部により生成された上記乱数ta_iと等しいか否かを検証する乱数検証部と、
をさらに含み、
上記中間サーバは、
j=1,…,mについて、aj番目の認証サーバから受信した上記暗号文EncUS_a_j(ta_j)を上記利用者装置へ送信する乱数転送部
をさらに含み、
上記利用者装置は、
i=1,…,mについて、当該利用者装置とai番目の認証サーバとの共通鍵を用いて、上記中間サーバから受信した上記暗号文EncUS_a_i(ta_i)を復号し上記乱数ta_iを得る乱数復号部
をさらに含み、
上記パスワード分散値暗号化部は、
i=1,…,nについて、上記利用者装置とi番目の上記認証サーバとの共通鍵を用いて、分散値[w']iを上記乱数ta_iと共に暗号化した暗号文EncUS_a_i(ta_i,[w']a_i)を得る
マルチパーティセキュア認証システム。
【請求項３】
請求項１または２に記載のマルチパーティセキュア認証システムであって、
上記認証サーバは、
上記分散値[r(W)]i,[r(1)]i,…,[r(n)]iを生成する乱数分散値生成部と、
上記分散値[0(W)]i,[0(a_1)]i,…,[r(a_m)]iを生成するゼロ分散値生成部と、
をさらに含むマルチパーティセキュア認証システム。
【請求項４】
請求項１または２に記載のマルチパーティセキュア認証システムであって、
上記利用者装置は、
上記乱数r(W),r(1),…,r(n)を生成し、上記乱数r(W),r(1),…,r(n)それぞれをn個に分散して上記分散値[r(W)]1,…,[r(W)]n及び上記分散値[r(i)]1,…,[r(i)]n（i=1,…,n）を生成する乱数分散値生成部と、
i=1,…,nについて、上記利用者装置とi番目の上記認証サーバとの共通鍵を用いて、分散値[r(W)]i,[r(i)]i,…,[r(n)]iを暗号化した暗号文EncUS_i([r(W)]i,[r(i)]i,…,[r(n)]i)を得る乱数分散値暗号化部と、
上記分散値[0(W)]1,…,[0(W)]n及び上記分散値[0(a_i)]1,…,[0(a_i)]n（i=1,…,m）を生成するゼロ分散値生成部と、
i=1,…,mについて、上記利用者装置とai番目の上記認証サーバとの共通鍵を用いて、分散値[0(W)]i,[0(1)]i,…,[0(m)]iを暗号化した暗号文EncUS_i([0(W)]i,[0(a_1)]i,…,[0(a_m)]i)を得る乱数分散値暗号化部と、
をさらに含み、
上記中間サーバは、
i=1,…,nについて、上記利用者装置から受信した上記暗号文EncUS_i([r(W)]i,[r(i)]i,…,[r(n)]i)をi番目の上記認証サーバへ送信する乱数分散値転送部と、
i=1,…,nについて、上記利用者装置から受信した上記暗号文EncUS_i([0(W)]i,[0(a_1)]i,…,[0(a_m)]i)をi番目の上記認証サーバへ送信するゼロ分散値転送部と、
を含むマルチパーティセキュア認証システム。
【請求項５】
n≧3であり、2k-1≦nであり、k≦mであり、m≦nであり、a1,…,amはam=nかつそれぞれ1以上n以下の相異なるm個の整数であり、(k,n)秘密分散はn個の分散値のうちk個以上あれば復元することができる秘密分散であり、[r(i)]1,…,[r(i)]n（i=1,…,n）は復元すると乱数r(i)となる(k,n)秘密分散による分散値であり、[0(a_i)]1,…,[0(a_i)]n（i=1,…,m）は復元すると0となる(k,n)秘密分散による分散値であり、
λa_i(j)（i∈1,…,m）は次式を満たす定数であり、
【数３８】
0006040313.tif 000039
^λa_i(j)（i∈1,…,m）は次式を満たす定数であり、
【数３９】
0006040313.tif 000040
利用者装置、中間認証サーバ及びn-1台の認証サーバを含むマルチパーティセキュア認証システムであって、
上記利用者装置は、
入力されたパスワードw'をn個の分散値[w']1,…,[w']nに分散するパスワード分散部と、
i=1,…,n-1について、上記利用者装置とi番目の上記認証サーバとの共通鍵を用いて、分散値[w']iを暗号化した暗号文EncUS_i([w']i)を得、上記利用者装置と上記中間認証サーバとの共通鍵を用いて、分散値[w']nを暗号化した暗号文EncUS_n([w']n)を得るパスワード分散値暗号化部と、
を含み、
上記中間認証サーバは、
パスワードwをn個に分散した分散値[w]1,…,[w]nのうちn番目の分散値[w]n、それぞれn番目の上記分散値[r(1)]n,…,[r(n)]nを記憶する分散値記憶部と、
i=1,…,n-1について、上記利用者装置から受信した上記暗号文EncUS_i([w']i)をi番目の上記認証サーバへ送信するパスワード分散値転送部と、
上記利用者装置と当該中間認証サーバとの共通鍵を用いて、上記暗号文EncUS_n([w']n)を復号して上記分散値[w']nを得るパスワード分散値復号部と、
j=1,…,mについて、次式により検証値qa_m(a_j)を求める認証サーバ検証値生成部と、
【数４０】
0006040313.tif 000041
j=1,…,m-1について、aj番目の上記認証サーバと当該中間認証サーバとの共通鍵を用いて、上記検証値qa_m(a_j)を暗号化した暗号文EncS_a_mS_a_j(qa_m(a_j))を得る認証サーバ検証値暗号化部と、
j=1,…,m-1について、aj番目の上記認証サーバと当該中間認証サーバとの共通鍵を用いて、aj番目の上記認証サーバから受信した暗号文EncS_a_mS_a_j(qa_j(a_m))を復号して上記検証値qa_j(a_m)を得る認証サーバ検証値復号部と、
上記検証値qa_1(a_m),…,qa_m(a_m)の総和が0と等しいか否かを検証する認証サーバ検証部と、
を含み、
上記認証サーバは、
i番目の上記分散値[w]i、それぞれi番目の上記分散値[r(1)]i,…,[r(n)]iを記憶する分散値記憶部と、
上記利用者装置と当該認証サーバとの共通鍵を用いて、上記中間認証サーバから受信した上記暗号文EncUS_i([w']i)を復号して上記分散値[w']iを得るパスワード分散値復号部と、
j=1,…,mについて、次式により検証値qa_i(a_j)を求める認証サーバ検証値生成部と、
【数４１】
0006040313.tif 000042
j=1,…,mについて、aj番目の上記認証サーバもしくは上記中間認証サーバと当該認証サーバとの共通鍵を用いて、上記検証値qa_i(a_j)を暗号化した暗号文EncS_a_iS_a_j(qa_i(a_j))を得る認証サーバ検証値暗号化部と、
j=1,…,mについて、aj番目の上記認証サーバもしくは上記中間認証サーバと当該認証サーバとの共通鍵を用いて、aj番目の上記認証サーバから受信した暗号文EncS_a_iS_a_j(qa_j(a_i))を復号して上記検証値qa_j(a_i)を得る認証サーバ検証値復号部と、
上記検証値qa_1(a_i),…,qa_m(a_i)の総和が0と等しいか否かを検証する認証サーバ検証部と、
を含むマルチパーティセキュア認証システム。
【請求項６】
請求項１から５のいずれかに記載のマルチパーティセキュア認証システムにおいて用いられる上記認証サーバ。
【請求項７】
n≧3であり、2k-1≦nであり、k≦mであり、m≦nであり、a1,…,amは1以上n以下の相異なるm個の整数であり、(k,n)秘密分散はn個の分散値のうちk個以上あれば復元することができる秘密分散であり、[r(W)]1,…,[r(W)]nは復元すると乱数r(W)となる(k,n)秘密分散による分散値であり、[r(i)]1,…,[r(i)]n（i=1,…,n）は復元すると乱数r(i)となる(k,n)秘密分散による分散値であり、[0(W)]1,…,[0(W)]nは復元すると0となる(k,n)秘密分散による分散値であり、[0(a_i)]1,…,[0(a_i)]n（i=1,…,m）は復元すると0となる(k,n)秘密分散による分散値であり、
利用者装置が、入力されたパスワードw'をn個の分散値[w']1,…,[w']nに分散するパスワード分散ステップと、
上記利用者装置が、i=1,…,nについて、上記利用者装置とi番目の認証サーバとの共通鍵を用いて、分散値[w']iを暗号化した暗号文EncUS_i([w']i)を得るパスワード分散値暗号化ステップと、
中間サーバが、i=1,…,nについて、上記利用者装置から受信した上記暗号文EncUS_i([w']i)をi番目の上記認証サーバへ送信するパスワード分散値転送ステップと、
上記認証サーバが、上記利用者装置と当該認証サーバとの共通鍵を用いて、上記中間サーバから受信した上記暗号文EncUS_i([w']i)を復号して上記分散値[w']iを得るパスワード分散値復号ステップと、
λa_i(W)（i∈1,…,m）は次式を満たす定数であり、
【数４８】
0006040313.tif 000043
^λa_i(W)（i∈1,…,m）は次式を満たす定数であり、
【数４９】
0006040313.tif 000044
λa_i(j)（i∈1,…,m）は次式を満たす定数であり、
【数５０】
0006040313.tif 000045
^λa_i(j)（i∈1,…,m）は次式を満たす定数であり、
【数５１】
0006040313.tif 000046
上記認証サーバが、次式により検証値qa_i(W)を求める中間サーバ検証値生成ステップと、
【数５２】
0006040313.tif 000047
上記認証サーバが、上記中間サーバと当該認証サーバとの共通鍵を用いて、上記検証値qa_i(W)を暗号化した暗号文EncWS_a_i(qa_i(W))を得る中間サーバ検証値暗号化ステップと、
上記中間サーバが、i=1,…,mについて、上記中間サーバとai番目の上記認証サーバとの共通鍵を用いて、ai番目の上記認証サーバから受信した暗号文EncWS_a_i(qa_i(W))を復号して検証値qa_i(W)を得る中間サーバ検証値復号ステップと、
上記中間サーバが、上記検証値qa_1(W),…,qa_m(W)の総和が0と等しいか否かを検証する中間サーバ検証ステップと、
上記認証サーバが、j=1,…,mについて、次式により検証値qa_i(a_j)を求める認証サーバ検証値生成ステップと、
【数５３】
0006040313.tif 000048
上記認証サーバが、j=1,…,mについて、aj番目の上記認証サーバと当該認証サーバとの共通鍵を用いて、上記検証値qa_i(a_j)を暗号化した暗号文EncS_a_iS_a_j(qa_i(a_j))を得る認証サーバ検証値暗号化ステップと、
上記認証サーバが、j=1,…,mについて、aj番目の上記認証サーバと当該認証サーバとの共通鍵を用いて、aj番目の上記認証サーバから受信した暗号文EncS_a_iS_a_j(qa_j(a_i))を復号して上記検証値qa_j(a_i)を得る認証サーバ検証値復号ステップと、
上記認証サーバが、上記検証値qa_1(a_i),…,qa_m(a_i)の総和が0と等しいか否かを検証する認証サーバ検証ステップと、
を含むマルチパーティセキュア認証方法。
【請求項８】
n≧3であり、2k-1≦nであり、k≦mであり、m≦nであり、a1,…,amはam=nかつそれぞれ1以上n以下の相異なるm個の整数であり、(k,n)秘密分散はn個の分散値のうちk個以上あれば復元することができる秘密分散であり、[r(i)]1,…,[r(i)]n（i=1,…,n）は復元すると乱数r(i)となる(k,n)秘密分散による分散値であり、[0(a_i)]1,…,[0(a_i)]n（i=1,…,m）は復元すると0となる(k,n)秘密分散による分散値であり、
λa_i(j)（i∈1,…,m）は次式を満たす定数であり、
【数５４】
0006040313.tif 000049
^λa_i(j)（i∈1,…,m）は次式を満たす定数であり、
【数５５】
0006040313.tif 000050
利用者装置が、入力されたパスワードw'をn個の分散値[w']1,…,[w']nに分散するパスワード分散ステップと、
上記利用者装置が、i=1,…,n-1について、上記利用者装置とi番目の認証サーバとの共通鍵を用いて、分散値[w']iを暗号化した暗号文EncUS_i([w']i)を得、上記利用者装置と中間認証サーバとの共通鍵を用いて、分散値[w']nを暗号化した暗号文EncUS_n([w']n)を得るパスワード分散値暗号化ステップと、
上記中間認証サーバが、i=1,…,n-1について、上記利用者装置から受信した上記暗号文EncUS_i([w']i)をi番目の上記認証サーバへ送信するパスワード分散値転送ステップと、
上記認証サーバが、上記利用者装置と当該認証サーバとの共通鍵を用いて、上記中間認証サーバから受信した上記暗号文EncUS_i([w']i)を復号して上記分散値[w']iを得る第一パスワード分散値復号ステップと、
上記中間認証サーバが、上記利用者装置と当該中間認証サーバとの共通鍵を用いて、上記暗号文EncUS_n([w']n)を復号して上記分散値[w']nを得る第二パスワード分散値復号ステップと、
上記認証サーバが、j=1,…,mについて、次式により検証値qa_i(a_j)を求める第一認証サーバ検証値生成ステップと、
【数５６】
0006040313.tif 000051
上記中間認証サーバが、j=1,…,mについて、次式により検証値qa_m(a_j)を求める第二認証サーバ検証値生成ステップと、
【数５７】
0006040313.tif 000052
上記認証サーバが、j=1,…,mについて、aj番目の上記認証サーバもしくは上記中間認証サーバと当該認証サーバとの共通鍵を用いて、上記検証値qa_i(a_j)を暗号化した暗号文EncS_a_iS_a_j(qa_i(a_j))を得る第一認証サーバ検証値暗号化ステップと、
上記中間認証サーバが、j=1,…,m-1について、aj番目の上記認証サーバと当該中間認証サーバとの共通鍵を用いて、上記検証値qa_m(a_j)を暗号化した暗号文EncS_a_mS_a_j(qa_m(a_j))を得る第二認証サーバ検証値暗号化ステップと、
上記認証サーバが、j=1,…,mについて、aj番目の上記認証サーバもしくは上記中間認証サーバと当該認証サーバとの共通鍵を用いて、aj番目の上記認証サーバから受信した暗号文EncS_a_iS_a_j(qa_j(a_i))を復号して上記検証値qa_j(a_i)を得る第一認証サーバ検証値復号ステップと、
上記中間認証サーバが、j=1,…,m-1について、aj番目の上記認証サーバと当該中間認証サーバとの共通鍵を用いて、aj番目の上記認証サーバから受信した暗号文EncS_a_mS_a_j(qa_j(a_m))を復号して上記検証値qa_j(a_m)を得る第二認証サーバ検証値復号ステップと、
上記認証サーバが、上記検証値qa_1(a_i),…,qa_m(a_i)の総和が0と等しいか否かを検証する第一認証サーバ検証ステップと、
上記中間認証サーバが、上記検証値qa_1(a_m),…,qa_m(a_m)の総和が0と等しいか否かを検証する第二認証サーバ検証ステップと、
を含むマルチパーティセキュア認証方法。
【請求項９】
請求項６に記載の認証サーバとしてコンピュータを機能させるためのプログラム。
【請求項１０】
請求項７または８に記載のマルチパーティセキュア認証方法の各ステップをコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ネットワーク上の認証において、複数のサーバが同時にユーザを安全に認証する技術に関する。
【背景技術】
【０００２】
ユーザが複数のサーバにまたがるサービスを受ける際に、各サーバに同時に安全に認証を受ける技術として、非特許文献１〜３に記載された技術が知られている（例えば、非特許文献１〜３参照。）。非特許文献１〜３に記載された技術は、安全なストレージサービスにおける認証技術であり、ユーザがパスワードを設定し、データを秘密分散と呼ばれる安全な方法で複数のサーバに分散して保管する。認証時に入力されたパスワードが正しければユーザは正しいデータを復元でき、パスワードが誤りであれば復元に失敗する。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ali Bagherzandi, Stanislaw Jarecki, Nitesh Saxena, and Yanbin Lu, “Password-protected secret sharing”, ACM Conference on Computer and Communications Security, pp. 433-444, 2011.
【非特許文献２】Jan Camenisch, Anna Lysyanskaya, and Gregory Neven, “Practical yet universally composable two-server password-authenticated secret sharing”, ACM Conference on Computer and Communications Security, pp. 525-536, 2012.
【非特許文献３】尾形わかは、「情報理論的に安全なパスワード付秘密分散法の安全性と効率化」、SCIS 2013
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来技術では、ユーザとストレージサーバが直結しているということを前提としており、Webサービス等におけるWebサーバのようにゲートウェイとしての中間サーバが存在する場合の安全性は保証できない。また、ストレージサービス以外に応用できないという課題もある。【０００５】
この発明の目的は、中間サーバが存在する場合であっても安全性を保証することができるマルチパーティセキュア認証技術を提供することである。
【課題を解決するための手段】
【０００６】
上記の課題を解決するために、この発明の第一の態様のマルチパーティセキュア認証方法は、パスワード分散ステップ、パスワード分散値暗号化ステップ、パスワード分散値転送ステップ、パスワード分散値復号ステップ、中間サーバ検証値生成ステップ、中間サーバ検証値暗号化ステップ、中間サーバ検証値復号ステップ、中間サーバ検証ステップ、認証サーバ検証値生成ステップ、認証サーバ検証値暗号化ステップ、認証サーバ検証値復号ステップ及び認証サーバ検証ステップを含む。【０００７】
以下では、n≧3であり、2k-1≦nであり、k≦mであり、m≦nであり、a1,…,amは1以上n以下の相異なるm個の整数であり、(k,n)秘密分散はn個の分散値のうちk個以上あれば復元することができる秘密分散であり、[r(W)]1,…,[r(W)]nは復元すると乱数r(W)となる(k,n)秘密分散による分散値であり、[r(i)]1,…,[r(i)]n（i=1,…,n）は復元すると乱数r(i)となる(k,n)秘密分散による分散値であり、[0(W)]1,…,[0(W)]nは復元すると0となる(k,n)秘密分散による分散値であり、[0(a_i)]1,…,[0(a_i)]n（i=1,…,m）は復元すると0となる(k,n)秘密分散による分散値であるとする。【０００８】
パスワード分散ステップにおいて、利用者装置が、入力されたパスワードw'をn個の分散値[w']1,…,[w']nに分散する。パスワード分散値暗号化ステップにおいて、利用者装置が、i=1,…,nについて、利用者装置とi番目の認証サーバとの共通鍵を用いて、分散値[w']iを暗号化した暗号文EncUS_i([w']i)を得る。パスワード分散値転送ステップにおいて、中間サーバが、i=1,…,nについて、利用者装置から受信した暗号文EncUS_i([w']i)をi番目の認証サーバへ送信する。パスワード分散値復号ステップにおいて、認証サーバが、利用者装置と当該認証サーバとの共通鍵を用いて、中間サーバから受信した暗号文EncUS_i([w']i)を復号して分散値[w']iを得る。中間サーバ検証値生成ステップにおいて、λa_i(W)（i∈1,…,m）は次式を満たす定数であり、
【０００９】
【数１】
0006040313.tif 000002
【００１０】
^λa_i(W)（i∈1,…,m）は次式を満たす定数であり、【００１１】
【数２】
0006040313.tif 000003
【００１２】
λa_i(j)（i∈1,…,m）は次式を満たす定数であり、【００１３】
【数３】
0006040313.tif 000004
【００１４】
^λa_i(j)（i∈1,…,m）は次式を満たす定数であるとして、【００１５】
【数４】
0006040313.tif 000005
【００１６】
認証サーバが、次式により検証値qa_i(W)を求める。【００１７】
【数５】
0006040313.tif 000006
【００１８】
中間サーバ検証値暗号化ステップにおいて、認証サーバが、中間サーバと当該認証サーバとの共通鍵を用いて、検証値qa_i(W)を暗号化した暗号文EncWS_a_i(qa_i(W))を得る。中間サーバ検証値復号ステップにおいて、中間サーバが、i=1,…,mについて、中間サーバとai番目の認証サーバとの共通鍵を用いて、ai番目の認証サーバから受信した暗号文EncWS_a_i(qa_i(W))を復号して検証値qa_i(W)を得る。中間サーバ検証ステップにおいて、中間サーバが、検証値qa_1(W),…,qa_m(W)の総和が0と等しいか否かを検証する。認証サーバ検証値生成ステップにおいて、認証サーバが、j=1,…,mについて、次式により検証値qa_i(a_j)を求める。【００１９】
【数６】
0006040313.tif 000007
【００２０】
認証サーバ検証値暗号化ステップにおいて、認証サーバが、j=1,…,mについて、aj番目の認証サーバと当該認証サーバとの共通鍵を用いて、検証値qa_i(a_j)を暗号化した暗号文EncS_a_iS_a_j(qa_i(a_j))を得る。認証サーバ検証値復号ステップにおいて、認証サーバが、j=1,…,mについて、aj番目の認証サーバと当該認証サーバとの共通鍵を用いて、aj番目の認証サーバから受信した暗号文EncS_a_iS_a_j(qa_j(a_i))を復号して検証値qa_j(a_i)を得る。認証サーバ検証ステップにおいて、認証サーバが、検証値qa_1(a_i),…,qa_m(a_i)の総和が0と等しいか否かを検証する。【００２１】
この発明の第二の態様のマルチパーティセキュア認証方法は、パスワード分散ステップ、パスワード分散値暗号化ステップ、パスワード分散値転送ステップ、第一パスワード分散値復号ステップ、第二パスワード分散値復号ステップ、第一認証サーバ検証値生成ステップ、第二認証サーバ検証値生成ステップ、第一認証サーバ検証値暗号化ステップ、第二認証サーバ検証値暗号化ステップ、第一認証サーバ検証値復号ステップ、第二認証サーバ検証値復号ステップ、第一認証サーバ検証ステップ及び第二認証サーバ検証ステップを含む。【００２２】
以下では、n≧3であり、2k-1≦nであり、k≦mであり、m≦nであり、a1,…,amはam=nかつそれぞれ1以上n以下の相異なるm個の整数であり、(k,n)秘密分散はn個の分散値のうちk個以上あれば復元することができる秘密分散であり、[r(i)]1,…,[r(i)]n（i=1,…,n）は復元すると乱数r(i)となる(k,n)秘密分散による分散値であり、[0(a_i)]1,…,[0(a_i)]n（i=1,…,m）は復元すると0となる(k,n)秘密分散による分散値であり、
λa_i(j)（i∈1,…,m）は次式を満たす定数であり、【００２３】
【数７】
0006040313.tif 000008
【００２４】
^λa_i(j)（i∈1,…,m）は次式を満たす定数であるとする。【００２５】
【数８】
0006040313.tif 000009
【００２６】
パスワード分散ステップにおいて、利用者装置が、入力されたパスワードw'をn個の分散値[w']1,…,[w']nに分散する。パスワード分散値暗号化ステップにおいて、利用者装置が、i=1,…,n-1について、利用者装置とi番目の認証サーバとの共通鍵を用いて、分散値[w']iを暗号化した暗号文EncUS_i([w']i)を得、利用者装置と中間認証サーバとの共通鍵を用いて、分散値[w']nを暗号化した暗号文EncUS_n([w']n)を得る。パスワード分散値転送ステップにおいて、中間認証サーバが、i=1,…,n-1について、利用者装置から受信した暗号文EncUS_i([w']i)をi番目の認証サーバへ送信する。第一パスワード分散値復号ステップにおいて、認証サーバが、利用者装置と当該認証サーバとの共通鍵を用いて、中間認証サーバから受信した暗号文EncUS_i([w']i)を復号して分散値[w']iを得る。第二パスワード分散値復号ステップにおいて、中間認証サーバが、利用者装置と当該中間認証サーバとの共通鍵を用いて、暗号文EncUS_n([w']n)を復号して分散値[w']nを得る。第一認証サーバ検証値生成ステップにおいて、認証サーバが、j=1,…,mについて、次式により検証値qa_i(a_j)を求める。
【００２７】
【数９】
0006040313.tif 000010
【００２８】
第二認証サーバ検証値生成ステップにおいて、中間認証サーバが、j=1,…,mについて、次式により検証値qa_m(a_j)を求める。【００２９】
【数１０】
0006040313.tif 000011
【００３０】
第一認証サーバ検証値暗号化ステップにおいて、認証サーバが、j=1,…,mについて、aj番目の認証サーバおよびam番目の中間認証サーバと当該認証サーバとの共通鍵を用いて、検証値qa_i(a_j)を暗号化した暗号文EncS_a_iS_a_j(qa_i(a_j))を得る。第二認証サーバ検証値暗号化ステップにおいて、中間認証サーバが、j=1,…,m-1について、aj番目の認証サーバと当該中間認証サーバとの共通鍵を用いて、検証値qa_m(a_j)を暗号化した暗号文EncS_a_mS_a_j(qa_m(a_j))を得る。第一認証サーバ検証値復号ステップにおいて、認証サーバが、j=1,…,mについて、aj番目の認証サーバおよびam番目の中間認証サーバと当該認証サーバとの共通鍵を用いて、aj番目の認証サーバから受信した暗号文EncS_a_iS_a_j(qa_j(a_i))を復号して検証値qa_j(a_i)を得る。第二認証サーバ検証値復号ステップにおいて、中間認証サーバが、j=1,…,m-1について、aj番目の認証サーバと当該中間認証サーバとの共通鍵を用いて、aj番目の認証サーバから受信した暗号文EncS_a_mS_a_j(qa_j(a_m))を復号して検証値qa_j(a_m)を得る。第一認証サーバ検証ステップにおいて、認証サーバが、検証値qa_1(a_i),…,qa_m(a_i)の総和が0と等しいか否かを検証する。第二認証サーバ検証ステップにおいて、中間認証サーバが、検証値qa_1(a_m),…,qa_m(a_m)の総和が0と等しいか否かを検証する。
【発明の効果】
【００３１】
この発明によれば、中間サーバが存在する場合であっても複数のサーバが同時にユーザを安全に認証することができる。
【図面の簡単な説明】
【００３２】
【図１】図１は、第一実施形態に係るマルチパーティセキュア認証システムの機能構成を例示する図である。
【図２】図２は、第一実施形態に係る利用者装置の機能構成を例示する図である。
【図３】図３は、第一実施形態に係る中間サーバの機能構成を例示する図である。
【図４】図４は、第一実施形態に係る認証サーバの機能構成を例示する図である。
【図５】図５は、第一実施形態に係るマルチパーティセキュア認証方法のパスワード登録フェーズの処理フローを例示する図である。
【図６】図６は、第一実施形態に係るマルチパーティセキュア認証方法の乱数生成フェーズの処理フローを例示する図である。
【図７】図７は、第一実施形態に係るマルチパーティセキュア認証方法の認証フェーズの処理フローを例示する図である。
【図８】図８は、第一実施形態に係るマルチパーティセキュア認証方法の認証フェーズの処理フローを例示する図である。
【図９】図９は、第一実施形態に係るマルチパーティセキュア認証方法の認証フェーズの処理フローを例示する図である。
【図１０】図１０は、第二実施形態に係るマルチパーティセキュア認証システムの機能構成を例示する図である。
【図１１】図１１は、第二実施形態に係る利用者装置の機能構成を例示する図である。
【図１２】図１２は、第二実施形態に係る中間サーバの機能構成を例示する図である。
【図１３】図１３は、第二実施形態に係る認証サーバの機能構成を例示する図である。
【図１４】図１４は、第二実施形態に係るマルチパーティセキュア認証方法の乱数生成フェーズの処理フローを例示する図である。
【図１５】図１５は、第二実施形態に係るマルチパーティセキュア認証方法の認証フェーズの処理フローを例示する図である。
【図１６】図１６は、第三実施形態に係るマルチパーティセキュア認証システムの機能構成を例示する図である。
【図１７】図１７は、第三実施形態に係る利用者装置の機能構成を例示する図である。
【図１８】図１８は、第三実施形態に係る中間サーバの機能構成を例示する図である。
【図１９】図１９は、第三実施形態に係る認証サーバの機能構成を例示する図である。
【図２０】図２０は、第三実施形態に係るマルチパーティセキュア認証方法の乱数生成フェーズの処理フローを例示する図である。
【図２１】図２１は、第三実施形態に係るマルチパーティセキュア認証方法の乱数生成フェーズの処理フローを例示する図である。
【発明を実施するための形態】
【００３３】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００３４】
［表記方法］
実施形態の説明に先立ち、この明細書で用いる表記方法および用語を定義する。
・_（アンダースコア）は下付き添字を表す。例えば、xy_zはyzがxに対する上付き添字であり、xy_zはyzがxに対する下付き添字であることを表す。
・^（キャレット）は直後の文字にサーカムフレックスが付されることを表す。例えば、^λは数式内における以下の文字を表している。
【００３５】
【数１１】
0006040313.tif 000012
【００３６】
・→（上付き右矢印）はベクトルを表す。
・[]（角括弧）は括弧内のデータの分散値を表す。例えば、[w]はwの分散値である。
・EncAB(X)は、ノードAとノードBとの共通鍵によりデータXを暗号化した暗号文を表す。
【００３７】
［基本的な考え方］
この発明のマルチパーティセキュア認証技術の基本的な考え方を説明する。
【００３８】
全体を通しての登場人物は、利用者端末（利用者装置とも呼ぶ）１、中間サーバ２及びn台の認証サーバ３1,…,３nである。ただし、nは3以上の整数である。
【００３９】
まず、システムを利用する利用者端末１のパスワードがwであることを認証サーバ群３1,…,３nに登録する。認証を実施する際に併せて用いるいくつかの乱数についてもユーザで生成し、各認証サーバ３1,…,３nに送る。このとき、間に入る中間サーバ２がこれらの情報を悪用し利用者端末１に成りすまさないよう、送信する分散値等は各認証サーバ３1,…,３nとの共通鍵で暗号化しておく。また、パスワード自体も秘密分散を用い、各認証サーバ３1,…,３nにはパスワードの分散値のみを保存する。そのため、各認証サーバ３1,…,３nは、パスワードそのものはわからない。
【００４０】
次に、認証の実施手順について述べる。利用者端末１がパスワードw’によって認証を試みてきた場合、登録されている利用者端末１のパスワードwと入力されたパスワードw’とが一致することを確認するために、wとw’との差が0であることを協調計算によって導く。認証の権限がシステムを構成する各参加者（具体的には、中間サーバ２及び認証サーバ３1,…,３n）のいずれかに偏ることがないように、各参加者が認証のための計算を行う。協調計算によって登録されたパスワードw及び入力されたパスワードw’が各参加者に知られることがないように、乱数と組み合わせて協調計算を行う。また、このとき用いられる乱数を次回の認証で使い回さないように、認証の手順の最後で乱数を更新する。
【００４１】
さらに、認証手順において中間サーバ２を介して交わされる暗号文を悪用することによるリプレイ攻撃に対処するために、あらかじめ認証サーバ３1,…,３nで乱数を生成し利用者端末１と共有することによって、認証時に送信するパスワードの暗号文を再利用できなくする改良方法について述べる。なお、リプレイ攻撃とは、認証成功した暗号文を再利用して、中間サーバ２が利用者装置１になりすまして認証を成功させてしまう攻撃である。
【００４２】
［秘密分散技術］
この発明では構成要素として秘密分散技術を用いる。この発明で用いる秘密分散技術では、2k-1<nであるような(k,n)秘密分散を用いる。(k,n)秘密分散は、あるデータをn個に分割し、そのうちk-1個まで集めても元データについては何もわからないが、k個以上集めると元データを復元できるような技術である。
【００４３】
具体的には、秘密分散技術は、以下に説明するShareアルゴリズムとReconstアルゴリズムとから構成される。
【００４４】
Shareアルゴリズムはデータを分割するアルゴリズムである。分割されたデータはシェアもしくは分散値と呼ばれる。Shareアルゴリズムは秘密sを入力としてn個に分割して出力する。この手続きを次式のように記述する。
【００４５】
【数１２】
0006040313.tif 000013
【００４６】
Reconstアルゴリズムはデータを復元するアルゴリズムである。Reconstアルゴリズムはm個（k≦m≦n）のシェアを入力として元の秘密sを出力する。この発明で利用する秘密分散技術では、mと{a1,…,am}とから決定するλa_i（i=1,…,m）が存在し、次式が成り立つとする。a1,…,amは1以上n以下の相異なるm個の整数である。
【００４７】
【数１３】
0006040313.tif 000014
【００４８】
［第一実施形態］
図１を参照して、第一実施形態に係るマルチパーティセキュア認証システムの機能構成の一例を説明する。マルチパーティセキュア認証システムは、利用者装置１、中間サーバ２及びn台の認証サーバ３1,…,３nを含む。
【００４９】
図２を参照して、利用者装置１の機能構成の一例を説明する。利用者装置１は、制御部１０１、メモリ１０２、共通鍵記憶部１１、パスワード分散部１２及びパスワード分散値暗号化部１３を含む。利用者装置１は、例えば、中央演算処理装置（Central Processing Unit、CPU）、主記憶装置（Random Access Memory、RAM）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。利用者装置１は、例えば、制御部１０１の制御のもとで各処理を実行する。利用者装置１に入力されたデータや各処理で得られたデータは、例えば、メモリ１０２に格納され、メモリ１０２に格納されたデータは必要に応じて読み出されて他の処理に利用される。利用者装置１が備える各記憶部は、例えば、RAM（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）のような半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。
【００５０】
図３を参照して、中間サーバ２の機能構成の一例を説明する。中間サーバ２は、制御部２０１、メモリ２０２、共通鍵記憶部２１、パスワード分散値転送部２２、中間サーバ検証値復号部２３及び中間サーバ検証部２４を含む。中間サーバ２は、例えば、中央演算処理装置（Central Processing Unit、CPU）、主記憶装置（Random Access Memory、RAM）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。中間サーバ２は、例えば、制御部２０１の制御のもとで各処理を実行する。利用者装置１に入力されたデータや各処理で得られたデータは、例えば、メモリ２０２に格納され、メモリ２０２に格納されたデータは必要に応じて読み出されて他の処理に利用される。中間サーバ２が備える各記憶部は、例えば、RAM（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）のような半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。
【００５１】
図４を参照して、認証サーバ３の機能構成の一例を説明する。認証サーバ３は、制御部３０１、メモリ３０２、乱数分散値生成部３１、ゼロ分散値生成部３２、パスワード分散値復号部３３、中間サーバ検証値生成部３４、中間サーバ検証値暗号化部３５、認証サーバ検証値生成部３６、認証サーバ検証値暗号化部３７、認証サーバ検証値復号部３８、認証サーバ検証部３９、共通鍵記憶部４１及び分散値記憶部４２を含む。認証サーバ３は、例えば、中央演算処理装置（Central Processing Unit、CPU）、主記憶装置（Random Access Memory、RAM）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。認証サーバ３は、例えば、制御部３０１の制御のもとで各処理を実行する。認証サーバ３に入力されたデータや各処理で得られたデータは、例えば、メモリ３０２に格納され、メモリ３０２に格納されたデータは必要に応じて読み出されて他の処理に利用される。認証サーバ３が備える各記憶部は、例えば、RAM（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）のような半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。認証サーバ３が備える各記憶部は、それぞれ論理的に分割されていればよく、一つの物理的な記憶装置に記憶されていてもよい。
【００５２】
図５〜１０を参照して、マルチパーティセキュア認証方法の処理フローの一例を、実際に行われる手続きの順に従って説明する。
【００５３】
利用者端末１の共通鍵記憶部１１には、利用者端末１が暗号化通信を行う各装置との共通鍵が記憶されている。具体的には、利用者端末１と各認証サーバ３1,…,３nとの共通鍵であり、計n個の共通鍵が記憶されている。
【００５４】
中間サーバ２の共通鍵記憶部２１には、中間サーバ２が暗号化通信を行う各装置との共通鍵が記憶されている。具体的には、中間サーバ２と各認証サーバ３1,…,３nとの共通鍵であり、計n個の共通鍵が記憶されている。
【００５５】
i番目の認証サーバ３iの共通鍵記憶部４１には、認証サーバ３iが暗号化通信を行う各装置との共通鍵が記憶されている。具体的には、利用者端末１、中間サーバ２、他のn-1台の認証サーバ３j（j=1,…,n、j≠i）との共通鍵であり、1台の認証サーバ３の共通鍵記憶部４１には計n+1個の共通鍵が記憶されている。
【００５６】
この発明で用いる共通鍵暗号方式は、既存のいかなる共通鍵暗号方式であってもよく、この発明を適用する情報システムにおいて求められる安全性や処理速度などを勘案して選択すればよい。各装置の記憶する共通鍵は、選択された共通鍵暗号方式に則って生成された共通鍵であり、当該共通鍵暗号方式が許容する鍵交換方式により共有すればよい。
【００５７】
＜＜パスワード登録フェーズ＞＞
図５を参照して、マルチパーティセキュア認証方法のパスワード登録フェーズの処理を説明する。パスワード登録フェーズは、新規にユーザを登録する場合または登録済みユーザのパスワードを変更する場合に実行される。
【００５８】
ステップＳ１０１において、利用者端末１のパスワード分散部１２は、パスワードwをn個の分散値[w]1,…,[w]nに分散する。パスワードwはユーザUにより利用者端末１を操作して入力された任意のパスワードである。つまり、パスワード分散部１２は、以下の式（３）の計算を行う。
【００５９】
【数１４】
0006040313.tif 000015
【００６０】
ステップＳ１０２において、利用者端末１のパスワード分散値暗号化部１３は、i=1,…,nについて、利用者装置１とi番目の認証サーバ３iとの共通鍵を用いて、分散値[w]iを暗号化した暗号文EncUS_i([w]i)を得る。
【００６１】
ステップＳ１０３において、利用者端末１のパスワード分散値暗号化部１３は、ステップＳ１０２で得たn個の暗号文EncUS_1([w]1),…,EncUS_n([w]n)を中間サーバ２へ送信する。
【００６２】
ステップＳ２０１において、中間サーバ２のパスワード分散値転送部２２は、利用者端末１から受信したn個の暗号文EncUS_1([w]1),…,EncUS_n([w]n)を受信し、i=1,…,nについて、暗号文EncUS_i([w]i)を認証サーバ３iへそれぞれ送信する。
【００６３】
ステップＳ３０１において、認証サーバ３iのパスワード分散値復号部３３は、中間サーバ２から転送された暗号文EncUS_i([w]i)を受信する。
【００６４】
ステップＳ３０２において、認証サーバ３iのパスワード分散値復号部３３は、利用者端末１と認証サーバ３iとの共通鍵を用いて、中間サーバ２から受信した暗号文EncUS_i([w]i)を復号して分散値[w]iを得る。分散値[w]iは、分散値記憶部４２へ記憶する。
【００６５】
＜＜乱数生成フェーズ＞＞
図６を参照して、マルチパーティセキュア認証方法の乱数生成フェーズの処理を説明する。乱数生成フェーズは、少なくともパスワードを登録したユーザが認証を行う前に実行されている必要がある。
【００６６】
ステップＳ３１１において、認証サーバ３iの乱数分散値生成部３１は、復元すると乱数r1,…,rdとなるd個の分散値[r1]i,…,[rd]iを生成する。生成した分散値[r1]i,…,[rd]iは、分散値記憶部４２へ記憶する。ここで、d≧1である。
【００６７】
ステップＳ３１２において、認証サーバ３iのゼロ分散値生成部３２は、復元すると0となるd個の分散値[01]i,…,[0d]iを生成する。生成した分散値[01]i,…,[0d]iは、分散値記憶部４２へ記憶する。
【００６８】
ステップＳ３１１からステップＳ３１２の処理は、ステップＳ１０１からステップＳ３０２の処理と並行して実行しても構わないし、独立して予め行なっておいても構わない。
【００６９】
＜＜認証フェーズ＞＞
図７〜９を参照して、マルチパーティセキュア認証方法の認証フェーズの処理を説明する。認証フェーズは、パスワードを登録しているユーザが認証を求める際に実行される。認証フェーズの処理は、n台の認証サーバ３1,…,３nすべてが行う必要はなく、任意に選択したm台のみが実行すればよい。以降の説明では、a1,…,amを1以上n以下の相異なるm個の整数として、m台の認証サーバ３a_1,…,３a_mが認証フェーズの処理を行うものとする。
【００７０】
認証サーバ３a_iは、分散値記憶部４２に記憶されている分散値[r1]a_i,…,[rd]a_iから[r(W)]a_i、[r(1)]a_i，…，[r(m)]a_iを選択する。また、同様に、認証サーバ３a_iは、分散値記憶部４２に記憶されている分散値[01]a_i,…,[0d]a_iから[0(W)]a_i，[0(1)]a_i，…，[0(m)]a_iを選択する。
【００７１】
図７に示すステップＳ１２１において、パスワードwを登録したユーザUが利用者端末１を操作して、認証を求めるためのパスワードw’を入力する。
【００７２】
ステップＳ１２２において、利用者端末１のパスワード分散部１２は、パスワードw’をn個の分散値[w’]1,…,[w’]nに分散する。つまり、パスワード分散部１２は、以下の計算を行う。
【００７３】
【数１５】
0006040313.tif 000016
【００７４】
ステップＳ１２３において、利用者端末１のパスワード分散値暗号化部１３は、i=1,…,mについて、分散値[w']a_iを利用者装置１とai番目の認証サーバ３a_iとの共通鍵を用いて暗号化した暗号文EncUS_a_i([w']a_i)を得る。
【００７５】
ステップＳ１２４において、利用者端末１のパスワード分散値暗号化部１３は、ステップＳ１２３で得たn個の暗号文EncUS_1([w']1),…,EncUS_n([w']n)を中間サーバ２へ送信する。
【００７６】
ステップＳ２２１において、中間サーバ２のパスワード分散値転送部２２は、利用者端末１から受信したn個の暗号文EncUS_1([w']1),…,EncUS_n([w']n)を受信し、i=1,…,mについて、暗号文EncUS_a_i([w']a_i)を認証サーバ３a_iへ送信する。
【００７７】
ステップＳ３２１において、認証サーバ３a_iのパスワード分散値復号部３３は、中間サーバ２から転送された暗号文EncUS_a_i([w']a_i)を受信する。
【００７８】
ステップＳ３２２において、認証サーバ３a_iのパスワード分散値復号部３３は、中間サーバ２から受信した暗号文EncUS_a_i([w']a_i)を利用者端末１と認証サーバ３a_iとの共通鍵を用いて復号して分散値[w']a_iを得る。
【００７９】
図８に示すステップＳ３３１において、認証サーバ３a_iの中間サーバ検証値生成部３４は、分散値記憶部４２に記憶されている分散値[w]a_i、[r(W)]a_i、[0(W)]a_i及びパスワード分散値復号部３３の出力する分散値[w']a_iを用いて、下記の式（５）により検証値qa_i(W)を求める。
【００８０】
【数１６】
0006040313.tif 000017
【００８１】
ここで、λa_i(W)は式（６）を満たす既知の定数であり、^λa_i(W)は式（７）を満たす既知の定数である。
【００８２】
【数１７】
0006040313.tif 000018
【００８３】
ステップＳ３３２において、認証サーバ３a_iの中間サーバ検証値暗号化部３５は、中間サーバ２と認証サーバ３a_iとの共通鍵を用いて、検証値qa_i(W)を暗号化した暗号文EncWS_a_i(qa_i(W))を得る。
【００８４】
ステップＳ３３３において、認証サーバ３a_iの中間サーバ検証値暗号化部３５は、ステップＳ３３２で得た暗号文EncWS_a_i(qa_i(W))を中間サーバ２へ送信する。
【００８５】
ステップＳ２３１において、中間サーバ２の中間サーバ検証値復号部２３は、m台の認証サーバ３a_1,…,３a_mから受信したm個の暗号文EncWS_a_1(qa_1(W)),…,EncWS_a_m(qa_m(W))を受信する。
【００８６】
ステップＳ２３２において、中間サーバ２の中間サーバ検証値復号部２３は、i=1,…,mについて、中間サーバ２とai番目の認証サーバ３a_iとの共通鍵を用いて、暗号文EncWS_a_i(qa_i(W))を復号して検証値qa_i(W)を得る。中間サーバ検証値復号部２３は、m個の検証値qa_1(W),…,qa_m(W)を中間サーバ検証部２４へ出力する。
【００８７】
ステップＳ２３３において、中間サーバ２の中間サーバ検証部２４は、検証値qa_1(W),…,qa_m(W)の総和が0と等しいか否かを検証する。中間サーバ検証部２４は、具体的には式（８）の等式が成り立つか否かを確認する。
【００８８】
【数１８】
0006040313.tif 000019
【００８９】
中間サーバ検証部２４は、式（８）が成り立つ場合には、利用者装置１へ認証成功を通知し、式（８）が成り立たない場合には、利用者装置１へ認証失敗を通知する。
【００９０】
図９に示すステップＳ３４１iにおいて、認証サーバ３a_iの認証サーバ検証値生成部３６は、j=1,…,mについて、分散値記憶部４２に記憶されている分散値[w]a_i、[r(a_j)]a_i、[0(a_j)]a_i及びパスワード分散値復号部３３の出力する分散値[w']a_iを用いて、下記の式（９）により検証値qa_i(a_j)を求める。
【００９１】
【数１９】
0006040313.tif 000020
【００９２】
ここで、λa_i(j)は式（１０）を満たす既知の定数であり、^λa_i(j)は式（１１）を満たす既知の定数である。
【００９３】
【数２０】
0006040313.tif 000021
【００９４】
ステップＳ３４２iにおいて、認証サーバ３a_iの認証サーバ検証値暗号化部３７は、j=1,…,m（j≠i）について、aj番目の認証サーバ３a_jとai番目の認証サーバ３a_iとの共通鍵を用いて、検証値qa_i(a_j)を暗号化した暗号文EncS_a_iS_a_j(qa_i(a_j))を得る。結果として、認証サーバ検証値暗号化部３７は、m-1個の暗号文EncS_a_iS_a_1(qa_i(a_1)),…,EncS_a_iS_a_m(qa_i(a_m))（ただし、EncS_a_iS_a_i(qa_i(a_i))を除く）を得ることになる。
【００９５】
ステップＳ３４３iにおいて、認証サーバ３a_iの認証サーバ検証値暗号化部３７は、j=1,…,m（j≠i）について、ステップＳ３４２iで得たm-1個の暗号文EncS_a_iS_a_1(qa_i(a_1)),…,EncS_a_iS_a_m(qa_i(a_m))（ただし、EncS_a_iS_a_i(qa_i(a_i))を除く）を認証サーバ３a_jへそれぞれ送信する。
【００９６】
ステップＳ３４４iにおいて、認証サーバ３a_iの認証サーバ検証値復号部３８は、m-1台の認証サーバ３a_j（j=1,…,m（j≠i））からm-1個の暗号文EncS_a_1S_a_i(qa_1(a_i)),…,EncS_a_mS_a_i(qa_m(a_i))（ただし、EncS_a_iS_a_i(qa_i(a_i))を除く）を受信する。
【００９７】
ステップＳ３４５iにおいて、認証サーバ３a_iの認証サーバ検証値復号部３８は、j=1,…,m（j≠i）について、aj番目の認証サーバ３a_jとai番目の認証サーバ３a_iとの共通鍵を用いて、暗号文EncS_a_jS_a_i(qa_j(a_i))を復号して検証値qa_i(a_j)を得る。認証サーバ検証値復号部３８は、ステップＳ３４１iにおいて認証サーバ検証値生成部３６が生成していた検証値qa_i(a_i)と併せて、m個の検証値qa_1(a_i),…,qa_m(a_i)を認証サーバ検証部３９へ出力する。
【００９８】
ステップＳ３４５iにおいて、認証サーバ３a_iの認証サーバ検証部３９は、検証値qa_1(a_i),…,qa_m(a_i)の総和が0と等しいか否かを検証する。認証サーバ検証部３９は、具体的には式（１２）の等式が成り立つか否かを確認する。
【００９９】
【数２１】
0006040313.tif 000022
【０１００】
認証サーバ検証部３９は、式（１２）が成り立つ場合には、利用者装置１へ認証成功を通知し、式（１２）が成り立たない場合には、利用者装置１へ認証失敗を通知する。
【０１０１】
＜＜乱数更新フェーズ＞＞
認証フェーズの処理を一回実行する度に、乱数更新フェーズの処理を実行する。乱数更新フェーズは、次回の認証で乱数を使い回さないように乱数を更新する処理である。乱数更新フェーズでは、以前の乱数生成フェーズの処理により生成された乱数のうち、未使用のものがあれば、次回の認証フェーズの処理において、その乱数を使用するように設定する。未使用の乱数がなければ、乱数生成フェーズの処理内容と同様に新たな乱数を生成する。乱数更新フェーズの処理は、認証フェーズの処理と並列に行なっても構わない。すなわち、認証フェーズにおいて乱数を利用した際に未使用の乱数が十分に残されているかを確認し、足りなければ新たな乱数を生成すればよい。
【０１０２】
［第二実施形態］
ユーザの利用する利用者端末と各認証サーバの間に存在するWebサーバ等の中間サーバには、認証の成否に加えて、利用者端末と認証サーバで交わされている暗号文を知られてしまう。中間サーバは認証に成功した際に認証手順で用いられたパスワードや乱数の分散値の暗号文を悪用してユーザに成りすまし、認証を成功させることができてしまう危険性がある。第二実施形態のマルチパーティセキュア認証システムは、送信済みの暗号文を悪用した中間サーバによるリプレイ攻撃を防ぐための改良方式である。
【０１０３】
以降の説明では、第一実施形態と相違する点を中心に説明し、第一実施形態と同様の部分については説明を省略する。
【０１０４】
図１０を参照して、第二実施形態に係るマルチパーティセキュア認証システムの機能構成の一例を説明する。マルチパーティセキュア認証システムは、利用者装置４、中間サーバ５及びn台の認証サーバ６1,…,６nを含む。
【０１０５】
図１１を参照して、利用者装置４の機能構成の一例を説明する。利用者装置４は、第一実施形態に係る利用者装置１と同様に、制御部１０１、メモリ１０２、共通鍵記憶部１１及びパスワード分散部１２を含む。第二実施形態に係る利用者装置４では、さらに、パスワード分散値暗号化部１４及び乱数復号部１５を含む。パスワード分散値暗号化部１４は第一実施形態に係るパスワード分散値暗号化部１３とは処理が異なる。
【０１０６】
図１２を参照して、中間サーバ５の機能構成の一例を説明する。中間サーバ５は、第一実施形態に係る中間サーバ２と同様に、制御部２０１、メモリ２０２、共通鍵記憶部２１、中間サーバ検証値復号部２３及び中間サーバ検証部２４を含む。第二実施形態に係る中間サーバ５では、さらに、パスワード分散値転送部２５及び乱数転送部２６を含む。パスワード分散値転送部２５は第一実施形態に係るパスワード分散値転送部２２とは処理が異なる。
【０１０７】
図１３を参照して、認証サーバ６の機能構成の一例を説明する。認証サーバ６は、第一実施形態に係る認証サーバ３と同様に、制御部３０１、メモリ３０２、乱数分散値生成部３１、ゼロ分散値生成部３２、中間サーバ検証値生成部３４、中間サーバ検証値暗号化部３５、認証サーバ検証値生成部３６、認証サーバ検証値暗号化部３７、認証サーバ検証値復号部３８、認証サーバ検証部３９、共通鍵記憶部４１及び分散値記憶部４２を含む。第二実施形態に係る認証サーバ６では、さらに、パスワード分散値復号部４３、乱数生成部４４、乱数暗号化部４５及び乱数検証部４６を含む。パスワード分散値復号部４３は第一実施形態に係るパスワード分散値復号部３３とは処理が異なる。
【０１０８】
図１４、１５を参照して、第二実施形態に係るマルチパーティセキュア認証方法の処理フローの一例を、実際に行われる手続きの順に従って説明する。
【０１０９】
図１４を参照して、リプレイ攻撃を防ぐために利用する乱数の生成手順を説明する。この乱数生成は認証フェーズを実行する前に予め行なっておく必要がある。この処理は比較的軽い処理であるため、認証フェーズを実行する直前に行うように構成してもよい。この処理は、n台の認証サーバ６1,…,６nすべてが行う必要はなく、任意に選択したm台のみが実行すればよい。以降の説明では、a1,…,amを1以上n以下の相異なるm個の整数として、m台の認証サーバ６a_1,…,６a_mが処理を行うものとする。
【０１１０】
ステップＳ３５１において、認証サーバ６a_iの乱数生成部４４は、乱数ta_iを生成する。
【０１１１】
ステップＳ３５２において、認証サーバ６a_iの乱数暗号化部４５は、利用者装置４とai番目の認証サーバ６a_iとの共通鍵を用いて、乱数ta_iを暗号化した暗号文EncUS_a_i(ta_i)を得る。
【０１１２】
ステップＳ３５３において、認証サーバ６a_iの乱数暗号化部４５は、暗号文EncUS_a_i(ta_i)を中間サーバ５へ送信する。
【０１１３】
ステップＳ２５１において、中間サーバ５の乱数転送部２６は、m台の認証サーバ６a_i（i=1,…,m）からm個の暗号文EncUS_a_i(ta_i)（i=1,…,m）を受信する。受信したm個の暗号文EncUS_a_i(ta_i)（i=1,…,m）は利用者端末４へ送信する。
【０１１４】
ステップＳ１５１において、利用者端末４の乱数復号部１５は、中間サーバ５からm個の暗号文EncUS_a_i(ta_i)（i=1,…,m）を受信する。
【０１１５】
ステップＳ１５２において、乱数復号部１５は、i=1,…,mについて、暗号文EncUS_a_i(ta_i)を復号して分散値ta_iを得る。分散値ta_iはメモリ１０２や共通鍵記憶部１１などのいずれかの記憶部に記憶する。
【０１１６】
図１５を参照して、リプレイ攻撃を防ぐために改良した認証フェーズの処理を説明する。第一実施形態の認証フェーズとの相違点は、ステップＳ１２３及びステップＳ２２１の処理が異なることと、ステップＳ３２３の処理が追加されたことである。
【０１１７】
ステップＳ１２３において、利用者端末４のパスワード分散値暗号化部１４は、i=1,…,mについて、分散値[w']a_iを乱数ta_iと共に利用者装置４とai番目の認証サーバ６a_iとの共通鍵を用いて暗号化した暗号文EncUS_a_i(ta_i,[w']a_i)を得る。
【０１１８】
ステップＳ２２１において、中間サーバ５のパスワード分散値転送部２５は、利用者端末４から受信したm個の暗号文EncUS_a_1(ta_i,[w']a_1),…,EncUS_a_m(ta_i,[w']a_m)を受信し、i=1,…,mについて、暗号文EncUS_a_i(ta_i,[w']a_i)を認証サーバ６a_iへ送信する。
【０１１９】
ステップＳ３２３において、認証サーバ６a_iの乱数検証部４６は、暗号文EncUS_a_i(ta_i,[w']a_i)を復号して得た乱数ta_iがステップＳ３５１で生成した乱数ta_iと等しいか否かを確認する。乱数検証部４６は、復号して得た乱数ta_iがステップＳ３５１で生成した乱数ta_iと等しくない場合には、利用者装置４へ認証失敗を通知する。その他の場合には、認証フェーズのステップＳ３３１以降の処理を続行する。
【０１２０】
［第三実施形態］
第一実施形態のマルチパーティセキュア認証システムは、各認証サーバが乱数生成フェーズの処理を実行した。第三実施形態のマルチパーティセキュア認証システムは、利用者端末が乱数生成フェーズの処理を実行する。以下では、第一実施形態のマルチパーティセキュア認証システムに適用した場合の例を説明するが、第三実施形態の構成方法は、第二実施形態のマルチパーティセキュア認証システムへも同様に適用することができる。
【０１２１】
以降の説明では、第一実施形態と相違する点を中心に説明し、第一実施形態と同様の部分については説明を省略する。
【０１２２】
図１６を参照して、第三実施形態に係るマルチパーティセキュア認証システムの機能構成の一例を説明する。マルチパーティセキュア認証システムは、利用者装置７、中間サーバ８及びn台の認証サーバ９1,…,９nを含む。
【０１２３】
図１７を参照して、利用者装置７の機能構成の一例を説明する。利用者装置７は、第一実施形態に係る利用者装置１と同様に、制御部１０１、メモリ１０２、共通鍵記憶部１１、パスワード分散部１２及びパスワード分散値暗号化部１３を含む。第三実施形態に係る利用者装置７では、さらに、乱数分散値生成部１６、乱数分散値暗号化部１７、ゼロ分散値生成部１８及びゼロ分散値暗号化部１９を含む。
【０１２４】
図１８を参照して、中間サーバ８の機能構成の一例を説明する。中間サーバ８は、第一実施形態に係る中間サーバ２と同様に、制御部２０１、メモリ２０２、共通鍵記憶部２１、パスワード分散値転送部２２、中間サーバ検証値復号部２３及び中間サーバ検証部２４を含む。第三実施形態に係る中間サーバ８では、さらに、乱数分散値転送部２７及びゼロ分散値転送部２８を含む。
【０１２５】
図１９を参照して、認証サーバ９の機能構成の一例を説明する。認証サーバ９は、第一実施形態に係る認証サーバ３と同様に、制御部３０１、メモリ３０２、中間サーバ検証値生成部３４、中間サーバ検証値暗号化部３５、認証サーバ検証値生成部３６、認証サーバ検証値暗号化部３７、認証サーバ検証値復号部３８、認証サーバ検証部３９、共通鍵記憶部４１及び分散値記憶部４２を含む。第三実施形態に係る認証サーバ９では、さらに、乱数分散値復号部４７及びゼロ分散値復号部４８を含む。
【０１２６】
図２０、２１を参照して、第三実施形態に係るマルチパーティセキュア認証方法の処理フローの一例を、実際に行われる手続きの順に従って説明する。
【０１２７】
＜＜乱数生成フェーズ＞＞
図２０、２１を参照して、第三実施形態に係る乱数生成フェーズの処理を説明する。
【０１２８】
図２０に示すステップＳ１１１において、利用者端末７の乱数分散値生成部１６は、n+1個の乱数r(W)、r(1),…,r(n)を生成する。
【０１２９】
ステップＳ１１２において、利用者端末７の乱数分散値生成部１６は、各乱数r(W)、r(1),…,r(n)をそれぞれn個の分散値[r(W)]1,…,[r(W)]n、[r(1)]1,…,[r(1)]n,…,[r(n)]1,…,[r(n)]nへ分散する。つまり、乱数分散値生成部１６は、以下の式（１３）（１４）の計算を行う。
【０１３０】
【数２２】
0006040313.tif 000023
【０１３１】
ステップＳ１１３において、利用者端末７の乱数分散値暗号化部１７は、i=1,…,nについて、利用者装置７とi番目の認証サーバ９iとの共通鍵を用いて、分散値[r(W)]i,[r(1)]i,…,[r(n)]iを暗号化した暗号文EncUS_i([r(W)]i,[r(1)]i,…,[r(n)]i)を得る。
【０１３２】
ステップＳ１１４において、利用者端末７の乱数分散値暗号化部１７は、ステップＳ１１３で得たn個の暗号文EncUS_1([r(W)]1,[r(1)]1,…,[r(n)]1),…,EncUS_n([r(W)]n,[r(1)]n,…,[r(n)]n)を中間サーバ８へ送信する。
【０１３３】
ステップＳ２１１において、中間サーバ８の乱数分散値転送部２７は、利用者端末７から受信したn個の暗号文EncUS_1([r(W)]1,[r(1)]1,…,[r(n)]1),…,EncUS_n([r(W)]n,[r(1)]n,…,[r(n)]n)を受信し、i=1,…,nについて、暗号文EncUS_i([r(W)]i,[r(1)]i,…,[r(n)]i)を認証サーバ９iへそれぞれ送信する。
【０１３４】
ステップＳ３１３において、認証サーバ９iの乱数分散値復号部４７は、中間サーバ８から転送された暗号文EncUS_i([r(W)]i,[r(1)]i,…,[r(n)]i)を受信する。
【０１３５】
ステップＳ３１４において、認証サーバ９iの乱数分散値復号部４７は、利用者端末７と認証サーバ９iとの共通鍵を用いて、中間サーバ８から受信した暗号文EncUS_i([r(W)]i,[r(1)]i,…,[r(n)]i)を復号してn+1個の分散値[r(W)]i,[r(1)]i,…,[r(n)]iを得る。分散値[r(W)]i,[r(1)]i,…,[r(n)]iは、分散値記憶部４２へ記憶する。
【０１３６】
図２１に示すステップＳ１１５において、利用者端末７のゼロ分散値生成部１８は、復元すると0となるm+1組の分散値[0(W)]1,…,[0(W)]n、[0(1)]1,…,[0(1)]n,…,[0(m)]1,…,[0(m)]nを生成する。
【０１３７】
ステップＳ１１６において、利用者端末７のゼロ分散値暗号化部１９は、i=1,…,nについて、利用者装置７とi番目の認証サーバ９iとの共通鍵を用いて、分散値[0(W)]i,[0(1)]i,…,[0(m)]iを暗号化した暗号文EncUS_i([0(W)]i,[0(1)]i,…,[0(m)]i)を得る。
【０１３８】
ステップＳ１１７において、利用者端末７のゼロ分散値暗号化部１９は、ステップＳ１１６で得たn個の暗号文EncUS_1([0(W)]1,[0(1)]1,…,[0(m)]1),…,EncUS_n([0(W)]n,[0(1)]n,…,[0(m)]n)を中間サーバ８へ送信する。
【０１３９】
ステップＳ２１２において、中間サーバ８のゼロ分散値転送部２８は、利用者端末７から受信したn個の暗号文EncUS_1([0(W)]1,[0(1)]1,…,[0(m)]1),…,EncUS_n([0(W)]n,[0(1)]n,…,[0(m)]n)を受信し、i=1,…,nについて、暗号文EncUS_i([0(W)]i,[0(1)]i,…,[0(m)]i)を認証サーバ９iへそれぞれ送信する。
【０１４０】
ステップＳ３１５において、認証サーバ９iのゼロ分散値復号部４８は、中間サーバ８から転送された暗号文EncUS_i([0(W)]i,[0(1)]i,…,[0(m)]i)を受信する。
【０１４１】
ステップＳ３１６において、認証サーバ９iのゼロ分散値復号部４８は、利用者端末７と認証サーバ９iとの共通鍵を用いて、中間サーバ８から受信した暗号文EncUS_i([0(W)]i,[0(1)]i,…,[0(m)]i)を復号してm+1個の分散値[0(W)]i,[0(1)]i,…,[0(m)]iを得る。分散値[0(W)]i,[0(1)]i,…,[0(m)]iは、分散値記憶部４２へ記憶する。
【０１４２】
ステップＳ１１１からステップＳ３１６の処理は、第一実施形態のマルチパーティセキュア認証方法と同様に、ステップＳ１０１からステップＳ３０２の処理と並行して実行しても構わないし、独立して予め行なっておいても構わない。
【０１４３】
［第四実施形態］
第四実施形態のマルチパーティセキュア認証システムは、乱数生成フェーズの処理のみが上述の実施形態とは異なる。第四実施形態の構成方法は、第一実施形態から第三実施形態のマルチパーティセキュア認証システムへ適用することができる。
【０１４４】
以降の説明では、第一実施形態と相違する点を中心に説明し、第一実施形態と同様の部分については説明を省略する。
【０１４５】
＜＜乱数生成フェーズ＞＞
第四実施形態に係る乱数生成フェーズの処理を説明する。この実施形態では、n台の認証サーバ３1,…,３nのうち任意のn-k+1台の組み合わせの集合を{b1,…,bB}とする。ただし、Bは次式で定義される。
【０１４６】
【数２３】
0006040313.tif 000024
【０１４７】
n台の認証サーバ３1,…,３nのうち任意のn-m+2台の組み合わせの集合を{c1,…,cC}とする。ただし、Cは次式で定義される。
【０１４８】
【数２４】
0006040313.tif 000025
【０１４９】
n台の認証サーバ３1,…,３nのうち任意のn-m+1台の組み合わせの集合を{d1,…,dD}とする。ただし、Dは次式で定義される。
【０１５０】
【数２５】
0006040313.tif 000026
【０１５１】
図６に示すステップＳ３１１において、認証サーバ３iの乱数分散値生成部３１は、乱数もしくは疑似乱数u(W)1,…,u(W)Bを生成し、i∈bjについて{u(W)b_j}を保持し、これを分散値[r(W)]iとする。乱数u(W)1,…,u(W)Bは、利用者端末１が生成して各認証サーバ３1,…,３nに送信してもよいし、認証サーバ３1,…,３nが相互に生成して互いに送りあってもよいし、あらかじめ認証サーバ３1,…,３nが保持していた疑似乱数のシードから生成してもよい。
【０１５２】
次に、認証サーバ３iの乱数分散値生成部３１は、j=1,…,nについて、乱数もしくは疑似乱数u(j)1,…,u(j)Bを生成し、j∈bhについて{u(j)b_h}を保持し、これを分散値[r(j)]iとする。乱数u(j)1,…,u(j)Bは、利用者端末１が生成して各認証サーバ３1,…,３nに送信してもよいし、認証サーバ３1,…,３nが相互に生成して互いに送りあってもよいし、あらかじめ認証サーバ３1,…,３nが保持していた疑似乱数のシードから生成してもよい。
【０１５３】
生成した分散値[r(W)]i、[r(1)]i,…,[r(n)]iは、分散値記憶部４２へ記憶する。
【０１５４】
図６に示すステップＳ３１２において、認証サーバ３iのゼロ分散値生成部３２は、乱数もしくは疑似乱数u(W)1,…,u(W)Cを生成し、i∈cjについて{u(W)c_j}を保持し、以下の式（１５）により、分散値[0(W)]iを計算する。
【０１５５】
【数２６】
0006040313.tif 000027
【０１５６】
ここで、δc_1,…,δc_Dは既知の定数である。
【０１５７】
次に、認証サーバ３iの乱数分散値生成部３１は、j=1,…,mについて、乱数もしくは疑似乱数u(j)1,…,u(j)Cを生成し、i∈chについて{u(j)c_h}を保持し、以下の式（１６）により、分散値[0(j)]iを計算する。
【０１５８】
【数２７】
0006040313.tif 000028
【０１５９】
生成した分散値[0(W)]i、[0(1)]i,…,[0(m)]iは、分散値記憶部４２へ記憶する。
【０１６０】
［第五実施形態］
第五実施形態のマルチパーティセキュア認証システムは、乱数生成フェーズの処理のみが上述の実施形態とは異なる。第五実施形態の構成方法は、第一実施形態から第三実施形態のマルチパーティセキュア認証システムへ適用することができる。
【０１６１】
以降の説明では、第一実施形態と相違する点を中心に説明し、第一実施形態と同様の部分については説明を省略する。
【０１６２】
＜＜乱数生成フェーズ＞＞
第五実施形態に係る乱数生成フェーズの処理を説明する。この実施形態の乱数生成フェーズでは、ステップＳ３１１の処理は第四実施形態と同様であり、ステップＳ３１２の処理のみが第四実施形態と異なる。
【０１６３】
ステップＳ３１２において、認証サーバ３iのゼロ分散値生成部３２は、乱数もしくは疑似乱数u(W)1,…,u(W)Cを生成し、i∈cjについて{u(W)c_j}を保持し、以下の式（１７）により、分散値[0(W)]iを計算する。
【０１６４】
【数２８】
0006040313.tif 000029
【０１６５】
ここで、fc_jは各u(W)c_j（1≦j≦C）に対しユニークな関数であり、fc_j(0)=1、fc_j(g)=0（gはcjに属さない）が成り立つ。
【０１６６】
次に、認証サーバ３iの乱数分散値生成部３１は、j=1,…,mについて、乱数もしくは疑似乱数u(j)1,…,u(j)Cを生成し、i∈chについて{u(j)c_h}を保持し、以下の式（１８）により、分散値[0(j)]iを計算する。
【０１６７】
【数２９】
0006040313.tif 000030
【０１６８】
［第六実施形態］
第六実施形態のマルチパーティセキュア認証システムは、乱数生成フェーズの処理のみが上述の実施形態とは異なる。第六実施形態の構成方法は、第一実施形態から第三実施形態のマルチパーティセキュア認証システムへ適用することができる。
【０１６９】
以降の説明では、第一実施形態と相違する点を中心に説明し、第一実施形態と同様の部分については説明を省略する。
【０１７０】
＜＜乱数生成フェーズ＞＞
第六実施形態に係る乱数生成フェーズの処理を説明する。この実施形態の乱数生成フェーズでは、ステップＳ３１２の処理は第四実施形態と同様であり、ステップＳ３１１の処理のみが第四実施形態と異なる。
【０１７１】
ステップＳ３１１において、認証サーバ３iの乱数分散値生成部３１は、乱数もしくは疑似乱数u(W)1,…,u(W)Bを生成し、i∈bjについて{u(W)b_j}を保持し、以下の式（１９）により、分散値[r(W)]iを計算する。
【０１７２】
【数３０】
0006040313.tif 000031
【０１７３】
ここで、fb_jは各u(W)b_j（1≦j≦B）に対しユニークな関数であり、fb_j(0)=1、fb_j(g)=0（gはbjに属さない）が成り立つ。この手法については「Ronald Cramer, Ivan Damgard, and Yuval Ishai, “Share conversion, pseudorandom secret-sharing and applications to secure computation”, TCC, Vol. 3378 of Lecture Notes in Computer Science, pp. 342-362, 2005.（参考文献１）」に詳しく記載されている。
【０１７４】
次に、認証サーバ３iの乱数分散値生成部３１は、j=1,…,mについて、乱数もしくは疑似乱数u(j)1,…,u(j)Bを生成し、i∈bhについて{u(j)b_h}を保持し、以下の式（２０）により、分散値[r(j)]iを計算する。
【０１７５】
【数３１】
0006040313.tif 000032
【０１７６】
［第七実施形態］
第七実施形態のマルチパーティセキュア認証システムは、乱数生成フェーズの処理のみが上述の実施形態とは異なる。第七実施形態の構成方法は、第一実施形態から第三実施形態のマルチパーティセキュア認証システムへ適用することができる。
【０１７７】
第七実施形態の乱数生成フェーズの処理内容は、ステップＳ３１１の処理内容が第六実施形態と同様であり、ステップＳ３１２の処理内容が第五実施形態と同様である。詳細な処理の手順は、上述の第六実施形態及び第五実施形態の説明を参照されたい。
【０１７８】
［第八実施形態］
第八実施形態のマルチパーティセキュア認証システムは、乱数生成フェーズの処理のみが上述の実施形態とは異なる。第八実施形態の構成方法は、第一実施形態から第三実施形態のマルチパーティセキュア認証システムへ適用することができる。
【０１７９】
以降の説明では、第一実施形態と相違する点を中心に説明し、第一実施形態と同様の部分については説明を省略する。
【０１８０】
＜＜乱数生成フェーズ＞＞
第八実施形態に係る乱数生成フェーズの処理を説明する。この実施形態では、n台の認証サーバ３1,…,３nのうち、k≦q≦nであるような任意のq台が参加して行うものとする。以下では、a1,…,aqは1以上n以下の相異なるq個の整数である。
【０１８１】
図６に示すステップＳ３１１において、認証サーバ３a_iの乱数分散値生成部３１は、乱数uiを生成し、乱数uiを(k,n)秘密分散を用いてn個の分散値[ui]1,…,[ui]nに分散する。乱数分散値生成部３１は、j=1,…,qについて、分散値[ui]a_jをaj番目の認証サーバ３a_jとai番目の認証サーバ３a_iとの共通鍵を用いて暗号化した暗号文EncS_a_iS_a_j([ui]a_j)を得る。乱数分散値生成部３１は、j=1,…,qについて、認証サーバ３a_jへ暗号文EncS_a_iS_a_j([ui]a_j)を送信する。
【０１８２】
次に、認証サーバ３a_iの乱数分散値生成部３１は、q-1台の認証サーバ３a_j（j=1,…,q、aj≠ai）からq-1個の暗号文EncS_a_1S_a_i([u1]a_i),…,EncS_a_qS_a_i([uq]a_i)（ただし、EncS_a_iS_a_i([ui]a_i)を除く）を受信し、j=1,…,qについて、暗号文EncS_a_jS_a_i([uj]a_i)をaj番目の認証サーバ３a_jとai番目の認証サーバ３a_iとの共通鍵を用いて復号して分散値[uj]a_iを得る。結果として、乱数分散値生成部３１は、自ら生成した分散値[ui]a_iと併せて、q個の分散値[u1]a_i,…,[uq]a_iを得ることになる。
【０１８３】
次に、認証サーバ３a_iの乱数分散値生成部３１は、Aをq×(q-k+1)行列とし、[u1]a_i,…,[uq]a_iを列ベクトル→uとみなし、ベクトル→u’=A→uを計算する。
【０１８４】
行列Aは、例えば、vandermonde行列もしくはHyper-Invertible行列を用いることができる。Hyper-Invertible行列についての詳細は「Zuzana Beerliova-Trubiniova and Martin Hirt, “Perfectly-secure mpc with linear communi-cation complexity”, TCC, Vol. 4948 of Lecture Notes in Computer Science, pp. 213-230, 2008」を参照されたい。
【０１８５】
次に、認証サーバ３a_iの乱数分散値生成部３１は、ベクトル→u’の各要素をそれぞれ[r(W)]a_i,[r(1)]a_i,…,[r(m)]a_iとみなす。なお、q-k+1<m+1のときは、ステップＳ３１１を最初から再度実行してベクトル→u’を追加で生成し、m+1個の要素を得られるまで繰り返す。逆に、もし多かった場合は、次回の認証に使うように保管しておく。
【０１８６】
図６に示すステップＳ３１２において、認証サーバ３a_iのゼロ分散値生成部３２は、乱数uiを生成し、乱数uiを(m-1,n)秘密分散を用いてn個の分散値[ui]1,…,[ui]nに分散する。乱数分散値生成部３１は、j=1,…,qについて、分散値[ui]a_jをaj番目の認証サーバ３a_jとai番目の認証サーバ３a_iとの共通鍵を用いて暗号化した暗号文EncS_a_iS_a_j([ui]a_j)を得る。乱数分散値生成部３１は、j=1,…,qについて、認証サーバ３a_jへ暗号文EncS_a_iS_a_j([ui]a_j)を送信する。
【０１８７】
次に、認証サーバ３a_iの乱数分散値生成部３１は、q-1台の認証サーバ３a_j（j=1,…,q、aj≠ai）からq-1個の暗号文EncS_a_1S_a_i([u1]a_i),…,EncS_a_qS_a_i([uq]a_i)（ただし、EncS_a_iS_a_i([ui]a_i)を除く）を受信し、j=1,…,qについて、暗号文EncS_a_jS_a_i([uj]a_i)をaj番目の認証サーバ３a_jとai番目の認証サーバ３a_iとの共通鍵を用いて復号して分散値[uj]a_iを得る。結果として、乱数分散値生成部３１は、自ら生成した分散値[ui]a_iと併せて、q個の分散値[u1]a_i,…,[uq]a_iを得ることになる。
【０１８８】
次に、認証サーバ３a_iの乱数分散値生成部３１は、Aをq×(q-k+1)行列とし、[u1]a_i,…,[uq]a_iを列ベクトル→uとみなし、ベクトル→u’=A→uを計算する。
【０１８９】
次に、認証サーバ３a_iの乱数分散値生成部３１は、ベクトル→u’の各要素にaiを乗じた値をそれぞれ[0(W)]a_i,[0(1)]a_i,…,[0(m)]a_iとみなす。なお、q-k+1<m+1のときは、ステップＳ３１２を最初から再度実行してベクトル→u’を追加で生成し、m+1個の要素を得られるまで繰り返す。逆に、もし多かった場合は、次回の認証に使うように保管しておく。
【０１９０】
［第九実施形態］
第九実施形態のマルチパーティセキュア認証システムは、乱数更新フェーズの処理のみが上述の実施形態とは異なる。第九実施形態の構成方法は、第一実施形態から第三実施形態のマルチパーティセキュア認証システムへ適用することができる。
【０１９１】
第九実施形態の乱数更新フェーズの処理内容は、第四実施形態の乱数生成フェーズの処理内容と同様であるので、上述の第四実施形態の説明を参照されたい。
【０１９２】
［第十実施形態］
第十実施形態のマルチパーティセキュア認証システムは、乱数更新フェーズの処理のみが上述の実施形態とは異なる。第十実施形態の構成方法は、第一実施形態から第三実施形態のマルチパーティセキュア認証システムへ適用することができる。
【０１９３】
第十実施形態の乱数更新フェーズの処理内容は、第五実施形態の乱数生成フェーズの処理内容と同様であるので、上述の第五実施形態の説明を参照されたい。
【０１９４】
［第十一実施形態］
第十一実施形態のマルチパーティセキュア認証システムは、乱数更新フェーズの処理のみが上述の実施形態とは異なる。第十一実施形態の構成方法は、第一実施形態から第三実施形態のマルチパーティセキュア認証システムへ適用することができる。
【０１９５】
第十一実施形態の乱数更新フェーズの処理内容は、第六実施形態の乱数生成フェーズの処理内容と同様であるので、上述の第六実施形態の説明を参照されたい。
［第十二実施形態］
第十二実施形態のマルチパーティセキュア認証システムは、乱数更新フェーズの処理のみが上述の実施形態とは異なる。第十二実施形態の構成方法は、第一実施形態から第三実施形態のマルチパーティセキュア認証システムへ適用することができる。
【０１９６】
第十二実施形態の乱数更新フェーズの処理内容は、第七実施形態の乱数生成フェーズの処理内容と同様であるので、上述の第七実施形態の説明を参照されたい。
【０１９７】
［第十三実施形態］
第十三実施形態のマルチパーティセキュア認証システムは、乱数更新フェーズの処理のみが上述の実施形態とは異なる。第十三実施形態の構成方法は、第一実施形態から第三実施形態のマルチパーティセキュア認証システムへ適用することができる。
【０１９８】
第十三実施形態の乱数更新フェーズの処理内容は、第八実施形態の乱数生成フェーズの処理内容と同様であるので、上述の第八実施形態の説明を参照されたい。
【０１９９】
［変形例］
上述の各実施形態では、マルチパーティセキュア認証システムが、利用者装置１、中間サーバ２及びn台の認証サーバ３1,…,３nを含む構成を例に説明をしたが、中間サーバ２と１台の認証サーバ３を１台の中間認証サーバとして構成することも可能である。すなわち、マルチパーティセキュア認証システムは、例えば、利用者装置１と、n-1台の認証サーバ３1,…,３n-1と、１台の中間認証サーバ３nとを含む構成とすることができる。
【０２００】
中間認証サーバ３nは、中間サーバ２が備える構成部と、認証サーバ３が備える構成部とを併せ持つことで構成される。ただし、上述の実施形態において、中間サーバ２と認証サーバ３とで送受信したデータは、メモリ１０２を介してサーバ内部で受け渡すことができるので、必ずしも暗号化する必要はない。具体的には、中間サーバ２と認証サーバ３との共通鍵により暗号化される中間サーバ検証値qa_n(W)を暗号化する必要がなくなる。そのため、中間認証サーバ３nは、中間サーバ検証値暗号化部３５を備えなくともよい。また、中間認証サーバ３nでの検証は認証サーバ検証値で可能なため、中間サーバ検証値は必要なくなる。そのため、中間認証サーバ３nは、中間サーバ検証値生成部３４、中間サーバ検証値暗号化部３５、中間サーバ検証値復号部２３及び中間サーバ検証部２４を備えなくともよい。
【０２０１】
また、中間サーバ２と認証サーバ３を１台の中間認証サーバ３nとして構成した場合には、中間サーバ２と各認証サーバ３1,…,３nとの共通鍵を、認証サーバ３nと他の認証サーバ３1,…,３n-1との共通鍵で併用できるため、システム全体での共通鍵の数をn個減らすことができる。
【０２０２】
［応用例］
この発明のマルチパーティセキュア認証技術は、パスワード認証を利用する様々な応用システムに適用することができる。
【０２０３】
例えば、ユーザがWebページを経由して、外部の第三者による情報システムのサービスを受ける際に、各サービスプロバイダを認証サーバとして第一実施形態または第二実施形態の認証を行ってから、各サービスは当該サービスをユーザに提供するように構成してもよい。なお、当該外部サービスは、複数のサーバが連携して行うサービスであってもよいし、それぞれの単一のサーバにより実施できるサービスであってもよい。
【０２０４】
また、例えば、第三実施形態のマルチパーティセキュア認証技術をシングルサインオンの方式として用いる応用例が考えられる。このように構成すれば、ユーザは各サーバのそれぞれのサービスを一つのパスワードで受けることができる。この発明を用いれば、シングルサインオンによる認証の過程における成りすましによる漏洩のリスクを低下させることができる。
【０２０５】
さらに、例えば、第三実施形態のマルチパーティセキュア認証技術を(k,n)秘密分散を用いたストレージサービスとする応用例が考えられる。(k,n)秘密分散とは、データをn個の分散値に分割する分割方法であって、そのうちいずれのk-1個の分散値だけでは元のデータの情報を一切得ることができないが、任意のk個の分散値があれば元のデータを完全に復元することができる秘密分散方式である。(k,n)秘密分散を用いたストレージサービスでは、サーバが連携して行うサービスではあるがサーバ同士が直接通信する必要はない。この発明のマルチパーティセキュア認証技術もサーバ同士の通信が不要であるため、利点を十分に享受することが可能な応用例であると言える。
【０２０６】
［発明の効果］
この発明を用いることで、Webサーバなどの中間サーバを介していても、不正者がユーザになりすまして認証を成功させることはできない。不正者とは中間者やサーバであることも想定される。すなわちパスワードを中間者もサーバも知らないということを含む。
【０２０７】
また、この発明は、Webのサービスモデルが適用できることの他に、以下の四つの要件を実現している。
１．ユーザは複数のパスワードや煩わしい証明書のインストールが必要ないこと
２．中間者やサーバでさえ成りすましができないこと
３．サーバ間には通信路が不要であること
４．ユーザへのレスポンスまでの通信回数が最低限なことからインターネット環境でレスポンスタイムを最低限にできること
【０２０８】
上記１及び４の要件は自明である。上記２の要件は、サーバが単一主体のモデルでは、サーバは自分でデータを持っているため、わざわざ外部から認証を通って不正をするメリットが小さいが、サーバが複数ありそれぞれ異なるデータを持つ場合には、他サーバのもつデータを外部から閲覧することにメリットがある。特に秘密分散においては、データが二つ集まるとセキュリティの効力が失われるため、この問題は重大である。上記３の要件は、システム構築の際にお互いの間に通信路を持たないようなサーバ上であっても連携したサービスを展開できることを意味する。例えば、アプリケーションプロバイダは適当な複数のクラウドサービス上に自社サービスを展開できる。言い換えると、クラウドサービス同士が連携している必要がない。
【０２０９】
この発明では、上記１の要件のためにパスワードが一つであり、２の要件のためにサーバも中間者もパスワードを知ることができない秘密分散によってパスワードを保護している。なお、パスワードのハッシュ値などではサーバのローカルで辞書攻撃が可能なため不十分である。また、上記３及び４の要件のため、サーバ間通信を許せばよく知られた秘匿回路計算を用いればよく（上記３の要件に対応）、また通信回数を増やせば暗号化通信路を用いて中間者がいない場合と同等の設定とできる（上記４の要件に対応）ところを、中間者を経由した低通信回数の秘匿回路計算を専用に設計している。
【０２１０】
［プログラム、記録媒体］
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施例において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０２１１】
また、上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０２１２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０２１３】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０２１４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０２１５】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
0006040313.tif 000053
【図２】
0006040313.tif 000054
【図３】
0006040313.tif 000055
【図４】
0006040313.tif 000056
【図５】
0006040313.tif 000057
【図６】
0006040313.tif 000058
【図７】
0006040313.tif 000059
【図８】
0006040313.tif 000060
【図９】
0006040313.tif 000061
【図１０】
0006040313.tif 000062
【図１１】
0006040313.tif 000063
【図１２】
0006040313.tif 000064
【図１３】
0006040313.tif 000065
【図１４】
0006040313.tif 000066
【図１５】
0006040313.tif 000067
【図１６】
0006040313.tif 000068
【図１７】
0006040313.tif 000069
【図１８】
0006040313.tif 000070
【図１９】
0006040313.tif 000071
【図２０】
0006040313.tif 000072
【図２１】
0006040313.tif 000073