(57)【特許請求の範囲】
【請求項１】
コミットメント生成装置とコミットメント検証装置とを有し、
G1，G2，GTが群であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが１以上の整数であり、m→=(m(1),...,m(k))∈G2kがメッセージであり、1/m(i)がm(i)の逆元であり、コミットメント鍵ckが前記群G1の任意の元g(0), g(1),...,g(k), h(0), h(1),..., h(k)∈G1を含み、
前記コミットメント生成装置は、
任意の元ta, tb, t(i)∈Zp (i=1,...,k)を選択する選択部と、
ca=g(0)ta・Πi=1k g(i)t(i)∈G1を計算する第１コミットメント計算部と、
cb=h(0)tb・Πi=1k h(i)t(i)∈G1を計算する第２コミットメント計算部と、
c(i)=m(i)・g2t(i)∈G2(i=1,...,k)を計算する第３コミットメント計算部と、
ca, cb, c(1),...,c(k)を含むコミットメントCを出力するコミットメント出力部と、
da=g2ta∈G2を計算する第１デコミット鍵計算部と、
db=g2tb∈G2を計算する第２デコミット鍵計算部と、
da, dbを含むデコミット鍵Dを出力するデコミット鍵出力部と、を含み、
前記コミットメント検証装置は、
前記コミットメントCの入力を受け付けるコミットメント入力部と、
前記メッセージm→、前記コミットメント鍵ck、及び前記デコミット鍵Dの入力を受け付けるオープニング情報入力部と、
関係e(ca, g2)=e(g(0), da)・Πi=1k e(g(i), c(i)/m(i))及びe(cb, g2)=e(h(0), db)・Πi=1k e(h(i), c(i)/m(i))の両方が満たされるかを検証し、両方の前記関係が満たされる場合に前記メッセージm→を受理し、前記関係の少なくとも一方が満たされない場合に前記メッセージm→を不受理とする検証部と、を含む、
コミットメントシステム。
【請求項２】
コミットメント生成装置とコミットメント検証装置とを有し、
G1，G2，GTが群であり、G1≠G2であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが１以上の整数であり、m→=(m(1),...,m(k))∈G2kがメッセージであり、1/m(i)がm(i)の逆元であり、コミットメント鍵ckが前記群G1の任意の元g(0), g(1),...,g(k)∈G1を含み、
前記コミットメント生成装置は、
任意の元ta, t(i)∈Zp (i=1,...,k)を選択する選択部と、
ca=g(0)ta・Πi=1k g(i)t(i)∈G1を計算する第１コミットメント計算部と、
c(i)=m(i)・g2t(i)∈G2(i=1,...,k)を計算する第３コミットメント計算部と、
ca, c(1),...,c(k)を含むコミットメントCを出力するコミットメント出力部と、
da=g2ta∈G2を計算する第１デコミット鍵計算部と、
daを含むデコミット鍵Dを出力するデコミット鍵出力部と、を含み、
前記コミットメント検証装置は、
前記コミットメントCの入力を受け付けるコミットメント入力部と、
前記メッセージm→、前記コミットメント鍵ck、及び前記デコミット鍵Dの入力を受け付けるオープニング情報入力部と、
関係e(ca, g2)=e(g(0), da)・Πi=1k e(g(i), c(i)/m(i))が満たされるかを検証し、前記関係が満たされる場合に前記メッセージm→を受理し、前記関係が満たされない場合に前記メッセージm→を不受理とする検証部と、を含む、
コミットメントシステム。
【請求項３】
G1，G2，GTが群であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが１以上の整数であり、m→=(m(1),...,m(k))∈G2kがメッセージであり、1/m(i)がm(i)の逆元であり、コミットメント鍵ckが前記群G1の任意の元g(0), g(1),...,g(k), h(0), h(1),..., h(k)∈G1を含み、
任意の元ta, tb, t(i)∈Zp (i=1,...,k)を選択する選択部と、
ca=g(0)ta・Πi=1k g(i)t(i)∈G1を計算する第１コミットメント計算部と、
cb=h(0)tb・Πi=1k h(i)t(i)∈G1を計算する第２コミットメント計算部と、
c(i)=m(i)・g2t(i)∈G2(i=1,...,k)を計算する第３コミットメント計算部と、
ca, cb, c(1),...,c(k)を含むコミットメントCを出力するコミットメント出力部と、
da=g2ta∈G2を計算する第１デコミット鍵計算部と、
db=g2tb∈G2を計算する第２デコミット鍵計算部と、
da, dbを含むデコミット鍵Dを出力するデコミット鍵出力部と、
を有するコミットメント生成装置。
【請求項４】
G1，G2，GTが群であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが１以上の整数であり、m→=(m(1),...,m(k))∈G2kがメッセージであり、1/m(i)がm(i)の逆元であり、コミットメント鍵ckが前記群G1の任意の元g(0), g(1),...,g(k), h(0), h(1),..., h(k)∈G1を含み、
ca∈G1, cb∈G1, c(1),...,c(k)∈G2を含むコミットメントCの入力を受け付けるコミットメント入力部と、
da, db∈G2を含むデコミット鍵D、前記メッセージm→、及び前記コミットメント鍵ckの入力を受け付けるオープニング情報入力部と、
関係e(ca, g2)=e(g(0), da)・Πi=1k e(g(i), c(i)/m(i))及びe(cb, g2)=e(h(0), db)・Πi=1k e(h(i), c(i)/m(i))の両方が満たされるかを検証し、両方の前記関係が満たされる場合に前記メッセージm→を受理し、前記関係の少なくとも一方が満たされない場合に前記メッセージm→を不受理とする検証部と、
を有するコミットメント検証装置。
【請求項５】
G1，G2，GTが群であり、G1≠G2であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが１以上の整数であり、m→=(m(1),...,m(k))∈G2kがメッセージであり、1/m(i)がm(i)の逆元であり、コミットメント鍵ckが前記群G1の任意の元g(0), g(1),...,g(k)∈G1を含み、
任意の元ta, t(i)∈Zp (i=1,...,k)を選択する選択部と、
ca=g(0)ta・Πi=1k g(i)t(i)∈G1を計算する第１コミットメント計算部と、
c(i)=m(i)・g2t(i)∈G2(i=1,...,k)を計算する第３コミットメント計算部と、
ca, c(1),...,c(k)を含むコミットメントCを出力するコミットメント出力部と、
da=g2ta∈G2を計算する第１デコミット鍵計算部と、
daを含むデコミット鍵Dを出力するデコミット鍵出力部と、
を有するコミットメント生成装置。
【請求項６】
G1，G2，GTが群であり、G1≠G2であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが１以上の整数であり、m→=(m(1),...,m(k))∈G2kがメッセージであり、1/m(i)がm(i)の逆元であり、コミットメント鍵ckが前記群G1の任意の元g(0), g(1),...,g(k)∈G1を含み、
ca∈G1, c(1),...,c(k)∈G2を含むコミットメントCの入力を受け付けるコミットメント入力部と、
da∈G2を含むデコミット鍵D、前記メッセージm→、及び前記コミットメント鍵ckの入力を受け付けるオープニング情報入力部と、
関係e(ca, g2)=e(g(0), da)・Πi=1k e(g(i), c(i)/m(i))が満たされるかを検証し、前記関係が満たされる場合に前記メッセージm→を受理し、前記関係が満たされない場合に前記メッセージm→を不受理とする検証部と、
を有するコミットメント検証装置。
【請求項７】
G1，G2，GTが群であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが１以上の整数であり、m→=(m(1),...,m(k))∈G2kがメッセージであり、1/m(i)がm(i)の逆元であり、コミットメント鍵ckが前記群G1の任意の元g(0), g(1),...,g(k), h(0), h(1),..., h(k)∈G1を含み、
コミットメント生成装置が、任意の元ta, tb, t(i)∈Zp (i=1,...,k)を選択するステップと、
前記コミットメント生成装置が、ca=g(0)ta・Πi=1k g(i)t(i)∈G1を計算するステップと、
前記コミットメント生成装置が、cb=h(0)tb・Πi=1k h(i)t(i)∈G1を計算するステップと、
前記コミットメント生成装置が、c(i)=m(i)・g2t(i)∈G2 (i=1,...,k)を計算するステップと、
前記コミットメント生成装置が、ca, cb, c(1),...,c(k)を含むコミットメントCを出力するステップと、
前記コミットメント生成装置が、da=g2ta∈G2を計算するステップと、
前記コミットメント生成装置が、db=g2tb∈G2を計算するステップと、
前記コミットメント生成装置が、da, dbを含むデコミット鍵Dを出力するステップと、
コミットメント検証装置が、前記コミットメントCの入力を受け付けるステップと、
前記コミットメント検証装置が、前記メッセージm→、前記コミットメント鍵ck、及び前記デコミット鍵Dの入力を受け付けるステップと、
前記コミットメント検証装置が、関係e(ca, g2)=e(g(0), da)・Πi=1k e(g(i), c(i)/m(i))及びe(cb, g2)=e(h(0), db)・Πi=1k e(h(i), c(i)/m(i))の両方が満たされるかを検証し、両方の前記関係が満たされる場合に前記メッセージm→を受理し、前記関係の少なくとも一方が満たされない場合に前記メッセージm→を不受理とするステップと、を含む、
コミットメント方法。
【請求項８】
G1，G2，GTが群であり、G1≠G2であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが１以上の整数であり、m→=(m(1),...,m(k))∈G2kがメッセージであり、1/m(i)がm(i)の逆元であり、コミットメント鍵ckが前記群G1の任意の元g(0), g(1),...,g(k)∈G1を含み、
コミットメント生成装置が、任意の元ta, t(i)∈Zp (i=1,...,k)を選択するステップと、
前記コミットメント生成装置が、ca=g(0)ta・Πi=1k g(i)t(i)∈G1を計算するステップと、
前記コミットメント生成装置が、c(i)=m(i)・g2t(i)∈G2 (i=1,...,k)を計算するステップと、
前記コミットメント生成装置が、ca, c(1),...,c(k)を含むコミットメントCを出力するステップと、
前記コミットメント生成装置が、da=g2ta∈G2を計算するステップと、
前記コミットメント生成装置が、daを含むデコミット鍵Dを出力するステップと、
コミットメント検証装置が、前記コミットメントCの入力を受け付けるステップと、
前記コミットメント検証装置が、前記メッセージm→、前記コミットメント鍵ck、及び前記デコミット鍵Dの入力を受け付けるステップと、
前記コミットメント検証装置が、関係e(ca, g2)=e(g(0), da)・Πi=1k e(g(i), c(i)/m(i))が満たされるかを検証し、前記関係が満たされる場合に前記メッセージm→を受理し、前記関係が満たされない場合に前記メッセージm→を不受理とするステップと、
を有するコミットメント方法。
【請求項９】
選択部と第１コミットメント計算部と第２コミットメント計算部と第３コミットメント計算部とコミットメント出力部と第１デコミット鍵計算部と第２デコミット鍵計算部とデコミット鍵出力部とを有するコミットメント生成装置が実行するコミットメント生成方法であって、
G1，G2，GTが群であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが１以上の整数であり、m→=(m(1),...,m(k))∈G2kがメッセージであり、1/m(i)がm(i)の逆元であり、コミットメント鍵ckが前記群G1の任意の元g(0), g(1),...,g(k), h(0), h(1),..., h(k)∈G1を含み、
前記選択部が、任意の元ta, tb, t(i)∈Zp (i=1,...,k)を選択するステップと、
前記第１コミットメント計算部が、ca=g(0)ta・Πi=1k g(i)t(i)∈G1を計算するステップと、
前記第２コミットメント計算部が、cb=h(0)tb・Πi=1k h(i)t(i)∈G1を計算するステップと、
前記第３コミットメント計算部が、c(i)=m(i)・g2t(i)∈G2 (i=1,...,k)を計算するステップと、
前記コミットメント出力部が、ca, cb, c(1),...,c(k)を含むコミットメントCを出力するステップと、
前記第１デコミット鍵計算部が、da=g2ta∈G2を計算するステップと、
前記第２デコミット鍵計算部が、db=g2tb∈G2を計算するステップと、
前記デコミット鍵出力部が、da, dbを含むデコミット鍵Dを出力するステップと、
を有するコミットメント生成方法。
【請求項１０】
コミットメント入力部とオープニング情報入力部と検証部とを有するコミットメント検証装置が実行するコミットメント検証方法であって、
G1，G2，GTが群であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが１以上の整数であり、m→=(m(1),...,m(k))∈G2kがメッセージであり、1/m(i)がm(i)の逆元であり、コミットメント鍵ckが前記群G1の任意の元g(0), g(1),...,g(k), h(0), h(1),..., h(k)∈G1を含み、
前記コミットメント入力部が、ca∈G1, cb∈G1, c(1),...,c(k)∈G2を含むコミットメントCの入力を受け付けるステップと、
前記オープニング情報入力部が、da, db∈G2を含むデコミット鍵D、前記メッセージm→、及び前記コミットメント鍵ckの入力を受け付けるステップと、
前記検証部が、関係e(ca, g2)=e(g(0), da)・Πi=1k e(g(i), c(i)/m(i))及びe(cb, g2)=e(h(0), db)・Πi=1k e(h(i), c(i)/m(i))の両方が満たされるかを検証し、両方の前記関係が満たされる場合に前記メッセージm→を受理し、前記関係の少なくとも一方が満たされない場合に前記メッセージm→を不受理とするステップと、
を有するコミットメント検証方法。
【請求項１１】
選択部と第１コミットメント計算部と第３コミットメント計算部とコミットメント出力部と第１デコミット鍵計算部とデコミット鍵出力部とを有するコミットメント生成装置が実行するコミットメント生成方法であって、
G1，G2，GTが群であり、G1≠G2であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが１以上の整数であり、m→=(m(1),...,m(k))∈G2kがメッセージであり、1/m(i)がm(i)の逆元であり、コミットメント鍵ckが前記群G1の任意の元g(0), g(1),...,g(k)∈G1を含み、
前記選択部が、任意の元ta, t(i)∈Zp (i=1,...,k)を選択するステップと、
前記第１コミットメント計算部が、ca=g(0)ta・Πi=1k g(i)t(i)∈G1を計算するステップと、
前記第３コミットメント計算部が、c(i)=m(i)・g2t(i)∈G2 (i=1,...,k)を計算するステップと、
前記コミットメント出力部が、ca, c(1),...,c(k)を含むコミットメントCを出力するステップと、
前記第１デコミット鍵計算部が、da=g2ta∈G2を計算するステップと、
前記デコミット鍵出力部が、daを含むデコミット鍵Dを出力するステップと、
を有するコミットメント生成方法。
【請求項１２】
コミットメント入力部とオープニング情報入力部と検証部とを有するコミットメント検証装置が実行するコミットメント検証方法であって、
G1，G2，GTが群であり、G1≠G2であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが１以上の整数であり、m→=(m(1),...,m(k))∈G2kがメッセージであり、1/m(i)がm(i)の逆元であり、コミットメント鍵ckが前記群G1の任意の元g(0), g(1),...,g(k)∈G1を含み、
前記コミットメント入力部が、ca∈G1, c(1),...,c(k)∈G2を含むコミットメントCの入力を受け付けるステップと、
前記オープニング情報入力部が、da∈G2を含むデコミット鍵D、前記メッセージm→、及び前記コミットメント鍵ckの入力を受け付けるステップと、
前記検証部が、関係e(ca, g2)=e(g(0), da)・Πi=1k e(g(i), c(i)/m(i))が満たされるかを検証し、前記関係が満たされる場合に前記メッセージm→を受理し、前記関係が満たされない場合に前記メッセージm→を不受理とするステップと、
を有するコミットメント検証方法。
【請求項１３】
請求項３又は５のコミットメント生成装置の各部としてコンピュータを機能させるためのプログラム。
【請求項１４】
請求項４又は６のコミットメント検証装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号技術に関し、特にコミットメント方式に関する。
【背景技術】
【０００２】
コミットメント方式は、電子現金システムの要素技術であるブラインド署名などの暗号プロトコルを構成する為に用いられる暗号要素技術である。特に、Groth-Sahaiによる効率的なゼロ知識証明と組み合わせて用いるためには、メッセージ、コミットメント、コミットメント鍵、デコミットメント鍵の要素のすべてが双線形写像を持つ群上の要素であることが望ましい。このような性質を群構造維持と呼ぶ。
【０００３】
双線形写像を持つ群上で構成されたコミットメント方式について、以下に３つの従来法を説明する。
＜従来方式１（非特許文献１のB.2節参照）＞
［コミットメント鍵の生成：COM.Key(Λ)］
γ∈Zpが選択され、f~=g2γとされる。コミットメント鍵としてck=(Λ, f~)が公開される。ただし、g2は群G2の生成元であり、Λはシステムパラメータである。
［コミットメント生成：COM.Com(ck, m)］
ランダムにδ∈Zpが選択され、コミットメントC=g2m・(f~)δが計算されて公開される。ただし、m∈Zpはメッセージを表す。
［オープニング：COM.Open(ck, m, C)］
デコミット鍵D=dk=g1δ∈G1が公開される。ただし、g1は群G1の生成元である。
［コミットメント検証：COM.Vrf(ck, m, C, D)］
以下の検証式が成り立つ場合、公開されたメッセージmがコミットされていたメッセージとして受理される。ただし、eは双線形写像を表す。
e(g1, C/g2m)=e(D, f~)
【０００４】
＜従来方式２（非特許文献１のB.4節，非特許文献２参照）＞
［コミットメント鍵の生成：COM.Key(Λ)］
ランダムにgt, hω∈G1、及びγ(i),δ(i)∈Zp* (i=1,...,k)が選択され、gi=gtγ(i)、及びhi=hωδ(i)が計算される。コミットメント鍵としてck=(gt, hω, g1, h1,...,gk, hk)が公開される。
［コミットメント生成：COM.Com(ck, M→)］
t, ω∈G2がランダムに選択され、以下が計算される。ただし、M→はメッセージM→=(m1,...,mk)∈G2kである。
C1=e(gt, t)・Πi=1ke(gi, mi)∈GT
C2=e(hω, ω)・Πi=1ke(hi, mi)∈GT
コミットメントC=(C1, C2)が公開される。
［オープニング：COM.Open(ck, M→, C)］
デコミット鍵D=(t, ω)が公開される。
［コミットメント検証：COM.Vrf(ck, M→, C, D)］
以下の検証式が成り立つ場合、公開されたメッセージM→がコミットされていたメッセージとして受理される。
C1=e(gt, t)・Πi=1ke(gi, mi)
C2=e(hω, ω)・Πi=1ke(hi, mi)
【０００５】
＜従来方式３（非特許文献１のB.3節参照）＞
［コミットメント鍵の生成：COM.Key(Λ)］
ランダムにgt, hω∈G2、及びγ(i),δ(i)∈Zp* (i=1,...,k)が選択され、gi=gtγ(i)、及びhi=hωδ(i)が計算される。コミットメント鍵としてck=(Λ, gt, hω, g1, h1,...,gk, hk)が公開される。
［コミットメント生成：COM.Com(ck, M→)］
t, ω∈G2がランダムに選択され、以下が計算される。RandOneSide((α0,β0),...,(αk,βk))は、β0,...,βkをβ0’,...,βk’にランダム化する処理を意味する。ただし、e(α0,β0)・...・e(αk,βk)=e(α0,β0’)・...・e(αk,βk’)が満たされる。
{caj}j=0k=RandOneSide((gt, t), (g1, m1),...,(gk, mk))
{cbj}j=0k=RandOneSide((hω, ω), (h1, m1),...,(hk, mk))
コミットメントとしてC=({caj}j=0k, {cbj}j=0k)が公開される。
［オープニング：COM.Open(ck, M→, C)］
デコミット鍵D=(t, ω)が公開される。
［コミットメント検証：COM.Vrf(ck, M→, C, D)］
以下の検証式が成り立つ場合、公開されたメッセージM→がコミットされていたメッセージとして受理される。
C1=e(gt, t)・Πi=1ke(gi, mi)
C2=e(hω, ω)・Πi=1ke(hi, mi)
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】M. Abe, K. Haralambiev,M. Ohkubo, “Signing on Elements in Bilinear Groups for Modular Protocol Design,” IACR e-print archive 2010/133
【非特許文献２】M. Abe, G. Fuchsbauer, J. Groth, K. Haralambiev, and M. Ohkubo, “Structure-Preserving Signatures and Commitments to Group Elements,” Crypto 2010, LNCS 6223, pp. 209-236, Springer, 2010
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来方式は群構造維持の性質を有しない。
まず従来方式１は、メッセージmが群の要素ではなく、Zpの要素であるため、群構造維持の性質を有しない。次に従来方式１では、コミットメント検証がメッセージmごとに行われるため、検証式の数がメッセージmの数に比例して増大する。効率的なゼロ知識証明では、証明すべき関係式の数が効率に大きく影響するため従来方式１をゼロ知識証明と組み合わせる場合の計算コストが大きい。
【０００８】
従来方式２では、メッセージm1,...,mkが双線形写像を持つ群G2の要素であり、メッセージの個数（kの値）に拘わらず検証式の数が一定である。しかしコミットメントが群GTの要素であり、群GTは双線形写像を持たない。よって、従来方式２は群構造維持の性質を有しない。
【０００９】
従来方式３では、メッセージ、コミットメント、コミットメント鍵、デコミットメント鍵の要素のすべてが双線形写像を持つ群上の要素であり、群構造維持の性質を有する。また、メッセージの個数（kの値）に拘わらず検証式の数が一定である。しかしながら、従来方式３では、コミットメントの群要素の個数がメッセージの群要素の個数の２倍以上（2・k+2個）となり、計算コストが大きい。
本発明はこのような点に鑑みてなされたものであり、群構造維持の性質を有し、計算コストが小さいコミットメント方式を提供することを目的とする。
【課題を解決するための手段】
【００１０】
第１の本発明では、G1，G2，GTが群であり、g2が群G2の生成元であり、eが群G1と群G2の直積群G1×G2の元に対して群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが１以上の整数であり、m→=(m(1),...,m(k))∈G2kがメッセージであり、1/m(i)がm(i)の逆元であり、コミットメント鍵ckが群G1の任意の元g(0), g(1),...,g(k), h(0), h(1),..., h(k)∈G1を含む。コミットメント生成装置は、任意の元ta, tb, t(i)∈Zp (i=1,...,k)を選択し、ca=g(0)ta・Πi=1k g(i)t(i)∈G1，cb=h(0)tb・Πi=1k h(i)t(i)∈G1，c(i)=m(i)・g2t(i)∈G2 (i=1,...,k)を計算し、ca, cb, c(1),...,c(k)を含むコミットメントCを出力する。さらにコミットメント生成装置は、da=g2ta∈G2，db=g2tb∈G2を計算し、da, dbを含むデコミット鍵Dを出力する。コミットメント検証装置は、コミットメントCの入力を受け付け、メッセージm→、コミットメント鍵ck、及びデコミット鍵Dの入力を受け付け、関係e(ca, g2)=e(g(0), da)・Πi=1k e(g(i), c(i)/m(i))及びe(cb, g2)=e(h(0), db)・Πi=1k e(h(i), c(i)/m(i))の両方が満たされるかを検証し、両方の関係が満たされる場合にメッセージm→を受理し、関係の少なくとも一方が満たされない場合にメッセージm→を不受理とする。
【００１１】
第２の本発明では、G1，G2，GTが群であり、G1≠G2であり、g2が群G2の生成元であり、eが群G1と群G2の直積群G1×G2の元に対して群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが１以上の整数であり、m→=(m(1),...,m(k))∈G2kがメッセージであり、1/m(i)がm(i)の逆元であり、コミットメント鍵ckが群G1の任意の元g(0), g(1),...,g(k)∈G1を含む。コミットメント生成装置は、任意の元ta, t(i)∈Zp (i=1,...,k)を選択し、ca=g(0)ta・Πi=1k g(i)t(i)∈G1，c(i)=m(i)・g2t(i)∈G2(i=1,...,k)を計算し、ca, c(1),...,c(k)を含むコミットメントCを出力する。さらにコミットメント生成装置は、da=g2ta∈G2を計算し、daを含むデコミット鍵Dを出力する。コミットメント検証装置は、コミットメントCの入力を受け付け、メッセージm→、コミットメント鍵ck、及びデコミット鍵Dの入力を受け付け、関係e(ca, g2)=e(g(0), da)・Πi=1k e(g(i), c(i)/m(i))が満たされるかを検証し、関係が満たされる場合にメッセージm→を受理し、関係が満たされない場合にメッセージm→を不受理とする。
【発明の効果】
【００１２】
本発明は、群構造維持の性質を有する。また、kの値にかかわらず検証式の数が一定であり、計算コストが小さい。
【図面の簡単な説明】
【００１３】
【図１】図１は、第１，２実施形態のコミットメントシステムの構成を説明するためのブロック図である。
【図２】図２Ａは、第１実施形態の管理装置の機能構成を説明するためのブロック図であり、図２Ｂは、第１実施形態のコミットメント検証装置の機能構成を説明するためのブロック図である。
【図３】図３は、第１実施形態のコミットメント生成装置の機能構成を説明するためのブロック図である。
【図４】図４は、第１実施形態のコミットメント鍵生成方法を説明するためのブロック図である。
【図５】図５は、第１実施形態のコミットメント生成方法を説明するためのブロック図である。
【図６】図６は、第１実施形態のコミットメント検証方法を説明するためのブロック図である。
【図７】図７Ａは、第２実施形態の管理装置の機能構成を説明するためのブロック図であり、図７Ｂは、第２実施形態のコミットメント検証装置の機能構成を説明するためのブロック図である。
【図８】図８は、第２実施形態のコミットメント生成装置の機能構成を説明するためのブロック図である。
【図９】図９は、第２実施形態のコミットメント鍵生成方法を説明するためのブロック図である。
【図１０】図１０は、第２実施形態のコミットメント生成方法を説明するためのブロック図である。
【図１１】図１１は、第２実施形態のコミットメント検証方法を説明するためのブロック図である。
【発明を実施するための形態】
【００１４】
図面を参照して本発明の実施形態を説明する。
〔第１実施形態〕
第１実施形態を説明する。
本形態では、G1，G2，GTが群（例えば巡回群）であり、g1が群G1の生成元であり、g2が群G2の生成元である。本形態の場合、G1=G2であってもよいし、G1≠G2であってもよい。α∈G1に対する1/α∈G1はαの逆元α-1∈G1を表し、β∈G2に対する1/β∈G2はβの逆元β-1∈G2を表す。eは群G1と群G2の直積群G1×G2の元に対して群GTの元を得る双線形写像G1×G2→GTである。双線形写像eの具体例は、WeilペアリングやTateペアリングなどのペアリングである。Zpは位数pの整数剰余環である。本形態の位数pは素数であり、群G1，G2の位数もpである。本形態のシステムパラメータをΛ=(p,G1,G2,GT,e,g1,g2)とする。
＜構成＞
図１に例示するように、本形態のコミットメントシステム１は、管理装置１１０、コミットメント生成装置１２０、及びコミットメント検証装置１３０を有し、ネットワークを通じて通信可能に構成されている。
【００１５】
図２Ａに例示するように、本形態の管理装置１１０は、出力部１１１、一時メモリ１１２ａ、記憶部１１２ｂ、制御部１１３、選択部１１４ａ，１１４ｂ、及びコミットメント鍵生成部１１４ｃを有する。本形態の管理装置１１０は、例えば、CPU(central processing unit)、RAM(random-access memory)等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて実行されることで構築される特別な装置である。本形態の管理装置１１０は、制御部１１３の制御のもとで各処理を実行する。各処理で得られたデータは、一時メモリ１１２ａ又は記憶部１１２ｂに格納され、必要に応じて読み出されて他の処理に利用される。
【００１６】
図２Ｂに例示するように、本形態のコミットメント検証装置１３０は、入力部１３１（「コミットメント入力部」「オープニング情報入力部」に相当）、一時メモリ１３２ａ、記憶部１３２ｂ、制御部１３３、及び検証部１３４を有する。本形態のコミットメント検証装置１３０は、公知又は専用のコンピュータに特別なプログラムが読み込まれて実行されることで構築される特別な装置である。本形態のコミットメント検証装置１３０は、制御部１３３の制御のもとで各処理を実行する。各処理で得られたデータは、一時メモリ１３２ａ又は記憶部１３２ｂに格納され、必要に応じて読み出されて他の処理に利用される。
【００１７】
図３に例示するように、本形態のコミットメント生成装置１２０は、入力部１２１ａ、出力部１２１ｂ（「コミットメント出力部」及び「デコミット鍵出力部」に相当）、一時メモリ１２２ａ、記憶部１２２ｂ、制御部１２３、選択部１２４ａ、コミットメント計算部１２４ｂ〜１２４ｄ、コミットメント生成部１２４ｅ、デコミット鍵計算部１２４ｆ，１２４ｇ、及びデコミット鍵生成部１２４ｈを有する。本形態のコミットメント生成装置１２０は、公知又は専用のコンピュータに特別なプログラムが読み込まれて実行されることで構築される特別な装置である。本形態のコミットメント生成装置１２０は、制御部１２３の制御のもとで各処理を実行する。各処理で得られたデータは、一時メモリ１２２ａ又は記憶部１２２ｂに格納され、必要に応じて読み出されて他の処理に利用される。
【００１８】
＜コミットメント鍵生成処理＞
図４に例示するように、システムパラメータΛ=(p,G1,G2,GT,e,g1,g2)が入力された管理装置１１０（図２Ａ）の選択部１１４ａが、任意の元g(0),h(0)∈G1をランダムに選択し（ステップＳ１０１）、選択部１１４ｂが任意の元g(i),h(i)∈G1 (i=1,...,k)をランダムに選択する（ステップＳ１０２）。任意の元g(0),h(0)と任意の元g(i),h(i)とは互いに独立に選択されたものでもよいし、ランダムに選択された任意の元ξ(i),η(i)∈Zpに対してg(i)=g(0)ξ(i), h(i)=h(0)η(i) (i=1,...,k)を満たすものであってもよい。システムパラメータΛと当該任意の元g(0),h(0),g(i),h(i) (i=1,...,k)はコミットメント鍵生成部１１４ｃに入力される。コミットメント鍵生成部１１４ｃは、システムパラメータΛと任意の元g(0), g(1),...,g(k), h(0), h(1),..., h(k)∈G1とを含むコミットメント鍵ck=(Λ, g(0), h(0), g(1), h(1),...,g(k), h(k))を生成する（ステップＳ１０３）。コミットメント鍵ckは記憶部１１２ｂに格納される。記憶部１１２ｂに格納されたコミットメント鍵ckは、例えば、他の装置からの要求等に応じて読み出され、出力部１１１から出力される（ステップＳ１０４）。
【００１９】
＜コミットメント生成処理＞
管理装置１１０から出力されたコミットメント鍵ckは、ネットワーク経由でコミットメント生成装置１２０（図３）に送られる。図５に例示するように、コミットメント鍵ckは、入力部１２１ａに入力されて記憶部１２２ｂに格納される（ステップＳ１１１）。入力部１２１ａには、メッセージm→=(m(1),...,m(k))∈G2kが入力され、それが記憶部１２２ｂに格納される（ステップＳ１１２）。ただし、kは１以上の予め定められた整数であり、m(i)∈G2 (i=1,...,k)を満たす。
【００２０】
選択部１２４ａは、任意の元ta, tb, t(i)∈Zp (i=1,...,k)をランダムに選択して出力する（ステップＳ１１３）。コミットメント計算部１２４ｂには、記憶部１２２ｂから読み出されたコミットメント鍵ckの要素、及び選択部１２４ａから出力された任意の元ta, t(i)が入力される。コミットメント計算部１２４ｂは、これらを用いてca=g(0)ta・Πi=1k g(i)t(i)∈G1を計算して出力する（ステップＳ１１４）。コミットメント計算部１２４ｃには、記憶部１２２ｂから読み出されたコミットメント鍵ckの要素、及び選択部１２４ａから出力された任意の元tb, t(i)が入力される。コミットメント計算部１２４ｃは、これらを用いてcb=h(0)tb・Πi=1k h(i)t(i)∈G1を計算して出力する（ステップＳ１１５）。コミットメント計算部１２４ｄには、記憶部１２２ｂから読み出されたコミットメント鍵ckの要素、メッセージm→、及び選択部１２４ａから出力された任意の元t(i)が入力される。コミットメント計算部１２４ｄは、これらを用いてc(i)=m(i)・g2t(i)∈G2(i=1,...,k)を計算して出力する（ステップＳ１１６）。コミットメント計算部１２４ｂ，１２４ｃ，１２４ｄから出力されたca，cb，c(1),...,c(k)は、コミットメント生成部１２４ｅに入力される。コミットメント生成部１２４ｅは、ca, cb, c(1),...,c(k)を含むコミットメントC=(ca, cb, c(1),...,c(k))を生成する。コミットメントCは記憶部１２２ｂに格納される。
【００２１】
デコミット鍵計算部１２４ｆには、記憶部１２２ｂから読み出された生成元g2、及び選択部１２４ａから出力された任意の元taが入力される。デコミット鍵計算部１２４ｆは、これらを用いてda=g2ta∈G2を計算して出力する（ステップＳ１１８）。デコミット鍵計算部１２４ｇには、記憶部１２２ｂから読み出された生成元g2、及び選択部１２４ａから出力された任意の元tbが入力される。デコミット鍵計算部１２４ｇは、これらを用いてdb=g2tb∈G2を計算して出力する（ステップＳ１１９）。デコミット鍵生成部１２４ｈには、デコミット鍵計算部１２４ｆ，１２４ｇから出力されたda及びdbが入力される。デコミット鍵生成部１２４ｈは、da及びdbを含むデコミット鍵D=(da, db)を生成して出力する（ステップＳ１２０）。デコミット鍵Dは、記憶部１２２ｂに格納される。
【００２２】
記憶部１２２ｂに格納されたコミットメントCは、任意の契機で出力され、ネットワーク経由でコミットメント検証装置１３０に送信される（ステップＳ１２１）。コミットメントCは、コミットメント検証装置１３０（図２Ｂ）の入力部１３１に入力され、記憶部１３２ｂに格納される。
【００２３】
＜コミットメント検証処理＞
図６に例示するように、管理装置１１０から出力されたコミットメント鍵ckは、ネットワーク経由でコミットメント検証装置１３０（図２Ｂ）にも送られ、入力部１３１に入力されて記憶部１３２ｂに格納される（ステップＳ１２１）。オープニング時には、コミットメント生成装置１２０（図３）の記憶部１２２ｂに格納されていたメッセージm→及びデコミット鍵Dが読み出され、出力部１２１ｂから出力される。メッセージm→及びデコミット鍵Dは、ネットワーク経由でコミットメント検証装置１３０（図２Ｂ）に送信され、入力部１３１に入力されて記憶部１３２ｂに格納される（ステップＳ１２２）。
【００２４】
検証部１３４は、記憶部１３２ｂから読み出したコミットメント鍵ck、コミットメントC、メッセージm→、及びデコミット鍵Dが以下の関係を満たすかを判定する（ステップＳ１２３）。
e(ca, g2)=e(g(0), da)・Πi=1k e(g(i), c(i)/m(i))  …(1)
検証式(1)の関係を満たさない場合、検証部１３４はメッセージm→を不受理として0を出力する（ステップＳ１２５）。
【００２５】
式(1)の関係を満たす場合、次に検証部１３４は記憶部１３２ｂから読み出したコミットメント鍵ck、コミットメントC、メッセージm→、及びデコミット鍵Dが以下の関係を満たすかを判定する（ステップＳ１２４）。
e(cb, g2)=e(h(0), db)・Πi=1k e(h(i), c(i)/m(i))  …(2)
検証式(2)の関係を満たさない場合、検証部１３４はメッセージm→を不受理として0を出力する（ステップＳ１２５）。一方、検証式(2)の関係を満たす場合、検証部１３４はメッセージm→がコミットメントCでコミットされていたメッセージであるとして受理し、1を出力する（ステップＳ１２６）。
【００２６】
＜本形態の特徴＞
ca=g(0)ta・Πi=1k g(i)t(i)，cb=h(0)tb・Πi=1k h(i)t(i)，c(i)=m(i)・g2t(i)，da=g2ta，db=g2tbより、オープニング時にコミットメント検証装置１３０に入力されたメッセージm→がコミットメントCに対応するものであれば、検証式(1)(2)は以下のように変形でき、検証式(1)(2)の関係を共に満たす。
式(1):
e(g(0)ta・Πi=1k g(i)t(i), g2)=e(g(0), g2ta)・Πi=1k e(g(i), m(i)・g2t(i)/m(i))
e(g(0)ta・g(1)t(1)・...・g(k)t(k) , g2)=e(g(0), g2ta)・e(g(1), g2t(1))・...・e(g(k), g2t(k))
e(g(0)ta・...・g(k)t(k), g2)=e(g(0)ta・...・g(k)t(k), g2)
式(2):
e(h(0)tb・Πi=1k h(i)t(i), g2)=e(h(0), g2tb)・Πi=1k e(h(i), m(i)・g2t(i)/m(i))
e(h(0)tb・h(1)t(1)・...・h(k)t(k), g2)=e(h(0), g2tb)・e(h(1), g2t(1))・...・e(h(k), g2t(k))
e(h(0)tb・h(1)t(1)・...・h(k)t(k), g2)=e(h(0)tb・h(1)t(1)・...・h(k)t(k), g2)
一方、メッセージm→がコミットメントCに対応するものでなければ、式(1)(2)の関係は満たされない。
【００２７】
本形態のメッセージm→、コミットメントC、コミットメント鍵ck、デコミットメント鍵Dの要素のすべてが双線形写像eを持つ群上の要素であり、本形態のコミットメント方式は群構造維持の性質を有する。よって、群構造を維持したままですべての演算ができ、暗号プロトコルへの拡張が容易である。
【００２８】
本形態のコミットメント方式では、メッセージm(k)の個数（kの値）にかかわらず、２個の検証式(1)(2)のみで検証処理が実行できる。さらに、メッセージの群要素の個数kに対するコミットメントCの群要素の個数がk+2であり、従来方式３の群要素の個数2・k+2よりも小さい。よって、従来方式１，３よりも計算コスト・通信コスト・記憶メモリコストが低い。
〔第２実施形態〕
第２実施形態を説明する。以下では第１実施形態との相違点を中心に説明する。
本形態では、G1，G2，GTが群（例えば巡回群）であり、g1が群G1の生成元であり、g2が群G2の生成元である。本形態の場合、G1≠G2である。本形態の位数pは素数であり、群G1，G2の位数もpである。本形態のシステムパラメータをΛsxdh=(p,G1,G2,GT,e,g1,g2)とする。
＜構成＞
図１に例示するように、本形態のコミットメントシステム２は、管理装置２１０、コミットメント生成装置２２０、及びコミットメント検証装置２３０を有し、ネットワークを通じて通信可能に構成されている。
【００２９】
図７Ａに例示するように、本形態の管理装置２１０は、出力部１１１、一時メモリ１１２ａ、記憶部２１２ｂ、制御部１１３、選択部２１４ａ，２１４ｂ、及びコミットメント鍵生成部２１４ｃを有する。本形態の管理装置２１０は、例えば、公知又は専用のコンピュータに特別なプログラムが読み込まれて実行されることで構築される特別な装置である。本形態の管理装置２１０は、制御部１１３の制御のもとで各処理を実行する。各処理で得られたデータは、一時メモリ１１２ａ又は記憶部２１２ｂに格納され、必要に応じて読み出されて他の処理に利用される。
【００３０】
図７Ｂに例示するように、本形態のコミットメント検証装置２３０は、入力部２３１（「コミットメント入力部」「オープニング情報入力部」に相当）、一時メモリ１３２ａ、記憶部２３２ｂ、制御部１３３、及び検証部２３４を有する。本形態のコミットメント検証装置２３０は、公知又は専用のコンピュータに特別なプログラムが読み込まれて実行されることで構築される特別な装置である。本形態のコミットメント検証装置２３０は、制御部１３３の制御のもとで各処理を実行する。各処理で得られたデータは、一時メモリ１３２ａ又は記憶部２３２ｂに格納され、必要に応じて読み出されて他の処理に利用される。
【００３１】
図８に例示するように、本形態のコミットメント生成装置２２０は、入力部２２１ａ、出力部２２１ｂ（「コミットメント出力部」及び「デコミット鍵出力部」に相当）、一時メモリ１２２ａ、記憶部２２２ｂ、制御部１２３、選択部２２４ａ、コミットメント計算部１２４ｂ，１２４ｄ、コミットメント生成部２２４ｅ、デコミット鍵計算部１２４ｆ、及びデコミット鍵生成部２２４ｈを有する。本形態のコミットメント生成装置２２０は、公知又は専用のコンピュータに特別なプログラムが読み込まれて実行されることで構築される特別な装置である。本形態のコミットメント生成装置２２０は、制御部１２３の制御のもとで各処理を実行する。各処理で得られたデータは、一時メモリ１２２ａ又は記憶部２２２ｂに格納され、必要に応じて読み出されて他の処理に利用される。
【００３２】
＜コミットメント鍵生成処理＞
図９に例示するように、システムパラメータΛsxdh=(p,G1,G2,GT,e,g1,g2)が入力された管理装置２１０（図７Ａ）の選択部２１４ａが、任意の元g(0)∈G1をランダムに選択し（ステップＳ２０１）、選択部２１４ｂが任意の元g(i)∈G1 (i=1,...,k)をランダムに選択する（ステップＳ２０２）。任意の元g(0)と任意の元g(i)とは互いに独立に選択されものでもよいし、ランダムに選択された任意の元ξ(i)∈Zpに対してg(i)=g(0)ξ(i) (i=1,...,k)を満たすものであってもよい。システムパラメータΛsxdhと当該任意の元g(0),g(i) (i=1,...,k)はコミットメント鍵生成部２１４ｃに入力される。コミットメント鍵生成部２１４ｃは、システムパラメータΛsxdhと任意の元g(0), g(1),...,g(k)∈G1とを含むコミットメント鍵ck=(Λsxdh, g(0), g(1),...,g(k))を生成する（ステップＳ２０３）。コミットメント鍵ckは記憶部２１２ｂに格納される。記憶部２１２ｂに格納されたコミットメント鍵ckは、例えば、他の装置からの要求等に応じて読み出され、出力部２１１から出力される（ステップＳ２０４）。
【００３３】
＜コミットメント生成処理＞
管理装置２１０から出力されたコミットメント鍵ckは、ネットワーク経由でコミットメント生成装置２２０（図８）に送られる。図１０に例示するように、コミットメント鍵ckは、入力部２２１ａに入力されて記憶部２２２ｂに格納される（ステップＳ２１１）。入力部２２１ａには、メッセージm→=(m(1),...,m(k))∈G2kが入力され、それが記憶部２２２ｂに格納される（ステップＳ２１２）。
【００３４】
選択部２２４ａは、任意の元ta, t(i)∈Zp (i=1,...,k)をランダムに選択して出力する（ステップＳ２１３）。コミットメント計算部１２４ｂには、記憶部２２２ｂから読み出されたコミットメント鍵ckの要素、及び選択部２２４ａから出力された任意の元ta, t(i)が入力される。コミットメント計算部１２４ｂは、これらを用いてca=g(0)ta・Πi=1k g(i)t(i)∈G1を計算して出力する（ステップＳ１１４）。コミットメント計算部１２４ｄには、記憶部２２２ｂから読み出されたコミットメント鍵ckの要素、メッセージm→、及び選択部２２４ａから出力された任意の元t(i)が入力される。コミットメント計算部１２４ｄは、これらを用いてc(i)=m(i)・g2t(i)∈G2(i=1,...,k)を計算して出力する（ステップＳ１１６）。コミットメント計算部１２４ｂ，１２４ｄから出力されたca，c(1),...,c(k)は、コミットメント生成部２２４ｅに入力される。コミットメント生成部２２４ｅは、ca, c(1),...,c(k)を含むコミットメントC=(ca, c(1),...,c(k))を生成する。コミットメントCは記憶部２２２ｂに格納される。
【００３５】
デコミット鍵計算部１２４ｆには、記憶部２２２ｂから読み出された生成元g2、及び選択部２２４ａから出力された任意の元taが入力される。デコミット鍵計算部１２４ｆは、これらを用いてda=g2ta∈G2を計算して出力する（ステップＳ１１８）。デコミット鍵生成部２２４ｈには、デコミット鍵計算部１２４ｆから出力されたdaが入力される。デコミット鍵生成部２２４ｈは、daを含むデコミット鍵D=(da)を生成して出力する（ステップＳ２２０）。デコミット鍵Dは、記憶部２２２ｂに格納される。
【００３６】
記憶部２２２ｂに格納されたコミットメントCは、任意の契機で出力され、ネットワーク経由でコミットメント検証装置２３０に送信される（ステップＳ２２１）。コミットメントCは、コミットメント検証装置２３０（図７Ｂ）の入力部２３１に入力され、記憶部２３２ｂに格納される。
【００３７】
＜コミットメント検証処理＞
図１１に例示するように、管理装置２１０から出力されたコミットメント鍵ckは、ネットワーク経由でコミットメント検証装置２３０（図７Ｂ）にも送られ、入力部２３１に入力されて記憶部２３２ｂに格納される（ステップＳ２２１）。オープニング時には、コミットメント生成装置２２０（図８）の記憶部２２２ｂに格納されていたメッセージm→及びデコミット鍵Dが読み出され、出力部２２１ｂから出力される。メッセージm→及びデコミット鍵Dは、ネットワーク経由でコミットメント検証装置２３０（図７Ｂ）に送信され、入力部２３１に入力されて記憶部２３２ｂに格納される（ステップＳ２２２）。
【００３８】
検証部２３４は、記憶部２３２ｂから読み出したコミットメント鍵ck、コミットメントC、メッセージm→、及びデコミット鍵Dが前述の検証式(1)の関係を満たすかを判定する（ステップＳ１２３）。
検証式(1)の関係を満たさない場合、検証部２３４はメッセージm→を不受理として0を出力する（ステップＳ２２５）。式(1)の関係を満たす場合、検証部２３４はメッセージm→がコミットメントCでコミットされていたメッセージであるとして受理し、1を出力する（ステップＳ２２６）。
【００３９】
＜本形態の特徴＞
本形態のメッセージm→、コミットメントC、コミットメント鍵ck、デコミットメント鍵Dの要素のすべてが双線形写像eを持つ群上の要素であり、本形態のコミットメント方式は群構造維持の性質を有する。よって、群構造を維持したままですべての演算ができ、暗号プロトコルへの拡張が容易である。
【００４０】
本形態のコミットメント方式では、メッセージm(k)の個数（kの値）にかかわらず、１個の検証式(1)のみで検証処理が実行できる。さらに、メッセージの群要素の個数kに対するコミットメントCの群要素の個数がk+1であり、従来方式３の群要素の個数2・k+2よりも小さい。よって、従来方式１，３よりも計算コスト・通信コスト・記憶メモリコストが低い。
【００４１】
〔その他の変形例等〕
本発明は上述の各実施形態に限定されるものではない。例えば、上述の各実施形態では、本形態の位数pが素数であり、群G1，G2の位数もpであることとした。しかし、プロトコルに要求される安全性の程度によっては、位数pが素数以外であってもよく、群G1，G2の位数がp以外であってもよい。群GTの位数もpであってもよいし、pでなくてもよい。また、上記の実施形態では各装置がネットワーク経由で通信を行うこととしたが、各装置がＩＣカード等の可搬型記録媒体を介して情報のやり取りを行ってもよい。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００４２】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。また、上記の実施形態では、コンピュータ上で所定のプログラムを実行させることにより、各装置を構成することとしたが、これらの処理内容の少なくとも一部が集積回路等のハードウェアによって実現されてもよい。
【符号の説明】
【００４３】
１，２  コミットメントシステム
１１０，２１０  管理装置
１２０，２２０  コミットメント生成装置
１３０，２３０  コミットメント検証相当
【図１】
0005698109.tif 000002
【図２】
0005698109.tif 000003
【図３】
0005698109.tif 000004
【図４】
0005698109.tif 000005
【図５】
0005698109.tif 000006
【図６】
0005698109.tif 000007
【図７】
0005698109.tif 000008
【図８】
0005698109.tif 000009
【図９】
0005698109.tif 000010
【図１０】
0005698109.tif 000011
【図１１】
0005698109.tif 000012