暗号学者の食事問題

暗号学において、ダイニング暗号学者問題は、ブールXOR関数の安全なマルチパーティ計算を実行する方法を研究する。この問題は、1980年代初頭にデビッド・ショームが初めて提案し、送信者と受信者の追跡が不可能な匿名メッセージを送信できることを示す例として使用した。この問題に基づく匿名通信ネットワークは、 DCネット（DCは「ダイニング暗号学者」の略）と呼ばれることが多い。 ^[1]

ダイニングという言葉にもかかわらず、ダイニング暗号学者問題はダイニング哲学者問題とは無関係です。

3 人の暗号学者が夕食のためにテーブルを囲んでいます。ウェイターは、食事の代金は誰かによって支払われたと伝えます。その人物は暗号学者の 1 人か、国家安全保障局(NSA) である可能性があります。暗号学者はお互いに匿名で支払いをする権利を尊重しますが、NSA が支払ったかどうかを調べたいと考えています。そこで、2 段階のプロトコルを実行することにしました。

最初の段階では、2 人の暗号作成者が 1 ビットの共有秘密を確立します。たとえば、メニューの背後にコインを投げて、2 人の暗号作成者だけが順番に 2 人の暗号作成者ごとに結果を確認できるようにします。たとえば、コインを投げた後、暗号作成者 A と B が秘密ビット を共有し、A と C が を共有し、B と C が を共有するとします。 ${\displaystyle 1}$${\displaystyle 0}$${\displaystyle 1}$

第 2 段階では、各暗号作成者が次のビットを公開します。

• 彼らが食事代を払わなかった場合、彼らが2人の隣人と共有している2つのビットの排他的論理和（XOR）は、
• 彼らが食事代を支払った場合は、その XOR の反対になります。

暗号学者の誰も支払わなかったと仮定すると、A は、B は、C は と発表します。一方、A が支払った場合は と発表します。 ${\displaystyle 1\oplus 0=1}$${\displaystyle 1\oplus 1=0}$${\displaystyle 0\oplus 1=1}$${\displaystyle \lnot (1\oplus 0)=0}$

3 つの公開発表を組み合わせると、質問の答えが明らかになります。発表された 3 つのビットの XOR を計算するだけです。結果が 0 の場合、暗号作成者の誰も支払っていないことを意味します (したがって、NSA が支払いをしたに違いありません)。それ以外の場合は、暗号作成者の 1 人が支払いましたが、その身元は他の暗号作成者には不明のままです。

David Chaum は、このプロトコルを「ダイニング クリプトグラファー ネットワーク」、または「DC-net」 という用語で表現しました。

DC-net プロトコルはシンプルで洗練されています。ただし、いくつかの制限があり、その後の研究でいくつかの解決策が検討されています (以下の参考文献セクションを参照)。

衝突

2 人の暗号学者が夕食代を支払った場合、彼らのメッセージは互いに打ち消し合い、最終的な XOR 結果は になります。これは衝突と呼ばれ、このプロトコルを使用して一度に送信できるのは 1 人の参加者だけです。より一般的なケースでは、偶数の参加者がメッセージを送信する限り、衝突が発生します。${\displaystyle 0}$

混乱

グループの通信を妨害したい悪意のある暗号作成者は、XOR の正しい結果の代わりにランダムなビットを送信するだけで、最終的な XOR 結果が役に立たないようにプロトコルを妨害することができます。この問題は、元のプロトコルが公開鍵技術を使用せずに設計されており、参加者がプロトコルに誠実に従っているかどうかを確認するための信頼できるメカニズムがないため発生します。^[2]

複雑

このプロトコルでは、参加者間でペアで共有される秘密鍵が必要ですが、参加者の数が多い場合は問題が発生する可能性があります。また、DC-net プロトコルは「無条件に安全」ですが、実際には参加者のペア間に「無条件に安全な」チャネルがすでに存在しているという前提に依存しており、実際にこれを実現するのは容易ではありません。

関連する匿名拒否ネットワークアルゴリズムは、DC ネットのような論理 XOR ではなく、複数のユーザーの入力の論理 OR を計算します。これは、論理 OR 結合操作が自然に適しているアプリケーションで役立つ場合があります。

デビッド・ショームは1980年代初頭にこの問題について初めて考えました。基本的な考え方を概説した最初の出版物は彼のものです。^{[3]ジャーナル版は}Journal of Cryptologyの創刊号に掲載されました。^[4]

DC ネットは、以下に説明するように、1 ラウンドあたり 1 ビットを超える送信、3 人以上の参加者のグループ、および 2 進数の 0 と 1 以外の任意の「アルファベット」を許可するように簡単に一般化できます。

匿名の送信者が DC ネット ラウンドごとに 1 ビット以上の情報を送信できるようにするには、暗号作成者のグループがプロトコルを必要な回数だけ繰り返すだけで、必要なビット数の送信帯域幅を作成できます。これらの繰り返しは、連続して実行する必要はありません。実際の DC ネット システムでは、参加者のペアが、たとえばDiffie-Hellman 鍵交換を使用して、単一の共有「マスター」シークレットに事前に同意するのが一般的です。次に、各参加者は、この共有マスター シークレットをローカルで疑似乱数ジェネレータに入力し、匿名の送信者が複数のビットの情報を送信できるように、必要な数の共有「コイン トス」を生成します。

このプロトコルは、参加者のグループに一般化できます。各参加者は、他の参加者と共通の共有秘密鍵を持っています。プロトコルの各ラウンドで、参加者が追跡不可能なメッセージをグループに送信したい場合、公開されたビットを反転します。参加者は、参加者を表す頂点と、共有秘密鍵を表す辺を持つ 完全に接続されたグラフとして視覚化できます。${\displaystyle n}$

このプロトコルは、完全接続ではない秘密分散グラフで実行できる場合があります。これにより、実際の DC ネット実装のパフォーマンスとスケーラビリティが向上しますが、共謀する参加者が秘密分散グラフを別々の接続コンポーネントに分割できる場合、匿名性が低下する潜在的なリスクがあります。 たとえば、直感的には魅力的ですが安全性の低いリング トポロジを使用する参加者への一般化は、テーブルの周りに座っている各暗号学者が、自分のすぐ左と右にいる暗号学者とのみ秘密を共有し、他のすべての暗号学者とは秘密を共有しないというものです。 このようなトポロジは、各暗号学者が ではなく、ラウンドごとに 2 回のコイントスを調整する必要があるため魅力的です。 しかし、アダムとチャーリーが実際には NSA エージェントで、罪のない被害者であるボブのすぐ左と右に座っていて、アダムとチャーリーが密かに共謀してお互いに秘密を明かした場合、参加者の合計数に関係なく、DC ネットの実行でボブが 1 ビットの送信者であったかどうかを確実に判断できます。これは、共謀した参加者のアダムとチャーリーが、秘密共有グラフを 2 つの独立した分離したコンポーネントに事実上「分割」し、一方にはボブのみが含まれ、もう一方には他のすべての正直な参加者が含まれるためです。 ${\displaystyle n>3}$${\displaystyle n}$

スケーラビリティのために Dissent システムで採用されている、もう 1 つの妥協的な秘密共有 DC ネット トポロジ^[5]は、クライアント/サーバーまたはユーザー/受託者トポロジとして説明できます。このバリエーションでは、異なる役割を果たす 2 種類の参加者がいると想定します。1 つは、匿名性を望む潜在的に多数のユーザーnと、もう 1 つは、ユーザーが匿名性を獲得するのを支援する役割を持つ、はるかに少数の受託者です。このトポロジでは、各ユーザーは各受託者と秘密を共有しますが、ユーザーは他のユーザーと秘密を直接共有せず、受託者は他の受託者と秘密を直接共有しません。その結果、秘密共有マトリックスが形成されます。受託者の数が少なければ、各ユーザーは少数の共有秘密のみを管理すればよく、リング トポロジと同様にユーザーの効率が向上します。ただし、少なくとも 1 人の受託者が誠実に行動し、秘密を漏らしたり他の参加者と共謀したりしない限り、その誠実な受託者は、他のユーザーや受託者が不正に共謀しているかどうかに関係なく、すべての誠実なユーザーを 1 つの完全に接続されたコンポーネントに接続する「ハブ」を形成します。ユーザーは、どの受託者が誠実であるかを知ったり推測したりする必要はありません。ユーザーのセキュリティは、少なくとも 1 人の誠実で共謀していない受託者の 存在のみに依存します。${\displaystyle m}$${\displaystyle n}$${\displaystyle m}$${\displaystyle n\times m}$${\displaystyle m}$

シンプルな DC-nets プロトコルでは、送信アルファベットとして2 進数を使用し、暗号文の結合には XOR 演算子を使用しますが、基本プロトコルは、ワンタイム パッド暗号化に適した任意のアルファベットと結合演算子に一般化されます。この柔軟性は、多数の参加者ペア間で共有される秘密が、実際には、単一の DC-net ラウンド内で対称的に結合されたワンタイム パッドにすぎないという事実から自然に生じます。

DC-nets のアルファベットと結合演算子の便利な代替選択肢の 1 つは、公開鍵暗号に適した有限群(シュノア群や楕円曲線など) をアルファベットとして使用し、関連する群演算子を DC-net 結合演算子として使用することです。このようなアルファベットと演算子の選択により、クライアントはゼロ知識証明技術を使用して、DC-net が提供する匿名性を損なうことなく、参加者が伝送チャネルを「妨害」していないなど、生成する DC-net 暗号文の正しさを証明できます。この技術は、最初に Golle と Juels によって提案され^[6] 、 Franck によってさらに開発され^[7]、後に暗号的に検証可能な Dissent システムの実装である Verdict に実装されました。^[8]

衝突を回避するために David Chaum 氏が最初に提案した対策は、衝突が検出されるとメッセージを再送信することですが、この論文では再送信をどのように手配するかについて具体的に説明されていません。

異議申し立てでは、検証可能なシャッフルを使用してDCネットの送信スケジュールを確立することで、意図しない衝突の可能性を回避します。これにより、各参加者はスケジュール内のどのビットが自分の送信スロットに対応しているかを正確に把握しますが、他の送信スロットを誰が所有しているかはわかりません。^[9]

Herbivore は、大規模な匿名ネットワークを小さな DC ネット グループに分割し、参加者が混乱したグループを離れて別のグループに参加することで、混乱の試みを回避できるようにします。参加者は、混乱者がいないグループを見つけるまで、混乱を回避します。^[10] この回避アプローチでは、多数のノードを所有する敵対者が、完全に侵害されていないグループのみを選択的に混乱させるリスクが生じます。その結果、参加者は、完全に侵害されているために機能している可能性のあるグループに「追いやられる」ことになります。^[11]

Dissent は、妨害に対抗するためにいくつかのスキームを実装しています。元のプロトコル^{[9]では、検証可能な}暗号シャッフルを使用してDC ネットの送信スケジュールを作成し、「送信割り当て」を配布することで、後続の DC ネット暗号文の正しさを単純な暗号ハッシュチェックで検証できるようにしていました。ただし、この手法では、各 DC ネット ラウンドの前に新しい検証可能なものが必要であり、レイテンシが高くなります。その後のより効率的なスキームでは、妨害がない場合、一連の DC ネット ラウンドをシャッフルを介さずに進めることができますが、妨害イベントへの対応では、シャッフルを使用して匿名の告発を配布し、妨害の被害者が犯人の身元を明らかにして証明できるようにします。^[5] 最後に、最近のバージョンでは、完全に検証可能なDCネットをサポートしていますが、DCネットでは公開鍵暗号を使用しているため計算効率が大幅に低下します。また、通常は効率的なXORベースのDCネットを使用し、中断時にのみ検証可能なDCネットを使用するハイブリッドモードもサポートされており、検証可能なシャッフルを使用するよりも迅速に告発を配布できます。^[8]