計算システム、計算方法、ならびに、プログラム
【課題】行列方程式の求解を分散して行って、匿名グループ認証を行うのに好適な、計算システム等を提供する。
【解決手段】計算システム１０１の端末装置１０２は、それぞれ、ベクトルw[*,1]，…，w[*,u]と秘密鍵s[1]，…，s[u]を秘密に保持し、公開鍵p[1]，…，p[u]を公開し、秘密鍵svと制御装置１０３が公開鍵pvで暗号化した行列の掃出しを秘密鍵を用いて順次行うとともに、公開鍵pvで暗号化したベクトルに順次掃出しを適用して、最終結果を制御装置１０３に返すと、制御装置１０３は、秘密鍵svを用いて、端末装置１０２の各々が記憶するベクトルからなる行列を用いた行列方程式の解を得る。
【解決手段】計算システム１０１の端末装置１０２は、それぞれ、ベクトルw[*,1]，…，w[*,u]と秘密鍵s[1]，…，s[u]を秘密に保持し、公開鍵p[1]，…，p[u]を公開し、秘密鍵svと制御装置１０３が公開鍵pvで暗号化した行列の掃出しを秘密鍵を用いて順次行うとともに、公開鍵pvで暗号化したベクトルに順次掃出しを適用して、最終結果を制御装置１０３に返すと、制御装置１０３は、秘密鍵svを用いて、端末装置１０２の各々が記憶するベクトルからなる行列を用いた行列方程式の解を得る。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、行列方程式の求解を分散して行って、匿名グループ認証を行うのに好適な、計算システム、計算方法、ならびに、これらをコンピュータ上にて実現するためのプログラムに関する。
【背景技術】
【０００２】
従来、認証技術の分野では、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, ２００５年
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、このような認証手法においては、通信の複雑さを抑制して、通信量を減らしたい、との要望は大きい。
【０００６】
このほか、このような認証方法における行列方程式の求解を、適切に行う必要もある。
【０００７】
本発明は、このような課題を解決するもので、行列方程式の求解を分散して行って、匿名グループ認証を行うのに好適な、計算システム、計算方法、ならびに、これらをコンピュータ上にて実現するためのプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記の課題を解決するため、本発明の原理にしたがい、以下の発明を開示する。
【０００９】
本発明の第１の観点に係る計算システムは、端末装置U1，…，Utと、制御装置と、を有する。
【００１０】
ここで、列ベクトルvのj行目の要素をv[j]と表記する。
【００１１】
【数１９】
【００１２】
行列Aのj行i列目の要素をA[j,i]と表記する。
【００１３】
【数２０】
【００１４】
素数Pを法とする有限体ZPの要素aを、加法群(ZP,+)からPを法とする生成元gの巡回乗法群G = 〈g〉へのホモモルフィック暗号e(・,・)を用いて、公開鍵pにより暗号化した結果を、e(p,a)と表記する。
【００１５】
すると、ZPの任意の要素x,yと任意の公開鍵pは、
e(p,x)e(p,y) = e(p,x+y)
を満たす。
【００１６】
さらに、h行k列の行列Aのj行i列の要素A[j,i] = aj,iを、公開鍵p1，…，pkにより暗号化した行列e(A)を
e(A)[j,i] = e(pi,aj,i)
と定義する。
【００１７】
【数２１】
【００１８】
また、h行の列ベクトルvのj行の要素v[j]を、公開鍵piにより暗号化した列ベクトルei(v)を、
ei(v)[j] = e(pi,v[j])
と定義する。
【００１９】
そして、H行u列の行列Bのh行i列の要素B[h,i] = bh,iと、u行K列の行列Cのi行k列の要素C[i,k] = ci,kと、についての演算B◎Cを、
B◎C[h,k] = Πi=1u C[i,k]B[h,i]
と定義する。
【００２０】
【数２２】
【００２１】
すると、行列A，Bについての演算B◎e(A)は、
B◎e(A)[h,k] = e(pk,Σi=1u B[h,i]A[i,k]) = Πi=1u e(pk,A[i,k])B[h,i]
すなわち
B◎e(A) = e(BA)
を満たす。
【００２２】
また、公開鍵piおよび列ベクトルvについての演算B◎ei(v)は、
B◎ei(v) = ei(Bv)
を満たす。
【００２３】
さて、i = 1，…，uのそれぞれについて、端末装置Uiは、有限体ZPに含まれる秘密値w[1,i]，…，w[u,i]と、ホモモルフィック暗号e(・,・)における秘密鍵siと公開鍵piと、があらかじめ記憶される端末記憶部を備える。
【００２４】
そして、制御装置は、ホモモルフィック暗号e(・,・)における秘密鍵svと公開鍵pvと、があらかじめ記憶される制御記憶部を備える。
【００２５】
さらに、当該計算システムは、端末装置U1，…，Utのそれぞれに記憶される秘密値を要素とするt行t列の行列Wと、ZPに含まれる要素からなるt行の列ベクトルfと、からなる行列方程式
W[j,i] = w[j,i]；
WX = f (mod P)
の解ベクトルXを求める。
【００２６】
【数２３】
【００２７】
ここで、i = 1，…，tのそれぞれについて、端末装置Uiは、秘密値w[1,i]，…，w[t,i]を、公開鍵piにより暗号化した暗号化済値
e(pi,w[1,i])，…，e(pi,w[t,i])
を計算する端末暗号化部、計算された暗号化済値を公開する端末公開部を備える。
【００２８】
一方、制御装置は、端末装置U1，…，Utにより公開された暗号化済値から、暗号化済行列e(W)および暗号化済ベクトルev(f)を
e(W)[j,i] = e(pi,w[j,i]) (1≦i≦t，1≦j≦t)；
ev(f)[j] = e(pv，f[j]) (1≦j≦t)
により生成するe生成部を備える。
【００２９】
【数２４】
【００３０】
【数２５】
【００３１】
さらに、制御装置は、生成された行列e(W)および当該列ベクトルev(f)を端末装置U1に送信する行列送信部を備える。
【００３２】
さらに、i = 1，…，tのそれぞれについて、端末装置Uiは、i = 1の場合、制御装置から送信された行列および列ベクトル
e(W)，ev(f)
を受信し、i > 1の場合、端末装置Ui-1から送信された行列および列ベクトル
Li-1◎…◎L1◎e(W) = e(Li-1…L1W)，Li-1◎…◎L1◎ev(f) = ev(Li-1…L1f)
を受信する行列受信部、受信された行列のi列目を、秘密鍵siにより復号し、i行目を軸に当該復号された列をガウス消去する行列Liを計算する消去行列計算部、計算された行列Liと、受信された行列および列ベクトルと、から、
Li◎Li-1◎…◎L1◎e(W) = e(LiLi-1…L1W)，Li◎Li-1◎…◎L1◎ev(f) = ev(LiLi-1…L1f)
を計算する◎行列段階計算部、計算された行列および列ベクトル
Li◎Li-1◎…◎L1◎e(W) = e(LiLi-1…L1W)，Li◎Li-1◎…◎L1◎ev(f) = ev(LiLi-1…L1f)
を、i < tの場合、端末装置Ui+1に送信する行列送信部を備える。
【００３３】
一方、制御装置は、端末装置Utにおいて計算された列ベクトル
ev(LtLt-1…L1f)
を秘密鍵svで
LtLt-1…L1f
に復号して、解ベクトルXとする求解部を備える。
【００３４】
また、本発明の計算システムにおいて、制御装置は、端末装置U1，…，UtのいずれかUkであり、秘密鍵sv = sk，公開鍵pv = pkとするように構成することができる。
【００３５】
また、本発明の計算システムは、外部装置をさらに備え、制御装置が制御記憶部を備えるのにかえて、外部装置は、ホモモルフィック暗号e(・,・)における秘密鍵svと公開鍵pvと、があらかじめ記憶される外部記憶部を備え、以下のように構成することができる。
【００３６】
当該計算システムは、当該t行t列の行列Wと、当該t行の列ベクトルfと、からなる行列方程式を解くのにかえて、端末装置U1，…，Utのそれぞれに記憶される秘密値を要素とする(t+1)行(t+1)列の行列Wと、ZPに含まれる要素からなる(t+1)行の列ベクトルfと、からなる行列方程式
W[j,i] = w[j,i] (1≦j≦t，1≦i≦t)；
W[t+1,i] = W[j,t+1] = 1 (1≦j≦t，1≦i≦t)；
W[t+1,t+1] = 0；
WX = f (mod P)
の解ベクトルXを求める。
【００３７】
【数２６】
【００３８】
そして、制御装置において、e生成部は、端末装置U1，…，Utにより公開された暗号化済値および公開鍵piと、外部装置により公開された公開鍵pvと、により、暗号化済行列e(W)と暗号化済ベクトルev(f)を、
e(W)[j,i] = e(pi,w[j,i]) (1≦j≦t，1≦i≦t)；
e(W)[t+1,i] = e(pi,1) (1≦i≦t)；
e(W)[j,t+1] = e(pv,1) (1≦j≦t)；
e(W)[t+1,t+1] = e(pv,0)；
ev(f)[j] = e(pv，f[j]) (1≦j≦t)
により生成する。
【００３９】
【数２７】
【００４０】
一方、制御装置は、求解部にかえて端末装置Utにおいて計算された行列および列ベクトル
Lt◎Lt-1…◎L1◎e(W) = e(LtLt-1…L1W)，ev(LtLt-1…L1f)
を、外部装置に転送する転送部を備える。
【００４１】
さらに、外部装置は、制御装置から転送された行列および列ベクトル
Lt◎Lt-1…◎L1◎e(W) = e(LtLt-1…L1W)，ev(LtLt-1…L1f)
を受け付ける行列受付部、受け付けられた行列のt+1列目を、秘密鍵svにより復号し、t+1行目を軸に当該復号された列をガウス消去する行列Lvを計算する消去行列計算部、受信された列ベクトルを秘密鍵svで
LtLt-1…L1f
に復号して、これと計算された行列Lvと、から、
LvLtLt-1…L1f
を計算して、これを解ベクトルXとする求解部を備える。
【００４２】
また、本発明の計算システムは、端末装置Ut+1，…，Umと、中央装置と、をさらに備え、以下のように構成することができる。
【００４３】
すなわち、中央装置は、j = 1，…，tおよびi = 1，…，mのそれぞれについて、ZPから値w[j,i]をランダムに一様に生成する値生成部、i = 1，…，mのそれぞれについて、値w[1,i]，…，w[t,i]を端末装置U[i]に送信する値送信部を備える。
【００４４】
一方、i = 1，…，mについて、端末装置Uiは、中央装置から送信された値w[1,i]，…，w[t,i]を受信する秘密値受信部を備え、受信されたw[1,i]，…，w[t,i]を、当該端末装置の秘密値w[1,i]，…，w[t,i]とし、y[1,i] = gw[1,i]，…，y[t,i] = gw[t,i]を当該端末装置の公開値とする。
【００４５】
さらに、端末装置U1，…，Utおよび制御装置は、端末群を構成し、当該端末群は、ZPから値c[0]，c[1]，…，c[m]をランダムに一様に生成するc生成部、生成された値c[0]，c[1]，…，c[m]と、公開された公開鍵と、から、j = 1，…，tのそれぞれについて、
r[j] = gc[0] Πi=1m y[j,i]c[i]
を計算するr計算部、生成された値c[0]，c[1]，…，c[m]と、計算されたr[1]，…，r[t]を、外部装置に送信するrc送信部を備える。
【００４６】
そして、外部装置は、端末群から送信されたc[0]，c[1]，…，c[m]と、r[1]，…，r[t]とを受信するrc受信部、ZPからbをランダムに選択するb選択部、選択されたbを、端末群に送信するb送信部を備える。
【００４７】
一方、端末群は、外部装置から送信されたbを受信するb受信部、j = 1，…，tのそれぞれについて、端末装置Uiにおいて、
f[j] = c[0] + Σi=1t w[j,i]c[i]
を計算し、端末群のいずれかの端末装置において
f[t+1] = b - Σi=t+1m c[i]
を計算するf計算部を備える。
【００４８】
さらに、端末群および外部装置は、計算された列ベクトルfにより、当該行列方程式
WX = f (mod P)
を求解する。
【００４９】
そして、外部装置は、求解された結果により、j = 1，…，tのそれぞれについて、
d[j] = X[j]
とし、
d[0] = X[t+1]
とし、j = t+1，…，mのそれぞれについて
d[j] = c[j]
とするd計算部、受信されたr[1]，…，r[t]と、得られたd[0]，d[1]，…，d[m]と、に対して、j = 1，…，tのすべてについて、
r[j] = gd[0] Πi=1m y[j,i]d[i]
が成立し、かつ、
b = Σi=1m d[i] (mod P)
が成立する場合、端末群の匿名認証を成功させる認証部を備える。
【００５０】
本発明のその他の観点に係る計算方法は、上記計算システムが実行する計算方法である。
【００５１】
本発明のその他の観点に係るプログラムは、コンピュータを、上記の計算システムの端末装置、制御装置、外部装置、もしくは、中央装置の各部として機能させるように構成する。
【００５２】
なお、上記のプログラムは、コンピュータ読取可能な情報記録媒体（コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、または、半導体メモリを含む。）に記録することができる。
【００５３】
そして、上記の情報記録媒体は、コンピュータとは独立して配布、販売することができるほか、インターネット等のコンピュータ通信網を介して上記のプログラムそのものを配布、販売することができる。
【発明の効果】
【００５４】
本発明によれば、行列方程式の求解を分散して行って、匿名グループ認証を行うのに好適な、計算システム、計算方法、ならびに、これらをコンピュータ上にて実現するためのプログラムを提供することができる。
【図面の簡単な説明】
【００５５】
【図１】実施例１に係る計算システムの概要構成を示す説明図である。
【図２】i番目の端末装置Uiの概要構成を示す説明図である。
【図３】制御装置の概要構成を示す説明図である。
【図４】本実施形態に係る求解処理の制御の流れを示すフローチャートである。
【図５】実施例２に係る計算システムの概要構成を示す模式図である。
【図６】外部装置が実行する外部処理の制御の流れを示す説明図である。
【図７】実施例３に係る計算システムの概要構成を示す模式図である。
【図８】全端末装置U1，…，Umの初期化を行う初期化処理の制御の流れを示すフローチャートである。
【図９】認証処理の制御の流れを示すフローチャートである。
【発明を実施するための形態】
【００５６】
以下に本発明の実施形態を説明する。なお、以下にあげる実施形態は、説明のためのものであり、本発明の範囲を制限するものではない。したがって、当業者であれば、これらの各要素または全要素を、これと均等なものに置換した実施形態を採用することが可能であるが、これらの実施形態も、本発明の範囲に含まれる。
【００５７】
なお、以下の実施形態において実現される各装置は、いずれも、他の装置と通信可能なコンピュータにおいて、所定のプログラムを実行することによって実現されるものとするのが典型的であるが、電子回路等のハードウェアによって、各装置を実現することとしても良い。
【実施例１】
【００５８】
図１は、本実施形態に係る計算システムの概要構成を示す説明図である。以下、本図を参照して説明する。
【００５９】
本図に示す計算システム１０１は、t台の端末装置１０２（それぞれU1，…，Utと呼ぶ。）と、制御装置１０３と、を備え、行列方程式の求解を行う。
【００６０】
以下、理解を容易にするため、［数１９］に示すように、一般に、列ベクトルvのj行目の要素をv[j]と表記する。
【００６１】
また、［数２０］に示すように、一般に、行列Aのj行i列目の要素をA[j,i]と表記する。
【００６２】
さらに、素数Pを法とする有限体ZPの要素aを、加法群(ZP,+)からPを法とする生成元gの巡回乗法群G = 〈g〉へのホモモルフィック暗号e(・,・)を用いて、公開鍵pにより暗号化した結果を、e(p,a)と表記する。
【００６３】
このようなホモモルフィック暗号としては、現在広く用いられている公開鍵暗号の技術を適用することができる。
【００６４】
すると、ZPの任意の要素x,yと任意の公開鍵pは、
e(p,x)e(p,y) = e(p,x+y)
を満たす。
【００６５】
ここで、h行k列の行列Aのj行i列の要素A[j,i] = aj,iを、公開鍵p1，…，pkにより暗号化した行列e(A)を、［数２１］のように、
e(A)[j,i] = e(pi,aj,i)
と定義する。
【００６６】
また、h行の列ベクトルvのj行の要素v[j]を、公開鍵piにより暗号化した列ベクトルei(v)を、
ei(v)[j] = e(pi,v[j])
と定義する。
【００６７】
さらに、H行u列の行列Bのh行i列の要素B[h,i] = bh,iと、u行K列の行列Cのi行k列の要素C[i,k] = ci,kと、についての演算B◎Cを、［数２２］のように、
B◎C[h,k] = Πi=1u C[i,k]B[h,i]
と定義する。
【００６８】
すると、行列A，Bについての演算B◎e(A)は、
B◎e(A)[h,k] = e(pk,Σi=1u B[h,i]A[i,k]) = Πi=1u e(pk,A[i,k])B[h,i]
すなわち
B◎e(A) = e(BA)
を満たすことがわかる。
【００６９】
また、公開鍵piおよび列ベクトルvについての演算B◎ei(v)は、
B◎ei(v) = ei(Bv)
を満たすこととなる。
【００７０】
図２は、i = 1，…，uのそれぞれに対して、i番目の端末装置１０２（Ui）の概要構成を示す説明図である。以下、本図を参照して説明する。
【００７１】
端末装置１０２（Ui）は、端末記憶部２０１、端末暗号化部２０２、端末公開部２０３、行列受信部２０４、消去行列計算部２０５、◎行列段階計算部２０６、行列送信部２０７を備える。
【００７２】
ここで、端末記憶部２０１には、有限体ZPに含まれる秘密値w[1,i]，…，w[u,i]（図では「w[*,i]」と表記する。）と、ホモモルフィック暗号e(・,・)における秘密鍵siと公開鍵piと、があらかじめ記憶される。
【００７３】
ここで、秘密値w[1,i]，…，w[u,i]と、秘密鍵siと、は、いずれも当該端末装置１０２（Ui）が秘密に記憶するものであり、他者に対して公開されることはない。
【００７４】
一方、公開鍵piは、秘密鍵siと対をなすものであるが、当該端末装置１０２（Ui）は、公開鍵piを、他者に対して公開することとなる。
【００７５】
ここで、理解を容易にするため、端末装置１０２（Ui）の他の要素については、後述することとし、以下では、制御装置１０３について説明する。
【００７６】
図３は、制御装置１０３の概要構成を示す説明図である。以下、本図を参照して説明する。
【００７７】
制御装置１０３は、制御記憶部３０１、e生成部３０２、行列送信部３０３、行列受信部３０４、求解部３０５を備える。
【００７８】
制御記憶部３０１には、ホモモルフィック暗号e(・,・)における秘密鍵svと公開鍵pvと、があらかじめ記憶される。
【００７９】
ここで、秘密鍵svは他者に対して公開されることはないが、これと対をなす公開鍵pvは、他者に対して公開される。
【００８０】
ここで、本計算システム１０１は、端末装置１０２（U1，…，Ut）のそれぞれに記憶される秘密値を要素とするt行t列の行列Wと、ZPに含まれる要素からなるt行の列ベクトルfと、からなる、［数２３］に示すような行列方程式
W[j,i] = w[j,i]；
WX = f (mod P)
の解ベクトルXを求める。なお、一般に、t≦uである。
【００８１】
上記のように、行列Wの各要素は、いずれかの端末装置１０２に秘密に記憶されるものである。したがって、この方程式を、直接解くことはできない。本実施形態は、秘密にすべき情報を外部に漏らさずに、ベクトルfと行列Wについての、Pを法とする行列方程式を求解する点に特徴がある。
【００８２】
以下、端末装置１０２および制御装置１０３の各部が実行する求解処理について、詳細に説明する。図４は、本実施形態に係る求解処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【００８３】
まず、i = 1，…，tのそれぞれについて、端末装置１０２（Ui）において、端末暗号化部２０２は、秘密値w[1,i]，…，w[t,i]を、公開鍵piにより暗号化した暗号化済値
e(pi,w[1,i])，…，e(pi,w[t,i])
を計算する（ステップＳ４０１）。
【００８４】
上記のように、秘密値w[1,i]，…，w[t,i]は、行列方程式の行列の要素をなすが、他者に対して秘密にされる。これを、自身の公開鍵piで暗号化するのである。
【００８５】
一方、端末公開部２０３は、計算された暗号化済値を公開する（ステップＳ４０２）。各端末装置１０２が公開した暗号化済値は、他の端末装置１０２および制御装置１０３で知得可能となる。公開の手法としては、装置間の通信を利用するのが典型的であるが、共有記憶域を設け、ここに対して読み書きを行うことによって、他者に公開することとしても良い。
【００８６】
さらに、制御装置１０３において、e生成部３０２は、端末装置１０２（U1，…，Ut）により公開された暗号化済値から、暗号化済行列e(W)および暗号化済ベクトルev(f)を、［数２４］［数２５］により、
e(W)[j,i] = e(pi,w[j,i]) (1≦i≦t，1≦j≦t)；
ev(f)[j] = e(pv，f[j]) (1≦j≦t)
のように生成する（ステップＳ４０３）。
【００８７】
上記のように、e(pi,w[j,i])は、各端末装置１０２によって公開された情報であり、これを並べることによって、行列e(W)を生成する。
【００８８】
一方、fは解くべき行列方程式に含まれるベクトルであり、各要素を、自身の公開鍵pvで暗号化するのである。
【００８９】
さらに、制御装置１０３において、行列送信部３０３は、生成された行列e(W)および当該列ベクトルev(f)を端末装置１０２（U1）に送信する（ステップＳ４０４）。
【００９０】
すると、i = 1，…，tのそれぞれについて、端末装置１０２（Ui）は、以下のように処理を行う。
【００９１】
すなわち、端末装置１０２（Ui）の行列受信部２０４は、i = 1の場合（ステップＳ４０５；Ｙｅｓ）、制御装置１０３から送信された行列および列ベクトル
e(W)，ev(f)
を受信する（ステップＳ４０６）。
【００９２】
ついで、消去行列計算部２０５は、受信された行列のi列目を、秘密鍵siにより復号し、i行目を軸に当該復号された列をガウス消去する行列Liを計算する（ステップＳ４０７）。
【００９３】
i = 1の場合、受信された行列のi列目は、順に、e(p1,w[1,1])，e(p1,w[2,1])，…，e(p1,w[t,1])であるから、秘密鍵で復号することができ、w[1,1]，w[2,1]，…，w[t,1]からなる列ベクトルが得られる。
【００９４】
i = 1の場合、行列Liを、この列ベクトルに乗じると、w[1,1]，w[2,1]，…，w[t,1]からなる列ベクトルのi行目の要素は１となり、その他の要素は０となる。
【００９５】
このような行列Liは、w[1,1]，w[2,1]，…，w[t,1]からなる列ベクトルが与えられれば、掃出し法によって、計算することができる。
【００９６】
ついで、◎行列段階計算部２０６は、計算された行列Liと、受信された行列および列ベクトルと、から、
Li◎Li-1◎…◎L1◎e(W) = e(LiLi-1…L1W)，Li◎Li-1◎…◎L1◎ev(f) = ev(LiLi-1…L1f)
を計算する（ステップＳ４０８）。
【００９７】
上記のように、◎演算については、
L1◎e(W) = e(L1W)，
L1◎ev(f) = ev(L1f)
が成立する。すなわち、◎演算の左側の項L1は、◎演算の右側の項のe(W)，ev(f)の括弧の中に、乗算として繰り込むことができるのである。
【００９８】
ついで、i = 1のように、i < tである場合（ステップＳ４０９；Ｙｅｓ）、行列送信部２０７は、計算された行列および列ベクトル
Li◎Li-1◎…◎L1◎e(W) = e(LiLi-1…L1W)，Li◎Li-1◎…◎L1◎ev(f) = ev(LiLi-1…L1f)
を、端末装置１０２（Ui+1）に送信する（ステップＳ４１０）。
【００９９】
一方、i > 1の場合（ステップＳ４０５；Ｎｏ）、行列受信部２０４は、端末装置１０２（Ui-1）から送信された行列および列ベクトル
Li-1◎…◎L1◎e(W) = e(Li-1…L1W)，Li-1◎…◎L1◎ev(f) = ev(Li-1…L1f)
を受信する（ステップＳ４１１）。
【０１００】
すると、端末装置１０２（Ui）において、消去行列計算部２０５は、受信された行列のi列目を、秘密鍵siにより復号し、i行目を軸に当該復号された列をガウス消去する行列Liを計算し（ステップＳ４０７）、◎行列段階計算部２０６は、計算された行列Liと、受信された行列および列ベクトルと、から、
Li◎Li-1◎…◎L1◎e(W) = e(LiLi-1…L1W)，Li◎Li-1◎…◎L1◎ev(f) = ev(LiLi-1…L1f)
を計算し（ステップＳ４０８）、i < tである場合（ステップＳ４０９；Ｙｅｓ）、行列送信部２０７は、計算された行列および列ベクトル
Li◎Li-1◎…◎L1◎e(W) = e(LiLi-1…L1W)，Li◎Li-1◎…◎L1◎ev(f) = ev(LiLi-1…L1f)
を、端末装置１０２（Ui+1）に送信する（ステップＳ４１０）。
【０１０１】
一方、i = tである場合（ステップＳ４０９；Ｎｏ）、行列送信部２０７は、計算された行列および列ベクトル
Lt◎Lt-1◎…◎L1◎e(W) = e(LtLt-1…L1W)，Lt◎Lt-1◎…◎L1◎ev(f) = ev(LtLt-1…L1f)
を、制御装置１０３に送信する（ステップＳ４１２）。
【０１０２】
なお、i = tである場合、◎行列段階計算部２０６による行列の計算、ならびに、行列送信部２０７による行列の送信は、いずれも省略が可能である。
【０１０３】
すると、制御装置１０３において、行列受信部３０４は端末装置１０２（Ut）において計算された列ベクトル
ev(LtLt-1…L1f)
を受信する（ステップＳ４１３）。
【０１０４】
そして、求解部３０５が、秘密鍵svで
LtLt-1…L1f
に復号し、これを解ベクトルXとして（ステップＳ４１４）、本処理を終了する。
【０１０５】
このように処理を実行することで、各端末装置１０２における秘密情報を漏らさずに、当該秘密情報を用いた行列方程式を求解することが可能となる。
【０１０６】
なお、本発明の計算システム１０１において、制御装置１０３を、端末装置１０２（U1，…，Ut）のいずれかUkとすることができる。この場合、秘密鍵sv = sk，公開鍵pv = pkとすれば良い。
【実施例２】
【０１０７】
本実施形態は、上記実施形態を変形したものであり、計算システム１０１は、外部装置をさらに備えるように構成する。
【０１０８】
図５は、本実施形態に係る計算システム１０１の概要構成を示す模式図である。以下、本図を参照して説明する。
【０１０９】
本実施形態では、制御装置１０３からは、制御記憶部３０１と求解部３０５を省略し、そのかわりに、転送部３１１を追加する。
【０１１０】
外部装置５０１（V）は、外部記憶部５１１、行列受付部５１２、求解部５１３を備える。
【０１１１】
ここで、外部記憶部５１１には、ホモモルフィック暗号e(・,・)における秘密鍵svと公開鍵pvと、があらかじめ記憶される。すなわち、上記実施形態における制御記憶部３０１と同様の役割を果たす。外部装置５０１（V）は、公開鍵pvを、他者に対して公開している。
【０１１２】
本計算システムは、上記実施形態の行列方程式にかえて、［数２６］に示すように、端末装置１０２（U1，…，Ut）のそれぞれに記憶される秘密値を要素とする(t+1)行(t+1)列の行列Wと、ZPに含まれる要素からなる(t+1)行の列ベクトルfと、からなる行列方程式
W[j,i] = w[j,i] (1≦j≦t，1≦i≦t)；
W[t+1,i] = W[j,t+1] = 1 (1≦j≦t，1≦i≦t)；
W[t+1,t+1] = 0；
WX = f (mod P)
の解ベクトルXを求めるものとする。
【０１１３】
このため、ステップＳ４０３において、制御装置１０３のe生成部３０２は、端末装置１０２（U1，…，Ut）により公開された暗号化済値および公開鍵piと、外部装置５０１（V）により公開された公開鍵pvと、により、暗号化済行列e(W)と暗号化済ベクトルev(f)を、［数２７］に示すように、
e(W)[j,i] = e(pi,w[j,i]) (1≦j≦t，1≦i≦t)；
e(W)[t+1,i] = e(pi,1) (1≦i≦t)；
e(W)[j,t+1] = e(pv,1) (1≦j≦t)；
e(W)[t+1,t+1] = e(pv,0)；
ev(f)[j] = e(pv，f[j]) (1≦j≦t)
により生成する。
【０１１４】
さらに、制御装置１０３は、ステップＳ４１３において求解部３０５が求解を行うのにかえて、受信された行列および列ベクトル
Lt◎Lt-1…◎L1◎e(W) = e(LtLt-1…L1W)，ev(LtLt-1…L1f)
を、転送部３１１が、外部装置５０１（V）に転送する。
【０１１５】
図６は、外部装置５０１（V）が実行する外部処理の制御の流れを示す説明図である。以下、本図を参照して説明する。
【０１１６】
外部装置５０１（V）において、行列受付部５１２は、制御装置１０３から転送された行列および列ベクトル
Lt◎Lt-1…◎L1◎e(W) = e(LtLt-1…L1W)，ev(LtLt-1…L1f)
を受け付ける（ステップＳ６０１）。
【０１１７】
そして、消去行列計算部２０５は、受け付けられた行列のt+1列目を、秘密鍵svにより復号し、t+1行目を軸に当該復号された列をガウス消去する行列Lvを計算する（ステップＳ６０２）。Lvの計算は、Liの計算と同様に、掃き出し法を用いることができる。
【０１１８】
ついで、求解部３０５は、受信された列ベクトルを秘密鍵svで
LtLt-1…L1f
に復号して、これと計算された行列Lvと、から、乗算により、
LvLtLt-1…L1f
を計算して、これを解ベクトルXとし（ステップＳ６０３）、本処理を終了する。
【０１１９】
本実施形態によれば、上記実施例の行列方程式に類似する行列方程式を、それぞれが持つ秘密情報を漏洩させずに、求解することが可能となる。
【実施例３】
【０１２０】
本実施形態は、実施例２の態様に、さらに、その他の端末装置１０２（Ut+1，…，Um）ならびに中央装置を備えるように構成するものであり、u = mと設定したものである。
【０１２１】
図７は、本実施形態に係る計算システムの概要構成を示す模式図である。以下、本図を参照して説明する。
【０１２２】
本実施形態においては、t台の端末装置１０２（U1，…，Ut）ならびに制御装置１０３（U1，…，Utのいずれかの端末装置１０２により実現される。）からなる端末群７０１を含むm台の端末装置１０２（U1，…，Um）が、中央装置７０２、外部装置５０１と情報のやりとりを行い、端末群７０１の認証を外部装置５０１にて行うものである。
【０１２３】
本実施形態において、中央装置７０２は、値生成部７１１、値送信部７１２を備える。
【０１２４】
一方、端末群７０１は、実施例２の構成のほか、c生成部７３１、r計算部７３２、rc送信部７３３、b受信部７３４、f計算部７３５を備える。これらの要素は、制御装置１０３として機能する端末装置１０２（Uk）により実現されるのが典型的である。
【０１２５】
さらに、外部装置５０１は、rc受信部７５１、b選択部７５２、b送信部７５３、d計算部７５４、認証部７５５を備える。
【０１２６】
図８は、全端末装置１０２（U1，…，Um）の初期化を行う初期化処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【０１２７】
まず、中央装置７０２において、値生成部７１１は、、j = 1，…，tおよびi = 1，…，mのそれぞれについて、ZPから値w[j,i]をランダムに一様に生成する（ステップＳ８０１）。
【０１２８】
そして、値送信部７１２は、i = 1，…，mのそれぞれについて、値w[1,i]，…，w[t,i]を端末装置１０２（U[i]）に送信する（ステップＳ８０２）。
【０１２９】
すると、i = 1，…，mについて、端末装置１０２（Ui）が中央装置７０２から送信された値w[1,i]，…，w[t,i]を受信する（ステップＳ８０３）。
【０１３０】
そして、受信されたw[1,i]，…，w[t,i]を、当該端末装置１０２の秘密値w[1,i]，…，w[t,i]とし、y[1,i] = gw[1,i]，…，y[t,i] = gw[t,i]を当該端末装置１０２の公開値とする（ステップＳ８０４）。
【０１３１】
全端末装置１０２は、中央装置７０２から入手した秘密値を保持することによって、中央装置７０２による「保証」を受けたことになる。
【０１３２】
このような状況下で、t台の端末装置１０２からなる端末群７０１の匿名認証を行う手法について、以下説明する。
【０１３３】
図９は、認証処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【０１３４】
外部装置５０１による匿名認証を受けようとする端末群７０１において、c生成部７３１は、ZPから値c[0]，c[1]，…，c[m]をランダムに一様に生成する（ステップＳ９０１）。
【０１３５】
ついで、r計算部７３２は、生成された値c[0]，c[1]，…，c[m]と、公開された公開鍵と、から、j = 1，…，tのそれぞれについて、
r[j] = gc[0] Πi=1m y[j,i]c[i]
を計算する（ステップＳ９０２）。
【０１３６】
さらに、rc送信部７３３は、生成された値c[0]，c[1]，…，c[m]と、計算されたr[1]，…，r[t]と、を、外部装置５０１に送信する（ステップＳ９０３）。
【０１３７】
一方、外部装置５０１において、rc受信部７５１は、端末群７０１から送信されたc[0]，c[1]，…，c[m]と、r[1]，…，r[t]と、を受信する（ステップＳ９０４）。
【０１３８】
さらに、b選択部７５２は、ZPからbをランダムに選択する（ステップＳ９０５）。
【０１３９】
ついで、b送信部７５３は、選択されたbを、端末群７０１に送信する（ステップＳ９０６）。
【０１４０】
すると、端末群７０１において、b受信部７３４は、外部装置５０１から送信されたbを受信する（ステップＳ９０７）。
【０１４１】
さらに、j = 1，…，tのそれぞれについて、端末装置１０２（Ui）において、f計算部７３５は、
f[j] = c[0] + Σi=1t w[j,i]c[i]
を計算し、いずれかの端末装置１０２において
f[t+1] = b - Σi=t+1m c[i]
を計算する（ステップＳ９０８）。
【０１４２】
このように、端末群７０１において、行列W、列ベクトルfが用意できたこととなる。そこで、端末群７０１および外部装置５０１は、計算された列ベクトルfにより、上記実施例２の手法に基づいて、行列方程式
WX = f (mod P)
を求解する（ステップＳ９０９）。
【０１４３】
なお、この際には、列ベクトルfは、端末群７０１から外部装置５０１へ送受される。
【０１４４】
ついで、外部装置５０１において、d計算部７５４は、求解された結果により、j = 1，…，tのそれぞれについて、
d[j] = X[j]
とし、
d[0] = X[t+1]
とし、j = t+1，…，mのそれぞれについて
d[j] = c[j]
とする（ステップＳ９１０）。
【０１４５】
さらに、認証部７５５は、認証条件「受信されたr[1]，…，r[t]と、得られたd[0]，d[1]，…，d[m]と、に対して、j = 1，…，tのすべてについて、
r[j] = gd[0] Πi=1m y[j,i]d[i]
であり、かつ、
b = Σi=1m d[i] (mod P)
である」が成立する場合（ステップＳ９１１；Ｙｅｓ）、端末群７０１の匿名認証を成功させ（ステップＳ９１２）、成立しない場合（ステップＳ９１１；Ｎｏ）、端末群７０１の匿名認証を失敗させる（ステップＳ９１３）。
【０１４６】
本実施形態によれば、行列方程式の求解を分散して行うことにより、中央装置７０２から端末装置１０２が入手した秘密情報を他者に明かさずに、匿名グループ認証を行うことができるようになる。
【産業上の利用可能性】
【０１４７】
本発明によれば、行列方程式の求解を分散して行って、匿名グループ認証を行うのに好適な、計算システム、計算方法、ならびに、これらをコンピュータ上にて実現するためのプログラムを提供することができる。
【符号の説明】
【０１４８】
１０１ 計算システム
１０２ 端末装置
１０３ 制御装置
２０１ 端末記憶部
２０２ 端末暗号化部
２０３ 端末公開部
２０４ 行列受信部
２０５ 消去行列計算部
２０６ ◎行列段階計算部
２０７ 行列送信部
３０１ 制御記憶部
３０２ e生成部
３０３ 行列送信部
３０４ 行列受信部
３０５ 求解部
３１１ 転送部
５０１ 外部装置
５１１ 外部記憶部
５１２ 行列受付部
５１３ 求解部
７０１ 端末群
７０２ 中央装置
７１１ 値生成部
７１２ 値送信部
７３１ c生成部
７３２ r計算部
７３３ rc送信部
７３４ b受信部
７３５ f計算部
７５１ rc受信部
７５２ b選択部
７５３ b送信部
７５４ d計算部
７５５ 認証部
【技術分野】
【０００１】
本発明は、行列方程式の求解を分散して行って、匿名グループ認証を行うのに好適な、計算システム、計算方法、ならびに、これらをコンピュータ上にて実現するためのプログラムに関する。
【背景技術】
【０００２】
従来、認証技術の分野では、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, ２００５年
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、このような認証手法においては、通信の複雑さを抑制して、通信量を減らしたい、との要望は大きい。
【０００６】
このほか、このような認証方法における行列方程式の求解を、適切に行う必要もある。
【０００７】
本発明は、このような課題を解決するもので、行列方程式の求解を分散して行って、匿名グループ認証を行うのに好適な、計算システム、計算方法、ならびに、これらをコンピュータ上にて実現するためのプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記の課題を解決するため、本発明の原理にしたがい、以下の発明を開示する。
【０００９】
本発明の第１の観点に係る計算システムは、端末装置U1，…，Utと、制御装置と、を有する。
【００１０】
ここで、列ベクトルvのj行目の要素をv[j]と表記する。
【００１１】
【数１９】
【００１２】
行列Aのj行i列目の要素をA[j,i]と表記する。
【００１３】
【数２０】
【００１４】
素数Pを法とする有限体ZPの要素aを、加法群(ZP,+)からPを法とする生成元gの巡回乗法群G = 〈g〉へのホモモルフィック暗号e(・,・)を用いて、公開鍵pにより暗号化した結果を、e(p,a)と表記する。
【００１５】
すると、ZPの任意の要素x,yと任意の公開鍵pは、
e(p,x)e(p,y) = e(p,x+y)
を満たす。
【００１６】
さらに、h行k列の行列Aのj行i列の要素A[j,i] = aj,iを、公開鍵p1，…，pkにより暗号化した行列e(A)を
e(A)[j,i] = e(pi,aj,i)
と定義する。
【００１７】
【数２１】
【００１８】
また、h行の列ベクトルvのj行の要素v[j]を、公開鍵piにより暗号化した列ベクトルei(v)を、
ei(v)[j] = e(pi,v[j])
と定義する。
【００１９】
そして、H行u列の行列Bのh行i列の要素B[h,i] = bh,iと、u行K列の行列Cのi行k列の要素C[i,k] = ci,kと、についての演算B◎Cを、
B◎C[h,k] = Πi=1u C[i,k]B[h,i]
と定義する。
【００２０】
【数２２】
【００２１】
すると、行列A，Bについての演算B◎e(A)は、
B◎e(A)[h,k] = e(pk,Σi=1u B[h,i]A[i,k]) = Πi=1u e(pk,A[i,k])B[h,i]
すなわち
B◎e(A) = e(BA)
を満たす。
【００２２】
また、公開鍵piおよび列ベクトルvについての演算B◎ei(v)は、
B◎ei(v) = ei(Bv)
を満たす。
【００２３】
さて、i = 1，…，uのそれぞれについて、端末装置Uiは、有限体ZPに含まれる秘密値w[1,i]，…，w[u,i]と、ホモモルフィック暗号e(・,・)における秘密鍵siと公開鍵piと、があらかじめ記憶される端末記憶部を備える。
【００２４】
そして、制御装置は、ホモモルフィック暗号e(・,・)における秘密鍵svと公開鍵pvと、があらかじめ記憶される制御記憶部を備える。
【００２５】
さらに、当該計算システムは、端末装置U1，…，Utのそれぞれに記憶される秘密値を要素とするt行t列の行列Wと、ZPに含まれる要素からなるt行の列ベクトルfと、からなる行列方程式
W[j,i] = w[j,i]；
WX = f (mod P)
の解ベクトルXを求める。
【００２６】
【数２３】
【００２７】
ここで、i = 1，…，tのそれぞれについて、端末装置Uiは、秘密値w[1,i]，…，w[t,i]を、公開鍵piにより暗号化した暗号化済値
e(pi,w[1,i])，…，e(pi,w[t,i])
を計算する端末暗号化部、計算された暗号化済値を公開する端末公開部を備える。
【００２８】
一方、制御装置は、端末装置U1，…，Utにより公開された暗号化済値から、暗号化済行列e(W)および暗号化済ベクトルev(f)を
e(W)[j,i] = e(pi,w[j,i]) (1≦i≦t，1≦j≦t)；
ev(f)[j] = e(pv，f[j]) (1≦j≦t)
により生成するe生成部を備える。
【００２９】
【数２４】
【００３０】
【数２５】
【００３１】
さらに、制御装置は、生成された行列e(W)および当該列ベクトルev(f)を端末装置U1に送信する行列送信部を備える。
【００３２】
さらに、i = 1，…，tのそれぞれについて、端末装置Uiは、i = 1の場合、制御装置から送信された行列および列ベクトル
e(W)，ev(f)
を受信し、i > 1の場合、端末装置Ui-1から送信された行列および列ベクトル
Li-1◎…◎L1◎e(W) = e(Li-1…L1W)，Li-1◎…◎L1◎ev(f) = ev(Li-1…L1f)
を受信する行列受信部、受信された行列のi列目を、秘密鍵siにより復号し、i行目を軸に当該復号された列をガウス消去する行列Liを計算する消去行列計算部、計算された行列Liと、受信された行列および列ベクトルと、から、
Li◎Li-1◎…◎L1◎e(W) = e(LiLi-1…L1W)，Li◎Li-1◎…◎L1◎ev(f) = ev(LiLi-1…L1f)
を計算する◎行列段階計算部、計算された行列および列ベクトル
Li◎Li-1◎…◎L1◎e(W) = e(LiLi-1…L1W)，Li◎Li-1◎…◎L1◎ev(f) = ev(LiLi-1…L1f)
を、i < tの場合、端末装置Ui+1に送信する行列送信部を備える。
【００３３】
一方、制御装置は、端末装置Utにおいて計算された列ベクトル
ev(LtLt-1…L1f)
を秘密鍵svで
LtLt-1…L1f
に復号して、解ベクトルXとする求解部を備える。
【００３４】
また、本発明の計算システムにおいて、制御装置は、端末装置U1，…，UtのいずれかUkであり、秘密鍵sv = sk，公開鍵pv = pkとするように構成することができる。
【００３５】
また、本発明の計算システムは、外部装置をさらに備え、制御装置が制御記憶部を備えるのにかえて、外部装置は、ホモモルフィック暗号e(・,・)における秘密鍵svと公開鍵pvと、があらかじめ記憶される外部記憶部を備え、以下のように構成することができる。
【００３６】
当該計算システムは、当該t行t列の行列Wと、当該t行の列ベクトルfと、からなる行列方程式を解くのにかえて、端末装置U1，…，Utのそれぞれに記憶される秘密値を要素とする(t+1)行(t+1)列の行列Wと、ZPに含まれる要素からなる(t+1)行の列ベクトルfと、からなる行列方程式
W[j,i] = w[j,i] (1≦j≦t，1≦i≦t)；
W[t+1,i] = W[j,t+1] = 1 (1≦j≦t，1≦i≦t)；
W[t+1,t+1] = 0；
WX = f (mod P)
の解ベクトルXを求める。
【００３７】
【数２６】
【００３８】
そして、制御装置において、e生成部は、端末装置U1，…，Utにより公開された暗号化済値および公開鍵piと、外部装置により公開された公開鍵pvと、により、暗号化済行列e(W)と暗号化済ベクトルev(f)を、
e(W)[j,i] = e(pi,w[j,i]) (1≦j≦t，1≦i≦t)；
e(W)[t+1,i] = e(pi,1) (1≦i≦t)；
e(W)[j,t+1] = e(pv,1) (1≦j≦t)；
e(W)[t+1,t+1] = e(pv,0)；
ev(f)[j] = e(pv，f[j]) (1≦j≦t)
により生成する。
【００３９】
【数２７】
【００４０】
一方、制御装置は、求解部にかえて端末装置Utにおいて計算された行列および列ベクトル
Lt◎Lt-1…◎L1◎e(W) = e(LtLt-1…L1W)，ev(LtLt-1…L1f)
を、外部装置に転送する転送部を備える。
【００４１】
さらに、外部装置は、制御装置から転送された行列および列ベクトル
Lt◎Lt-1…◎L1◎e(W) = e(LtLt-1…L1W)，ev(LtLt-1…L1f)
を受け付ける行列受付部、受け付けられた行列のt+1列目を、秘密鍵svにより復号し、t+1行目を軸に当該復号された列をガウス消去する行列Lvを計算する消去行列計算部、受信された列ベクトルを秘密鍵svで
LtLt-1…L1f
に復号して、これと計算された行列Lvと、から、
LvLtLt-1…L1f
を計算して、これを解ベクトルXとする求解部を備える。
【００４２】
また、本発明の計算システムは、端末装置Ut+1，…，Umと、中央装置と、をさらに備え、以下のように構成することができる。
【００４３】
すなわち、中央装置は、j = 1，…，tおよびi = 1，…，mのそれぞれについて、ZPから値w[j,i]をランダムに一様に生成する値生成部、i = 1，…，mのそれぞれについて、値w[1,i]，…，w[t,i]を端末装置U[i]に送信する値送信部を備える。
【００４４】
一方、i = 1，…，mについて、端末装置Uiは、中央装置から送信された値w[1,i]，…，w[t,i]を受信する秘密値受信部を備え、受信されたw[1,i]，…，w[t,i]を、当該端末装置の秘密値w[1,i]，…，w[t,i]とし、y[1,i] = gw[1,i]，…，y[t,i] = gw[t,i]を当該端末装置の公開値とする。
【００４５】
さらに、端末装置U1，…，Utおよび制御装置は、端末群を構成し、当該端末群は、ZPから値c[0]，c[1]，…，c[m]をランダムに一様に生成するc生成部、生成された値c[0]，c[1]，…，c[m]と、公開された公開鍵と、から、j = 1，…，tのそれぞれについて、
r[j] = gc[0] Πi=1m y[j,i]c[i]
を計算するr計算部、生成された値c[0]，c[1]，…，c[m]と、計算されたr[1]，…，r[t]を、外部装置に送信するrc送信部を備える。
【００４６】
そして、外部装置は、端末群から送信されたc[0]，c[1]，…，c[m]と、r[1]，…，r[t]とを受信するrc受信部、ZPからbをランダムに選択するb選択部、選択されたbを、端末群に送信するb送信部を備える。
【００４７】
一方、端末群は、外部装置から送信されたbを受信するb受信部、j = 1，…，tのそれぞれについて、端末装置Uiにおいて、
f[j] = c[0] + Σi=1t w[j,i]c[i]
を計算し、端末群のいずれかの端末装置において
f[t+1] = b - Σi=t+1m c[i]
を計算するf計算部を備える。
【００４８】
さらに、端末群および外部装置は、計算された列ベクトルfにより、当該行列方程式
WX = f (mod P)
を求解する。
【００４９】
そして、外部装置は、求解された結果により、j = 1，…，tのそれぞれについて、
d[j] = X[j]
とし、
d[0] = X[t+1]
とし、j = t+1，…，mのそれぞれについて
d[j] = c[j]
とするd計算部、受信されたr[1]，…，r[t]と、得られたd[0]，d[1]，…，d[m]と、に対して、j = 1，…，tのすべてについて、
r[j] = gd[0] Πi=1m y[j,i]d[i]
が成立し、かつ、
b = Σi=1m d[i] (mod P)
が成立する場合、端末群の匿名認証を成功させる認証部を備える。
【００５０】
本発明のその他の観点に係る計算方法は、上記計算システムが実行する計算方法である。
【００５１】
本発明のその他の観点に係るプログラムは、コンピュータを、上記の計算システムの端末装置、制御装置、外部装置、もしくは、中央装置の各部として機能させるように構成する。
【００５２】
なお、上記のプログラムは、コンピュータ読取可能な情報記録媒体（コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、または、半導体メモリを含む。）に記録することができる。
【００５３】
そして、上記の情報記録媒体は、コンピュータとは独立して配布、販売することができるほか、インターネット等のコンピュータ通信網を介して上記のプログラムそのものを配布、販売することができる。
【発明の効果】
【００５４】
本発明によれば、行列方程式の求解を分散して行って、匿名グループ認証を行うのに好適な、計算システム、計算方法、ならびに、これらをコンピュータ上にて実現するためのプログラムを提供することができる。
【図面の簡単な説明】
【００５５】
【図１】実施例１に係る計算システムの概要構成を示す説明図である。
【図２】i番目の端末装置Uiの概要構成を示す説明図である。
【図３】制御装置の概要構成を示す説明図である。
【図４】本実施形態に係る求解処理の制御の流れを示すフローチャートである。
【図５】実施例２に係る計算システムの概要構成を示す模式図である。
【図６】外部装置が実行する外部処理の制御の流れを示す説明図である。
【図７】実施例３に係る計算システムの概要構成を示す模式図である。
【図８】全端末装置U1，…，Umの初期化を行う初期化処理の制御の流れを示すフローチャートである。
【図９】認証処理の制御の流れを示すフローチャートである。
【発明を実施するための形態】
【００５６】
以下に本発明の実施形態を説明する。なお、以下にあげる実施形態は、説明のためのものであり、本発明の範囲を制限するものではない。したがって、当業者であれば、これらの各要素または全要素を、これと均等なものに置換した実施形態を採用することが可能であるが、これらの実施形態も、本発明の範囲に含まれる。
【００５７】
なお、以下の実施形態において実現される各装置は、いずれも、他の装置と通信可能なコンピュータにおいて、所定のプログラムを実行することによって実現されるものとするのが典型的であるが、電子回路等のハードウェアによって、各装置を実現することとしても良い。
【実施例１】
【００５８】
図１は、本実施形態に係る計算システムの概要構成を示す説明図である。以下、本図を参照して説明する。
【００５９】
本図に示す計算システム１０１は、t台の端末装置１０２（それぞれU1，…，Utと呼ぶ。）と、制御装置１０３と、を備え、行列方程式の求解を行う。
【００６０】
以下、理解を容易にするため、［数１９］に示すように、一般に、列ベクトルvのj行目の要素をv[j]と表記する。
【００６１】
また、［数２０］に示すように、一般に、行列Aのj行i列目の要素をA[j,i]と表記する。
【００６２】
さらに、素数Pを法とする有限体ZPの要素aを、加法群(ZP,+)からPを法とする生成元gの巡回乗法群G = 〈g〉へのホモモルフィック暗号e(・,・)を用いて、公開鍵pにより暗号化した結果を、e(p,a)と表記する。
【００６３】
このようなホモモルフィック暗号としては、現在広く用いられている公開鍵暗号の技術を適用することができる。
【００６４】
すると、ZPの任意の要素x,yと任意の公開鍵pは、
e(p,x)e(p,y) = e(p,x+y)
を満たす。
【００６５】
ここで、h行k列の行列Aのj行i列の要素A[j,i] = aj,iを、公開鍵p1，…，pkにより暗号化した行列e(A)を、［数２１］のように、
e(A)[j,i] = e(pi,aj,i)
と定義する。
【００６６】
また、h行の列ベクトルvのj行の要素v[j]を、公開鍵piにより暗号化した列ベクトルei(v)を、
ei(v)[j] = e(pi,v[j])
と定義する。
【００６７】
さらに、H行u列の行列Bのh行i列の要素B[h,i] = bh,iと、u行K列の行列Cのi行k列の要素C[i,k] = ci,kと、についての演算B◎Cを、［数２２］のように、
B◎C[h,k] = Πi=1u C[i,k]B[h,i]
と定義する。
【００６８】
すると、行列A，Bについての演算B◎e(A)は、
B◎e(A)[h,k] = e(pk,Σi=1u B[h,i]A[i,k]) = Πi=1u e(pk,A[i,k])B[h,i]
すなわち
B◎e(A) = e(BA)
を満たすことがわかる。
【００６９】
また、公開鍵piおよび列ベクトルvについての演算B◎ei(v)は、
B◎ei(v) = ei(Bv)
を満たすこととなる。
【００７０】
図２は、i = 1，…，uのそれぞれに対して、i番目の端末装置１０２（Ui）の概要構成を示す説明図である。以下、本図を参照して説明する。
【００７１】
端末装置１０２（Ui）は、端末記憶部２０１、端末暗号化部２０２、端末公開部２０３、行列受信部２０４、消去行列計算部２０５、◎行列段階計算部２０６、行列送信部２０７を備える。
【００７２】
ここで、端末記憶部２０１には、有限体ZPに含まれる秘密値w[1,i]，…，w[u,i]（図では「w[*,i]」と表記する。）と、ホモモルフィック暗号e(・,・)における秘密鍵siと公開鍵piと、があらかじめ記憶される。
【００７３】
ここで、秘密値w[1,i]，…，w[u,i]と、秘密鍵siと、は、いずれも当該端末装置１０２（Ui）が秘密に記憶するものであり、他者に対して公開されることはない。
【００７４】
一方、公開鍵piは、秘密鍵siと対をなすものであるが、当該端末装置１０２（Ui）は、公開鍵piを、他者に対して公開することとなる。
【００７５】
ここで、理解を容易にするため、端末装置１０２（Ui）の他の要素については、後述することとし、以下では、制御装置１０３について説明する。
【００７６】
図３は、制御装置１０３の概要構成を示す説明図である。以下、本図を参照して説明する。
【００７７】
制御装置１０３は、制御記憶部３０１、e生成部３０２、行列送信部３０３、行列受信部３０４、求解部３０５を備える。
【００７８】
制御記憶部３０１には、ホモモルフィック暗号e(・,・)における秘密鍵svと公開鍵pvと、があらかじめ記憶される。
【００７９】
ここで、秘密鍵svは他者に対して公開されることはないが、これと対をなす公開鍵pvは、他者に対して公開される。
【００８０】
ここで、本計算システム１０１は、端末装置１０２（U1，…，Ut）のそれぞれに記憶される秘密値を要素とするt行t列の行列Wと、ZPに含まれる要素からなるt行の列ベクトルfと、からなる、［数２３］に示すような行列方程式
W[j,i] = w[j,i]；
WX = f (mod P)
の解ベクトルXを求める。なお、一般に、t≦uである。
【００８１】
上記のように、行列Wの各要素は、いずれかの端末装置１０２に秘密に記憶されるものである。したがって、この方程式を、直接解くことはできない。本実施形態は、秘密にすべき情報を外部に漏らさずに、ベクトルfと行列Wについての、Pを法とする行列方程式を求解する点に特徴がある。
【００８２】
以下、端末装置１０２および制御装置１０３の各部が実行する求解処理について、詳細に説明する。図４は、本実施形態に係る求解処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【００８３】
まず、i = 1，…，tのそれぞれについて、端末装置１０２（Ui）において、端末暗号化部２０２は、秘密値w[1,i]，…，w[t,i]を、公開鍵piにより暗号化した暗号化済値
e(pi,w[1,i])，…，e(pi,w[t,i])
を計算する（ステップＳ４０１）。
【００８４】
上記のように、秘密値w[1,i]，…，w[t,i]は、行列方程式の行列の要素をなすが、他者に対して秘密にされる。これを、自身の公開鍵piで暗号化するのである。
【００８５】
一方、端末公開部２０３は、計算された暗号化済値を公開する（ステップＳ４０２）。各端末装置１０２が公開した暗号化済値は、他の端末装置１０２および制御装置１０３で知得可能となる。公開の手法としては、装置間の通信を利用するのが典型的であるが、共有記憶域を設け、ここに対して読み書きを行うことによって、他者に公開することとしても良い。
【００８６】
さらに、制御装置１０３において、e生成部３０２は、端末装置１０２（U1，…，Ut）により公開された暗号化済値から、暗号化済行列e(W)および暗号化済ベクトルev(f)を、［数２４］［数２５］により、
e(W)[j,i] = e(pi,w[j,i]) (1≦i≦t，1≦j≦t)；
ev(f)[j] = e(pv，f[j]) (1≦j≦t)
のように生成する（ステップＳ４０３）。
【００８７】
上記のように、e(pi,w[j,i])は、各端末装置１０２によって公開された情報であり、これを並べることによって、行列e(W)を生成する。
【００８８】
一方、fは解くべき行列方程式に含まれるベクトルであり、各要素を、自身の公開鍵pvで暗号化するのである。
【００８９】
さらに、制御装置１０３において、行列送信部３０３は、生成された行列e(W)および当該列ベクトルev(f)を端末装置１０２（U1）に送信する（ステップＳ４０４）。
【００９０】
すると、i = 1，…，tのそれぞれについて、端末装置１０２（Ui）は、以下のように処理を行う。
【００９１】
すなわち、端末装置１０２（Ui）の行列受信部２０４は、i = 1の場合（ステップＳ４０５；Ｙｅｓ）、制御装置１０３から送信された行列および列ベクトル
e(W)，ev(f)
を受信する（ステップＳ４０６）。
【００９２】
ついで、消去行列計算部２０５は、受信された行列のi列目を、秘密鍵siにより復号し、i行目を軸に当該復号された列をガウス消去する行列Liを計算する（ステップＳ４０７）。
【００９３】
i = 1の場合、受信された行列のi列目は、順に、e(p1,w[1,1])，e(p1,w[2,1])，…，e(p1,w[t,1])であるから、秘密鍵で復号することができ、w[1,1]，w[2,1]，…，w[t,1]からなる列ベクトルが得られる。
【００９４】
i = 1の場合、行列Liを、この列ベクトルに乗じると、w[1,1]，w[2,1]，…，w[t,1]からなる列ベクトルのi行目の要素は１となり、その他の要素は０となる。
【００９５】
このような行列Liは、w[1,1]，w[2,1]，…，w[t,1]からなる列ベクトルが与えられれば、掃出し法によって、計算することができる。
【００９６】
ついで、◎行列段階計算部２０６は、計算された行列Liと、受信された行列および列ベクトルと、から、
Li◎Li-1◎…◎L1◎e(W) = e(LiLi-1…L1W)，Li◎Li-1◎…◎L1◎ev(f) = ev(LiLi-1…L1f)
を計算する（ステップＳ４０８）。
【００９７】
上記のように、◎演算については、
L1◎e(W) = e(L1W)，
L1◎ev(f) = ev(L1f)
が成立する。すなわち、◎演算の左側の項L1は、◎演算の右側の項のe(W)，ev(f)の括弧の中に、乗算として繰り込むことができるのである。
【００９８】
ついで、i = 1のように、i < tである場合（ステップＳ４０９；Ｙｅｓ）、行列送信部２０７は、計算された行列および列ベクトル
Li◎Li-1◎…◎L1◎e(W) = e(LiLi-1…L1W)，Li◎Li-1◎…◎L1◎ev(f) = ev(LiLi-1…L1f)
を、端末装置１０２（Ui+1）に送信する（ステップＳ４１０）。
【００９９】
一方、i > 1の場合（ステップＳ４０５；Ｎｏ）、行列受信部２０４は、端末装置１０２（Ui-1）から送信された行列および列ベクトル
Li-1◎…◎L1◎e(W) = e(Li-1…L1W)，Li-1◎…◎L1◎ev(f) = ev(Li-1…L1f)
を受信する（ステップＳ４１１）。
【０１００】
すると、端末装置１０２（Ui）において、消去行列計算部２０５は、受信された行列のi列目を、秘密鍵siにより復号し、i行目を軸に当該復号された列をガウス消去する行列Liを計算し（ステップＳ４０７）、◎行列段階計算部２０６は、計算された行列Liと、受信された行列および列ベクトルと、から、
Li◎Li-1◎…◎L1◎e(W) = e(LiLi-1…L1W)，Li◎Li-1◎…◎L1◎ev(f) = ev(LiLi-1…L1f)
を計算し（ステップＳ４０８）、i < tである場合（ステップＳ４０９；Ｙｅｓ）、行列送信部２０７は、計算された行列および列ベクトル
Li◎Li-1◎…◎L1◎e(W) = e(LiLi-1…L1W)，Li◎Li-1◎…◎L1◎ev(f) = ev(LiLi-1…L1f)
を、端末装置１０２（Ui+1）に送信する（ステップＳ４１０）。
【０１０１】
一方、i = tである場合（ステップＳ４０９；Ｎｏ）、行列送信部２０７は、計算された行列および列ベクトル
Lt◎Lt-1◎…◎L1◎e(W) = e(LtLt-1…L1W)，Lt◎Lt-1◎…◎L1◎ev(f) = ev(LtLt-1…L1f)
を、制御装置１０３に送信する（ステップＳ４１２）。
【０１０２】
なお、i = tである場合、◎行列段階計算部２０６による行列の計算、ならびに、行列送信部２０７による行列の送信は、いずれも省略が可能である。
【０１０３】
すると、制御装置１０３において、行列受信部３０４は端末装置１０２（Ut）において計算された列ベクトル
ev(LtLt-1…L1f)
を受信する（ステップＳ４１３）。
【０１０４】
そして、求解部３０５が、秘密鍵svで
LtLt-1…L1f
に復号し、これを解ベクトルXとして（ステップＳ４１４）、本処理を終了する。
【０１０５】
このように処理を実行することで、各端末装置１０２における秘密情報を漏らさずに、当該秘密情報を用いた行列方程式を求解することが可能となる。
【０１０６】
なお、本発明の計算システム１０１において、制御装置１０３を、端末装置１０２（U1，…，Ut）のいずれかUkとすることができる。この場合、秘密鍵sv = sk，公開鍵pv = pkとすれば良い。
【実施例２】
【０１０７】
本実施形態は、上記実施形態を変形したものであり、計算システム１０１は、外部装置をさらに備えるように構成する。
【０１０８】
図５は、本実施形態に係る計算システム１０１の概要構成を示す模式図である。以下、本図を参照して説明する。
【０１０９】
本実施形態では、制御装置１０３からは、制御記憶部３０１と求解部３０５を省略し、そのかわりに、転送部３１１を追加する。
【０１１０】
外部装置５０１（V）は、外部記憶部５１１、行列受付部５１２、求解部５１３を備える。
【０１１１】
ここで、外部記憶部５１１には、ホモモルフィック暗号e(・,・)における秘密鍵svと公開鍵pvと、があらかじめ記憶される。すなわち、上記実施形態における制御記憶部３０１と同様の役割を果たす。外部装置５０１（V）は、公開鍵pvを、他者に対して公開している。
【０１１２】
本計算システムは、上記実施形態の行列方程式にかえて、［数２６］に示すように、端末装置１０２（U1，…，Ut）のそれぞれに記憶される秘密値を要素とする(t+1)行(t+1)列の行列Wと、ZPに含まれる要素からなる(t+1)行の列ベクトルfと、からなる行列方程式
W[j,i] = w[j,i] (1≦j≦t，1≦i≦t)；
W[t+1,i] = W[j,t+1] = 1 (1≦j≦t，1≦i≦t)；
W[t+1,t+1] = 0；
WX = f (mod P)
の解ベクトルXを求めるものとする。
【０１１３】
このため、ステップＳ４０３において、制御装置１０３のe生成部３０２は、端末装置１０２（U1，…，Ut）により公開された暗号化済値および公開鍵piと、外部装置５０１（V）により公開された公開鍵pvと、により、暗号化済行列e(W)と暗号化済ベクトルev(f)を、［数２７］に示すように、
e(W)[j,i] = e(pi,w[j,i]) (1≦j≦t，1≦i≦t)；
e(W)[t+1,i] = e(pi,1) (1≦i≦t)；
e(W)[j,t+1] = e(pv,1) (1≦j≦t)；
e(W)[t+1,t+1] = e(pv,0)；
ev(f)[j] = e(pv，f[j]) (1≦j≦t)
により生成する。
【０１１４】
さらに、制御装置１０３は、ステップＳ４１３において求解部３０５が求解を行うのにかえて、受信された行列および列ベクトル
Lt◎Lt-1…◎L1◎e(W) = e(LtLt-1…L1W)，ev(LtLt-1…L1f)
を、転送部３１１が、外部装置５０１（V）に転送する。
【０１１５】
図６は、外部装置５０１（V）が実行する外部処理の制御の流れを示す説明図である。以下、本図を参照して説明する。
【０１１６】
外部装置５０１（V）において、行列受付部５１２は、制御装置１０３から転送された行列および列ベクトル
Lt◎Lt-1…◎L1◎e(W) = e(LtLt-1…L1W)，ev(LtLt-1…L1f)
を受け付ける（ステップＳ６０１）。
【０１１７】
そして、消去行列計算部２０５は、受け付けられた行列のt+1列目を、秘密鍵svにより復号し、t+1行目を軸に当該復号された列をガウス消去する行列Lvを計算する（ステップＳ６０２）。Lvの計算は、Liの計算と同様に、掃き出し法を用いることができる。
【０１１８】
ついで、求解部３０５は、受信された列ベクトルを秘密鍵svで
LtLt-1…L1f
に復号して、これと計算された行列Lvと、から、乗算により、
LvLtLt-1…L1f
を計算して、これを解ベクトルXとし（ステップＳ６０３）、本処理を終了する。
【０１１９】
本実施形態によれば、上記実施例の行列方程式に類似する行列方程式を、それぞれが持つ秘密情報を漏洩させずに、求解することが可能となる。
【実施例３】
【０１２０】
本実施形態は、実施例２の態様に、さらに、その他の端末装置１０２（Ut+1，…，Um）ならびに中央装置を備えるように構成するものであり、u = mと設定したものである。
【０１２１】
図７は、本実施形態に係る計算システムの概要構成を示す模式図である。以下、本図を参照して説明する。
【０１２２】
本実施形態においては、t台の端末装置１０２（U1，…，Ut）ならびに制御装置１０３（U1，…，Utのいずれかの端末装置１０２により実現される。）からなる端末群７０１を含むm台の端末装置１０２（U1，…，Um）が、中央装置７０２、外部装置５０１と情報のやりとりを行い、端末群７０１の認証を外部装置５０１にて行うものである。
【０１２３】
本実施形態において、中央装置７０２は、値生成部７１１、値送信部７１２を備える。
【０１２４】
一方、端末群７０１は、実施例２の構成のほか、c生成部７３１、r計算部７３２、rc送信部７３３、b受信部７３４、f計算部７３５を備える。これらの要素は、制御装置１０３として機能する端末装置１０２（Uk）により実現されるのが典型的である。
【０１２５】
さらに、外部装置５０１は、rc受信部７５１、b選択部７５２、b送信部７５３、d計算部７５４、認証部７５５を備える。
【０１２６】
図８は、全端末装置１０２（U1，…，Um）の初期化を行う初期化処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【０１２７】
まず、中央装置７０２において、値生成部７１１は、、j = 1，…，tおよびi = 1，…，mのそれぞれについて、ZPから値w[j,i]をランダムに一様に生成する（ステップＳ８０１）。
【０１２８】
そして、値送信部７１２は、i = 1，…，mのそれぞれについて、値w[1,i]，…，w[t,i]を端末装置１０２（U[i]）に送信する（ステップＳ８０２）。
【０１２９】
すると、i = 1，…，mについて、端末装置１０２（Ui）が中央装置７０２から送信された値w[1,i]，…，w[t,i]を受信する（ステップＳ８０３）。
【０１３０】
そして、受信されたw[1,i]，…，w[t,i]を、当該端末装置１０２の秘密値w[1,i]，…，w[t,i]とし、y[1,i] = gw[1,i]，…，y[t,i] = gw[t,i]を当該端末装置１０２の公開値とする（ステップＳ８０４）。
【０１３１】
全端末装置１０２は、中央装置７０２から入手した秘密値を保持することによって、中央装置７０２による「保証」を受けたことになる。
【０１３２】
このような状況下で、t台の端末装置１０２からなる端末群７０１の匿名認証を行う手法について、以下説明する。
【０１３３】
図９は、認証処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。
【０１３４】
外部装置５０１による匿名認証を受けようとする端末群７０１において、c生成部７３１は、ZPから値c[0]，c[1]，…，c[m]をランダムに一様に生成する（ステップＳ９０１）。
【０１３５】
ついで、r計算部７３２は、生成された値c[0]，c[1]，…，c[m]と、公開された公開鍵と、から、j = 1，…，tのそれぞれについて、
r[j] = gc[0] Πi=1m y[j,i]c[i]
を計算する（ステップＳ９０２）。
【０１３６】
さらに、rc送信部７３３は、生成された値c[0]，c[1]，…，c[m]と、計算されたr[1]，…，r[t]と、を、外部装置５０１に送信する（ステップＳ９０３）。
【０１３７】
一方、外部装置５０１において、rc受信部７５１は、端末群７０１から送信されたc[0]，c[1]，…，c[m]と、r[1]，…，r[t]と、を受信する（ステップＳ９０４）。
【０１３８】
さらに、b選択部７５２は、ZPからbをランダムに選択する（ステップＳ９０５）。
【０１３９】
ついで、b送信部７５３は、選択されたbを、端末群７０１に送信する（ステップＳ９０６）。
【０１４０】
すると、端末群７０１において、b受信部７３４は、外部装置５０１から送信されたbを受信する（ステップＳ９０７）。
【０１４１】
さらに、j = 1，…，tのそれぞれについて、端末装置１０２（Ui）において、f計算部７３５は、
f[j] = c[0] + Σi=1t w[j,i]c[i]
を計算し、いずれかの端末装置１０２において
f[t+1] = b - Σi=t+1m c[i]
を計算する（ステップＳ９０８）。
【０１４２】
このように、端末群７０１において、行列W、列ベクトルfが用意できたこととなる。そこで、端末群７０１および外部装置５０１は、計算された列ベクトルfにより、上記実施例２の手法に基づいて、行列方程式
WX = f (mod P)
を求解する（ステップＳ９０９）。
【０１４３】
なお、この際には、列ベクトルfは、端末群７０１から外部装置５０１へ送受される。
【０１４４】
ついで、外部装置５０１において、d計算部７５４は、求解された結果により、j = 1，…，tのそれぞれについて、
d[j] = X[j]
とし、
d[0] = X[t+1]
とし、j = t+1，…，mのそれぞれについて
d[j] = c[j]
とする（ステップＳ９１０）。
【０１４５】
さらに、認証部７５５は、認証条件「受信されたr[1]，…，r[t]と、得られたd[0]，d[1]，…，d[m]と、に対して、j = 1，…，tのすべてについて、
r[j] = gd[0] Πi=1m y[j,i]d[i]
であり、かつ、
b = Σi=1m d[i] (mod P)
である」が成立する場合（ステップＳ９１１；Ｙｅｓ）、端末群７０１の匿名認証を成功させ（ステップＳ９１２）、成立しない場合（ステップＳ９１１；Ｎｏ）、端末群７０１の匿名認証を失敗させる（ステップＳ９１３）。
【０１４６】
本実施形態によれば、行列方程式の求解を分散して行うことにより、中央装置７０２から端末装置１０２が入手した秘密情報を他者に明かさずに、匿名グループ認証を行うことができるようになる。
【産業上の利用可能性】
【０１４７】
本発明によれば、行列方程式の求解を分散して行って、匿名グループ認証を行うのに好適な、計算システム、計算方法、ならびに、これらをコンピュータ上にて実現するためのプログラムを提供することができる。
【符号の説明】
【０１４８】
１０１ 計算システム
１０２ 端末装置
１０３ 制御装置
２０１ 端末記憶部
２０２ 端末暗号化部
２０３ 端末公開部
２０４ 行列受信部
２０５ 消去行列計算部
２０６ ◎行列段階計算部
２０７ 行列送信部
３０１ 制御記憶部
３０２ e生成部
３０３ 行列送信部
３０４ 行列受信部
３０５ 求解部
３１１ 転送部
５０１ 外部装置
５１１ 外部記憶部
５１２ 行列受付部
５１３ 求解部
７０１ 端末群
７０２ 中央装置
７１１ 値生成部
７１２ 値送信部
７３１ c生成部
７３２ r計算部
７３３ rc送信部
７３４ b受信部
７３５ f計算部
７５１ rc受信部
７５２ b選択部
７５３ b送信部
７５４ d計算部
７５５ 認証部
【特許請求の範囲】
【請求項１】
端末装置U1，…，Utと、制御装置と、を有する計算システムであって、当該計算システムでは、
列ベクトルvのj行目の要素をv[j]と表記し、
【数１】
行列Aのj行i列目の要素をA[j,i]と表記し、
【数２】
素数Pを法とする有限体ZPの要素aを、加法群(ZP,+)からPを法とする生成元gの巡回乗法群G = 〈g〉へのホモモルフィック暗号e(・,・)を用いて、公開鍵pにより暗号化した結果を、e(p,a)と表記すると、
ZPの任意の要素x,yと任意の公開鍵pは、
e(p,x)e(p,y) = e(p,x+y)
を満たし、
h行k列の行列Aのj行i列の要素A[j,i] = aj,iを、公開鍵p1，…，pkにより暗号化した行列e(A)を
e(A)[j,i] = e(pi,aj,i)
【数３】
と定義し、
h行の列ベクトルvのj行の要素v[j]を、公開鍵piにより暗号化した列ベクトルei(v)を、
ei(v)[j] = e(pi,v[j])
と定義し、
H行u列の行列Bのh行i列の要素B[h,i] = bh,iと、u行K列の行列Cのi行k列の要素C[i,k] = ci,kと、についての演算B◎Cを、
B◎C[h,k] = Πi=1u C[i,k]B[h,i]
【数４】
と定義すると、
行列A，Bについての演算B◎e(A)は、
B◎e(A)[h,k] = e(pk,Σi=1u B[h,i]A[i,k]) = Πi=1u e(pk,A[i,k])B[h,i]
すなわち
B◎e(A) = e(BA)
を満たし、
公開鍵piおよび列ベクトルvについての演算B◎ei(v)は、
B◎ei(v) = ei(Bv)
を満たし、
当該計算システムにおいて、
i = 1，…，uのそれぞれについて、前記端末装置Uiは、有限体ZPに含まれる秘密値w[1,i]，…，w[u,i]と、ホモモルフィック暗号e(・,・)における秘密鍵siと公開鍵piと、があらかじめ記憶される端末記憶部を備え、
前記制御装置は、ホモモルフィック暗号e(・,・)における秘密鍵svと公開鍵pvと、があらかじめ記憶される制御記憶部を備え、
当該計算システムにおいて、前記端末装置U1，…，Utのそれぞれに記憶される秘密値を要素とするt行t列の行列Wと、ZPに含まれる要素からなるt行の列ベクトルfと、からなる行列方程式
W[j,i] = w[j,i]；
WX = f (mod P)
【数５】
の解ベクトルXを求めるため、
（ａ）i = 1，…，tのそれぞれについて、前記端末装置Uiは、
秘密値w[1,i]，…，w[t,i]を、公開鍵piにより暗号化した暗号化済値
e(pi,w[1,i])，…，e(pi,w[t,i])
を計算する端末暗号化部、
前記計算された暗号化済値を公開する端末公開部
を備え、
（ｂ）前記制御装置は、
前記端末装置U1，…，Utにより公開された暗号化済値から、暗号化済行列e(W)および暗号化済ベクトルev(f)を
e(W)[j,i] = e(pi,w[j,i]) (1≦i≦t，1≦j≦t)
【数６】
ev(f)[j] = e(pv，f[j]) (1≦j≦t)
【数７】
により生成するe生成部、
前記生成された行列e(W)および当該列ベクトルev(f)を前記端末装置U1に送信する行列送信部
を備え、
（ｃ）i = 1，…，tのそれぞれについて、前記端末装置Uiは、
i = 1の場合、前記制御装置から送信された行列および列ベクトル
e(W)，ev(f)
を受信し、i > 1の場合、前記端末装置Ui-1から送信された行列および列ベクトル
Li-1◎…◎L1◎e(W) = e(Li-1…L1W)，Li-1◎…◎L1◎ev(f) = ev(Li-1…L1f)
を受信する行列受信部、
前記受信された行列のi列目を、秘密鍵siにより復号し、i行目を軸に当該復号された列をガウス消去する行列Liを計算する消去行列計算部、
前記計算された行列Liと、前記受信された行列および列ベクトルと、から、
Li◎Li-1◎…◎L1◎e(W) = e(LiLi-1…L1W)，Li◎Li-1◎…◎L1◎ev(f) = ev(LiLi-1…L1f)
を計算する◎行列段階計算部、
前記計算された行列および列ベクトル
Li◎Li-1◎…◎L1◎e(W) = e(LiLi-1…L1W)，Li◎Li-1◎…◎L1◎ev(f) = ev(LiLi-1…L1f)
を、i < tの場合、前記端末装置Ui+1に送信する行列送信部
を備え、
（ｄ）前記制御装置は、
前記端末装置Utにおいて計算された列ベクトル
ev(LtLt-1…L1f)
を秘密鍵svで
LtLt-1…L1f
に復号して、解ベクトルXとする求解部
を備えることを特徴とする計算システム。
【請求項２】
請求項１に記載の計算システムであって、
前記制御装置は、前記端末装置U1，…，UtのいずれかUkであり、秘密鍵sv = sk，公開鍵pv = pkとする
ことを特徴とする計算システム。
【請求項３】
請求項１に記載の計算システムであって、外部装置をさらに備え、
前記制御装置が制御記憶部を備えるのにかえて、前記外部装置は、ホモモルフィック暗号e(・,・)における秘密鍵svと公開鍵pvと、があらかじめ記憶される外部記憶部を備え、
当該計算システムは、当該t行t列の行列Wと、当該t行の列ベクトルfと、からなる行列方程式を解くのにかえて、前記端末装置U1，…，Utのそれぞれに記憶される秘密値を要素とする(t+1)行(t+1)列の行列Wと、ZPに含まれる要素からなる(t+1)行の列ベクトルfと、からなる行列方程式
W[j,i] = w[j,i] (1≦j≦t，1≦i≦t)；
W[t+1,i] = W[j,t+1] = 1 (1≦j≦t，1≦i≦t)；
W[t+1,t+1] = 0；
WX = f (mod P)
【数８】
の解ベクトルXを求めるため、
（ｂ'）前記制御装置において、前記e生成部は、前記端末装置U1，…，Utにより公開された暗号化済値および公開鍵piと、前記外部装置により公開された公開鍵pvと、により、暗号化済行列e(W)と暗号化済ベクトルev(f)を、
e(W)[j,i] = e(pi,w[j,i]) (1≦j≦t，1≦i≦t)；
e(W)[t+1,i] = e(pi,1) (1≦i≦t)；
e(W)[j,t+1] = e(pv,1) (1≦j≦t)；
e(W)[t+1,t+1] = e(pv,0)
【数９】
ev(f)[j] = e(pv，f[j]) (1≦j≦t)
により生成し、
（ｄ'）前記制御装置は、前記求解部にかえて前記端末装置Utにおいて計算された行列および列ベクトル
Lt◎Lt-1…◎L1◎e(W) = e(LtLt-1…L1W)，ev(LtLt-1…L1f)
を、前記外部装置に転送する転送部を備え、
（ｅ）前記外部装置は、
前記制御装置から転送された行列および列ベクトル
Lt◎Lt-1…◎L1◎e(W) = e(LtLt-1…L1W)，ev(LtLt-1…L1f)
を受け付ける行列受付部、
前記受け付けられた行列のt+1列目を、秘密鍵svにより復号し、t+1行目を軸に当該復号された列をガウス消去する行列Lvを計算する消去行列計算部、
前記受信された列ベクトルを秘密鍵svで
LtLt-1…L1f
に復号して、これと前記計算された行列Lvと、から、
LvLtLt-1…L1f
を計算して、これを解ベクトルXとする求解部
を備えることを特徴とする計算システム。
【請求項４】
請求項３に記載の計算システムであって、端末装置Ut+1，…，Umと、中央装置と、をさらに備え、
（ｆ）前記中央装置は、j = 1，…，tおよびi = 1，…，mのそれぞれについて、ZPから値w[j,i]をランダムに一様に生成する値生成部、
i = 1，…，mのそれぞれについて、値w[1,i]，…，w[t,i]を前記端末装置U[i]に送信する値送信部
を備え、
（ｇ）i = 1，…，mについて、前記端末装置Uiは、前記中央装置から送信された値w[1,i]，…，w[t,i]を受信する秘密値受信部
を備え、
前記受信されたw[1,i]，…，w[t,i]を、当該端末装置の秘密値w[1,i]，…，w[t,i]とし、
y[1,i] = gw[1,i]，…，y[t,i] = gw[t,i]を当該端末装置の公開値とし、
（ｈ）前記端末装置U1，…，Utおよび前記制御装置は、端末群を構成し、当該端末群は、
ZPから値c[0]，c[1]，…，c[m]をランダムに一様に生成するc生成部、
前記生成された値c[0]，c[1]，…，c[m]と、前記公開された公開鍵と、から、j = 1，…，tのそれぞれについて、
r[j] = gc[0] Πi=1m y[j,i]c[i]
を計算するr計算部、
前記生成された値c[0]，c[1]，…，c[m]と、前記計算されたr[1]，…，r[t]と、を、前記外部装置に送信するrc送信部
を備え、
（ｉ）前記外部装置は、
前記端末群から送信されたc[0]，c[1]，…，c[m]と、r[1]，…，r[t]と、を受信するrc受信部、
ZPからbをランダムに選択するb選択部、
前記選択されたbを、前記端末群に送信するb送信部
を備え、
（ｊ）前記端末群は、
前記外部装置から送信されたbを受信するb受信部、
j = 1，…，tのそれぞれについて、前記端末装置Uiにおいて、
f[j] = c[0] + Σi=1t w[j,i]c[i]
を計算し、前記端末群のいずれかの端末装置において
f[t+1] = b - Σi=t+1m c[i]
を計算するf計算部
を備え、
（ｋ）前記端末群および前記外部装置は、前記計算された列ベクトルfにより、当該行列方程式
WX = f (mod P)
を求解し、
（ｌ）前記外部装置は、
前記求解された結果により、j = 1，…，tのそれぞれについて、
d[j] = X[j]
とし、
d[0] = X[t+1]
とし、j = t+1，…，mのそれぞれについて
d[j] = c[j]
とするd計算部、
前記受信されたr[1]，…，r[t]と、前記得られたd[0]，d[1]，…，d[m]と、に対して、j = 1，…，tのすべてについて、
r[j] = gd[0] Πi=1m y[j,i]d[i]
が成立し、かつ、
b = Σi=1m d[i] (mod P)
が成立する場合、端末群の匿名認証を成功させる認証部
を備える
ことを特徴とする計算システム。
【請求項５】
端末装置U1，…，Utと、制御装置と、を有する計算システムが実行する計算方法であって、当該計算方法では、
列ベクトルvのj行目の要素をv[j]と表記し、
【数１０】
行列Aのj行i列目の要素をA[j,i]と表記し、
【数１１】
素数Pを法とする有限体ZPの要素aを、加法群(ZP,+)からPを法とする生成元gの巡回乗法群G = 〈g〉へのホモモルフィック暗号e(・,・)を用いて、公開鍵pにより暗号化した結果を、e(p,a)と表記すると、
ZPの任意の要素x,yと任意の公開鍵pは、
e(p,x)e(p,y) = e(p,x+y)
を満たし、
h行k列の行列Aのj行i列の要素A[j,i] = aj,iを、公開鍵p1，…，pkにより暗号化した行列e(A)を
e(A)[j,i] = e(pi,aj,i)
【数１２】
と定義し、
h行の列ベクトルvのj行の要素v[j]を、公開鍵piにより暗号化した列ベクトルei(v)を、
ei(v)[j] = e(pi,v[j])
と定義し、
H行u列の行列Bのh行i列の要素B[h,i] = bh,iと、u行K列の行列Cのi行k列の要素C[i,k] = ci,kと、についての演算B◎Cを、
B◎C[h,k] = Πi=1u C[i,k]B[h,i]
【数１３】
と定義すると、
行列A，Bについての演算B◎e(A)は、
B◎e(A)[h,k] = e(pk,Σi=1u B[h,i]A[i,k]) = Πi=1u e(pk,A[i,k])B[h,i]
すなわち
B◎e(A) = e(BA)
を満たし、
公開鍵piおよび列ベクトルvについての演算B◎ei(v)は、
B◎ei(v) = ei(Bv)
を満たし、
当該計算方法において、
i = 1，…，uのそれぞれについて、前記端末装置Uiは、有限体ZPに含まれる秘密値w[1,i]，…，w[u,i]と、ホモモルフィック暗号e(・,・)における秘密鍵siと公開鍵piと、があらかじめ記憶される端末記憶部、端末暗号化部、端末公開部、行列受信部、消去行列計算部、◎行列段階計算部、行列送信部を備え、
前記制御装置は、ホモモルフィック暗号e(・,・)における秘密鍵svと公開鍵pvと、があらかじめ記憶される制御記憶部、e生成部、行列送信部、求解部を備え、
当該計算方法において、前記端末装置U1，…，Utのそれぞれに記憶される秘密値を要素とするt行t列の行列Wと、ZPに含まれる要素からなるt行の列ベクトルfと、からなる行列方程式
W[j,i] = w[j,i]；
WX = f (mod P)
【数１４】
の解ベクトルXを求めるため、
（ａ）i = 1，…，tのそれぞれについて、前記端末装置Uiにおいて、
前記端末暗号化部が、秘密値w[1,i]，…，w[t,i]を、公開鍵piにより暗号化した暗号化済値
e(pi,w[1,i])，…，e(pi,w[t,i])
を計算する端末暗号化工程
前記端末公開部が、前記計算された暗号化済値を公開する端末公開工程
を備え、
（ｂ）前記制御装置において、
前記e生成部が、前記端末装置U1，…，Utにより公開された暗号化済値から、暗号化済行列e(W)および暗号化済ベクトルev(f)を
e(W)[j,i] = e(pi,w[j,i]) (1≦i≦t，1≦j≦t)
【数１５】
ev(f)[j] = e(pv，f[j]) (1≦j≦t)
【数１６】
により生成するe生成工程、
前記行列送信部が、前記生成された行列e(W)および当該列ベクトルev(f)を前記端末装置U1に送信する行列送信工程
を備え、
（ｃ）i = 1，…，tのそれぞれについて、前記端末装置Uiにおいて、
前記行列受信部が、i = 1の場合、前記制御装置から送信された行列および列ベクトル
e(W)，ev(f)
を受信し、i > 1の場合、前記端末装置Ui-1から送信された行列および列ベクトル
Li-1◎…◎L1◎e(W) = e(Li-1…L1W)，Li-1◎…◎L1◎ev(f) = ev(Li-1…L1f)
を受信する行列受信工程、
前記消去行列計算部が、前記受信された行列のi列目を、秘密鍵siにより復号し、i行目を軸に当該復号された列をガウス消去する行列Liを計算する消去行列計算工程、
前記◎行列段階計算部が、前記計算された行列Liと、前記受信された行列および列ベクトルと、から、
Li◎Li-1◎…◎L1◎e(W) = e(LiLi-1…L1W)，Li◎Li-1◎…◎L1◎ev(f) = ev(LiLi-1…L1f)
を計算する◎行列段階計算工程、
前記行列送信部が、前記計算された行列および列ベクトル
Li◎Li-1◎…◎L1◎e(W) = e(LiLi-1…L1W)，Li◎Li-1◎…◎L1◎ev(f) = ev(LiLi-1…L1f)
を、i < tの場合、前記端末装置Ui+1に送信する行列送信工程
を備え、
（ｄ）前記制御装置において、
前記求解部が、前記端末装置Utにおいて計算された列ベクトル
ev(LtLt-1…L1f)
を秘密鍵svで
LtLt-1…L1f
に復号して、解ベクトルXとする求解工程
を備えることを特徴とする計算方法。
【請求項６】
請求項５に記載の計算方法であって、
前記制御装置は、前記端末装置U1，…，UtのいずれかUkであり、秘密鍵sv = sk，公開鍵pv = pkとする
ことを特徴とする計算方法。
【請求項７】
請求項５に記載の計算方法であって、外部装置がさらに実行し、
前記制御装置が制御記憶部を備えるのにかえて、前記外部装置は、ホモモルフィック暗号e(・,・)における秘密鍵svと公開鍵pvと、があらかじめ記憶される外部記憶部、行列受付部、消去行列計算部、求解部を備え、
前記制御装置は、前記求解部にかえて転送部を備え、
当該計算方法は、当該t行t列の行列Wと、当該t行の列ベクトルfと、からなる行列方程式を解くのにかえて、前記端末装置U1，…，Utのそれぞれに記憶される秘密値を要素とする(t+1)行(t+1)列の行列Wと、ZPに含まれる要素からなる(t+1)行の列ベクトルfと、からなる行列方程式
W[j,i] = w[j,i] (1≦j≦t，1≦i≦t)；
W[t+1,i] = W[j,t+1] = 1 (1≦j≦t，1≦i≦t)；
W[t+1,t+1] = 0；
WX = f (mod P)
【数１７】
の解ベクトルXを求めるため、
（ｂ'）前記制御装置において、前記e生成工程では、前記端末装置U1，…，Utにより公開された暗号化済値および公開鍵piと、前記外部装置により公開された公開鍵pvと、により、暗号化済行列e(W)と暗号化済ベクトルev(f)を、
e(W)[j,i] = e(pi,w[j,i]) (1≦j≦t，1≦i≦t)；
e(W)[t+1,i] = e(pi,1) (1≦i≦t)；
e(W)[j,t+1] = e(pv,1) (1≦j≦t)；
e(W)[t+1,t+1] = e(pv,0)
【数１８】
ev(f)[j] = e(pv，f[j]) (1≦j≦t)
により生成し、
（ｄ'）前記制御装置において、前記転送部が、前記端末装置Utにおいて計算された行列および列ベクトル
Lt◎Lt-1…◎L1◎e(W) = e(LtLt-1…L1W)，ev(LtLt-1…L1f)
を、前記外部装置に転送する転送工程を備え、
（ｅ）前記外部装置において、
前記行列受付部が、前記制御装置から転送された行列および列ベクトル
Lt◎Lt-1…◎L1◎e(W) = e(LtLt-1…L1W)，ev(LtLt-1…L1f)
を受け付ける行列受付工程、
前記消去行列計算部が、前記受け付けられた行列のt+1列目を、秘密鍵svにより復号し、t+1行目を軸に当該復号された列をガウス消去する行列Lvを計算する消去行列計算工程、
前記求解部が、前記受信された列ベクトルを秘密鍵svで
LtLt-1…L1f
に復号して、これと前記計算された行列Lvと、から、
LvLtLt-1…L1f
を計算して、これを解ベクトルXとする求解工程
を備えることを特徴とする計算システム。
【請求項８】
請求項７に記載の計算方法であって、端末装置Ut+1，…，Umと、中央装置と、がさらに実行し、
前記中央装置は、値生成部、値送信部を備え、
i = 1，…，mについて、前記端末装置Uiは、秘密値受信部を備え、
前記端末装置U1，…，Utおよび前記制御装置は、端末群を構成し、当該端末群は、c生成部、r計算部、rc送信部、b受信部、f計算部を備え、
前記外部装置は、rc受信部、b選択部、b送信部、d計算部、認証部を備え、
（ｆ）前記中央装置において、
前記値生成部が、j = 1，…，tおよびi = 1，…，mのそれぞれについて、ZPから値w[j,i]をランダムに一様に生成する値生成工程、
前記値送信部が、i = 1，…，mのそれぞれについて、値w[1,i]，…，w[t,i]を前記端末装置U[i]に送信する値送信工程
を備え、
（ｇ）i = 1，…，mについて、前記端末装置Uiにおいて、
前記秘密値受信部が、前記中央装置から送信された値w[1,i]，…，w[t,i]を受信する秘密値受信工程
を備え、
前記受信されたw[1,i]，…，w[t,i]を、当該端末装置の秘密値w[1,i]，…，w[t,i]とし、
y[1,i] = gw[1,i]，…，y[t,i] = gw[t,i]を当該端末装置の公開値とし、
（ｈ）前記端末群において、
前記c生成部が、ZPから値c[0]，c[1]，…，c[m]をランダムに一様に生成するc生成工程、
前記r計算部が、前記生成された値c[0]，c[1]，…，c[m]と、前記公開された公開鍵と、から、j = 1，…，tのそれぞれについて、
r[j] = gc[0] Πi=1m y[j,i]c[i]
を計算するr計算工程、
前記rc送信部が、前記生成された値c[0]，c[1]，…，c[m]と、前記計算されたr[1]，…，r[t]と、を、前記外部装置に送信するrc送信工程
を備え、
（ｉ）前記外部装置において、
前記rc受信部が、前記端末群から送信されたc[0]，c[1]，…，c[m]と、r[1]，…，r[t]と、を受信するrc受信工程、
前記b選択部が、ZPからbをランダムに選択するb選択工程、
前記b送信部が、前記選択されたbを、前記端末群に送信するb送信工程
を備え、
（ｊ）前記端末群において、
前記b受信部が、前記外部装置から送信されたbを受信するb受信工程、
j = 1，…，tのそれぞれについて、前記端末装置Uiにおいて、
f[j] = c[0] + Σi=1t w[j,i]c[i]
を計算し、前記端末群のいずれかの端末装置において
f[t+1] = b - Σi=t+1m c[i]
を計算するf計算工程
を備え、
（ｋ）前記端末群および前記外部装置において、前記計算された列ベクトルfにより、当該行列方程式
WX = f (mod P)
を求解し、
（ｌ）前記外部装置において、
前記d計算部が、前記求解された結果により、j = 1，…，tのそれぞれについて、
d[j] = X[j]
とし、
d[0] = X[t+1]
とし、j = t+1，…，mのそれぞれについて
d[j] = c[j]
とするd計算工程、
前記認証部が、前記受信されたr[1]，…，r[t]と、前記得られたd[0]，d[1]，…，d[m]と、に対して、j = 1，…，tのすべてについて、
r[j] = gd[0] Πi=1m y[j,i]d[i]
が成立し、かつ、
b = Σi=1m d[i] (mod P)
が成立する場合、前記端末群の匿名認証を成功させる認証工程
を備える
ことを特徴とする計算方法。
【請求項９】
コンピュータを、請求項１から４のいずれか１項に記載の端末装置の各部として機能させることを特徴とするプログラム。
【請求項１０】
コンピュータを、請求項１から４のいずれか１項に記載の制御装置の各部として機能させることを特徴とするプログラム。
【請求項１１】
コンピュータを、請求項３または４に記載の外部装置の各部として機能させることを特徴とするプログラム。
【請求項１２】
コンピュータを、請求項４に記載の中央装置の各部として機能させることを特徴とするプログラム。
【請求項１】
端末装置U1，…，Utと、制御装置と、を有する計算システムであって、当該計算システムでは、
列ベクトルvのj行目の要素をv[j]と表記し、
【数１】
行列Aのj行i列目の要素をA[j,i]と表記し、
【数２】
素数Pを法とする有限体ZPの要素aを、加法群(ZP,+)からPを法とする生成元gの巡回乗法群G = 〈g〉へのホモモルフィック暗号e(・,・)を用いて、公開鍵pにより暗号化した結果を、e(p,a)と表記すると、
ZPの任意の要素x,yと任意の公開鍵pは、
e(p,x)e(p,y) = e(p,x+y)
を満たし、
h行k列の行列Aのj行i列の要素A[j,i] = aj,iを、公開鍵p1，…，pkにより暗号化した行列e(A)を
e(A)[j,i] = e(pi,aj,i)
【数３】
と定義し、
h行の列ベクトルvのj行の要素v[j]を、公開鍵piにより暗号化した列ベクトルei(v)を、
ei(v)[j] = e(pi,v[j])
と定義し、
H行u列の行列Bのh行i列の要素B[h,i] = bh,iと、u行K列の行列Cのi行k列の要素C[i,k] = ci,kと、についての演算B◎Cを、
B◎C[h,k] = Πi=1u C[i,k]B[h,i]
【数４】
と定義すると、
行列A，Bについての演算B◎e(A)は、
B◎e(A)[h,k] = e(pk,Σi=1u B[h,i]A[i,k]) = Πi=1u e(pk,A[i,k])B[h,i]
すなわち
B◎e(A) = e(BA)
を満たし、
公開鍵piおよび列ベクトルvについての演算B◎ei(v)は、
B◎ei(v) = ei(Bv)
を満たし、
当該計算システムにおいて、
i = 1，…，uのそれぞれについて、前記端末装置Uiは、有限体ZPに含まれる秘密値w[1,i]，…，w[u,i]と、ホモモルフィック暗号e(・,・)における秘密鍵siと公開鍵piと、があらかじめ記憶される端末記憶部を備え、
前記制御装置は、ホモモルフィック暗号e(・,・)における秘密鍵svと公開鍵pvと、があらかじめ記憶される制御記憶部を備え、
当該計算システムにおいて、前記端末装置U1，…，Utのそれぞれに記憶される秘密値を要素とするt行t列の行列Wと、ZPに含まれる要素からなるt行の列ベクトルfと、からなる行列方程式
W[j,i] = w[j,i]；
WX = f (mod P)
【数５】
の解ベクトルXを求めるため、
（ａ）i = 1，…，tのそれぞれについて、前記端末装置Uiは、
秘密値w[1,i]，…，w[t,i]を、公開鍵piにより暗号化した暗号化済値
e(pi,w[1,i])，…，e(pi,w[t,i])
を計算する端末暗号化部、
前記計算された暗号化済値を公開する端末公開部
を備え、
（ｂ）前記制御装置は、
前記端末装置U1，…，Utにより公開された暗号化済値から、暗号化済行列e(W)および暗号化済ベクトルev(f)を
e(W)[j,i] = e(pi,w[j,i]) (1≦i≦t，1≦j≦t)
【数６】
ev(f)[j] = e(pv，f[j]) (1≦j≦t)
【数７】
により生成するe生成部、
前記生成された行列e(W)および当該列ベクトルev(f)を前記端末装置U1に送信する行列送信部
を備え、
（ｃ）i = 1，…，tのそれぞれについて、前記端末装置Uiは、
i = 1の場合、前記制御装置から送信された行列および列ベクトル
e(W)，ev(f)
を受信し、i > 1の場合、前記端末装置Ui-1から送信された行列および列ベクトル
Li-1◎…◎L1◎e(W) = e(Li-1…L1W)，Li-1◎…◎L1◎ev(f) = ev(Li-1…L1f)
を受信する行列受信部、
前記受信された行列のi列目を、秘密鍵siにより復号し、i行目を軸に当該復号された列をガウス消去する行列Liを計算する消去行列計算部、
前記計算された行列Liと、前記受信された行列および列ベクトルと、から、
Li◎Li-1◎…◎L1◎e(W) = e(LiLi-1…L1W)，Li◎Li-1◎…◎L1◎ev(f) = ev(LiLi-1…L1f)
を計算する◎行列段階計算部、
前記計算された行列および列ベクトル
Li◎Li-1◎…◎L1◎e(W) = e(LiLi-1…L1W)，Li◎Li-1◎…◎L1◎ev(f) = ev(LiLi-1…L1f)
を、i < tの場合、前記端末装置Ui+1に送信する行列送信部
を備え、
（ｄ）前記制御装置は、
前記端末装置Utにおいて計算された列ベクトル
ev(LtLt-1…L1f)
を秘密鍵svで
LtLt-1…L1f
に復号して、解ベクトルXとする求解部
を備えることを特徴とする計算システム。
【請求項２】
請求項１に記載の計算システムであって、
前記制御装置は、前記端末装置U1，…，UtのいずれかUkであり、秘密鍵sv = sk，公開鍵pv = pkとする
ことを特徴とする計算システム。
【請求項３】
請求項１に記載の計算システムであって、外部装置をさらに備え、
前記制御装置が制御記憶部を備えるのにかえて、前記外部装置は、ホモモルフィック暗号e(・,・)における秘密鍵svと公開鍵pvと、があらかじめ記憶される外部記憶部を備え、
当該計算システムは、当該t行t列の行列Wと、当該t行の列ベクトルfと、からなる行列方程式を解くのにかえて、前記端末装置U1，…，Utのそれぞれに記憶される秘密値を要素とする(t+1)行(t+1)列の行列Wと、ZPに含まれる要素からなる(t+1)行の列ベクトルfと、からなる行列方程式
W[j,i] = w[j,i] (1≦j≦t，1≦i≦t)；
W[t+1,i] = W[j,t+1] = 1 (1≦j≦t，1≦i≦t)；
W[t+1,t+1] = 0；
WX = f (mod P)
【数８】
の解ベクトルXを求めるため、
（ｂ'）前記制御装置において、前記e生成部は、前記端末装置U1，…，Utにより公開された暗号化済値および公開鍵piと、前記外部装置により公開された公開鍵pvと、により、暗号化済行列e(W)と暗号化済ベクトルev(f)を、
e(W)[j,i] = e(pi,w[j,i]) (1≦j≦t，1≦i≦t)；
e(W)[t+1,i] = e(pi,1) (1≦i≦t)；
e(W)[j,t+1] = e(pv,1) (1≦j≦t)；
e(W)[t+1,t+1] = e(pv,0)
【数９】
ev(f)[j] = e(pv，f[j]) (1≦j≦t)
により生成し、
（ｄ'）前記制御装置は、前記求解部にかえて前記端末装置Utにおいて計算された行列および列ベクトル
Lt◎Lt-1…◎L1◎e(W) = e(LtLt-1…L1W)，ev(LtLt-1…L1f)
を、前記外部装置に転送する転送部を備え、
（ｅ）前記外部装置は、
前記制御装置から転送された行列および列ベクトル
Lt◎Lt-1…◎L1◎e(W) = e(LtLt-1…L1W)，ev(LtLt-1…L1f)
を受け付ける行列受付部、
前記受け付けられた行列のt+1列目を、秘密鍵svにより復号し、t+1行目を軸に当該復号された列をガウス消去する行列Lvを計算する消去行列計算部、
前記受信された列ベクトルを秘密鍵svで
LtLt-1…L1f
に復号して、これと前記計算された行列Lvと、から、
LvLtLt-1…L1f
を計算して、これを解ベクトルXとする求解部
を備えることを特徴とする計算システム。
【請求項４】
請求項３に記載の計算システムであって、端末装置Ut+1，…，Umと、中央装置と、をさらに備え、
（ｆ）前記中央装置は、j = 1，…，tおよびi = 1，…，mのそれぞれについて、ZPから値w[j,i]をランダムに一様に生成する値生成部、
i = 1，…，mのそれぞれについて、値w[1,i]，…，w[t,i]を前記端末装置U[i]に送信する値送信部
を備え、
（ｇ）i = 1，…，mについて、前記端末装置Uiは、前記中央装置から送信された値w[1,i]，…，w[t,i]を受信する秘密値受信部
を備え、
前記受信されたw[1,i]，…，w[t,i]を、当該端末装置の秘密値w[1,i]，…，w[t,i]とし、
y[1,i] = gw[1,i]，…，y[t,i] = gw[t,i]を当該端末装置の公開値とし、
（ｈ）前記端末装置U1，…，Utおよび前記制御装置は、端末群を構成し、当該端末群は、
ZPから値c[0]，c[1]，…，c[m]をランダムに一様に生成するc生成部、
前記生成された値c[0]，c[1]，…，c[m]と、前記公開された公開鍵と、から、j = 1，…，tのそれぞれについて、
r[j] = gc[0] Πi=1m y[j,i]c[i]
を計算するr計算部、
前記生成された値c[0]，c[1]，…，c[m]と、前記計算されたr[1]，…，r[t]と、を、前記外部装置に送信するrc送信部
を備え、
（ｉ）前記外部装置は、
前記端末群から送信されたc[0]，c[1]，…，c[m]と、r[1]，…，r[t]と、を受信するrc受信部、
ZPからbをランダムに選択するb選択部、
前記選択されたbを、前記端末群に送信するb送信部
を備え、
（ｊ）前記端末群は、
前記外部装置から送信されたbを受信するb受信部、
j = 1，…，tのそれぞれについて、前記端末装置Uiにおいて、
f[j] = c[0] + Σi=1t w[j,i]c[i]
を計算し、前記端末群のいずれかの端末装置において
f[t+1] = b - Σi=t+1m c[i]
を計算するf計算部
を備え、
（ｋ）前記端末群および前記外部装置は、前記計算された列ベクトルfにより、当該行列方程式
WX = f (mod P)
を求解し、
（ｌ）前記外部装置は、
前記求解された結果により、j = 1，…，tのそれぞれについて、
d[j] = X[j]
とし、
d[0] = X[t+1]
とし、j = t+1，…，mのそれぞれについて
d[j] = c[j]
とするd計算部、
前記受信されたr[1]，…，r[t]と、前記得られたd[0]，d[1]，…，d[m]と、に対して、j = 1，…，tのすべてについて、
r[j] = gd[0] Πi=1m y[j,i]d[i]
が成立し、かつ、
b = Σi=1m d[i] (mod P)
が成立する場合、端末群の匿名認証を成功させる認証部
を備える
ことを特徴とする計算システム。
【請求項５】
端末装置U1，…，Utと、制御装置と、を有する計算システムが実行する計算方法であって、当該計算方法では、
列ベクトルvのj行目の要素をv[j]と表記し、
【数１０】
行列Aのj行i列目の要素をA[j,i]と表記し、
【数１１】
素数Pを法とする有限体ZPの要素aを、加法群(ZP,+)からPを法とする生成元gの巡回乗法群G = 〈g〉へのホモモルフィック暗号e(・,・)を用いて、公開鍵pにより暗号化した結果を、e(p,a)と表記すると、
ZPの任意の要素x,yと任意の公開鍵pは、
e(p,x)e(p,y) = e(p,x+y)
を満たし、
h行k列の行列Aのj行i列の要素A[j,i] = aj,iを、公開鍵p1，…，pkにより暗号化した行列e(A)を
e(A)[j,i] = e(pi,aj,i)
【数１２】
と定義し、
h行の列ベクトルvのj行の要素v[j]を、公開鍵piにより暗号化した列ベクトルei(v)を、
ei(v)[j] = e(pi,v[j])
と定義し、
H行u列の行列Bのh行i列の要素B[h,i] = bh,iと、u行K列の行列Cのi行k列の要素C[i,k] = ci,kと、についての演算B◎Cを、
B◎C[h,k] = Πi=1u C[i,k]B[h,i]
【数１３】
と定義すると、
行列A，Bについての演算B◎e(A)は、
B◎e(A)[h,k] = e(pk,Σi=1u B[h,i]A[i,k]) = Πi=1u e(pk,A[i,k])B[h,i]
すなわち
B◎e(A) = e(BA)
を満たし、
公開鍵piおよび列ベクトルvについての演算B◎ei(v)は、
B◎ei(v) = ei(Bv)
を満たし、
当該計算方法において、
i = 1，…，uのそれぞれについて、前記端末装置Uiは、有限体ZPに含まれる秘密値w[1,i]，…，w[u,i]と、ホモモルフィック暗号e(・,・)における秘密鍵siと公開鍵piと、があらかじめ記憶される端末記憶部、端末暗号化部、端末公開部、行列受信部、消去行列計算部、◎行列段階計算部、行列送信部を備え、
前記制御装置は、ホモモルフィック暗号e(・,・)における秘密鍵svと公開鍵pvと、があらかじめ記憶される制御記憶部、e生成部、行列送信部、求解部を備え、
当該計算方法において、前記端末装置U1，…，Utのそれぞれに記憶される秘密値を要素とするt行t列の行列Wと、ZPに含まれる要素からなるt行の列ベクトルfと、からなる行列方程式
W[j,i] = w[j,i]；
WX = f (mod P)
【数１４】
の解ベクトルXを求めるため、
（ａ）i = 1，…，tのそれぞれについて、前記端末装置Uiにおいて、
前記端末暗号化部が、秘密値w[1,i]，…，w[t,i]を、公開鍵piにより暗号化した暗号化済値
e(pi,w[1,i])，…，e(pi,w[t,i])
を計算する端末暗号化工程
前記端末公開部が、前記計算された暗号化済値を公開する端末公開工程
を備え、
（ｂ）前記制御装置において、
前記e生成部が、前記端末装置U1，…，Utにより公開された暗号化済値から、暗号化済行列e(W)および暗号化済ベクトルev(f)を
e(W)[j,i] = e(pi,w[j,i]) (1≦i≦t，1≦j≦t)
【数１５】
ev(f)[j] = e(pv，f[j]) (1≦j≦t)
【数１６】
により生成するe生成工程、
前記行列送信部が、前記生成された行列e(W)および当該列ベクトルev(f)を前記端末装置U1に送信する行列送信工程
を備え、
（ｃ）i = 1，…，tのそれぞれについて、前記端末装置Uiにおいて、
前記行列受信部が、i = 1の場合、前記制御装置から送信された行列および列ベクトル
e(W)，ev(f)
を受信し、i > 1の場合、前記端末装置Ui-1から送信された行列および列ベクトル
Li-1◎…◎L1◎e(W) = e(Li-1…L1W)，Li-1◎…◎L1◎ev(f) = ev(Li-1…L1f)
を受信する行列受信工程、
前記消去行列計算部が、前記受信された行列のi列目を、秘密鍵siにより復号し、i行目を軸に当該復号された列をガウス消去する行列Liを計算する消去行列計算工程、
前記◎行列段階計算部が、前記計算された行列Liと、前記受信された行列および列ベクトルと、から、
Li◎Li-1◎…◎L1◎e(W) = e(LiLi-1…L1W)，Li◎Li-1◎…◎L1◎ev(f) = ev(LiLi-1…L1f)
を計算する◎行列段階計算工程、
前記行列送信部が、前記計算された行列および列ベクトル
Li◎Li-1◎…◎L1◎e(W) = e(LiLi-1…L1W)，Li◎Li-1◎…◎L1◎ev(f) = ev(LiLi-1…L1f)
を、i < tの場合、前記端末装置Ui+1に送信する行列送信工程
を備え、
（ｄ）前記制御装置において、
前記求解部が、前記端末装置Utにおいて計算された列ベクトル
ev(LtLt-1…L1f)
を秘密鍵svで
LtLt-1…L1f
に復号して、解ベクトルXとする求解工程
を備えることを特徴とする計算方法。
【請求項６】
請求項５に記載の計算方法であって、
前記制御装置は、前記端末装置U1，…，UtのいずれかUkであり、秘密鍵sv = sk，公開鍵pv = pkとする
ことを特徴とする計算方法。
【請求項７】
請求項５に記載の計算方法であって、外部装置がさらに実行し、
前記制御装置が制御記憶部を備えるのにかえて、前記外部装置は、ホモモルフィック暗号e(・,・)における秘密鍵svと公開鍵pvと、があらかじめ記憶される外部記憶部、行列受付部、消去行列計算部、求解部を備え、
前記制御装置は、前記求解部にかえて転送部を備え、
当該計算方法は、当該t行t列の行列Wと、当該t行の列ベクトルfと、からなる行列方程式を解くのにかえて、前記端末装置U1，…，Utのそれぞれに記憶される秘密値を要素とする(t+1)行(t+1)列の行列Wと、ZPに含まれる要素からなる(t+1)行の列ベクトルfと、からなる行列方程式
W[j,i] = w[j,i] (1≦j≦t，1≦i≦t)；
W[t+1,i] = W[j,t+1] = 1 (1≦j≦t，1≦i≦t)；
W[t+1,t+1] = 0；
WX = f (mod P)
【数１７】
の解ベクトルXを求めるため、
（ｂ'）前記制御装置において、前記e生成工程では、前記端末装置U1，…，Utにより公開された暗号化済値および公開鍵piと、前記外部装置により公開された公開鍵pvと、により、暗号化済行列e(W)と暗号化済ベクトルev(f)を、
e(W)[j,i] = e(pi,w[j,i]) (1≦j≦t，1≦i≦t)；
e(W)[t+1,i] = e(pi,1) (1≦i≦t)；
e(W)[j,t+1] = e(pv,1) (1≦j≦t)；
e(W)[t+1,t+1] = e(pv,0)
【数１８】
ev(f)[j] = e(pv，f[j]) (1≦j≦t)
により生成し、
（ｄ'）前記制御装置において、前記転送部が、前記端末装置Utにおいて計算された行列および列ベクトル
Lt◎Lt-1…◎L1◎e(W) = e(LtLt-1…L1W)，ev(LtLt-1…L1f)
を、前記外部装置に転送する転送工程を備え、
（ｅ）前記外部装置において、
前記行列受付部が、前記制御装置から転送された行列および列ベクトル
Lt◎Lt-1…◎L1◎e(W) = e(LtLt-1…L1W)，ev(LtLt-1…L1f)
を受け付ける行列受付工程、
前記消去行列計算部が、前記受け付けられた行列のt+1列目を、秘密鍵svにより復号し、t+1行目を軸に当該復号された列をガウス消去する行列Lvを計算する消去行列計算工程、
前記求解部が、前記受信された列ベクトルを秘密鍵svで
LtLt-1…L1f
に復号して、これと前記計算された行列Lvと、から、
LvLtLt-1…L1f
を計算して、これを解ベクトルXとする求解工程
を備えることを特徴とする計算システム。
【請求項８】
請求項７に記載の計算方法であって、端末装置Ut+1，…，Umと、中央装置と、がさらに実行し、
前記中央装置は、値生成部、値送信部を備え、
i = 1，…，mについて、前記端末装置Uiは、秘密値受信部を備え、
前記端末装置U1，…，Utおよび前記制御装置は、端末群を構成し、当該端末群は、c生成部、r計算部、rc送信部、b受信部、f計算部を備え、
前記外部装置は、rc受信部、b選択部、b送信部、d計算部、認証部を備え、
（ｆ）前記中央装置において、
前記値生成部が、j = 1，…，tおよびi = 1，…，mのそれぞれについて、ZPから値w[j,i]をランダムに一様に生成する値生成工程、
前記値送信部が、i = 1，…，mのそれぞれについて、値w[1,i]，…，w[t,i]を前記端末装置U[i]に送信する値送信工程
を備え、
（ｇ）i = 1，…，mについて、前記端末装置Uiにおいて、
前記秘密値受信部が、前記中央装置から送信された値w[1,i]，…，w[t,i]を受信する秘密値受信工程
を備え、
前記受信されたw[1,i]，…，w[t,i]を、当該端末装置の秘密値w[1,i]，…，w[t,i]とし、
y[1,i] = gw[1,i]，…，y[t,i] = gw[t,i]を当該端末装置の公開値とし、
（ｈ）前記端末群において、
前記c生成部が、ZPから値c[0]，c[1]，…，c[m]をランダムに一様に生成するc生成工程、
前記r計算部が、前記生成された値c[0]，c[1]，…，c[m]と、前記公開された公開鍵と、から、j = 1，…，tのそれぞれについて、
r[j] = gc[0] Πi=1m y[j,i]c[i]
を計算するr計算工程、
前記rc送信部が、前記生成された値c[0]，c[1]，…，c[m]と、前記計算されたr[1]，…，r[t]と、を、前記外部装置に送信するrc送信工程
を備え、
（ｉ）前記外部装置において、
前記rc受信部が、前記端末群から送信されたc[0]，c[1]，…，c[m]と、r[1]，…，r[t]と、を受信するrc受信工程、
前記b選択部が、ZPからbをランダムに選択するb選択工程、
前記b送信部が、前記選択されたbを、前記端末群に送信するb送信工程
を備え、
（ｊ）前記端末群において、
前記b受信部が、前記外部装置から送信されたbを受信するb受信工程、
j = 1，…，tのそれぞれについて、前記端末装置Uiにおいて、
f[j] = c[0] + Σi=1t w[j,i]c[i]
を計算し、前記端末群のいずれかの端末装置において
f[t+1] = b - Σi=t+1m c[i]
を計算するf計算工程
を備え、
（ｋ）前記端末群および前記外部装置において、前記計算された列ベクトルfにより、当該行列方程式
WX = f (mod P)
を求解し、
（ｌ）前記外部装置において、
前記d計算部が、前記求解された結果により、j = 1，…，tのそれぞれについて、
d[j] = X[j]
とし、
d[0] = X[t+1]
とし、j = t+1，…，mのそれぞれについて
d[j] = c[j]
とするd計算工程、
前記認証部が、前記受信されたr[1]，…，r[t]と、前記得られたd[0]，d[1]，…，d[m]と、に対して、j = 1，…，tのすべてについて、
r[j] = gd[0] Πi=1m y[j,i]d[i]
が成立し、かつ、
b = Σi=1m d[i] (mod P)
が成立する場合、前記端末群の匿名認証を成功させる認証工程
を備える
ことを特徴とする計算方法。
【請求項９】
コンピュータを、請求項１から４のいずれか１項に記載の端末装置の各部として機能させることを特徴とするプログラム。
【請求項１０】
コンピュータを、請求項１から４のいずれか１項に記載の制御装置の各部として機能させることを特徴とするプログラム。
【請求項１１】
コンピュータを、請求項３または４に記載の外部装置の各部として機能させることを特徴とするプログラム。
【請求項１２】
コンピュータを、請求項４に記載の中央装置の各部として機能させることを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１１−８０５５（Ｐ２０１１−８０５５Ａ）
【公開日】平成２３年１月１３日（２０１１．１．１３）
【国際特許分類】
【出願番号】特願２００９−１５１９０２（Ｐ２００９−１５１９０２）
【出願日】平成２１年６月２６日（２００９．６．２６）
【出願人】（３０１０２２４７１）独立行政法人情報通信研究機構 (1,071)
【Ｆターム（参考）】
【公開日】平成２３年１月１３日（２０１１．１．１３）
【国際特許分類】
【出願日】平成２１年６月２６日（２００９．６．２６）
【出願人】（３０１０２２４７１）独立行政法人情報通信研究機構 (1,071)
【Ｆターム（参考）】
[ Back to top ]