秘密計算を実装するにあたって

2023/10/18 9:342023/10/24 2:57

⚠️注意

本ページは ✅問題（１）解説と ✅問題（２）解説を読んでいることが前提になります。

今回の問題で紹介したアルゴリズムをプログラムとして実装する際には、紙の上で数式を扱うだけでは現れない気をつけるべき点がたくさんあります。

以下ではその例をいくつか紹介します。

RS アルゴリズムでは以下の処理がありました。

あなたがを秘密裏に生成し、その Share をそれぞれ人 1,2 に配布します。

ここではを生成出来たとして, その後のに分割する操作に注目してみます。

一見すると整数をランダムに作成し、で定めればいいように思えます。

しかし実際にはすべての整数からランダムに数を作成することは難しく, また受け取り手からしてものような非常に大きい数が送られてくる可能性を考慮しておかないといけないのは大変です。

そこで Acompany ではある整数を取り決め、を満たすをランダムに取ると言う仕様にしています。

しかし、このを人2が知っていた場合、人2はを受け取った際に以下のようにしてを知ってしまう可能性があります。

論文にはこう言った実装するにあたってのコーナーケースまでは書いていないことも多く、自分で気付き対策を考える必要があります。

対策としては例えばのような非常に大きい値を取ると言った方法が考えられます。

これは非常に単純かつ力技な対応ですが、が特定出来てしまうケースの発生確率を以下と言う大変小さな値に抑えることが出来る強力な手法になります。

しかし Share の存在範囲を広く取ることは次に述べる問題を引き起こしやすくなります。

コンピューターで小数を扱う時は情報落ちや桁落ちなどによる誤差の発生に注意する必要があると言うのは、エンジニアであれば知っている人も多いと思います。

これらの概念について簡単に説明すると、情報落ちは絶対値が大きく異なる二つの値の足し算をした際、桁落ちは値が非常に近い二つの値を引き算した際に起きる問題で、どちらも計算結果に無視出来ない誤差を発生させてしまうものです。

加法的秘密分散法ではこう言ったケースが非常によく現れます。

例えばを Share に分割する際をとったとします。

この場合となりそうですが、コンピューターは情報落ちの影響でをと計算してしまいます。

この時点でとなってしまうため、以降は全てとして計算が進むことになってしまいます。

整数で計算する場合もオーバーフローに注意する必要があります。

C++ や Go など多くの言語ではあらかじめ扱う整数の最大桁数を固定することが多く、計算中にこの桁数を超える数が出てしまった場合はオーバーフローと言って間違った値が計算結果に入ってしまいます。

最大桁数は一般には 18 桁程度のことが多く、実際足し算や掛け算を行う中で 19 桁以上の数が現れるケースは（業務内容に強く依存しますが）稀であるため、この制約を強く意識する機会が無いエンジニアも多数いると思います。

しかし加法的秘密分散法では先述の通り（扱うデータの値がそんなに大きく無い場合であっても）計算過程では Share として大きな値を扱うことがあるため、プログラムの実装段階で注意深く取り得る値の最大値最小値を見積もる必要があります。

また、最大桁数の固定を無理やり無くしたり、代数空間として整数環の代わりに剰余環を考えると言った方法で対策ができる場合もあります。

加法的秘密分散法を実装するにあたって注意すべき点は他にもたくさんあります。

間違った計算結果出るタイプのバグはテストコードを書くことである程度は発見できますが、一方で最初に述べたような、使用者が公開されている情報から秘密情報に辿り着けてしまう類のバグに関しては開発者が各処理にじっくり向き合い一つ一つ発見するしかなく非常に大変です。

こう言った点に注意しながら実装出来る人間を Acompany では広く歓迎しています。

また、数学的な処理以外にも考えることは山積みです。

たとえば Share を通信する際に傍受されてしまえばせっかくの秘密計算が全て台無しなので、通信の暗号化なども考えないといけません。

それから、実際に事業として運用していく上で発生するタスクもあります。

今回扱った問題の設定をもう少し Acompany が扱っている実際の事業に近づけると、太郎くんと花子さんが持っていた数列はそれぞれ彼らの会社が所持している顧客の個人情報などに対応します。

例えば「太郎くんの会社は愛知県在住の男性の個人情報を100~200人持っている」と言う情報なら花子さんに開示しても問題ないのか？と言ったことについては、個人情報保護法と照らし合わせたり個人情報保護委員会に問い合わせたりして確認の作業が必要かもしれません。

また、今回のアルゴリズムでは花子さんとも太郎さんとも違う人が乱数を作成、配布する処理がありましたが、そう言った第三者が関与出来る範囲についても同様に確認する必要があります。

もちろんそれとは別に、Acompany の顧客である太郎くんと花子さんが本当に知りたいことは何か？と言ったことも適切にヒアリングしなければなりません。（例えば問題（１）ではの内積を求めていましたが、実はの相関係数が分かるならそっちの方が嬉しいかもしれません）

最後に、それら全ての結果を踏まえて法的な制約もクリアしつつ顧客の要望を実現出来る適切なアルゴリズムを選択します。

今回は加法的秘密分散法の紹介をしましたが、弊社では R&D チームと開発チームが一丸となって用途に応じた様々なプライバシーテックアルゴリズムを日々調査、作成、実装しています。

少しでも興味を持った方はお気軽に話を聞きに来てください。