ビットコミットメントとは？わかりやすく解説

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

歴史

ビットコミットメント方式の概念は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つ組

(h,f(x),b\oplus h(x))

[1]

[2]

[3]

ビットコミットメントとは？ わかりやすく解説