ビットコミットメント
ビットコミットメント、コミットメント方式とは、暗号理論におけるプロトコルである。ビットコミットメントを用いることで、ユーザーは値を秘密裏にコミットすることができる。また、ユーザーは後にコミットされた値を明らかにすることが可能である。 コミットメント方式を想像するには以下の喩えが有効である。送信者は値を書いた紙を箱に入れカギを掛け、その箱を受信者に送る。箱の中身は受信者には見えないし、送信者が鍵を送らなければ錠前を開けることもできない。また受信者が箱を持っているので送信者が箱の中身を改ざんすることも不可能である。コミットメント方式は暗号プロトコルと密接な関係を持っている。とくにゼロ知識証明やマルチパーティ計算、また電子マネーや電子投票 に用いられている。
計算量的秘匿かつ完全拘束なビットコミットメント方式を一方向性関数によって構成できる。
任意の一方向性関数はGoldreich-Levinの定理により、簡単な変換によってハードコア述語を持つことが知られている。以下、簡単のため一方向性置換のみを扱う。fを一方向性置換、hをそのハードコア述語とする。Aliceはxとハードコア述語hをランダムに選ぶ。秘密のビットbを決定した後、3つ組
( h , f ( x ) , b ⊕ h ( x ) ) {\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の逆関数を求めるのと同程度に困難である)。