本稿について
本稿では、EnigmaのWhitepaperの「5 Privacy-enforcing computation」のうち、「5.1 Overview of secure multi-party computation」の「5.1.1 Privacy(passive adversaries)」までの日本語訳を掲載します。
原文はこちらになります。
スポンサードサーチ
5 プライバシー強制の計算
この章では、Enigmaの計算モデルを説明します。まず、暗号学における最先端の進歩に基づく公に検証可能でセキュアなMPCの簡潔な紹介から始めます。次に、ネットワークが巨大である時でもセキュアなMPCを実践的にさせる一連のパフォーマンス改善手法、すなわち階層的セキュアMPCとネットワーク縮小、順応回路について説明します。
Enigmaを使うために、開発者は高度なコードを書いています。パブリックな部分はブロックチェーン上で実行され、プライベートな部分はEnigmaプラットフォームのオフチェーン上で実行されます。これらはプライべとな情報を処理することのできるスマートコントラクトなので、プライベートコントラクトと呼称します。
5.1 セキュアなマルチパーティ計算の概観
5.1.1 プライバシー（受動的な攻撃者）
1982年、Yaoはセキュアな二者間計算プロトコルへの初めてとなる解決法を紹介しました。同論文で、Yaoはポピュラーなミリオネア問題、すなわち二人の富豪が実際の純資産を明かすことなくどちらがよりお金持ちであるかを知る問題を提示しました。それ以来数十年、その二者間問題はMPCへと一般化され、N者間の場合に触れるようになっています。基本的なMPCゲートの回路から各プロトコルを構成できる汎用MPCでは、長年にわたって2つの主要なアプローチが開発されてきました。すなわち、YaoのGarbled Circuit（筆者注：スクランブルされた回路）や秘密分散に基づくMPCです。後者はプロダクションシステムでより一般的に利用されているとともに、私たちが焦点を当てているものになります。
閾値暗号システムは、閾値（t+1, n）で定義されます。ここで、nは参加者の数のことであり、t+1は閾値暗号によって暗号化された秘密を復号するために必須となる最小の参加者の数を指します。秘密分散は、秘密sがnの間で分割されるものであって、sを再構成するのに少なくともt+1を必要とすることを満たす閾値暗号システムです。いかなるtの部分集合も秘密について何も知ることはできません。線形秘密分散法（LSSS）は、分散情報が秘密の線形結合であることを満たすように、秘密を分散情報に分割します。シャミアの秘密分散法（SSS）はLSSSの一例で、多項式補間を使い、有限体Fpの下で安全です。具体的には、秘密sを分散するために、ランダムなt次元多項式q(x)を選択肢します。
分散情報は次の式によって与えられます。
次に、任意のt+1の分散情報が与えられると、q(x)はラグランジュ補間を使って自明に再構成することができ、秘密sはs=q(0)であることを利用して復元されます。シャミアの秘密分散法は線形であるので、加法準同型でもあり、スカラー演算による加算と乗算がインタラクションすることなく直接分散情報で実行できます。公式的には次のようになります。
2つの秘密s1とs2の乗算はもう少し複雑です。各参加者が2つの秘密の積をローカルで計算しようとすれば、2t次元の多項式を漏れなく入手して、多項式の次数下げステップが（2t → t）必要となります。情報理論な設定では、この結果はプライバシーと正当性に誠実な多数決制約（つまり、t < n/2）を加えます。もし攻撃者の計算能力を制限すれば、プライバシーと正当性は汚染された参加者がいくついるとしても保証されますが、公正性とアウトプットに対する決定性は誠実な多数が依然として必要です。
パフォーマンスに関しては、次数下げステップにおいて事前共有が必須とされ、このステップは各参加者が他の全ての参加者とインタラクションしなければならないように実装することになります（従って、O(n2)のコミュニケーションが発生します）。これは、参加者を示す小さな定数nよりも大きな値について、MPCを非実用的にしてしまいます。一方、ならし計算量の改善向けに最適化されたソリューションはありますが、それは実行時に機能を制限するという仮定に基づいています。逆に言えば、私たちは第5章2節であらゆる機能にとっての問題（筆者注：参加者の数が少なくなければMPCが必要となってしまうが、それをならし計算量の改善で解決しようとすると機能を制限しなくてはならないという問題）に対する包括的なソリューションを詳述しますが、それがセキュアMPCを任意の巨大なネットワークにおいて実現可能にするのです。
セキュアな加算・乗算プロトコルで、私たちは任意の演算機能用の回路を作成することができる点に留意しておいてください。チューリング完全性のために、制御フローも処理する必要があります。秘密の値を含む条件宣言にとって、これは実行にランダム性を加える分岐とFOR文による動的ループの両方を評価することを意味します。私たちの汎用MPCインタプリタは、本ホワイトペーパーの至る所で示されるコアコンセプトや他の最適化手法に基づいています。
（次稿へ進む）
（前稿へ戻る）
免責
邦訳には誤りがある場合がございます。予めご承知おき下さい。
確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。