はじめに
この記事は 暗号技術 Advent Calendar 2024 の 9 日目の記事です。
前回の記事ではシャミアの秘密分散法の説明をしました。
今回は、シャミアの秘密分散法を Rust で実装していきます。
シャミアの秘密分散法の実装
まずは $(k, n)$ しきい値法を表す構造体 SecretSharing を定義します。
struct SecretSharing {
k: usize,
n: usize,
}
ここからは、この構造体にメソッドを実装していきます。
シェアの生成
シェアの生成方法は簡単に説明すると以下の通りです。
- 定数項を秘密情報 $S$ とするランダムな $k-1$ 次多項式 $f(x)$ を生成
- その多項式 $f(x)$ を使って $i$ 番目の人に $(i, f(i))$ をシェアとして配布
なので、上記の通りに関数を定義します。
impl SecretSharing {
fn generate_shares(&self, secret: f64) -> Vec<(f64, f64)> {
let polynomial = self.generate_polynomial(secret);
(1..=self.n)
.map(|i| (i as f64, self.calculate(i as f64, &polynomial)))
.collect()
}
}
ここで秘密情報やシェアの型を f64 としていますが、これは後のラグランジュ補間の実装を楽にするためです。
一般的には有限体上で計算されます。
特に素数を法とするモジュロ演算を用いるものが多いです。
また、今回のように f64 等の浮動小数点数を用いる場合、誤差に気を付ける必要があります。
ただし、今回はそういった誤差について意識した実装を行わないことにします。
多項式の生成
上記の share 関数内で使われている generate_polynomial 関数の定義をしていきます。
この関数は、ランダムな多項式を生成する関数でした。
ここでのランダムな多項式とは、係数がランダムな値になっている多項式のことです。
ただし定数項は秘密情報 $S$ となるようにし、次数は $k-1$ となるようにします。
impl SecretSharing {
fn generate_polynomial(&self, secret: f64) -> Vec<f64> {
let mut rng = rand::thread_rng();
let mut polynomial = vec![secret];
polynomial.extend((0..self.k - 1).map(|_| rng.gen::<f64>()));
polynomial
}
}
多項式として関数を返すようにしてもよいですが、ここでは係数の配列を返すようにしています。
また $x^i \; (i \geq 0)$ の係数は polynomial[i] と対応するように生成しています。つまり、次数の低いものの係数が配列の前へ来るようにしています。
多項式への代入
先程定義した関数は、多項式の係数の配列を生成する関数でした。
そこで、係数の配列として表された多項式に値を代入する calculate 関数を定義します。
impl SecretSharing {
fn calculate(&self, x: f64, polynomial: &[f64]) -> f64 {
polynomial
.iter()
.enumerate()
.fold(0.0, |acc, (i, a)| acc + a * x.powf(i as f64))
}
}
特に工夫はしておらず、定義通りに計算しています。
これで share 関数が動くようになり、シェアの生成ができるようになりました。
次はシェアから秘密情報を再構成できるようにしていきます。
秘密情報の再構成
秘密情報の再構成は簡単に説明すると以下の通りです。
- シェアの集合から多項式 $f(x)$ を補間
- この多項式 $f(x)$ の補間にはラグランジュ補間を用いる
- 補間した多項式 $f(x)$ に $0$ を代入し、定数項である秘密情報 $S$ を再構成
なので、上記の通りに関数を定義します。
fn reconstruct(&self, shares: &[(f64, f64)]) -> f64 {
assert!(shares.len() >= self.k);
self.interpolate(shares)
}
再構成するために必要な情報が足りない場合の処理として、ここでは assert をしています。
また、詳細は後述しますが、ここでは interpolate 関数で 1. と 2. を同時に行うことにしています。
ラグランジュ補間
点 $(x_i, y_i)$ の組が $k$ 個あり、それらの点から多項式 $f(x)$ を補間するとき、ラグランジュの補間公式は以下の形でした。
$$
f(x) = \sum_{i=1}^{k} y_i \prod_{j \neq i} \frac{x - x_j}{x_i - x_j}
$$
これをそのまま実装しても良いですが、多項式 $f(x)$ に $x = 0$ を代入することが分かっているので、
$$
f(0) = \sum_{i=1}^{k} y_i \prod_{j \neq i} \frac{-x_j}{x_i - x_j}
$$
と事前にしておき、これをそのまま実装します。
impl SecretSharing {
fn interpolate(&self, points: &[(f64, f64)]) -> f64 {
let xs = points.iter().map(|(x, _)| *x).collect::<Vec<_>>();
points
.iter()
.map(|(xi, yi)| {
xs.iter()
.filter(|&xj| xj != xi)
.fold(*yi, |acc, xj| acc * -xj / (xi - xj))
})
.sum()
}
}
これで、シェアの生成から秘密情報の再構成までの実装が完了したので、実際に動かしてみます。
動作確認
まずは、生成したシェアをそのまま渡したときに、秘密情報を再構成できるか見てみます。
let secret = 123456789.0;
println!("secret: {}", secret);
let ss = SecretSharing { k: 2, n: 3 };
let shares = ss.generate_shares(secret);
println!("shares: {:?}", shares);
let reconstructed_secret = ss.reconstruct(&shares);
println!("reconstructed_secret: {}", reconstructed_secret);
上記のコードは、シャミアの $(2, 3)$ しきい値法で試しているものです。
ランダムな部分があるので、多少異なる部分があると思いますが、実行結果は以下のようになりました。
secret: 123456789
shares: [(1.0, 123456789.56490812), (2.0, 123456790.12981625), (3.0, 123456790.69472437)]
reconstructed_secret: 123456788.99999993
浮動小数点数を用いているので、微妙に異なる値が出力されていますが、殆ど同じと言える値が出力されていそうです。
次に、生成されたシェアを使う個数が2つだけでも、秘密情報が再構成できるかを見てみます。
let reconstructed_secret = ss.reconstruct(&shares[0..2]);
println!("reconstructed_secret (1, 2): {}", reconstructed_secret);
let reconstructed_secret = ss.reconstruct(&shares[1..3]);
println!("reconstructed_secret (2, 3): {}", reconstructed_secret);
let reconstructed_secret = ss.reconstruct(&[shares[0], shares[2]]);
println!("reconstructed_secret (1, 3): {}", reconstructed_secret);
どのような2つの選び方でも、再構成ができるかを見ています。
実行結果は以下のようになりました。
reconstructed_secret (1, 2): 123456788.99999999
reconstructed_secret (2, 3): 123456789.00000003
reconstructed_secret (1, 3): 123456788.99999997
こちらも誤差がありますが、大体秘密情報と同じ値になっています。
おわりに
この記事では、Rust によるシャミアの秘密分散法の実装をしました。
次の記事では、視覚復号型秘密分散法と呼ばれる秘密分散法の説明と実装を書く予定です。