秘密計算手法その２（秘密分散法）

EAGLYSアドベントカレンダー12日目の記事です。

この記事は？

この記事は暗号技術の基礎の一つである「秘密分散法」について解説します！秘密分散法は代数の知識がふんだんに使われたとてもおもしろい技術で、秘密計算の一種であるマルチパーティ計算を中心に利用されています！では実際に数式を用いつつ、どうやって秘密分散が実現されているのか、見ていきましょう。

※秘密分散は多項式補間や多項式を使った書き方がされることが多いのですが、この記事では線形代数を使って秘密分散する試みをしています。

秘密分散法とは？？

まずは数式を使わずに秘密分散を紹介します。

秘密分散法(Secret Sharing Scheme)とは、秘密をシェアと呼ばれる欠片に分割して管理する方式です。分割した秘密は一定数集めると、復元することが出来ます。この一定数をしきい値と呼ぶことにします。

特徴的な性質として、しきい値より少ない個数のシェアから秘密の情報を一切得られないというものがあります。例えば、秘密$s$を5つのシェアに分割し、しきい値を$3$としましょう。この時、

• 2つのシェアから秘密の情報を得ることはできない。
• 3つのシェアから秘密の情報を得ることはできる。

となります。この安全性は情報理論的安全性といい、RSA暗号などで用いられている計算量的安全性より強固なものです。つまり秘密分散においては

• どんなに膨大な計算資源があってもしきい値未満のシェアから秘密を復元することはできない

ということです。この安全性を持つ暗号としてはワンタイムパッドが挙げられます。

秘密分散の数式による定義

秘密$s$を体の要素、つまり$s\in F$とし、秘密分散の参加者を$n$人とし、その集合を

\mathcal{P}=\{P_1,P_2,\dots,P_n\}

とします。しきい値を$k$とし、各$n$人に配布するシェアを$\mathbf{v}=\{v_1,v_2,\dots,v_n\}$とします。このアルゴリズムには$n$人の参加者に加え、ディーラー$\mathcal{D}$という信頼された第三者が存在するとします。

すると、秘密分散は以下の二つのアルゴリズムから定義されます。以下のアルゴリズムはいずれも$\mathcal{D}$が行うものです。

• 秘密$s$をシェア$\mathbf{v}$に分割する$Share(s)$

• シェア$\mathbf{v}$のうち$k$個から秘密$s$を復元する$Reconst(v_1,v_2,\dots,v_{k})$

$Share(s)$では秘密$s$を$n$個のシェアに分割し$n$人に配布します。一方$Reconst(v_1,v_2,\dots,v_{k})$は分割したシェア$\mathbf{v}=(v_1,\dots,v_n)$の$v_i$のうち、$k$個を集め、復元します。

この定義について次のセクションではシャミアの秘密分散法を使って具体的に説明します。以降は簡単のため、$\boldsymbol{v}$のうち$k$個を$v_1,v_2,\dots,v_k$とします。

シャミアの秘密分散法

シャミアの秘密分散法は1979年にアディ・シャミアによって作られた技術です。(k,n)しきい値秘密分散法の代表例です。

まずはアルゴリズムから書いて、記号については後に説明します。ここでは多項式を用いたよく見かける定義と線形代数による同値な定義を紹介します。なお、$n$と$k$と$i$以外は体の要素です。

多項式による定義

Share

以下の手順をディーラーが行う。

1. 秘密情報を$s$とする。
2. 下の形をした適当な$k-1$次元多項式$f(x)$を生成する。
3. $v_i=(i,f(i))(i=1,2,\dots,n)$とする。$v_i$をそれぞれ$P_i$に送る。

f(x) = s + a_1\cdot x + a_2\cdot x^2 + \dots + a_{k-1} x^{k-1} 

Reconst

1. シェアを$k$個以上集める。

2. $v_i=(x,y)=(i,f(i))$より多項式の通る点が$k$個分かるので、ラグランジュの多項式補間で多項式$f(x)$を復元する。

3. $f(0)$を出力する。

線形代数らしい定義

Share

以下の手順をディーラーが行う。

1. 秘密情報を$s$、$a_1,\dots,a_n$を適当な値とするベクトル$\boldsymbol{s}=(s,a_1,\dots,a_{k-1})$を生成する。
2. 以下を計算をする。$v_i=(i,f_i)$をそれぞれ$P_i$に送る。($X$の定義は後述)

    \boldsymbol{X} \cdot \mathbf{s} =
    \left(
    \begin{array}{c}
    f_1 \\ 
    f_2 \\
    f_3 \\
    \vdots\\
    f_n 
    \end{array}
    \right)

Reconst

1. 係数行列を$\boldsymbol{X}$とし、未知数を$\boldsymbol{s}$とする下の連立一次方程式を解く。

2. $\boldsymbol{x}=(1,x_0,x_0^2,\dots,x_0^{k-1})=(1,0,0,\dots,0)$とし、$\boldsymbol{x}\cdot \boldsymbol{s}$を計算する。$s$を出力する。

\begin{aligned}
    s + x_1a_1 + x_1^2a_2 +& \dots + x_1^{k-1}a_{k-1} = f_1\\
    s + x_2a_1 + x_2^2a_2 +& \dots + x_2^{k-1}a_{k-1} = f_2\\
                           & \vdots\\
    s + x_ka_1 + x_k^2a_2 +& \dots + x_k^{k-1}a_{k-1} = f_k\\
\end{aligned}

解説

線形代数の定義を用います。まずは$Share$についてです。ベクトル$\boldsymbol{s}$は次のようなベクトルです。

(s,a_1,\dots,a_{k-1})

秘密$s$を一番目に含んでおり、それ以外の$a_1,\dots,a_{k-1}$は乱数です。この乱数$a_1,\dots,a_{k-1}$は$\mathcal{D}$しか知らない秘密の値です。これらの値がわからないことを利用して秘密を漏らさないようにします。

行列$\boldsymbol{X}$は次のようなヴァンデルモンド行列っぽい行列です。

    \left(
    \begin{array}{ccccc}
    1 & x_1 & x_1^2 & \dots & x_1^{k-1} \\
    1 & x_2 & x_2^2 & \dots & x_2^{k-1} \\
    1 & x_3 & x_3^2 & \dots & x_3^{k-1} \\
    \vdots　& \vdots & \vdots & \ddots & \vdots \\
    1 & x_n & x_n^2 & \dots & x_n^{k-1} \\
    \end{array}
    \right)

$n=k$でない限り、正方行列ではないのでヴァンデルモンド行列ではありません。さて、これらを用いると手順$2$は次のように表せます。

    X \cdot \boldsymbol{s} 
　　=
    \left(
    \begin{array}{ccccc}
    1 & x_1 & x_1^2 & \dots & x_1^{k-1} \\
    1 & x_2 & x_2^2 & \dots & x_2^{k-1} \\
    1 & x_3 & x_3^2 & \dots & x_3^{k-1} \\
    \vdots　& \vdots & \vdots & \ddots & \vdots \\
    1 & x_n & x_n^2 & \dots & x_n^{k-1} \\
    \end{array}
    \right)
    \left(
    \begin{array}{c}
    s \\ 
    a_1 \\
    a_2 \\
    \vdots\\
    a_{k-1} 
    \end{array}
    \right) = 
    \left(
    \begin{array}{c}
    v_1 \\ 
    v_2 \\
    v_3 \\
    \vdots\\
    v_n 
    \end{array}
    \right)

表現行列$X$が存在することから関数$Share$は線形写像です。このように線形写像で表せる秘密分散方式を線形秘密分散方式といいます。このアルゴリズムは$\boldsymbol{v}=(v_1,v_2,\dots,v_n)^T$を出力して、$v_i$を$P_i$に送ります。$v_1$は$P_1$に、$v_2$は$P_2$に...といった具合です。また、この行列表現の方程式はReconstの連立１次方程式と同じものです。

次はReconstについてです。連立１次方程式のうち、公開されている情報を整理します。分かっているのは

• $(v_1,v_2,\dots,v_k)$
• $(v_1,v_2,\dots,v_k)$に含まれる$f_1,f_2,\dots,f_k$
• $(v_1,v_2,\dots,v_k)$から求まる行列$\boldsymbol{X}$

ベクトル$\boldsymbol{s}=(s,a_1,\dots,a_{k-1})$を未知数とみなします。復元時に現れる行列は正方行列なのでヴァンデルモンド行列になってます。後ほど述べますが、この連立１次方程式の解は一意なので方程式を解けば解は一意に求まります。

2番目の手順では、$\boldsymbol{x}$の定義と$\boldsymbol{s}$の定義から$\boldsymbol{x}\cdot \boldsymbol{s}=s$であることがわかります。

\boldsymbol{x}\cdot \boldsymbol{s}=1\cdot s+0\cdot r_1+\dots+0\cdot r_{k-1}=s

##　秘密が漏れない理由

ヴァンデルモンド行列は$x_1,x_2,\dots,x_n$が全て異なれば、逆行列が存在します。つまり、ヴァンデルモンド行列は全ての行ベクトルが一次独立で、完全階数です。解の自由度の概念を思い出すと、

---

解の自由度＝行数ー階数

---

です。完全階数かつ、正則なので、行数＝階数になり解の自由度は$0$になります。つまり、解は一意に定まります。
一方、集まったシェアが$k$未満なら$\boldsymbol{X}$は正則にならないので解の自由度が0にならず解は不定です。よって、解が一意に定まらないことになります。

これを秘密分散に当てはめると、しきい値$k$にならない限り解の自由度は$0$にならないので解は一意に定まらないことになります。つまり、$s$を未知の変数と見なすと

    \left(
    \begin{array}{ccccc}
    1 & x_1 & x_1^2 & \dots & x_1^{k-1} \\
    1 & x_2 & x_2^2 & \dots & x_2^{k-1} \\
    1 & x_3 & x_3^2 & \dots & x_3^{k-1} \\
    \vdots　& \vdots & \vdots & \ddots & \vdots \\
    1 & x_n & x_n^2 & \dots & x_n^{k-1} \\
    \end{array}
    \right)
    \left(
    \begin{array}{c}
    s \\ 
    a_1 \\
    a_2 \\
    \vdots\\
    a_{k-1} 
    \end{array}
    \right) = 
    \left(
    \begin{array}{c}
    v_1 \\ 
    v_2 \\
    v_3 \\
    \vdots\\
    v_n 
    \end{array}
    \right)

は連立$k$変数一次方程式とみなせます。この$k$変数の解が不定ならば

• 解のうちどれが秘密かわからないので秘密の情報は漏れていない

ということになります。逆に解の自由度が$0$になっていれば解は一意に定まり、秘密を確実に復元できることになります。

この事実はくだけた言い方をすると、式の数（集まったシェアの数、または行数）と変数の数（多項式の次元数、列数）が同じである必要があるということです。

プログラム

プログラムを書いてみました。今回はRustを使って書いています。Pythonも追加できたらします。rust-ndarrayとrust-ndarray-linargを利用しています。（ベクトルは有限体上であるべきなのですが、例示する分には問題ないので実数体になっています。また、シェアは実装の都合で$(i,f_i)$ではなく$f_i$になっています。）

extern crate ndarray;
extern crate ndarray_linalg;
extern crate intel_mkl_src;

use ndarray::*;
use ndarray_linalg::*;

fn share(secret: f64)->Array1<f64>{
    //ヴァンデルモンドっぽい行列
    //i=1,2,3...,nなので必ずこの値になっている
    let mat_x:Array2<f64> = arr2(&[
        [1., 1., 1.],
        [1., 2., 4.],
        [1., 3., 9.],
        [1., 4., 16.],
        [1., 5., 25.],
    ]);

    //secret以外は適当な数をいれておく
    let s : Array1<f64> = arr1(&[secret,2.,3.]);

    //X・s = v 
    return mat_x.dot(&s);
}

fn reconst(shares:&mut Array1<f64>,k: usize)->f64{
    //ヴァンデルモンド行列
    //i=1,2,3...,nなので必ずこの値になっている
    let mat_x:Array2<f64> = arr2(&[
        [1., 1., 1.],
        [1., 2., 4.],
        [1., 3., 9.],
    ]);

    let x = arr1(&[1.,0.,0.]);

    //シェアのうちk個を集める。
    let vd = shares.slice_mut(s![0..k]);

    //X*s = fを解く
    let ans = mat_x.solve_into(vd).unwrap();

    //x*s = secret
    let secret = &x.dot(&ans);

    return *secret;
}


//体を成すために、係数はf64にする
fn main() {
    //参加者数をn、しきい値をkとする。nは書いていない
    let k = 3;
    let secret = 8.;

    let mut shares = share(secret);
    let secret = reconst(&mut shares,k);

    println!("{}", secret); // 結果：8
}

という感じになります。

準同型性

さて、秘密分散は線形写像によって行われるので加法準同型性を持っています。上のmain関数を次のように変更します。

fn main() {
    let k = 3;
    let secret1 = 8.;
    let shares1 = share(secret1);

    let secret2 = 12.;
    let shares2 = share(secret2);

    let mut shares3 = &shares1 + &shares2;

    let secret = reconst(&mut shares3,k);

    println!("{}", secret); // 結果：20
}

線形写像の定義より、$f(x+y)=f(x)+f(y)$です。結果が$8+12=20$であることからも準同型性を持つことが確認できます。

まとめ

この記事では秘密分散について紹介しました。秘密分散は属性ベース暗号のようなアクセス権を複雑に制御する必要がある暗号や、多人数での秘密計算において秘密を配布するのに活躍します。数学的にも面白い技術なのですが、ユースケースも広いです！

参考

• 光成　滋生　クラウドを支えるこれからの暗号技術 2015 秀和システム 　
• 萩田 真理子　暗号のための代数入門 2011 サイエンス社