ビットコミットメント

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

歴史

ビットコミットメント方式の概念は1988年にGilles Brassrd, David Chaum, Claude Crepeauによって定式化された^[1]。定式化の前に1987年にOded Goldreich, Silvio Micali, Avi Wigdersonの任意のNP言語がゼロ知識証明を持つ証明に使われていることが^[2]によって指摘されている。

応用

この手法が必要となる例として安全なコイン投げが挙げられる。 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)の段階でコミットメントの中身を書き換える必要がある。これらの行為はコミットメントが良いものであれば防げる。^[3][2]

用語/安全性

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

コミットメント方式では、二つの暗号学的な安全性が定義される。

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

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

コミットメント方式の構成法

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

一方向性関数によるビットコミットメント

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

任意の一方向性関数はGoldreich-Levinの定理により、簡単な変換によってハードコア述語を持つことが知られている。以下、簡単のため一方向性置換のみを扱う。fを一方向性置換、hをそのハードコア述語とする。Aliceはxとハードコア述語hをランダムに選ぶ。秘密のビットbを決定した後、3つ組

${\displaystyle (h,f(x),b\oplus h(x))}$

をBobに送る(${\displaystyle \oplus }$ はXORを表す)。Aliceが秘密を明かす時は、ただxをBobに送るだけでよい。 この方式は秘匿性を持つ。Bobがbを知るためにはh(x)を知る必要がある。しかし、hはハードコア述語であるからf(x)とhからh(x)を求めるのは困難である。(h(x)を1/2より大きい確率で求めることはfの逆関数を求めるのと同程度に困難である)。

擬似乱数生成器に基づくビットコミットメント方式

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

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

Gをnビットの入力から3nビットの乱数を出力する擬似乱数生成器とし、Aliceがあるビットbを秘密に持つとする。

• Bobはランダムに3nビットのベクトルRを選んでAliceに送る。
• AliceはランダムにnビットのベクトルYを選び、3nビットのG(Y)を計算する。
• もしb=1であればAliceはG(Y)をBobに送り、そうでなければ(b=0ならば)${\displaystyle G(Y)\oplus R}$をBobに送る。

秘密を明かすにはAliceがYをBobに送れば、Bobは先ほど受け取ったのがG(Y)と${\displaystyle G(Y)\oplus R}$のどちらだったかを確かめることができる。

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

離散対数問題に基づいた完全秘匿かつ計算量的拘束な方式

Aliceはある素数pを位数とする群とその生成元gを選ぶ。

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

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

完全に秘匿なコミットメント方式の例は以下である。 素数位数qの群Gと群の生成元gについて合意があるものとする。アリスは秘密mを持っているとする。（mは{1,...,q-1}の要素）

• ボブは{1,...,q-1}からランダムにyを選び、h=g^yを計算する。hをアリスに送る。
• アリスは乱数rを{1,...,q-1}から選び、c=g^mh^rを計算する。cをボブに送る。
• 公開フェーズではアリスは(m,r)をボブに送る。ボブはc=g^mh^rかどうかを確認する。

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

量子ビットコミットメント方式

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

1996年にDominic Mayersが不可能性を証明した (概要として^[4]を参照のこと)。無条件安全性を持つビットコミットメント方式は、以下の方式に帰着される。Aliceがコミットしたい値によって、コミットフェーズ後に系は二つの純粋状態の内どちらかの純粋状態にあるとする。もしこの方式が完全秘匿であるならば、この状態をシュミット分解によりもう一方の純粋状態に変えることが出来る。したがって、拘束性が敗れる。

Mayersの証明では、ある時点ではコミットフェーズが終わっていなければならない。この証明では、プロトコルがキャンセルされるかコミットされたビットが明らかになるまで連続的に情報が流れているような方式は考慮されていない。しかしこの場合にも、拘束性が成り立たないことが知られている^[5]。

参考文献

1. Giles Brassard, David Chaum, and Claude Crepeau, Minimum Disclosure Proofs of Knowledge, Journal of Computer and System Sciences, vol. 37, pp. 156-189, 1988.
2. ^ Moni Naor, Bit Commitment Using Pseudorandomness, Journal of Cryptology 4: 2 pp. 151-158, 1991.
3. Manuel Blum, Coin Flipping by Telephone, Proceedings of CRYPTO 1981, pp. 11-15, 1981, reprinted in SIGACT News vol. 15, pp. 23-27, 1983.
4. Brassard, Crepeau, Mayers, Salvail: A brief review on the impossibility of quantum bit commitment
5. A. Kent: Secure classical Bit Commitment using Fixed Capacity Communication Channels

外部リンク

• Quantum bit commitment on arxiv.org