本稿について
本稿では、EnigmaのWhitepaperの「5 Privacy-enforcing computation」のうち、「5.2 Hierarchical secure MPC」、「5.3 Network reduction」、「5.4 Adaptable circuits」までの日本語訳を掲載します。
原文はこちらになります。
5.2 階層的セキュアMPC
情報理論の結果は、セキュアMPCプロトコルは各計算ノードが他の全てのノードとインタラクションする（O(n2)の通信複雑性）ことと、定数ラウンドが必要であることを示しています。LSSSのケースでは、この計算複雑性は全ての乗算オペレーションに適用されるのに対し、加算オペレーションは相互通信することなく並行処理されます。既に述べたように、セキュアな加算と乗算プロトコルで、任意のコードを安全に評価する汎用インタプリタを十分に構成することができます。
Cohenらは、図3に示すように、一定サイズのMPCゲートの対数深度フォーミュラ（※筆者注を後述）を使って参加者数をnとするときのセキュアプロトコルをシミュレーションする方法を提案しました。私たちは彼らの成果をLSSSに拡張し、計算複雑性の増大という代償を払って、乗算における通信複雑性を二次から一次へと下げられるようにしました。これは並列処理可能です。図4は、私たちの実装が任意の巨大なネットワークに対してスケールアップできる一方で、ありきたりなMPCがいかに参加者数によって制限されるかを示しています。
※対数深度フォーミュラについての筆者注※
ホワイトペーパーに参考文献として示されている文献を辿ると、対数深度フォーミュラ（log-depth formula）について次のような記載があります。
原文：A formula is a circuit with fan-out 1. A logarithmic-depth formula (more precisely, infinite family of formulas) is one whose depth is O(logn), where n is the number of inputs.
これを翻訳すると、「フォーミュラとは、論理出力数が1であるような回路のことです。対数深度フォーミュラ（より正確に言えば、フォーミュラの無限集合体）はその深さがO(logn)であるようなフォーミュラで、ここでnは入力の数とします」となります。すなわち、「入力数がnで深さがO(logn)であることように論理出力数が1の回路を構成した回路の集合体」が定義と言えるでしょう。
5.3 ネットワーク縮小
ネットワークの計算パワーを最大化するために、ネットワーク縮小技術を紹介します。ネットワーク縮小技術は、ネットワーク全体のうち、ランダムなサブセットが選択されて計算を実行するというものです。このランダムなプロセスでは、ロードバランシングの要件及び累積評判に基づいて優先的にノードを選択します。累積評判は、ノードが公に行っている検証行動によって測定されます。これにより、あらゆる時点においてもネットワークが完全に調整されることが確約されます。
5.4 順応回路
私たちのシステムで評価されるコードは、不誠実な多数が（t ≥ n/2を満たすように）共謀しない限り、何らの情報も漏らさないことが保証されます。これは入力値と同様に、コードを評価する間に計算されるあらゆる中間の変数についても当てはまります。鋭い読者の方は、関数が入力から出力まで評価されるにつれて中間の結果が一般により記述的でなくなるとともにより集約的になるということに気づくでしょう。
単純な関数やほとんど入力が関わらない関数にとってこのことは必ずしも真でないかもしれませんが、これらの関数は素早く計算できるので追加のステップは不要です。
しかし、多くのコード行数を持ち莫大な入力が関わる計算機的に高価な関数にとっては、関数評価プロセス全体に固定値nを取る代わりに（筆者注：参加者の数と等しいnの計算ノードを割り当てる代わりに）、進捗が進むにつれて計算ノードの数を劇的に減らすことができます。具体的には、結果を入力から出力へと伝播させるフィードフォワードネットワーク（図5）を設計します。元のコードが再編成され、まず入力に対して加算ゲートを処理し、続いて乗算ゲートを処理します。そのあと中間の結果がN/cのノード秘密分散されます。このプロセスを再帰的に繰り返します。
（次稿へ進む）
（前稿へ戻る）
スポンサードサーチ
免責
邦訳には誤りがある場合がございます。予めご承知おき下さい。
確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。