Mental MahjongとはP2Pの仕組みを用いて、不誠実な（不正をするかもしれない）プレイヤー同士で、 第三者的の公平なジャッジサーバーを用いずに公平なゲームをする方法です。 Mental Pokerという ゲームを参考に僕（@yyu）と @shincblや@re_Ord、 @linerlock、@mimizunohimono や@ioriveurなどと考えました。
まずプレイヤーをその局の時の自風でそれぞれ次のように呼びます。
- E （東）
- S （南）
- W （西）
- N （北）
また、このゲームでは麻雀牌136枚にそれぞれ別の数字を割り当てます。 つまり、四枚ある同じ牌でも別の番号を振るということです。
このゲームでは複数人で行うDiffie-Hellman鍵交換を用います。
直感の印象としては次のよう感じです。
- 暗号化
- 鞄に南京錠を付ける
- 復号化
- 鞄にある南京錠を取り除く
鞄に南京錠が一つも付いていない時、それは平文であるということです。 鞄に自分の付けた南京錠しかない時、自分は自分の南京錠を取り外せるので開錠できます。 また、自分の持つ南京錠の鍵は他のプレイヤーに渡すことができ、 鍵を受け取ったプレイヤーはその南京錠を開錠することができます。 ただし、鞄に現在どの鍵が付いているのかという情報を鞄から得ることはできません。
例えば南京錠Aをかけた後に南京錠Bをかけたカバンがあるとします。
南京錠ですからAを開錠した後にBを開錠するのと、
Bを開錠してからAを開錠するのとの間に違いはありません。
つまり暗号化と復号化の順番が対応していなくても、得られる平文に違いはないということです。
このような性質を持つ暗号技術を用いているということです。
まず、全ての麻雀牌（136枚）には別々の数字が割り当てられているので、
1から136までの数字を E （親）がシャッフルして、任意の順番にします。
そして、E は鍵E_kを生成してそれでそれぞれの数字を暗号化します。
暗号化された1から136までの数字がランダムに並んだデータを、 S に送信します。
この時、 S が受け取ったデータはE_kで暗号化されているので元の数字は分かりません。
S はこの受け取ったデータを任意の順番に並び換えます。
そして鍵S_kを生成し、136個のデータをそれぞれ暗号化します。
ここまでを図にすると次のようになります。
このように、シャッフルしては暗号化し次の者へ渡すというのを
E , S , W , N の順に行ないます。ここで、 W の用いた鍵をW_k、
N の用いた鍵をN_kとします。
すると、最後には四人の鍵で暗号化された136枚の牌が得られます。
最後に暗号化した N は、牌のデータを再び E へ送ります。
E はE_k、S_k、W_k、N_kで暗号化された列に対して、
自分が行った暗号化を鍵E_kに対する復号鍵E_k'を用いて取り除きます。
そして、 E はE_k1, E_k2, E_k3, ..., E_k136までの136個の鍵を生成し、
E_k1で136個のうちの最初の牌を、E_k2で二番目の牌を、という具合に暗号化します。
そして最終的にできあがったデータを S に渡します。
S は N と同様に、自身が行った暗号化を取り除き、
鍵をS_k1, S_k2, ..., S_k136までの136個を生成し、
それで暗号化をして、それを次に W へ送り、 W も同様の操作をして N へ送ります。
N が最後に暗号化を終えた時には、最初のデータは鍵E_k1, S_k1, W_k1, N_k1で暗号化され、
次のデータは鍵E_k2, S_k2, W_k2, N_k2で暗号化されています。
このデータを N は他のプレイヤーに送り共有します。
これが山となります。
ドラ表示牌は山の先頭になります。先頭は鍵E_k1, S_k1, W_k1, N_k1で暗号化されているので、
プレイヤー E , S , W , N は鍵E_k1, S_k1, W_k1, N_k1に対応する復号鍵を公開することで、
ドラ表示牌を復号化します。
これはカンドラや裏ドラに対しても同様で、その時の山の n 番目に対応する復号鍵をプレイヤー全員が公開することで、 ドラ表示牌を共有します。
配牌やツモなど、山から牌を取り出す際には次のような手法を用います。
例えばここではプレイヤー E がツモあるいは配牌で山の先頭から n 番目のデータを取り出したいとします。
ここで、山の先頭から n 番目の牌は鍵E_kn, S_kn, W_kn, N_knで暗号化されています。
- 鍵
E_kn,S_kn,W_kn,N_knで暗号化されたデータを S へ送る - S は鍵
S_knによる暗号化を解除する。この時牌は鍵E_kn,W_kn,N_knで暗号化されているので分からない - S は鍵
E_kn,W_kn,N_knで暗号化されているデータを W へ送る - W は鍵
W_knによる暗号化を解除する。この時牌は鍵E_kn,N_knで暗号化されているので分からない - W は鍵
E_kn,N_knで暗号化されているデータを N へ送る - N は鍵
N_knによる暗号化を解除する。この時牌は鍵E_knで暗号化されているので分からない - N は鍵
E_knで暗号化されているデータを E へ送る - E は鍵
E_knによる暗号化を解除する。これで暗号化されていない牌が得られる
という方法を用います。
図にある番号（10）は最初に牌に振った1から136までの番号です。
このような要領で各プレイヤーがツモりあいます。
捨牌の情報は公開情報なので、平文を他のプレイヤーにブロードキャストします。
プレイヤーが和了または流局してその局が終了した場合、その局の間に不正がなかったのかを検証します。 ここで言う不正とは、少なくとも次の状況です。
- ツモや配牌で持ってきた牌を偽った
- 持っていない牌を切った
これは少なくとも次の方法で検証することができると考えています。
- すべてプレイヤーは局の終了時に自分が持つ復号鍵を全て全員に公開して、山を全て復号化して矛盾がないか検証する
しかしながら、この方法を用いると自分以外のプレイヤーの手牌も復号化できてしまい、 結果他プレイヤーの戦略が明らかになってしまいます。 そこでClaude Crtpeauの論文 などを参考にして、他のプレイヤーの手牌を公開することなく 確率的 に不正のなさを検証したいと考えています。
また、LibTMCGというライブラリがあるようで、これも参考になるのかと考えています。
なんだか不正の検証あたりが微妙なので、誰か考て欲しいです。