Pebble Coding

ソフトウェアエンジニアによるIT技術、数学の備忘録

コミットメントスキーム(=ビットコミットメント)

コミットメントスキームの概念を理解するために、まず、コイン投げプロトコルを考えます。

Alice,Bobの2人が同じ場所に居合わせ、Aliceがコインを投げ、Bobが表が出るか裏が出るかを当て、勝敗を決めるゲームを考えます。
このゲームの手順のことをプロトコルと言います。

コイン投げプロトコル

1) Aliceがコインを投げて手の中のコインの表,裏を確定させる。
表,裏どちらになっているかはAliceは知っているが、Bobには分からないものとする。
2) Bobが表,裏どちらかを推測し、宣言してAliceに伝える。
3) Aliceが手を開き、表,裏をBobに見せる。
Aliceの手の中の値とBobが宣言した値を比較し、同じならBobが勝利、異なればAliceが勝利となる。

1)でコインの表裏が確定した手のことをコミットメントといいます。
1),2)の手順のことをコミットメントフェーズと呼びます。
3)の手順のことをオープンフェーズと呼びます。

秘匿性 ( hiding property )

Bob が1)の時点で、表裏の情報の分からなさがどの程度かを秘匿性の度合いと言います。
例えば、BobがAliceの手のレントゲン写真を取れば、手の中の状態が分かりますから、その程度の秘匿性ということです。

束縛性 ( binding property )

Alice が3) で手を開く時に、ズルをして、1)で確定したコインの表,裏を異なるものとして
公開することがどの程度できないかの度合いを束縛性と言います。
Alice が実は高度なテクニックを持つマジシャンであれば、2) でBobがAliceに伝えたのと逆側をオープンすることができます。

離散対数問題(DLP)を用いてみる

さすがに、人の手を使うのは、秘匿性も束縛性も低すぎますから、精度を上げるために、離散対数問題という数学を用います。

ここ Commitment scheme - Wikipedia

のリンクの「A perfectly binding scheme based on the discrete log problem and beyond」 に書かれた方法を使ってみます。

離散対数問題では、解はただ一つしかありませんから束縛性は完全になります。
また、離散対数問題は計算量的に解くことが困難とされていますから、秘匿性は計算量的になります。

秘匿性が計算量的であれば、暗号として使うには強度として十分と言えます。

離散対数を用いた時のプロトコル

p, q を大きな素数とし、q|(p-1)であるとする。
gを Z_p^*の部分群の生成元とする。なおこの部分群の位数はqとする。
aを Z_qからランダムに選び秘密の値とする。
 h = {q}^{a} \mod pとする。
(p, q, g, h)を公開し、(a) を秘密とする。

メッセージ  m \in Z_q をコミットするため、送信者はランダムに r \in Z_qを選び、
コミットメント c = {g}^{m} {h}^{r} \mod pを受信者に送ります。
オープンフェーズとして、送信者はm,rを明らかにし、受信者は c = {g}^{m} {h}^{r} \mod pであることを確かめます。

何に使うのか?

仮想通貨のトランザクションの匿名化に用いられているようです。

Moneroで使われているので、詳しくはこの辺りを参照してください。

Monero日本語解説シリーズ\\ {\Large Monero Japanese Article Series - Overleaf

Pedersen Commitment | Moneropedia | Monero - secure, private, untraceable

個人的おすすめアルトコイン(8) - "Monero"(モネロ) - ニルスの暗号通貨日記

ZCASHの場合は、匿名化にzk-SNARK というプロトコルを用いているようです。

最近、さら改良された BulletProof というプロトコルが提案されています。 https://eprint.iacr.org/2017/1066.pdf

論文にBitcoinのコアメンバの名があります。