秘密分散について

秘密分散は 1979 年に Shamir 氏と Blakley 氏によって独立に提案されました。 大切な情報や秘密にしたい情報（以下、秘密情報）を複数のシェアと呼ばれるデータに分割し、ある決められた組み合わせのシェアが集まると秘密情報を復元できるが、その条件を満たさないシェアからは秘密情報を復元できない仕組みを提供する技術です。 シェア管理者（パーティ）の一部が不正な攻撃を受けても、秘密そのものが漏洩するリスクを低減できます。

秘密分散における登場人物として、「ディーラー」と「パーティ」がいます。

• ディーラー: 秘密情報そのものを持つもの
• パーティ: 秘密情報のシェアを持つもの

ディーラーが秘密情報から複数のシェアを作成し、それらを複数のパーティに配布します。

(k,n)しきい値法

$(k,n)$しきい値法は、$n$個のシェアのうち$k$個以上のシェアが集まれば秘密情報を復元できるが、$k-1$個以下のシェアでは秘密情報が一切漏洩しない方式です。 シェアのうち$n-k$個以下の破損や紛失、$k-1$個以下の盗難や漏洩に対して安全であるといえます。

ここでは、$(k,n)$しきい値法を構成する秘密分散法として、

• Shamir の秘密分散法
• 加法型秘密分散法
• 複製型秘密分散法

を紹介します。

Shamir の秘密分散法

Shamir の秘密分散法は、多項式補間（ラグランジュ補間）を利用して秘密情報を分散・復元する方式です。$f(0)=s(\text{秘密情報})$となる有限体上の$k-1$次多項式$f(x)$をランダムに生成し、その多項式上の$n$個の点をシェアとして扱います。$k$個の点が集まれば、$k-1$次多項式が一意に定まり、秘密情報$f(0)=s$を計算することができます。

シェアの作成例 - (3,4)Shamir の秘密分散法

• 秘密情報$s=31$、しきい値$k=3$、シェアの総数$n=4$
• $f(0)=s=31$となる$k-1=3-1=2$次多項式$f(x)$をランダムに生成
• $f(x)$上の$n=4$個の点をシェアとする

生成されたランダムな$f(x)=-5x^2+13x+31$上の点$(1,39),(2,37),(3,25),(4,3)$をシェアとして、各パーティに配布します。

• パーティ 1 のシェア: 39
• パーティ 2 のシェア: 37
• パーティ 3 のシェア: 25
• パーティ 4 のシェア: 3

秘密情報の復元例 - (3,4)Shamir の秘密分散法

• 3 個の点が集まれば、$3-1=2$次多項式が一意に定まり、秘密情報$f(0)=s=31$を計算可能
• 3 個未満では候補となる 2 次多項式が無数に存在するため、秘密情報$s$が求まらない

パーティ 1 のシェアだけ、パーティ 1 と 2 のシェアだけ、のように、$k-1=2$個以下のシェアでは、2 次多項式が定まりません。 パーティ 1 と 2 と 3 のシェア、パーティ 2 と 3 と 4 のシェア、のように、シェアが 3 個以上集まることで、2 次多項式が一意に定まり、秘密情報$f(0)=s=31$を計算することができます。

加法型秘密分散法

加法型秘密分散法は、総和が元の秘密値になるようにシェアを作成、分散する方式です。$(n,n)$加法型秘密分散法とも表記され、秘密情報を$n$個のシェアに分散した場合、全$n$パーティが復元に参加する必要があります。そのため、この方式を使用して$n$以外のしきい値を設定するには、複製型秘密分散法を用いるといった工夫が必要になります。

シェアの作成例 - (3,3)加法型秘密分散法

• 秘密情報$s=31$、しきい値$k=2$、シェアの総数$n=3$
• $s=31=(s_1+s_2+s_3) \space mod \space q$を満たすシェア$s_1,s_2,s_3$をランダムに生成
• $q$には素数あるいは$2^m$が選ばれることが多い

また、排他的論理和（exclusive-OR, XOR）演算を用いてシェアとすることもあります。この場合、各シェアを秘密情報と同等のデータサイズで管理できます。

$$s=s_1 \oplus s_2 \oplus s_3$$

• パーティ 1 のシェア: $s_1$
• パーティ 2 のシェア: $s_2$
• パーティ 3 のシェア: $s_3$

秘密情報の復元例 - (3,3)加法型秘密分散法

全てのパーティが協力することにより$n$個のシェアが全て集まり、

$$s=(s_1+s_2+s_3) \space mod \space q$$

または

$$s=s_1 \oplus s_2 \oplus s_3$$

により、秘密情報$s$を計算することができます。

複製型秘密分散法

複製型秘密分散法は、$(n,n)$加法型秘密分散法のシェアを一パーティに複数割り当てることで$(k,n)$しきい値法を構成する方式です。

シェアの作成例 - (2,3)複製型秘密分散法

• 秘密情報$s=31$、しきい値$k=2$、シェアの総数$n=3$
• $s=31=(s_1+s_2+s_3) \space mod \space q$を満たすシェア$s_1,s_2,s_3$をランダムに生成

ここまでは加法型秘密分散法と同様ですが、各パーティに複数のシェアを割り当てる点が異なります。

• パーティ 1 のシェア: $(s_1,s_2)$
• パーティ 2 のシェア: $(s_2,s_3)$
• パーティ 3 のシェア: $(s_3,s_1)$

秘密情報の復元例 - (2,3)複製型秘密分散法

任意の 2 パーティが協力することにより$s_1,s_2,s_3$が集まるため、加法型秘密分散法の復元と同様の手順で秘密情報$s$を計算することができます。