はじめに

これまでの記事で、コミットメントという暗号技術を用いることでユーザーも運営も意図的な確率操作ができない公平なガチャシステムを構成できるということが分かった。この記事ではコミットメントを運営が反故にしたり、ユーザーが偽のコミットメントを受けとったかのように装うなどの悪意ある振る舞いを防止するために、電子署名を導入する。
この記事を読んでなにか不明な点や改善するべき点を見つけた場合は、コメントなどで気軽に教えてほしい。

これまでの議論

ここでは、これまでに議論された内容についてのリンクを紹介する。隠蔽と束縛についての記事は読まなくてもよいが、この記事の前半にはコミットメントについての簡単な説明があるので読むと参考になるだろう。

コミットメント

コミットメントは次のような操作ができるプロトコルである。

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

そして、次の二つの性質を持つ。

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

この二つの性質は同時に無条件で得ることはできないので、片方を無条件に得るかわりに、もう一方は計算の複雑さに依存させている。詳細は前回の記事を参照してほしい。

コミットメントを用いたガチャシステム

前述の議論で述べていることを要約すると、次のような手順によってガチャシステムを構成する。ただし、コミットメントの関数を$C$として、この関数は第一引数に付加情報$r$をとり、第二引数にメッセージ$m$を取る。この関数$C$は、あらかじめ運営とユーザーの間で共有しておく。

運営は、$N$種類のカード$K_1 \dots K_N$に番号を割り当てる

カード番号

$K_1$ $1$

$K_2$ $2$

$\vdots$ $\vdots$

$K_N$ $N$
運営は割り当てた番号をユーザーへ公開する
運営はキーと呼ばれる数値$m$を用意する（ただし、キーは$N$より小さい）
運営はキーのコミットメント$c := C(r, m)$を計算し、$c$をユーザーへ送信する
ユーザーはコミットメント$c$を受けとり、(1)の番号の中から一枚$x$を選択し、$x$を運営へ送信する
運営は$m$と$r$を公開する
ユーザーは$c = C(r, m)$を検証する
ユーザーは選択した番号$x$にキー$m$を足して$N$で割った余り$k$を求める
```
k := (x + m) \bmod N
```
ユーザーは(7)で求めた余り$k$に対応するカードを得る

カード	番号
$K_1$	$1$
$K_2$	$2$
$\vdots$	$\vdots$
$K_N$	$N$

コミットメントを用いたガチャシステムの課題

コミットメントを用いたガチャは、前述したように次のような問題を抱えている。

ユーザーが運営が発行したものではない偽のコミットメントを捏造する
運営が、あるコミットメントを発行していないと嘘をつく

このような問題を電子署名によって解決することができる。

電子署名

電子署名とは、ある情報$b$に対して次のことを保証する技術である。

認証: 情報$b$を発行した者がアリスであることを検証できる
否認拒否: アリスが発行した情報$b$をアリスは否認できない

まず認証によって、ある情報$b$は間違いなくガチャシステムの運営が作成したデータであることを検証できる。また否認拒否は、ガチャシステムの運営が発行した情報$b$を後になって発行していないと否認することを抑制する。この二つの効果によって、これまでのコミットメントを用いたガチャシステムにあった課題を解決する。

署名のプロトコル

署名にはいくつか種類があるが、ここでは次の二つの鍵を用いた方法について解説する。

秘密鍵: 署名をするために使う鍵であり、これは署名者のみが知る
公開鍵: 署名を検証するために使う鍵であり、これは多くの検証者が知る

秘密鍵を$d$、公開鍵を$e$として任意のデータ$x$に対して次が成り立つ。

\def\Verify{\text{Verify}}
\def\Sign{\text{Sign}}
\Verify_e(\Sign_d(x), x) = true

署名にはDSAやRSAを用いたものなどいくつか実装があるが、ここではどれを用いても構わない。

署名とコミットメントを用いたガチャシステムのプロトコル

署名を用いてコミットメントを用いたガチャシステムを次のように改良する。ただし、コミットメントに用いる関数$C$と署名の具体的なアルゴリズムについてはあらかじめ運営とユーザーの間で共有しておく。

運営は、$N$種類のカード$K_1 \dots K_N$に番号を割り当てる

カード番号

$K_1$ $1$

$K_2$ $2$

$\vdots$ $\vdots$

$K_N$ $N$
運営は割り当てた番号をユーザーへ公開する
運営は署名の公開鍵$e$と秘密鍵$d$を生成し、公開鍵$e$をユーザーへ公開する
運営はキーと呼ばれる数値$m$を用意する（ただし、キーは$N$より小さい）
運営はキーのコミットメント$c := C(r, m), s := \Sign_d(c)$を計算し、$c$と$s$をユーザーへ送信する
ユーザーはコミットメント$c$を受けとり、(1)の番号の中から一枚$x$を選択し、$x$を運営へ送信する
運営は$m$と$r$を公開する

カード	番号
$K_1$	$1$
$K_2$	$2$
$\vdots$	$\vdots$
$K_N$	$N$

ユーザーは次を検証する

c = C(r, m) \wedge \Verify_e(s, c) = true

ユーザーは選択した番号$x$にキー$m$を足して$N$で割った余り$k$を求める
```
k := (x + m) \bmod N
```
ユーザーは(7)で求めた余り$k$に対応するカードを得る

このようにコミットメント$c$の署名を検証することで、運営が発行していないコミットメントをユーザーが捏造したり、あるいは運営が発行したコミットメントを反故にしたりすることを防げる。

公開鍵の配布と公平な鍵配布機関

上記のプロトコルはまだ一つ考えなければならないことがある。それは(3)において、誰が運営の公開鍵$e$をユーザーに配布するのか、ということである。これは運営のWebサイトなどに公開鍵$e$を設置して、そこにユーザーがアクセスすればよいと考えるかもしれない。しかし、運営は不正をする可能性があるという前提なので、公開鍵を無効なものに書き換える、という悪意ある振る舞いをする可能性がある。したがって、運営の公開鍵を配布するだけの信頼できる第三者が必要である。

まとめ

長い間、ガチャシステムをどうすれば運営にもユーザーにも悪意ある振る舞いを不可能にさせることができるだろうかと考えてきたが、最終的には公平な第三者が必要という結論になったことは、やや興味深いと言えるかもしれない。この公平なガチャシステムから公平な第三者を排除することが、今後の課題になるだろう。

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