はじめに
この記事では、秘密計算(秘匿計算)の実現方法の一つであるMulti-party Computation(MPC)において、乗法を効率的に行うことができる「Beaver Multiplication Triples」について紹介します。ただし、秘密計算やMPC、秘密分散法についての基礎的な知識を前提としております。
秘密計算やMPC、秘密分散法については、以前の記事で解説しておりますので、まずはそちらを参照して下さい。
一般に、MPCを用いる方法では、加法と乗法が定義できれば任意の計算を実行することができます。そのため、「Beaver Multiplication Triples」を用いて効率的に乗法が実現できることは、大きなメリットとなります。また、その実現方法はシンプルであるため容易に実装することができます。
それでは詳しく紹介していきます。
Beaver Multiplication Triples による乗法の手順
ある秘密情報$x$ が任意の線形秘密分散法によってシェアにされている状態を$[x]$ と書くことにします。
ここで、$c = ab$ となる乱数$(a, b, c)$ のシェア$[a],[b],[c]$ を各パーティが保持しているとします。このような乱数をBeaver Multiplication Triples と呼びます。
さらに、各パーティは秘密情報のシェア$[x], [y]$ を保持しています。この時、$z=xy$ となるような$z$ のシェア$[z]$ を各パーティが保持することを目指します。
以下の方法を用いることで計算することができます。
- 各パーティがローカルで$[d] = [x]-[a],[e]= [y]-[b]$ を計算する
- 全てのパーティが$[d],[e]$ を公開し、$d, e$ の値を復元する
- 各パーティはローカルで$[z] = e[a] + d[b] + [c] + de$ を計算する（加法的秘密分散の場合+de項は1Partyのみ計算する）
上記の方法により計算された$[z]$ が$z$ のシェアであることは、以下の式変形によって確認できます。
$$ \begin{array}{ccl} z &=& ea + db + c + de \\ &=& (y – b)a + (x – a)b + ab + (x – a)(y – b) \\ &=& xy \end{array} $$
最終的に、$[a],[b],[c],[x],[y]$ を用いることで$[z]$ を各パーティが保持することができました。ここで、この方法はローカルでの加法と定数倍の乗法、通信を用いた2つのシェアの復元を行うだけで実現できることから、シンプルかつ効率の良い方法と言えます。
ただし、$c=ab$ となる乱数の組を用意する方法はシステムの目的や構成に依存するため、絶対的な解はありません。そのため、実装するMPCシステムに適合した方法を実装する必要があります。
まとめ
この記事のまとめは以下になります。
- Beaver Multiplication Triples で効率的に乗算を実現できる
- 事前計算された3つの乱数のシェアを使用する
- ローカルでの加法と定数倍の乗法、通信を用いたシェアの復号処理だけで実現できる
- 3つの乱数の生成はシステムの構成に依存する
参考文献
https://link.springer.com/content/pdf/10.1007/3-540-46766-1_34.pdf
https://www.jstage.jst.go.jp/article/isciesci/63/2/63_71/_pdf
