📝
【技術】秘密分散法とは
はじめに
この記事では「秘密分散法」についての簡単な紹介を行います。秘密分散法とは、データを「シェア」という特殊なパーツに分解して、複数パーティ間で共有する方法です。重要なのは、一つ一つのシェアからは元のデータに関する情報は得られず、一定数のシェアを集めることで初めて元のデータを復元できるという性質です。例えば、 秘密分散法と書けば、データを 個のシェアに分解して、 個以上のシェアを集めることで復元できることを意味します。ただし、 であると定義します。 のことをしばしばしきい値と呼んだりします。以下では、秘密分散法の代表例である「加法的秘密分散」と「シャミア秘密分散」について紹介します。
加法的秘密分散
加法的秘密分散は最も直感的に理解しやすいであろう手法の一つです。加法的秘密分散法は、 秘密分散法です。つまり、全てのシェアを集めなければ元のデータを復元できません。
ある秘密情報sのシェア化は以下のように行われます。
パーティ集合 :
s のシェア : （ は が所持するシェア）
- 以外のパーティ () がそれぞれ乱数 を生成する
- 秘密情報提供者 に対し、 以外のパーティ が独立して を送信する
- は に を送信する
- は受け取った を自分のシェアとする。つまり とする
- 以外のパーティ は とする
上記のシェア化によって、元のデータsが復元できることを確かめるのは簡単です。加法的秘密分散法では、名前の通り全シェアを足し合わせることで復元できます。
シャミア秘密分散
こちらもとても有名な秘密分散手法です。シャミア秘密分散法は 秘密分散手法です。 を満たすしきい値 を自由に設定できます。
シェア化の手順を説明する前に、シャミア秘密分散を理解する上で欠かせない事項について述べます。ここでは、 次多項式 について考えます。ネタ晴らしをすると、この の 次の項 に秘密情報 が入ります。また、 () は全て未知であることを前提としています。秘密情報 () を得るためには、 上の 個の点 () についての情報が必要です。ただし、 の時 です。 個の未知数 を一意に求めるためには、 個の一次独立な方程式が必要であることは自明です。実際の復元アルゴリズムの中で () を求める際には、連立方程式を解かずにラグランジュ補間というものを用います。
ここまで読めば勘の良い読者は既に気付いていると思いますが、秘密情報 のシェアは 上の点として与えらます。つまり、 個のパーティ () に対し、シェア () を分配するということです。 人の内いずれか 人がシェアを開示することで、 を復元できます。ラグランジュ補間は、 次多項式fにおいて、 上の 個の点を元に、 上の任意の 1 点 を求めることが出来るアルゴリズムです。連立方程式を解くことでも s を求めることは可能です。しかし、連立方程式を解く代表的なアルゴリズムであるガウスの消去法の計算量が であるのに対し、ラグランジュ補間の計算量は （実装によっては ）であるため、この場面ではラグランジュ補間の方が優れています。
ある秘密情報sのシェア化は以下のように行われます。
パーティ :
のシェア （ は が所持するシェア）
- 秘密情報提供者 は乱数 を用いて 次多項式 を作成する
- は各パーティ に の値を送信する()
- は受け取った を自分のシェアとする。つまり、 とする。
まとめ
この記事では、秘密分散法の中でも特に有名で理解しやすい 2 つの手法について簡単に説明しました。弊社が提供する一部サービスの根幹となる MPC とは、秘密分散法によってデータを分散したまま各種計算を行う技術です。なぜ分散した状態で計算可能であるのかはまた別の記事にて記していきます。