ビットコミットメントのソースを表示

'''ビットコミットメント'''、'''コミットメント方式'''とは、[[暗号理論]]におけるプロトコルである。ビットコミットメントを用いることで、ユーザーは値を秘密裏にコミットすることができる。また、ユーザーは後にコミットされた値を明らかにすることが可能である。
コミットメント方式を想像するには以下の喩えが有効である。送信者は値を書いた紙を箱に入れカギを掛け、その箱を受信者に送る。箱の中身は受信者には見えないし、送信者が鍵を送らなければ錠前を開けることもできない。また受信者が箱を持っているので送信者が箱の中身を改ざんすることも不可能である。コミットメント方式は[[暗号プロトコル]]と密接な関係を持っている。とくに[[ゼロ知識証明]]や[[マルチパーティ計算]]、また[[電子マネー]]や[[電子投票]] に用いられている。

== 歴史 ==
ビットコミットメント方式の概念は1988年にGilles Brassrd, David Chaum, Claude Crepeauによって定式化された<ref name="BCC">Giles Brassard, David Chaum, and Claude Crepeau, ''[http://crypto.cs.mcgill.ca/~crepeau/PDF/BCC88-jcss.pdf Minimum Disclosure Proofs of Knowledge]'', Journal of Computer and System Sciences, vol. 37, pp. 156-189, 1988.</ref>。定式化の前に1987年にOded Goldreich, Silvio Micali, Avi Wigdersonの任意のNP言語がゼロ知識証明を持つ証明に使われていることが<ref name="Naor" />によって指摘されている。

== 応用 ==
この手法が必要となる例として安全なコイン投げが挙げられる。
2人のプレイヤAliceとBobは相反する目的を持っているとする。2人はその決着を[[コイントス]]で付けたい。
両者が物理的に同じ場所に居るのであれば以下のようにすればよい。
(1) Bobは"表"か"裏"かを宣言する。
(2) Aliceがコインを投げ、AliceとBobの両方がその結果（コインの裏表）を見て、その結果に決着を委ねる。

例を修正して、2人が電話で決着を付けようとしている場合を考える。この場合、Bobはコインの表裏を確かめられない。従って、Aliceは正直に裏表を言う必要はなく、自分に有利になるようにBobに表裏を伝えることができる。

コミットメント方式を用いる場合、以下のようにコイン投げを行う。
(1) Bobはコインの"表"か"裏"を選び、その値をコミットする。コミットメントをAliceに伝える。(2) Aliceはコインを投げ、結果をBobに伝える。(3) Bobはコミットした値をAliceに伝える。(4) Bobの値とAliceの値が一致している場合Bobの勝ちとする。そうでない場合、Aliceの勝ちとする。
さてAliceがずるをして勝とうとした場合、(2)の段階でBobのコミットメントの中身を知る必要がある。同様にBobがずるをして勝とうとした場合、(3)の段階でコミットメントの中身を書き換える必要がある。これらの行為はコミットメントが''良い''ものであれば防げる。<ref name="Blum">Manuel Blum, ''[https://www.cs.cmu.edu/~mblum/research/pdf/coin/in4.html Coin Flipping by Telephone]'', Proceedings of [[CRYPTO]] 1981, pp. 11-15, 1981, reprinted in SIGACT News vol. 15, pp. 23-27, 1983.</ref><ref name="Naor">Moni Naor, ''[http://citeseer.ist.psu.edu/naor91bit.html Bit Commitment Using Pseudorandomness]'', Journal of Cryptology 4: 2 pp. 151-158, 1991.</ref>

== 用語/安全性 ==
コミットメント方式中で行われるメッセージのやり取りは二つの段階に分かれる。
''コミット・フェーズ''では、コミットされる値が選ばれコミットメントが作られる。
''公開フェーズ''ではコミットされた値が公開され検証される。

コミットメント方式では、二つの暗号学的な安全性が定義される。
* ''秘匿性''（''hiding property''または''concealing property''）: 受信者がコミットフェーズ終了時にコミットされた値の情報を知り得ないことを保証する。コミットメントの値がコミットされた値と完全に独立であるとき（すなわち、受信者が無限の能力を持っていたとしてもコミットされた値がわからない）完全秘匿といい、現実的な計算能力ではコミットされた値の識別ができない場合には計算量秘匿という。
* ''拘束性''（''binding property''） : 送信者が公開フェーズ時にコミットした値と違う値に公開できないことを保証する。送信者が無限の能力を持っていたとしても違う値に公開できない（受信者を欺けない）とき、完全拘束といい、現実的な計算能力を持つ送信者にはそれができない場合には計算量拘束という。

"ビット・コミットメント"方式はコミットされる値が1ビットであるコミットメント方式のことを言う。複数ビットをコミットするコミットメント方式を特に"ストリング・コミットメント"方式と呼ぶこともある。

== コミットメント方式の構成法 ==
コミットメント方式は完全秘匿または完全拘束のどちらかを満たすことが可能である。しかし、同時に満たすことはできない。

=== 一方向性関数によるビットコミットメント ===
計算量的秘匿かつ完全拘束なビットコミットメント方式を[[一方向性関数]]によって構成できる。

任意の一方向性関数はGoldreich-Levinの定理により、簡単な変換によって[[ハードコア述語]]を持つことが知られている。以下、簡単のため一方向性置換のみを扱う。''f''を一方向性置換、''h''をそのハードコア述語とする。Aliceは''x''とハードコア述語''h''をランダムに選ぶ。秘密のビット''b''を決定した後、3つ組
: <math>(h,f(x),b \oplus h(x))</math>
をBobに送る(<math>\oplus</math> はXORを表す)。Aliceが秘密を明かす時は、ただ''x''をBobに送るだけでよい。
この方式は秘匿性を持つ。Bobが''b''を知るためには''h(x)''を知る必要がある。しかし、''h''はハードコア述語であるから''f(x)''と''h''から''h(x)''を求めるのは困難である。(h(x)を1/2より大きい確率で求めることは''f''の逆関数を求めるのと同程度に困難である)。

=== 擬似乱数生成器に基づくビットコミットメント方式 ===
一方向性関数から一方向性置換を得る方法は知られていないため、この章ではビットコミットメント方式を構成するのに必要な暗号論的仮定を弱める。

1991年にMoni Naor<ref name="Naor" />によって[[擬似乱数#暗号論的擬似乱数|暗号論的擬似乱数]]を用いてビットコミットメント方式を構成する手法が示された。その構成法は以下の通りである。

''G''を''n''ビットの入力から''3n''ビットの乱数を出力する擬似乱数生成器とし、Aliceがあるビット''b''を秘密に持つとする。
* Bobはランダムに''3n''ビットのベクトル''R''を選んでAliceに送る。
* Aliceはランダムに''n''ビットのベクトル''Y''を選び、''3n''ビットの''G(Y)''を計算する。
* もし''b''=1であればAliceは''G(Y)''をBobに送り、そうでなければ(''b''=0ならば)<math>G(Y)\oplus R</math>をBobに送る。
秘密を明かすにはAliceが''Y''をBobに送れば、Bobは先ほど受け取ったのが''G(Y)''と<math>G(Y)\oplus R</math>のどちらだったかを確かめることができる。

この方式は情報理論的拘束性を持つ。すなわち、Aliceが無限の計算能力を持っていたとしても、2<sup>-''n''</sup>より高い確率で不正をすることはできない。また計算量的秘匿性も簡単な帰着によって得られる。もしBobがAliceが選んだのが0,1のどちらか当てられるとすれば、彼は擬似乱数生成器''G''の出力と真の乱数とを区別できるということである。これは擬似乱数生成器の定義に矛盾する。

=== 離散対数問題に基づいた完全秘匿かつ計算量的拘束な方式 ===
Aliceはある素数''p''を位数とする[[群(数学)|群]]とその生成元''g''を選ぶ。

Aliceは秘密の整数''x''を''{0,...,p-1}''からランダムに選び、''c''=''g''<sup>''x''</sup>を計算して''c''を公開する。[[離散対数問題]]より、''c''から''x''を計算することは計算量的に困難であるから、この仮定のもとではBobは''x''を計算できない。一方、Aliceも''g''<sup>''x' ''</sup>=''c''なる''x' '' <> ''x''を計算することはできないので、完全拘束性を持つ。

しかし、[[離散対数問題]]を解くことが出来る者であれば秘密の整数''x''を計算できるので、この方式は完全秘匿ではない（実際、この方式は秘匿性の定義におけるゲームの観点からすれば全く秘匿性を持たない。このゲームは、[[IND-CPA]]ゲームと同様に敵に2つのメッセージのうち、どちらがコミットされた値かを当てさせるゲームである。）

完全に秘匿なコミットメント方式の例は以下である。
素数位数''q''の群''G''と群の生成元''g''について合意があるものとする。アリスは秘密''m''を持っているとする。（''m''は''{1,...,q-1}''の要素）
* ボブは''{1,...,q-1}''からランダムに''y''を選び、''h''=''g''<sup>''y''</sup>を計算する。''h''をアリスに送る。
* アリスは乱数''r''を''{1,...,q-1}''から選び、''c''=''g''<sup>''m''</sup>''h''<sup>''r''</sup>を計算する。''c''をボブに送る。
* 公開フェーズではアリスは''(m,r)''をボブに送る。ボブは''c''=''g''<sup>''m''</sup>''h''<sup>''r''</sup>かどうかを確認する。

アリスが二通りの開け方が出来るならば、''(g,h)''から''y''が求められる。また、任意のコミットメント''c''と秘密''m''に対して''c''=''g''<sup>''m''</sup>''h''<sup>''r''</sup>となる''r''は一意に決まる。よって完全秘匿性が言える。

== 量子ビットコミットメント方式 ==
[[量子暗号理論]]の観点から、''完全秘匿かつ完全拘束''なビットコミットメント方式が実現できるか? という問題が提示された。量子固有の性質を用いて、量子鍵交換のように無条件安全性を満たすものが構成できるのではないかと考えられた。

1996年にDominic Mayersが不可能性を証明した (概要として<ref>Brassard, Crepeau, Mayers, Salvail: [https://arxiv.org/abs/quant-ph/9712023 A brief review on the impossibility of quantum bit commitment]</ref>を参照のこと)。無条件安全性を持つビットコミットメント方式は、以下の方式に帰着される。Aliceがコミットしたい値によって、コミットフェーズ後に系は二つの純粋状態の内どちらかの純粋状態にあるとする。もしこの方式が完全秘匿であるならば、この状態を[[シュミット分解]]によりもう一方の純粋状態に変えることが出来る。したがって、拘束性が敗れる。

Mayersの証明では、ある時点ではコミットフェーズが終わっていなければならない。この証明では、プロトコルがキャンセルされるかコミットされたビットが明らかになるまで連続的に情報が流れているような方式は考慮されていない。しかしこの場合にも、拘束性が成り立たないことが知られている<ref>A. Kent: [https://arxiv.org/abs/quant-ph/9906103 Secure classical Bit Commitment using Fixed Capacity Communication Channels]</ref>。

== 参考文献 ==
<div class="references-small">
<references />
</div>

== 外部リンク ==
* [http://xstructure.inr.ac.ru/x-bin/theme2.py?arxiv=quant-ph&level=1&index1=1432 Quantum bit commitment on arxiv.org]

{{DEFAULTSORT:ひつとこみつとめんと}}
[[Category:暗号技術]]