利用者:Roget/試訳/Shamirの秘密分散法

en:Shamir's Secret Sharing 12:24, 2 February 2009

Shamirの秘密分散法とは暗号理論における秘密分散を実現する方式の1つである。 秘密はいくつかの部分に分けられ、各参加者に分け与えられる。秘密を復元するには、いくつか、または、全てを集めることが必要である。

全員が集まって秘密を復元するのは現実的では無い。 そこで我々は閾値方式を用いる。これはLiuの問題として知られる。 "11人の科学者が秘密のプロジェクトに参加しているとしよう。キャビネットに書類を保管する。キャビネットの鍵は6人以上が一度に集まらないと開けられないようにしたい。"

Shamir's Secret Sharing is an algorithm in cryptography. It is a form of secret sharing, where a secret is divided into parts, giving each participant its own unique part, where some of the parts or all of them are needed in order to reconstruct the secret.

Counting on all participants to combine together the secret might be impractical, and therefore we may use the threshold scheme, as demonstrated by Liu's problem: "11 scientists are working on a secret project. They wish to lock up the documents in a cabinet so that the cabinet can be opened if and only if 6 or more of the scientists are present".

Mathematical definition

目標はデータ$D$を、以下の条件を満たす、データ$D_{1},\cdots ,D_{n}\,\!$に分割することである。

1. $k\,\!$個以上の$D_{i}\,\!$を集めれば、簡単に$D\,\!$を計算できる。
2. $k-1\,\!$個以下の$D_{i}\,\!$を集めても、$D\,\!$を完全に決定できない（どのような値にも等確率でなり得る）。

このような方式は$\left(k,n\right)\,\!$閾値分散法と呼ばれる。もし、$k=n\,\!$ならば、すべての参加者が集まらないと秘密を復元できない。

Formally, our goal is to divide some data $D$ (e.g., the safe combination) into $n\,\!$ pieces $D_{1},\cdots ,D_{n}\,\!$ in such a way that:

1. Knowledge of any $k\,\!$ or more $D_{i}\,\!$ pieces makes $D\,\!$ easily computable.
2. Knowledge of any $k-1\,\!$ or fewer $D_{i}\,\!$ pieces leaves $D\,\!$ completely undetermined (in the sense that all its possible values are equally likely).

This scheme is called $\left(k,n\right)\,\!$ threshold scheme. If $k=n\,\!$ then all participants are required together to reconstruct the secret.

シャミアの秘密分散法

Adi Shamirのアイデアは閾値法である: 2点あれば, その点を通る直線を一意に定義できる. 同様に3点あれば放物線を, 4点あれば3次曲線を定義できる. すなわち, $k\,\!$点で, 次数$k-1\,\!$の1変数多項式を一意に定義できる.

今, 秘密となる自然数$S\,\!$を分散する$\left(k,n\right)\,\!$閾値法を構成したいとしよう. ($k<n\,\!$とする.) $k\,\!$と$n\,\!$は方式の強さを決定するパラメータである.

ランダムに$k-1\,\!$個の$a_{1},\cdots ,a_{k-1}\,\!$を取り, $a_{0}=S\,\!$とする. 多項式$f\left(x\right)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{k-1}x^{k-1}\,\!$を構成する. $n\,\!$個の点をこの多項式で評価する. たとえば, $i=1,\cdots ,n\,\!$とし, $\left(i,f\left(i\right)\right)\,\!$を計算する. 参加者は各点 (多項式への入力と評価のペア) を受け取る. 任意の$k\,\!$個のペアを与えられたととき, ???を用いて多項式の係数を決定できる. 後, $a_{0}\,\!$を求めればそれが秘密である.

(あとでReed-Solomon符号へリンクする. あと有限体使ってないのでこれは厳密には間違いか?)

The essential idea of Adi Shamir's threshold scheme is that 2 points are sufficient to define a line, 3 points are sufficient to define a parabola, 4 points to define a cubic curve and so forth. That is, it takes $k\,\!$ points to define a polynomial of degree $k-1\,\!$.

Suppose we want to use $\left(k,n\right)\,\!$ threshold scheme to share our secret $S\,\!$ (without loss of generality, some number) where $k<n\,\!$. The decision of values for $k\,\!$ and $n\,\!$ controls the strength of the system.

Choose at random $\left(k-1\right)\,\!$ coefficients $a_{1},\cdots ,a_{k-1}\,\!$, and let $a_{0}=S\,\!$. Build polynomial $f\left(x\right)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{k-1}x^{k-1}\,\!$. Let us construct any $n\,\!$ points out of it, for instance set $i=1,\cdots ,n\,\!$ to retrieve $\left(i,f\left(i\right)\right)\,\!$. Every participant is given a point (a pair of input to the polynomial and output). Given any subset of $k\,\!$ of these pairs, we can find the coefficients of the polynomial by polynomial curve fitting, and then evaluate $a_{0}\,\!$, which is the secret.

Usage

準備

秘密がATMの4桁の数 1234 $(S=1234)\,\!$ であるとする.

Suppose that our secret is our ATM code: 1234 $(S=1234)\,\!$.

この秘密を6つに $(n=6)\,\!$ 分割し, 3つ $(k=3)\,\!$ 集まれば元の秘密が復元できるようにする. 乱数として2つの数 166, 94 を選んだとする.

We wish to divide the secret into 6 parts $(n=6)\,\!$, where any subset of 3 parts $(k=3)\,\!$ is sufficient to reconstruct the secret. At random we obtain 2 numbers: 166, 94.

$(a_{1}=166;a_{2}=94)\,\!$

シェアを生成する多項式は:

Our polynomial to produce secret shares (points) is therefore:

$f\left(x\right)=1234+166x+94x^{2}\,\!$

となる.

この多項式から以下の6点を構成する.

We construct 6 points from the polynomial:

$\left(1,1494\right);\left(2,1942\right);\left(3,2578\right);\left(4,3402\right);\left(5,4414\right);\left(6,5614\right)\,\!$

各ユーザに異なる点 $(x,f(x))\,\!$ を配布する.

We give each participant a different single point (both $x\,\!$ and $f\left(x\right)\,\!$).

復元

3点からもとの秘密を復元することができる.

In order to reconstruct the secret any 3 points will be enough.

$\left(x_{0},y_{0}\right)=\left(2,1942\right);\left(x_{1},y_{1}\right)=\left(4,3402\right);\left(x_{2},y_{2}\right)=\left(5,4414\right)\,\!$の3点を考える.

Let us consider $\left(x_{0},y_{0}\right)=\left(2,1942\right);\left(x_{1},y_{1}\right)=\left(4,3402\right);\left(x_{2},y_{2}\right)=\left(5,4414\right)\,\!$.

ラグランジュの補完公式より,

We will compute Lagrange basis polynomials:

$\ell _{0}={\frac {x-x_{1}}{x_{0}-x_{1}}}\cdot {\frac {x-x_{2}}{x_{0}-x_{2}}}={\frac {x-4}{2-4}}\cdot {\frac {x-5}{2-5}}={\frac {1}{6}}x^{2}-1{\frac {1}{2}}x+3{\frac {1}{3}}\,\!$

$\ell _{1}={\frac {x-x_{0}}{x_{1}-x_{0}}}\cdot {\frac {x-x_{2}}{x_{1}-x_{2}}}={\frac {x-2}{4-2}}\cdot {\frac {x-5}{4-5}}=-{\frac {1}{2}}x^{2}+3{\frac {1}{2}}x-5\,\!$

$\ell _{2}={\frac {x-x_{0}}{x_{2}-x_{0}}}\cdot {\frac {x-x_{1}}{x_{2}-x_{1}}}={\frac {x-2}{5-2}}\cdot {\frac {x-4}{5-4}}={\frac {1}{3}}x^{2}-2x+2{\frac {2}{3}}\,\!$

従って,

$f(x)=\sum _{j=0}^{2}y_{j}\cdot \ell _{j}(x)\,\!$

$=1942\cdot \left({\frac {1}{6}}x^{2}-1{\frac {1}{2}}x+3{\frac {1}{3}}\right)+3402\cdot \left(-{\frac {1}{2}}x^{2}+3{\frac {1}{2}}x-5\right)+4414\cdot \left({\frac {1}{3}}x^{2}-2x+2{\frac {2}{3}}\right)\,\!$

$=1234+166x+94x^{2}\,\!$

となる.

秘密は定数項であったので, $S=1234\,\!$を得る.

Recall that the secret is the free coefficient, which means that $S=1234\,\!$, and we are done.

性質

Shamirの$\left(k,n\right)\,\!$は以下の特徴を持つ.

1. 安全性: 情報理論的安全性を有する.
2. 最小性: 各シェアはオリジナルのデータのサイズより大きくなることはない.
3. 拡張性: $k\,\!$が固定された場合, 新しいシェア$D_{i}\,\!$を加えても, またシェア$D_{i}\,\!$が失われたとしても (すなわち, 科学者が解雇者がまたは死んだ場合), 他のシェアを変更する必要はない.
4. 動的: 秘密を変更することなく安全性を高めることが出来る. しかし, この場合, 多項式を変更する必要があり, 新しいシェアを再配布する必要がある.
5. 可変性: 階層が重要な組織においては, 各ユーザーの重要度により与えるシェアの個数を変えることができる. 例えば, 社長はひとりで鍵を開けることが出来るが, 秘書は3人集まらないと鍵を開けることが出来ない, と設定することができる.

Some of the useful properties of Shamir's $\left(k,n\right)\,\!$ threshold scheme are:

1. Secure: Information theoretic security.
2. Minimal: The size of each piece does not exceed the size of the original data.
3. Extensible: When $k\,\!$ is kept fixed, $D_{i}\,\!$ pieces can be dynamically added or deleted (e.g., when scientists are fired or suddenly die) without affecting the other pieces.
4. Dynamic: Security can be easily enhanced without changing the secret, but by changing the polynomial occasionally (keeping the same free term) and constructing new shares to the participants.
5. Flexible: In organizations where hierarchy is important, we can supply each participant different number of pieces according to his importance inside the organization. For instance, the president can unlock the safe alone, whereas 3 secretaries are required together to unlock it.

See also

• Secret sharing
• Lagrange polynomial
• Homomorphic secret sharing - A simplistic decentralized voting protocol.

References

• Shamir, Adi, “How to share a secret”, Communications of the ACM 22 (11): 612-613, doi:10.1145/359168.359176 .

• Liu, C. L. (1968), Introduction to Combinatorial Mathematics, New York: McGraw-Hill .

• Dawson, E.; Donovan, D. (1994), “The breadth of Shamir's secret-sharing scheme”, Computers & Security 13: 69–78 .

• Knuth, D. E. (1997), The Art of Computer Programming, II: Seminumerical Algorithms (3rd ed.), Addison-Wesley, p. 505 .

External links

• A perl implementaton of Shamir's Secret Sharing
• ssss: A free (GPL) implementation of Shamir's Scheme
• Secret Sharp: A free (GPL) implementation of Shamir's Scheme for windows
• Christophe David's web based implementation of Shamir's scheme 'How to share a Secret'

[Category:Cryptographic algorithms]

[de:Shamir's Secret Sharing] [es:Esquema de Shamir] [ru:Схема разделения секрета Шамира]