コミットメントシステム、コミットメント生成装置、コミットメント検証装置、それらの方法及びプログラム
【課題】群構造維持の性質を有し、計算コストが小さいコミットメント方式を提供する。
【解決手段】コミットメント生成装置が、任意の元ta,tb,t(i)を選択し、ca=g(0)ta・Πi=1k g(i)t(i),cb=h(0)tb・Πi=1k h(i)t(i)∈G1,c(i)=m(i)・g2t(i)∈G2を含むコミットメントCを出力する。コミットメント生成装置は、da=g2ta∈G2,db=g2tb∈G2を含むデコミット鍵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))の両方が満たされるかを検証する。
【解決手段】コミットメント生成装置が、任意の元ta,tb,t(i)を選択し、ca=g(0)ta・Πi=1k g(i)t(i),cb=h(0)tb・Πi=1k h(i)t(i)∈G1,c(i)=m(i)・g2t(i)∈G2を含むコミットメントCを出力する。コミットメント生成装置は、da=g2ta∈G2,db=g2tb∈G2を含むデコミット鍵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))の両方が満たされるかを検証する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、暗号技術に関し、特にコミットメント方式に関する。
【背景技術】
【0002】
コミットメント方式は、電子現金システムの要素技術であるブラインド署名などの暗号プロトコルを構成する為に用いられる暗号要素技術である。特に、Groth-Sahaiによる効率的なゼロ知識証明と組み合わせて用いるためには、メッセージ、コミットメント、コミットメント鍵、デコミットメント鍵の要素のすべてが双線形写像を持つ群上の要素であることが望ましい。このような性質を群構造維持と呼ぶ。
【0003】
双線形写像を持つ群上で構成されたコミットメント方式について、以下に3つの従来法を説明する。
<従来方式1(非特許文献1の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~)
【0004】
<従来方式2(非特許文献1のB.4節,非特許文献2参照)>
[コミットメント鍵の生成: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)
【0005】
<従来方式3(非特許文献1の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)
【先行技術文献】
【非特許文献】
【0006】
【非特許文献1】M. Abe, K. Haralambiev,M. Ohkubo, “Signing on Elements in Bilinear Groups for Modular Protocol Design,” IACR e-print archive 2010/133
【非特許文献2】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
【発明の概要】
【発明が解決しようとする課題】
【0007】
しかしながら、従来方式は群構造維持の性質を有しない。
まず従来方式1は、メッセージmが群の要素ではなく、Zpの要素であるため、群構造維持の性質を有しない。次に従来方式1では、コミットメント検証がメッセージmごとに行われるため、検証式の数がメッセージmの数に比例して増大する。効率的なゼロ知識証明では、証明すべき関係式の数が効率に大きく影響するため従来方式1をゼロ知識証明と組み合わせる場合の計算コストが大きい。
【0008】
従来方式2では、メッセージm1,...,mkが双線形写像を持つ群G2の要素であり、メッセージの個数(kの値)に拘わらず検証式の数が一定である。しかしコミットメントが群GTの要素であり、群GTは双線形写像を持たない。よって、従来方式2は群構造維持の性質を有しない。
【0009】
従来方式3では、メッセージ、コミットメント、コミットメント鍵、デコミットメント鍵の要素のすべてが双線形写像を持つ群上の要素であり、群構造維持の性質を有する。また、メッセージの個数(kの値)に拘わらず検証式の数が一定である。しかしながら、従来方式3では、コミットメントの群要素の個数がメッセージの群要素の個数の2倍以上(2・k+2個)となり、計算コストが大きい。
本発明はこのような点に鑑みてなされたものであり、群構造維持の性質を有し、計算コストが小さいコミットメント方式を提供することを目的とする。
【課題を解決するための手段】
【0010】
第1の本発明では、G1,G2,GTが群であり、g2が群G2の生成元であり、eが群G1と群G2の直積群G1×G2の元に対して群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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→を不受理とする。
【0011】
第2の本発明では、G1,G2,GTが群であり、G1≠G2であり、g2が群G2の生成元であり、eが群G1と群G2の直積群G1×G2の元に対して群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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→を不受理とする。
【発明の効果】
【0012】
本発明は、群構造維持の性質を有する。また、kの値にかかわらず検証式の数が一定であり、計算コストが小さい。
【図面の簡単な説明】
【0013】
【図1】図1は、第1,2実施形態のコミットメントシステムの構成を説明するためのブロック図である。
【図2】図2Aは、第1実施形態の管理装置の機能構成を説明するためのブロック図であり、図2Bは、第1実施形態のコミットメント検証装置の機能構成を説明するためのブロック図である。
【図3】図3は、第1実施形態のコミットメント生成装置の機能構成を説明するためのブロック図である。
【図4】図4は、第1実施形態のコミットメント鍵生成方法を説明するためのブロック図である。
【図5】図5は、第1実施形態のコミットメント生成方法を説明するためのブロック図である。
【図6】図6は、第1実施形態のコミットメント検証方法を説明するためのブロック図である。
【図7】図7Aは、第2実施形態の管理装置の機能構成を説明するためのブロック図であり、図7Bは、第2実施形態のコミットメント検証装置の機能構成を説明するためのブロック図である。
【図8】図8は、第2実施形態のコミットメント生成装置の機能構成を説明するためのブロック図である。
【図9】図9は、第2実施形態のコミットメント鍵生成方法を説明するためのブロック図である。
【図10】図10は、第2実施形態のコミットメント生成方法を説明するためのブロック図である。
【図11】図11は、第2実施形態のコミットメント検証方法を説明するためのブロック図である。
【発明を実施するための形態】
【0014】
図面を参照して本発明の実施形態を説明する。
〔第1実施形態〕
第1実施形態を説明する。
本形態では、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)とする。
<構成>
図1に例示するように、本形態のコミットメントシステム1は、管理装置110、コミットメント生成装置120、及びコミットメント検証装置130を有し、ネットワークを通じて通信可能に構成されている。
【0015】
図2Aに例示するように、本形態の管理装置110は、出力部111、一時メモリ112a、記憶部112b、制御部113、選択部114a,114b、及びコミットメント鍵生成部114cを有する。本形態の管理装置110は、例えば、CPU(central processing unit)、RAM(random-access memory)等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて実行されることで構築される特別な装置である。本形態の管理装置110は、制御部113の制御のもとで各処理を実行する。各処理で得られたデータは、一時メモリ112a又は記憶部112bに格納され、必要に応じて読み出されて他の処理に利用される。
【0016】
図2Bに例示するように、本形態のコミットメント検証装置130は、入力部131(「コミットメント入力部」「オープニング情報入力部」に相当)、一時メモリ132a、記憶部132b、制御部133、及び検証部134を有する。本形態のコミットメント検証装置130は、公知又は専用のコンピュータに特別なプログラムが読み込まれて実行されることで構築される特別な装置である。本形態のコミットメント検証装置130は、制御部133の制御のもとで各処理を実行する。各処理で得られたデータは、一時メモリ132a又は記憶部132bに格納され、必要に応じて読み出されて他の処理に利用される。
【0017】
図3に例示するように、本形態のコミットメント生成装置120は、入力部121a、出力部121b(「コミットメント出力部」及び「デコミット鍵出力部」に相当)、一時メモリ122a、記憶部122b、制御部123、選択部124a、コミットメント計算部124b〜124d、コミットメント生成部124e、デコミット鍵計算部124f,124g、及びデコミット鍵生成部124hを有する。本形態のコミットメント生成装置120は、公知又は専用のコンピュータに特別なプログラムが読み込まれて実行されることで構築される特別な装置である。本形態のコミットメント生成装置120は、制御部123の制御のもとで各処理を実行する。各処理で得られたデータは、一時メモリ122a又は記憶部122bに格納され、必要に応じて読み出されて他の処理に利用される。
【0018】
<コミットメント鍵生成処理>
図4に例示するように、システムパラメータΛ=(p,G1,G2,GT,e,g1,g2)が入力された管理装置110(図2A)の選択部114aが、任意の元g(0),h(0)∈G1をランダムに選択し(ステップS101)、選択部114bが任意の元g(i),h(i)∈G1 (i=1,...,k)をランダムに選択する(ステップS102)。任意の元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)はコミットメント鍵生成部114cに入力される。コミットメント鍵生成部114cは、システムパラメータΛと任意の元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))を生成する(ステップS103)。コミットメント鍵ckは記憶部112bに格納される。記憶部112bに格納されたコミットメント鍵ckは、例えば、他の装置からの要求等に応じて読み出され、出力部111から出力される(ステップS104)。
【0019】
<コミットメント生成処理>
管理装置110から出力されたコミットメント鍵ckは、ネットワーク経由でコミットメント生成装置120(図3)に送られる。図5に例示するように、コミットメント鍵ckは、入力部121aに入力されて記憶部122bに格納される(ステップS111)。入力部121aには、メッセージm→=(m(1),...,m(k))∈G2kが入力され、それが記憶部122bに格納される(ステップS112)。ただし、kは1以上の予め定められた整数であり、m(i)∈G2 (i=1,...,k)を満たす。
【0020】
選択部124aは、任意の元ta, tb, t(i)∈Zp (i=1,...,k)をランダムに選択して出力する(ステップS113)。コミットメント計算部124bには、記憶部122bから読み出されたコミットメント鍵ckの要素、及び選択部124aから出力された任意の元ta, t(i)が入力される。コミットメント計算部124bは、これらを用いてca=g(0)ta・Πi=1k g(i)t(i)∈G1を計算して出力する(ステップS114)。コミットメント計算部124cには、記憶部122bから読み出されたコミットメント鍵ckの要素、及び選択部124aから出力された任意の元tb, t(i)が入力される。コミットメント計算部124cは、これらを用いてcb=h(0)tb・Πi=1k h(i)t(i)∈G1を計算して出力する(ステップS115)。コミットメント計算部124dには、記憶部122bから読み出されたコミットメント鍵ckの要素、メッセージm→、及び選択部124aから出力された任意の元t(i)が入力される。コミットメント計算部124dは、これらを用いてc(i)=m(i)・g2t(i)∈G2(i=1,...,k)を計算して出力する(ステップS116)。コミットメント計算部124b,124c,124dから出力されたca,cb,c(1),...,c(k)は、コミットメント生成部124eに入力される。コミットメント生成部124eは、ca, cb, c(1),...,c(k)を含むコミットメントC=(ca, cb, c(1),...,c(k))を生成する。コミットメントCは記憶部122bに格納される。
【0021】
デコミット鍵計算部124fには、記憶部122bから読み出された生成元g2、及び選択部124aから出力された任意の元taが入力される。デコミット鍵計算部124fは、これらを用いてda=g2ta∈G2を計算して出力する(ステップS118)。デコミット鍵計算部124gには、記憶部122bから読み出された生成元g2、及び選択部124aから出力された任意の元tbが入力される。デコミット鍵計算部124gは、これらを用いてdb=g2tb∈G2を計算して出力する(ステップS119)。デコミット鍵生成部124hには、デコミット鍵計算部124f,124gから出力されたda及びdbが入力される。デコミット鍵生成部124hは、da及びdbを含むデコミット鍵D=(da, db)を生成して出力する(ステップS120)。デコミット鍵Dは、記憶部122bに格納される。
【0022】
記憶部122bに格納されたコミットメントCは、任意の契機で出力され、ネットワーク経由でコミットメント検証装置130に送信される(ステップS121)。コミットメントCは、コミットメント検証装置130(図2B)の入力部131に入力され、記憶部132bに格納される。
【0023】
<コミットメント検証処理>
図6に例示するように、管理装置110から出力されたコミットメント鍵ckは、ネットワーク経由でコミットメント検証装置130(図2B)にも送られ、入力部131に入力されて記憶部132bに格納される(ステップS121)。オープニング時には、コミットメント生成装置120(図3)の記憶部122bに格納されていたメッセージm→及びデコミット鍵Dが読み出され、出力部121bから出力される。メッセージm→及びデコミット鍵Dは、ネットワーク経由でコミットメント検証装置130(図2B)に送信され、入力部131に入力されて記憶部132bに格納される(ステップS122)。
【0024】
検証部134は、記憶部132bから読み出したコミットメント鍵ck、コミットメントC、メッセージm→、及びデコミット鍵Dが以下の関係を満たすかを判定する(ステップS123)。
e(ca, g2)=e(g(0), da)・Πi=1k e(g(i), c(i)/m(i)) …(1)
検証式(1)の関係を満たさない場合、検証部134はメッセージm→を不受理として0を出力する(ステップS125)。
【0025】
式(1)の関係を満たす場合、次に検証部134は記憶部132bから読み出したコミットメント鍵ck、コミットメントC、メッセージm→、及びデコミット鍵Dが以下の関係を満たすかを判定する(ステップS124)。
e(cb, g2)=e(h(0), db)・Πi=1k e(h(i), c(i)/m(i)) …(2)
検証式(2)の関係を満たさない場合、検証部134はメッセージm→を不受理として0を出力する(ステップS125)。一方、検証式(2)の関係を満たす場合、検証部134はメッセージm→がコミットメントCでコミットされていたメッセージであるとして受理し、1を出力する(ステップS126)。
【0026】
<本形態の特徴>
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より、オープニング時にコミットメント検証装置130に入力されたメッセージ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)の関係は満たされない。
【0027】
本形態のメッセージm→、コミットメントC、コミットメント鍵ck、デコミットメント鍵Dの要素のすべてが双線形写像eを持つ群上の要素であり、本形態のコミットメント方式は群構造維持の性質を有する。よって、群構造を維持したままですべての演算ができ、暗号プロトコルへの拡張が容易である。
【0028】
本形態のコミットメント方式では、メッセージm(k)の個数(kの値)にかかわらず、2個の検証式(1)(2)のみで検証処理が実行できる。さらに、メッセージの群要素の個数kに対するコミットメントCの群要素の個数がk+2であり、従来方式3の群要素の個数2・k+2よりも小さい。よって、従来方式1,3よりも計算コスト・通信コスト・記憶メモリコストが低い。
〔第2実施形態〕
第2実施形態を説明する。以下では第1実施形態との相違点を中心に説明する。
本形態では、G1,G2,GTが群(例えば巡回群)であり、g1が群G1の生成元であり、g2が群G2の生成元である。本形態の場合、G1≠G2である。本形態の位数pは素数であり、群G1,G2の位数もpである。本形態のシステムパラメータをΛsxdh=(p,G1,G2,GT,e,g1,g2)とする。
<構成>
図1に例示するように、本形態のコミットメントシステム2は、管理装置210、コミットメント生成装置220、及びコミットメント検証装置230を有し、ネットワークを通じて通信可能に構成されている。
【0029】
図7Aに例示するように、本形態の管理装置210は、出力部111、一時メモリ112a、記憶部212b、制御部113、選択部214a,214b、及びコミットメント鍵生成部214cを有する。本形態の管理装置210は、例えば、公知又は専用のコンピュータに特別なプログラムが読み込まれて実行されることで構築される特別な装置である。本形態の管理装置210は、制御部113の制御のもとで各処理を実行する。各処理で得られたデータは、一時メモリ112a又は記憶部212bに格納され、必要に応じて読み出されて他の処理に利用される。
【0030】
図7Bに例示するように、本形態のコミットメント検証装置230は、入力部231(「コミットメント入力部」「オープニング情報入力部」に相当)、一時メモリ132a、記憶部232b、制御部133、及び検証部234を有する。本形態のコミットメント検証装置230は、公知又は専用のコンピュータに特別なプログラムが読み込まれて実行されることで構築される特別な装置である。本形態のコミットメント検証装置230は、制御部133の制御のもとで各処理を実行する。各処理で得られたデータは、一時メモリ132a又は記憶部232bに格納され、必要に応じて読み出されて他の処理に利用される。
【0031】
図8に例示するように、本形態のコミットメント生成装置220は、入力部221a、出力部221b(「コミットメント出力部」及び「デコミット鍵出力部」に相当)、一時メモリ122a、記憶部222b、制御部123、選択部224a、コミットメント計算部124b,124d、コミットメント生成部224e、デコミット鍵計算部124f、及びデコミット鍵生成部224hを有する。本形態のコミットメント生成装置220は、公知又は専用のコンピュータに特別なプログラムが読み込まれて実行されることで構築される特別な装置である。本形態のコミットメント生成装置220は、制御部123の制御のもとで各処理を実行する。各処理で得られたデータは、一時メモリ122a又は記憶部222bに格納され、必要に応じて読み出されて他の処理に利用される。
【0032】
<コミットメント鍵生成処理>
図9に例示するように、システムパラメータΛsxdh=(p,G1,G2,GT,e,g1,g2)が入力された管理装置210(図7A)の選択部214aが、任意の元g(0)∈G1をランダムに選択し(ステップS201)、選択部214bが任意の元g(i)∈G1 (i=1,...,k)をランダムに選択する(ステップS202)。任意の元g(0)と任意の元g(i)とは互いに独立に選択されものでもよいし、ランダムに選択された任意の元ξ(i)∈Zpに対してg(i)=g(0)ξ(i) (i=1,...,k)を満たすものであってもよい。システムパラメータΛsxdhと当該任意の元g(0),g(i) (i=1,...,k)はコミットメント鍵生成部214cに入力される。コミットメント鍵生成部214cは、システムパラメータΛsxdhと任意の元g(0), g(1),...,g(k)∈G1とを含むコミットメント鍵ck=(Λsxdh, g(0), g(1),...,g(k))を生成する(ステップS203)。コミットメント鍵ckは記憶部212bに格納される。記憶部212bに格納されたコミットメント鍵ckは、例えば、他の装置からの要求等に応じて読み出され、出力部211から出力される(ステップS204)。
【0033】
<コミットメント生成処理>
管理装置210から出力されたコミットメント鍵ckは、ネットワーク経由でコミットメント生成装置220(図8)に送られる。図10に例示するように、コミットメント鍵ckは、入力部221aに入力されて記憶部222bに格納される(ステップS211)。入力部221aには、メッセージm→=(m(1),...,m(k))∈G2kが入力され、それが記憶部222bに格納される(ステップS212)。
【0034】
選択部224aは、任意の元ta, t(i)∈Zp (i=1,...,k)をランダムに選択して出力する(ステップS213)。コミットメント計算部124bには、記憶部222bから読み出されたコミットメント鍵ckの要素、及び選択部224aから出力された任意の元ta, t(i)が入力される。コミットメント計算部124bは、これらを用いてca=g(0)ta・Πi=1k g(i)t(i)∈G1を計算して出力する(ステップS114)。コミットメント計算部124dには、記憶部222bから読み出されたコミットメント鍵ckの要素、メッセージm→、及び選択部224aから出力された任意の元t(i)が入力される。コミットメント計算部124dは、これらを用いてc(i)=m(i)・g2t(i)∈G2(i=1,...,k)を計算して出力する(ステップS116)。コミットメント計算部124b,124dから出力されたca,c(1),...,c(k)は、コミットメント生成部224eに入力される。コミットメント生成部224eは、ca, c(1),...,c(k)を含むコミットメントC=(ca, c(1),...,c(k))を生成する。コミットメントCは記憶部222bに格納される。
【0035】
デコミット鍵計算部124fには、記憶部222bから読み出された生成元g2、及び選択部224aから出力された任意の元taが入力される。デコミット鍵計算部124fは、これらを用いてda=g2ta∈G2を計算して出力する(ステップS118)。デコミット鍵生成部224hには、デコミット鍵計算部124fから出力されたdaが入力される。デコミット鍵生成部224hは、daを含むデコミット鍵D=(da)を生成して出力する(ステップS220)。デコミット鍵Dは、記憶部222bに格納される。
【0036】
記憶部222bに格納されたコミットメントCは、任意の契機で出力され、ネットワーク経由でコミットメント検証装置230に送信される(ステップS221)。コミットメントCは、コミットメント検証装置230(図7B)の入力部231に入力され、記憶部232bに格納される。
【0037】
<コミットメント検証処理>
図11に例示するように、管理装置210から出力されたコミットメント鍵ckは、ネットワーク経由でコミットメント検証装置230(図7B)にも送られ、入力部231に入力されて記憶部232bに格納される(ステップS221)。オープニング時には、コミットメント生成装置220(図8)の記憶部222bに格納されていたメッセージm→及びデコミット鍵Dが読み出され、出力部221bから出力される。メッセージm→及びデコミット鍵Dは、ネットワーク経由でコミットメント検証装置230(図7B)に送信され、入力部231に入力されて記憶部232bに格納される(ステップS222)。
【0038】
検証部234は、記憶部232bから読み出したコミットメント鍵ck、コミットメントC、メッセージm→、及びデコミット鍵Dが前述の検証式(1)の関係を満たすかを判定する(ステップS123)。
検証式(1)の関係を満たさない場合、検証部234はメッセージm→を不受理として0を出力する(ステップS225)。式(1)の関係を満たす場合、検証部234はメッセージm→がコミットメントCでコミットされていたメッセージであるとして受理し、1を出力する(ステップS226)。
【0039】
<本形態の特徴>
本形態のメッセージm→、コミットメントC、コミットメント鍵ck、デコミットメント鍵Dの要素のすべてが双線形写像eを持つ群上の要素であり、本形態のコミットメント方式は群構造維持の性質を有する。よって、群構造を維持したままですべての演算ができ、暗号プロトコルへの拡張が容易である。
【0040】
本形態のコミットメント方式では、メッセージm(k)の個数(kの値)にかかわらず、1個の検証式(1)のみで検証処理が実行できる。さらに、メッセージの群要素の個数kに対するコミットメントCの群要素の個数がk+1であり、従来方式3の群要素の個数2・k+2よりも小さい。よって、従来方式1,3よりも計算コスト・通信コスト・記憶メモリコストが低い。
【0041】
〔その他の変形例等〕
本発明は上述の各実施形態に限定されるものではない。例えば、上述の各実施形態では、本形態の位数pが素数であり、群G1,G2の位数もpであることとした。しかし、プロトコルに要求される安全性の程度によっては、位数pが素数以外であってもよく、群G1,G2の位数がp以外であってもよい。群GTの位数もpであってもよいし、pでなくてもよい。また、上記の実施形態では各装置がネットワーク経由で通信を行うこととしたが、各装置がICカード等の可搬型記録媒体を介して情報のやり取りを行ってもよい。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【0042】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な(non-transitory)記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD−ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP(Application Service Provider)型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの(コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等)を含むものとする。また、上記の実施形態では、コンピュータ上で所定のプログラムを実行させることにより、各装置を構成することとしたが、これらの処理内容の少なくとも一部が集積回路等のハードウェアによって実現されてもよい。
【符号の説明】
【0043】
1,2 コミットメントシステム
110,210 管理装置
120,220 コミットメント生成装置
130,230 コミットメント検証相当
【技術分野】
【0001】
本発明は、暗号技術に関し、特にコミットメント方式に関する。
【背景技術】
【0002】
コミットメント方式は、電子現金システムの要素技術であるブラインド署名などの暗号プロトコルを構成する為に用いられる暗号要素技術である。特に、Groth-Sahaiによる効率的なゼロ知識証明と組み合わせて用いるためには、メッセージ、コミットメント、コミットメント鍵、デコミットメント鍵の要素のすべてが双線形写像を持つ群上の要素であることが望ましい。このような性質を群構造維持と呼ぶ。
【0003】
双線形写像を持つ群上で構成されたコミットメント方式について、以下に3つの従来法を説明する。
<従来方式1(非特許文献1の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~)
【0004】
<従来方式2(非特許文献1のB.4節,非特許文献2参照)>
[コミットメント鍵の生成: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)
【0005】
<従来方式3(非特許文献1の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)
【先行技術文献】
【非特許文献】
【0006】
【非特許文献1】M. Abe, K. Haralambiev,M. Ohkubo, “Signing on Elements in Bilinear Groups for Modular Protocol Design,” IACR e-print archive 2010/133
【非特許文献2】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
【発明の概要】
【発明が解決しようとする課題】
【0007】
しかしながら、従来方式は群構造維持の性質を有しない。
まず従来方式1は、メッセージmが群の要素ではなく、Zpの要素であるため、群構造維持の性質を有しない。次に従来方式1では、コミットメント検証がメッセージmごとに行われるため、検証式の数がメッセージmの数に比例して増大する。効率的なゼロ知識証明では、証明すべき関係式の数が効率に大きく影響するため従来方式1をゼロ知識証明と組み合わせる場合の計算コストが大きい。
【0008】
従来方式2では、メッセージm1,...,mkが双線形写像を持つ群G2の要素であり、メッセージの個数(kの値)に拘わらず検証式の数が一定である。しかしコミットメントが群GTの要素であり、群GTは双線形写像を持たない。よって、従来方式2は群構造維持の性質を有しない。
【0009】
従来方式3では、メッセージ、コミットメント、コミットメント鍵、デコミットメント鍵の要素のすべてが双線形写像を持つ群上の要素であり、群構造維持の性質を有する。また、メッセージの個数(kの値)に拘わらず検証式の数が一定である。しかしながら、従来方式3では、コミットメントの群要素の個数がメッセージの群要素の個数の2倍以上(2・k+2個)となり、計算コストが大きい。
本発明はこのような点に鑑みてなされたものであり、群構造維持の性質を有し、計算コストが小さいコミットメント方式を提供することを目的とする。
【課題を解決するための手段】
【0010】
第1の本発明では、G1,G2,GTが群であり、g2が群G2の生成元であり、eが群G1と群G2の直積群G1×G2の元に対して群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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→を不受理とする。
【0011】
第2の本発明では、G1,G2,GTが群であり、G1≠G2であり、g2が群G2の生成元であり、eが群G1と群G2の直積群G1×G2の元に対して群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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→を不受理とする。
【発明の効果】
【0012】
本発明は、群構造維持の性質を有する。また、kの値にかかわらず検証式の数が一定であり、計算コストが小さい。
【図面の簡単な説明】
【0013】
【図1】図1は、第1,2実施形態のコミットメントシステムの構成を説明するためのブロック図である。
【図2】図2Aは、第1実施形態の管理装置の機能構成を説明するためのブロック図であり、図2Bは、第1実施形態のコミットメント検証装置の機能構成を説明するためのブロック図である。
【図3】図3は、第1実施形態のコミットメント生成装置の機能構成を説明するためのブロック図である。
【図4】図4は、第1実施形態のコミットメント鍵生成方法を説明するためのブロック図である。
【図5】図5は、第1実施形態のコミットメント生成方法を説明するためのブロック図である。
【図6】図6は、第1実施形態のコミットメント検証方法を説明するためのブロック図である。
【図7】図7Aは、第2実施形態の管理装置の機能構成を説明するためのブロック図であり、図7Bは、第2実施形態のコミットメント検証装置の機能構成を説明するためのブロック図である。
【図8】図8は、第2実施形態のコミットメント生成装置の機能構成を説明するためのブロック図である。
【図9】図9は、第2実施形態のコミットメント鍵生成方法を説明するためのブロック図である。
【図10】図10は、第2実施形態のコミットメント生成方法を説明するためのブロック図である。
【図11】図11は、第2実施形態のコミットメント検証方法を説明するためのブロック図である。
【発明を実施するための形態】
【0014】
図面を参照して本発明の実施形態を説明する。
〔第1実施形態〕
第1実施形態を説明する。
本形態では、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)とする。
<構成>
図1に例示するように、本形態のコミットメントシステム1は、管理装置110、コミットメント生成装置120、及びコミットメント検証装置130を有し、ネットワークを通じて通信可能に構成されている。
【0015】
図2Aに例示するように、本形態の管理装置110は、出力部111、一時メモリ112a、記憶部112b、制御部113、選択部114a,114b、及びコミットメント鍵生成部114cを有する。本形態の管理装置110は、例えば、CPU(central processing unit)、RAM(random-access memory)等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて実行されることで構築される特別な装置である。本形態の管理装置110は、制御部113の制御のもとで各処理を実行する。各処理で得られたデータは、一時メモリ112a又は記憶部112bに格納され、必要に応じて読み出されて他の処理に利用される。
【0016】
図2Bに例示するように、本形態のコミットメント検証装置130は、入力部131(「コミットメント入力部」「オープニング情報入力部」に相当)、一時メモリ132a、記憶部132b、制御部133、及び検証部134を有する。本形態のコミットメント検証装置130は、公知又は専用のコンピュータに特別なプログラムが読み込まれて実行されることで構築される特別な装置である。本形態のコミットメント検証装置130は、制御部133の制御のもとで各処理を実行する。各処理で得られたデータは、一時メモリ132a又は記憶部132bに格納され、必要に応じて読み出されて他の処理に利用される。
【0017】
図3に例示するように、本形態のコミットメント生成装置120は、入力部121a、出力部121b(「コミットメント出力部」及び「デコミット鍵出力部」に相当)、一時メモリ122a、記憶部122b、制御部123、選択部124a、コミットメント計算部124b〜124d、コミットメント生成部124e、デコミット鍵計算部124f,124g、及びデコミット鍵生成部124hを有する。本形態のコミットメント生成装置120は、公知又は専用のコンピュータに特別なプログラムが読み込まれて実行されることで構築される特別な装置である。本形態のコミットメント生成装置120は、制御部123の制御のもとで各処理を実行する。各処理で得られたデータは、一時メモリ122a又は記憶部122bに格納され、必要に応じて読み出されて他の処理に利用される。
【0018】
<コミットメント鍵生成処理>
図4に例示するように、システムパラメータΛ=(p,G1,G2,GT,e,g1,g2)が入力された管理装置110(図2A)の選択部114aが、任意の元g(0),h(0)∈G1をランダムに選択し(ステップS101)、選択部114bが任意の元g(i),h(i)∈G1 (i=1,...,k)をランダムに選択する(ステップS102)。任意の元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)はコミットメント鍵生成部114cに入力される。コミットメント鍵生成部114cは、システムパラメータΛと任意の元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))を生成する(ステップS103)。コミットメント鍵ckは記憶部112bに格納される。記憶部112bに格納されたコミットメント鍵ckは、例えば、他の装置からの要求等に応じて読み出され、出力部111から出力される(ステップS104)。
【0019】
<コミットメント生成処理>
管理装置110から出力されたコミットメント鍵ckは、ネットワーク経由でコミットメント生成装置120(図3)に送られる。図5に例示するように、コミットメント鍵ckは、入力部121aに入力されて記憶部122bに格納される(ステップS111)。入力部121aには、メッセージm→=(m(1),...,m(k))∈G2kが入力され、それが記憶部122bに格納される(ステップS112)。ただし、kは1以上の予め定められた整数であり、m(i)∈G2 (i=1,...,k)を満たす。
【0020】
選択部124aは、任意の元ta, tb, t(i)∈Zp (i=1,...,k)をランダムに選択して出力する(ステップS113)。コミットメント計算部124bには、記憶部122bから読み出されたコミットメント鍵ckの要素、及び選択部124aから出力された任意の元ta, t(i)が入力される。コミットメント計算部124bは、これらを用いてca=g(0)ta・Πi=1k g(i)t(i)∈G1を計算して出力する(ステップS114)。コミットメント計算部124cには、記憶部122bから読み出されたコミットメント鍵ckの要素、及び選択部124aから出力された任意の元tb, t(i)が入力される。コミットメント計算部124cは、これらを用いてcb=h(0)tb・Πi=1k h(i)t(i)∈G1を計算して出力する(ステップS115)。コミットメント計算部124dには、記憶部122bから読み出されたコミットメント鍵ckの要素、メッセージm→、及び選択部124aから出力された任意の元t(i)が入力される。コミットメント計算部124dは、これらを用いてc(i)=m(i)・g2t(i)∈G2(i=1,...,k)を計算して出力する(ステップS116)。コミットメント計算部124b,124c,124dから出力されたca,cb,c(1),...,c(k)は、コミットメント生成部124eに入力される。コミットメント生成部124eは、ca, cb, c(1),...,c(k)を含むコミットメントC=(ca, cb, c(1),...,c(k))を生成する。コミットメントCは記憶部122bに格納される。
【0021】
デコミット鍵計算部124fには、記憶部122bから読み出された生成元g2、及び選択部124aから出力された任意の元taが入力される。デコミット鍵計算部124fは、これらを用いてda=g2ta∈G2を計算して出力する(ステップS118)。デコミット鍵計算部124gには、記憶部122bから読み出された生成元g2、及び選択部124aから出力された任意の元tbが入力される。デコミット鍵計算部124gは、これらを用いてdb=g2tb∈G2を計算して出力する(ステップS119)。デコミット鍵生成部124hには、デコミット鍵計算部124f,124gから出力されたda及びdbが入力される。デコミット鍵生成部124hは、da及びdbを含むデコミット鍵D=(da, db)を生成して出力する(ステップS120)。デコミット鍵Dは、記憶部122bに格納される。
【0022】
記憶部122bに格納されたコミットメントCは、任意の契機で出力され、ネットワーク経由でコミットメント検証装置130に送信される(ステップS121)。コミットメントCは、コミットメント検証装置130(図2B)の入力部131に入力され、記憶部132bに格納される。
【0023】
<コミットメント検証処理>
図6に例示するように、管理装置110から出力されたコミットメント鍵ckは、ネットワーク経由でコミットメント検証装置130(図2B)にも送られ、入力部131に入力されて記憶部132bに格納される(ステップS121)。オープニング時には、コミットメント生成装置120(図3)の記憶部122bに格納されていたメッセージm→及びデコミット鍵Dが読み出され、出力部121bから出力される。メッセージm→及びデコミット鍵Dは、ネットワーク経由でコミットメント検証装置130(図2B)に送信され、入力部131に入力されて記憶部132bに格納される(ステップS122)。
【0024】
検証部134は、記憶部132bから読み出したコミットメント鍵ck、コミットメントC、メッセージm→、及びデコミット鍵Dが以下の関係を満たすかを判定する(ステップS123)。
e(ca, g2)=e(g(0), da)・Πi=1k e(g(i), c(i)/m(i)) …(1)
検証式(1)の関係を満たさない場合、検証部134はメッセージm→を不受理として0を出力する(ステップS125)。
【0025】
式(1)の関係を満たす場合、次に検証部134は記憶部132bから読み出したコミットメント鍵ck、コミットメントC、メッセージm→、及びデコミット鍵Dが以下の関係を満たすかを判定する(ステップS124)。
e(cb, g2)=e(h(0), db)・Πi=1k e(h(i), c(i)/m(i)) …(2)
検証式(2)の関係を満たさない場合、検証部134はメッセージm→を不受理として0を出力する(ステップS125)。一方、検証式(2)の関係を満たす場合、検証部134はメッセージm→がコミットメントCでコミットされていたメッセージであるとして受理し、1を出力する(ステップS126)。
【0026】
<本形態の特徴>
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より、オープニング時にコミットメント検証装置130に入力されたメッセージ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)の関係は満たされない。
【0027】
本形態のメッセージm→、コミットメントC、コミットメント鍵ck、デコミットメント鍵Dの要素のすべてが双線形写像eを持つ群上の要素であり、本形態のコミットメント方式は群構造維持の性質を有する。よって、群構造を維持したままですべての演算ができ、暗号プロトコルへの拡張が容易である。
【0028】
本形態のコミットメント方式では、メッセージm(k)の個数(kの値)にかかわらず、2個の検証式(1)(2)のみで検証処理が実行できる。さらに、メッセージの群要素の個数kに対するコミットメントCの群要素の個数がk+2であり、従来方式3の群要素の個数2・k+2よりも小さい。よって、従来方式1,3よりも計算コスト・通信コスト・記憶メモリコストが低い。
〔第2実施形態〕
第2実施形態を説明する。以下では第1実施形態との相違点を中心に説明する。
本形態では、G1,G2,GTが群(例えば巡回群)であり、g1が群G1の生成元であり、g2が群G2の生成元である。本形態の場合、G1≠G2である。本形態の位数pは素数であり、群G1,G2の位数もpである。本形態のシステムパラメータをΛsxdh=(p,G1,G2,GT,e,g1,g2)とする。
<構成>
図1に例示するように、本形態のコミットメントシステム2は、管理装置210、コミットメント生成装置220、及びコミットメント検証装置230を有し、ネットワークを通じて通信可能に構成されている。
【0029】
図7Aに例示するように、本形態の管理装置210は、出力部111、一時メモリ112a、記憶部212b、制御部113、選択部214a,214b、及びコミットメント鍵生成部214cを有する。本形態の管理装置210は、例えば、公知又は専用のコンピュータに特別なプログラムが読み込まれて実行されることで構築される特別な装置である。本形態の管理装置210は、制御部113の制御のもとで各処理を実行する。各処理で得られたデータは、一時メモリ112a又は記憶部212bに格納され、必要に応じて読み出されて他の処理に利用される。
【0030】
図7Bに例示するように、本形態のコミットメント検証装置230は、入力部231(「コミットメント入力部」「オープニング情報入力部」に相当)、一時メモリ132a、記憶部232b、制御部133、及び検証部234を有する。本形態のコミットメント検証装置230は、公知又は専用のコンピュータに特別なプログラムが読み込まれて実行されることで構築される特別な装置である。本形態のコミットメント検証装置230は、制御部133の制御のもとで各処理を実行する。各処理で得られたデータは、一時メモリ132a又は記憶部232bに格納され、必要に応じて読み出されて他の処理に利用される。
【0031】
図8に例示するように、本形態のコミットメント生成装置220は、入力部221a、出力部221b(「コミットメント出力部」及び「デコミット鍵出力部」に相当)、一時メモリ122a、記憶部222b、制御部123、選択部224a、コミットメント計算部124b,124d、コミットメント生成部224e、デコミット鍵計算部124f、及びデコミット鍵生成部224hを有する。本形態のコミットメント生成装置220は、公知又は専用のコンピュータに特別なプログラムが読み込まれて実行されることで構築される特別な装置である。本形態のコミットメント生成装置220は、制御部123の制御のもとで各処理を実行する。各処理で得られたデータは、一時メモリ122a又は記憶部222bに格納され、必要に応じて読み出されて他の処理に利用される。
【0032】
<コミットメント鍵生成処理>
図9に例示するように、システムパラメータΛsxdh=(p,G1,G2,GT,e,g1,g2)が入力された管理装置210(図7A)の選択部214aが、任意の元g(0)∈G1をランダムに選択し(ステップS201)、選択部214bが任意の元g(i)∈G1 (i=1,...,k)をランダムに選択する(ステップS202)。任意の元g(0)と任意の元g(i)とは互いに独立に選択されものでもよいし、ランダムに選択された任意の元ξ(i)∈Zpに対してg(i)=g(0)ξ(i) (i=1,...,k)を満たすものであってもよい。システムパラメータΛsxdhと当該任意の元g(0),g(i) (i=1,...,k)はコミットメント鍵生成部214cに入力される。コミットメント鍵生成部214cは、システムパラメータΛsxdhと任意の元g(0), g(1),...,g(k)∈G1とを含むコミットメント鍵ck=(Λsxdh, g(0), g(1),...,g(k))を生成する(ステップS203)。コミットメント鍵ckは記憶部212bに格納される。記憶部212bに格納されたコミットメント鍵ckは、例えば、他の装置からの要求等に応じて読み出され、出力部211から出力される(ステップS204)。
【0033】
<コミットメント生成処理>
管理装置210から出力されたコミットメント鍵ckは、ネットワーク経由でコミットメント生成装置220(図8)に送られる。図10に例示するように、コミットメント鍵ckは、入力部221aに入力されて記憶部222bに格納される(ステップS211)。入力部221aには、メッセージm→=(m(1),...,m(k))∈G2kが入力され、それが記憶部222bに格納される(ステップS212)。
【0034】
選択部224aは、任意の元ta, t(i)∈Zp (i=1,...,k)をランダムに選択して出力する(ステップS213)。コミットメント計算部124bには、記憶部222bから読み出されたコミットメント鍵ckの要素、及び選択部224aから出力された任意の元ta, t(i)が入力される。コミットメント計算部124bは、これらを用いてca=g(0)ta・Πi=1k g(i)t(i)∈G1を計算して出力する(ステップS114)。コミットメント計算部124dには、記憶部222bから読み出されたコミットメント鍵ckの要素、メッセージm→、及び選択部224aから出力された任意の元t(i)が入力される。コミットメント計算部124dは、これらを用いてc(i)=m(i)・g2t(i)∈G2(i=1,...,k)を計算して出力する(ステップS116)。コミットメント計算部124b,124dから出力されたca,c(1),...,c(k)は、コミットメント生成部224eに入力される。コミットメント生成部224eは、ca, c(1),...,c(k)を含むコミットメントC=(ca, c(1),...,c(k))を生成する。コミットメントCは記憶部222bに格納される。
【0035】
デコミット鍵計算部124fには、記憶部222bから読み出された生成元g2、及び選択部224aから出力された任意の元taが入力される。デコミット鍵計算部124fは、これらを用いてda=g2ta∈G2を計算して出力する(ステップS118)。デコミット鍵生成部224hには、デコミット鍵計算部124fから出力されたdaが入力される。デコミット鍵生成部224hは、daを含むデコミット鍵D=(da)を生成して出力する(ステップS220)。デコミット鍵Dは、記憶部222bに格納される。
【0036】
記憶部222bに格納されたコミットメントCは、任意の契機で出力され、ネットワーク経由でコミットメント検証装置230に送信される(ステップS221)。コミットメントCは、コミットメント検証装置230(図7B)の入力部231に入力され、記憶部232bに格納される。
【0037】
<コミットメント検証処理>
図11に例示するように、管理装置210から出力されたコミットメント鍵ckは、ネットワーク経由でコミットメント検証装置230(図7B)にも送られ、入力部231に入力されて記憶部232bに格納される(ステップS221)。オープニング時には、コミットメント生成装置220(図8)の記憶部222bに格納されていたメッセージm→及びデコミット鍵Dが読み出され、出力部221bから出力される。メッセージm→及びデコミット鍵Dは、ネットワーク経由でコミットメント検証装置230(図7B)に送信され、入力部231に入力されて記憶部232bに格納される(ステップS222)。
【0038】
検証部234は、記憶部232bから読み出したコミットメント鍵ck、コミットメントC、メッセージm→、及びデコミット鍵Dが前述の検証式(1)の関係を満たすかを判定する(ステップS123)。
検証式(1)の関係を満たさない場合、検証部234はメッセージm→を不受理として0を出力する(ステップS225)。式(1)の関係を満たす場合、検証部234はメッセージm→がコミットメントCでコミットされていたメッセージであるとして受理し、1を出力する(ステップS226)。
【0039】
<本形態の特徴>
本形態のメッセージm→、コミットメントC、コミットメント鍵ck、デコミットメント鍵Dの要素のすべてが双線形写像eを持つ群上の要素であり、本形態のコミットメント方式は群構造維持の性質を有する。よって、群構造を維持したままですべての演算ができ、暗号プロトコルへの拡張が容易である。
【0040】
本形態のコミットメント方式では、メッセージm(k)の個数(kの値)にかかわらず、1個の検証式(1)のみで検証処理が実行できる。さらに、メッセージの群要素の個数kに対するコミットメントCの群要素の個数がk+1であり、従来方式3の群要素の個数2・k+2よりも小さい。よって、従来方式1,3よりも計算コスト・通信コスト・記憶メモリコストが低い。
【0041】
〔その他の変形例等〕
本発明は上述の各実施形態に限定されるものではない。例えば、上述の各実施形態では、本形態の位数pが素数であり、群G1,G2の位数もpであることとした。しかし、プロトコルに要求される安全性の程度によっては、位数pが素数以外であってもよく、群G1,G2の位数がp以外であってもよい。群GTの位数もpであってもよいし、pでなくてもよい。また、上記の実施形態では各装置がネットワーク経由で通信を行うこととしたが、各装置がICカード等の可搬型記録媒体を介して情報のやり取りを行ってもよい。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【0042】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な(non-transitory)記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD−ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP(Application Service Provider)型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの(コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等)を含むものとする。また、上記の実施形態では、コンピュータ上で所定のプログラムを実行させることにより、各装置を構成することとしたが、これらの処理内容の少なくとも一部が集積回路等のハードウェアによって実現されてもよい。
【符号の説明】
【0043】
1,2 コミットメントシステム
110,210 管理装置
120,220 コミットメント生成装置
130,230 コミットメント検証相当
【特許請求の範囲】
【請求項1】
コミットメント生成装置とコミットメント検証装置とを有し、
G1,G2,GTが群であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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を計算する第1コミットメント計算部と、
cb=h(0)tb・Πi=1k h(i)t(i)∈G1を計算する第2コミットメント計算部と、
c(i)=m(i)・g2t(i)∈G2(i=1,...,k)を計算する第3コミットメント計算部と、
ca, cb, c(1),...,c(k)を含むコミットメントCを出力するコミットメント出力部と、
da=g2ta∈G2を計算する第1デコミット鍵計算部と、
db=g2tb∈G2を計算する第2デコミット鍵計算部と、
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→を不受理とする検証部と、を含む、
コミットメントシステム。
【請求項2】
コミットメント生成装置とコミットメント検証装置とを有し、
G1,G2,GTが群であり、G1≠G2であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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を計算する第1コミットメント計算部と、
c(i)=m(i)・g2t(i)∈G2(i=1,...,k)を計算する第3コミットメント計算部と、
ca, c(1),...,c(k)を含むコミットメントCを出力するコミットメント出力部と、
da=g2ta∈G2を計算する第1デコミット鍵計算部と、
daを含むデコミット鍵Dを出力するデコミット鍵出力部と、を含み、
前記コミットメント検証装置は、
前記コミットメントCの入力を受け付けるコミットメント入力部と、
前記メッセージm→、前記コミットメント鍵ck、及び前記デコミット鍵Dの入力を受け付けるオープニング情報入力部と、
関係e(ca, g2)=e(g(0), da)・Πi=1k e(g(i), c(i)/m(i))が満たされるかを検証し、前記関係が満たされる場合に前記メッセージm→を受理し、前記関係が満たされない場合に前記メッセージm→を不受理とする検証部と、を含む、
コミットメントシステム。
【請求項3】
G1,G2,GTが群であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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を計算する第1コミットメント計算部と、
cb=h(0)tb・Πi=1k h(i)t(i)∈G1を計算する第2コミットメント計算部と、
c(i)=m(i)・g2t(i)∈G2(i=1,...,k)を計算する第3コミットメント計算部と、
ca, cb, c(1),...,c(k)を含むコミットメントCを出力するコミットメント出力部と、
da=g2ta∈G2を計算する第1デコミット鍵計算部と、
db=g2tb∈G2を計算する第2デコミット鍵計算部と、
da, dbを含むデコミット鍵Dを出力するデコミット鍵出力部と、
を有するコミットメント生成装置。
【請求項4】
G1,G2,GTが群であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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→を不受理とする検証部と、
を有するコミットメント検証装置。
【請求項5】
G1,G2,GTが群であり、G1≠G2であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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を計算する第1コミットメント計算部と、
c(i)=m(i)・g2t(i)∈G2(i=1,...,k)を計算する第3コミットメント計算部と、
ca, c(1),...,c(k)を含むコミットメントCを出力するコミットメント出力部と、
da=g2ta∈G2を計算する第1デコミット鍵計算部と、
daを含むデコミット鍵Dを出力するデコミット鍵出力部と、
を有するコミットメント生成装置。
【請求項6】
G1,G2,GTが群であり、G1≠G2であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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→を不受理とする検証部と、
を有するコミットメント検証装置。
【請求項7】
G1,G2,GTが群であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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→を不受理とするステップと、を含む、
コミットメント方法。
【請求項8】
G1,G2,GTが群であり、G1≠G2であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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→を不受理とするステップと、
を有するコミットメント方法。
【請求項9】
G1,G2,GTが群であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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)を選択するステップと、
第1コミットメント計算部で、ca=g(0)ta・Πi=1k g(i)t(i)∈G1を計算するステップと、
第2コミットメント計算部で、cb=h(0)tb・Πi=1k h(i)t(i)∈G1を計算するステップと、
第3コミットメント計算部で、c(i)=m(i)・g2t(i)∈G2 (i=1,...,k)を計算するステップと、
コミットメント出力部で、ca, cb, c(1),...,c(k)を含むコミットメントCを出力するステップと、
第1デコミット鍵計算部で、da=g2ta∈G2を計算するステップと、
第2デコミット鍵計算部で、db=g2tb∈G2を計算するステップと、
デコミット鍵出力部で、da, dbを含むデコミット鍵Dを出力するステップと、
を有するコミットメント生成方法。
【請求項10】
G1,G2,GTが群であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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→を不受理とするステップと、
を有するコミットメント検証方法。
【請求項11】
G1,G2,GTが群であり、G1≠G2であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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)を選択するステップと、
第1コミットメント計算部で、ca=g(0)ta・Πi=1k g(i)t(i)∈G1を計算するステップと、
第3コミットメント計算部で、c(i)=m(i)・g2t(i)∈G2 (i=1,...,k)を計算するステップと、
コミットメント出力部で、ca, c(1),...,c(k)を含むコミットメントCを出力するステップと、
第1デコミット鍵計算部で、da=g2ta∈G2を計算するステップと、
デコミット鍵出力部で、daを含むデコミット鍵Dを出力するステップと、
を有するコミットメント生成方法。
【請求項12】
G1,G2,GTが群であり、G1≠G2であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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→を不受理とするステップと、
を有するコミットメント検証方法。
【請求項13】
請求項3又は5のコミットメント生成装置の各部としてコンピュータを機能させるためのプログラム。
【請求項14】
請求項4又は6のコミットメント検証装置の各部としてコンピュータを機能させるためのプログラム。
【請求項1】
コミットメント生成装置とコミットメント検証装置とを有し、
G1,G2,GTが群であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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を計算する第1コミットメント計算部と、
cb=h(0)tb・Πi=1k h(i)t(i)∈G1を計算する第2コミットメント計算部と、
c(i)=m(i)・g2t(i)∈G2(i=1,...,k)を計算する第3コミットメント計算部と、
ca, cb, c(1),...,c(k)を含むコミットメントCを出力するコミットメント出力部と、
da=g2ta∈G2を計算する第1デコミット鍵計算部と、
db=g2tb∈G2を計算する第2デコミット鍵計算部と、
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→を不受理とする検証部と、を含む、
コミットメントシステム。
【請求項2】
コミットメント生成装置とコミットメント検証装置とを有し、
G1,G2,GTが群であり、G1≠G2であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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を計算する第1コミットメント計算部と、
c(i)=m(i)・g2t(i)∈G2(i=1,...,k)を計算する第3コミットメント計算部と、
ca, c(1),...,c(k)を含むコミットメントCを出力するコミットメント出力部と、
da=g2ta∈G2を計算する第1デコミット鍵計算部と、
daを含むデコミット鍵Dを出力するデコミット鍵出力部と、を含み、
前記コミットメント検証装置は、
前記コミットメントCの入力を受け付けるコミットメント入力部と、
前記メッセージm→、前記コミットメント鍵ck、及び前記デコミット鍵Dの入力を受け付けるオープニング情報入力部と、
関係e(ca, g2)=e(g(0), da)・Πi=1k e(g(i), c(i)/m(i))が満たされるかを検証し、前記関係が満たされる場合に前記メッセージm→を受理し、前記関係が満たされない場合に前記メッセージm→を不受理とする検証部と、を含む、
コミットメントシステム。
【請求項3】
G1,G2,GTが群であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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を計算する第1コミットメント計算部と、
cb=h(0)tb・Πi=1k h(i)t(i)∈G1を計算する第2コミットメント計算部と、
c(i)=m(i)・g2t(i)∈G2(i=1,...,k)を計算する第3コミットメント計算部と、
ca, cb, c(1),...,c(k)を含むコミットメントCを出力するコミットメント出力部と、
da=g2ta∈G2を計算する第1デコミット鍵計算部と、
db=g2tb∈G2を計算する第2デコミット鍵計算部と、
da, dbを含むデコミット鍵Dを出力するデコミット鍵出力部と、
を有するコミットメント生成装置。
【請求項4】
G1,G2,GTが群であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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→を不受理とする検証部と、
を有するコミットメント検証装置。
【請求項5】
G1,G2,GTが群であり、G1≠G2であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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を計算する第1コミットメント計算部と、
c(i)=m(i)・g2t(i)∈G2(i=1,...,k)を計算する第3コミットメント計算部と、
ca, c(1),...,c(k)を含むコミットメントCを出力するコミットメント出力部と、
da=g2ta∈G2を計算する第1デコミット鍵計算部と、
daを含むデコミット鍵Dを出力するデコミット鍵出力部と、
を有するコミットメント生成装置。
【請求項6】
G1,G2,GTが群であり、G1≠G2であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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→を不受理とする検証部と、
を有するコミットメント検証装置。
【請求項7】
G1,G2,GTが群であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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→を不受理とするステップと、を含む、
コミットメント方法。
【請求項8】
G1,G2,GTが群であり、G1≠G2であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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→を不受理とするステップと、
を有するコミットメント方法。
【請求項9】
G1,G2,GTが群であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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)を選択するステップと、
第1コミットメント計算部で、ca=g(0)ta・Πi=1k g(i)t(i)∈G1を計算するステップと、
第2コミットメント計算部で、cb=h(0)tb・Πi=1k h(i)t(i)∈G1を計算するステップと、
第3コミットメント計算部で、c(i)=m(i)・g2t(i)∈G2 (i=1,...,k)を計算するステップと、
コミットメント出力部で、ca, cb, c(1),...,c(k)を含むコミットメントCを出力するステップと、
第1デコミット鍵計算部で、da=g2ta∈G2を計算するステップと、
第2デコミット鍵計算部で、db=g2tb∈G2を計算するステップと、
デコミット鍵出力部で、da, dbを含むデコミット鍵Dを出力するステップと、
を有するコミットメント生成方法。
【請求項10】
G1,G2,GTが群であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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→を不受理とするステップと、
を有するコミットメント検証方法。
【請求項11】
G1,G2,GTが群であり、G1≠G2であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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)を選択するステップと、
第1コミットメント計算部で、ca=g(0)ta・Πi=1k g(i)t(i)∈G1を計算するステップと、
第3コミットメント計算部で、c(i)=m(i)・g2t(i)∈G2 (i=1,...,k)を計算するステップと、
コミットメント出力部で、ca, c(1),...,c(k)を含むコミットメントCを出力するステップと、
第1デコミット鍵計算部で、da=g2ta∈G2を計算するステップと、
デコミット鍵出力部で、daを含むデコミット鍵Dを出力するステップと、
を有するコミットメント生成方法。
【請求項12】
G1,G2,GTが群であり、G1≠G2であり、g2が前記群G2の生成元であり、eが前記群G1と前記群G2の直積群G1×G2の元に対して前記群GTの元を得る双線形写像G1×G2→GTであり、Zpが位数pの整数剰余環であり、kが1以上の整数であり、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→を不受理とするステップと、
を有するコミットメント検証方法。
【請求項13】
請求項3又は5のコミットメント生成装置の各部としてコンピュータを機能させるためのプログラム。
【請求項14】
請求項4又は6のコミットメント検証装置の各部としてコンピュータを機能させるためのプログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【公開番号】特開2013−115602(P2013−115602A)
【公開日】平成25年6月10日(2013.6.10)
【国際特許分類】
【出願番号】特願2011−259762(P2011−259762)
【出願日】平成23年11月29日(2011.11.29)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
【公開日】平成25年6月10日(2013.6.10)
【国際特許分類】
【出願日】平成23年11月29日(2011.11.29)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
[ Back to top ]