アルゴリズム論特論（塩田）2024年度

アルゴリズム論特論（塩田）第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}}}$

秘密分散

　秘密分散とは次の要請を満たす仕組みのことです。

秘密分散の要請

このとき、

$t$ を分割数、

$k$ を閾(しきい)値と呼ぶ。

　例えば、暗号化された企業秘密の復号鍵が

$x$ であるとし、

$t$ 人の重役にはその部分情報だけを教えておくとします。重役のうち

$k$ 人が合意すれば復号ができますが、

$k-1$ 人以下の合意では復号できない、そういう仕組みです。

中国剰余アルゴリズムの利用

中国剰余アルゴリズムを利用した設計

要請(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$ -ビット以上不足しています。

※　実用に当たってはもう少し複雑な設計をすることが多いですが、基本的なアイデアはこれと同じです。