ビットコミットメントシステム、ビットコミットメント方法、ビットコミットメント送信装置、ビットコミットメント受信装置、ビットコミットメント送信方法、ビットコミットメント受信方法、ビットコミットメントプログラム
【課題】非対話方式、かつ、複数ビットコミットメント方式のビットコミットメントシステムの提供という課題がある。
【解決手段】本発明のビットコミットメントシステムは、情報ｍを送信する送信装置と受信装置と公開装置からなる。公開装置は、ＡＢＯ−ＴＤＦの関数インデックスｓを含む共通参照情報ｃｒｓを公開し、送信装置は、検証鍵ｖｋを損失枝として、関数インデックスｓ及び乱数ｒａから、ＡＢＯ−ＴＤＦを用いて、ｃ０を求め、乱数ｒｂを用いて、ｃ０のランダム化を行い、ｃ１を生成し、乱数ｒａ及び情報ｍからｃ２を求め、ｃ１及びｃ２から、署名鍵ｓｋを用いて、署名σを生成する署名生成部と、ｃ１、ｃ２及びσを含むコミットメントｃｏｍを生成するコミットメント生成部とを備え、受信装置は、共通参照情報ｃｒｓ及び開封情報Ｍを用いてコミットメントｃｏｍを検証するコミットメント検証部とを備える。
【解決手段】本発明のビットコミットメントシステムは、情報ｍを送信する送信装置と受信装置と公開装置からなる。公開装置は、ＡＢＯ−ＴＤＦの関数インデックスｓを含む共通参照情報ｃｒｓを公開し、送信装置は、検証鍵ｖｋを損失枝として、関数インデックスｓ及び乱数ｒａから、ＡＢＯ−ＴＤＦを用いて、ｃ０を求め、乱数ｒｂを用いて、ｃ０のランダム化を行い、ｃ１を生成し、乱数ｒａ及び情報ｍからｃ２を求め、ｃ１及びｃ２から、署名鍵ｓｋを用いて、署名σを生成する署名生成部と、ｃ１、ｃ２及びσを含むコミットメントｃｏｍを生成するコミットメント生成部とを備え、受信装置は、共通参照情報ｃｒｓ及び開封情報Ｍを用いてコミットメントｃｏｍを検証するコミットメント検証部とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電気通信システムにおいて、ある情報をコミット（確約）し、検証するビットコミットメントシステム、ビットコミットメント送信装置、ビットコミットメント受信装置、その方法及びそのプログラムに関する。
【背景技術】
【０００２】
非対話方式、かつ、単一ビットコミットメント方式として非特許文献１が従来技術として知られている。一方、対話方式、かつ、複数ビットコミットメント方式であって、２つのコミットメントを生成する方式として非特許文献２が従来技術として知られている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ran Canetti, Marc Fischlin, "Universally Composable Commitments", Advances in Cryptology - CRYPTO 2001, Springer Berlin / Heidelberg, 2001, Volume 2139/2001, p.19-40
【非特許文献２】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
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来技術は非対話方式であるが、複数ビットコミットメント方式でないか、複数ビットコミットメント方式であるが、非対話方式でないものしか存在しなかった。非対話方式、かつ、複数ビットコミットメント方式のビットコミットメントシステム、ビットコミットメント方法及びそのための装置の提供という課題がある。
【課題を解決するための手段】
【０００５】
本発明のビットコミットメントシステムは、１ビット以上の情報ｍをコミットする送信装置とコミットメントを検証する受信装置と信用できる第三者が管理する公開装置からなる。公開装置は、Ａｌｌ−Ｂｕｔ−Ｏｎｅ落とし戸付一方向性関数（以下、「ＡＢＯ−ＴＤＦ」という）の関数インデックスｓを含む共通参照情報ｃｒｓを生成、公開する。送信装置は、検証鍵ｖｋを損失枝として、関数インデックスｓ及び乱数ｒａから、ＡＢＯ−ＴＤＦを用いて、ｃ０を求め、乱数ｒｂを用いて、ｃ０のランダム化を行い、ｃ１を生成し、乱数ｒａ及び情報ｍからｃ２を求め、ｃ１及びｃ２から、署名鍵ｓｋを用いて、署名σを生成する署名生成部と、ｃ１、ｃ２及びσを含むコミットメントｃｏｍを生成するコミットメント生成部と、情報ｍ、乱数ｒａ、ｒｂを含む開封情報Ｍを生成する開封情報生成部とを備える。受信装置は、検証鍵ｖｋを用いて、署名σを検証する署名検証部と、共通参照情報ｃｒｓ及び開封情報Ｍを用いてコミットメントｃｏｍを検証するコミットメント検証部とを備える。
【０００６】
なお、本発明は、Ａｌｌ−ｂｕｔ−Ｏｎｅ落とし戸付一方向性関数（以下、「ＡＢＯ−ＴＤＦ」という）とその準同型性を利用している。ＡＢＯ−ＴＤＦについて、詳しくは、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（以下「参考文献１」という）に記載されている。ここでは、ＡＢＯ−ＴＤＦの概略について説明する。λをＡＢＯ−ＴＤＦのセキュリティパラメータとする。なお、セキュリティパラメータは、署名文を偽造することの困難さを表した尺度である。ｎ（λ）は関数の入力長を、ｋ（λ）は関数の欠落度を（以下、λを省略する）、ｒは剰余漏洩量を表し、
ｒ（λ）＝ｎ（λ）−ｋ（λ）
と定義する。また、ＡＢＯ−ＴＤＦは枝を持ち、Ｂ＝｛Ｂλ｝λ∈Ｎは、セキュリティパラメータをλとした場合の枝の集合を表す。ＡＢＯ−ＴＤＦは、一方向性関数アルゴリズムＧａｂｏ、関数インデックス及び落とし戸を生成する関数インデックス生成アルゴリズムＳａｂｏ、及び、逆関数アルゴリズムＧ−１ａｂｏからなり、以下のような性質を有する。
（１）任意の損失枝Ｌｂ∈Ｂλに対し、
【０００７】
【数１】
を生成する。但し、ｓは関数のインデックスを、ｚは落とし戸を表す。但し、
【０００８】
【数２】
は、ｙがＡ（ｘ１，ｘ２，…；ｒ）と乱数ｒを用いて生成されることを意味する。よって、式（１）は、セキュリティパラメータλ、損失枝Ｌｂ及び乱数ｒを用いて関数インデックスｓ及び落とし戸ｚを生成することを意味する。
（２）任意の単射枝Ｉｂ∈Ｂλに対し（但し、Ｉｂ≠Ｌｂ）、Ｇａｂｏ（ｓ，Ｉｂ，・）は定義域｛０，１｝ｎ上で、全射関数ｇｓ，Ｉｂ（・）を計算する。Ｇ−１ａｂｏ（ｚ，Ｉｂ，・）は逆関数ｇ−１ｓ，Ｉｂ（・）を計算する。Ｇａｂｏ（ｓ，Ｌｂ，・）は定義域｛０，１｝ｎ上で、全射関数ｇｓ，Ｌｂ（・）を計算する。但し、その値域の大きさは２ｒ＝２ｎ−ｋである。
（３）任意のＬｂ０、Ｌｂ１∈Ｂλに対し、ｓ０とｓ１は多項式時間アルゴリズムでは識別不可能である。但し、（ｓ０，ｔ０）←Ｓａｂｏ（１λ，Ｌｂ０）かつ、（ｓ１，ｔ１）←Ｓａｂｏ（１λ，Ｌｂ１）である。
【０００９】
また、公開鍵暗号方式（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）が準同型性をもつとは、以下を満たすことである。但し、Ｇｅｎは鍵生成アルゴリズム、Ｅｎｃは暗号アルゴリズム、Ｄｅｃは復号アルゴリズムを表す。任意のｎ及び
【００１０】
【数３】
に対し、群Μ（メッセージ空間であり、群演算子は◎）とＣ（暗号文空間であり、群演算子は▲）において、
（１）任意のｍ∈Μに対し、Ｅｎｃｐｋ（ｍ）∈Ｃである。
（２）任意のｍ１，ｍ２∈Μとｃ１，ｃ２∈Ｃ、かつ、ｍ１＝Ｄｅｃｓｋ（ｃ１）かつｍ２＝Ｄｅｃｓｋ（ｃ２）に対し、次が成立する。
Ｄｅｃｓｋ（ｃ１▲ｃ２）＝ｍ１◎ｍ２
但し、群演算はそれぞれΜとＣで実行される。
【発明の効果】
【００１１】
本発明は、ビットコミットメント方式において、従来のビットコミットメント方式と同様の安全性を実現し、さらに、非対話方式としてユーザの操作を簡略化し、かつ、複数ビットコミットメント方式により計算量や通信量等を効率化するという効果を奏する。
【図面の簡単な説明】
【００１２】
【図１】ビットコミットメントシステムの構成例を示す図。
【図２】ビットコミットメントシステムのフロー例を示す図。
【図３】公開装置３００の構成例を示す図。
【図４】公開装置３００のフロー例を示す図。
【図５】送信装置１００の構成例を示す図。
【図６】送信装置１００のフロー例を示す図。
【図７】署名生成部１３０のフロー例を示す図。
【図８】受信装置２００の構成例を示す図。
【図９】受信装置２００のフロー例を示す図。
【図１０】送信装置１００のハードウェア構成を例示したブロック図。
【発明を実施するための形態】
【００１３】
以下、本発明の実施の形態について、詳細に説明する。
【実施例１】
【００１４】
［ビットコミットメントシステム１］
図１はビットコミットメントシステム１の構成例を、図２はビットコミットメントシステム１のフロー例を示す。図１及び２を用いて実施例１に係るビットコミットメントシステムの概要を説明する。ビットコミットメントシステム１は、１ビット以上の情報ｍをコミットする送信装置１００とコミットメントを検証する受信装置２００と信用できる第三者が管理する公開装置３００からなる。本実施例では、ＡＢＯ−ＴＤＦを実現するために、ＤＤＨ（decisional Diffie-Hellman）問題を利用する。
【００１５】
まず、送信装置１００は、公開装置３００に共通参照情報ｃｒｓを要求する（ｓ１０）。
【００１６】
公開装置３００は、要求に応じて、ｃｒｓを生成し、送信装置１００へ送信する（ｓ１２）。
【００１７】
送信装置１００は、鍵生成アルゴリズムＧｅｎを用いて、署名鍵ｓｋ及び検証鍵ｖｋを生成する。（ｓ１４）。送信装置１００は、共通参照情報ｃｒｓ及び署名アルゴリズムＳｉｇｎを用いて、情報ｍに基づき生成される情報に対する署名σを生成する。さらに、署名σ及び検証鍵ｖｋを含むコミットメントｃｏｍを生成し、受信装置２００へ送信する（ｓ１８）。
【００１８】
コミットメントを受信した受信装置２００は、共通参照情報ｃｒｓを公開装置３００へ要求する（ｓ２０）。公開装置３００は、要求に応え、ｃｒｓを受信装置へ送信する（ｓ２２）。受信装置２００は、検証アルゴリズムＶｒｆｙ及び検証鍵ｖｋを用いて、署名σの正当性を検証する（ｓ２４）。
【００１９】
送信装置１００は、情報ｍを受信装置２００へ送信する（ｓ２６）。
【００２０】
受信装置２００は、情報ｍ、コミットメントｃｏｍ及び共通参照情報ｃｒｓを用いて、コミットメントｃｏｍを受信してから情報ｍを受信するまでに、情報ｍが改竄等されていないことを検証する（ｓ２８）。
【００２１】
なお、本実施例は発明の内容を限定するものではない。例えば、共通参照情報ｃｒｓを要求するタイミングは、コミットメントｃｏｍ検証前であればよい。また、署名を検証するタイミングは、コミットメントｃｏｍ受信後であればよい。また、送信装置１００はＧｅｎ，Ｓｉｇｎを記憶し、受信装置２００はＶｒｆｙを記憶しているが、公開装置３００にＧｅｎ，Ｓｉｇｎ，Ｖｒｆｙを公開し、必要に応じて、送信装置１００、受信装置２００が受信する構成としてもよい。公開鍵ｖｋを生成したのが送信装置１００であることが確かである場合には、公開鍵ｖｋを公開装置３００へ送信し、公開装置３００が公開鍵ｖｋを公開し、受信装置２００は、必要に応じて、公開鍵ｖｋを公開装置３００から受信する構成としてもよい。また、送信装置１００と公開装置３００における通信が安全である場合には、鍵生成を公開装置３００が行い、署名鍵ｓｋを送信装置１００に送信し、公開鍵ｖｋを公開し、受信装置２００は、必要に応じて、公開鍵ｖｋを公開装置３００から受信する構成としてもよい。なお、鍵生成アルゴリズムＧｅｎで生成された署名鍵ｓｋと署名アルゴリズムＳｉｇｎを用いて生成された署名は、対の検証鍵ｖｋと検証アルゴリズムＶｒｆｙを用いて検証することができる。また、この電子署名方式は、１回、または、複数回の選択文書攻撃に対し強存在的偽造不可であるものとする。
【００２２】
［公開装置３００］
図３は公開装置３００の構成例を、図４は公開装置３００のフロー例を示す。公開装置３００は、信頼できる第三者等が管理し、通信部３０１、記憶部３０３、制御部３０５、乱数生成部３１０及び共通参照情報３２０を有する。公開装置３００は、共通参照情報ｃｒｓを公開する。なお、「公開」とは、利用者の求めに応じて、情報（例えば、共通参照情報ｃｒｓ）を閲覧可能、または、取得可能とすることを意味する。公開装置３００は、送信装置１００から共通参照情報ｃｒｓを要求されると（ｓ３０１ａ）、乱数を生成し（ｓ３１０）、乱数を用いて共通参照情報を生成し（ｓ３２０）、これを記憶部へ記録し（ｓ３０３）、送信装置へ送信する（ｓ３０１ｃ）。さらに、受信装置から共通参照情報ｃｒｓを要求されると（ｓ３０１ｅ）、記憶部３０３から情報を呼び出し、受信装置２００へ送信する（ｓ３０１ｇ）。以下、各部の詳細を説明する。
【００２３】
＜通信部３０１＞
公開装置３００は、通信部３０１を介して、送信装置１００及び受信装置２００と通信する。以下、特に記述しなくとも、送信装置１００及び受信装置２００と通信する際には、通信部３０１を介して行われるものとする。同様に、各装置（送信装置１００及び受信装置２００）は、各通信部１０１及び２０１を介して他の装置と通信する。各通信部１０１、２０１及び３０１は、例えば、ＬＡＮアダプタ等により構成され、ＬＡＮやインターネット等からなる通信回線と接続される。但し、必ずしも通信部を有さずともよく、例えば、キーボード等の入力装置から共通参照情報ｃｒｓ等を入力してもよいし、また、ＵＳＢメモリ等の可搬媒体に共通参照情報ｃｒｓ等を記憶し、それを入力してもよい。
【００２４】
＜記憶部３０３＞
記憶部３０３は、ｃｒｓ等を記憶する（ｓ３０３）。また、落とし戸情報ｚｊを秘密に記憶する。なお、特に示さない限り、入出力される各データや演算過程の各データは、逐一、記憶部３０３に格納・読み出され、各演算処理が進められる。但し、必ずしも記憶部３０３に記憶しなければならないわけではなく、各部間で直接データを受け渡してもよい。なお、各装置（送信装置１００及び受信装置２００）における記憶部１０３、２０３も同様である。
【００２５】
＜制御部３０５＞
制御部３０５は、各処理を制御する。同様に、各装置（送信装置１００及び受信装置２００）において、各制御部１０５及び２０５は、各処理を制御する。
【００２６】
＜乱数生成部３１０＞
乱数生成部３１０は、乱数ｒ＝（ｒ１，…，ｒｎ）を生成する（ｓ３１０）。但し、ｐを素数とし、位数ｐの巡回群をＧ、Ｇの生成元をｇ、各ｒｉは乱数であり、ｉ∈［ｎ］、［ｎ］＝｛１，２，…，ｎ｝、ｒ∈Ｚｐとする。なお、Ｚｐ＝｛０，…，ｐ−１｝である。乱数生成部３１０は、乱数ｒを共通参照情報生成部３２０へ出力する。但し、必ずしも乱数生成部３１０を有さずともよく、例えば、キーボード等の入力装置から乱数ｒを入力してもよいし、また、ＵＳＢメモリ等の可搬媒体に乱数ｒを記憶し、それを入力してもよい。後述する送信装置１００の乱数生成部１１０も同様である。なお、本実施例において、ｐ，Ｇ，ｇは、予め各装置において共有しているが、公開装置３００が公開パラメータとして、公開し、他の装置が受信する構成としてもよい。
【００２７】
＜共通参照情報生成部３２０＞
共通参照情報生成部３２０は、ＡＢＯ−ＴＤＦの関数インデックスｓを含む共通参照情報ｃｒｓを生成する（ｓ３２０）。例えば、ｈ（）を対独立ハッシュ関数、ｔｊ＝ｇ＾ｚｊとし、ｃｒｓを（ｓ，ｈ（），ｔｊ）とする。但し、ａ＾ｂはａｂを意味し、落とし戸情報をｚｊ∈Ｚｐとする。なお、ｊ∈［ｎ］である。対独立ハッシュ関数とは、ｘ≠ｘ’、ｙ≠ｙ’、定義域をＤ、値域をＲとし、全ての異なるｘ、ｘ’∈Ｄと全てのｙ、ｙ’∈Ｒに対しｈをランダムに選んだとき、次の式が成立する関数である。
Pr[h(x)=y^h(x')=y']=1/|R|2
なお、生成した共通参照情報ｃｒｓを記憶部３０３へ出力し、記憶部３０３はこれを記憶する。
【００２８】
関数インデックスｓは、損失枝Ｌｂとして、以下の行列として表される。
ｓ＝（ｃｉ，ｊ）
【００２９】
【数４】
なお、ｃｉ，ｊ＝Ｅｎｃｔｊ（Ｌｂ；ｒｉ）
とする。なお、Ｅｎｃｔｊにおけるｔｊはｔｊを意味する。ここで、Ｅｎｃは以下の処理を行う。
Ｅｎｃｔ（ａ，ｒ）＝（ｇｒ，ｔｒｇａ）
よって、
ｃｉ，ｊ＝（ｇｒｉ，ｔｊｒｉｇＬｂ）
である。本実施例では、説明を簡単にするため、Ｌｂ＝０として計算する。よって、
ｃｉ，ｊ＝（ｇｒｉ，ｔｊｒｉ）
となる。つまり、式（１）より、共通参照情報生成部は、損失枝を０とし、セキュリティパラメータをλとして、乱数ｒを用いて、関数インデックスｓ及び落とし戸ｚｊを生成する。
【００３０】
【数５】
なお、Ｌｂ≠０であっても同様に計算することができる。但し、通常、検証鍵ｖｋ≠０であることを考慮し、Ｌｂ≠ｖｋとするため、Ｌｂ＝０としてもよい。なお、情報ｍが入力される毎に異なる共通参照情報ｃｒｓが生成されることになる。但し、安全性が低くなるが、同一の共通参照情報を用いてもよい。
【００３１】
［送信装置１００］
図５は送信装置１００の構成例を、図６は送信装置のフロー例を示す。送信装置１００（ビットコミットメント送信装置１００と呼んでもよい）は、通信部１０１、記憶部１０３、制御部１０５、乱数生成部１１０、鍵生成部１２０、署名生成部１３０、コミットメント生成部１５０及び開封情報生成部１６０とを有する。
【００３２】
送信装置１００は、制御部１０５の制御の下、キーボード等の入力部等から１ビット以上の情報ｍが入力されると（ｓ１００）、情報ｍをコミットするために、通信部１０１を介して、公開装置３００に共通参照情報ｃｒｓを要求し、公開装置３００から共通参照情報ｃｒｓを受信する（ｓ１０１ａ）。但し、ｍ∈Ｚｐとする。また、送信装置１００は、コミットメント及び開封情報Ｍを生成し、受信装置２００へコミットメントｃｏｍを送信する（ｓ１０１ｃ）。そして開封情報Ｍを送信できる場合には（ｓ１６５）、受信装置２００へ開封情報Ｍを送信する（ｓ１０１ｅ）。開封情報Ｍを送信できる場合とは、例えば、予め定めた時刻を経過した場合等が考えられる。受信装置２００からの応答等を必要とせず、非対話型のビットコミットメントシステムを実現できる。
【００３３】
記憶部１０３は、公開装置から受け取った共通参照情報ｃｒｓ等を記憶し、送信する情報ｍや生成した署名鍵ｓｋ、検証鍵ｖｋ、乱数ｒａ、ｒｂ、署名σ、コミットメントｃｏｍ及び開封情報Ｍ等を記憶してもよい。
【００３４】
＜乱数生成部１１０＞
乱数生成部１１０は、乱数ｒａ及びｒｂを生成する（ｓ１１０）。但し、乱数ｒａ，ｒｂ∈Ｚｐである。
【００３５】
＜鍵生成部１２０＞
鍵生成部１２０は、鍵生成アルゴリズムＧｅｎを用いて、署名鍵ｓｋ及び検証鍵ｖｋを生成する（ｓ１２０）。例えば、乱数生成部１１０において、乱数ｒ３を生成し、セキュリティパラメータと乱数ｒ３を入力として、鍵生成アルゴリズムを用いて署名鍵ｓｋ及び検証鍵ｖｋを生成する。鍵生成アルゴリズムが実行される度に異なる乱数が選ばれるので、情報ｍが入力される毎に異なる公開鍵・秘密鍵ペアが割り振られることになる。但し、安全性が低くなるが、同一の公開鍵・秘密鍵ペアを用いてもよい。
【００３６】
＜署名生成部１３０＞
署名生成部１３０は、乱数生成部１１０から乱数ｒａ及びｒｂを、鍵生成部１２０から署名鍵ｓｋ及び検証鍵ｖｋを、公開装置１００から共通参照情報ｃｒｓを、入力部等から情報ｍを入力される。但し、一旦、記憶部１０３に記憶された情報を入力されてもよい。署名生成部１３０は、これらの情報から情報ｃ１及びｃ２を生成し、さらに、ｃ１及びｃ２から署名σを生成する。生成したｃ１、ｃ２、σをコミットメント生成部１５０へ出力する。
【００３７】
図７は、署名生成部１３０のフロー例を示す図である。まず、共通参照情報ｃｒｓに含まれる関数インデックスｓ、検証鍵ｖｋ及び乱数ｒａから、落とし戸付一方向性関数ＡＢＯ−ＴＤＦを用いて、ｃ０を求める（ｓ１３１）。落とし戸付一方向性関数ＡＢＯ−ＴＤＦを用いるとは、一方向性関数アルゴリズムＧａｂｏによってｃ０を求めることを意味する。
ｃ０＝Ｇａｂｏ（ｓ，ｖｋ，ｒａ）
例えば、Ｇａｂｏは以下の式によって実現される。
ｃ０＝ｙ＝ｒａ（ｓ★ｖｋ・Ｉ）
但し、ｒａ＝（ｒａ１，ｒａ２，…，ｒａｎ），ｒａｊ∈｛０，１｝、ｙ＝ｙ１，…，ｙｎであり、Ｉは単位行列、つまり、対角成分のみ１で残りは全て０の行列である。また、演算子★は、暗号アルゴリズムＥｎｃが、ｃ＝（ｃ１，ｃ２）＝Ｅｎｃｔ（ｍ；ｒ）＝（ｇｒ，ｔｒｇｍ）のとき（ｇは生成元、ｔ＝ｇ＾ｚｊであり、ｚｊは落とし戸情報である）、
c★v=(c1,c2・gv)=Enct(m;r)■Enct(v;0)=Enct(m+v;r)
と定義される。なお、演算子■は成分ごとの乗算を表す。また、Ｅｎｃｔ（ｍ；ｒ）＝（ｇｒ，ｔｒｇｍ）より、Ｅｎｃｔ（ｍ１；ｒ１）■Ｅｎｃｔ（ｍ２；ｒ２）＝（ｇｒ１，ｔｒ１ｇｍ１）・（ｇｒ２，ｔｒ２ｇｍ２）＝（ｇｒ１＋ｒ２，ｔｒ１＋ｒ２ｇｍ１＋ｍ２）＝Ｅｎｃｔ（ｍ１＋ｍ２；ｒ１＋ｒ２）となり、ｘ∈ＺｐのときＥｎｃｔ（ｍ；ｒ）ｘ＝（ｇｒｘ，ｔｒｘｇｍｘ）＝Ｅｎｃｔ（ｍｘ；ｒｘ）となる。
【００３８】
ｙの各要素ｙｊは以下のように定義することもできる。
yj＝■i∈[ｎ](ci,j★vk・δi,j)^rai=Enchj(vk・raj:<ra,r>)
但し、yj＝■i∈[ｎ](ci,j★vk・δi,j)^raiは、
yj=(c1,j★vk・δ1,j)^ra1■(c２,j★vk・δ２,j)^ra２■…■(cｎ,j★vk・δｎ,j)^raｎ
を意味し、ｉ＝ｊならδｉ，ｊ＝１、ｉ≠ｊならδｉ，ｊ＝０であり、Enchjにおけるｈｊは、ｈｊを意味する。
【００３９】
次に、乱数ｒｂを用い、関数インデックスｓの準同型性を利用して、ｃ０のランダム化を行いｃ１を生成する（ｓ１３３）。例えば、以下の式により、ランダム化を行う。
ｃ１＝ｙ’＝ｒａ（ｓ★ｖｋ・Ｉ）☆ｒｂ
但し、演算子☆は、
c☆rb=(c1・grb,c2・trb)= Enct(m;r)■Enct(0;rb)=Enct(m;r+rb)
と定義される。（なお、Ｄｅｃｓｋ（ｃ☆ｒｂ）＝ｍである。）
よって、
ｙ’ｊ＝Ｅｎｃｈｊ（（ｖｋ−０）ｒａｊ；＜ｒａ，ｒ＞＋ｒｂｊ） （２）
を得て、ｃ１＝ｙ’＝（ｙ’１，…，ｙ’ｎ）を生成する。
【００４０】
ｃ２は、例えば、以下のように求める。乱数ｒａから、ハッシュ関数ｈ（）を用いて、ハッシュ値ｈ（ｒａ）を求める（ｓ１３５）。ハッシュ値ｈ（ｒａ）と情報ｍとの排他的論理和をｃ２として求める（ｓ１３７）。
【００４１】
【数６】
このような方法によると少ない演算量でｃ２を求めることができる。但し、ｃ２の生成方法は、この方法に限るものではなく、ｃ２に情報ｍ及び乱数ｒａを含むが、ｃ２を見ただけでは、情報ｍ及び乱数ｒａを知ることはできない方法であれば、他の方法を用いてもよい。
【００４２】
ｃ１及びｃ２から、署名鍵ｓｋ及び署名アルゴリズムＳｉｇｎを用いて、署名σを生成する（ｓ１３７）。
σ＝Ｓｉｇｎｓｋ（ｃ１，ｃ２）
なお、ｃ１、ｃ２は何れを先に生成してもよいし、並行処理してもよい。
【００４３】
＜コミットメント生成部１５０＞
コミットメント生成部１５０は、ｃ１、ｃ２、σ及びｖｋを含むコミットメントｃｏｍを生成する（ｓ１５０）。署名生成部１３０からｃ１、ｃ２、σを、鍵生成部１２０からｖｋを入力され、ｃｏｍを出力する。
ｃｏｍ＝（ｃ１，ｃ２，ｖｋ，σ）
【００４４】
＜開封情報生成部１６０＞
開封情報生成部１６０は、情報ｍ、乱数ｒａ、ｒｂを含む開封情報Ｍを生成する（ｓ１６０）。入力部等から情報ｍを、乱数生成部１１０から乱数ｒａ，ｒｂを入力され、開封情報Ｍを出力する。
Ｍ＝（ｍ，ｒａ，ｒｂ）
なお、開封情報Ｍ生成と鍵生成等の順番はどちらを先に処理してもよいし、並行処理してもよい。
［受信装置２００］
図８は受信装置２００の構成例を、図９は受信装置２００のフロー例を示す。受信装置２００（ビットコミットメント受信装置２００と呼んでもよい）は、通信部２０１、記憶部２０３、制御部２０５、署名検証部２３０及びコミットメント検証部２５０を有する。
【００４５】
受信装置２００は、制御部２０５の制御の下、通信部２０１を介して、送信装置１００からコミットメントｃｏｍを受信する（ｓ２０１ａ）。受信装置２００は、コミットメントｃｏｍを記憶部２０３に記憶する（ｓ２０３）。そして、コミットメントｃｏｍに含まれる署名σの検証を行う（ｓ２３０）。コミットメントｃｏｍを検証するために、公開装置３００に共通参照情報ｃｒｓを要求し、公開装置３００から共通参照情報ｃｒｓを受信する（ｓ２０１ｃ）。さらに、受信装置２００は、開封情報Ｍを受信し（ｓ２０１ｅ）、コミットメントｃｏｍの検証を行う（ｓ２５０）。
【００４６】
＜署名検証部２３０＞
署名検証部２３０は、コミットメントｃｏｍに含まれる検証鍵ｖｋ及び検証アルゴリズムＶｒｆｙを用いて、署名σの正当性を検証する（ｓ２３０）。署名検証部２３０は、コミットメントを入力され、検証結果を出力する。
Ｖｒｆｙｖｋ（σ，ｃ１，ｃ２）
署名が検証を通過しなかった場合には、例えば、エラーを出力する（ｓ２３１）。再度、コミットメントｃｏｍを送信装置１００に要求する構成としてもよい。
【００４７】
＜コミットメント検証部２５０＞
コミットメント検証部２５０は、共通参照情報ｃｒｓ及び開封情報Ｍを用いてコミットメントｃｏｍを検証する（ｓ２５０）。共通参照情報ｃｒｓ及び開封情報Ｍを入力され、コミットメントｃｏｍの検証結果を出力する。コミットメントが検証を通過しなかった場合には、例えば、エラーを出力する（ｓ２５１）。コミットメント検証部２５０は、署名σが検証を通過し、かつ、公開装置３００から共通参照情報ｃｒｓを受信し、かつ、開封情報Ｍを受信した場合に、コミットメントを検証することができる。
【００４８】
共通参照情報ｃｒｓに含まれる関数インデックスｓとコミットメントｃｏｍに含まれるｖｋと開封情報Ｍに含まれるｒａ，ｒｂから、
ｒａ（ｓ★ｖｋ・Ｉ）☆ｒｂ
を計算し、得られる値がコミットメントｃｏｍに含まれるｃ１と同一であるか検証する。
【００４９】
また、共通参照情報ｃｒｓに含まれるハッシュ関数ｈ（）とコミットメントｃｏｍに含まれるｃ２から
【００５０】
【数７】
を計算し、得られる値が開封情報Ｍに含まれる情報ｍと同一であるか検証する。何れか一方の検証を通過しなかった場合には、エラーを出力する。
【００５１】
このような構成とすることで、非対話方式、かつ、複数ビットコミットメント方式のビットコミットメントシステムを提供することができる。また、電子署名方式が選択文書攻撃に対し強存在的偽造不可かつdecisional Diffie-Hellman仮定が真であれば、汎用的結合可能安全である。
【００５２】
＜ハードウェア構成＞
図１０は、本実施例における送信装置１００のハードウェア構成を例示したブロック図である。受信装置２００及び公開装置３００も同様の構成を有する。
【００５３】
図１０に例示するように、この例の送信装置１００、受信装置２００、公開装置３００は、それぞれＣＰＵ（Central Processing Unit）１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ（Read Only Memory）１５、ＲＡＭ（Random Access Memory）１６及びバス１７を有している。
【００５４】
この例のＣＰＵ１１は、制御部１１ａ、演算部１１ｂ及びレジスタ１１ｃを有し、レジスタ１１ｃに読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部１２は、データが入力される入力インターフェース、キーボード、マウス等であり、出力部１３は、データが出力される出力インターフェース等である。補助記憶装置１４は、例えば、ハードディスク、ＭＯ（Magneto-Optical disc）、半導体メモリ等であり、送信装置１００、受信装置２００及び公開装置３００としてコンピュータを機能させるためのプログラムが格納されるプログラム領域１４ａ及び各種データが格納されるデータ領域１４ｂを有している。また、ＲＡＭ１６は、ＳＲＡＭ (Static Random Access Memory)、ＤＲＡＭ (Dynamic Random Access Memory)等であり、上記のプログラムが格納されるプログラム領域１６ａ及び各種データが格納されるデータ領域１６ｂを有している。また、バス１７は、ＣＰＵ１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ１５及びＲＡＭ１６を通信可能に接続する。
【００５５】
なお、このようなハードウェアの具体例としては、例えば、パーソナルコンピュータの他、サーバ装置やワークステーション等を例示できる。
【００５６】
＜プログラム構成＞
上述のように、プログラム領域１４ａ，１６ａには、本実施例の送信装置１００、受信装置２００、公開装置３００の各処理を実行するための各プログラムが格納される。送信プログラム、受信プログラム及び公開プログラムを構成する各プログラムは、単一のプログラム列として記載されていてもよく、また、少なくとも一部のプログラムが別個のモジュールとしてライブラリに格納されていてもよい。また、各プログラムが単体でそれぞれの機能を実現してもよいし、各プログラムがさらに他のライブラリを読み出して各機能を実現するものでもよい。
【００５７】
＜ハードウェアとプログラムとの協働＞
ＣＰＵ１１（図１０）は、読み込まれたＯＳ（Operating System）プログラムに従い、補助記憶装置１４のプログラム領域１４ａに格納されている上述のプログラムをＲＡＭ１６のプログラム領域１６ａに書き込む。同様にＣＰＵ１１は、補助記憶装置１４のデータ領域１４ｂに格納されている各種データを、ＲＡＭ１６のデータ領域１６ｂに書き込む。そして、このプログラムやデータが書き込まれたＲＡＭ１６上のアドレスがＣＰＵ１１のレジスタ１１ｃに格納される。ＣＰＵ１１の制御部１１ａは、レジスタ１１ｃに格納されたこれらのアドレスを順次読み出し、読み出したアドレスが示すＲＡＭ１６上の領域からプログラムやデータを読み出し、そのプログラムが示す演算を演算部１１ｂに順次実行させ、その演算結果をレジスタ１１ｃに格納していく。
【００５８】
図３、５、８は、このようにＣＰＵ１１に上述のプログラムが読み込まれて実行されることにより構成される公開装置３００、送信装置１００、受信装置２００の機能構成を例示したブロック図である。
【００５９】
ここで、記憶部１０３、２０３及び３０３は、補助記憶装置１４、ＲＡＭ１６、レジスタ１１ｃ、その他のバッファメモリやキャッシュメモリ等の何れか、あるいはこれらを併用した記憶領域に相当する。また、通信部１０１と、記憶部１０３と、制御部１０５と、乱数生成部１１０と、鍵生成部１２０と、署名生成部１３０と、コミットメント生成部１５０と、開封情報生成部１６０と、ＣＰＵ１１に送信プログラムを実行させることにより構成されるものである。また、通信部２０１と、記憶部２０３と、制御部２０５と、署名検証部２３０と、コミットメント検証部２５０は、ＣＰＵ１１に受信プログラムを実行させることにより構成されるものである。また、通信部３０１と、記憶部３０３と、制御部３０５と、乱数生成部３１０と、共通情報生成部３２０は、ＣＰＵ１１に公開プログラムを実行させることにより構成されるものである。
【００６０】
また、本形態の送信装置１００、受信装置２００及び公開装置３００は、各制御部１０５、２０５及び３０５の制御のもと各処理を実行する。
【実施例２】
【００６１】
実施例１と異なる部分について、実施例２に係るビットコミットメントシステムを説明する。
【００６２】
［ビットコミットメントシステム１０００］
ビットコミットメントシステム１０００は、１ビット以上の情報ｍをコミットする送信装置１１００とコミットメントを検証する受信装置１２００と信用できる第三者が管理する公開装置１３００からなる。本実施例では、ＡＢＯ−ＴＤＦを実現するために、ＤＣＲ（decisional composite residuosity）問題を利用する。
【００６３】
［公開装置１３００］
公開装置１３００は、信頼できる第三者等が管理し、通信部３０１、記憶部３０３、制御部３０５、乱数生成部１３１０、共通参照情報１３２０を有する。
【００６４】
＜乱数生成部１３１０＞
乱数生成部１３１０は、乱数ｒ∈Ｚ＊Ｎを生成し、共通参照情報生成部１３２０へ出力する。Ｎについては、後述する。
【００６５】
＜共通参照情報生成部１３２０＞
共通参照情報生成部１３２０は、ＡＢＯ−ＴＤＦの関数インデックスｓを含む共通参照情報ｃｒｓを生成する。例えば、ＲＳＡモジュラスＮ＝ｐｑ、ｇｃｄ（Ｎ，φ（Ｎ））＝１を満たす奇素数ｐ，ｑを選択し、Ｎを生成する。ｆを１以上の整数とし、ＡＢＯ−ＴＤＦの損失枝をＬｂとし、乱数ｒ∈Ｚ＊Ｎを用いて、関数インデックスｓ＝（１＋Ｎ）−Ｌｂｒ＾Ｎｆを生成する。実施例１と同様の理由により、Ｌｂ＝０とすると、ｓ＝ｒ＾Ｎｆとなる。また、ｐ，ｑを用いて、落とし戸情報τ＝ｌｃｍ（ｐ−１，ｑ−１）を生成する。さらに、関数インデックスｓ、Ｎ及びｆを含む共通参照情報ｃｒｓを生成する。なお、このようなＮに対して、乗法群Ｚ＊Ｎ＾ｆ＋１は直積Ｇ×Ｈである。但し、Ｇは位数Ｎｆの巡回群、ＨはＺ＊Ｎと同型である。なお、ｍ∈Ｚ＊Ｎ^fとする。また、奇素数ｐ，ｑは秘密に管理する。
【００６６】
［送信装置１１００］
送信装置１１００は、通信部１０１、記憶部１０３、制御部１０５、乱数生成部１１１０、鍵生成部１２０、署名生成部１１３０、コミットメント生成部１５０及び開封情報生成部１６０とを有する。
【００６７】
＜乱数生成部１１０＞
乱数生成部１１１０は、乱数ｒａ及びｒｂを生成する。但し、ｒｂ∈Ｚ＊Ｎとする。
【００６８】
＜署名生成部１１３０＞
まず、共通参照情報ｃｒｓに含まれる関数インデックスｓ、検証鍵ｖｋ及び乱数ｒａから、落とし戸付一方向性関数ＡＢＯ−ＴＤＦを用いて、ｃ０を求める。落とし戸付一方向性関数ＡＢＯ−ＴＤＦを用いるとは、一方向性関数アルゴリズムＧａｂｏによってｃ０を求めることを意味する。
ｃ０＝Ｇａｂｏ（ｓ，ｖｋ，ｒａ）
例えば、Ｇａｂｏは以下の式によって実現される。
ｃ０＝ｙ＝（ｓ◆ｖｋ）ｒａ
ここで、演算子◆は、暗号アルゴリズムＥｎｃが、
ｃ＝ＥｎｃＮ（ｍ；ｒ）＝（１＋Ｎ）ｍｒ＾Ｎｆ ｍｏｄ Ｎｆ＋１
のとき
c◆v=c・(1+N)v=EncN(m;r)・EncN(v;1)=EncN(m+v,r)
と定義される。よって、
ｙ＝（ｓ◆ｖｋ）ｒａ＝ＥｎｃＮ（ｖｋ・ｒａ；ｒ）
と表される。なお、ＥｎｃＮ（ｍ；ｒ）＝（１＋Ｎ）ｍｒ＾Ｎｆｍｏｄ Ｎｆ＋１より、ＥｎｃＮ（ｍ１；ｒ１）・ＥｎｃＮ（ｍ２；ｒ２）＝ＥｎｃＮ（ｍ１＋ｍ２；ｒ１・ｒ２）となり、ＥｎｃＮ（ｍ；ｒ）ｘ＝ＥｎｃＮ（ｍｘ；ｒｘ）となる。
【００６９】
次に、乱数ｒｂを用い、関数インデックスｓの準同型性を利用して、ｃ０のランダム化を行いｃ１を生成する。例えば、以下の式により、ランダム化を行う。
ｃ１＝ｙ’＝（ｓ◆ｖｋ）ｒａ◇ｒｂ
但し、演算子◇は、
c◇rb=c・rb^Nf=EncN(m;r)・EncN(0;rb)= EncN(m;r・rb)
と定義される。
よって、ｃ１＝ＥｎｃＮ（（ｖｋ−０）ｒａ；ｒｒａ・ｒｂ）を生成する。
ｃ２及び署名σの生成方法は実施例１の署名生成部１３０と同様である。
【００７０】
［受信装置１２００］
受信装置１２００は、通信部２０１、記憶部２０３、制御部２０５、署名検証部２３０及びコミットメント検証部１２５０を有する。
【００７１】
＜コミットメント検証部１２５０＞
コミットメント検証部１２５０は、共通参照情報ｃｒｓ及び開封情報Ｍを用いてコミットメントｃｏｍを検証する。共通参照情報ｃｒｓ及び開封情報Ｍを入力され、コミットメントｃｏｍの検証結果を出力する。コミットメントが検証を通過しなかった場合には、例えば、エラーを出力する。コミットメント検証部２５０は、署名σが検証を通過し、かつ、公開装置３００から共通参照情報ｃｒｓを受信し、かつ、開封情報Ｍを受信した場合に、コミットメントを検証することができる。
【００７２】
共通参照情報ｃｒｓに含まれる関数インデックスｓとコミットメントｃｏｍに含まれるｖｋと開封情報Ｍに含まれるｒａ，ｒｂから、
（ｓ◆ｖｋ）ｒａ◇ｒｂ
を計算し、得られる値がコミットメントｃｏｍに含まれるｃ１と同一であるか検証する。
【００７３】
また、共通参照情報ｃｒｓに含まれるハッシュ関数ｈ（）とコミットメントｃｏｍに含まれるｃ２から
【００７４】
【数８】
を計算し、得られる値が開封情報Ｍに含まれる情報ｍと同一であるか検証する。何れか一方の検証を通過しなかった場合には、エラーを出力する。
【００７５】
このような構成とすることで、実施例１と同様に、非対話方式、かつ、複数ビットコミットメント方式のビットコミットメントシステムを提供することができる。また、電子署名方式が選択文書攻撃に対し強存在的偽造不可かつdecisional composite residuosity仮定が真であれば、汎用的結合可能安全である。
【符号の説明】
【００７６】
１ ビットコミットメントシステム
１００ 送信装置
２００ 受信装置
３００ 公開装置
１０１、２０１、３０１ 通信部
１０３、２０３、３０３ 記憶部
１０５、２０５、３０５ 制御部
１１０、３１０ 乱数生成部
１２０ 鍵生成部
１３０ 署名生成部
１５０ コミットメント生成部
１６０ 開封情報生成部
２３０ 署名検証部
２５０ コミットメント検証部
３２０ 共通参照情報生成部
【技術分野】
【０００１】
本発明は、電気通信システムにおいて、ある情報をコミット（確約）し、検証するビットコミットメントシステム、ビットコミットメント送信装置、ビットコミットメント受信装置、その方法及びそのプログラムに関する。
【背景技術】
【０００２】
非対話方式、かつ、単一ビットコミットメント方式として非特許文献１が従来技術として知られている。一方、対話方式、かつ、複数ビットコミットメント方式であって、２つのコミットメントを生成する方式として非特許文献２が従来技術として知られている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ran Canetti, Marc Fischlin, "Universally Composable Commitments", Advances in Cryptology - CRYPTO 2001, Springer Berlin / Heidelberg, 2001, Volume 2139/2001, p.19-40
【非特許文献２】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
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来技術は非対話方式であるが、複数ビットコミットメント方式でないか、複数ビットコミットメント方式であるが、非対話方式でないものしか存在しなかった。非対話方式、かつ、複数ビットコミットメント方式のビットコミットメントシステム、ビットコミットメント方法及びそのための装置の提供という課題がある。
【課題を解決するための手段】
【０００５】
本発明のビットコミットメントシステムは、１ビット以上の情報ｍをコミットする送信装置とコミットメントを検証する受信装置と信用できる第三者が管理する公開装置からなる。公開装置は、Ａｌｌ−Ｂｕｔ−Ｏｎｅ落とし戸付一方向性関数（以下、「ＡＢＯ−ＴＤＦ」という）の関数インデックスｓを含む共通参照情報ｃｒｓを生成、公開する。送信装置は、検証鍵ｖｋを損失枝として、関数インデックスｓ及び乱数ｒａから、ＡＢＯ−ＴＤＦを用いて、ｃ０を求め、乱数ｒｂを用いて、ｃ０のランダム化を行い、ｃ１を生成し、乱数ｒａ及び情報ｍからｃ２を求め、ｃ１及びｃ２から、署名鍵ｓｋを用いて、署名σを生成する署名生成部と、ｃ１、ｃ２及びσを含むコミットメントｃｏｍを生成するコミットメント生成部と、情報ｍ、乱数ｒａ、ｒｂを含む開封情報Ｍを生成する開封情報生成部とを備える。受信装置は、検証鍵ｖｋを用いて、署名σを検証する署名検証部と、共通参照情報ｃｒｓ及び開封情報Ｍを用いてコミットメントｃｏｍを検証するコミットメント検証部とを備える。
【０００６】
なお、本発明は、Ａｌｌ−ｂｕｔ−Ｏｎｅ落とし戸付一方向性関数（以下、「ＡＢＯ−ＴＤＦ」という）とその準同型性を利用している。ＡＢＯ−ＴＤＦについて、詳しくは、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（以下「参考文献１」という）に記載されている。ここでは、ＡＢＯ−ＴＤＦの概略について説明する。λをＡＢＯ−ＴＤＦのセキュリティパラメータとする。なお、セキュリティパラメータは、署名文を偽造することの困難さを表した尺度である。ｎ（λ）は関数の入力長を、ｋ（λ）は関数の欠落度を（以下、λを省略する）、ｒは剰余漏洩量を表し、
ｒ（λ）＝ｎ（λ）−ｋ（λ）
と定義する。また、ＡＢＯ−ＴＤＦは枝を持ち、Ｂ＝｛Ｂλ｝λ∈Ｎは、セキュリティパラメータをλとした場合の枝の集合を表す。ＡＢＯ−ＴＤＦは、一方向性関数アルゴリズムＧａｂｏ、関数インデックス及び落とし戸を生成する関数インデックス生成アルゴリズムＳａｂｏ、及び、逆関数アルゴリズムＧ−１ａｂｏからなり、以下のような性質を有する。
（１）任意の損失枝Ｌｂ∈Ｂλに対し、
【０００７】
【数１】
を生成する。但し、ｓは関数のインデックスを、ｚは落とし戸を表す。但し、
【０００８】
【数２】
は、ｙがＡ（ｘ１，ｘ２，…；ｒ）と乱数ｒを用いて生成されることを意味する。よって、式（１）は、セキュリティパラメータλ、損失枝Ｌｂ及び乱数ｒを用いて関数インデックスｓ及び落とし戸ｚを生成することを意味する。
（２）任意の単射枝Ｉｂ∈Ｂλに対し（但し、Ｉｂ≠Ｌｂ）、Ｇａｂｏ（ｓ，Ｉｂ，・）は定義域｛０，１｝ｎ上で、全射関数ｇｓ，Ｉｂ（・）を計算する。Ｇ−１ａｂｏ（ｚ，Ｉｂ，・）は逆関数ｇ−１ｓ，Ｉｂ（・）を計算する。Ｇａｂｏ（ｓ，Ｌｂ，・）は定義域｛０，１｝ｎ上で、全射関数ｇｓ，Ｌｂ（・）を計算する。但し、その値域の大きさは２ｒ＝２ｎ−ｋである。
（３）任意のＬｂ０、Ｌｂ１∈Ｂλに対し、ｓ０とｓ１は多項式時間アルゴリズムでは識別不可能である。但し、（ｓ０，ｔ０）←Ｓａｂｏ（１λ，Ｌｂ０）かつ、（ｓ１，ｔ１）←Ｓａｂｏ（１λ，Ｌｂ１）である。
【０００９】
また、公開鍵暗号方式（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）が準同型性をもつとは、以下を満たすことである。但し、Ｇｅｎは鍵生成アルゴリズム、Ｅｎｃは暗号アルゴリズム、Ｄｅｃは復号アルゴリズムを表す。任意のｎ及び
【００１０】
【数３】
に対し、群Μ（メッセージ空間であり、群演算子は◎）とＣ（暗号文空間であり、群演算子は▲）において、
（１）任意のｍ∈Μに対し、Ｅｎｃｐｋ（ｍ）∈Ｃである。
（２）任意のｍ１，ｍ２∈Μとｃ１，ｃ２∈Ｃ、かつ、ｍ１＝Ｄｅｃｓｋ（ｃ１）かつｍ２＝Ｄｅｃｓｋ（ｃ２）に対し、次が成立する。
Ｄｅｃｓｋ（ｃ１▲ｃ２）＝ｍ１◎ｍ２
但し、群演算はそれぞれΜとＣで実行される。
【発明の効果】
【００１１】
本発明は、ビットコミットメント方式において、従来のビットコミットメント方式と同様の安全性を実現し、さらに、非対話方式としてユーザの操作を簡略化し、かつ、複数ビットコミットメント方式により計算量や通信量等を効率化するという効果を奏する。
【図面の簡単な説明】
【００１２】
【図１】ビットコミットメントシステムの構成例を示す図。
【図２】ビットコミットメントシステムのフロー例を示す図。
【図３】公開装置３００の構成例を示す図。
【図４】公開装置３００のフロー例を示す図。
【図５】送信装置１００の構成例を示す図。
【図６】送信装置１００のフロー例を示す図。
【図７】署名生成部１３０のフロー例を示す図。
【図８】受信装置２００の構成例を示す図。
【図９】受信装置２００のフロー例を示す図。
【図１０】送信装置１００のハードウェア構成を例示したブロック図。
【発明を実施するための形態】
【００１３】
以下、本発明の実施の形態について、詳細に説明する。
【実施例１】
【００１４】
［ビットコミットメントシステム１］
図１はビットコミットメントシステム１の構成例を、図２はビットコミットメントシステム１のフロー例を示す。図１及び２を用いて実施例１に係るビットコミットメントシステムの概要を説明する。ビットコミットメントシステム１は、１ビット以上の情報ｍをコミットする送信装置１００とコミットメントを検証する受信装置２００と信用できる第三者が管理する公開装置３００からなる。本実施例では、ＡＢＯ−ＴＤＦを実現するために、ＤＤＨ（decisional Diffie-Hellman）問題を利用する。
【００１５】
まず、送信装置１００は、公開装置３００に共通参照情報ｃｒｓを要求する（ｓ１０）。
【００１６】
公開装置３００は、要求に応じて、ｃｒｓを生成し、送信装置１００へ送信する（ｓ１２）。
【００１７】
送信装置１００は、鍵生成アルゴリズムＧｅｎを用いて、署名鍵ｓｋ及び検証鍵ｖｋを生成する。（ｓ１４）。送信装置１００は、共通参照情報ｃｒｓ及び署名アルゴリズムＳｉｇｎを用いて、情報ｍに基づき生成される情報に対する署名σを生成する。さらに、署名σ及び検証鍵ｖｋを含むコミットメントｃｏｍを生成し、受信装置２００へ送信する（ｓ１８）。
【００１８】
コミットメントを受信した受信装置２００は、共通参照情報ｃｒｓを公開装置３００へ要求する（ｓ２０）。公開装置３００は、要求に応え、ｃｒｓを受信装置へ送信する（ｓ２２）。受信装置２００は、検証アルゴリズムＶｒｆｙ及び検証鍵ｖｋを用いて、署名σの正当性を検証する（ｓ２４）。
【００１９】
送信装置１００は、情報ｍを受信装置２００へ送信する（ｓ２６）。
【００２０】
受信装置２００は、情報ｍ、コミットメントｃｏｍ及び共通参照情報ｃｒｓを用いて、コミットメントｃｏｍを受信してから情報ｍを受信するまでに、情報ｍが改竄等されていないことを検証する（ｓ２８）。
【００２１】
なお、本実施例は発明の内容を限定するものではない。例えば、共通参照情報ｃｒｓを要求するタイミングは、コミットメントｃｏｍ検証前であればよい。また、署名を検証するタイミングは、コミットメントｃｏｍ受信後であればよい。また、送信装置１００はＧｅｎ，Ｓｉｇｎを記憶し、受信装置２００はＶｒｆｙを記憶しているが、公開装置３００にＧｅｎ，Ｓｉｇｎ，Ｖｒｆｙを公開し、必要に応じて、送信装置１００、受信装置２００が受信する構成としてもよい。公開鍵ｖｋを生成したのが送信装置１００であることが確かである場合には、公開鍵ｖｋを公開装置３００へ送信し、公開装置３００が公開鍵ｖｋを公開し、受信装置２００は、必要に応じて、公開鍵ｖｋを公開装置３００から受信する構成としてもよい。また、送信装置１００と公開装置３００における通信が安全である場合には、鍵生成を公開装置３００が行い、署名鍵ｓｋを送信装置１００に送信し、公開鍵ｖｋを公開し、受信装置２００は、必要に応じて、公開鍵ｖｋを公開装置３００から受信する構成としてもよい。なお、鍵生成アルゴリズムＧｅｎで生成された署名鍵ｓｋと署名アルゴリズムＳｉｇｎを用いて生成された署名は、対の検証鍵ｖｋと検証アルゴリズムＶｒｆｙを用いて検証することができる。また、この電子署名方式は、１回、または、複数回の選択文書攻撃に対し強存在的偽造不可であるものとする。
【００２２】
［公開装置３００］
図３は公開装置３００の構成例を、図４は公開装置３００のフロー例を示す。公開装置３００は、信頼できる第三者等が管理し、通信部３０１、記憶部３０３、制御部３０５、乱数生成部３１０及び共通参照情報３２０を有する。公開装置３００は、共通参照情報ｃｒｓを公開する。なお、「公開」とは、利用者の求めに応じて、情報（例えば、共通参照情報ｃｒｓ）を閲覧可能、または、取得可能とすることを意味する。公開装置３００は、送信装置１００から共通参照情報ｃｒｓを要求されると（ｓ３０１ａ）、乱数を生成し（ｓ３１０）、乱数を用いて共通参照情報を生成し（ｓ３２０）、これを記憶部へ記録し（ｓ３０３）、送信装置へ送信する（ｓ３０１ｃ）。さらに、受信装置から共通参照情報ｃｒｓを要求されると（ｓ３０１ｅ）、記憶部３０３から情報を呼び出し、受信装置２００へ送信する（ｓ３０１ｇ）。以下、各部の詳細を説明する。
【００２３】
＜通信部３０１＞
公開装置３００は、通信部３０１を介して、送信装置１００及び受信装置２００と通信する。以下、特に記述しなくとも、送信装置１００及び受信装置２００と通信する際には、通信部３０１を介して行われるものとする。同様に、各装置（送信装置１００及び受信装置２００）は、各通信部１０１及び２０１を介して他の装置と通信する。各通信部１０１、２０１及び３０１は、例えば、ＬＡＮアダプタ等により構成され、ＬＡＮやインターネット等からなる通信回線と接続される。但し、必ずしも通信部を有さずともよく、例えば、キーボード等の入力装置から共通参照情報ｃｒｓ等を入力してもよいし、また、ＵＳＢメモリ等の可搬媒体に共通参照情報ｃｒｓ等を記憶し、それを入力してもよい。
【００２４】
＜記憶部３０３＞
記憶部３０３は、ｃｒｓ等を記憶する（ｓ３０３）。また、落とし戸情報ｚｊを秘密に記憶する。なお、特に示さない限り、入出力される各データや演算過程の各データは、逐一、記憶部３０３に格納・読み出され、各演算処理が進められる。但し、必ずしも記憶部３０３に記憶しなければならないわけではなく、各部間で直接データを受け渡してもよい。なお、各装置（送信装置１００及び受信装置２００）における記憶部１０３、２０３も同様である。
【００２５】
＜制御部３０５＞
制御部３０５は、各処理を制御する。同様に、各装置（送信装置１００及び受信装置２００）において、各制御部１０５及び２０５は、各処理を制御する。
【００２６】
＜乱数生成部３１０＞
乱数生成部３１０は、乱数ｒ＝（ｒ１，…，ｒｎ）を生成する（ｓ３１０）。但し、ｐを素数とし、位数ｐの巡回群をＧ、Ｇの生成元をｇ、各ｒｉは乱数であり、ｉ∈［ｎ］、［ｎ］＝｛１，２，…，ｎ｝、ｒ∈Ｚｐとする。なお、Ｚｐ＝｛０，…，ｐ−１｝である。乱数生成部３１０は、乱数ｒを共通参照情報生成部３２０へ出力する。但し、必ずしも乱数生成部３１０を有さずともよく、例えば、キーボード等の入力装置から乱数ｒを入力してもよいし、また、ＵＳＢメモリ等の可搬媒体に乱数ｒを記憶し、それを入力してもよい。後述する送信装置１００の乱数生成部１１０も同様である。なお、本実施例において、ｐ，Ｇ，ｇは、予め各装置において共有しているが、公開装置３００が公開パラメータとして、公開し、他の装置が受信する構成としてもよい。
【００２７】
＜共通参照情報生成部３２０＞
共通参照情報生成部３２０は、ＡＢＯ−ＴＤＦの関数インデックスｓを含む共通参照情報ｃｒｓを生成する（ｓ３２０）。例えば、ｈ（）を対独立ハッシュ関数、ｔｊ＝ｇ＾ｚｊとし、ｃｒｓを（ｓ，ｈ（），ｔｊ）とする。但し、ａ＾ｂはａｂを意味し、落とし戸情報をｚｊ∈Ｚｐとする。なお、ｊ∈［ｎ］である。対独立ハッシュ関数とは、ｘ≠ｘ’、ｙ≠ｙ’、定義域をＤ、値域をＲとし、全ての異なるｘ、ｘ’∈Ｄと全てのｙ、ｙ’∈Ｒに対しｈをランダムに選んだとき、次の式が成立する関数である。
Pr[h(x)=y^h(x')=y']=1/|R|2
なお、生成した共通参照情報ｃｒｓを記憶部３０３へ出力し、記憶部３０３はこれを記憶する。
【００２８】
関数インデックスｓは、損失枝Ｌｂとして、以下の行列として表される。
ｓ＝（ｃｉ，ｊ）
【００２９】
【数４】
なお、ｃｉ，ｊ＝Ｅｎｃｔｊ（Ｌｂ；ｒｉ）
とする。なお、Ｅｎｃｔｊにおけるｔｊはｔｊを意味する。ここで、Ｅｎｃは以下の処理を行う。
Ｅｎｃｔ（ａ，ｒ）＝（ｇｒ，ｔｒｇａ）
よって、
ｃｉ，ｊ＝（ｇｒｉ，ｔｊｒｉｇＬｂ）
である。本実施例では、説明を簡単にするため、Ｌｂ＝０として計算する。よって、
ｃｉ，ｊ＝（ｇｒｉ，ｔｊｒｉ）
となる。つまり、式（１）より、共通参照情報生成部は、損失枝を０とし、セキュリティパラメータをλとして、乱数ｒを用いて、関数インデックスｓ及び落とし戸ｚｊを生成する。
【００３０】
【数５】
なお、Ｌｂ≠０であっても同様に計算することができる。但し、通常、検証鍵ｖｋ≠０であることを考慮し、Ｌｂ≠ｖｋとするため、Ｌｂ＝０としてもよい。なお、情報ｍが入力される毎に異なる共通参照情報ｃｒｓが生成されることになる。但し、安全性が低くなるが、同一の共通参照情報を用いてもよい。
【００３１】
［送信装置１００］
図５は送信装置１００の構成例を、図６は送信装置のフロー例を示す。送信装置１００（ビットコミットメント送信装置１００と呼んでもよい）は、通信部１０１、記憶部１０３、制御部１０５、乱数生成部１１０、鍵生成部１２０、署名生成部１３０、コミットメント生成部１５０及び開封情報生成部１６０とを有する。
【００３２】
送信装置１００は、制御部１０５の制御の下、キーボード等の入力部等から１ビット以上の情報ｍが入力されると（ｓ１００）、情報ｍをコミットするために、通信部１０１を介して、公開装置３００に共通参照情報ｃｒｓを要求し、公開装置３００から共通参照情報ｃｒｓを受信する（ｓ１０１ａ）。但し、ｍ∈Ｚｐとする。また、送信装置１００は、コミットメント及び開封情報Ｍを生成し、受信装置２００へコミットメントｃｏｍを送信する（ｓ１０１ｃ）。そして開封情報Ｍを送信できる場合には（ｓ１６５）、受信装置２００へ開封情報Ｍを送信する（ｓ１０１ｅ）。開封情報Ｍを送信できる場合とは、例えば、予め定めた時刻を経過した場合等が考えられる。受信装置２００からの応答等を必要とせず、非対話型のビットコミットメントシステムを実現できる。
【００３３】
記憶部１０３は、公開装置から受け取った共通参照情報ｃｒｓ等を記憶し、送信する情報ｍや生成した署名鍵ｓｋ、検証鍵ｖｋ、乱数ｒａ、ｒｂ、署名σ、コミットメントｃｏｍ及び開封情報Ｍ等を記憶してもよい。
【００３４】
＜乱数生成部１１０＞
乱数生成部１１０は、乱数ｒａ及びｒｂを生成する（ｓ１１０）。但し、乱数ｒａ，ｒｂ∈Ｚｐである。
【００３５】
＜鍵生成部１２０＞
鍵生成部１２０は、鍵生成アルゴリズムＧｅｎを用いて、署名鍵ｓｋ及び検証鍵ｖｋを生成する（ｓ１２０）。例えば、乱数生成部１１０において、乱数ｒ３を生成し、セキュリティパラメータと乱数ｒ３を入力として、鍵生成アルゴリズムを用いて署名鍵ｓｋ及び検証鍵ｖｋを生成する。鍵生成アルゴリズムが実行される度に異なる乱数が選ばれるので、情報ｍが入力される毎に異なる公開鍵・秘密鍵ペアが割り振られることになる。但し、安全性が低くなるが、同一の公開鍵・秘密鍵ペアを用いてもよい。
【００３６】
＜署名生成部１３０＞
署名生成部１３０は、乱数生成部１１０から乱数ｒａ及びｒｂを、鍵生成部１２０から署名鍵ｓｋ及び検証鍵ｖｋを、公開装置１００から共通参照情報ｃｒｓを、入力部等から情報ｍを入力される。但し、一旦、記憶部１０３に記憶された情報を入力されてもよい。署名生成部１３０は、これらの情報から情報ｃ１及びｃ２を生成し、さらに、ｃ１及びｃ２から署名σを生成する。生成したｃ１、ｃ２、σをコミットメント生成部１５０へ出力する。
【００３７】
図７は、署名生成部１３０のフロー例を示す図である。まず、共通参照情報ｃｒｓに含まれる関数インデックスｓ、検証鍵ｖｋ及び乱数ｒａから、落とし戸付一方向性関数ＡＢＯ−ＴＤＦを用いて、ｃ０を求める（ｓ１３１）。落とし戸付一方向性関数ＡＢＯ−ＴＤＦを用いるとは、一方向性関数アルゴリズムＧａｂｏによってｃ０を求めることを意味する。
ｃ０＝Ｇａｂｏ（ｓ，ｖｋ，ｒａ）
例えば、Ｇａｂｏは以下の式によって実現される。
ｃ０＝ｙ＝ｒａ（ｓ★ｖｋ・Ｉ）
但し、ｒａ＝（ｒａ１，ｒａ２，…，ｒａｎ），ｒａｊ∈｛０，１｝、ｙ＝ｙ１，…，ｙｎであり、Ｉは単位行列、つまり、対角成分のみ１で残りは全て０の行列である。また、演算子★は、暗号アルゴリズムＥｎｃが、ｃ＝（ｃ１，ｃ２）＝Ｅｎｃｔ（ｍ；ｒ）＝（ｇｒ，ｔｒｇｍ）のとき（ｇは生成元、ｔ＝ｇ＾ｚｊであり、ｚｊは落とし戸情報である）、
c★v=(c1,c2・gv)=Enct(m;r)■Enct(v;0)=Enct(m+v;r)
と定義される。なお、演算子■は成分ごとの乗算を表す。また、Ｅｎｃｔ（ｍ；ｒ）＝（ｇｒ，ｔｒｇｍ）より、Ｅｎｃｔ（ｍ１；ｒ１）■Ｅｎｃｔ（ｍ２；ｒ２）＝（ｇｒ１，ｔｒ１ｇｍ１）・（ｇｒ２，ｔｒ２ｇｍ２）＝（ｇｒ１＋ｒ２，ｔｒ１＋ｒ２ｇｍ１＋ｍ２）＝Ｅｎｃｔ（ｍ１＋ｍ２；ｒ１＋ｒ２）となり、ｘ∈ＺｐのときＥｎｃｔ（ｍ；ｒ）ｘ＝（ｇｒｘ，ｔｒｘｇｍｘ）＝Ｅｎｃｔ（ｍｘ；ｒｘ）となる。
【００３８】
ｙの各要素ｙｊは以下のように定義することもできる。
yj＝■i∈[ｎ](ci,j★vk・δi,j)^rai=Enchj(vk・raj:<ra,r>)
但し、yj＝■i∈[ｎ](ci,j★vk・δi,j)^raiは、
yj=(c1,j★vk・δ1,j)^ra1■(c２,j★vk・δ２,j)^ra２■…■(cｎ,j★vk・δｎ,j)^raｎ
を意味し、ｉ＝ｊならδｉ，ｊ＝１、ｉ≠ｊならδｉ，ｊ＝０であり、Enchjにおけるｈｊは、ｈｊを意味する。
【００３９】
次に、乱数ｒｂを用い、関数インデックスｓの準同型性を利用して、ｃ０のランダム化を行いｃ１を生成する（ｓ１３３）。例えば、以下の式により、ランダム化を行う。
ｃ１＝ｙ’＝ｒａ（ｓ★ｖｋ・Ｉ）☆ｒｂ
但し、演算子☆は、
c☆rb=(c1・grb,c2・trb)= Enct(m;r)■Enct(0;rb)=Enct(m;r+rb)
と定義される。（なお、Ｄｅｃｓｋ（ｃ☆ｒｂ）＝ｍである。）
よって、
ｙ’ｊ＝Ｅｎｃｈｊ（（ｖｋ−０）ｒａｊ；＜ｒａ，ｒ＞＋ｒｂｊ） （２）
を得て、ｃ１＝ｙ’＝（ｙ’１，…，ｙ’ｎ）を生成する。
【００４０】
ｃ２は、例えば、以下のように求める。乱数ｒａから、ハッシュ関数ｈ（）を用いて、ハッシュ値ｈ（ｒａ）を求める（ｓ１３５）。ハッシュ値ｈ（ｒａ）と情報ｍとの排他的論理和をｃ２として求める（ｓ１３７）。
【００４１】
【数６】
このような方法によると少ない演算量でｃ２を求めることができる。但し、ｃ２の生成方法は、この方法に限るものではなく、ｃ２に情報ｍ及び乱数ｒａを含むが、ｃ２を見ただけでは、情報ｍ及び乱数ｒａを知ることはできない方法であれば、他の方法を用いてもよい。
【００４２】
ｃ１及びｃ２から、署名鍵ｓｋ及び署名アルゴリズムＳｉｇｎを用いて、署名σを生成する（ｓ１３７）。
σ＝Ｓｉｇｎｓｋ（ｃ１，ｃ２）
なお、ｃ１、ｃ２は何れを先に生成してもよいし、並行処理してもよい。
【００４３】
＜コミットメント生成部１５０＞
コミットメント生成部１５０は、ｃ１、ｃ２、σ及びｖｋを含むコミットメントｃｏｍを生成する（ｓ１５０）。署名生成部１３０からｃ１、ｃ２、σを、鍵生成部１２０からｖｋを入力され、ｃｏｍを出力する。
ｃｏｍ＝（ｃ１，ｃ２，ｖｋ，σ）
【００４４】
＜開封情報生成部１６０＞
開封情報生成部１６０は、情報ｍ、乱数ｒａ、ｒｂを含む開封情報Ｍを生成する（ｓ１６０）。入力部等から情報ｍを、乱数生成部１１０から乱数ｒａ，ｒｂを入力され、開封情報Ｍを出力する。
Ｍ＝（ｍ，ｒａ，ｒｂ）
なお、開封情報Ｍ生成と鍵生成等の順番はどちらを先に処理してもよいし、並行処理してもよい。
［受信装置２００］
図８は受信装置２００の構成例を、図９は受信装置２００のフロー例を示す。受信装置２００（ビットコミットメント受信装置２００と呼んでもよい）は、通信部２０１、記憶部２０３、制御部２０５、署名検証部２３０及びコミットメント検証部２５０を有する。
【００４５】
受信装置２００は、制御部２０５の制御の下、通信部２０１を介して、送信装置１００からコミットメントｃｏｍを受信する（ｓ２０１ａ）。受信装置２００は、コミットメントｃｏｍを記憶部２０３に記憶する（ｓ２０３）。そして、コミットメントｃｏｍに含まれる署名σの検証を行う（ｓ２３０）。コミットメントｃｏｍを検証するために、公開装置３００に共通参照情報ｃｒｓを要求し、公開装置３００から共通参照情報ｃｒｓを受信する（ｓ２０１ｃ）。さらに、受信装置２００は、開封情報Ｍを受信し（ｓ２０１ｅ）、コミットメントｃｏｍの検証を行う（ｓ２５０）。
【００４６】
＜署名検証部２３０＞
署名検証部２３０は、コミットメントｃｏｍに含まれる検証鍵ｖｋ及び検証アルゴリズムＶｒｆｙを用いて、署名σの正当性を検証する（ｓ２３０）。署名検証部２３０は、コミットメントを入力され、検証結果を出力する。
Ｖｒｆｙｖｋ（σ，ｃ１，ｃ２）
署名が検証を通過しなかった場合には、例えば、エラーを出力する（ｓ２３１）。再度、コミットメントｃｏｍを送信装置１００に要求する構成としてもよい。
【００４７】
＜コミットメント検証部２５０＞
コミットメント検証部２５０は、共通参照情報ｃｒｓ及び開封情報Ｍを用いてコミットメントｃｏｍを検証する（ｓ２５０）。共通参照情報ｃｒｓ及び開封情報Ｍを入力され、コミットメントｃｏｍの検証結果を出力する。コミットメントが検証を通過しなかった場合には、例えば、エラーを出力する（ｓ２５１）。コミットメント検証部２５０は、署名σが検証を通過し、かつ、公開装置３００から共通参照情報ｃｒｓを受信し、かつ、開封情報Ｍを受信した場合に、コミットメントを検証することができる。
【００４８】
共通参照情報ｃｒｓに含まれる関数インデックスｓとコミットメントｃｏｍに含まれるｖｋと開封情報Ｍに含まれるｒａ，ｒｂから、
ｒａ（ｓ★ｖｋ・Ｉ）☆ｒｂ
を計算し、得られる値がコミットメントｃｏｍに含まれるｃ１と同一であるか検証する。
【００４９】
また、共通参照情報ｃｒｓに含まれるハッシュ関数ｈ（）とコミットメントｃｏｍに含まれるｃ２から
【００５０】
【数７】
を計算し、得られる値が開封情報Ｍに含まれる情報ｍと同一であるか検証する。何れか一方の検証を通過しなかった場合には、エラーを出力する。
【００５１】
このような構成とすることで、非対話方式、かつ、複数ビットコミットメント方式のビットコミットメントシステムを提供することができる。また、電子署名方式が選択文書攻撃に対し強存在的偽造不可かつdecisional Diffie-Hellman仮定が真であれば、汎用的結合可能安全である。
【００５２】
＜ハードウェア構成＞
図１０は、本実施例における送信装置１００のハードウェア構成を例示したブロック図である。受信装置２００及び公開装置３００も同様の構成を有する。
【００５３】
図１０に例示するように、この例の送信装置１００、受信装置２００、公開装置３００は、それぞれＣＰＵ（Central Processing Unit）１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ（Read Only Memory）１５、ＲＡＭ（Random Access Memory）１６及びバス１７を有している。
【００５４】
この例のＣＰＵ１１は、制御部１１ａ、演算部１１ｂ及びレジスタ１１ｃを有し、レジスタ１１ｃに読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部１２は、データが入力される入力インターフェース、キーボード、マウス等であり、出力部１３は、データが出力される出力インターフェース等である。補助記憶装置１４は、例えば、ハードディスク、ＭＯ（Magneto-Optical disc）、半導体メモリ等であり、送信装置１００、受信装置２００及び公開装置３００としてコンピュータを機能させるためのプログラムが格納されるプログラム領域１４ａ及び各種データが格納されるデータ領域１４ｂを有している。また、ＲＡＭ１６は、ＳＲＡＭ (Static Random Access Memory)、ＤＲＡＭ (Dynamic Random Access Memory)等であり、上記のプログラムが格納されるプログラム領域１６ａ及び各種データが格納されるデータ領域１６ｂを有している。また、バス１７は、ＣＰＵ１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ１５及びＲＡＭ１６を通信可能に接続する。
【００５５】
なお、このようなハードウェアの具体例としては、例えば、パーソナルコンピュータの他、サーバ装置やワークステーション等を例示できる。
【００５６】
＜プログラム構成＞
上述のように、プログラム領域１４ａ，１６ａには、本実施例の送信装置１００、受信装置２００、公開装置３００の各処理を実行するための各プログラムが格納される。送信プログラム、受信プログラム及び公開プログラムを構成する各プログラムは、単一のプログラム列として記載されていてもよく、また、少なくとも一部のプログラムが別個のモジュールとしてライブラリに格納されていてもよい。また、各プログラムが単体でそれぞれの機能を実現してもよいし、各プログラムがさらに他のライブラリを読み出して各機能を実現するものでもよい。
【００５７】
＜ハードウェアとプログラムとの協働＞
ＣＰＵ１１（図１０）は、読み込まれたＯＳ（Operating System）プログラムに従い、補助記憶装置１４のプログラム領域１４ａに格納されている上述のプログラムをＲＡＭ１６のプログラム領域１６ａに書き込む。同様にＣＰＵ１１は、補助記憶装置１４のデータ領域１４ｂに格納されている各種データを、ＲＡＭ１６のデータ領域１６ｂに書き込む。そして、このプログラムやデータが書き込まれたＲＡＭ１６上のアドレスがＣＰＵ１１のレジスタ１１ｃに格納される。ＣＰＵ１１の制御部１１ａは、レジスタ１１ｃに格納されたこれらのアドレスを順次読み出し、読み出したアドレスが示すＲＡＭ１６上の領域からプログラムやデータを読み出し、そのプログラムが示す演算を演算部１１ｂに順次実行させ、その演算結果をレジスタ１１ｃに格納していく。
【００５８】
図３、５、８は、このようにＣＰＵ１１に上述のプログラムが読み込まれて実行されることにより構成される公開装置３００、送信装置１００、受信装置２００の機能構成を例示したブロック図である。
【００５９】
ここで、記憶部１０３、２０３及び３０３は、補助記憶装置１４、ＲＡＭ１６、レジスタ１１ｃ、その他のバッファメモリやキャッシュメモリ等の何れか、あるいはこれらを併用した記憶領域に相当する。また、通信部１０１と、記憶部１０３と、制御部１０５と、乱数生成部１１０と、鍵生成部１２０と、署名生成部１３０と、コミットメント生成部１５０と、開封情報生成部１６０と、ＣＰＵ１１に送信プログラムを実行させることにより構成されるものである。また、通信部２０１と、記憶部２０３と、制御部２０５と、署名検証部２３０と、コミットメント検証部２５０は、ＣＰＵ１１に受信プログラムを実行させることにより構成されるものである。また、通信部３０１と、記憶部３０３と、制御部３０５と、乱数生成部３１０と、共通情報生成部３２０は、ＣＰＵ１１に公開プログラムを実行させることにより構成されるものである。
【００６０】
また、本形態の送信装置１００、受信装置２００及び公開装置３００は、各制御部１０５、２０５及び３０５の制御のもと各処理を実行する。
【実施例２】
【００６１】
実施例１と異なる部分について、実施例２に係るビットコミットメントシステムを説明する。
【００６２】
［ビットコミットメントシステム１０００］
ビットコミットメントシステム１０００は、１ビット以上の情報ｍをコミットする送信装置１１００とコミットメントを検証する受信装置１２００と信用できる第三者が管理する公開装置１３００からなる。本実施例では、ＡＢＯ−ＴＤＦを実現するために、ＤＣＲ（decisional composite residuosity）問題を利用する。
【００６３】
［公開装置１３００］
公開装置１３００は、信頼できる第三者等が管理し、通信部３０１、記憶部３０３、制御部３０５、乱数生成部１３１０、共通参照情報１３２０を有する。
【００６４】
＜乱数生成部１３１０＞
乱数生成部１３１０は、乱数ｒ∈Ｚ＊Ｎを生成し、共通参照情報生成部１３２０へ出力する。Ｎについては、後述する。
【００６５】
＜共通参照情報生成部１３２０＞
共通参照情報生成部１３２０は、ＡＢＯ−ＴＤＦの関数インデックスｓを含む共通参照情報ｃｒｓを生成する。例えば、ＲＳＡモジュラスＮ＝ｐｑ、ｇｃｄ（Ｎ，φ（Ｎ））＝１を満たす奇素数ｐ，ｑを選択し、Ｎを生成する。ｆを１以上の整数とし、ＡＢＯ−ＴＤＦの損失枝をＬｂとし、乱数ｒ∈Ｚ＊Ｎを用いて、関数インデックスｓ＝（１＋Ｎ）−Ｌｂｒ＾Ｎｆを生成する。実施例１と同様の理由により、Ｌｂ＝０とすると、ｓ＝ｒ＾Ｎｆとなる。また、ｐ，ｑを用いて、落とし戸情報τ＝ｌｃｍ（ｐ−１，ｑ−１）を生成する。さらに、関数インデックスｓ、Ｎ及びｆを含む共通参照情報ｃｒｓを生成する。なお、このようなＮに対して、乗法群Ｚ＊Ｎ＾ｆ＋１は直積Ｇ×Ｈである。但し、Ｇは位数Ｎｆの巡回群、ＨはＺ＊Ｎと同型である。なお、ｍ∈Ｚ＊Ｎ^fとする。また、奇素数ｐ，ｑは秘密に管理する。
【００６６】
［送信装置１１００］
送信装置１１００は、通信部１０１、記憶部１０３、制御部１０５、乱数生成部１１１０、鍵生成部１２０、署名生成部１１３０、コミットメント生成部１５０及び開封情報生成部１６０とを有する。
【００６７】
＜乱数生成部１１０＞
乱数生成部１１１０は、乱数ｒａ及びｒｂを生成する。但し、ｒｂ∈Ｚ＊Ｎとする。
【００６８】
＜署名生成部１１３０＞
まず、共通参照情報ｃｒｓに含まれる関数インデックスｓ、検証鍵ｖｋ及び乱数ｒａから、落とし戸付一方向性関数ＡＢＯ−ＴＤＦを用いて、ｃ０を求める。落とし戸付一方向性関数ＡＢＯ−ＴＤＦを用いるとは、一方向性関数アルゴリズムＧａｂｏによってｃ０を求めることを意味する。
ｃ０＝Ｇａｂｏ（ｓ，ｖｋ，ｒａ）
例えば、Ｇａｂｏは以下の式によって実現される。
ｃ０＝ｙ＝（ｓ◆ｖｋ）ｒａ
ここで、演算子◆は、暗号アルゴリズムＥｎｃが、
ｃ＝ＥｎｃＮ（ｍ；ｒ）＝（１＋Ｎ）ｍｒ＾Ｎｆ ｍｏｄ Ｎｆ＋１
のとき
c◆v=c・(1+N)v=EncN(m;r)・EncN(v;1)=EncN(m+v,r)
と定義される。よって、
ｙ＝（ｓ◆ｖｋ）ｒａ＝ＥｎｃＮ（ｖｋ・ｒａ；ｒ）
と表される。なお、ＥｎｃＮ（ｍ；ｒ）＝（１＋Ｎ）ｍｒ＾Ｎｆｍｏｄ Ｎｆ＋１より、ＥｎｃＮ（ｍ１；ｒ１）・ＥｎｃＮ（ｍ２；ｒ２）＝ＥｎｃＮ（ｍ１＋ｍ２；ｒ１・ｒ２）となり、ＥｎｃＮ（ｍ；ｒ）ｘ＝ＥｎｃＮ（ｍｘ；ｒｘ）となる。
【００６９】
次に、乱数ｒｂを用い、関数インデックスｓの準同型性を利用して、ｃ０のランダム化を行いｃ１を生成する。例えば、以下の式により、ランダム化を行う。
ｃ１＝ｙ’＝（ｓ◆ｖｋ）ｒａ◇ｒｂ
但し、演算子◇は、
c◇rb=c・rb^Nf=EncN(m;r)・EncN(0;rb)= EncN(m;r・rb)
と定義される。
よって、ｃ１＝ＥｎｃＮ（（ｖｋ−０）ｒａ；ｒｒａ・ｒｂ）を生成する。
ｃ２及び署名σの生成方法は実施例１の署名生成部１３０と同様である。
【００７０】
［受信装置１２００］
受信装置１２００は、通信部２０１、記憶部２０３、制御部２０５、署名検証部２３０及びコミットメント検証部１２５０を有する。
【００７１】
＜コミットメント検証部１２５０＞
コミットメント検証部１２５０は、共通参照情報ｃｒｓ及び開封情報Ｍを用いてコミットメントｃｏｍを検証する。共通参照情報ｃｒｓ及び開封情報Ｍを入力され、コミットメントｃｏｍの検証結果を出力する。コミットメントが検証を通過しなかった場合には、例えば、エラーを出力する。コミットメント検証部２５０は、署名σが検証を通過し、かつ、公開装置３００から共通参照情報ｃｒｓを受信し、かつ、開封情報Ｍを受信した場合に、コミットメントを検証することができる。
【００７２】
共通参照情報ｃｒｓに含まれる関数インデックスｓとコミットメントｃｏｍに含まれるｖｋと開封情報Ｍに含まれるｒａ，ｒｂから、
（ｓ◆ｖｋ）ｒａ◇ｒｂ
を計算し、得られる値がコミットメントｃｏｍに含まれるｃ１と同一であるか検証する。
【００７３】
また、共通参照情報ｃｒｓに含まれるハッシュ関数ｈ（）とコミットメントｃｏｍに含まれるｃ２から
【００７４】
【数８】
を計算し、得られる値が開封情報Ｍに含まれる情報ｍと同一であるか検証する。何れか一方の検証を通過しなかった場合には、エラーを出力する。
【００７５】
このような構成とすることで、実施例１と同様に、非対話方式、かつ、複数ビットコミットメント方式のビットコミットメントシステムを提供することができる。また、電子署名方式が選択文書攻撃に対し強存在的偽造不可かつdecisional composite residuosity仮定が真であれば、汎用的結合可能安全である。
【符号の説明】
【００７６】
１ ビットコミットメントシステム
１００ 送信装置
２００ 受信装置
３００ 公開装置
１０１、２０１、３０１ 通信部
１０３、２０３、３０３ 記憶部
１０５、２０５、３０５ 制御部
１１０、３１０ 乱数生成部
１２０ 鍵生成部
１３０ 署名生成部
１５０ コミットメント生成部
１６０ 開封情報生成部
２３０ 署名検証部
２５０ コミットメント検証部
３２０ 共通参照情報生成部
【特許請求の範囲】
【請求項１】
１ビット以上の情報ｍをコミットする送信装置とコミットメントを検証する受信装置と信用できる第三者が管理する公開装置からなるビットコミットメントシステムであって、
前記公開装置は、
Ａｌｌ−Ｂｕｔ−Ｏｎｅ落とし戸付一方向性関数（以下、「ＡＢＯ−ＴＤＦ」という）の関数インデックスｓを含む共通参照情報ｃｒｓを生成、公開し、
前記送信装置は、
検証鍵ｖｋを損失枝として、前記関数インデックスｓ及び乱数ｒａから、ＡＢＯ−ＴＤＦを用いて、ｃ０を求め、乱数ｒｂを用いて、前記ｃ０のランダム化を行い、ｃ１を生成し、前記乱数ｒａ及び前記情報ｍからｃ２を求め、前記ｃ１及びｃ２から、署名鍵ｓｋを用いて、署名σを生成する署名生成部と、
前記ｃ１、ｃ２及びσを含むコミットメントｃｏｍを生成するコミットメント生成部と、
前記情報ｍ、乱数ｒａ、ｒｂを含む開封情報Ｍを生成する開封情報生成部とを備え、
前記受信装置は、
前記検証鍵ｖｋを用いて、署名σを検証する署名検証部と、
前記共通参照情報ｃｒｓ及び開封情報Ｍを用いてコミットメントｃｏｍを検証するコミットメント検証部とを備える、
ことを特徴とするビットコミットメントシステム。
【請求項２】
請求項１記載のビットコミットメントシステムであって、
ｐを素数とし、位数ｐの巡回群をＧ、Ｇの生成元をｇ、ｉ，ｊ∈［ｎ］、［ｎ］＝｛１，２，…，ｎ｝、ｒ＝（ｒ１，…ｒｉ…，ｒｎ）、ｒ∈Ｚｐは乱数、ｒａ∈Ｚｐ、ｒａ＝（ｒａ１，…，ｒａｎ）、ｒａｊ∈｛０，１｝、ｒｂ＝（ｒｂ１，…，ｒｂｎ）、ｒｂ∈Ｚｐは乱数、Ｉは単位行列とし、
前記公開装置は、
ｔｊ＝ｇ＾ｚｊであり、Ｌｂを損失枝として、ｃｉ，ｊ＝（ｇｒｉ，ｔｊｒｉｇＬｂ）とし、関数インデックスｓを行列（ｃｉ，ｊ）として生成し、ＡＢＯ−ＴＤＦの落とし戸情報ｚｊ∈Ｚｐを生成し、ＡＢＯ−ＴＤＦの関数インデックスｓ及ｔびを含む共通参照情報ｃｒｓを生成、公開し、
前記送信装置の署名生成部は、
ｃ＝（ｃ１，ｃ２）＝（ｇｒ，ｔｒｇｍ）のとき、演算子★を、ｃ★ｖ＝（ｃ１，ｃ２・ｇｖ）と定義し、演算子☆を、ｃ☆ｒｂ＝（ｃ１・ｇｒｂ，ｃ２・ｔｒｂ）と定義して、
前記ｃ０＝ｒａ（s★ｖｋ・Ｉ）としてを生成し、
前記乱数ｒｂを用いて、前記ｃ０のランダム化を行い、前記ｃ１＝ｒａ（s★ｖｋ・Ｉ）☆ｒｂとして、生成し、
前記受信装置のコミットメント検証部は、
ｒａ（ｓ★ｖｋ・Ｉ）☆ｒｂを計算し、得られた値と前記ｃ１の値が同一か検証を行うこと、
を特徴とするビットコミットメントシステム。
【請求項３】
請求項１記載のビットコミットメントシステムであって、
前記公開装置は、
Ｎ＝ｐｑ、ｇｃｄ（Ｎ，φ（Ｎ））＝１を満たす奇素数ｐ，ｑを選択し、１以上の整数ｆを選択し、乱数ｒ∈Ｚ＊Ｎを生成し、ＡＢＯ−ＴＤＦの損失枝をＬｂとし、関数インデックスｓ＝（１＋Ｎ）−Ｌｂｒ＾Ｎｆ及び落とし戸情報τ＝ｌｃｍ（ｐ−１，ｑ−１）を生成し、関数インデックスｓ、Ｎ及びｆを含む共通参照情報ｃｒｓを生成、公開し、
前記送信装置の署名生成部は、
ｃ＝（１＋Ｎ）ｍｒ＾Ｎｆのとき、演算子◆をｃ◆ｖ＝ｃ・（１＋Ｎ）ｖと定義し、演算子◇をｃ◇ｒｂ＝ｃ・ｒｂ＾Ｎｆと定義して、前記ｃ０＝（ｓ◆ｖｋ）ｒａとして生成し、前記乱数ｒｂ∈Ｚ＊Ｎを用いて、前記ｃ０のランダム化を行い、ｃ１＝（ｓ◆ｖｋ）ｒａ◇ｒｂ
として生成し、
前記受信装置の署名検証部は、
（ｓ◆ｖｋ）ｒａ◇ｒｂを計算し、得られた値と前記ｃ１の値が同一か検証を行うこと、
を特徴とするビットコミットメントシステム。
【請求項４】
検証鍵ｖｋをＡｌｌ−Ｂｕｔ−Ｏｎｅ落とし戸付一方向性関数（以下、「ＡＢＯ−ＴＤＦ」という）の損失枝として、ＡＢＯ−ＴＤＦの関数インデックスｓ及び乱数ｒａから、ＡＢＯ−ＴＤＦを用いて、ｃ０を求め、乱数ｒｂを用いて、前記ｃ０のランダム化を行い、ｃ１を生成し、前記乱数ｒａ及び１ビット以上の情報ｍからｃ２を求め、前記ｃ１及びｃ２から、署名鍵ｓｋを用いて、署名σを生成する署名生成部と、
前記ｃ１、ｃ２及びσを含むコミットメントｃｏｍを生成するコミットメント生成部と、
前記情報ｍ、乱数ｒａ、ｒｂを含む開封情報Ｍを生成する開封情報生成部と、
を有するビットコミットメント送信装置。
【請求項５】
請求項４記載のビットコミットメント送信装置であって、
ｐを素数とし、位数ｐの巡回群をＧ、Ｇの生成元をｇ、ｉ，ｊ∈［ｎ］、［ｎ］＝｛１，２，…，ｎ｝、ｒ＝（ｒ１，…ｒｉ…，ｒｎ）、ｒ∈Ｚｐは乱数、ｒａ∈Ｚｐ、ｒａ＝（ｒａ１，…，ｒａｎ）、ｒａｊ∈｛０，１｝、ｒｂ＝（ｒｂ１，…，ｒｂｎ）、ｒｂ∈Ｚｐは乱数、Ｉは単位行列とし、
署名生成部は、ｃ＝（ｃ１，ｃ２）＝（ｇｒ，ｔｒｇｍ）のとき、演算子★を、ｃ★ｖ＝（ｃ１，ｃ２・ｇｖ）と定義し、演算子☆を、ｃ☆ｒｂ＝（ｃ１・ｇｒｂ，ｃ２・ｔｒｂ）と定義して、前記ｃ０＝ｒａ（s★ｖｋ・Ｉ）としてを生成し、前記乱数ｒｂを用いて、前記ｃ０のランダム化を行い、前記ｃ１＝ｒａ（s★ｖｋ・Ｉ）☆ｒｂとして、生成すること、
を特徴とするビットコミットメント送信装置。
【請求項６】
請求項４記載のビットコミットメント送信装置であって、
ｐ，ｑを奇素数、Ｎ＝ｐｑ、ｇｃｄ（Ｎ，φ（Ｎ））＝１、乱数ｒ∈Ｚ＊Ｎとし、
前記署名生成部は、
ｃ＝（１＋Ｎ）ｍｒ＾Ｎｆのとき、演算子◆をｃ◆ｖ＝ｃ・（１＋Ｎ）ｖと定義し、演算子◇をｃ◇ｒｂ＝ｃ・ｒｂ＾Ｎｆと定義して、前記ｃ０＝（ｓ◆ｖｋ）ｒａとして生成し、前記乱数ｒｂ∈Ｚ＊Ｎを用いて、前記ｃ０のランダム化を行い、前記ｃ１＝（ｓ◆ｖｋ）ｒａ◇ｒｂとして生成すること、
を特徴とするビットコミットメント送信装置。
【請求項７】
検証鍵ｖｋを損失枝として、Ａｌｌ−Ｂｕｔ−Ｏｎｅ落とし戸付一方向性関数（以下、「ＡＢＯ−ＴＤＦ」という）の関数インデックスｓ及び乱数ｒａから、ＡＢＯ−ＴＤＦを用いて、ｃ０を求め、乱数ｒｂを用いて、前記ｃ０のランダム化を行い、ｃ１を生成し、前記乱数ｒａ及び前記情報ｍからｃ２を求め、前記ｃ１及びｃ２から、署名鍵ｓｋを用いて、生成された署名σを、検証鍵ｖｋを用いて、検証する署名検証部と、
ＡＢＯ−ＴＤＦの関数インデックスｓを含む共通参照情報ｃｒｓ及び乱数ｒａ、ｒｂを含む開封情報Ｍを用いてコミットメントｃｏｍを検証するコミットメント検証部とを備える、
ことを特徴とするビットコミットメント受信装置。
【請求項８】
請求項７記載のビットコミットメント受信装置であって、
ｐを素数、位数ｐの巡回群をＧ、Ｇの生成元をｇ、ｉ，ｊ∈［ｎ］、［ｎ］＝｛１，２，…，ｎ｝、ｒ＝（ｒ１，…ｒｉ…，ｒｎ）、ｒ∈Ｚｐは乱数、ｒａ∈Ｚｐ、ｒａ＝（ｒａ１，…，ｒａｎ）、ｒａｊ∈｛０，１｝、ｒｂ＝（ｒｂ１，…，ｒｂｎ）、ｒｂ∈Ｚｐは乱数、Ｉは単位行列、ｔｊ＝ｇ＾ｚｊ、Ｌｂを損失枝、ｃｉ，ｊ＝（ｇｒｉ，ｔｊｒｉｇＬｂ）、関数インデックスｓを行列（ｃｉ，ｊ）とし、ｃ＝（ｃ１，ｃ２）＝（ｇｒ，ｔｒｇｍ）のとき、演算子★を、ｃ★ｖ＝（ｃ１，ｃ２・ｇｖ）と定義し、演算子☆を、ｃ☆ｒｂ＝（ｃ１・ｇｒｂ，ｃ２・ｔｒｂ）と定義して、前記ｃ１＝ｒａ（s★ｖｋ・Ｉ）☆ｒｂとして、
前記コミットメント検証部は、
ｒａ（ｓ★ｖｋ・Ｉ）☆ｒｂを計算し、得られた値と前記ｃ１の値が同一か検証を行うこと、
を特徴とするビットコミットメント受信装置。
【請求項９】
請求項７記載のビットコミットメント受信装置であって、
ｐ，ｑは奇素数、Ｎ＝ｐｑ、ｇｃｄ（Ｎ，φ（Ｎ））＝１を満たし、ｃ＝（１＋Ｎ）ｍｒ＾Ｎｆのとき、演算子◆をｃ◆ｖ＝ｃ・（１＋Ｎ）ｖと定義し、演算子◇をｃ◇ｒｂ＝ｃ・ｒｂ＾Ｎｆと定義して、ｒｂ∈Ｚ＊Ｎ、前記ｃ１＝（ｓ◆ｖｋ）ｒａ◇ｒｂとして、
前記受信装置の署名検証部は、
（ｓ◆ｖｋ）ｒａ◇ｒｂを計算し、得られた値と前記ｃ１の値が同一か検証を行うこと、
を特徴とするビットコミットメント受信装置。
【請求項１０】
１ビット以上の情報ｍをコミットする送信装置とコミットメントを検証する受信装置と信用できる第三者が管理する公開装置を用いるビットコミットメント方法であって、
前記公開装置が、Ａｌｌ−Ｂｕｔ−Ｏｎｅ落とし戸付一方向性関数（以下、「ＡＢＯ−ＴＤＦ」という）の関数インデックスｓを含む共通参照情報ｃｒｓを生成、公開するステップと、
前記送信装置が、検証鍵ｖｋを損失枝として、前記関数インデックスｓ及び乱数ｒａから、ＡＢＯ−ＴＤＦを用いて、ｃ０を求め、乱数ｒｂを用いて、前記ｃ０のランダム化を行い、ｃ１を生成し、前記乱数ｒａ及び前記情報ｍからｃ２を求め、前記ｃ１及びｃ２から、署名鍵ｓｋを用いて、署名σを生成する署名生成ステップと、
前記送信装置が、前記ｃ１、ｃ２及びσを含むコミットメントｃｏｍを生成するコミットメント生成ステップと、
前記受信装置が、前記検証鍵ｖｋを用いて、署名σを検証する署名検証ステップと、
前記送信装置が、前記情報ｍ、乱数ｒａ、ｒｂを含む開封情報Ｍを生成する開封情報生成ステップと、
前記受信装置が、前記共通参照情報ｃｒｓ及び開封情報Ｍを用いてコミットメントｃｏｍを検証するコミットメント検証ステップとを備える、
ことを特徴とするビットコミットメント方法。
【請求項１１】
検証鍵ｖｋをＡｌｌ−Ｂｕｔ−Ｏｎｅ落とし戸付一方向性関数（以下、「ＡＢＯ−ＴＤＦ」という）の損失枝として、ＡＢＯ−ＴＤＦの関数インデックスｓ及び乱数ｒａから、ＡＢＯ−ＴＤＦを用いて、ｃ０を求めるステップと、
乱数ｒｂを用いて、前記ｃ０のランダム化を行い、ｃ１を生成するステップと、
前記乱数ｒａ及び１ビット以上の情報ｍからｃ２を求めるステップと、
前記ｃ１及びｃ２から、署名鍵ｓｋを用いて、署名σを生成する署名生成ステップと、
前記ｃ１、ｃ２及びσを含むコミットメントｃｏｍを生成するコミットメント生成ステップと、
前記情報ｍ、乱数ｒａ、ｒｂを含む開封情報Ｍを生成する開封情報生成ステップと、
を有するビットコミットメント送信方法。
【請求項１２】
検証鍵ｖｋを損失枝として、Ａｌｌ−Ｂｕｔ−Ｏｎｅ落とし戸付一方向性関数（以下、「ＡＢＯ−ＴＤＦ」という）の関数インデックスｓ及び乱数ｒａから、ＡＢＯ−ＴＤＦを用いて、ｃ０を求め、乱数ｒｂを用いて、前記ｃ０のランダム化を行い、ｃ１を生成し、前記乱数ｒａ及び前記情報ｍからｃ２を求め、前記ｃ１及びｃ２から、署名鍵ｓｋを用いて、生成された署名σを、検証鍵ｖｋを用いて、検証する署名検証ステップと、
ＡＢＯ−ＴＤＦの関数インデックスｓを含む共通参照情報ｃｒｓ及び乱数ｒａ、ｒｂを含む開封情報Ｍを用いてコミットメントｃｏｍを検証するコミットメント検証ステップとを備える、
ことを特徴とするビットコミットメント受信方法。
【請求項１３】
請求項４から９記載の何れかのビットコミットメント送信装置、または、ビットコミットメント受信装置として、コンピュータを機能させるためのビットコミットメントプログラム。
【請求項１】
１ビット以上の情報ｍをコミットする送信装置とコミットメントを検証する受信装置と信用できる第三者が管理する公開装置からなるビットコミットメントシステムであって、
前記公開装置は、
Ａｌｌ−Ｂｕｔ−Ｏｎｅ落とし戸付一方向性関数（以下、「ＡＢＯ−ＴＤＦ」という）の関数インデックスｓを含む共通参照情報ｃｒｓを生成、公開し、
前記送信装置は、
検証鍵ｖｋを損失枝として、前記関数インデックスｓ及び乱数ｒａから、ＡＢＯ−ＴＤＦを用いて、ｃ０を求め、乱数ｒｂを用いて、前記ｃ０のランダム化を行い、ｃ１を生成し、前記乱数ｒａ及び前記情報ｍからｃ２を求め、前記ｃ１及びｃ２から、署名鍵ｓｋを用いて、署名σを生成する署名生成部と、
前記ｃ１、ｃ２及びσを含むコミットメントｃｏｍを生成するコミットメント生成部と、
前記情報ｍ、乱数ｒａ、ｒｂを含む開封情報Ｍを生成する開封情報生成部とを備え、
前記受信装置は、
前記検証鍵ｖｋを用いて、署名σを検証する署名検証部と、
前記共通参照情報ｃｒｓ及び開封情報Ｍを用いてコミットメントｃｏｍを検証するコミットメント検証部とを備える、
ことを特徴とするビットコミットメントシステム。
【請求項２】
請求項１記載のビットコミットメントシステムであって、
ｐを素数とし、位数ｐの巡回群をＧ、Ｇの生成元をｇ、ｉ，ｊ∈［ｎ］、［ｎ］＝｛１，２，…，ｎ｝、ｒ＝（ｒ１，…ｒｉ…，ｒｎ）、ｒ∈Ｚｐは乱数、ｒａ∈Ｚｐ、ｒａ＝（ｒａ１，…，ｒａｎ）、ｒａｊ∈｛０，１｝、ｒｂ＝（ｒｂ１，…，ｒｂｎ）、ｒｂ∈Ｚｐは乱数、Ｉは単位行列とし、
前記公開装置は、
ｔｊ＝ｇ＾ｚｊであり、Ｌｂを損失枝として、ｃｉ，ｊ＝（ｇｒｉ，ｔｊｒｉｇＬｂ）とし、関数インデックスｓを行列（ｃｉ，ｊ）として生成し、ＡＢＯ−ＴＤＦの落とし戸情報ｚｊ∈Ｚｐを生成し、ＡＢＯ−ＴＤＦの関数インデックスｓ及ｔびを含む共通参照情報ｃｒｓを生成、公開し、
前記送信装置の署名生成部は、
ｃ＝（ｃ１，ｃ２）＝（ｇｒ，ｔｒｇｍ）のとき、演算子★を、ｃ★ｖ＝（ｃ１，ｃ２・ｇｖ）と定義し、演算子☆を、ｃ☆ｒｂ＝（ｃ１・ｇｒｂ，ｃ２・ｔｒｂ）と定義して、
前記ｃ０＝ｒａ（s★ｖｋ・Ｉ）としてを生成し、
前記乱数ｒｂを用いて、前記ｃ０のランダム化を行い、前記ｃ１＝ｒａ（s★ｖｋ・Ｉ）☆ｒｂとして、生成し、
前記受信装置のコミットメント検証部は、
ｒａ（ｓ★ｖｋ・Ｉ）☆ｒｂを計算し、得られた値と前記ｃ１の値が同一か検証を行うこと、
を特徴とするビットコミットメントシステム。
【請求項３】
請求項１記載のビットコミットメントシステムであって、
前記公開装置は、
Ｎ＝ｐｑ、ｇｃｄ（Ｎ，φ（Ｎ））＝１を満たす奇素数ｐ，ｑを選択し、１以上の整数ｆを選択し、乱数ｒ∈Ｚ＊Ｎを生成し、ＡＢＯ−ＴＤＦの損失枝をＬｂとし、関数インデックスｓ＝（１＋Ｎ）−Ｌｂｒ＾Ｎｆ及び落とし戸情報τ＝ｌｃｍ（ｐ−１，ｑ−１）を生成し、関数インデックスｓ、Ｎ及びｆを含む共通参照情報ｃｒｓを生成、公開し、
前記送信装置の署名生成部は、
ｃ＝（１＋Ｎ）ｍｒ＾Ｎｆのとき、演算子◆をｃ◆ｖ＝ｃ・（１＋Ｎ）ｖと定義し、演算子◇をｃ◇ｒｂ＝ｃ・ｒｂ＾Ｎｆと定義して、前記ｃ０＝（ｓ◆ｖｋ）ｒａとして生成し、前記乱数ｒｂ∈Ｚ＊Ｎを用いて、前記ｃ０のランダム化を行い、ｃ１＝（ｓ◆ｖｋ）ｒａ◇ｒｂ
として生成し、
前記受信装置の署名検証部は、
（ｓ◆ｖｋ）ｒａ◇ｒｂを計算し、得られた値と前記ｃ１の値が同一か検証を行うこと、
を特徴とするビットコミットメントシステム。
【請求項４】
検証鍵ｖｋをＡｌｌ−Ｂｕｔ−Ｏｎｅ落とし戸付一方向性関数（以下、「ＡＢＯ−ＴＤＦ」という）の損失枝として、ＡＢＯ−ＴＤＦの関数インデックスｓ及び乱数ｒａから、ＡＢＯ−ＴＤＦを用いて、ｃ０を求め、乱数ｒｂを用いて、前記ｃ０のランダム化を行い、ｃ１を生成し、前記乱数ｒａ及び１ビット以上の情報ｍからｃ２を求め、前記ｃ１及びｃ２から、署名鍵ｓｋを用いて、署名σを生成する署名生成部と、
前記ｃ１、ｃ２及びσを含むコミットメントｃｏｍを生成するコミットメント生成部と、
前記情報ｍ、乱数ｒａ、ｒｂを含む開封情報Ｍを生成する開封情報生成部と、
を有するビットコミットメント送信装置。
【請求項５】
請求項４記載のビットコミットメント送信装置であって、
ｐを素数とし、位数ｐの巡回群をＧ、Ｇの生成元をｇ、ｉ，ｊ∈［ｎ］、［ｎ］＝｛１，２，…，ｎ｝、ｒ＝（ｒ１，…ｒｉ…，ｒｎ）、ｒ∈Ｚｐは乱数、ｒａ∈Ｚｐ、ｒａ＝（ｒａ１，…，ｒａｎ）、ｒａｊ∈｛０，１｝、ｒｂ＝（ｒｂ１，…，ｒｂｎ）、ｒｂ∈Ｚｐは乱数、Ｉは単位行列とし、
署名生成部は、ｃ＝（ｃ１，ｃ２）＝（ｇｒ，ｔｒｇｍ）のとき、演算子★を、ｃ★ｖ＝（ｃ１，ｃ２・ｇｖ）と定義し、演算子☆を、ｃ☆ｒｂ＝（ｃ１・ｇｒｂ，ｃ２・ｔｒｂ）と定義して、前記ｃ０＝ｒａ（s★ｖｋ・Ｉ）としてを生成し、前記乱数ｒｂを用いて、前記ｃ０のランダム化を行い、前記ｃ１＝ｒａ（s★ｖｋ・Ｉ）☆ｒｂとして、生成すること、
を特徴とするビットコミットメント送信装置。
【請求項６】
請求項４記載のビットコミットメント送信装置であって、
ｐ，ｑを奇素数、Ｎ＝ｐｑ、ｇｃｄ（Ｎ，φ（Ｎ））＝１、乱数ｒ∈Ｚ＊Ｎとし、
前記署名生成部は、
ｃ＝（１＋Ｎ）ｍｒ＾Ｎｆのとき、演算子◆をｃ◆ｖ＝ｃ・（１＋Ｎ）ｖと定義し、演算子◇をｃ◇ｒｂ＝ｃ・ｒｂ＾Ｎｆと定義して、前記ｃ０＝（ｓ◆ｖｋ）ｒａとして生成し、前記乱数ｒｂ∈Ｚ＊Ｎを用いて、前記ｃ０のランダム化を行い、前記ｃ１＝（ｓ◆ｖｋ）ｒａ◇ｒｂとして生成すること、
を特徴とするビットコミットメント送信装置。
【請求項７】
検証鍵ｖｋを損失枝として、Ａｌｌ−Ｂｕｔ−Ｏｎｅ落とし戸付一方向性関数（以下、「ＡＢＯ−ＴＤＦ」という）の関数インデックスｓ及び乱数ｒａから、ＡＢＯ−ＴＤＦを用いて、ｃ０を求め、乱数ｒｂを用いて、前記ｃ０のランダム化を行い、ｃ１を生成し、前記乱数ｒａ及び前記情報ｍからｃ２を求め、前記ｃ１及びｃ２から、署名鍵ｓｋを用いて、生成された署名σを、検証鍵ｖｋを用いて、検証する署名検証部と、
ＡＢＯ−ＴＤＦの関数インデックスｓを含む共通参照情報ｃｒｓ及び乱数ｒａ、ｒｂを含む開封情報Ｍを用いてコミットメントｃｏｍを検証するコミットメント検証部とを備える、
ことを特徴とするビットコミットメント受信装置。
【請求項８】
請求項７記載のビットコミットメント受信装置であって、
ｐを素数、位数ｐの巡回群をＧ、Ｇの生成元をｇ、ｉ，ｊ∈［ｎ］、［ｎ］＝｛１，２，…，ｎ｝、ｒ＝（ｒ１，…ｒｉ…，ｒｎ）、ｒ∈Ｚｐは乱数、ｒａ∈Ｚｐ、ｒａ＝（ｒａ１，…，ｒａｎ）、ｒａｊ∈｛０，１｝、ｒｂ＝（ｒｂ１，…，ｒｂｎ）、ｒｂ∈Ｚｐは乱数、Ｉは単位行列、ｔｊ＝ｇ＾ｚｊ、Ｌｂを損失枝、ｃｉ，ｊ＝（ｇｒｉ，ｔｊｒｉｇＬｂ）、関数インデックスｓを行列（ｃｉ，ｊ）とし、ｃ＝（ｃ１，ｃ２）＝（ｇｒ，ｔｒｇｍ）のとき、演算子★を、ｃ★ｖ＝（ｃ１，ｃ２・ｇｖ）と定義し、演算子☆を、ｃ☆ｒｂ＝（ｃ１・ｇｒｂ，ｃ２・ｔｒｂ）と定義して、前記ｃ１＝ｒａ（s★ｖｋ・Ｉ）☆ｒｂとして、
前記コミットメント検証部は、
ｒａ（ｓ★ｖｋ・Ｉ）☆ｒｂを計算し、得られた値と前記ｃ１の値が同一か検証を行うこと、
を特徴とするビットコミットメント受信装置。
【請求項９】
請求項７記載のビットコミットメント受信装置であって、
ｐ，ｑは奇素数、Ｎ＝ｐｑ、ｇｃｄ（Ｎ，φ（Ｎ））＝１を満たし、ｃ＝（１＋Ｎ）ｍｒ＾Ｎｆのとき、演算子◆をｃ◆ｖ＝ｃ・（１＋Ｎ）ｖと定義し、演算子◇をｃ◇ｒｂ＝ｃ・ｒｂ＾Ｎｆと定義して、ｒｂ∈Ｚ＊Ｎ、前記ｃ１＝（ｓ◆ｖｋ）ｒａ◇ｒｂとして、
前記受信装置の署名検証部は、
（ｓ◆ｖｋ）ｒａ◇ｒｂを計算し、得られた値と前記ｃ１の値が同一か検証を行うこと、
を特徴とするビットコミットメント受信装置。
【請求項１０】
１ビット以上の情報ｍをコミットする送信装置とコミットメントを検証する受信装置と信用できる第三者が管理する公開装置を用いるビットコミットメント方法であって、
前記公開装置が、Ａｌｌ−Ｂｕｔ−Ｏｎｅ落とし戸付一方向性関数（以下、「ＡＢＯ−ＴＤＦ」という）の関数インデックスｓを含む共通参照情報ｃｒｓを生成、公開するステップと、
前記送信装置が、検証鍵ｖｋを損失枝として、前記関数インデックスｓ及び乱数ｒａから、ＡＢＯ−ＴＤＦを用いて、ｃ０を求め、乱数ｒｂを用いて、前記ｃ０のランダム化を行い、ｃ１を生成し、前記乱数ｒａ及び前記情報ｍからｃ２を求め、前記ｃ１及びｃ２から、署名鍵ｓｋを用いて、署名σを生成する署名生成ステップと、
前記送信装置が、前記ｃ１、ｃ２及びσを含むコミットメントｃｏｍを生成するコミットメント生成ステップと、
前記受信装置が、前記検証鍵ｖｋを用いて、署名σを検証する署名検証ステップと、
前記送信装置が、前記情報ｍ、乱数ｒａ、ｒｂを含む開封情報Ｍを生成する開封情報生成ステップと、
前記受信装置が、前記共通参照情報ｃｒｓ及び開封情報Ｍを用いてコミットメントｃｏｍを検証するコミットメント検証ステップとを備える、
ことを特徴とするビットコミットメント方法。
【請求項１１】
検証鍵ｖｋをＡｌｌ−Ｂｕｔ−Ｏｎｅ落とし戸付一方向性関数（以下、「ＡＢＯ−ＴＤＦ」という）の損失枝として、ＡＢＯ−ＴＤＦの関数インデックスｓ及び乱数ｒａから、ＡＢＯ−ＴＤＦを用いて、ｃ０を求めるステップと、
乱数ｒｂを用いて、前記ｃ０のランダム化を行い、ｃ１を生成するステップと、
前記乱数ｒａ及び１ビット以上の情報ｍからｃ２を求めるステップと、
前記ｃ１及びｃ２から、署名鍵ｓｋを用いて、署名σを生成する署名生成ステップと、
前記ｃ１、ｃ２及びσを含むコミットメントｃｏｍを生成するコミットメント生成ステップと、
前記情報ｍ、乱数ｒａ、ｒｂを含む開封情報Ｍを生成する開封情報生成ステップと、
を有するビットコミットメント送信方法。
【請求項１２】
検証鍵ｖｋを損失枝として、Ａｌｌ−Ｂｕｔ−Ｏｎｅ落とし戸付一方向性関数（以下、「ＡＢＯ−ＴＤＦ」という）の関数インデックスｓ及び乱数ｒａから、ＡＢＯ−ＴＤＦを用いて、ｃ０を求め、乱数ｒｂを用いて、前記ｃ０のランダム化を行い、ｃ１を生成し、前記乱数ｒａ及び前記情報ｍからｃ２を求め、前記ｃ１及びｃ２から、署名鍵ｓｋを用いて、生成された署名σを、検証鍵ｖｋを用いて、検証する署名検証ステップと、
ＡＢＯ−ＴＤＦの関数インデックスｓを含む共通参照情報ｃｒｓ及び乱数ｒａ、ｒｂを含む開封情報Ｍを用いてコミットメントｃｏｍを検証するコミットメント検証ステップとを備える、
ことを特徴とするビットコミットメント受信方法。
【請求項１３】
請求項４から９記載の何れかのビットコミットメント送信装置、または、ビットコミットメント受信装置として、コンピュータを機能させるためのビットコミットメントプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１０−１６４８７６（Ｐ２０１０−１６４８７６Ａ）
【公開日】平成２２年７月２９日（２０１０．７．２９）
【国際特許分類】
【出願番号】特願２００９−８４８２（Ｐ２００９−８４８２）
【出願日】平成２１年１月１９日（２００９．１．１９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２２年７月２９日（２０１０．７．２９）
【国際特許分類】
【出願日】平成２１年１月１９日（２００９．１．１９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]