はじめに
ここでは、MPCを自作することに焦点をあて、計算式のなどについては説明しませんので、ご了承ください。 またここでは加法的秘密分散についての仕組みをスコープにします。
まず「秘匿計算」について少しだけ触れておくと、これは暗号化されたままのデータで計算する、といったものです。 暗号化された情報を数値化して計算したのちに再び暗号化するのでありません。
メリットは？といえば、データが漏洩しても大丈夫なんです。では早速！
どう暗号化するのか？
例を挙げて説明します。
まず対象のデータに対して乱数を複数発生させます。乱数は64bitの大きな数値を使うべきですが、ここでは説明なので解釈が容易な数値を例に使います。
| 対象データ(d) | 暗号化データ#1 (d1) | 暗号データ#2 (r1) | 暗号データ#3 (r2) |
|---|---|---|---|
| {対象データ} - {乱数#1} - {乱数#2} | 乱数#1 | 乱数#2 | |
| 2 | 3013 | -1008 | -2003 |
| 4 | 4015 | -1508 | -2503 |
対象データ[2と4] を乱数によってデータ#1-#3 の暗号化情報にします。（実際の乱数は20桁なので、#1-#3 はなんのデータなのか全く想像できないです）
どうでしょう？ 簡単じゃありません？ はい、簡単なんです。
暗号された情報はどう計算するのか？ （乗算以外編）
面倒ですが、ちょっとだけ数式で説明します。まずは上記のデータを例に総和(sum)演算で説明します。
[定義式1] d1[i] = d[i] - r1[i] - r2[i]
変形すると d[i] = d1[i] + r1[i] + r2[i] 全部加算すると元データが得られるので加法的秘密分散
[総和]
d[1] + d[2] = {d1[0] + r1[0] + r2[0]}
+ {d1[1] + r1[1] + r2[1]}
要は d1 と r1 と r2 を独立して演算することができる、ってことです。
これを表で見ていきます。 Excelなどにデータを移して計算式を当ててみるとより理解できると思います。
| 対象データ(d) | 暗号化データ#1 (d1) | 暗号データ#2 (r1) | 暗号データ#3 (r2) |
|---|---|---|---|
| 2 | 3013 | -1008 | -2003 |
| 4 | 4015 | -1508 | -2503 |
| sum | |||
| 7028 | -2516 | -4506 |
d1, r1, r2 単体の演算結果でなんの演算なのかさっぱりですが、これを d に戻す、全部加算すると実データの演算結果が得られます。
7028 -2516 - 4506 = 7028 - 7022 = 6
計算できました！
これは d を複数の乱数によって d1, r1, r2 に分散することで秘匿計算が実現されたのです。
ではもう一つ。同じ仕組みで 平均値を計算してみようと思います。 これ除算があるから乗算がある？と思いがちですが、「暗号化データ同士の乗算」でなければ全て上記と同様に処理できます。
| 対象データ(d) | 暗号化データ#1 (d1) | 暗号データ#2 (r1) | 暗号データ#3 (r2) |
|---|---|---|---|
| 2 | 3013 | -1008 | -2003 |
| 4 | 4015 | -1508 | -2503 |
| sum | |||
| 6 | 7028 | -2516 | -4506 |
| mean | |||
| => 3 | 7028/2 = 3514 | -2516/2 = -1258 | -4506/2 = -2253 |
これを d に戻すと d = 3514 -1258 - 2253 = 3514 - 3511 = 3 となりました！
暗号された情報はどう計算するのか？ （乗算編）
ここまで簡単すぎないか？と思った方も多いことでしょう。ですが本当に簡単なんです。
ただ乗算となるとそう簡単には行かなくなってしまいます。 暗号化されたデータ同士の演算をそのまましてしまうのと下記になります。
| 対象データ(d) | 暗号化データ#1 (d1) | 暗号データ#2 (r1) | 暗号データ#3 (r2) |
|---|---|---|---|
| 2 | 3013 | -1008 | -2003 |
| 4 | 4015 | -1508 | -2503 |
| 乗算 2 x 4 | |||
| ❌ | 3013 * 4015 = 12097195 | -1008 * -1508 = 1520064 | -2003 * -2503 = 5013509 |
これらを加算した値は当然ながら 8 にはなりません。
なんですが、これを解決する有名な方法があります。それが Beaver Multiplication Triples です。この説明はキーワードでググればたくさんでてきますのでリンクも貼りません。ここではこれを解決するためにすべき演算方法のみに言及します。とはいえ、少しだけフローと数式が必要なのでそれを掲載した後、これまで同様の表に演算を記載して、乗算方法を明らかにしていきます。
まず、d1, r1, r2 のようにシェア(分散)されている状態のデータを [x] 、復元されたデータを x のように記載します。また、 d1, r1, r2 列をそれぞれパーティーと呼ぶことにします。
以下、xとyの乗算を例に処理フローを示します。
- まず c = a・b となる乱数を用意します。 具体的には a と b の二つの乱数を用意します。この乱数こそが Beaver Multiplication Triples と呼ばれるものです。
- 用意した a, b, c 乱数をそれぞれ シェア化します。d = d1 + r1 + r2 と同じ要領で、a,b,c それぞれを d1, r1, r2 に分散させます。
- 次に、各バーティーで [d] = [x]-[a] , [e] = [y]-[b] の演算をします。
- 次に、各パーティーで演算した [d],[e] を全パーティで共有して d,e データを復元します。
- 最後に各パーティーで [xy] = [c] + d[b] + e[a] + de 演算をして完了です。ただし、加法的秘密分散では de部は１パーティーのみ計算します。
文章で書くとちょっと分かりにくいと思うので、これを先ほどのように表で時系列に説明していきます。
| 対象データ(d) | 暗号化データ#1 (d1) | 暗号データ#2 (r1) | 暗号データ#3 (r2) |
|---|---|---|---|
| 2 | 3013 | -1008 | -2003 |
| 4 | 4015 | -1508 | -2503 |
| (1),(2) c = a・b乱数発生 | |||
| a = 1000 | 71000 | -30000 | -40000 |
| b = 2000 | 78000 | -33000 | -43000 |
| c = 2000000 | 2082000 | -36000 | -46000 |
| (3) 各バーティーそれぞれで [d] = [x]-[a] , [e] = [y]-[b]演算 | |||
| 3013-7100=-67987 | -1008-(-30000)=28992 | -2003-(-40000)=37997 | |
| 4015-78000=-73985 | -1508-(-33000)=31497 | -2503-(-43000)=40497 | |
| (4) 演算した[d][e]を全パーティで共有し、d, e を復元 | |||
| d= -998 | 3013-7100=-67987 | -1008-(-30000)=28992 | -2003-(-40000)=37997 |
| e= -1996 | 4015-78000=-73985 | -1508-(-33000)=31497 | -2503-(-43000)=40497 |
| d・e= 1992008 | |||
| (5) [xy] = [c] + d[b] + e[a] + de 演算 | |||
| 8 | -215485992 | 92778000 | 122708000 |
d1 : x・y = [c] + d[b] + e[a] + de
= 2082000 + (-998 * 78000) + (-1996 * 71000) + 1992008
= -215485992
r1 : x・y = [c] + d[b] + e[a]
= -36000 + (-998 * -33000) + (-1996 * -30000)
= 92778000
r2 : x・y = [c] + d[b] + e[a]
= -46000 + (-998 * -43000) + (-1996 * -40000)
= 122708000
乗算は、Beaver Multiplication Triples を使って演算します。
実装的に面倒なのは、①同一のBeaver Multiplication Triples 値を全パーティーが得ることと、②それぞれのパーティで [d],[e]を演算し、それを全パーティーで共有して d, e 値にしなければならないことで、②ではパーティ間での同期処理が必要になります。
パーティー処理をマルチスレッド処理するなら実装も容易ですが、分散して秘匿性を保つのならパーティーそれぞれのデータ格納や演算を別にするために docker やホスト分散した方がいいかもしれません。
ただどんなに分散しても最終的に実データを得るためには d1, r1, r2 を集める必要があるため、パーティ毎のデータを独立格納しておけばそれで十分なのかもしれません。
おわりに
僕自身、今回初めてMPC秘匿計算について勉強しました。勉強にあたっては QuickMPC なるオープンソースを参考にしました。
QuickMPC は乗算の同期処理などを考慮した通信のために Envoyが配備され、またパーティー毎には docker が配備されています。 １パーティー実装でも、「データ管理のためのManage」 と 「演算のためのCompute」それぞれがdocker で実装されており、解読難易度はそこそこにあります。
ただ紐解いてみたなら、こんなにも簡単に MPC秘匿計算が実現できていることには本当に驚きました。と同時に、これをオープンソースで公開してくださっていることに感謝の気持ちでいっぱいになりました。 本当に、本当にありがとうございます。