Notice: Undefined variable: fterm_desc_sub in /mnt/www/biblio_conv.php on line 353
ビットコミットメントシステム、ビットコミットメント方法、ビットコミットメント送信装置、ビットコミットメント受信装置、ビットコミットメント送信方法、ビットコミットメント受信方法、ビットコミットメントプログラム
説明

ビットコミットメントシステム、ビットコミットメント方法、ビットコミットメント送信装置、ビットコミットメント受信装置、ビットコミットメント送信方法、ビットコミットメント受信方法、ビットコミットメントプログラム

【課題】非対話方式、かつ、複数ビットコミットメント方式のビットコミットメントシステムの提供という課題がある。
【解決手段】本発明のビットコミットメントシステムは、情報mを送信する送信装置と受信装置と公開装置からなる。公開装置は、ABO−TDFの関数インデックスsを含む共通参照情報crsを公開し、送信装置は、検証鍵vkを損失枝として、関数インデックスs及び乱数raから、ABO−TDFを用いて、c0を求め、乱数rbを用いて、c0のランダム化を行い、c1を生成し、乱数ra及び情報mからc2を求め、c1及びc2から、署名鍵skを用いて、署名σを生成する署名生成部と、c1、c2及びσを含むコミットメントcomを生成するコミットメント生成部とを備え、受信装置は、共通参照情報crs及び開封情報Mを用いてコミットメントcomを検証するコミットメント検証部とを備える。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、電気通信システムにおいて、ある情報をコミット(確約)し、検証するビットコミットメントシステム、ビットコミットメント送信装置、ビットコミットメント受信装置、その方法及びそのプログラムに関する。
【背景技術】
【0002】
非対話方式、かつ、単一ビットコミットメント方式として非特許文献1が従来技術として知られている。一方、対話方式、かつ、複数ビットコミットメント方式であって、2つのコミットメントを生成する方式として非特許文献2が従来技術として知られている。
【先行技術文献】
【非特許文献】
【0003】
【非特許文献1】Ran Canetti, Marc Fischlin, "Universally Composable Commitments", Advances in Cryptology - CRYPTO 2001, Springer Berlin / Heidelberg, 2001, Volume 2139/2001, p.19-40
【非特許文献2】Ivan Damgard, Jens Groth, "Non-interactive and reusable non-malleable commitment schemes", Annual ACM Symposium on Theory of Computing, San Diego, CA, USA, ACM, 2003, p.426 - 437
【発明の概要】
【発明が解決しようとする課題】
【0004】
しかしながら、従来技術は非対話方式であるが、複数ビットコミットメント方式でないか、複数ビットコミットメント方式であるが、非対話方式でないものしか存在しなかった。非対話方式、かつ、複数ビットコミットメント方式のビットコミットメントシステム、ビットコミットメント方法及びそのための装置の提供という課題がある。
【課題を解決するための手段】
【0005】
本発明のビットコミットメントシステムは、1ビット以上の情報mをコミットする送信装置とコミットメントを検証する受信装置と信用できる第三者が管理する公開装置からなる。公開装置は、All−But−One落とし戸付一方向性関数(以下、「ABO−TDF」という)の関数インデックスsを含む共通参照情報crsを生成、公開する。送信装置は、検証鍵vkを損失枝として、関数インデックスs及び乱数raから、ABO−TDFを用いて、c0を求め、乱数rbを用いて、c0のランダム化を行い、c1を生成し、乱数ra及び情報mからc2を求め、c1及びc2から、署名鍵skを用いて、署名σを生成する署名生成部と、c1、c2及びσを含むコミットメントcomを生成するコミットメント生成部と、情報m、乱数ra、rbを含む開封情報Mを生成する開封情報生成部とを備える。受信装置は、検証鍵vkを用いて、署名σを検証する署名検証部と、共通参照情報crs及び開封情報Mを用いてコミットメントcomを検証するコミットメント検証部とを備える。
【0006】
なお、本発明は、All−but−One落とし戸付一方向性関数(以下、「ABO−TDF」という)とその準同型性を利用している。ABO−TDFについて、詳しくは、Chris Peikert, Brent Waters, " Lossy trapdoor functions and their applications ", Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, ACM, 2008, p.187-196(以下「参考文献1」という)に記載されている。ここでは、ABO−TDFの概略について説明する。λをABO−TDFのセキュリティパラメータとする。なお、セキュリティパラメータは、署名文を偽造することの困難さを表した尺度である。n(λ)は関数の入力長を、k(λ)は関数の欠落度を(以下、λを省略する)、rは剰余漏洩量を表し、
r(λ)=n(λ)−k(λ)
と定義する。また、ABO−TDFは枝を持ち、B={Bλλ∈Nは、セキュリティパラメータをλとした場合の枝の集合を表す。ABO−TDFは、一方向性関数アルゴリズムGabo、関数インデックス及び落とし戸を生成する関数インデックス生成アルゴリズムSabo、及び、逆関数アルゴリズムG−1aboからなり、以下のような性質を有する。
(1)任意の損失枝Lb∈Bλに対し、
【0007】
【数1】

を生成する。但し、sは関数のインデックスを、zは落とし戸を表す。但し、
【0008】
【数2】

は、yがA(x1,x2,…;r)と乱数rを用いて生成されることを意味する。よって、式(1)は、セキュリティパラメータλ、損失枝Lb及び乱数rを用いて関数インデックスs及び落とし戸zを生成することを意味する。
(2)任意の単射枝Ib∈Bλに対し(但し、Ib≠Lb)、Gabo(s,Ib,・)は定義域{0,1}上で、全射関数gs,Ib(・)を計算する。G−1abo(z,Ib,・)は逆関数g−1s,Ib(・)を計算する。Gabo(s,Lb,・)は定義域{0,1}上で、全射関数gs,Lb(・)を計算する。但し、その値域の大きさは2=2n−kである。
(3)任意のLb、Lb∈Bλに対し、sとsは多項式時間アルゴリズムでは識別不可能である。但し、(s,t)←Sabo(1λ,Lb)かつ、(s,t)←Sabo(1λ,Lb)である。
【0009】
また、公開鍵暗号方式(Gen,Enc,Dec)が準同型性をもつとは、以下を満たすことである。但し、Genは鍵生成アルゴリズム、Encは暗号アルゴリズム、Decは復号アルゴリズムを表す。任意のn及び
【0010】
【数3】

に対し、群Μ(メッセージ空間であり、群演算子は◎)とC(暗号文空間であり、群演算子は▲)において、
(1)任意のm∈Μに対し、Encpk(m)∈Cである。
(2)任意のm1,m2∈Μとc1,c2∈C、かつ、m1=Decsk(c1)かつm2=Decsk(c2)に対し、次が成立する。
Decsk(c1▲c2)=m1◎m2
但し、群演算はそれぞれΜとCで実行される。
【発明の効果】
【0011】
本発明は、ビットコミットメント方式において、従来のビットコミットメント方式と同様の安全性を実現し、さらに、非対話方式としてユーザの操作を簡略化し、かつ、複数ビットコミットメント方式により計算量や通信量等を効率化するという効果を奏する。
【図面の簡単な説明】
【0012】
【図1】ビットコミットメントシステムの構成例を示す図。
【図2】ビットコミットメントシステムのフロー例を示す図。
【図3】公開装置300の構成例を示す図。
【図4】公開装置300のフロー例を示す図。
【図5】送信装置100の構成例を示す図。
【図6】送信装置100のフロー例を示す図。
【図7】署名生成部130のフロー例を示す図。
【図8】受信装置200の構成例を示す図。
【図9】受信装置200のフロー例を示す図。
【図10】送信装置100のハードウェア構成を例示したブロック図。
【発明を実施するための形態】
【0013】
以下、本発明の実施の形態について、詳細に説明する。
【実施例1】
【0014】
[ビットコミットメントシステム1]
図1はビットコミットメントシステム1の構成例を、図2はビットコミットメントシステム1のフロー例を示す。図1及び2を用いて実施例1に係るビットコミットメントシステムの概要を説明する。ビットコミットメントシステム1は、1ビット以上の情報mをコミットする送信装置100とコミットメントを検証する受信装置200と信用できる第三者が管理する公開装置300からなる。本実施例では、ABO−TDFを実現するために、DDH(decisional Diffie-Hellman)問題を利用する。
【0015】
まず、送信装置100は、公開装置300に共通参照情報crsを要求する(s10)。
【0016】
公開装置300は、要求に応じて、crsを生成し、送信装置100へ送信する(s12)。
【0017】
送信装置100は、鍵生成アルゴリズムGenを用いて、署名鍵sk及び検証鍵vkを生成する。(s14)。送信装置100は、共通参照情報crs及び署名アルゴリズムSignを用いて、情報mに基づき生成される情報に対する署名σを生成する。さらに、署名σ及び検証鍵vkを含むコミットメントcomを生成し、受信装置200へ送信する(s18)。
【0018】
コミットメントを受信した受信装置200は、共通参照情報crsを公開装置300へ要求する(s20)。公開装置300は、要求に応え、crsを受信装置へ送信する(s22)。受信装置200は、検証アルゴリズムVrfy及び検証鍵vkを用いて、署名σの正当性を検証する(s24)。
【0019】
送信装置100は、情報mを受信装置200へ送信する(s26)。
【0020】
受信装置200は、情報m、コミットメントcom及び共通参照情報crsを用いて、コミットメントcomを受信してから情報mを受信するまでに、情報mが改竄等されていないことを検証する(s28)。
【0021】
なお、本実施例は発明の内容を限定するものではない。例えば、共通参照情報crsを要求するタイミングは、コミットメントcom検証前であればよい。また、署名を検証するタイミングは、コミットメントcom受信後であればよい。また、送信装置100はGen,Signを記憶し、受信装置200はVrfyを記憶しているが、公開装置300にGen,Sign,Vrfyを公開し、必要に応じて、送信装置100、受信装置200が受信する構成としてもよい。公開鍵vkを生成したのが送信装置100であることが確かである場合には、公開鍵vkを公開装置300へ送信し、公開装置300が公開鍵vkを公開し、受信装置200は、必要に応じて、公開鍵vkを公開装置300から受信する構成としてもよい。また、送信装置100と公開装置300における通信が安全である場合には、鍵生成を公開装置300が行い、署名鍵skを送信装置100に送信し、公開鍵vkを公開し、受信装置200は、必要に応じて、公開鍵vkを公開装置300から受信する構成としてもよい。なお、鍵生成アルゴリズムGenで生成された署名鍵skと署名アルゴリズムSignを用いて生成された署名は、対の検証鍵vkと検証アルゴリズムVrfyを用いて検証することができる。また、この電子署名方式は、1回、または、複数回の選択文書攻撃に対し強存在的偽造不可であるものとする。
【0022】
[公開装置300]
図3は公開装置300の構成例を、図4は公開装置300のフロー例を示す。公開装置300は、信頼できる第三者等が管理し、通信部301、記憶部303、制御部305、乱数生成部310及び共通参照情報320を有する。公開装置300は、共通参照情報crsを公開する。なお、「公開」とは、利用者の求めに応じて、情報(例えば、共通参照情報crs)を閲覧可能、または、取得可能とすることを意味する。公開装置300は、送信装置100から共通参照情報crsを要求されると(s301a)、乱数を生成し(s310)、乱数を用いて共通参照情報を生成し(s320)、これを記憶部へ記録し(s303)、送信装置へ送信する(s301c)。さらに、受信装置から共通参照情報crsを要求されると(s301e)、記憶部303から情報を呼び出し、受信装置200へ送信する(s301g)。以下、各部の詳細を説明する。
【0023】
<通信部301>
公開装置300は、通信部301を介して、送信装置100及び受信装置200と通信する。以下、特に記述しなくとも、送信装置100及び受信装置200と通信する際には、通信部301を介して行われるものとする。同様に、各装置(送信装置100及び受信装置200)は、各通信部101及び201を介して他の装置と通信する。各通信部101、201及び301は、例えば、LANアダプタ等により構成され、LANやインターネット等からなる通信回線と接続される。但し、必ずしも通信部を有さずともよく、例えば、キーボード等の入力装置から共通参照情報crs等を入力してもよいし、また、USBメモリ等の可搬媒体に共通参照情報crs等を記憶し、それを入力してもよい。
【0024】
<記憶部303>
記憶部303は、crs等を記憶する(s303)。また、落とし戸情報zを秘密に記憶する。なお、特に示さない限り、入出力される各データや演算過程の各データは、逐一、記憶部303に格納・読み出され、各演算処理が進められる。但し、必ずしも記憶部303に記憶しなければならないわけではなく、各部間で直接データを受け渡してもよい。なお、各装置(送信装置100及び受信装置200)における記憶部103、203も同様である。
【0025】
<制御部305>
制御部305は、各処理を制御する。同様に、各装置(送信装置100及び受信装置200)において、各制御部105及び205は、各処理を制御する。
【0026】
<乱数生成部310>
乱数生成部310は、乱数r=(r1,…,rn)を生成する(s310)。但し、pを素数とし、位数pの巡回群をG、Gの生成元をg、各riは乱数であり、i∈[n]、[n]={1,2,…,n}、r∈Zとする。なお、Z={0,…,p−1}である。乱数生成部310は、乱数rを共通参照情報生成部320へ出力する。但し、必ずしも乱数生成部310を有さずともよく、例えば、キーボード等の入力装置から乱数rを入力してもよいし、また、USBメモリ等の可搬媒体に乱数rを記憶し、それを入力してもよい。後述する送信装置100の乱数生成部110も同様である。なお、本実施例において、p,G,gは、予め各装置において共有しているが、公開装置300が公開パラメータとして、公開し、他の装置が受信する構成としてもよい。
【0027】
<共通参照情報生成部320>
共通参照情報生成部320は、ABO−TDFの関数インデックスsを含む共通参照情報crsを生成する(s320)。例えば、h()を対独立ハッシュ関数、t=g^zとし、crsを(s,h(),t)とする。但し、a^bはaを意味し、落とし戸情報をz∈Zとする。なお、j∈[n]である。対独立ハッシュ関数とは、x≠x’、y≠y’、定義域をD、値域をRとし、全ての異なるx、x’∈Dと全てのy、y’∈Rに対しhをランダムに選んだとき、次の式が成立する関数である。
Pr[h(x)=y^h(x')=y']=1/|R|2
なお、生成した共通参照情報crsを記憶部303へ出力し、記憶部303はこれを記憶する。
【0028】
関数インデックスsは、損失枝Lbとして、以下の行列として表される。
s=(ci,j
【0029】
【数4】

なお、ci,j=Enctj(Lb;ri)
とする。なお、Enctjにおけるtjはtを意味する。ここで、Encは以下の処理を行う。
Enc(a,r)=(g,t
よって、
i,j=(gri,triLb
である。本実施例では、説明を簡単にするため、Lb=0として計算する。よって、
i,j=(gri,tri
となる。つまり、式(1)より、共通参照情報生成部は、損失枝を0とし、セキュリティパラメータをλとして、乱数rを用いて、関数インデックスs及び落とし戸zを生成する。
【0030】
【数5】

なお、Lb≠0であっても同様に計算することができる。但し、通常、検証鍵vk≠0であることを考慮し、Lb≠vkとするため、Lb=0としてもよい。なお、情報mが入力される毎に異なる共通参照情報crsが生成されることになる。但し、安全性が低くなるが、同一の共通参照情報を用いてもよい。
【0031】
[送信装置100]
図5は送信装置100の構成例を、図6は送信装置のフロー例を示す。送信装置100(ビットコミットメント送信装置100と呼んでもよい)は、通信部101、記憶部103、制御部105、乱数生成部110、鍵生成部120、署名生成部130、コミットメント生成部150及び開封情報生成部160とを有する。
【0032】
送信装置100は、制御部105の制御の下、キーボード等の入力部等から1ビット以上の情報mが入力されると(s100)、情報mをコミットするために、通信部101を介して、公開装置300に共通参照情報crsを要求し、公開装置300から共通参照情報crsを受信する(s101a)。但し、m∈Zとする。また、送信装置100は、コミットメント及び開封情報Mを生成し、受信装置200へコミットメントcomを送信する(s101c)。そして開封情報Mを送信できる場合には(s165)、受信装置200へ開封情報Mを送信する(s101e)。開封情報Mを送信できる場合とは、例えば、予め定めた時刻を経過した場合等が考えられる。受信装置200からの応答等を必要とせず、非対話型のビットコミットメントシステムを実現できる。
【0033】
記憶部103は、公開装置から受け取った共通参照情報crs等を記憶し、送信する情報mや生成した署名鍵sk、検証鍵vk、乱数ra、rb、署名σ、コミットメントcom及び開封情報M等を記憶してもよい。
【0034】
<乱数生成部110>
乱数生成部110は、乱数ra及びrbを生成する(s110)。但し、乱数ra,rb∈Zである。
【0035】
<鍵生成部120>
鍵生成部120は、鍵生成アルゴリズムGenを用いて、署名鍵sk及び検証鍵vkを生成する(s120)。例えば、乱数生成部110において、乱数r3を生成し、セキュリティパラメータと乱数r3を入力として、鍵生成アルゴリズムを用いて署名鍵sk及び検証鍵vkを生成する。鍵生成アルゴリズムが実行される度に異なる乱数が選ばれるので、情報mが入力される毎に異なる公開鍵・秘密鍵ペアが割り振られることになる。但し、安全性が低くなるが、同一の公開鍵・秘密鍵ペアを用いてもよい。
【0036】
<署名生成部130>
署名生成部130は、乱数生成部110から乱数ra及びrbを、鍵生成部120から署名鍵sk及び検証鍵vkを、公開装置100から共通参照情報crsを、入力部等から情報mを入力される。但し、一旦、記憶部103に記憶された情報を入力されてもよい。署名生成部130は、これらの情報から情報c1及びc2を生成し、さらに、c1及びc2から署名σを生成する。生成したc1、c2、σをコミットメント生成部150へ出力する。
【0037】
図7は、署名生成部130のフロー例を示す図である。まず、共通参照情報crsに含まれる関数インデックスs、検証鍵vk及び乱数raから、落とし戸付一方向性関数ABO−TDFを用いて、c0を求める(s131)。落とし戸付一方向性関数ABO−TDFを用いるとは、一方向性関数アルゴリズムGaboによってc0を求めることを意味する。
c0=Gabo(s,vk,ra)
例えば、Gaboは以下の式によって実現される。
c0=y=ra(s★vk・I)
但し、ra=(ra,ra,…,ra),ra∈{0,1}、y=y,…,yであり、Iは単位行列、つまり、対角成分のみ1で残りは全て0の行列である。また、演算子★は、暗号アルゴリズムEncが、c=(c1,c2)=Enc(m;r)=(g,t)のとき(gは生成元、t=g^zであり、zは落とし戸情報である)、
c★v=(c1,c2・gv)=Enct(m;r)■Enct(v;0)=Enct(m+v;r)
と定義される。なお、演算子■は成分ごとの乗算を表す。また、Enc(m;r)=(g,t)より、Enc(m1;r1)■Enc(m2;r2)=(gr1,tr1m1)・(gr2,tr2m2)=(gr1+r2,tr1+r2m1+m2)=Enc(m1+m2;r1+r2)となり、x∈ZのときEnc(m;r)=(grx,trxmx)=Enc(mx;rx)となる。
【0038】
yの各要素yは以下のように定義することもできる。
yj=■i∈[n](ci,j★vk・δi,j)^rai=Enchj(vk・raj:<ra,r>)
但し、yj=■i∈[n](ci,j★vk・δi,j)^raiは、
yj=(c1,j★vk・δ1,j)^ra1■(c2,j★vk・δ2,j)^ra■…■(cn,j★vk・δn,j)^ra
を意味し、i=jならδi,j=1、i≠jならδi,j=0であり、Enchjにおけるhjは、hを意味する。
【0039】
次に、乱数rbを用い、関数インデックスsの準同型性を利用して、c0のランダム化を行いc1を生成する(s133)。例えば、以下の式により、ランダム化を行う。
c1=y’=ra(s★vk・I)☆rb
但し、演算子☆は、
c☆rb=(c1・grb,c2・trb)= Enct(m;r)■Enct(0;rb)=Enct(m;r+rb)
と定義される。(なお、Decsk(c☆rb)=mである。)
よって、
y’=Enchj((vk−0)ra;<ra,r>+rb) (2)
を得て、c1=y’=(y’,…,y’)を生成する。
【0040】
c2は、例えば、以下のように求める。乱数raから、ハッシュ関数h()を用いて、ハッシュ値h(ra)を求める(s135)。ハッシュ値h(ra)と情報mとの排他的論理和をc2として求める(s137)。
【0041】
【数6】

このような方法によると少ない演算量でc2を求めることができる。但し、c2の生成方法は、この方法に限るものではなく、c2に情報m及び乱数raを含むが、c2を見ただけでは、情報m及び乱数raを知ることはできない方法であれば、他の方法を用いてもよい。
【0042】
c1及びc2から、署名鍵sk及び署名アルゴリズムSignを用いて、署名σを生成する(s137)。
σ=Signsk(c1,c2)
なお、c1、c2は何れを先に生成してもよいし、並行処理してもよい。
【0043】
<コミットメント生成部150>
コミットメント生成部150は、c1、c2、σ及びvkを含むコミットメントcomを生成する(s150)。署名生成部130からc1、c2、σを、鍵生成部120からvkを入力され、comを出力する。
com=(c1,c2,vk,σ)
【0044】
<開封情報生成部160>
開封情報生成部160は、情報m、乱数ra、rbを含む開封情報Mを生成する(s160)。入力部等から情報mを、乱数生成部110から乱数ra,rbを入力され、開封情報Mを出力する。
M=(m,ra,rb)
なお、開封情報M生成と鍵生成等の順番はどちらを先に処理してもよいし、並行処理してもよい。
[受信装置200]
図8は受信装置200の構成例を、図9は受信装置200のフロー例を示す。受信装置200(ビットコミットメント受信装置200と呼んでもよい)は、通信部201、記憶部203、制御部205、署名検証部230及びコミットメント検証部250を有する。
【0045】
受信装置200は、制御部205の制御の下、通信部201を介して、送信装置100からコミットメントcomを受信する(s201a)。受信装置200は、コミットメントcomを記憶部203に記憶する(s203)。そして、コミットメントcomに含まれる署名σの検証を行う(s230)。コミットメントcomを検証するために、公開装置300に共通参照情報crsを要求し、公開装置300から共通参照情報crsを受信する(s201c)。さらに、受信装置200は、開封情報Mを受信し(s201e)、コミットメントcomの検証を行う(s250)。
【0046】
<署名検証部230>
署名検証部230は、コミットメントcomに含まれる検証鍵vk及び検証アルゴリズムVrfyを用いて、署名σの正当性を検証する(s230)。署名検証部230は、コミットメントを入力され、検証結果を出力する。
Vrfyvk(σ,c1,c2)
署名が検証を通過しなかった場合には、例えば、エラーを出力する(s231)。再度、コミットメントcomを送信装置100に要求する構成としてもよい。
【0047】
<コミットメント検証部250>
コミットメント検証部250は、共通参照情報crs及び開封情報Mを用いてコミットメントcomを検証する(s250)。共通参照情報crs及び開封情報Mを入力され、コミットメントcomの検証結果を出力する。コミットメントが検証を通過しなかった場合には、例えば、エラーを出力する(s251)。コミットメント検証部250は、署名σが検証を通過し、かつ、公開装置300から共通参照情報crsを受信し、かつ、開封情報Mを受信した場合に、コミットメントを検証することができる。
【0048】
共通参照情報crsに含まれる関数インデックスsとコミットメントcomに含まれるvkと開封情報Mに含まれるra,rbから、
ra(s★vk・I)☆rb
を計算し、得られる値がコミットメントcomに含まれるc1と同一であるか検証する。
【0049】
また、共通参照情報crsに含まれるハッシュ関数h()とコミットメントcomに含まれるc2から
【0050】
【数7】

を計算し、得られる値が開封情報Mに含まれる情報mと同一であるか検証する。何れか一方の検証を通過しなかった場合には、エラーを出力する。
【0051】
このような構成とすることで、非対話方式、かつ、複数ビットコミットメント方式のビットコミットメントシステムを提供することができる。また、電子署名方式が選択文書攻撃に対し強存在的偽造不可かつdecisional Diffie-Hellman仮定が真であれば、汎用的結合可能安全である。
【0052】
<ハードウェア構成>
図10は、本実施例における送信装置100のハードウェア構成を例示したブロック図である。受信装置200及び公開装置300も同様の構成を有する。
【0053】
図10に例示するように、この例の送信装置100、受信装置200、公開装置300は、それぞれCPU(Central Processing Unit)11、入力部12、出力部13、補助記憶装置14、ROM(Read Only Memory)15、RAM(Random Access Memory)16及びバス17を有している。
【0054】
この例のCPU11は、制御部11a、演算部11b及びレジスタ11cを有し、レジスタ11cに読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部12は、データが入力される入力インターフェース、キーボード、マウス等であり、出力部13は、データが出力される出力インターフェース等である。補助記憶装置14は、例えば、ハードディスク、MO(Magneto-Optical disc)、半導体メモリ等であり、送信装置100、受信装置200及び公開装置300としてコンピュータを機能させるためのプログラムが格納されるプログラム領域14a及び各種データが格納されるデータ領域14bを有している。また、RAM16は、SRAM (Static Random Access Memory)、DRAM (Dynamic Random Access Memory)等であり、上記のプログラムが格納されるプログラム領域16a及び各種データが格納されるデータ領域16bを有している。また、バス17は、CPU11、入力部12、出力部13、補助記憶装置14、ROM15及びRAM16を通信可能に接続する。
【0055】
なお、このようなハードウェアの具体例としては、例えば、パーソナルコンピュータの他、サーバ装置やワークステーション等を例示できる。
【0056】
<プログラム構成>
上述のように、プログラム領域14a,16aには、本実施例の送信装置100、受信装置200、公開装置300の各処理を実行するための各プログラムが格納される。送信プログラム、受信プログラム及び公開プログラムを構成する各プログラムは、単一のプログラム列として記載されていてもよく、また、少なくとも一部のプログラムが別個のモジュールとしてライブラリに格納されていてもよい。また、各プログラムが単体でそれぞれの機能を実現してもよいし、各プログラムがさらに他のライブラリを読み出して各機能を実現するものでもよい。
【0057】
<ハードウェアとプログラムとの協働>
CPU11(図10)は、読み込まれたOS(Operating System)プログラムに従い、補助記憶装置14のプログラム領域14aに格納されている上述のプログラムをRAM16のプログラム領域16aに書き込む。同様にCPU11は、補助記憶装置14のデータ領域14bに格納されている各種データを、RAM16のデータ領域16bに書き込む。そして、このプログラムやデータが書き込まれたRAM16上のアドレスがCPU11のレジスタ11cに格納される。CPU11の制御部11aは、レジスタ11cに格納されたこれらのアドレスを順次読み出し、読み出したアドレスが示すRAM16上の領域からプログラムやデータを読み出し、そのプログラムが示す演算を演算部11bに順次実行させ、その演算結果をレジスタ11cに格納していく。
【0058】
図3、5、8は、このようにCPU11に上述のプログラムが読み込まれて実行されることにより構成される公開装置300、送信装置100、受信装置200の機能構成を例示したブロック図である。
【0059】
ここで、記憶部103、203及び303は、補助記憶装置14、RAM16、レジスタ11c、その他のバッファメモリやキャッシュメモリ等の何れか、あるいはこれらを併用した記憶領域に相当する。また、通信部101と、記憶部103と、制御部105と、乱数生成部110と、鍵生成部120と、署名生成部130と、コミットメント生成部150と、開封情報生成部160と、CPU11に送信プログラムを実行させることにより構成されるものである。また、通信部201と、記憶部203と、制御部205と、署名検証部230と、コミットメント検証部250は、CPU11に受信プログラムを実行させることにより構成されるものである。また、通信部301と、記憶部303と、制御部305と、乱数生成部310と、共通情報生成部320は、CPU11に公開プログラムを実行させることにより構成されるものである。
【0060】
また、本形態の送信装置100、受信装置200及び公開装置300は、各制御部105、205及び305の制御のもと各処理を実行する。
【実施例2】
【0061】
実施例1と異なる部分について、実施例2に係るビットコミットメントシステムを説明する。
【0062】
[ビットコミットメントシステム1000]
ビットコミットメントシステム1000は、1ビット以上の情報mをコミットする送信装置1100とコミットメントを検証する受信装置1200と信用できる第三者が管理する公開装置1300からなる。本実施例では、ABO−TDFを実現するために、DCR(decisional composite residuosity)問題を利用する。
【0063】
[公開装置1300]
公開装置1300は、信頼できる第三者等が管理し、通信部301、記憶部303、制御部305、乱数生成部1310、共通参照情報1320を有する。
【0064】
<乱数生成部1310>
乱数生成部1310は、乱数r∈Zを生成し、共通参照情報生成部1320へ出力する。Nについては、後述する。
【0065】
<共通参照情報生成部1320>
共通参照情報生成部1320は、ABO−TDFの関数インデックスsを含む共通参照情報crsを生成する。例えば、RSAモジュラスN=pq、gcd(N,φ(N))=1を満たす奇素数p,qを選択し、Nを生成する。fを1以上の整数とし、ABO−TDFの損失枝をLbとし、乱数r∈Zを用いて、関数インデックスs=(1+N)−Lbr^Nを生成する。実施例1と同様の理由により、Lb=0とすると、s=r^Nとなる。また、p,qを用いて、落とし戸情報τ=lcm(p−1,q−1)を生成する。さらに、関数インデックスs、N及びfを含む共通参照情報crsを生成する。なお、このようなNに対して、乗法群ZN^f+1は直積G×Hである。但し、Gは位数Nの巡回群、HはZと同型である。なお、m∈ZN^fとする。また、奇素数p,qは秘密に管理する。
【0066】
[送信装置1100]
送信装置1100は、通信部101、記憶部103、制御部105、乱数生成部1110、鍵生成部120、署名生成部1130、コミットメント生成部150及び開封情報生成部160とを有する。
【0067】
<乱数生成部110>
乱数生成部1110は、乱数ra及びrbを生成する。但し、rb∈Zとする。
【0068】
<署名生成部1130>
まず、共通参照情報crsに含まれる関数インデックスs、検証鍵vk及び乱数raから、落とし戸付一方向性関数ABO−TDFを用いて、c0を求める。落とし戸付一方向性関数ABO−TDFを用いるとは、一方向性関数アルゴリズムGaboによってc0を求めることを意味する。
c0=Gabo(s,vk,ra)
例えば、Gaboは以下の式によって実現される。
c0=y=(s◆vk)ra
ここで、演算子◆は、暗号アルゴリズムEncが、
c=Enc(m;r)=(1+N)r^N mod Nf+1
のとき
c◆v=c・(1+N)v=EncN(m;r)・EncN(v;1)=EncN(m+v,r)
と定義される。よって、
y=(s◆vk)ra=Enc(vk・ra;r)
と表される。なお、Enc(m;r)=(1+N)r^Nmod Nf+1より、Enc(m1;r1)・Enc(m2;r2)=Enc(m1+m2;r1・r2)となり、Enc(m;r)=Enc(mx;r)となる。
【0069】
次に、乱数rbを用い、関数インデックスsの準同型性を利用して、c0のランダム化を行いc1を生成する。例えば、以下の式により、ランダム化を行う。
c1=y’=(s◆vk)ra◇rb
但し、演算子◇は、
c◇rb=c・rb^Nf=EncN(m;r)・EncN(0;rb)= EncN(m;r・rb)
と定義される。
よって、c1=Enc((vk−0)ra;rra・rb)を生成する。
c2及び署名σの生成方法は実施例1の署名生成部130と同様である。
【0070】
[受信装置1200]
受信装置1200は、通信部201、記憶部203、制御部205、署名検証部230及びコミットメント検証部1250を有する。
【0071】
<コミットメント検証部1250>
コミットメント検証部1250は、共通参照情報crs及び開封情報Mを用いてコミットメントcomを検証する。共通参照情報crs及び開封情報Mを入力され、コミットメントcomの検証結果を出力する。コミットメントが検証を通過しなかった場合には、例えば、エラーを出力する。コミットメント検証部250は、署名σが検証を通過し、かつ、公開装置300から共通参照情報crsを受信し、かつ、開封情報Mを受信した場合に、コミットメントを検証することができる。
【0072】
共通参照情報crsに含まれる関数インデックスsとコミットメントcomに含まれるvkと開封情報Mに含まれるra,rbから、
(s◆vk)ra◇rb
を計算し、得られる値がコミットメントcomに含まれるc1と同一であるか検証する。
【0073】
また、共通参照情報crsに含まれるハッシュ関数h()とコミットメントcomに含まれるc2から
【0074】
【数8】

を計算し、得られる値が開封情報Mに含まれる情報mと同一であるか検証する。何れか一方の検証を通過しなかった場合には、エラーを出力する。
【0075】
このような構成とすることで、実施例1と同様に、非対話方式、かつ、複数ビットコミットメント方式のビットコミットメントシステムを提供することができる。また、電子署名方式が選択文書攻撃に対し強存在的偽造不可かつdecisional composite residuosity仮定が真であれば、汎用的結合可能安全である。
【符号の説明】
【0076】
1 ビットコミットメントシステム
100 送信装置
200 受信装置
300 公開装置
101、201、301 通信部
103、203、303 記憶部
105、205、305 制御部
110、310 乱数生成部
120 鍵生成部
130 署名生成部
150 コミットメント生成部
160 開封情報生成部
230 署名検証部
250 コミットメント検証部
320 共通参照情報生成部

【特許請求の範囲】
【請求項1】
1ビット以上の情報mをコミットする送信装置とコミットメントを検証する受信装置と信用できる第三者が管理する公開装置からなるビットコミットメントシステムであって、
前記公開装置は、
All−But−One落とし戸付一方向性関数(以下、「ABO−TDF」という)の関数インデックスsを含む共通参照情報crsを生成、公開し、
前記送信装置は、
検証鍵vkを損失枝として、前記関数インデックスs及び乱数raから、ABO−TDFを用いて、c0を求め、乱数rbを用いて、前記c0のランダム化を行い、c1を生成し、前記乱数ra及び前記情報mからc2を求め、前記c1及びc2から、署名鍵skを用いて、署名σを生成する署名生成部と、
前記c1、c2及びσを含むコミットメントcomを生成するコミットメント生成部と、
前記情報m、乱数ra、rbを含む開封情報Mを生成する開封情報生成部とを備え、
前記受信装置は、
前記検証鍵vkを用いて、署名σを検証する署名検証部と、
前記共通参照情報crs及び開封情報Mを用いてコミットメントcomを検証するコミットメント検証部とを備える、
ことを特徴とするビットコミットメントシステム。
【請求項2】
請求項1記載のビットコミットメントシステムであって、
pを素数とし、位数pの巡回群をG、Gの生成元をg、i,j∈[n]、[n]={1,2,…,n}、r=(r1,…ri…,rn)、r∈Zは乱数、ra∈Z、ra=(ra,…,ra)、ra∈{0,1}、rb=(rb,…,rb)、rb∈Zは乱数、Iは単位行列とし、
前記公開装置は、
=g^zであり、Lbを損失枝として、ci,j=(gri,triLb)とし、関数インデックスsを行列(ci,j)として生成し、ABO−TDFの落とし戸情報z∈Zを生成し、ABO−TDFの関数インデックスs及tびを含む共通参照情報crsを生成、公開し、
前記送信装置の署名生成部は、
c=(c1,c2)=(g,t)のとき、演算子★を、c★v=(c1,c2・g)と定義し、演算子☆を、c☆rb=(c1・grb,c2・trb)と定義して、
前記c0=ra(s★vk・I)としてを生成し、
前記乱数rbを用いて、前記c0のランダム化を行い、前記c1=ra(s★vk・I)☆rbとして、生成し、
前記受信装置のコミットメント検証部は、
ra(s★vk・I)☆rbを計算し、得られた値と前記c1の値が同一か検証を行うこと、
を特徴とするビットコミットメントシステム。
【請求項3】
請求項1記載のビットコミットメントシステムであって、
前記公開装置は、
N=pq、gcd(N,φ(N))=1を満たす奇素数p,qを選択し、1以上の整数fを選択し、乱数r∈Zを生成し、ABO−TDFの損失枝をLbとし、関数インデックスs=(1+N)−Lbr^N及び落とし戸情報τ=lcm(p−1,q−1)を生成し、関数インデックスs、N及びfを含む共通参照情報crsを生成、公開し、
前記送信装置の署名生成部は、
c=(1+N)r^Nのとき、演算子◆をc◆v=c・(1+N)と定義し、演算子◇をc◇rb=c・rb^Nと定義して、前記c0=(s◆vk)raとして生成し、前記乱数rb∈Zを用いて、前記c0のランダム化を行い、c1=(s◆vk)ra◇rb
として生成し、
前記受信装置の署名検証部は、
(s◆vk)ra◇rbを計算し、得られた値と前記c1の値が同一か検証を行うこと、
を特徴とするビットコミットメントシステム。
【請求項4】
検証鍵vkをAll−But−One落とし戸付一方向性関数(以下、「ABO−TDF」という)の損失枝として、ABO−TDFの関数インデックスs及び乱数raから、ABO−TDFを用いて、c0を求め、乱数rbを用いて、前記c0のランダム化を行い、c1を生成し、前記乱数ra及び1ビット以上の情報mからc2を求め、前記c1及びc2から、署名鍵skを用いて、署名σを生成する署名生成部と、
前記c1、c2及びσを含むコミットメントcomを生成するコミットメント生成部と、
前記情報m、乱数ra、rbを含む開封情報Mを生成する開封情報生成部と、
を有するビットコミットメント送信装置。
【請求項5】
請求項4記載のビットコミットメント送信装置であって、
pを素数とし、位数pの巡回群をG、Gの生成元をg、i,j∈[n]、[n]={1,2,…,n}、r=(r1,…ri…,rn)、r∈Zは乱数、ra∈Z、ra=(ra,…,ra)、ra∈{0,1}、rb=(rb,…,rb)、rb∈Zは乱数、Iは単位行列とし、
署名生成部は、c=(c1,c2)=(g,t)のとき、演算子★を、c★v=(c1,c2・g)と定義し、演算子☆を、c☆rb=(c1・grb,c2・trb)と定義して、前記c0=ra(s★vk・I)としてを生成し、前記乱数rbを用いて、前記c0のランダム化を行い、前記c1=ra(s★vk・I)☆rbとして、生成すること、
を特徴とするビットコミットメント送信装置。
【請求項6】
請求項4記載のビットコミットメント送信装置であって、
p,qを奇素数、N=pq、gcd(N,φ(N))=1、乱数r∈Zとし、
前記署名生成部は、
c=(1+N)r^Nのとき、演算子◆をc◆v=c・(1+N)と定義し、演算子◇をc◇rb=c・rb^Nと定義して、前記c0=(s◆vk)raとして生成し、前記乱数rb∈Zを用いて、前記c0のランダム化を行い、前記c1=(s◆vk)ra◇rbとして生成すること、
を特徴とするビットコミットメント送信装置。
【請求項7】
検証鍵vkを損失枝として、All−But−One落とし戸付一方向性関数(以下、「ABO−TDF」という)の関数インデックスs及び乱数raから、ABO−TDFを用いて、c0を求め、乱数rbを用いて、前記c0のランダム化を行い、c1を生成し、前記乱数ra及び前記情報mからc2を求め、前記c1及びc2から、署名鍵skを用いて、生成された署名σを、検証鍵vkを用いて、検証する署名検証部と、
ABO−TDFの関数インデックスsを含む共通参照情報crs及び乱数ra、rbを含む開封情報Mを用いてコミットメントcomを検証するコミットメント検証部とを備える、
ことを特徴とするビットコミットメント受信装置。
【請求項8】
請求項7記載のビットコミットメント受信装置であって、
pを素数、位数pの巡回群をG、Gの生成元をg、i,j∈[n]、[n]={1,2,…,n}、r=(r1,…ri…,rn)、r∈Zは乱数、ra∈Z、ra=(ra,…,ra)、ra∈{0,1}、rb=(rb,…,rb)、rb∈Zは乱数、Iは単位行列、t=g^z、Lbを損失枝、ci,j=(gri,triLb)、関数インデックスsを行列(ci,j)とし、c=(c1,c2)=(g,t)のとき、演算子★を、c★v=(c1,c2・g)と定義し、演算子☆を、c☆rb=(c1・grb,c2・trb)と定義して、前記c1=ra(s★vk・I)☆rbとして、
前記コミットメント検証部は、
ra(s★vk・I)☆rbを計算し、得られた値と前記c1の値が同一か検証を行うこと、
を特徴とするビットコミットメント受信装置。
【請求項9】
請求項7記載のビットコミットメント受信装置であって、
p,qは奇素数、N=pq、gcd(N,φ(N))=1を満たし、c=(1+N)r^Nのとき、演算子◆をc◆v=c・(1+N)と定義し、演算子◇をc◇rb=c・rb^Nと定義して、rb∈Z、前記c1=(s◆vk)ra◇rbとして、
前記受信装置の署名検証部は、
(s◆vk)ra◇rbを計算し、得られた値と前記c1の値が同一か検証を行うこと、
を特徴とするビットコミットメント受信装置。
【請求項10】
1ビット以上の情報mをコミットする送信装置とコミットメントを検証する受信装置と信用できる第三者が管理する公開装置を用いるビットコミットメント方法であって、
前記公開装置が、All−But−One落とし戸付一方向性関数(以下、「ABO−TDF」という)の関数インデックスsを含む共通参照情報crsを生成、公開するステップと、
前記送信装置が、検証鍵vkを損失枝として、前記関数インデックスs及び乱数raから、ABO−TDFを用いて、c0を求め、乱数rbを用いて、前記c0のランダム化を行い、c1を生成し、前記乱数ra及び前記情報mからc2を求め、前記c1及びc2から、署名鍵skを用いて、署名σを生成する署名生成ステップと、
前記送信装置が、前記c1、c2及びσを含むコミットメントcomを生成するコミットメント生成ステップと、
前記受信装置が、前記検証鍵vkを用いて、署名σを検証する署名検証ステップと、
前記送信装置が、前記情報m、乱数ra、rbを含む開封情報Mを生成する開封情報生成ステップと、
前記受信装置が、前記共通参照情報crs及び開封情報Mを用いてコミットメントcomを検証するコミットメント検証ステップとを備える、
ことを特徴とするビットコミットメント方法。
【請求項11】
検証鍵vkをAll−But−One落とし戸付一方向性関数(以下、「ABO−TDF」という)の損失枝として、ABO−TDFの関数インデックスs及び乱数raから、ABO−TDFを用いて、c0を求めるステップと、
乱数rbを用いて、前記c0のランダム化を行い、c1を生成するステップと、
前記乱数ra及び1ビット以上の情報mからc2を求めるステップと、
前記c1及びc2から、署名鍵skを用いて、署名σを生成する署名生成ステップと、
前記c1、c2及びσを含むコミットメントcomを生成するコミットメント生成ステップと、
前記情報m、乱数ra、rbを含む開封情報Mを生成する開封情報生成ステップと、
を有するビットコミットメント送信方法。
【請求項12】
検証鍵vkを損失枝として、All−But−One落とし戸付一方向性関数(以下、「ABO−TDF」という)の関数インデックスs及び乱数raから、ABO−TDFを用いて、c0を求め、乱数rbを用いて、前記c0のランダム化を行い、c1を生成し、前記乱数ra及び前記情報mからc2を求め、前記c1及びc2から、署名鍵skを用いて、生成された署名σを、検証鍵vkを用いて、検証する署名検証ステップと、
ABO−TDFの関数インデックスsを含む共通参照情報crs及び乱数ra、rbを含む開封情報Mを用いてコミットメントcomを検証するコミットメント検証ステップとを備える、
ことを特徴とするビットコミットメント受信方法。
【請求項13】
請求項4から9記載の何れかのビットコミットメント送信装置、または、ビットコミットメント受信装置として、コンピュータを機能させるためのビットコミットメントプログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate


【公開番号】特開2010−164876(P2010−164876A)
【公開日】平成22年7月29日(2010.7.29)
【国際特許分類】
【出願番号】特願2009−8482(P2009−8482)
【出願日】平成21年1月19日(2009.1.19)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】