アルゴリズム論特論（塩田）第14回 (3) 秘密分散
前へ / 戻る / 次へ
$\newcommand{\ol}[1]{\overline{#1}}$
$\newcommand{\znz}[1]{\mathbb{Z}/#1 \mathbb{Z}}$
$\newcommand{\znzc}[1]{(\mathbb{Z}/#1 \mathbb{Z})^{\times}}$
$\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$
秘密分散
秘密分散とは次の要請を満たす仕組みのことです。
秘密分散の要請
- 秘密にしたい情報 $x$ から $t$ 個の部分情報
$x_1$, $x_2$, $\cdots$, $x_t$
を作る。
- $t$ 個の部分情報のうち $k$ 個があれば元の情報 $x$ を計算できる。
- $t$ 個の部分情報のうち $k-1$ 個以下しか無ければ元の情報 $x$ は計算できない。
このとき、$t$ を分割数、$k$ を閾
(しきい)値と呼ぶ。
例えば、暗号化された企業秘密の復号鍵が $x$ であるとし、
$t$ 人の重役にはその部分情報だけを教えておくとします。
重役のうち $k$ 人が合意すれば復号ができますが、
$k-1$ 人以下の合意では復号できない、
そういう仕組みです。
中国剰余アルゴリズムの利用
中国剰余アルゴリズムを利用した設計
- $x$ は約 $N$-ビットの情報とする。
- $N/k$-ビット強の、互いに素な $t$ 個の法
$m_1$, $m_2$, $\cdots$, $m_t$ を作る。
- $x_i = x \,\%\, m_i$ とする。
要請(2)を満たすこと $k$ 個の $x_i$ から中国剰余アルゴリズムを用いて連立合同式
$y \equiv x_i \pmod{m_i}$
の解 $y$ を求めれば、$y$ を定める法のビット長は
$(N/k) \times k = N$ 強
ゆえ、$y$ は元の $x$ に等しくなります。
要請(3)を満たすこと $k-1$ 個以下の $x_i$ から連立合同式
$y \equiv x_i \pmod{m_i}$
の解 $y$ を求めても、$y$ を定める法のビット長は
$(N/k) \times (k-1)$
以下ゆえ、$y$ の情報はまだ約 $N/k$-ビット以上不足しています。
※ 実用に当たってはもう少し複雑な設計をすることが多いですが、
基本的なアイデアはこれと同じです。