食事する暗号学者の問題 (dining cryptographers problem)とは、匿名による情報発信法やその匿名性の証明に関する問題である。3人以上の暗号学者達が円卓で食事を取っていた。そこにウェイターがやって来て匿名の何者かが彼ら全員分の食事代を支払ったと学者達に伝えた。学者のうちの誰かが払ったのかもしれないし、学者達の雇い主であるNSA(アメリカ国家安全保障局)が支払ったのかもしれない。どちらが支払ったのか知りたいが、もし学者のうちの誰かが支払ったのなら、匿名で支払ったという意思を尊重したい。どちらが支払ったのか、支払った学者を特定することなく知る方法はあるだろうか？例として4人の場合を考える。まず右隣りの学者との間で、メニューの裏でこっそりコインをトスする。結果は2人だけで共有し、他の学者には秘密にする。次に対面の学者とも同様にコインをトスし、秘密を共有する。この時点で各学者は右隣り、左隣り、対面の3人の学者とのコイントスの結果を持っている。そして各学者は3回のコイントスの結果、表が出た回数が奇数であったか偶数であったか全員に向かって宣言する。ただし食事代を支払った学者だけは反対の結果を宣言する。この時点で4人分の宣言の結果が揃っている。4人の中で「奇数」と宣言した学者の数が奇数であれば学者の1人が支払ったという情報が得られ、偶数であればNSAが支払ったという情報が得られる。学者の人数が一般のnの場合も同様にn-1人とコインをトスすればよい。食事する暗号学者のプロトコルはDCネットとも呼ばれる(3節)。2ビット以上のメッセージを発信する場合は一連の動作を複数回繰り返せばよい。このとき、同時に複数の参加者がビット1を発信した場合、衝突して消えてしまう恐れがある。衝突を検知した場合、無作為な時間だけ待ってから再送する回避方法(CSMA/CD)がある(2.2節)。また、通信枠の予約(slot reservation)を使った回避方法もある(2.2節)。この場合通信はmビットのブロック単位で扱う。まず情報発信する参加者は1からmの間の数iを無作為に選ぶ。次に最初のブロックの送信時にi番目のビットのみを1とし、それ以外を0とする。そして最初のブロックで衝突が無かった場合、次のブロックではi番目のビットを使って情報を発信する。誕生日のパラドックスがあるため、衝突確率を一定以下に保つためには、ブロックのサイズを参加者数の自乗に比例させる必要がある(2.5節)。食事する暗号学者のプロトコルでは、1人を除く全員が結託したときに限り発信者を特定できる(1.3節)。これを一般化して自分以外の全員と秘密を共有するのではなく、限られた参加者とのみ秘密を共有する場合を考える。すると各参加者を端点とし、秘密の共有関係を辺としたグラフが考えられる。ここでグラフからいくつかの辺を取り除く場合を考える。このとき各連結成分を、取り除いた辺の集合に対する匿名性集合(anonymity set)という(1.1節)。そして複数の参加者が結託して発信者を特定しようとした場合、結託した参加者に接する辺をグラフから取り除く。このとき結託した参加者は各匿名性集合ごとに情報発信した参加者の有無を得られるが、匿名性集合の中の発信者は特定できない(1.1節, 1.4節)。特別な場合として、グラフが円構造の場合、両隣の2人が結託した場合、その発信者の匿名性は失なわれる(2.3節)。故意や実装のバグによりノイズを流す参加者がいると他の参加者による情報発信が妨害されてしまう。これに対し、妨害者と接する辺を少しずつ減らしていく方法が提唱されている(2.5節)。の著者による匿名情報発信技術の1つであるミックスネットワークの匿名性は、公開鍵暗号技術に依存しているため計算量的安全性しか持たない。一方で食事する暗号学者のプロトコルは鍵を安全に交換した場合情報理論的安全性を持つ(3節)。

出典:wikipedia