認証システム、認証方法、ならびに、プログラム
【課題】あるグループ内のサブグループにおいて、通信の複雑さを抑制して効率良く認証を行うための認証システム等を提供する。
【解決手段】端末装置111(U[1],…,U[t],…,U[m])はそれぞれの公開鍵Y[1],…,Y[t],…,Y[m]を公開し、端末群１３１の代表７０１は、種Rを生成して認証装置１２１に送信し、認証装置１２１は、チャレンジbを生成して端末群１３１に送信し、端末群１３１の端末装置111(U[1],…,U[t])の秘密鍵W[1],…,W[t]から応答d[0],…,d[m]を生成して認証装置１２１に送信し、認証装置１２１は、種R、公開鍵Y[1],…,Y[t],…,Y[m]、チャレンジbを参照して端末群１３１の匿名グループ認証を行う。
【解決手段】端末装置111(U[1],…,U[t],…,U[m])はそれぞれの公開鍵Y[1],…,Y[t],…,Y[m]を公開し、端末群１３１の代表７０１は、種Rを生成して認証装置１２１に送信し、認証装置１２１は、チャレンジbを生成して端末群１３１に送信し、端末群１３１の端末装置111(U[1],…,U[t])の秘密鍵W[1],…,W[t]から応答d[0],…,d[m]を生成して認証装置１２１に送信し、認証装置１２１は、種R、公開鍵Y[1],…,Y[t],…,Y[m]、チャレンジbを参照して端末群１３１の匿名グループ認証を行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、あるグループ内のサブグループにおいて、通信の複雑さを抑制して効率良く認証を行うための認証システム、認証方法、ならびに、これらをコンピュータ上にて実現するためのプログラムに関する。
【背景技術】
【０００２】
従来、認証技術の分野では、m人のユーザのグループのうち、少なくともt人のサブグループのユーザがいるときに、サーバと匿名でセッション鍵を共有するための手法が提案されている。このような手法を、t-out-of-m手法という。このような技術については、以下の文献に開示されている。
【非特許文献１】Duong Quang Viet，Akihiro Yamamura and Hidema Tanaka, Anonymous Password-Based Authenticated Key Exchange, Book Progress in Cryptology - INDOCRYPT 2005, Lecture Notes in Computer Science, Springer Berlin / Heidelberg, Volume 3797/2005, ISBN 978-3-540-30805-8, p.244-p.257, ２００５年
【０００３】
[特許文献１]では、匿名でパスワードに基づいた認証鍵の交換手法、特に、あるグループ内のユーザがサーバと匿名でセッション鍵を確立する手法について提案している。本手法では、正当なグループ内のユーザとサーバは、人が覚えやすいパスワードを共有しており、互いに認証を行うことができ、辞書攻撃に対して安全である。
【０００４】
従来、このような手法における通信の複雑さ（通信量に相当する）は、Θ(mn log m)のオーダーであった。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、t-out-of-m手法においては、通信の複雑さを抑制して、通信量を減らしたい、との要望は大きい。
【０００６】
本発明は、このような課題を解決するもので、あるグループ内のサブグループにおいて、通信の複雑さを抑制して効率良く認証を行うための認証システム、認証方法、ならびに、これらをコンピュータ上にて実現するためのプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記の課題を解決するため、本発明の原理にしたがい、以下の発明を開示する。
【０００８】
本発明の第１の観点に係る認証システムは、素数pを位数とする巡回群Gと、Gの生成元gと、pを法とする有限体Zpと、当該有限体Zpに対する乗法群Zp*と、ユーザ総数mと、匿名グループ認証を求める端末群に含まれる端末装置数tと、に対する認証システムであって、認証装置と、m台の端末装置U[1]，U[2]，…，U[m]と、を備え、認証装置は、種受信部、チャレンジ選択部、チャレンジ送信部、応答受信部、認証部を備え、m台の端末装置U[1]，U[2]，…，U[m]のそれぞれは、秘密鍵選択部、公開鍵生成部、公開鍵公開部を備え、m台の端末装置のうち、匿名グループ認証を求めるt台の端末装置U[1]，U[2]，…，U[t]からなる端末群は、元選択部、種計算部、種送信部、チャレンジ受信部、中間計算部、応答計算部、応答送信部を備え、以下のように構成する。
（ａ） 整数i = 1，2，…，mのそれぞれについて、m台の端末装置のうち端末装置U[i]において、秘密鍵選択部が、当該乗法群Zp*からt個の元
w[1,i]，w[2,i]，…，w[t,i]
を一様にランダムに秘密鍵として選択し、公開鍵生成部が、選択された秘密鍵から公開鍵
y[1,i] = gw[1,i]，
y[2,i] = gw[2,i]，
…，
y[t,i] = gw[t,i]
を生成し、公開鍵公開部が、m台の端末装置、および、認証装置に、生成された公開鍵
y[1,i]，y[2,i]，…，y[t,i]
を公開する。
（ｂ）端末群において、元選択部が、当該有限体Zpからm+1個の元
c[0]，c[1]，c[2]，…，c[m]
を一様にランダムに選択し、種計算部が、選択された元と、公開された公開鍵と、から、種
r[1] = gc[0] Πi=1m y[1,i]c[i]，
r[2] = gc[0] Πi=1m y[2,i]c[i]，
…，
r[t] = gc[0] Πi=1m y[t,i]c[i]
を計算し、種送信部が、認証装置に、計算された種
r[1]，r[2]，…，r[t]
を送信する。
（ｃ）認証装置において、種受信部が、端末群から送信された種
r[1]，r[2]，…，r[t]
を受信し、チャレンジ選択部が、当該有限体Zpから一様にランダムに１個の元をチャレンジbとして選択し、チャレンジ送信部が、選択されたチャレンジbを、端末群に送信する。
（ｄ）端末群において、チャレンジ受信部が、認証装置から送信されるチャレンジbを受信し、中間計算部が、整数k = 1，2，…，tについて
f[k] = c[0] + Σi=1t w[k,i]c[i] (mod p)
および
f[t+1] = b - (c[t+1] + c[t+2] + … + c[m]) (mod p)
を計算し、応答計算部が、端末群に含まれる端末装置U[1]，U[2]，…，U[t]のそれぞれの秘密鍵
w[1,1]，w[2,1],…，w[t,1]，
w[1,2]，w[2,2],…，w[t,2]，
…，
w[1,t]，w[2,t],…，w[t,t]
により、当該有限体Zpの上で、以下の条件［数３］を満たす応答
d[0]，d[1]，d[2]，…，d[t]，d[t+1]，d[t+2]，…，d[m]
を計算する。
【０００９】
【数３】
【００１０】
そして、応答送信部が、計算された応答
d[0]，d[1]，…，d[m]
を、認証装置に送信する。
（ｅ）認証装置において、応答受信部が、端末群から送信される応答
d[0]，d[1]，…，d[m]
を受信し、認証部が、受信された応答
d[0]，d[1]，…，d[m]
と、公開された公開鍵
y[1,1]，y[2,1]，…，y[t,1]，
y[1,2]，y[2,2]，…，y[t,2]，
…,
y[1,m]，y[2,m]，…，y[t,m]
と、により、
b = Σi=1m d[i] (mod p)
が成立し、かつ、整数j = 1，2，…，tのそれぞれについて、
r[j] = gd[0] Πi=1m y[j,i]d[i]
が成立する場合、当該端末群に対する認証を成功させる。
【００１１】
また、本発明の認証システムは、鍵提供装置をさらに備え、鍵提供装置は、秘密鍵取得部、秘密鍵送信部を備え、m台の端末装置のそれぞれは、秘密鍵受信部をさらに備え、以下のように構成することができる。
（ｆ）鍵提供装置において、秘密鍵取得部が、当該乗法群Zp*からt×m個の元
w[1,1]，w[2,1]，…，w[t,1]，
w[1,2]，w[2,2]，…，w[t,2]，
…,
w[1,m]，w[2,m]，…，w[t,m]
を一様にランダムに取得し、秘密鍵送信部が、整数i = 1，2，…，mのそれぞれについて、m台の端末装置のうち端末装置U[i]に、取得された
w[1,i]，w[2,i]，…，w[t,i]
を個別鍵として送信する。
（ｇ）整数i = 1，2，…，mのそれぞれについて、m台の端末装置のうち端末装置U[i]において、秘密鍵受信部が、鍵提供装置から送信された個別鍵
w[1,i]，w[2,i]，…，w[t,i]
を受信し、秘密鍵選択工程では、受信された個別鍵
w[1,i]，w[2,i]，…，w[t,i]
を当該秘密鍵として選択する。
【００１２】
また、本発明の認証システムにおいて、端末群に含まれるいずれか１台の端末装置へ、端末群に含まれる他の端末装置は、それぞれの秘密鍵を通知し、端末群に含まれる当該１台の端末装置が、元選択部、種計算部、種送信部、中間計算部、応答計算部、応答送信部を備えるように構成することができる。
【００１３】
また、本発明の認証システムにおいて、応答計算部は、当該有限体Zp上での掃き出し法により、
d[0]，d[1]，d[2]，…，d[t]
を求めるように構成することができる。
【００１４】
本発明のその他の観点に係る認証方法は、素数pを位数とする巡回群Gと、Gの生成元gと、pを法とする有限体Zpと、当該有限体Zpに対する乗法群Zp*と、ユーザ総数mと、匿名グループ認証を求める端末群に含まれる端末装置数tと、に対する認証方法であって、認証装置と、m台の端末装置U[1]，U[2]，…，U[m]と、において実行され、認証装置は、種受信部、チャレンジ選択部、チャレンジ送信部、応答受信部、認証部を備え、m台の端末装置U[1]，U[2]，…，U[m]のそれぞれは、秘密鍵選択部、公開鍵生成部、公開鍵公開部を備え、m台の端末装置のうち、匿名グループ認証を求めるt台の端末装置U[1]，U[2]，…，U[t]からなる端末群は、元選択部、種計算部、種送信部、チャレンジ受信部、中間計算部、応答計算部、応答送信部を備え、当該認証方法は、種受信工程、チャレンジ選択工程、チャレンジ送信工程、応答受信工程、認証工程、秘密鍵選択工程、公開鍵生成工程、公開鍵公開工程、元選択工程、種計算工程、種送信工程、チャレンジ受信工程、中間計算工程、応答計算工程、応答送信工程、を備え、以下のように構成する。
（ａ） 整数i = 1，2，…，mのそれぞれについて、m台の端末装置のうち端末装置U[i]において、秘密鍵選択工程では、秘密鍵選択部が、当該乗法群Zp*からt個の元
w[1,i]，w[2,i]，…，w[t,i]
を一様にランダムに秘密鍵として選択し、公開鍵生成工程では、公開鍵生成部が、選択された秘密鍵から公開鍵
y[1,i] = gw[1,i]，
y[2,i] = gw[2,i]，
…，
y[t,i] = gw[t,i]
を生成し、公開鍵公開工程では、公開鍵公開部が、m台の端末装置、および、認証装置に、生成された公開鍵
y[1,i]，y[2,i]，…，y[t,i]
を公開する。
（ｂ）m台の端末装置のうち、匿名グループ認証を求めるt台の端末装置U[1]，U[2]，…，U[t]からなる端末群において、元選択工程では、元選択部が、当該有限体Zpからm+1個の元
c[0]，c[1]，c[2]，…，c[m]
を一様にランダムに選択し、種計算工程では、種計算部が、選択された元と、公開された公開鍵と、から、種
r[1] = gc[0] Πi=1m y[1,i]c[i]，
r[2] = gc[0] Πi=1m y[2,i]c[i]，
…，
r[t] = gc[0] Πi=1m y[t,i]c[i]
を計算し、種送信工程では、種送信部が、認証装置に、計算された種
r[1]，r[2]，…，r[t]
を送信する。
（ｃ）認証装置において、種受信工程では、種受信部が、端末群から送信された種
r[1]，r[2]，…，r[t]
を受信し、チャレンジ選択工程では、チャレンジ選択部が、当該有限体Zpから一様にランダムに１個の元をチャレンジbとして選択し、チャレンジ送信工程では、チャレンジ送信部が、選択されたチャレンジbを、端末群に送信する。
（ｄ）端末群において、チャレンジ受信工程では、チャレンジ受信部が、認証装置から送信されるチャレンジbを受信し、中間計算工程では、中間計算部が、整数k = 1，2，…，tについて
f[k] = c[0] + Σi=1t w[k,i]c[i] (mod p)
および
f[t+1] = b - (c[t+1] + c[t+2] + … + c[m]) (mod p)
を計算し、応答計算工程では、応答計算部が、端末群に含まれる端末装置U[1]，U[2]，…，U[t]のそれぞれの秘密鍵
w[1,1]，w[2,1],…，w[t,1]，
w[1,2]，w[2,2],…，w[t,2]，
…，
w[1,t]，w[2,t],…，w[t,t]
により、当該有限体Zpの上で、［数３］を満たす応答
d[0]，d[1]，d[2]，…，d[t]，d[t+1]，d[t+2]，…，d[m]
を計算し、応答送信工程では、応答送信部が、計算された応答
d[0]，d[1]，…，d[m]
を、認証装置に送信する。
（ｅ）認証装置において、応答受信工程では、応答受信部が、端末群から送信される応答
d[0]，d[1]，…，d[m]
を受信し、認証工程では、認証部が、受信された応答
d[0]，d[1]，…，d[m]
と、公開された公開鍵
y[1,1]，y[2,1]，…，y[t,1]，
y[1,2]，y[2,2]，…，y[t,2]，
…,
y[1,m]，y[2,m]，…，y[t,m]
と、により、
b = Σi=1m d[i] (mod p)
が成立し、かつ、整数j = 1，2，…，tのそれぞれについて、
r[j] = gd[0] Πi=1m y[j,i]d[i]
が成立する場合、当該端末群に対する認証を成功させる。
【００１５】
また、本発明の認証方法において、さらに鍵提供装置において実行され、鍵提供装置は、秘密鍵取得部、秘密鍵送信部を備え、m台の端末装置のそれぞれは、秘密鍵受信部をさらに備え、当該認証方法は、秘密鍵取得工程、秘密鍵送信工程、秘密鍵受信工程をさらに備え、以下のように構成することができる。
（ｆ）鍵提供装置において、秘密鍵取得工程では、秘密鍵取得部が、当該乗法群Zp*からt×m個の元
w[1,1]，w[2,1]，…，w[t,1]，
w[1,2]，w[2,2]，…，w[t,2]，
…,
w[1,m]，w[2,m]，…，w[t,m]
を一様にランダムに取得し、秘密鍵送信工程では、秘密鍵送信部が、整数i = 1，2，…，mのそれぞれについて、m台の端末装置のうち端末装置U[i]に、取得された
w[1,i]，w[2,i]，…，w[t,i]
を個別鍵として送信する。
（ｇ）整数i = 1，2，…，mのそれぞれについて、m台の端末装置のうち端末装置U[i]において、秘密鍵受信工程では、秘密鍵受信部が、鍵提供装置から送信された個別鍵
w[1,i]，w[2,i]，…，w[t,i]
を受信し、秘密鍵選択工程では、受信された個別鍵
w[1,i]，w[2,i]，…，w[t,i]
を当該秘密鍵として選択する。
【００１６】
また、本発明の認証方法において、端末群に含まれるいずれか１台の端末装置へ、端末群に含まれる他の端末装置は、それぞれの秘密鍵を通知し、端末群に含まれる当該１台の端末装置において、元選択工程、種計算工程、種送信工程、中間計算工程、応答計算工程、応答送信工程が実行されるように構成することができる。
【００１７】
また、本発明の認証方法において、応答計算工程では、当該有限体Zp上での掃き出し法により、
d[0]，d[1]，d[2]，…，d[t]
を求めるように構成することができる。
【００１８】
本発明のその他の観点に係るプログラムは、コンピュータを、上記の認証システムの認証装置、端末装置、端末群の各部として機能させるように構成する。
【００１９】
特に、(m+1)台のコンピュータのうち、第1から第mまでのコンピュータのそれぞれを、請求項１に記載の認証システムのm台の端末装置のいずれかとして機能させ、第1から第tまでのコンピュータ群を、当該認証システムの端末群として機能させ、第(m+1)のコンピュータを、当該認証システムの認証装置として機能させるように構成することができる。
【００２０】
なお、上記のプログラムは、コンピュータ読取可能な情報記録媒体（コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、または、半導体メモリを含む。）に記録することができる。
【００２１】
そして、上記の情報記録媒体は、コンピュータとは独立して配布、販売することができるほか、インターネット等のコンピュータ通信網を介して上記のプログラムそのものを配布、販売することができる。
【発明の効果】
【００２２】
本発明によれば、あるグループ内のサブグループにおいて、通信の複雑さを抑制して効率良く認証を行うための認証システム、認証方法、ならびに、これらをコンピュータ上にて実現するためのプログラムを提供することができる。
【発明を実施するための最良の形態】
【００２３】
以下に本発明の実施形態を説明する。なお、以下にあげる実施形態は、説明のためのものであり、本発明の範囲を制限するものではない。したがって、当業者であれば、これらの各要素または全要素を、これと均等なものに置換した実施形態を採用することが可能であるが、これらの実施形態も、本発明の範囲に含まれる。
【実施例１】
【００２４】
図１は、本実施形態に係る認証システムの概要構成を示す説明図である。以下、本図を参照して説明する。
【００２５】
本図に示すように、認証システム１０１は、認証の対象となる複数の端末装置１１１と、認証を行う認証装置１２１と、から構成され、インターネットなどのコンピュータ通信網１４１を介して、相互に通信可能に接続されている。
【００２６】
ここで、本実施形態は、m台の端末装置１１１のうち、t台の端末装置１１１からなるグループを認証するものであり、当該端末群１３１が、全体として、t台の端末装置１１１からなることを、それぞれが持つ鍵を参照して、認証装置１２１が認証するものである。
【００２７】
この際に、当該端末群１３１に含まれる各端末装置１１１のそれぞれと、認証装置１２１とが、個別に通信をしてしまうと、どの端末装置１１１がどの鍵を持っているか、について、認証装置１２１にわかってしまう。
【００２８】
しかしながら、本実施形態においては、端末装置１１１からなる端末群１３１が全体として、典型的には、いずれかの１台の端末装置１１１を代表とし、端末群１３１に含まれる端末装置１１１と鍵との対応関係は秘匿したままで、認証装置１２１と通信する。
【００２９】
このように、グループ全体は特定の端末装置１１１からなることが判明するが、グループ内のいずれの端末装置１１１かを個別に判定しない手法が、匿名グループ認証である。
【００３０】
また、m台の中のt台の端末装置１１１であることがわかれば認証が成功することとなる。本実施形態では公開鍵システムを利用するが、t台の端末装置１１１の公開鍵だけを参照するのではなく、m台の端末装置１１１の公開鍵全部を参照する。
【００３１】
したがって、特定のt台であることが認証されるのではない。すなわち、ある公開鍵を持つ端末装置１１１が端末群１３１に含まれるか否かは、匿名グループ認証の際には判明しない。
【００３２】
本実施形態では、以下の概念を、以下の記号により表記する。
（１）素数pを位数とする巡回群G。
（２）Gの生成元g。
（３）pを法とする有限体Zp。
（４）当該有限体Zpに対する乗法群Zp*。
（５）ユーザ総数m。
（６）匿名グループ認証を求める端末群１３１に含まれる端末装置数t。
【００３３】
これらの情報は、U[1]，U[2]，…，U[m]からなるm台の端末装置１１１、および、認証装置１２１において共有される。
【００３４】
各端末装置１１１や認証装置１２１は、コンピュータ通信網に接続された情報処理装置によって実現されるのが典型的である。一般的な情報処理装置は、ＣＰＵ（Central Processing Unit）の制御の下、ＲＡＭ（Random Access Memory）を一時的な記憶領域とし、ハードディスク等を一時的もしくは不揮発な記憶領域とし、ＮＩＣ（Network Interface Card）経由でインターネット等のコンピュータ通信網に接続され、他の情報処理装置と通信することができる。情報処理装置において、端末装置１１１用のプログラムを実行すれば端末装置１１１として機能し、認証装置１２１用のプログラムを実行すれば認証装置１２１として機能することとなる。
【００３５】
図２は、端末装置１１１の概要構成を示す模式図である。以下、本図を参照して説明する。
【００３６】
まず、端末装置１１１のそれぞれは、秘密鍵選択部２０１、公開鍵生成部２０２、公開鍵公開部２０３を備える。
【００３７】
また、匿名グループ認証を求めるt台の端末装置１１１（U[1]，U[2]，…，U[t]）は、端末群１３１を構成する。ここで、端末群１３１（U[1]，U[2]，…，U[t]）は、端末装置１１１の全体U[1]，U[2]，…，U[m]に含まれるサブグループであり、その添字については、上記のように設定しても一般性を失わない。
【００３８】
さて、当該端末群１３１は、元選択部２０４、種計算部２０５、種送信部２０６、チャレンジ受信部２０７、中間計算部２０８、応答計算部２０９、応答送信部２１０を備える。
【００３９】
まず、認証を行うための準備として、各端末装置１１１は、鍵処理を行う。図３は、鍵処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【００４０】
U[1]，U[2]，…，U[m]の端末装置１１１のうち、i番目の端末装置１１１（U[i]）において、秘密鍵選択部２０１が、当該乗法群Zp*からt個の元
w[1,i]，w[2,i]，…，w[t,i]
を秘密鍵（W[i]）として選択する（ステップＳ３０１）。秘密鍵の選択は、他の端末装置１１１とは独立に秘匿して、また、一様にランダムに行うのが望ましい。
【００４１】
ついで、公開鍵生成部２０２が、選択された秘密鍵から
y[1,i] = gw[1,i]，
y[2,i] = gw[2,i]，
…，
y[t,i] = gw[t,i]
を公開鍵（Y[i]）として生成する（ステップＳ３０２）。
【００４２】
さらに、公開鍵公開部２０３が、m台の端末装置１１１、および、認証装置１２１に、生成された公開鍵
Y[i] = y[1,i]，y[2,i]，…，y[t,i]
を公開して（ステップＳ３０３）、本処理を終了する。
【００４３】
公開鍵の公開の手法については、種々の手法を採用することができる。たとえば、端末装置１１１の識別符号（たとえば、ユーザ名、マシン名、ＩＰアドレス、ＭＡＣアドレス等を利用することができる。）と、公開鍵と、を対応付けて記憶する鍵サーバに公開鍵を登録する。そして、鍵サーバに識別符号を指定した問い合わせをすると、これに対応付けられる公開鍵を指定した回答が得られる、というものである。認証装置１２１をこの鍵サーバとして利用しても良い。
【００４４】
したがって、情報処理装置のＣＰＵは、ＲＡＭやＮＩＣ等と共働して、秘密鍵選択部２０１、公開鍵生成部２０２、公開鍵公開部２０３として機能する。
【００４５】
図４は、認証装置１２１の概要構成を示す模式図である。以下、本図を参照して説明する。
【００４６】
本図に示すように、認証装置１２１は、種受信部４０１、チャレンジ選択部４０２、チャレンジ送信部４０３、応答受信部４０４、認証部４０５を備える。
【００４７】
図５は、m台の端末装置１１１（U[1]，U[2]，…，U[m]）のうち、匿名グループ認証を求めるt台の端末装置１１１（U[1]，U[2]，…，U[t]）からなる端末群１３１にて実行される被認証処理の制御の流れを示すフローチャートである。
【００４８】
一方、図６は、認証装置１２１にて実行される認証処理の制御の流れを示すフローチャートである。以下、これらの図を参照して説明する。
【００４９】
まず、端末群１３１側の被認証処理において、元選択部２０４が、当該有限体Zpからm+1個の元
c[0]，c[1]，c[2]，…，c[m]
を一様にランダムに選択する（ステップＳ５０１）。以下、これらの元をまとめてCと表記する。
【００５０】
ついで、種計算部２０５が、選択された元と、公開された公開鍵と、から、種
r[1] = gc[0] Πi=1m y[1,i]c[i]，
r[2] = gc[0] Πi=1m y[2,i]c[i]，
…，
r[t] = gc[0] Πi=1m y[t,i]c[i]
を計算する（ステップＳ５０２）。以下、これらの種をまとめてRと表記する。
【００５１】
さらに、種送信部２０６が、認証装置１２１に、計算された種
r[1]，r[2]，…，r[t]
を送信する（ステップＳ５０３）。
【００５２】
これらの計算には、端末装置１１１（U[i]）の秘密鍵w[1,i]，w[2,i]，…，w[t,i]を用いる必要はない。
【００５３】
したがって、ＣＰＵが、ＲＡＭやＮＩＣ等と共働して、元選択部２０４、種計算部２０５、種送信部２０６として機能する。
【００５４】
すると、認証装置１２１側の認証処理において、種受信部４０１が、端末群１３１から送信された種
r[1]，r[2]，…，r[t]
を受信する（ステップＳ５０４）。
【００５５】
次に、チャレンジ選択部４０２が、当該有限体Zpから一様にランダムに１個の元をチャレンジbとして選択する（ステップＳ５０５）。そして、チャレンジ送信部４０３が、選択されたチャレンジbを、端末群１３１に送信する（ステップＳ５０６）。
【００５６】
したがって、ＣＰＵは、ＲＡＭやＮＩＣ等と共働して、種受信部４０１、チャレンジ選択部４０２、チャレンジ送信部４０３として機能する。
【００５７】
すると、端末群１３１側の被認証処理において、チャレンジ受信部２０７が、認証装置１２１から送信されるチャレンジbを受信する（ステップＳ５０７）。
【００５８】
ついで、中間計算部２０８が、整数k = 1，2，…，tについて
f[k] = c[0] + Σi=1t w[k,i]c[i] (mod p)
を計算し、さらに、
f[t+1] = b - (c[t+1] + c[t+2] + … + c[m]) (mod p)
を計算する（ステップＳ５０８）。これらをまとめて中間値Fと呼ぶ。
【００５９】
応答計算部２０９が、端末群１３１に含まれる端末装置１１１（U[1]，U[2]，…，U[t]）のそれぞれの秘密鍵
w[1,1]，w[2,1],…，w[t,1]，
w[1,2]，w[2,2],…，w[t,2]，
…，
w[1,t]，w[2,t],…，w[t,t]
により、当該有限体Zpの上で、［数３］を満たす応答
d[0]，d[1]，d[2]，…，d[t]，d[t+1]，d[t+2]，…，d[m]
を計算する（ステップＳ５０９）。これらをまとめて応答Dと呼ぶ。
【００６０】
ここで、［数３］における行列方程式は、有限体Zpにおける加減乗除を用いたものであり、行列方程式を解くにあたっては、当該有限体Zp上での掃き出し法により、
d[0]，d[1]，d[2]，…，d[t]
を求めるのが典型的である。
【００６１】
また、この計算においては、端末装置１１１（U[1]，U[2]，…，U[t]）のそれぞれの秘密鍵
w[1,1]，w[2,1],…，w[t,1]，
w[1,2]，w[2,2],…，w[t,2]，
…，
w[1,t]，w[2,t],…，w[t,t]
を参照する必要があるため、端末群１３１の中の代表となる端末装置１１１に、それぞれの端末装置１１１の秘密鍵を通知する等の処理を行うこととなる。この情報のやり取りの態様については後述する。
【００６２】
ついで、応答送信部２１０が、計算された応答
d[0]，d[1]，…，d[m]
を、認証装置１２１に送信する（ステップＳ５１０）。
【００６３】
したがって、ＣＰＵはＲＡＭ、ＮＩＣ等と共働して、チャレンジ受信部２０７、中間計算部２０８、応答計算部２０９、応答送信部２１０として機能する。
【００６４】
さて、認証装置１２１側の認証処理では、応答受信部４０４が、端末群１３１から送信される応答
d[0]，d[1]，…，d[m]
を受信する（ステップＳ５１１）。
【００６５】
認証工程では、認証部４０５が、以下の認証条件が満たされるか否かを判定する（ステップＳ５１２）。
【００６６】
すなわち、認証条件とは、「受信された応答
d[0]，d[1]，…，d[m]
と、公開された公開鍵
y[1,1]，y[2,1]，…，y[t,1]，
y[1,2]，y[2,2]，…，y[t,2]，
…,
y[1,m]，y[2,m]，…，y[t,m]
と、により、
b = Σi=1m d[i] (mod p)
が成立し、かつ、整数j = 1，2，…，tのすべてについて、
r[j] = gd[0] Πi=1m y[j,i]d[i]
成立する」をいう。
【００６７】
認証条件が成立すれば（ステップＳ５１２；Ｙｅｓ）、当該端末群１３１に対する認証を成功させ（ステップＳ５１３）、いずれかもしくはすべてについて成立しなければ（ステップＳ５１２；Ｎｏ）、当該端末群１３１に対する認証を失敗させて（ステップＳ５１４）、本処理を終了する。
【００６８】
ここで、使用する公開鍵は、認証を求める端末群１３１に含まれるt台の端末装置１１１のみならず、m台の端末装置１１１のものを平等に使用している。
【００６９】
したがって、認証が成功したとしても、m個の公開鍵からいずれか１つの公開鍵が選ばれたときに、「当該選ばれた公開鍵を持つ端末装置１１１は、端末群１３１をなすt台の端末装置１１１のいずれかである」のか、それとも、「当該選ばれた公開鍵を持つ端末装置１１１は、端末群１３１をなすt台の端末装置１１１のいずれでもない」のかは、認証装置１２１側にはわからない。
【００７０】
一方、端末群１３１側では、t台の端末装置１１１の秘密鍵をまとめて計算処理する必要があるため、この計算処理を行う機器（典型的には代表となっている端末装置１１１である。）に秘密鍵が知得されてしまう。
【００７１】
したがって、公開鍵と秘密鍵のペアは、t台の端末群１３１の認証がされるごとに、m台の端末装置１１１全体で一斉に新規に生成し直すことが望ましい。
【００７２】
図７は、本実施形態において情報がやりとりされる様子を示す模式図である。以下、本図を参照して説明する。
【００７３】
m台の端末装置１１１のそれぞれ（U[i]）には、秘密鍵（W[i] = (w[1,i]，w[2,i]，…，w[t,i])）と公開鍵（Y[i] = (y[1,i]，y[2,i]，…，y[t,i])）の対が割り当てられている。
【００７４】
t台の端末装置１１１からなる端末群１３１の代表７０１は、一様にランダムに選択した元（C = (c[0]，c[1]，…，c[m])）と公開鍵全体（Y[1]，Y[2]，…，Y[m]）を参照して種R = (r[1]，r[2]，…，r[t])を生成し、認証装置１２１に送信する。
【００７５】
認証装置１２１は、一様にランダムに選択したチャレンジ（b）を端末群１３１に送信する。
【００７６】
端末群１３１では、端末群１３１に含まれる端末装置１１１の秘密鍵（W[1]，W[2]，…，W[t]）を参照して（共有し、もしくは、代表７０１となる端末に集中させるのが典型的である。）、応答（D = (d[0]，d[1]，…，d[m])）を求め、これを認証装置１２１に送信する。
【００７７】
認証装置１２１では、チャレンジ（b）と、受信した応答（D = (d[0]，d[1]，…，d[m])）と、公開鍵全体（Y[1]，Y[2]，…，Y[m]）と、を参照して、認証が成功するか否かを判定する。
【実施例２】
【００７８】
上記実施形態では、端末装置１１１それぞれが秘密鍵を選択することとしていたが、本実施形態においては、鍵提供装置により、秘密鍵を生成する手法を採用する。
【００７９】
図８は、鍵提供装置を含むシステムの一部の構成を示す模式図である。以下、本図を参照して説明する。
【００８０】
すなわち、鍵提供装置８０１は、秘密鍵取得部８０２、秘密鍵送信部８０３を有し、対応する処理を実行するため、各端末装置１１１は、秘密鍵受信部８０４をさらに有する。
【００８１】
すなわち、鍵提供装置８０１では、秘密鍵取得部８０２が、当該乗法群Zp*からt×m個の元
w[1,1]，w[2,1]，…，w[t,1]，
w[1,2]，w[2,2]，…，w[t,2]，
…,
w[1,m]，w[2,m]，…，w[t,m]
を一様にランダムに取得する。
【００８２】
上記実施形態では、i番目の端末装置１１１が秘密鍵（W[i] = (w[1,i]，w[2,i]，…，w[t,i])）を個別に生成していたが、本実施形態では、秘密鍵取得部８０２が、まとめて秘密鍵（W[1]，W[2]，…，W[m]）を生成することになる。
【００８３】
そして、秘密鍵送信部８０３が、整数i = 1，2，…，mのそれぞれについて、m台の端末装置１１１のうち端末装置１１１（U[i]）に、取得された
W[i] = (w[1,i]，w[2,i]，…，w[t,i])
を個別鍵として送信する。
【００８４】
一方、m台の端末装置１１１のうちi番目の端末装置１１１（U[i]）において、秘密鍵受信部８０４が、鍵提供装置８０１から送信された個別鍵
W[i] = (w[1,i]，w[2,i]，…，w[t,i])
を受信する。
【００８５】
そして、秘密鍵選択部２０１は、受信された個別鍵
W[i] = (w[1,i]，w[2,i]，…，w[t,i])
を当該秘密鍵として選択する。
【産業上の利用可能性】
【００８６】
本発明によれば、あるグループ内のサブグループにおいて、通信の複雑さを抑制して効率良く認証を行うための認証システム、認証方法、ならびに、これらをコンピュータ上にて実現するためのプログラムを提供することができる。
【図面の簡単な説明】
【００８７】
【図１】本実施形態に係る認証システムの概要構成を示す説明図である。
【図２】本実施形態に係る端末装置の概要構成を示す模式図である。
【図３】本実施形態に係る端末装置にて実行される鍵処理の制御の流れを示すフローチャートである。
【図４】本実施形態に係る認証装置の概要構成を示す模式図である。
【図５】匿名グループ認証を求めるt台の端末装置からなる端末群にて実行される被認証処理の制御の流れを示すフローチャートである。
【図６】認証装置にて実行される認証処理の制御の流れを示すフローチャートである。
【図７】本実施形態において情報がやりとりされる様子を示す模式図である。
【図８】鍵提供装置を含むシステムの一部の構成を示す模式図である。
【符号の説明】
【００８８】
１０１ 認証システム
１１１ 端末装置
１２１ 認証装置
１３１ 端末群
２０１ 秘密鍵選択部
２０２ 公開鍵生成部
２０３ 公開鍵公開部
２０４ 元選択部
２０５ 種計算部
２０６ 種送信部
２０７ チャレンジ受信部
２０８ 中間計算部
２０９ 応答計算部
２１０ 応答送信部
４０１ 種受信部
４０２ チャレンジ選択部
４０３ チャレンジ送信部
４０４ 応答受信部
４０５ 認証部
７０１ 代表
８０１ 鍵提供装置
８０２ 秘密鍵取得部
８０３ 秘密鍵送信部
８０４ 秘密鍵受信部
【技術分野】
【０００１】
本発明は、あるグループ内のサブグループにおいて、通信の複雑さを抑制して効率良く認証を行うための認証システム、認証方法、ならびに、これらをコンピュータ上にて実現するためのプログラムに関する。
【背景技術】
【０００２】
従来、認証技術の分野では、m人のユーザのグループのうち、少なくともt人のサブグループのユーザがいるときに、サーバと匿名でセッション鍵を共有するための手法が提案されている。このような手法を、t-out-of-m手法という。このような技術については、以下の文献に開示されている。
【非特許文献１】Duong Quang Viet，Akihiro Yamamura and Hidema Tanaka, Anonymous Password-Based Authenticated Key Exchange, Book Progress in Cryptology - INDOCRYPT 2005, Lecture Notes in Computer Science, Springer Berlin / Heidelberg, Volume 3797/2005, ISBN 978-3-540-30805-8, p.244-p.257, ２００５年
【０００３】
[特許文献１]では、匿名でパスワードに基づいた認証鍵の交換手法、特に、あるグループ内のユーザがサーバと匿名でセッション鍵を確立する手法について提案している。本手法では、正当なグループ内のユーザとサーバは、人が覚えやすいパスワードを共有しており、互いに認証を行うことができ、辞書攻撃に対して安全である。
【０００４】
従来、このような手法における通信の複雑さ（通信量に相当する）は、Θ(mn log m)のオーダーであった。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、t-out-of-m手法においては、通信の複雑さを抑制して、通信量を減らしたい、との要望は大きい。
【０００６】
本発明は、このような課題を解決するもので、あるグループ内のサブグループにおいて、通信の複雑さを抑制して効率良く認証を行うための認証システム、認証方法、ならびに、これらをコンピュータ上にて実現するためのプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記の課題を解決するため、本発明の原理にしたがい、以下の発明を開示する。
【０００８】
本発明の第１の観点に係る認証システムは、素数pを位数とする巡回群Gと、Gの生成元gと、pを法とする有限体Zpと、当該有限体Zpに対する乗法群Zp*と、ユーザ総数mと、匿名グループ認証を求める端末群に含まれる端末装置数tと、に対する認証システムであって、認証装置と、m台の端末装置U[1]，U[2]，…，U[m]と、を備え、認証装置は、種受信部、チャレンジ選択部、チャレンジ送信部、応答受信部、認証部を備え、m台の端末装置U[1]，U[2]，…，U[m]のそれぞれは、秘密鍵選択部、公開鍵生成部、公開鍵公開部を備え、m台の端末装置のうち、匿名グループ認証を求めるt台の端末装置U[1]，U[2]，…，U[t]からなる端末群は、元選択部、種計算部、種送信部、チャレンジ受信部、中間計算部、応答計算部、応答送信部を備え、以下のように構成する。
（ａ） 整数i = 1，2，…，mのそれぞれについて、m台の端末装置のうち端末装置U[i]において、秘密鍵選択部が、当該乗法群Zp*からt個の元
w[1,i]，w[2,i]，…，w[t,i]
を一様にランダムに秘密鍵として選択し、公開鍵生成部が、選択された秘密鍵から公開鍵
y[1,i] = gw[1,i]，
y[2,i] = gw[2,i]，
…，
y[t,i] = gw[t,i]
を生成し、公開鍵公開部が、m台の端末装置、および、認証装置に、生成された公開鍵
y[1,i]，y[2,i]，…，y[t,i]
を公開する。
（ｂ）端末群において、元選択部が、当該有限体Zpからm+1個の元
c[0]，c[1]，c[2]，…，c[m]
を一様にランダムに選択し、種計算部が、選択された元と、公開された公開鍵と、から、種
r[1] = gc[0] Πi=1m y[1,i]c[i]，
r[2] = gc[0] Πi=1m y[2,i]c[i]，
…，
r[t] = gc[0] Πi=1m y[t,i]c[i]
を計算し、種送信部が、認証装置に、計算された種
r[1]，r[2]，…，r[t]
を送信する。
（ｃ）認証装置において、種受信部が、端末群から送信された種
r[1]，r[2]，…，r[t]
を受信し、チャレンジ選択部が、当該有限体Zpから一様にランダムに１個の元をチャレンジbとして選択し、チャレンジ送信部が、選択されたチャレンジbを、端末群に送信する。
（ｄ）端末群において、チャレンジ受信部が、認証装置から送信されるチャレンジbを受信し、中間計算部が、整数k = 1，2，…，tについて
f[k] = c[0] + Σi=1t w[k,i]c[i] (mod p)
および
f[t+1] = b - (c[t+1] + c[t+2] + … + c[m]) (mod p)
を計算し、応答計算部が、端末群に含まれる端末装置U[1]，U[2]，…，U[t]のそれぞれの秘密鍵
w[1,1]，w[2,1],…，w[t,1]，
w[1,2]，w[2,2],…，w[t,2]，
…，
w[1,t]，w[2,t],…，w[t,t]
により、当該有限体Zpの上で、以下の条件［数３］を満たす応答
d[0]，d[1]，d[2]，…，d[t]，d[t+1]，d[t+2]，…，d[m]
を計算する。
【０００９】
【数３】
【００１０】
そして、応答送信部が、計算された応答
d[0]，d[1]，…，d[m]
を、認証装置に送信する。
（ｅ）認証装置において、応答受信部が、端末群から送信される応答
d[0]，d[1]，…，d[m]
を受信し、認証部が、受信された応答
d[0]，d[1]，…，d[m]
と、公開された公開鍵
y[1,1]，y[2,1]，…，y[t,1]，
y[1,2]，y[2,2]，…，y[t,2]，
…,
y[1,m]，y[2,m]，…，y[t,m]
と、により、
b = Σi=1m d[i] (mod p)
が成立し、かつ、整数j = 1，2，…，tのそれぞれについて、
r[j] = gd[0] Πi=1m y[j,i]d[i]
が成立する場合、当該端末群に対する認証を成功させる。
【００１１】
また、本発明の認証システムは、鍵提供装置をさらに備え、鍵提供装置は、秘密鍵取得部、秘密鍵送信部を備え、m台の端末装置のそれぞれは、秘密鍵受信部をさらに備え、以下のように構成することができる。
（ｆ）鍵提供装置において、秘密鍵取得部が、当該乗法群Zp*からt×m個の元
w[1,1]，w[2,1]，…，w[t,1]，
w[1,2]，w[2,2]，…，w[t,2]，
…,
w[1,m]，w[2,m]，…，w[t,m]
を一様にランダムに取得し、秘密鍵送信部が、整数i = 1，2，…，mのそれぞれについて、m台の端末装置のうち端末装置U[i]に、取得された
w[1,i]，w[2,i]，…，w[t,i]
を個別鍵として送信する。
（ｇ）整数i = 1，2，…，mのそれぞれについて、m台の端末装置のうち端末装置U[i]において、秘密鍵受信部が、鍵提供装置から送信された個別鍵
w[1,i]，w[2,i]，…，w[t,i]
を受信し、秘密鍵選択工程では、受信された個別鍵
w[1,i]，w[2,i]，…，w[t,i]
を当該秘密鍵として選択する。
【００１２】
また、本発明の認証システムにおいて、端末群に含まれるいずれか１台の端末装置へ、端末群に含まれる他の端末装置は、それぞれの秘密鍵を通知し、端末群に含まれる当該１台の端末装置が、元選択部、種計算部、種送信部、中間計算部、応答計算部、応答送信部を備えるように構成することができる。
【００１３】
また、本発明の認証システムにおいて、応答計算部は、当該有限体Zp上での掃き出し法により、
d[0]，d[1]，d[2]，…，d[t]
を求めるように構成することができる。
【００１４】
本発明のその他の観点に係る認証方法は、素数pを位数とする巡回群Gと、Gの生成元gと、pを法とする有限体Zpと、当該有限体Zpに対する乗法群Zp*と、ユーザ総数mと、匿名グループ認証を求める端末群に含まれる端末装置数tと、に対する認証方法であって、認証装置と、m台の端末装置U[1]，U[2]，…，U[m]と、において実行され、認証装置は、種受信部、チャレンジ選択部、チャレンジ送信部、応答受信部、認証部を備え、m台の端末装置U[1]，U[2]，…，U[m]のそれぞれは、秘密鍵選択部、公開鍵生成部、公開鍵公開部を備え、m台の端末装置のうち、匿名グループ認証を求めるt台の端末装置U[1]，U[2]，…，U[t]からなる端末群は、元選択部、種計算部、種送信部、チャレンジ受信部、中間計算部、応答計算部、応答送信部を備え、当該認証方法は、種受信工程、チャレンジ選択工程、チャレンジ送信工程、応答受信工程、認証工程、秘密鍵選択工程、公開鍵生成工程、公開鍵公開工程、元選択工程、種計算工程、種送信工程、チャレンジ受信工程、中間計算工程、応答計算工程、応答送信工程、を備え、以下のように構成する。
（ａ） 整数i = 1，2，…，mのそれぞれについて、m台の端末装置のうち端末装置U[i]において、秘密鍵選択工程では、秘密鍵選択部が、当該乗法群Zp*からt個の元
w[1,i]，w[2,i]，…，w[t,i]
を一様にランダムに秘密鍵として選択し、公開鍵生成工程では、公開鍵生成部が、選択された秘密鍵から公開鍵
y[1,i] = gw[1,i]，
y[2,i] = gw[2,i]，
…，
y[t,i] = gw[t,i]
を生成し、公開鍵公開工程では、公開鍵公開部が、m台の端末装置、および、認証装置に、生成された公開鍵
y[1,i]，y[2,i]，…，y[t,i]
を公開する。
（ｂ）m台の端末装置のうち、匿名グループ認証を求めるt台の端末装置U[1]，U[2]，…，U[t]からなる端末群において、元選択工程では、元選択部が、当該有限体Zpからm+1個の元
c[0]，c[1]，c[2]，…，c[m]
を一様にランダムに選択し、種計算工程では、種計算部が、選択された元と、公開された公開鍵と、から、種
r[1] = gc[0] Πi=1m y[1,i]c[i]，
r[2] = gc[0] Πi=1m y[2,i]c[i]，
…，
r[t] = gc[0] Πi=1m y[t,i]c[i]
を計算し、種送信工程では、種送信部が、認証装置に、計算された種
r[1]，r[2]，…，r[t]
を送信する。
（ｃ）認証装置において、種受信工程では、種受信部が、端末群から送信された種
r[1]，r[2]，…，r[t]
を受信し、チャレンジ選択工程では、チャレンジ選択部が、当該有限体Zpから一様にランダムに１個の元をチャレンジbとして選択し、チャレンジ送信工程では、チャレンジ送信部が、選択されたチャレンジbを、端末群に送信する。
（ｄ）端末群において、チャレンジ受信工程では、チャレンジ受信部が、認証装置から送信されるチャレンジbを受信し、中間計算工程では、中間計算部が、整数k = 1，2，…，tについて
f[k] = c[0] + Σi=1t w[k,i]c[i] (mod p)
および
f[t+1] = b - (c[t+1] + c[t+2] + … + c[m]) (mod p)
を計算し、応答計算工程では、応答計算部が、端末群に含まれる端末装置U[1]，U[2]，…，U[t]のそれぞれの秘密鍵
w[1,1]，w[2,1],…，w[t,1]，
w[1,2]，w[2,2],…，w[t,2]，
…，
w[1,t]，w[2,t],…，w[t,t]
により、当該有限体Zpの上で、［数３］を満たす応答
d[0]，d[1]，d[2]，…，d[t]，d[t+1]，d[t+2]，…，d[m]
を計算し、応答送信工程では、応答送信部が、計算された応答
d[0]，d[1]，…，d[m]
を、認証装置に送信する。
（ｅ）認証装置において、応答受信工程では、応答受信部が、端末群から送信される応答
d[0]，d[1]，…，d[m]
を受信し、認証工程では、認証部が、受信された応答
d[0]，d[1]，…，d[m]
と、公開された公開鍵
y[1,1]，y[2,1]，…，y[t,1]，
y[1,2]，y[2,2]，…，y[t,2]，
…,
y[1,m]，y[2,m]，…，y[t,m]
と、により、
b = Σi=1m d[i] (mod p)
が成立し、かつ、整数j = 1，2，…，tのそれぞれについて、
r[j] = gd[0] Πi=1m y[j,i]d[i]
が成立する場合、当該端末群に対する認証を成功させる。
【００１５】
また、本発明の認証方法において、さらに鍵提供装置において実行され、鍵提供装置は、秘密鍵取得部、秘密鍵送信部を備え、m台の端末装置のそれぞれは、秘密鍵受信部をさらに備え、当該認証方法は、秘密鍵取得工程、秘密鍵送信工程、秘密鍵受信工程をさらに備え、以下のように構成することができる。
（ｆ）鍵提供装置において、秘密鍵取得工程では、秘密鍵取得部が、当該乗法群Zp*からt×m個の元
w[1,1]，w[2,1]，…，w[t,1]，
w[1,2]，w[2,2]，…，w[t,2]，
…,
w[1,m]，w[2,m]，…，w[t,m]
を一様にランダムに取得し、秘密鍵送信工程では、秘密鍵送信部が、整数i = 1，2，…，mのそれぞれについて、m台の端末装置のうち端末装置U[i]に、取得された
w[1,i]，w[2,i]，…，w[t,i]
を個別鍵として送信する。
（ｇ）整数i = 1，2，…，mのそれぞれについて、m台の端末装置のうち端末装置U[i]において、秘密鍵受信工程では、秘密鍵受信部が、鍵提供装置から送信された個別鍵
w[1,i]，w[2,i]，…，w[t,i]
を受信し、秘密鍵選択工程では、受信された個別鍵
w[1,i]，w[2,i]，…，w[t,i]
を当該秘密鍵として選択する。
【００１６】
また、本発明の認証方法において、端末群に含まれるいずれか１台の端末装置へ、端末群に含まれる他の端末装置は、それぞれの秘密鍵を通知し、端末群に含まれる当該１台の端末装置において、元選択工程、種計算工程、種送信工程、中間計算工程、応答計算工程、応答送信工程が実行されるように構成することができる。
【００１７】
また、本発明の認証方法において、応答計算工程では、当該有限体Zp上での掃き出し法により、
d[0]，d[1]，d[2]，…，d[t]
を求めるように構成することができる。
【００１８】
本発明のその他の観点に係るプログラムは、コンピュータを、上記の認証システムの認証装置、端末装置、端末群の各部として機能させるように構成する。
【００１９】
特に、(m+1)台のコンピュータのうち、第1から第mまでのコンピュータのそれぞれを、請求項１に記載の認証システムのm台の端末装置のいずれかとして機能させ、第1から第tまでのコンピュータ群を、当該認証システムの端末群として機能させ、第(m+1)のコンピュータを、当該認証システムの認証装置として機能させるように構成することができる。
【００２０】
なお、上記のプログラムは、コンピュータ読取可能な情報記録媒体（コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、または、半導体メモリを含む。）に記録することができる。
【００２１】
そして、上記の情報記録媒体は、コンピュータとは独立して配布、販売することができるほか、インターネット等のコンピュータ通信網を介して上記のプログラムそのものを配布、販売することができる。
【発明の効果】
【００２２】
本発明によれば、あるグループ内のサブグループにおいて、通信の複雑さを抑制して効率良く認証を行うための認証システム、認証方法、ならびに、これらをコンピュータ上にて実現するためのプログラムを提供することができる。
【発明を実施するための最良の形態】
【００２３】
以下に本発明の実施形態を説明する。なお、以下にあげる実施形態は、説明のためのものであり、本発明の範囲を制限するものではない。したがって、当業者であれば、これらの各要素または全要素を、これと均等なものに置換した実施形態を採用することが可能であるが、これらの実施形態も、本発明の範囲に含まれる。
【実施例１】
【００２４】
図１は、本実施形態に係る認証システムの概要構成を示す説明図である。以下、本図を参照して説明する。
【００２５】
本図に示すように、認証システム１０１は、認証の対象となる複数の端末装置１１１と、認証を行う認証装置１２１と、から構成され、インターネットなどのコンピュータ通信網１４１を介して、相互に通信可能に接続されている。
【００２６】
ここで、本実施形態は、m台の端末装置１１１のうち、t台の端末装置１１１からなるグループを認証するものであり、当該端末群１３１が、全体として、t台の端末装置１１１からなることを、それぞれが持つ鍵を参照して、認証装置１２１が認証するものである。
【００２７】
この際に、当該端末群１３１に含まれる各端末装置１１１のそれぞれと、認証装置１２１とが、個別に通信をしてしまうと、どの端末装置１１１がどの鍵を持っているか、について、認証装置１２１にわかってしまう。
【００２８】
しかしながら、本実施形態においては、端末装置１１１からなる端末群１３１が全体として、典型的には、いずれかの１台の端末装置１１１を代表とし、端末群１３１に含まれる端末装置１１１と鍵との対応関係は秘匿したままで、認証装置１２１と通信する。
【００２９】
このように、グループ全体は特定の端末装置１１１からなることが判明するが、グループ内のいずれの端末装置１１１かを個別に判定しない手法が、匿名グループ認証である。
【００３０】
また、m台の中のt台の端末装置１１１であることがわかれば認証が成功することとなる。本実施形態では公開鍵システムを利用するが、t台の端末装置１１１の公開鍵だけを参照するのではなく、m台の端末装置１１１の公開鍵全部を参照する。
【００３１】
したがって、特定のt台であることが認証されるのではない。すなわち、ある公開鍵を持つ端末装置１１１が端末群１３１に含まれるか否かは、匿名グループ認証の際には判明しない。
【００３２】
本実施形態では、以下の概念を、以下の記号により表記する。
（１）素数pを位数とする巡回群G。
（２）Gの生成元g。
（３）pを法とする有限体Zp。
（４）当該有限体Zpに対する乗法群Zp*。
（５）ユーザ総数m。
（６）匿名グループ認証を求める端末群１３１に含まれる端末装置数t。
【００３３】
これらの情報は、U[1]，U[2]，…，U[m]からなるm台の端末装置１１１、および、認証装置１２１において共有される。
【００３４】
各端末装置１１１や認証装置１２１は、コンピュータ通信網に接続された情報処理装置によって実現されるのが典型的である。一般的な情報処理装置は、ＣＰＵ（Central Processing Unit）の制御の下、ＲＡＭ（Random Access Memory）を一時的な記憶領域とし、ハードディスク等を一時的もしくは不揮発な記憶領域とし、ＮＩＣ（Network Interface Card）経由でインターネット等のコンピュータ通信網に接続され、他の情報処理装置と通信することができる。情報処理装置において、端末装置１１１用のプログラムを実行すれば端末装置１１１として機能し、認証装置１２１用のプログラムを実行すれば認証装置１２１として機能することとなる。
【００３５】
図２は、端末装置１１１の概要構成を示す模式図である。以下、本図を参照して説明する。
【００３６】
まず、端末装置１１１のそれぞれは、秘密鍵選択部２０１、公開鍵生成部２０２、公開鍵公開部２０３を備える。
【００３７】
また、匿名グループ認証を求めるt台の端末装置１１１（U[1]，U[2]，…，U[t]）は、端末群１３１を構成する。ここで、端末群１３１（U[1]，U[2]，…，U[t]）は、端末装置１１１の全体U[1]，U[2]，…，U[m]に含まれるサブグループであり、その添字については、上記のように設定しても一般性を失わない。
【００３８】
さて、当該端末群１３１は、元選択部２０４、種計算部２０５、種送信部２０６、チャレンジ受信部２０７、中間計算部２０８、応答計算部２０９、応答送信部２１０を備える。
【００３９】
まず、認証を行うための準備として、各端末装置１１１は、鍵処理を行う。図３は、鍵処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【００４０】
U[1]，U[2]，…，U[m]の端末装置１１１のうち、i番目の端末装置１１１（U[i]）において、秘密鍵選択部２０１が、当該乗法群Zp*からt個の元
w[1,i]，w[2,i]，…，w[t,i]
を秘密鍵（W[i]）として選択する（ステップＳ３０１）。秘密鍵の選択は、他の端末装置１１１とは独立に秘匿して、また、一様にランダムに行うのが望ましい。
【００４１】
ついで、公開鍵生成部２０２が、選択された秘密鍵から
y[1,i] = gw[1,i]，
y[2,i] = gw[2,i]，
…，
y[t,i] = gw[t,i]
を公開鍵（Y[i]）として生成する（ステップＳ３０２）。
【００４２】
さらに、公開鍵公開部２０３が、m台の端末装置１１１、および、認証装置１２１に、生成された公開鍵
Y[i] = y[1,i]，y[2,i]，…，y[t,i]
を公開して（ステップＳ３０３）、本処理を終了する。
【００４３】
公開鍵の公開の手法については、種々の手法を採用することができる。たとえば、端末装置１１１の識別符号（たとえば、ユーザ名、マシン名、ＩＰアドレス、ＭＡＣアドレス等を利用することができる。）と、公開鍵と、を対応付けて記憶する鍵サーバに公開鍵を登録する。そして、鍵サーバに識別符号を指定した問い合わせをすると、これに対応付けられる公開鍵を指定した回答が得られる、というものである。認証装置１２１をこの鍵サーバとして利用しても良い。
【００４４】
したがって、情報処理装置のＣＰＵは、ＲＡＭやＮＩＣ等と共働して、秘密鍵選択部２０１、公開鍵生成部２０２、公開鍵公開部２０３として機能する。
【００４５】
図４は、認証装置１２１の概要構成を示す模式図である。以下、本図を参照して説明する。
【００４６】
本図に示すように、認証装置１２１は、種受信部４０１、チャレンジ選択部４０２、チャレンジ送信部４０３、応答受信部４０４、認証部４０５を備える。
【００４７】
図５は、m台の端末装置１１１（U[1]，U[2]，…，U[m]）のうち、匿名グループ認証を求めるt台の端末装置１１１（U[1]，U[2]，…，U[t]）からなる端末群１３１にて実行される被認証処理の制御の流れを示すフローチャートである。
【００４８】
一方、図６は、認証装置１２１にて実行される認証処理の制御の流れを示すフローチャートである。以下、これらの図を参照して説明する。
【００４９】
まず、端末群１３１側の被認証処理において、元選択部２０４が、当該有限体Zpからm+1個の元
c[0]，c[1]，c[2]，…，c[m]
を一様にランダムに選択する（ステップＳ５０１）。以下、これらの元をまとめてCと表記する。
【００５０】
ついで、種計算部２０５が、選択された元と、公開された公開鍵と、から、種
r[1] = gc[0] Πi=1m y[1,i]c[i]，
r[2] = gc[0] Πi=1m y[2,i]c[i]，
…，
r[t] = gc[0] Πi=1m y[t,i]c[i]
を計算する（ステップＳ５０２）。以下、これらの種をまとめてRと表記する。
【００５１】
さらに、種送信部２０６が、認証装置１２１に、計算された種
r[1]，r[2]，…，r[t]
を送信する（ステップＳ５０３）。
【００５２】
これらの計算には、端末装置１１１（U[i]）の秘密鍵w[1,i]，w[2,i]，…，w[t,i]を用いる必要はない。
【００５３】
したがって、ＣＰＵが、ＲＡＭやＮＩＣ等と共働して、元選択部２０４、種計算部２０５、種送信部２０６として機能する。
【００５４】
すると、認証装置１２１側の認証処理において、種受信部４０１が、端末群１３１から送信された種
r[1]，r[2]，…，r[t]
を受信する（ステップＳ５０４）。
【００５５】
次に、チャレンジ選択部４０２が、当該有限体Zpから一様にランダムに１個の元をチャレンジbとして選択する（ステップＳ５０５）。そして、チャレンジ送信部４０３が、選択されたチャレンジbを、端末群１３１に送信する（ステップＳ５０６）。
【００５６】
したがって、ＣＰＵは、ＲＡＭやＮＩＣ等と共働して、種受信部４０１、チャレンジ選択部４０２、チャレンジ送信部４０３として機能する。
【００５７】
すると、端末群１３１側の被認証処理において、チャレンジ受信部２０７が、認証装置１２１から送信されるチャレンジbを受信する（ステップＳ５０７）。
【００５８】
ついで、中間計算部２０８が、整数k = 1，2，…，tについて
f[k] = c[0] + Σi=1t w[k,i]c[i] (mod p)
を計算し、さらに、
f[t+1] = b - (c[t+1] + c[t+2] + … + c[m]) (mod p)
を計算する（ステップＳ５０８）。これらをまとめて中間値Fと呼ぶ。
【００５９】
応答計算部２０９が、端末群１３１に含まれる端末装置１１１（U[1]，U[2]，…，U[t]）のそれぞれの秘密鍵
w[1,1]，w[2,1],…，w[t,1]，
w[1,2]，w[2,2],…，w[t,2]，
…，
w[1,t]，w[2,t],…，w[t,t]
により、当該有限体Zpの上で、［数３］を満たす応答
d[0]，d[1]，d[2]，…，d[t]，d[t+1]，d[t+2]，…，d[m]
を計算する（ステップＳ５０９）。これらをまとめて応答Dと呼ぶ。
【００６０】
ここで、［数３］における行列方程式は、有限体Zpにおける加減乗除を用いたものであり、行列方程式を解くにあたっては、当該有限体Zp上での掃き出し法により、
d[0]，d[1]，d[2]，…，d[t]
を求めるのが典型的である。
【００６１】
また、この計算においては、端末装置１１１（U[1]，U[2]，…，U[t]）のそれぞれの秘密鍵
w[1,1]，w[2,1],…，w[t,1]，
w[1,2]，w[2,2],…，w[t,2]，
…，
w[1,t]，w[2,t],…，w[t,t]
を参照する必要があるため、端末群１３１の中の代表となる端末装置１１１に、それぞれの端末装置１１１の秘密鍵を通知する等の処理を行うこととなる。この情報のやり取りの態様については後述する。
【００６２】
ついで、応答送信部２１０が、計算された応答
d[0]，d[1]，…，d[m]
を、認証装置１２１に送信する（ステップＳ５１０）。
【００６３】
したがって、ＣＰＵはＲＡＭ、ＮＩＣ等と共働して、チャレンジ受信部２０７、中間計算部２０８、応答計算部２０９、応答送信部２１０として機能する。
【００６４】
さて、認証装置１２１側の認証処理では、応答受信部４０４が、端末群１３１から送信される応答
d[0]，d[1]，…，d[m]
を受信する（ステップＳ５１１）。
【００６５】
認証工程では、認証部４０５が、以下の認証条件が満たされるか否かを判定する（ステップＳ５１２）。
【００６６】
すなわち、認証条件とは、「受信された応答
d[0]，d[1]，…，d[m]
と、公開された公開鍵
y[1,1]，y[2,1]，…，y[t,1]，
y[1,2]，y[2,2]，…，y[t,2]，
…,
y[1,m]，y[2,m]，…，y[t,m]
と、により、
b = Σi=1m d[i] (mod p)
が成立し、かつ、整数j = 1，2，…，tのすべてについて、
r[j] = gd[0] Πi=1m y[j,i]d[i]
成立する」をいう。
【００６７】
認証条件が成立すれば（ステップＳ５１２；Ｙｅｓ）、当該端末群１３１に対する認証を成功させ（ステップＳ５１３）、いずれかもしくはすべてについて成立しなければ（ステップＳ５１２；Ｎｏ）、当該端末群１３１に対する認証を失敗させて（ステップＳ５１４）、本処理を終了する。
【００６８】
ここで、使用する公開鍵は、認証を求める端末群１３１に含まれるt台の端末装置１１１のみならず、m台の端末装置１１１のものを平等に使用している。
【００６９】
したがって、認証が成功したとしても、m個の公開鍵からいずれか１つの公開鍵が選ばれたときに、「当該選ばれた公開鍵を持つ端末装置１１１は、端末群１３１をなすt台の端末装置１１１のいずれかである」のか、それとも、「当該選ばれた公開鍵を持つ端末装置１１１は、端末群１３１をなすt台の端末装置１１１のいずれでもない」のかは、認証装置１２１側にはわからない。
【００７０】
一方、端末群１３１側では、t台の端末装置１１１の秘密鍵をまとめて計算処理する必要があるため、この計算処理を行う機器（典型的には代表となっている端末装置１１１である。）に秘密鍵が知得されてしまう。
【００７１】
したがって、公開鍵と秘密鍵のペアは、t台の端末群１３１の認証がされるごとに、m台の端末装置１１１全体で一斉に新規に生成し直すことが望ましい。
【００７２】
図７は、本実施形態において情報がやりとりされる様子を示す模式図である。以下、本図を参照して説明する。
【００７３】
m台の端末装置１１１のそれぞれ（U[i]）には、秘密鍵（W[i] = (w[1,i]，w[2,i]，…，w[t,i])）と公開鍵（Y[i] = (y[1,i]，y[2,i]，…，y[t,i])）の対が割り当てられている。
【００７４】
t台の端末装置１１１からなる端末群１３１の代表７０１は、一様にランダムに選択した元（C = (c[0]，c[1]，…，c[m])）と公開鍵全体（Y[1]，Y[2]，…，Y[m]）を参照して種R = (r[1]，r[2]，…，r[t])を生成し、認証装置１２１に送信する。
【００７５】
認証装置１２１は、一様にランダムに選択したチャレンジ（b）を端末群１３１に送信する。
【００７６】
端末群１３１では、端末群１３１に含まれる端末装置１１１の秘密鍵（W[1]，W[2]，…，W[t]）を参照して（共有し、もしくは、代表７０１となる端末に集中させるのが典型的である。）、応答（D = (d[0]，d[1]，…，d[m])）を求め、これを認証装置１２１に送信する。
【００７７】
認証装置１２１では、チャレンジ（b）と、受信した応答（D = (d[0]，d[1]，…，d[m])）と、公開鍵全体（Y[1]，Y[2]，…，Y[m]）と、を参照して、認証が成功するか否かを判定する。
【実施例２】
【００７８】
上記実施形態では、端末装置１１１それぞれが秘密鍵を選択することとしていたが、本実施形態においては、鍵提供装置により、秘密鍵を生成する手法を採用する。
【００７９】
図８は、鍵提供装置を含むシステムの一部の構成を示す模式図である。以下、本図を参照して説明する。
【００８０】
すなわち、鍵提供装置８０１は、秘密鍵取得部８０２、秘密鍵送信部８０３を有し、対応する処理を実行するため、各端末装置１１１は、秘密鍵受信部８０４をさらに有する。
【００８１】
すなわち、鍵提供装置８０１では、秘密鍵取得部８０２が、当該乗法群Zp*からt×m個の元
w[1,1]，w[2,1]，…，w[t,1]，
w[1,2]，w[2,2]，…，w[t,2]，
…,
w[1,m]，w[2,m]，…，w[t,m]
を一様にランダムに取得する。
【００８２】
上記実施形態では、i番目の端末装置１１１が秘密鍵（W[i] = (w[1,i]，w[2,i]，…，w[t,i])）を個別に生成していたが、本実施形態では、秘密鍵取得部８０２が、まとめて秘密鍵（W[1]，W[2]，…，W[m]）を生成することになる。
【００８３】
そして、秘密鍵送信部８０３が、整数i = 1，2，…，mのそれぞれについて、m台の端末装置１１１のうち端末装置１１１（U[i]）に、取得された
W[i] = (w[1,i]，w[2,i]，…，w[t,i])
を個別鍵として送信する。
【００８４】
一方、m台の端末装置１１１のうちi番目の端末装置１１１（U[i]）において、秘密鍵受信部８０４が、鍵提供装置８０１から送信された個別鍵
W[i] = (w[1,i]，w[2,i]，…，w[t,i])
を受信する。
【００８５】
そして、秘密鍵選択部２０１は、受信された個別鍵
W[i] = (w[1,i]，w[2,i]，…，w[t,i])
を当該秘密鍵として選択する。
【産業上の利用可能性】
【００８６】
本発明によれば、あるグループ内のサブグループにおいて、通信の複雑さを抑制して効率良く認証を行うための認証システム、認証方法、ならびに、これらをコンピュータ上にて実現するためのプログラムを提供することができる。
【図面の簡単な説明】
【００８７】
【図１】本実施形態に係る認証システムの概要構成を示す説明図である。
【図２】本実施形態に係る端末装置の概要構成を示す模式図である。
【図３】本実施形態に係る端末装置にて実行される鍵処理の制御の流れを示すフローチャートである。
【図４】本実施形態に係る認証装置の概要構成を示す模式図である。
【図５】匿名グループ認証を求めるt台の端末装置からなる端末群にて実行される被認証処理の制御の流れを示すフローチャートである。
【図６】認証装置にて実行される認証処理の制御の流れを示すフローチャートである。
【図７】本実施形態において情報がやりとりされる様子を示す模式図である。
【図８】鍵提供装置を含むシステムの一部の構成を示す模式図である。
【符号の説明】
【００８８】
１０１ 認証システム
１１１ 端末装置
１２１ 認証装置
１３１ 端末群
２０１ 秘密鍵選択部
２０２ 公開鍵生成部
２０３ 公開鍵公開部
２０４ 元選択部
２０５ 種計算部
２０６ 種送信部
２０７ チャレンジ受信部
２０８ 中間計算部
２０９ 応答計算部
２１０ 応答送信部
４０１ 種受信部
４０２ チャレンジ選択部
４０３ チャレンジ送信部
４０４ 応答受信部
４０５ 認証部
７０１ 代表
８０１ 鍵提供装置
８０２ 秘密鍵取得部
８０３ 秘密鍵送信部
８０４ 秘密鍵受信部
【特許請求の範囲】
【請求項１】
素数pを位数とする巡回群Gと、Gの生成元gと、pを法とする有限体Zpと、当該有限体Zpに対する乗法群Zp*と、ユーザ総数mと、匿名グループ認証を求める端末群に含まれる端末装置数tと、に対する認証システムであって、認証装置と、m台の端末装置U[1]，U[2]，…，U[m]と、を有し、
（ａ） 整数i = 1，2，…，mのそれぞれについて、前記m台の端末装置のうち端末装置U[i]は、
当該乗法群Zp*からt個の元
w[1,i]，w[2,i]，…，w[t,i]
を一様にランダムに秘密鍵として選択する秘密鍵選択部、
前記選択された秘密鍵から公開鍵
y[1,i] = gw[1,i]，
y[2,i] = gw[2,i]，
…，
y[t,i] = gw[t,i]
を生成する公開鍵生成部、
前記m台の端末装置、および、前記認証装置に、前記生成された公開鍵
y[1,i]，y[2,i]，…，y[t,i]
を公開する公開鍵公開部を備え、
（ｂ）前記m台の端末装置のうち、匿名グループ認証を求めるt台の端末装置U[1]，U[2]，…，U[t]からなる端末群は、
有限体Zpからm+1個の元
c[0]，c[1]，c[2]，…，c[m]
を一様にランダムに選択する元選択部、
前記選択された元と、前記公開された公開鍵と、から、種
r[1] = gc[0] Πi=1m y[1,i]c[i]，
r[2] = gc[0] Πi=1m y[2,i]c[i]，
…，
r[t] = gc[0] Πi=1m y[t,i]c[i]
を計算する種計算部、
前記認証装置に、前記計算された種
r[1]，r[2]，…，r[t]
を送信する種送信部を備え、
（ｃ）前記認証装置は、
前記端末群から送信された種
r[1]，r[2]，…，r[t]
を受信する種受信部、
有限体Zpから一様にランダムに１個の元をチャレンジbとして選択するチャレンジ選択部、
前記選択されたチャレンジbを、前記端末群に送信するチャレンジ送信部を備え、
（ｄ）前記端末群は、
前記認証装置から送信されるチャレンジbを受信するチャレンジ受信部、
整数k = 1，2，…，tについて
f[k] = c[0] + Σi=1t w[k,i]c[i] (mod p)
および
f[t+1] = b - (c[t+1] + c[t+2] + … + c[m]) (mod p)
を計算する中間計算部、
前記端末群に含まれる端末装置U[1]，U[2]，…，U[t]のそれぞれの秘密鍵
w[1,1]，w[2,1],…，w[t,1]，
w[1,2]，w[2,2],…，w[t,2]，
…，
w[1,t]，w[2,t],…，w[t,t]
により、当該有限体Zpの上で、
【数１】
を満たす応答
d[0]，d[1]，d[2]，…，d[t]，d[t+1]，d[t+2]，…，d[m]
を計算する応答計算部、
前記計算された応答
d[0]，d[1]，…，d[m]
を、前記認証装置に送信する応答送信部を備え、
（ｅ）前記認証装置は、
前記端末群から送信される応答
d[0]，d[1]，…，d[m]
を受信する応答受信部、
前記受信された応答
d[0]，d[1]，…，d[m]
と、前記公開された公開鍵
y[1,1]，y[2,1]，…，y[t,1]，
y[1,2]，y[2,2]，…，y[t,2]，
…,
y[1,m]，y[2,m]，…，y[t,m]
と、により、
b = Σi=1m d[i] (mod p)
が成立し、かつ、整数j = 1，2，…，tのそれぞれについて、
r[j] = gd[0] Πi=1m y[j,i]d[i]
が成立する場合、当該端末群に対する認証を成功させる認証部を備える
ことを特徴とする認証システム。
【請求項２】
請求項１に記載の認証システムであって、さらに鍵提供装置を備え、
（ｆ）前記鍵提供装置は、
乗法群Zp*からt×m個の元
w[1,1]，w[2,1]，…，w[t,1]，
w[1,2]，w[2,2]，…，w[t,2]，
…,
w[1,m]，w[2,m]，…，w[t,m]
を一様にランダムに取得する秘密鍵取得部、
整数i = 1，2，…，mのそれぞれについて、前記m台の端末装置のうち端末装置U[i]に、前記取得された
w[1,i]，w[2,i]，…，w[t,i]
を個別鍵として送信する秘密鍵送信部を備え、
（ｇ）整数i = 1，2，…，mのそれぞれについて、前記m台の端末装置のうち端末装置U[i]は、
前記鍵提供装置から送信された個別鍵
w[1,i]，w[2,i]，…，w[t,i]
を受信する秘密鍵受信部をさらに備え、
前記秘密鍵選択部は、前記受信された個別鍵
w[1,i]，w[2,i]，…，w[t,i]
を当該秘密鍵として選択する
ことを特徴とする認証システム。
【請求項３】
請求項１または２に記載の認証システムであって、
前記端末群に含まれるいずれか１台の端末装置へ、前記端末群に含まれる他の端末装置は、それぞれの秘密鍵を通知し、
前記端末群に含まれる当該１台の端末装置は、前記元選択部、前記種計算部、前記種送信部、前記中間計算部、前記応答計算部、前記応答送信部を備える
ことを特徴とする認証システム。
【請求項４】
請求項１から３のいずれか１項に記載の認証システムであって、
前記応答計算部は、当該有限体Zp上での掃き出し法により、
d[0]，d[1]，d[2]，…，d[t]
を求める
ことを特徴とする認証システム。
【請求項５】
素数pを位数とする巡回群Gと、Gの生成元gと、pを法とする有限体Zpと、当該有限体Zpに対する乗法群Zp*と、ユーザ総数mと、匿名グループ認証を求める端末群に含まれる端末装置数tと、に対する認証方法であって、認証装置と、m台の端末装置U[1]，U[2]，…，U[m]と、において実行され、前記認証装置は、種受信部、チャレンジ選択部、チャレンジ送信部、応答受信部、認証部を備え、前記m台の端末装置U[1]，U[2]，…，U[m]のそれぞれは、秘密鍵選択部、公開鍵生成部、公開鍵公開部を備え、前記m台の端末装置のうち、匿名グループ認証を求めるt台の端末装置U[1]，U[2]，…，U[t]からなる端末群は、元選択部、種計算部、種送信部、チャレンジ受信部、中間計算部、応答計算部、応答送信部を備え、
（ａ） 整数i = 1，2，…，mのそれぞれについて、前記m台の端末装置のうち端末装置U[i]において、
前記秘密鍵選択部が、当該乗法群Zp*からt個の元
w[1,i]，w[2,i]，…，w[t,i]
を一様にランダムに秘密鍵として選択する秘密鍵選択工程、
前記公開鍵生成部が、前記選択された秘密鍵から公開鍵
y[1,i] = gw[1,i]，
y[2,i] = gw[2,i]，
…，
y[t,i] = gw[t,i]
を生成する公開鍵生成工程、
前記公開鍵公開部が、前記m台の端末装置、および、前記認証装置に、前記生成された公開鍵
y[1,i]，y[2,i]，…，y[t,i]
を公開する公開鍵公開工程を備え、
（ｂ）前記m台の端末装置のうち、匿名グループ認証を求めるt台の端末装置U[1]，U[2]，…，U[t]からなる端末群において、
前記元選択部が、当該有限体Zpからm+1個の元
c[0]，c[1]，c[2]，…，c[m]
を一様にランダムに選択する元選択工程、
前記種計算部が、前記選択された元と、前記公開された公開鍵と、から、種
r[1] = gc[0] Πi=1m y[1,i]c[i]，
r[2] = gc[0] Πi=1m y[2,i]c[i]，
…，
r[t] = gc[0] Πi=1m y[t,i]c[i]
を計算する種計算工程、
前記種送信部が、前記認証装置に、前記計算された種
r[1]，r[2]，…，r[t]
を送信する種送信工程を備え、
（ｃ）前記認証装置において、
前記種受信部が、前記端末群から送信された種
r[1]，r[2]，…，r[t]
を受信する種受信工程、
前記チャレンジ選択部が、当該有限体Zpから一様にランダムに１個の元をチャレンジbとして選択するチャレンジ選択工程、
前記チャレンジ送信部が、前記選択されたチャレンジbを、前記端末群に送信するチャレンジ送信工程を備え、
（ｄ）前記端末群において、
前記チャレンジ受信部が、前記認証装置から送信されるチャレンジbを受信するチャレンジ受信工程、
前記中間計算部が、整数k = 1，2，…，tについて
f[k] = c[0] + Σi=1t w[k,i]c[i] (mod p)
および
f[t+1] = b - (c[t+1] + c[t+2] + … + c[m]) (mod p)
を計算する中間計算工程、
前記応答計算部が、前記端末群に含まれる端末装置U[1]，U[2]，…，U[t]のそれぞれの秘密鍵
w[1,1]，w[2,1],…，w[t,1]，
w[1,2]，w[2,2],…，w[t,2]，
…，
w[1,t]，w[2,t],…，w[t,t]
により、当該有限体Zpの上で、
【数２】
を満たす応答
d[0]，d[1]，d[2]，…，d[t]，d[t+1]，d[t+2]，…，d[m]
を計算する応答計算工程、
前記応答送信部が、前記計算された応答
d[0]，d[1]，…，d[m]
を、前記認証装置に送信する応答送信工程を備え、
（ｅ）前記認証装置において、
応答受信部が、前記端末群から送信される応答
d[0]，d[1]，…，d[m]
を受信する応答受信工程、
前記認証部が、前記受信された応答
d[0]，d[1]，…，d[m]
と、前記公開された公開鍵
y[1,1]，y[2,1]，…，y[t,1]，
y[1,2]，y[2,2]，…，y[t,2]，
…,
y[1,m]，y[2,m]，…，y[t,m]
と、により、
b = Σi=1m d[i] (mod p)
が成立し、かつ、整数j = 1，2，…，tのそれぞれについて、
r[j] = gd[0] Πi=1m y[j,i]d[i]
が成立する場合、当該端末群に対する認証を成功させる認証工程を備える
ことを特徴とする認証方法。
【請求項６】
請求項５に記載の認証方法であって、さらに鍵提供装置において実行され、前記鍵提供装置は、秘密鍵取得部、秘密鍵送信部を備え、前記m台の端末装置のそれぞれは、秘密鍵受信部をさらに備え、
（ｆ）前記鍵提供装置において、
前記秘密鍵取得部が、当該乗法群Zp*からt×m個の元
w[1,1]，w[2,1]，…，w[t,1]，
w[1,2]，w[2,2]，…，w[t,2]，
…,
w[1,m]，w[2,m]，…，w[t,m]
を一様にランダムに取得する秘密鍵取得工程、
前記秘密鍵送信部が、整数i = 1，2，…，mのそれぞれについて、前記m台の端末装置のうち端末装置U[i]に、前記取得された
w[1,i]，w[2,i]，…，w[t,i]
を個別鍵として送信する秘密鍵送信工程を備え、
（ｇ）整数i = 1，2，…，mのそれぞれについて、前記m台の端末装置のうち端末装置U[i]において、
前記秘密鍵受信部が、前記鍵提供装置から送信された個別鍵
w[1,i]，w[2,i]，…，w[t,i]
を受信する秘密鍵受信工程をさらに備え、
前記秘密鍵選択工程では、前記受信された個別鍵
w[1,i]，w[2,i]，…，w[t,i]
を当該秘密鍵として選択する
ことを特徴とする認証方法。
【請求項７】
請求項５または６に記載の認証方法であって、
前記端末群に含まれるいずれか１台の端末装置へ、前記端末群に含まれる他の端末装置は、それぞれの秘密鍵を通知し、
前記端末群に含まれる当該１台の端末装置において、前記元選択工程、前記種計算工程、前記種送信工程、前記中間計算工程、前記応答計算工程、前記応答送信工程が実行される
ことを特徴とする認証方法。
【請求項８】
請求項５から７のいずれか１項に記載の認証方法であって、
前記応答計算工程では、当該有限体Zp上での掃き出し法により、
d[0]，d[1]，d[2]，…，d[t]
を求める
ことを特徴とする認証方法。
【請求項９】
(m+1)台のコンピュータのうち、第1から第mまでのコンピュータのそれぞれを、請求項１に記載の認証システムのm台の端末装置のいずれかとして機能させ、第1から第tまでのコンピュータ群を、当該認証システムの端末群として機能させ、第(m+1)のコンピュータを、当該認証システムの認証装置として機能させる
ことを特徴とするプログラム。
【請求項１】
素数pを位数とする巡回群Gと、Gの生成元gと、pを法とする有限体Zpと、当該有限体Zpに対する乗法群Zp*と、ユーザ総数mと、匿名グループ認証を求める端末群に含まれる端末装置数tと、に対する認証システムであって、認証装置と、m台の端末装置U[1]，U[2]，…，U[m]と、を有し、
（ａ） 整数i = 1，2，…，mのそれぞれについて、前記m台の端末装置のうち端末装置U[i]は、
当該乗法群Zp*からt個の元
w[1,i]，w[2,i]，…，w[t,i]
を一様にランダムに秘密鍵として選択する秘密鍵選択部、
前記選択された秘密鍵から公開鍵
y[1,i] = gw[1,i]，
y[2,i] = gw[2,i]，
…，
y[t,i] = gw[t,i]
を生成する公開鍵生成部、
前記m台の端末装置、および、前記認証装置に、前記生成された公開鍵
y[1,i]，y[2,i]，…，y[t,i]
を公開する公開鍵公開部を備え、
（ｂ）前記m台の端末装置のうち、匿名グループ認証を求めるt台の端末装置U[1]，U[2]，…，U[t]からなる端末群は、
有限体Zpからm+1個の元
c[0]，c[1]，c[2]，…，c[m]
を一様にランダムに選択する元選択部、
前記選択された元と、前記公開された公開鍵と、から、種
r[1] = gc[0] Πi=1m y[1,i]c[i]，
r[2] = gc[0] Πi=1m y[2,i]c[i]，
…，
r[t] = gc[0] Πi=1m y[t,i]c[i]
を計算する種計算部、
前記認証装置に、前記計算された種
r[1]，r[2]，…，r[t]
を送信する種送信部を備え、
（ｃ）前記認証装置は、
前記端末群から送信された種
r[1]，r[2]，…，r[t]
を受信する種受信部、
有限体Zpから一様にランダムに１個の元をチャレンジbとして選択するチャレンジ選択部、
前記選択されたチャレンジbを、前記端末群に送信するチャレンジ送信部を備え、
（ｄ）前記端末群は、
前記認証装置から送信されるチャレンジbを受信するチャレンジ受信部、
整数k = 1，2，…，tについて
f[k] = c[0] + Σi=1t w[k,i]c[i] (mod p)
および
f[t+1] = b - (c[t+1] + c[t+2] + … + c[m]) (mod p)
を計算する中間計算部、
前記端末群に含まれる端末装置U[1]，U[2]，…，U[t]のそれぞれの秘密鍵
w[1,1]，w[2,1],…，w[t,1]，
w[1,2]，w[2,2],…，w[t,2]，
…，
w[1,t]，w[2,t],…，w[t,t]
により、当該有限体Zpの上で、
【数１】
を満たす応答
d[0]，d[1]，d[2]，…，d[t]，d[t+1]，d[t+2]，…，d[m]
を計算する応答計算部、
前記計算された応答
d[0]，d[1]，…，d[m]
を、前記認証装置に送信する応答送信部を備え、
（ｅ）前記認証装置は、
前記端末群から送信される応答
d[0]，d[1]，…，d[m]
を受信する応答受信部、
前記受信された応答
d[0]，d[1]，…，d[m]
と、前記公開された公開鍵
y[1,1]，y[2,1]，…，y[t,1]，
y[1,2]，y[2,2]，…，y[t,2]，
…,
y[1,m]，y[2,m]，…，y[t,m]
と、により、
b = Σi=1m d[i] (mod p)
が成立し、かつ、整数j = 1，2，…，tのそれぞれについて、
r[j] = gd[0] Πi=1m y[j,i]d[i]
が成立する場合、当該端末群に対する認証を成功させる認証部を備える
ことを特徴とする認証システム。
【請求項２】
請求項１に記載の認証システムであって、さらに鍵提供装置を備え、
（ｆ）前記鍵提供装置は、
乗法群Zp*からt×m個の元
w[1,1]，w[2,1]，…，w[t,1]，
w[1,2]，w[2,2]，…，w[t,2]，
…,
w[1,m]，w[2,m]，…，w[t,m]
を一様にランダムに取得する秘密鍵取得部、
整数i = 1，2，…，mのそれぞれについて、前記m台の端末装置のうち端末装置U[i]に、前記取得された
w[1,i]，w[2,i]，…，w[t,i]
を個別鍵として送信する秘密鍵送信部を備え、
（ｇ）整数i = 1，2，…，mのそれぞれについて、前記m台の端末装置のうち端末装置U[i]は、
前記鍵提供装置から送信された個別鍵
w[1,i]，w[2,i]，…，w[t,i]
を受信する秘密鍵受信部をさらに備え、
前記秘密鍵選択部は、前記受信された個別鍵
w[1,i]，w[2,i]，…，w[t,i]
を当該秘密鍵として選択する
ことを特徴とする認証システム。
【請求項３】
請求項１または２に記載の認証システムであって、
前記端末群に含まれるいずれか１台の端末装置へ、前記端末群に含まれる他の端末装置は、それぞれの秘密鍵を通知し、
前記端末群に含まれる当該１台の端末装置は、前記元選択部、前記種計算部、前記種送信部、前記中間計算部、前記応答計算部、前記応答送信部を備える
ことを特徴とする認証システム。
【請求項４】
請求項１から３のいずれか１項に記載の認証システムであって、
前記応答計算部は、当該有限体Zp上での掃き出し法により、
d[0]，d[1]，d[2]，…，d[t]
を求める
ことを特徴とする認証システム。
【請求項５】
素数pを位数とする巡回群Gと、Gの生成元gと、pを法とする有限体Zpと、当該有限体Zpに対する乗法群Zp*と、ユーザ総数mと、匿名グループ認証を求める端末群に含まれる端末装置数tと、に対する認証方法であって、認証装置と、m台の端末装置U[1]，U[2]，…，U[m]と、において実行され、前記認証装置は、種受信部、チャレンジ選択部、チャレンジ送信部、応答受信部、認証部を備え、前記m台の端末装置U[1]，U[2]，…，U[m]のそれぞれは、秘密鍵選択部、公開鍵生成部、公開鍵公開部を備え、前記m台の端末装置のうち、匿名グループ認証を求めるt台の端末装置U[1]，U[2]，…，U[t]からなる端末群は、元選択部、種計算部、種送信部、チャレンジ受信部、中間計算部、応答計算部、応答送信部を備え、
（ａ） 整数i = 1，2，…，mのそれぞれについて、前記m台の端末装置のうち端末装置U[i]において、
前記秘密鍵選択部が、当該乗法群Zp*からt個の元
w[1,i]，w[2,i]，…，w[t,i]
を一様にランダムに秘密鍵として選択する秘密鍵選択工程、
前記公開鍵生成部が、前記選択された秘密鍵から公開鍵
y[1,i] = gw[1,i]，
y[2,i] = gw[2,i]，
…，
y[t,i] = gw[t,i]
を生成する公開鍵生成工程、
前記公開鍵公開部が、前記m台の端末装置、および、前記認証装置に、前記生成された公開鍵
y[1,i]，y[2,i]，…，y[t,i]
を公開する公開鍵公開工程を備え、
（ｂ）前記m台の端末装置のうち、匿名グループ認証を求めるt台の端末装置U[1]，U[2]，…，U[t]からなる端末群において、
前記元選択部が、当該有限体Zpからm+1個の元
c[0]，c[1]，c[2]，…，c[m]
を一様にランダムに選択する元選択工程、
前記種計算部が、前記選択された元と、前記公開された公開鍵と、から、種
r[1] = gc[0] Πi=1m y[1,i]c[i]，
r[2] = gc[0] Πi=1m y[2,i]c[i]，
…，
r[t] = gc[0] Πi=1m y[t,i]c[i]
を計算する種計算工程、
前記種送信部が、前記認証装置に、前記計算された種
r[1]，r[2]，…，r[t]
を送信する種送信工程を備え、
（ｃ）前記認証装置において、
前記種受信部が、前記端末群から送信された種
r[1]，r[2]，…，r[t]
を受信する種受信工程、
前記チャレンジ選択部が、当該有限体Zpから一様にランダムに１個の元をチャレンジbとして選択するチャレンジ選択工程、
前記チャレンジ送信部が、前記選択されたチャレンジbを、前記端末群に送信するチャレンジ送信工程を備え、
（ｄ）前記端末群において、
前記チャレンジ受信部が、前記認証装置から送信されるチャレンジbを受信するチャレンジ受信工程、
前記中間計算部が、整数k = 1，2，…，tについて
f[k] = c[0] + Σi=1t w[k,i]c[i] (mod p)
および
f[t+1] = b - (c[t+1] + c[t+2] + … + c[m]) (mod p)
を計算する中間計算工程、
前記応答計算部が、前記端末群に含まれる端末装置U[1]，U[2]，…，U[t]のそれぞれの秘密鍵
w[1,1]，w[2,1],…，w[t,1]，
w[1,2]，w[2,2],…，w[t,2]，
…，
w[1,t]，w[2,t],…，w[t,t]
により、当該有限体Zpの上で、
【数２】
を満たす応答
d[0]，d[1]，d[2]，…，d[t]，d[t+1]，d[t+2]，…，d[m]
を計算する応答計算工程、
前記応答送信部が、前記計算された応答
d[0]，d[1]，…，d[m]
を、前記認証装置に送信する応答送信工程を備え、
（ｅ）前記認証装置において、
応答受信部が、前記端末群から送信される応答
d[0]，d[1]，…，d[m]
を受信する応答受信工程、
前記認証部が、前記受信された応答
d[0]，d[1]，…，d[m]
と、前記公開された公開鍵
y[1,1]，y[2,1]，…，y[t,1]，
y[1,2]，y[2,2]，…，y[t,2]，
…,
y[1,m]，y[2,m]，…，y[t,m]
と、により、
b = Σi=1m d[i] (mod p)
が成立し、かつ、整数j = 1，2，…，tのそれぞれについて、
r[j] = gd[0] Πi=1m y[j,i]d[i]
が成立する場合、当該端末群に対する認証を成功させる認証工程を備える
ことを特徴とする認証方法。
【請求項６】
請求項５に記載の認証方法であって、さらに鍵提供装置において実行され、前記鍵提供装置は、秘密鍵取得部、秘密鍵送信部を備え、前記m台の端末装置のそれぞれは、秘密鍵受信部をさらに備え、
（ｆ）前記鍵提供装置において、
前記秘密鍵取得部が、当該乗法群Zp*からt×m個の元
w[1,1]，w[2,1]，…，w[t,1]，
w[1,2]，w[2,2]，…，w[t,2]，
…,
w[1,m]，w[2,m]，…，w[t,m]
を一様にランダムに取得する秘密鍵取得工程、
前記秘密鍵送信部が、整数i = 1，2，…，mのそれぞれについて、前記m台の端末装置のうち端末装置U[i]に、前記取得された
w[1,i]，w[2,i]，…，w[t,i]
を個別鍵として送信する秘密鍵送信工程を備え、
（ｇ）整数i = 1，2，…，mのそれぞれについて、前記m台の端末装置のうち端末装置U[i]において、
前記秘密鍵受信部が、前記鍵提供装置から送信された個別鍵
w[1,i]，w[2,i]，…，w[t,i]
を受信する秘密鍵受信工程をさらに備え、
前記秘密鍵選択工程では、前記受信された個別鍵
w[1,i]，w[2,i]，…，w[t,i]
を当該秘密鍵として選択する
ことを特徴とする認証方法。
【請求項７】
請求項５または６に記載の認証方法であって、
前記端末群に含まれるいずれか１台の端末装置へ、前記端末群に含まれる他の端末装置は、それぞれの秘密鍵を通知し、
前記端末群に含まれる当該１台の端末装置において、前記元選択工程、前記種計算工程、前記種送信工程、前記中間計算工程、前記応答計算工程、前記応答送信工程が実行される
ことを特徴とする認証方法。
【請求項８】
請求項５から７のいずれか１項に記載の認証方法であって、
前記応答計算工程では、当該有限体Zp上での掃き出し法により、
d[0]，d[1]，d[2]，…，d[t]
を求める
ことを特徴とする認証方法。
【請求項９】
(m+1)台のコンピュータのうち、第1から第mまでのコンピュータのそれぞれを、請求項１に記載の認証システムのm台の端末装置のいずれかとして機能させ、第1から第tまでのコンピュータ群を、当該認証システムの端末群として機能させ、第(m+1)のコンピュータを、当該認証システムの認証装置として機能させる
ことを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２００９−２７５１３（Ｐ２００９−２７５１３Ａ）
【公開日】平成２１年２月５日（２００９．２．５）
【国際特許分類】
【出願番号】特願２００７−１８９４３３（Ｐ２００７−１８９４３３）
【出願日】平成１９年７月２０日（２００７．７．２０）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 社団法人電子情報通信学会、２００７年 暗号と情報セキュリティシンポジウム、平成１９年１月２３日発行
【出願人】（３０１０２２４７１）独立行政法人情報通信研究機構 (1,071)
【Ｆターム（参考）】
【公開日】平成２１年２月５日（２００９．２．５）
【国際特許分類】
【出願日】平成１９年７月２０日（２００７．７．２０）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 社団法人電子情報通信学会、２００７年 暗号と情報セキュリティシンポジウム、平成１９年１月２３日発行
【出願人】（３０１０２２４７１）独立行政法人情報通信研究機構 (1,071)
【Ｆターム（参考）】
[ Back to top ]