暗号応用技術
共通鍵暗号や公開鍵暗号等の暗号技術は，情報セキュリティの基盤技術として幅広く利用されてきている．これらの暗号技術は，データの単純な暗号化やディジタル署名以外にもさまざまな応用が考えられている．暗号応用技術として，分散暗号，ゼロ知識証明，秘密計算，各種暗号プロトコルなどの原理とその応用について解説する．
今後，これらの技術を用いたアプリケーションやシステムが増えていくものと思われる．これらの応用技術を理解する上での基礎知識やその原理を解説する．
分散暗号技術
秘密分散共有法
一定数以上の人数が集まると秘密情報 $S$ を復元できるが，それ以下では $S$ は全く分からないように $S$ を分散符号化する方法である．
応用として，以下のようなものが考えられる．
- 企業における機密データの管理（集中管理における事故や災害に対する危険性対策）
- 重要事項の判断を多数決で行う
秘密情報から複数の分散情報（シェア）を作り，参加者それぞれに1つの分散情報を配布する．秘密情報からシェアを作る参加者はディーラと呼ばれる．一定数以上の参加者が持つ分散情報を集めると，元の秘密情報を復元できる．しかし，それ以下の参加者が集まっても秘密情報は復元できない．この復元の条件により，以下の2種類の方法がある．
- 満場一致法
全員が集まらないと復元できない． - しきい値法
ある人数以上集まると復元できる．
例えば，満場一致法で参加者が3人，秘密情報が $n$ ビットの数 $S$ とするとき，分散情報 $v_1$，$v_2$，$v_3$ は，
\[ S = v_1 + v_2 + v_3 \bmod 2^n \]を満たす $n$ ビットの任意の数とすればよい．
また，満場一致法には AONT と呼ばれる秘密分散法がある (→ AONT)．
- 閾(しきい)値法 (SS)
分配者(ディーラ)が，ある秘密情報を $n$ 個の分割情報に分割し，それぞれを $n$ 人の分割情報保持者に配る．このとき，$k$ 人の分割保持者が集まると元の情報が復元できる方式を ($k, n$) しきい値法(Secret Sharing: SS)という．
しきい値法は，以下のような方式により実現できる．
$k - 1$ 次の多項式 \[ f(z) = a_0 + a_1 z + \cdots + a_{k-1}z^{k-1} \] において，多項式を満たす $k$ 個の点の組 $(z_i, f(z_i))\ (i=1, 2, \ldots,k)$ が与えられた時，多項式の $k$ 個の係数 $a_i$ は唯一定まり，$f(z)$ は以下のように与えられる (Lagrangeの補間多項式)． \[ f(z) = \sum_{i=1}^{k} f(z_i)\cdot L_i(z) \] \[ L_i(z) = \prod_{j=1,\ j \ne i}^{k}(z - z_j)/(z_i - z_j) \] ここで，$z = 0$ を代入すると上式は次のようになる． \[ f(0) = a_0 = \sum_{i=1}^{k} f(z_i)\cdot L_i(0) \] \[ \lambda_i = L_i(0) = \prod_{j=1,\ j \ne i}^{k} z_j/(z_j - z_i) \] $\lambda_i$ をLagrange係数と呼ぶ．
これより，の定数項 $a_0$ は $k$ 個の点の組 $(i, f(i))\ (i = 1,2,\ldots,k)$ を選択することにより求めることができる $(z_i = i$ とする)． $a_0$ が秘密情報に対応し，各 $f(i)$ が分割情報に対応する．すなわち，秘密情報を $x$，分割情報を $x_i$ とするとき， \[ x = \sum_{i=1}^{k} \lambda_i \cdot x_i \] となる．
分散情報を $n$ 個とし，そのうち $k\ (\le n)$ 個集まれば秘密情報が復元できるようにするには，$k - 1$ 次の多項式 $f(z)$ を選び $f(i)\ (i=1, 2, \ldots n)$ を分配すればよい．このうちの任意の $k$ 個を選択すれば復元できるが，$k - 1$ 個以下のいかなる分割情報を用いても秘密情報は復元できない． - VSS
しきい値法(SS)において，分配者が正しく分割情報を作らないと $k$ 個以上の分割情報を用いても秘密情報を復元できない．
Verifiable Secret Sharing (VSS)は，SSにおいて分割情報が正しく作成されていることを検証できる機能を付与したものである． 分散情報を受け取った各参加者が，秘密情報を復元できることを検証することができ，ディーラの不正を防止できる方式である．
VSSは，ゼロ知識証明を用いて実現でき，その手順は以下のとおりである．- 秘密情報 $x$ を持つ分配者は，$x$ を暗号化し $C(x)$ を生成する．
- 分配者は，$C(x)$ をSSを用いて各分割保持者 $j\ (j = 1,\ldots,n)$ に配る．
- 分配者は，各分割情報が上記の手順により正しく作成されていることを各分割保持者に対してゼロ知識証明により証明する．
分散復号
- RSA分散復号
満場一致法によるRSA分散復号を示す．- 分散秘密鍵
RSA暗号の公開鍵を $(e,\ n)$，秘密鍵を $d$ とするとき，$N$ 人の参加者は \[ d = \sum_{i=1}^N d_i \bmod \lambda(n) \] を満たす分散秘密鍵 $d_i$ をそれぞれ保持する． - 暗号化
暗号文の送信者は，公開鍵 $(e, n)$ を用いてメッセージ $m$ を暗号化し，暗号文 $c$ を求める． - 復号
$N$ 人の参加者は，暗号文 $c$ を復号するため，協力して以下の計算を行う．- 分散秘密鍵 $d_i$ を持つ参加者は，$m_i = e^{d_i} \bmod n$ を計算し，公開する $(i = 1,\ldots,N)$．
- 公開された $m_i\ (i = 1,\ldots,N)$ を用いて \[ m = \prod_{i=1}^N m_i \bmod n \] を計算する．
- 分散秘密鍵
- 閾値型分散復号
公開鍵で暗号化した情報を $N$ 人の参加者のうち $t$ 人が協力することにより，情報の復号が可能な方式を示す．
- パラメータ生成
パラメータ $p$，$q$，$g$ を $p$ のビット長を指定して生成する．ここで，$p$，$q$ は素数で $q|p-1$，$g$ は位数が $q$ となるような群 ${\mathbb{F}_p}^*$ の部分群 $G$ の元. - 鍵生成
参加者 $i\ (i = 1,\ldots,N)$ が以下の処理を行い，公開鍵と分散秘密鍵を求める．- 多項式生成
閾値 $t$ を指定して $t - 1$ 次の多項式 $f_i(x)$ を生成する． ここで，各係数 $a_{i,j}$ は $0$ 以上 $q - 1$ 以下の整数である． - 秘密鍵生成
分散秘密鍵 $f_i(j)\ (j = 1,2,\dots,N)$ を計算する． - 分散秘密鍵の配布
参加者 $j$ に，分散秘密鍵 $f_i(j)\ (j = 1,\ldots,N)$ を配布する． - 公開値生成
参加者 $i$ は，以下を計算する． \[ G_{i, j} = g^{f_i(j)} \bmod p\ (j = 1,\ldots,N) \] - 公開鍵生成
公開鍵
\[ T=\prod_{1\le i,j \le n}G_{i,j}^{\lambda_j}\ (=g^{\sum a_{i,0}}\ \bmod p) \] を計算する．ここで，$j = j_1,\ldots,j_t\ (j_1,\ldots,j_t$ は $1$ 以上 $N$ 以下の相異なる整数)．$\lambda_j$ は，Lagrange係数である．
- 多項式生成
- 暗号化
暗号化を実行する参加者は，公開鍵 $T$ を用いて文書 $m$ を ElGamal暗号により暗号化し，暗号文 $c$ を求める． \[ c = (g^r \bmod p,\ mT^r \bmod p) \] ここで，$r$ は $1$ 以上 $p - 1$ 以下の乱数である． - 復号
- 分散復号情報の生成
参加者 $i$ は，暗号文 $c$ の部分情報 $g^r$ と自身の秘密鍵 $f_j(i)$ を用いて \[ H_i=(g^r)^{\sum_{j=1}^{N} f_j(i)}\ \bmod p\ (j=1, \ldots, N) \] を計算する． - 復号処理
復号を実行する参加者は，閾値 $t$ 以上の数の $H_i$ と暗号文の部分情報 $mT^r$ を用いて以下の処理 (ElGamal暗号の復号)を行い，復号結果 $m$ を得る． \[ \tilde{g} = \prod_{1\le i \le N}H_i^{\lambda_j} \bmod p \] \[ mT^r/\tilde{g}\ (= m) \] ここで，$i=1,\ldots,N$，$j=j_1,\ldots,j_t\ $($j_1,\ldots,j_t$ は $1$ 以上 $N$ 以下の相異なる整数).
- 分散復号情報の生成
- パラメータ生成
／