はじめに

コミットメントという暗号技術がソーシャルゲームなどで重要な役割をはたすことを、前回の記事で述べた。前回の記事ではコミットメントであればガチャに用いることができるということを述べたが、今回は前々回の記事で述べたハッシュ関数を用いたガチャからコミットメントを構成できることを述べる。また、離散対数を用いたコミットメントとハッシュ関数から構成したコミットメントの間には微妙な違いがあり、それがガチャシステムにどのように作用するのかということについても述べる。
この記事を読んで意見や疑問、改善点を見つけた場合はコメントなどで気軽に教えて欲しい。

続編を書きました

コミットメントによる公平なガチャシステムと電子署名

コミットメント

コミットメントは前回の記事であるように、次のような操作ができる暗号に機能を追加したようなものである。

コミット: 送信者はコミットしたい情報$b$を暗号化して受信者に送信する
公開: 送信者は受信者が$b$を復元できるように付加的な情報を受信者に送信する

そして、この二つの操作には次のようなことが言える。

コミットのステップでは、受信者はコミットされた値について何も分からない
送信者はコミットのステップ後に、コミットした値を変更することができない

このような特徴を持つコミットメントを構成する方法として、前回の記事では離散対数を用いた。

離散対数を用いたコミットメント

離散対数を用いたコミットメントは次のように構成する。今、アリスがボブに対してメッセージ$m \in \{0,1,\dots,q−1\}$をコミットメントしたいものとする。

ボブは次を満たす素数$p, q$と$\mathbb{Z}_p^{*}$¹から、集合の元の数が$q$となるような部分群$G$から生成元$g$と生成元$v \ne 1$をランダムに選び、$p, q, g, v$を$A$へ送信する
p := 2q + 1
アリスは次を検証する

$p, q$が共に素数であり、$p = 2q + 1$であること

$g, v$が$q$個の元を持つ集合の生成元であること

アリスは乱数$r \in \{0, 1, \dots, q - 1\}$を選ぶ

アリスはボブに$c := g^r v^m$を送信する

公開の際、アリスはボブに$r$と$m$を送信する

ボブは$c = g^r v^m$を検証する

このようにすることで、ボブは$c$から$m$を復元することはできないし、またアリスが$c$をコミットした後にそれを反故にすることも離散対数問題により困難であることが知られている。

ハッシュ関数を用いたコミットメント

さて、次にハッシュ関数を用いてどのようにコミットメントを構成するのかについて述べる。今、アリスがボブに対してメッセージ$m \in \{0,1,\dots,2^n - 1\}$をコミットメントしたいものとする²。

アリスとボブの間で、$n$ビットのハッシュ値を出力するハッシュ関数$H$について同意する
アリスは$n - |m|$ビットの長さを持つ乱数$r$を生成する³
アリスはボブに$c := H(m \mid\mid r)$を送信する⁴
公開の際、アリスはボブに$r$と$m$を送信する
ボブは$c = H(m \mid\mid r)$を検証する

このようにすることで、コミットメントを構成できる。

隠蔽と束縛

コミットメントには隠蔽と束縛という二つの性質がある。

隠蔽: コミットのステップでは、受信者はコミットされた値について何も分からない
束縛: 送信者はコミットのステップ後に、コミットした値を変更することができない

実はこの二つを同時に無条件で満すことは不可能である。これらの二つの性質を同時に満すコミットメント$C$を仮定する。$C$は二つの引数を取り、第一引数が$n$ビットからなる付加的な情報$r$で、第二引数が1ビットからなるコミットメント$b$であるとする。アリスがコミットメント$c = C(r, b)$をボブに送信するとき、$c = C(r', 1 - b)$を満すような$r'$が存在しなければならない。そうでなければ、ボブは無限の計算資源を用いて総当たりをするなどして$r$と$b$を特定することができる。ボブが$r$と$b$を特定できるということは、隠蔽の条件を破っているということになる。しかし、もしアリスも無限の計算資源を持っていれば、$c = C(r', 1 - b)$を見つけることができるので、$1 - b$をさもコミットメントしたかのように装うことができ、これは束縛の条件を破っているということになる。
このように、隠蔽と束縛を同時に満すようなコミットメントは存在しないことが言える。ただ、隠蔽と束縛のどちらかを完全に満し、片方は計算の複雑さに依存させることはできる。

離散対数を用いたコミットメントの隠蔽と束縛

まずは隠蔽について考える。$g$と$v$は$G$の生成元であることから、あるコミットメント$c$において、$m$に対する$r$が必ず存在する。つまりどのような$m$であったとしても、$c = g^r v^m$となるような$r$が必ず存在するので、離散対数を用いたコミットメントは完全な隠蔽を持つ。
一方で、このことからアリスが$m$でコミットした後で$m' \ne m$となる$m'$に変更される恐れがある。しかし、変更するためには前回の記事で紹介した離散対数問題を解かなければならず、このことから束縛に対しては計算の複雑さに依存している。

ハッシュ関数を用いたコミットの隠蔽と束縛

こちらもまず隠蔽を考える。$c = H(m \mid\mid r)$となっており、かつ$m$のビット長と$r$のビット長を足すと$n$になることから、こちらは総当たり的に$m$と対応する$r$を計算すればいずれは$m$に対応する$r$を見つけることができるので、完全な隠蔽はできない。一方で総当たり的に$m$と$r$を試行するのは、ハッシュ関数の長さがある程度長ければ困難であると言えることから、隠蔽については計算の複雑さに依存している。
ただ、逆にある$m$と$r$が完全に一つに定まることから、アリスは$m$をコミットした後で$m' \ne m$となる$m'$に変更することは不可能である。よって、ハッシュ関数を用いたコミットメントは完全な束縛を持つ。

ガチャシステムにおける隠蔽と束縛

さて、このようにコミットメントには二律背反な性質である隠蔽と束縛があり、離散対数を用いたコミットメントとハッシュ関数を用いたコミットメントではそれぞれ、どちらかが完全であるならどちらかは計算の複雑さに依存している。このことがガチャシステムにどう影響を与えるかについて考える。

隠蔽が計算量に依存している場合

隠蔽が計算量に依存しているので、ユーザーは時間や計算資源を投入すればコミットメントから元のメッセージを復元することができるので、たとえばガチャシステムでレアなアイテムが出るようにする可能性がある。すると、そのデータなどがオークションなどへ出品され、当然それは投入した計算資源を回収するような価格で売られることになる。つまり市場価格のようなものが生まれてしまう可能性がある。
一方で、束縛が完全であることから、アリス（つまりは送信者、ガチャシステムの運営）は絶対に不正ができないので、ユーザーに与える安心感は大きいと考えられる。

束縛が計算量に依存している場合

隠蔽の場合とは全く逆で、つまりユーザーはどれだけ時間や計算資源を投入したとしても、コミットメントからメッセージを復元することは不可能であるので、市場価格のようなものが生まれることは避けられる。
一方で束縛が計算の複雑さに依存しているので、運営が莫大な計算資源を用いて不正をしているのではないかという疑惑が生まれる可能性はある。

まとめ

このように、コミットメントには二つの同時に達成することが不可能な隠蔽と束縛という性質があり、どちらかは計算の複雑さに依存せざるを得ない。どちらを採用するかによって、ガチャシステムの性質を大きく決めることになるので、より議論が必要であると思われる。

$\mathbb{Z}_p^{*}$は何らかの$y$が存在して$x = y \bmod p$かつ$xz \equiv 1 \pmod{p}$を満たす逆元$z$が存在する$x$の集合を表す。 ↩
$n$は後述するハッシュ関数$H$の出力するハッシュ値の長さである。 ↩
$|m|$はメッセージ$m$のビット長を表す。 ↩
$\mid\mid$はビット列の連結を表す。 ↩

ガチャシステムとコミットメントにおける隠蔽と束縛