2者間で次のCOMMITフェーズとREVEALフェーズを実行するプロトコルを考える。
このとき、次のように定義する。
フェーズはCOMMITフェーズとREVEALフェーズの2つに分かれていて、次のような動作を行う。
[1]COMMITフェーズ
Piはcommitしたい値b（ここでは1ビットなのでcommit bitという）とランダム値rからcommitment情報c=Com(b;r)を作る。そしてこのcをPjへ送る。
[2]REVEALフェーズ
decommitment情報b,rをPjへ送る。Pjはc=Com(b;r)の検証式が成り立つかどうかをチェックして、成り立てばbを出力する。成り立たなければ何もしない（これを⊥で表す）。
この2つのフェーズを図にすると次のようになる。
以上のプロトコルをまとめると次のようになる。
commitment schemeで実現できるサービスは、COMMITフェーズでは相手にbを隠した状態で送っておき、選択したbをこれから使うことを約束する。その後、REVEALフェーズでCOMMITフェーズで使用した値を相手に開かすわけである。
もちろんcompleteness（完全性）を満たしていなければならない。即ちsenderがhonestにプロトコルを実行したら、receiverはacceptするということである（必ずacceptするならperfect completeness）。
さらに、このプロトコルは最終的にbを認識させるというサービス以外にも、満たさなければならない性質がある。ここで、p(n)は多項式関数とする（nは十分大きい）。commitment schemeであるためには、次の2つの性質を持たなければならないわけである。
この2つの性質を満たすために、Comの計算でどういった操作をするのかということは、各種commtiment schemeによって異なる。例えば、離散対数問題をベースにしたタイプのものであれば、c=gmhrのように計算してmとrを隠すことができる。さらにこの操作方法によって、hidingやbindingの強さ（information-theoretically*1/computationally）などが変わってくる。
commitment schemeではcommitしたい値（ビットあるいはストリング）を何らかの演算（上記ではComとした）を行ってから、相手に送信する。この演算で使う値はcommitしたい値とランダム値（プロトコルの実行のたびに新たに作る）である。この演算Comは一種の暗号化と見ることができる。暗号化する度にランダム値を使うので確率的暗号の暗号化アルゴリズムを使う。入力であるcommitしたい値が平文で相当し、出力結果であるcommitment情報が暗号文に相当する。これはもちろん暗号化されているので、内容を知ることはできない。ちょうどcommitmentのhidingの性質と対応している。
送信者は後ほどcommitしたい値と暗号化に使ったランダム値を受信者に送る。受信者はそれらの情報から暗号化アルゴリズムを通して、その結果が最初に受け取った情報と一致しているかどうかを検証する。送信者が後で別の値にオープンしたいとしても、相手にはすでにcommitment情報を送っているので、うまくつじつまは合わせられない。つまり、bindingを持つときと同じ状況になる。
commitment schemeは暗号プロトコルの中でも基本的なものであり、多くの場面で使われている。例えば次のようなプロトコルを構成するためのコンポーネントとして使われる。
オークションといってもたくさんの種類がある。ここでいう匿名オークションとは、一般的なネットオークションのようなタイプではなく、野球選手獲得のためのオークションに近い。ある決められた時間までに入札するとする。このとき入札値は決められた時間になるまで、オークション入札者同士やオークションを催すディーラー側にも秘密になっている。つまり、入札値を書いた紙を封筒に入れて封をして、ディーラー側に渡しているようなイメージである。決められた時間になると、入札値が開票され、一番高い値段を付けた人がその商品を落札することになる。
これはそのままcommitment schemeで実現できる。決められた時間こそがREVEALフェーズ開始時である。commitment shemeはhidingという性質を持つので、COMMITフェーズ内ではディーラーにも第三者の入札者にも入札値がわからない。またbindingという性質を持つので、入札者は別の入札者に誤魔化したり、上書きなどはできない。
現実世界でじゃんけんをするときは、「じゃんけん」という掛け声の後に、お互いが同時に手を出せばよい。電話機の場合は双方向の通信なので、「じゃんけん」という掛け声の後に、お互いが同時に手を言葉で伝えればよい。しかしながら、無線機の通信においては、双方向の通信ではない。通話するときにボタンを押して、押した側だけが一方通行で通話できるようになっている。つまり、会話のターンが交互に行われると考えられる。そういう場面においてじゃんけんをどのように実現したらよいだろうか。
実現方法のアイデアはいくつかあるだろうが、もっとも素朴なアイデアはcommitment schemeを使うという方法がある。Aliceはじゃんけんの手をcommitすることで、隠したままBobに送ることができる。hidingから、BobはAliceの手の内を知らない。よって、何の情報もなく自分の手を考えなければならない。Bobは自分の手をそのままAliceに送る。Aliceはその後、自分の手とそのときに使ったランダム値をBobに送信する。AliceはBobから手を送られたときに、自分が負けるような手をcommitしていたら、それを止めにして後出ししたい。しかし、これはcommtiment schemeの性質のbindingにより不可能である。よって、プロトコルが最後まで実行される限り、AliceもBobもいかさまができず、きちんとじゃんけんが実行されることになる。
ここでプロトコルが最後まで実行される限りと断った理由は、AliceがBobの手を受け取ったときに、自分が負けていたら、自分の手を送らない（一種のDoSアタック）という可能性がある。これは暗号とは別のレイヤーで解決するようにすればよい。例えば、Aliceから最後の返答が返ってこなければ、無条件でBobの勝ちというような仕組みを導入すれば解決する。
ブラインド署名＋匿名通信路＋commitment schemeで電子投票方式FOO92が構築できる。
commitment schemeに必須である性質はcompleteness,hiding,bindingだが、その他にもあると嬉しい性質がある。
本来の送信者Sと受信者Rの間に中間者攻撃（PITM attack：Person In The Middle attack）を行うアドバーサリーAが割り込む。AはSの発信したメッセージmに対応するコミットメントcを得たとする。このときAがmと関連のあるメッセージm'に対応する偽のコミットメント情報c'を作ることができないとき、（commitmentに関して）non-malleability（NM）を満たしているという。そして、REVEALフェーズでc'に対応するm'にオープンできないとき、（openingに関して）non-malleability（NM）を満たしているという。
[補講]公開鍵暗号系のnon-malleabilityでは、「暗号文から、その暗号文の平文に関する別の暗号文を作ることができない」という性質であった。これのcommitment schemeバージョンと考えばよい。
このとき単にコピーするのではなく、多項式時間で判定できるときリレーションR（⊆M×M）をinteresting relationと呼ぶ。ここでMはAによって選ばれる分布である。
NMをフォーマルに定義する前に少し記号の定義が必要である。
次に、シミュレータA'を考える。A'はsenderの助けなし（senderとの対話は与えられない）に、related messeageをcommitしようとする。ただし、A'はメッセージ長と公開パラメータは知ることができるとする。
このA'に関しての確率も、同様に定義される。
これで準備ができたので、NMを定義する。
[定義]
（1）「non-malleable with respect to commitment」
⇔def「」
（2）「non-malleable with respect to opening」
⇔def「」
Aはアドバーサリー、A'はシミュレータ、Rはinteresting relationである。
ここで、A'をrelaxさせたexpected poly-time simulator A'を定義する。
[定義]
「expected poly-time simulator A'」
⇔def「実行時間はまれにpoly-time内に終わらないが、平均実行時間はpoly-timeであるようなA'のこと」
このexpected poly-time simulator A'において、non-malleable with respect to commitment/openingが示されるなら、それぞれliberal non-malleable with respect to commitment/openingと呼ぶ。
trapdoorが与えられれば、hidingを効率的に破ることができる性質のことである。
trapdoorが与えられれば、bindingを効率的に破ることができる性質のことである。
senderがreceiverにcommitする値が1ビットであるようなcommitment schemeのこと。このときcommitする値のことをcommit bitという。
senderがreceiverにcommitする値が多ビット（＝string）であるようなcommitment schemeのこと。このときcommitする値のことをcommit stingという。
bit commitment schemeを単純に繰り返すことでstring commitment schemeを構築できるが、それでは効率が悪くなってしまう。そこで効率のよいstring commitment schemeの構築方法が課題となっている。
commitment schemeはhidingとbindingの強さによって大きく2つに分けることができる。
・PPT receiver、all-powerful senderに対して安全。
・PPT receiverは、COMMITフェーズにおいてsenderによってcommitされた値についての情報を何も知ることはできない。つまり、computationally hidingを持つ。
・そして、all-powerful senderはCOMMITフェーズでcommitした値とは別の値に、REVEALフェーズでオープンしようとしてもできない。つまり、information-theoretically bindingを持つ。
・all-powerful receiver、PPT senderに対して安全。
・all-powerful receiverは、COMMITフェーズにおいてsenderによってcommitされた値についての情報を何も知ることはできない。つまり、information-theoretically hidingを持つ。
・そして、PPTl senderはCOMMITフェーズでcommitした値とは別の値に、REVEALフェーズでオープンしようとしてもできない。つまり、computationally bindingを持つ。
・standard commitment schemeを作るより、perfect commitment schemeを作るほうが難しい。特にone-way permutationに基づくperfect commtiment schemeの作り方は知られているが、one-way functionに基づくようなperfect commitment schemeの作り方は未解決である。
証明システム（proof system）をmixしたcommitment schemeである。
hiding,binding,equivocality,extractabilityの4つの性質を持たせることができれば、UC commitment schemeが安全に実現できることが知られている[CF01]。
hiding,binding,equivocalityを持つcommitment schemeはtrapdoor commitment schemeとして存在する。しかし、同時にextractabilityを持たせることが一番問題となる。plainモデルではUC commitment schemeは存在しないことが証明されており、これを解決するには何らかのsetup assumptionを設けるか、UC安全性の定義をrelaxさせる方法が考案されている。
[定理]
information-theoretically hidingかつinformation-theoretically bindingであるcommitment schemeは存在しない。
[定理][GMW1]
「one-way permutationが存在する」
⇒「bit commitment schemeを作れる」
[定理]
「psedo-random generator（PRG）が存在する」
⇒「bit commitment schemeを作れる」
[定理][Yao]
「one-way permutationが存在する」
⇒「PRGが存在する」
[定理][ILL]
「one-way function（permutationである必要はない）が存在する」
⇒「non-uniform assumptionの下で、PRGが作れる」
[定理][H]
「one-way function（permutationである必要はない）が存在する」
⇒「uniform assumptionの下で、PRGが作れる」