Enigma ホワイトペーパーの日本語訳及び解説 part2

続きです。５章の途中までです。数式まわりでわかりにくいところは（※）で私がコメントしてます。

５ Privacy-enforcing computation

このセクションではEnigmaの計算モデルについて説明する。まずは 最先端の暗号技術の進歩に基づいた、公的に検証可能なセキュアなMPCについて簡単に紹介する。 次に、階層的なセキュアなMPC、ネットワークの削減、adaptable circuitsによる、ネットワークが大きくても実用性が保たれるセキュアなMPCの一連のパフォーマンス改善について説明する。 エニグマを使用するには、開発者はハイレベルなコードを書く必要があり、パブリックpartはブロックチェーン上で実行され、プライベートpartはエニグマのプラットフォーム上でオフラインで実行されるようにする必要がある。 プライベートな情報を扱うことができるスマートコントラクトであるため、私たちはこれらのプライベートコントラクトと命名した。

5.1 Overview of secure multi-party computation

5.1.1 Privacy (passive adversaries)

Yaoは1982年にセキュアな二者間計算プロトコル問題の解決法を初めて導出した。同論文でYaoは、今では有名な、資産額を公開せずにどちらの方が金持ちであるかを知ろうとする二人の億万長者の問題を提起した。 以来数十年かけて、二者間問題はn人のケースにMPCとして一般化された。 すべてのプロトコルを基本MPCゲートの回路から構成できる汎用MPCでは、長年に渡って、Yaoのガルバール（ブール）回路及び秘密共有に基づくMPCとの2つの主要なアプローチが開発されてきた。後者はプロダクションシステムでより一般的に使用されており、我々が焦点を当てているところでもある。

(t+1,n)で定義されたthreshold cryptosystemを考える。ここでnは当事者の数であり、t + 1はthreshold cryptosystemで暗号化された秘密を復号するのに必要な当事者の最小数である。

  秘密sがn人の間で分割され、sを再現するためには少なくともt+1人が必要とされる秘密共有は、threshold cryptosystemの一例である。 t人以下では、秘密sについて何の情報も得ることができない。

  線形秘密分散スキーム（LSSS）は、秘密sをパーツに分割して、各パーツが秘密sの線形結合となるようにする。 Shamirの秘密分散（SSS）は、多項式補間を使用した有限体Fpの下で安全であるLSSSの一例である。

つまり、秘密sを共有するために、t次元多項式q(x)をランダムに選び、

q(x)=a0+a1x+a2x^2+…+atx^t   (1)

a0=s

ai～U(0,p-1)    (2) (※aiは0からp-1の間で一様分布)

とする。ここで、1～nがそれぞれ受け取る情報は、

∀i ∈ {1, · · · , n} : [s]pi = q(i)

とすると、そのうち任意のt+1個の[s]pi を知ることができれば、ラグランジュ法により（※単純にt+1元1次連立方程式はt＋１本の一次独立な式があれば解けるよね、という話）関数q(x)の各項の係数を計算できるので、x=0を代入することでs = q(0)として秘密sを知ることができる。

SSSは線形かつ準同型であるため、スカラ演算による加算と乗算は、iterationなしに [s]pi に対して直接実行できる。数式で書くと、

c × s = reconstruct({c[s]pi } t+1 i∈n ), (4)

s1 + s2 = reconstruct({[s1]pi + [s2]pi } t+1 i∈n ). (5)

となる。（※個々人が受け取った数字をc倍してから解けば、出てくる値はc × sとなるし、同じように、足してから解くのも解いてから足すのも同じになる。）

二つの秘密s1とs2の掛け算となると、話は少し難しくなって、元がt次元の多項式なので、掛けた結果は2t次元多項式になる。そのため、結果をプライベートかつ正確に再現するためには、正直に値を申告する人の数がt<2nを満たさなければならない。

もし敵対者の計算能力を制限できれば、正しくない値を申告する当事者がある程度いても両方の特性（プライバシーと正確性）が保証されるが、公正さの担保と出力の決定においては、依然として正しい値を申告する当事者が十分な数いることを必要とする。

パフォーマンスに関しては、次元を落とすステップにおいて、すべての当事者が他のすべての当事者とn^2のオーダーで対話しなければならないことを意味する。

 これは、十分に大きなnに対しては、MPCが非実用的であることを意味する。

この複雑さを改善するための最適化されたソリューションは存在するが、実際に用いると機能が制限されることになる。

セクション5.2では、任意の機能に対するこの問題の一般的な解決方法について説明する。これにより、任意の大規模なネットワークに対してセキュアなMPCが実現可能になる。

セキュアな加算および乗算プロトコルでは、任意の算術関数用の回路を構築できることに注意する。 チューリング完全性のためには、制御フローも処理する必要がある。

秘密の値を含む条件文の場合、これは両方のブランチを評価することを意味し、動的ループに対して実行にランダム性を追加する。

私たちの汎用MPCインタプリタは、これらのコアコンセプトと、この論文全体で提示されるその他の最適化に基づいている。