ビットコミットメント、コミットメント方式とは、暗号理論におけるプロトコルである。ビットコミットメントを用いることで、ユーザーは値を秘密裏にコミットすることができる。また、ユーザーは後にコミットされた値を明らかにすることが可能である。コミットメント方式を想像するには以下の喩えが有効である。送信者は値を書いた紙を箱に入れカギを掛け、その箱を受信者に送る。箱の中身は受信者には見えないし、送信者が鍵を送らなければ錠前を開けることもできない。また受信者が箱を持っているので送信者が箱の中身を改ざんすることも不可能である。コミットメント方式は暗号プロトコルと密接な関係を持っている。とくにゼロ知識証明やマルチパーティ計算、また電子マネーや電子投票 に用いられている。ビットコミットメント方式の概念は1988年にGilles Brassrd, David Chaum, Claude Crepeauによって定式化された。定式化の前に1987年にOded Goldreich, Silvio Micali, Avi Wigdersonの任意のNP言語がゼロ知識証明を持つ証明に使われていることがによって指摘されている。この手法が必要となる例として安全なコイン投げが挙げられる。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)の段階でコミットメントの中身を書き換える必要がある。これらの行為はコミットメントが"良い"ものであれば防げる。コミットメント方式中で行われるメッセージのやり取りは二つの段階に分かれる。"コミット・フェーズ"では、コミットされる値が選ばれコミットメントが作られる。"公開フェーズ"ではコミットされた値が公開され検証される。コミットメント方式では、二つの暗号学的な安全性が定義される。"ビット・コミットメント"方式はコミットされる値が1ビットであるコミットメント方式のことを言う。複数ビットをコミットするコミットメント方式を特に"ストリング・コミットメント"方式と呼ぶこともある。コミットメント方式は完全秘匿または完全拘束のどちらかを満たすことが可能である。しかし、同時に満たすことはできない。計算量的秘匿かつ完全拘束なビットコミットメント方式を一方向性関数によって構成できる。任意の一方向性関数はGoldreich-Levinの定理により、簡単な変換によってハードコア述語を持つことが知られている。以下、簡単のため一方向性置換のみを扱う。"f"を一方向性置換、"h"をそのハードコア述語とする。Aliceは"x"とハードコア述語"h"をランダムに選ぶ。秘密のビット"b"を決定した後、3つ組をBobに送る(formula_2 はXORを表す)。Aliceが秘密を明かす時は、ただ"x"をBobに送るだけでよい。この方式は秘匿性を持つ。Bobが"b"を知るためには"h(x)"を知る必要がある。しかし、"h"はハードコア述語であるから"f(x)"と"h"から"h(x)"を求めるのは困難である。(h(x)を1/2より大きい確率で求めることは"f"の逆関数を求めるのと同程度に困難である)。一方向性関数から一方向性置換を得る方法は知られていないため、この章ではビットコミットメント方式を構成するのに必要な暗号論的仮定を弱める。1991年にMoni Naorによって暗号論的擬似乱数を用いてビットコミットメント方式を構成する手法が示された。その構成法は以下の通りである。"G"を"n"ビットの入力から"3n"ビットの乱数を出力する擬似乱数生成器とし、Aliceがあるビット"b"を秘密に持つとする。秘密を明かすにはAliceが"Y"をBobに送れば、Bobは先ほど受け取ったのが"G(Y)"とformula_3のどちらだったかを確かめることができる。この方式は情報理論的拘束性を持つ。すなわち、Aliceが無限の計算能力を持っていたとしても、2より高い確率で不正をすることはできない。また計算量的秘匿性も簡単な帰着によって得られる。もしBobがAliceが選んだのが0,1のどちらか当てられるとすれば、彼は擬似乱数生成器"G"の出力と真の乱数とを区別できるということである。これは擬似乱数生成器の定義に矛盾する。Aliceはある素数"p"を位数とする群とその生成元"g"を選ぶ。Aliceは秘密の整数"x"を"{0...,p-1}"からランダムに選び、"c"="g"を計算して"c"を公開する。離散対数問題より、"c"から"x"を計算することは計算量的に困難であるから、この仮定のもとではBobは"x"を計算できない。一方、Aliceも"g"="c"なる"x' " <> "x"を計算することはできないので、完全拘束性を持つ。しかし、離散対数問題を解くことが出来る者であれば秘密の整数"x"を計算できるので、この方式は完全秘匿ではない（実際、この方式は秘匿性の定義におけるゲームの観点からすれば全く秘匿性を持たない。このゲームは、IND-CPAゲームと同様に敵に2つのメッセージのうち、どちらがコミットされた値かを当てさせるゲームである。）完全に秘匿なコミットメント方式の例は以下である。素数位数"q"の群"G"と群の生成元"g"について合意があるものとする。アリスは秘密"m"を持っているとする。（"m"は"{1...,q-1}"の要素）アリスが二通りの開け方が出来るならば、"(g,h)"から"y"が求められる。また、任意のコミットメント"c"と秘密"m"に対して"c"="g"h"となる"r"は一意に決まる。よって完全秘匿性が言える。量子暗号理論の観点から、"完全秘匿かつ完全拘束"なビットコミットメント方式が実現できるか? という問題が提示された。量子固有の性質を用いて、量子鍵交換のように無条件安全性を満たすものが構成できるのではないかと考えられた。1996年にDominic Mayersが不可能性を証明した (概要としてを参照のこと)。無条件安全性を持つビットコミットメント方式は、以下の方式に帰着される。Aliceがコミットしたい値によって、コミットフェーズ後に系は二つの純粋状態の内どちらかの純粋状態にあるとする。もしこの方式が完全秘匿であるならば、この状態をシュミット分解によりもう一方の純粋状態に変えることが出来る。したがって、拘束性が敗れる。Mayersの証明では、ある時点ではコミットフェーズが終わっていなければならない。この証明では、プロトコルがキャンセルされるかコミットされたビットが明らかになるまで連続的に情報が流れているような方式は考慮されていない。しかしこの場合にも、拘束性が成り立たないことが知られている。

出典:wikipedia