【秘密計算】Replicated Additive Secret Sharing とは？高速乗算可能な秘密分散法

Posted at 2020-12-14

はじめに

この記事では、秘密分散法の一つであるReplicated Additive Secret Sharing について解説します。

秘密分散法には、大きく2つのプロトコルがあります。

Shamir’s Secret Sharing Scheme(シャミア秘密分散法)
Additive Secret Sharing Scheme(加法的秘密分散法)

今回解説する方法は後者のAdditive Secret Sharing Scheme に属する方法となります。

この記事では基本的な秘密分散法についての詳しい解説は省きます。

秘密分散法の基本的な技術は【技術】秘密分散法とは。数式を用いて解説の記事を参考にしてください。

今回のReplicated Additive Secret Sharing を用いることのメリットは、3パーティである場合に非常に簡単な方法でシェア同士の乗算と加算が実現可能であることです。

それでは詳しく見ていきましょう。

Replicated Additive Secret Sharing の方法

Replicated Additive Secret Sharing は3パーティ以上に適用できる方法ですが、3パーティの場合が最も効率が良いため、ここでは3パーティの場合について解説します。この場合(2, 3) 閾値秘密分散となり、2つのパーティが持つシェアを集めることで秘密情報を復元することができます。

あるパーティ$P_i$ が持つ秘密情報$s$ をシェア化する方法は以下です。

パーティ集合 : {$P_1, P_2, P_3$}

$s$ のシェア : {$s_1, s_2, s_3$} (ただし、$s = s_1 + s_2 + s_3$)

$P_i$ は乱数$s_1, s_2$ を生成し、$s_3 = s - s_1 - s_2$ を計算する。
$P_i$ は$P_{j\neq i}$ に$s_j, s_{j + 1}$ を送信する。ただし、便宜上$s_4$ は$s_1$ とみなす。
$P_{j \neq i}$ は受け取った2つのシェアを自分のシェアとする。

結果的にシェアは以下の状態で保持されます。

$P_1 : (s_1, s_2)$

$P_2 : (s_2, s_3)$

$P_3 : (s_3, s_1)$

この場合、明らかに2つのパーティが持つシェアを足し合わせることで、秘密情報$s$ が復元できることが分かります。

このように、各パーティがシェアのレプリカを保持する仕組みであることから、"Replicated" という名称になっていることが理解できます。

加算と乗算の方法

加算と乗算の方法を見ていきます。

まず、シェア同士の加算については明らかに準同型性を持っているため、各パーティがローカルで加算を行うことで実現できます。

また、定数による加算と乗算も同様です。

次に、シェア同士の乗算については、直接的にシェア同士を乗算することはできません。したがって、以下に説明するような方法を用いて実現します。

秘密情報$a$, $b$ を用いて$c = ab$ となる$c$ のシェアを計算することを目指します。

$a$ のシェア : {$a_1, a_2, a_3$}

$b$ のシェア : {$b_1, b_2, b_3$}

$P_i$ は$u_i = a_ib_i + a_ib_{i+1} +a_{i+1}b_i$ をローカルで計算する。
$P_i$ は$u_i$ を$P_{i - 1}$に送信する。ただし、便宜上$P_0$ は$P_3$とする。
$P_i$ は$c$ のシェアとしてそれぞれ$c_i = u_i, c_{i+1} = u_{i + 1}$とする。

この時$c$ は以下のように整理できる。

$$\begin{array}{ll} c&= (a_1 + a_2 + a_3)(b_1 + b_2 + b_3)\ &= a_1b_1 + a_1b_2 + ... + a_3b_2 + a_3b_3 \ &= u_1 + u_2 + u_3 \ &= c_1 + c_2 + c_3 \end{array}$$

結果的に計算結果のシェアは以下のように保持されます。

$P_1 : (c_1, c_2)$

$P_2 : (c_2, c_3)$

$P_3 : (c_3, c_1)$

この場合、明らかに2つのパーティが持つシェアの値を足し合わせることで$c$ が復元できることが分かります。

したがって、$c=ab$ となる$c$ のシェアを計算し、各パーティがシェアを保持することができました。

以上の方法を用いることで、Replicated Aditive Secret Sharing では乗算と加算を実現しています。ただし、パーティ数$N$に応じてシェアのデータ数、通信回数が$O(N^2)$で増加するため、今回紹介した3パーティでの適用が最も推奨されます。