シャミアの秘密分散法入門 理論編

## はじめに

この記事は 暗号技術 Advent Calendar 2024 の 8 日目の記事です。

https://qiita.com/advent-calendar/2024/cryptography

## 秘密分散について

暗号技術の一つに秘密分散というものがあります。
その名の通り、秘密としたい情報を何人かで分割して保管する方法のことです。
また、この分割した情報のことをシェアといいます。

この記事では、秘密分散の中でも $(k, n)$ しきい値法と呼ばれる秘密分散法、特にシャミアの秘密分散法と呼ばれるものを扱います。

### (k, n) しきい値法

:::note info
$(k, n)$ は k-out-of-n と読みます。
:::

秘密情報を $n$ 個のシェアに分けるとき、以下の性質を満たすようなものを $(k, n)$ しきい値法といいます。

- シェアが $k$ 個以上集まった場合、元の情報を再構成できる
- シェアが $k$ 個未満の場合、元の情報が再構成できない

また、元の情報を再構成できる集合のことを qualified set といい、
元の情報が**全く**得られないような集合のことを forbidden set といいます。

シェアが $k$ 個未満でも情報が部分的に得られるような秘密分散法もありますが、この記事ではそのような秘密分散法は扱わないことにします。
つまり、任意のシェアの集合が qualified set もしくは forbidden set のどちらかとなるような方法を考えます。

ここからは実際にそのような $(k, n)$ しきい値法を考えていきます。

### シンプルな (k, n) しきい値法

ここでは簡単のため、秘密情報を何かしらの方法で、任意の長さの二進数に変換したものとし、その値を秘密情報 $S$ とします。

最初から任意の $k$ についての方法を考えるのは難しいので、まずは $k = n$ の場合について考えます。

#### k = n の場合

まず、シェアとして、秘密情報 $S$ と同じ長さのランダムな二進数 $P_i$ ($1 \leq i < n$) を $n-1$ 人に渡します。
そして、残った一人に

$$
P_n = S \oplus P_1 \oplus P_2 \oplus \cdots \oplus P_{n-1}
$$

をシェアとして渡します。($\oplus$ は排他的論理和)

:::note info
排他的論理和でなくとも、群の公理を満たすような演算であれば良いです。
:::


これにより全員が集まったとき、排他的論理和の特性から

$$
P_1 \oplus P_2 \oplus \cdots \oplus P_{n} = S
$$

となるため再構成ができます。
また、人数が $n$ 人未満のとき、例えば $2$ から $n$ までの人が集まったとき、

$$
P_2 \oplus P_3 \oplus \cdots \oplus P_n = S \oplus P_1
$$

となり $P_1$ がランダムな二進数であるため $S \oplus P_1$ もランダムな二進数になります。
よって、この場合はいかなる情報も漏れないことが分かります。
他の集合の場合も同様です。

次に任意の $k$ ($1 \leq k \leq n$) の場合を考えます。

#### 任意の k (1 ≤ k ≤ n) の場合

サイズが $k$ となるような全ての集合に対して $k = n$ の場合と同じような手法をとることで実現できます。

例えば $(2, 4)$ のときには、

- 1番目と2番目の人に $P_{1,1}$ と $S \oplus P_{1,2}$
- 1番目と3番目の人に $P_{2,1}$ と $S \oplus P_{2,2}$
- 1番目と4番目の人に $P_{3,1}$ と $S \oplus P_{3,2}$
- 2番目と3番目の人に $P_{4,1}$ と $S \oplus P_{4,2}$
- 2番目と4番目の人に $P_{5,1}$ と $S \oplus P_{5,2}$
- 3番目と4番目の人に $P_{6,1}$ と $S \oplus P_{6,2}$

のシェアを渡します。
これによって、2人以上が集まれば秘密情報 $S$ を再構成できます。

上記の手法では $n$ が大きくなると、必要なシェアの数がかなり大きくなってしまいます。
具体的には $k \cdot {}_nC_k$ 個のシェアが必要になります。

これはかなり非効率的なので、より良い方法としてシャミアの秘密分散法を扱います。

### シャミアの秘密分散法

$k+1$ 個の点の情報から、それらの点を通る $k$ 次以下の曲線が一意に定まるという性質を用いて $(k, n)$ しきい値法を実現する方法をシャミアの秘密分散法といいます。
上記の性質は 2点から直線の式を求められることや、3点から放物線の式を求められることを思い出すと、理解しやすいかもしれません。

まずは $(2, 3)$ しきい値法をシャミアの秘密分散法で考えてみます。
また、ここでは秘密情報を何かしらの方法で、任意の実数に変換したものとし、その値を秘密情報 $S$ とします。

#### シャミアの (2, 3) しきい値法

まず、定数項を $S$ とするランダムな $1$ 次多項式 $f(x)$ を生成します。

$$
f(x) = A_1 x + S
$$

ここで $A_1$ はランダムな実数です。
この関数を利用し、$i$ 番目の人にシェアとして $(i, f(i))$ のペアを渡します。

:::note info
シェアとして渡す情報は、全ての人に渡す点が相異なるものであればよいので、実数 $x_i \\; (\neq 0)$ を用いて $(x_i, f(x_i))$ をシェアとしても良いです。
:::

これにより2人以上が集まったとき、2点の情報から直線の式が求められ $S$ を再構成することができます。

また2人未満、つまり1人の場合、1点の情報から直線を一つに定めることはできず、$y$ 切片として任意の値をとることができることから、いかなる情報も漏れないことが分かります。

#### シャミアの (k, n) しきい値法

同様にして任意の $k, n$ の場合でも、ランダムな $k-1$ 次多項式 $f(x)$ を生成して、シェアとして $i$ 番目の人に $(i, f(i))$ を渡せば良いです。

ここで問題となるのが、相異なる $k$ 点の情報から $k-1$ 次多項式 $f(x)$ を復元する方法ですが、これはラグランジュの補間公式を用いることで求めることができます。
この辺りは下記のサイトの説明が理解しやすいと思います。

https://manabitimes.jp/math/725#5

このサイトには $k$ 点が与えられたときに $k-1$ 次以下の多項式が構成できることの証明が書かれています。
なので $k-1$ 点以下では情報が漏れないことの証明をここでしていきます。

一般的に書くと煩雑になってしまうため $1$ 番目から $k-1$ 番目までの $k-1$ 人のシェアが集められているとします。
このとき、ある多項式 $f(x)$ が、シェアとして集められた全ての点を通り、$f(0) = C$ ($C$ は任意の定数) とできれば、証明として十分です。

なので、実際にそのような多項式 $f(x)$ を構成します。

まず、任意の定数 $C'$ を用いて、$k-1$ 次多項式 $g(x)$ を以下のように定義します。

$$
g(x) = C' \prod_{i=1}^{k-1}(i-x)
$$

この $g(x)$ は $x = 1, 2, \cdots k-1$ のときに 0 となり、それ以外のときは 0 になることはありません。
次に、シェアとして集められた $k-1$ 点を通る $k-2$ 次以下の多項式 $h(x)$ を用いて、

$$
f(x) = g(x) + h(x)
$$

を定義します。
この $f(x)$ は $x = 1, 2, \cdots k-1$ のとき $h(x)$ になります。
よって、この $f(x)$ は集められた $k-1$ 点を通る多項式であることが分かります。
また $x = 0$ のとき、

$$
f(0) = h(0) + C' \prod_{i=1}^{k-1} i
$$

となります。
$C'$ は任意の定数なので、この値も任意の値を取ることができます。

これで、シェアとして集められた全ての点を通り、$f(0) = C$ ($C$ は任意の定数) となる多項式 $f(x)$ が実際に構成できました。
よって $k-1$ 点の情報からは、いかなる情報も漏れないことが分かります。

シェアの集合が異なる場合も同じような証明をすればよいです。

## おわりに

この記事では、シャミアの秘密分散法による、秘密情報の分割方法とその再構成の方法を説明しました。
次の記事では、プログラムによるシャミアの秘密分散法の実装を書く予定です。