中国剰余定理を用いた秘密分散法

前述のとおり、ミグノット閾値秘密分散方式では、中国剰余定理（CRT）に加えて、( k , n ) -ミグノット数列と呼ばれる特別な整数列を使用します。この数列は、互いに素なn個の整数から構成され、そのうち最小のk個の積が、最大のk -1個の積よりも大きくなります。この条件は、この方式が2つの積の間の整数を秘密として選択することを前提としているため、非常に重要です。この条件により、秘密を完全に復元するには、どのように選択されたかに関わらず、少なくともk個のシェアが必要になることが保証されます。

形式的には、2 ≤ k ≤ nを整数とする。( k , n ) -ミニョット数列は、正の整数の厳密に増加する数列である。${\displaystyle m_{1}<\cdots <m_{n}}$、 と${\displaystyle (m_{i},m_{j})=1}$すべての1 ≤ i < j ≤ nに対して、${\displaystyle m_{n-k+2}\cdots m_{n}<m_{1}\cdots m_{k}}$。 させて$\displaystyle \alpha =m_{n-k+2}\cdots m_{n}}$そして$\displaystyle \beta =m_{1}\cdots m_{k}}$; 厳密にその間にある整数を と呼びます${\displaystyle \alpha }$そして${\displaystyle \beta }$許可された範囲。我々は、次のように( k , n )しきい値秘密分散方式を構築します。秘密S をランダムな整数として選択します。${\displaystyle \alpha <S<\beta }$許可された範囲内で。1 ≤ i ≤ nごとに、 Sのm _iを法とする還元を計算します。これをs _iと呼びます。これらがシェアです。次に、任意のk個の異なるシェアについて${\displaystyle s_{i_{1}},\ldots ,s_{i_{k}}}$そこで、合同式の体系を考えてみましょう。

${\displaystyle {\begin{cases}x\equiv &s_{i_{1}}\ {\bmod {\ }}m_{i_{1}}\\&\vdots \\x\equiv &s_{i_{k}}\ {\bmod {\ }}m_{i_{k}}\\\end{cases}}}$

中国剰余定理により、${\displaystyle m_{i_{1}},\ldots ,m_{i_{k}}}$が互いに素である場合、システムは法 で一意の解を持ちます。${\displaystyle m_{i_{1}}\cdots m_{i_{k}}}$我々の株式の構成によれば、この解決策は回復すべき秘密のSに他ならない。

この方式では、特別な整数列も使用します。2 ≤ k ≤ nを整数とします。互いに素な正の整数の列を考えます。${\displaystyle m_{0}<...<m_{n}}$そのため${\displaystyle m_{0}\cdot m_{n-k+2}\cdots m_{n}<m_{1}\cdots m_{k}}$この与えられたシーケンスに対して、秘密Sを集合Z / m ₀ Z内のランダムな整数として選択します。

次に、ランダムな整数αを選択します。${\displaystyle S+\alpha \cdot m_{0}<m_{1}\cdots m_{k}}$。我々は、 m _iを法とする還元を計算する。${\displaystyle S+\alpha \cdot m_{0}}$1 ≤ i ≤ nのすべてについて、これらはシェアです${\displaystyle I_{i}=(s_{i},m_{i})}$。さて、任意のk 個の異なるシェアについて${\displaystyle I_{i_{1}},...,I_{i_{k}}}$そこで、合同式の体系を考えてみましょう。

${\displaystyle {\begin{cases}x\equiv &s_{i_{1}}\ {\bmod {\ }}m_{i_{1}}\\&\vdots \\x\equiv &s_{i_{k}}\ {\bmod {\ }}m_{i_{k}}\\\end{cases}}}$

中国剰余定理により、${\displaystyle m_{i_{1}},...,m_{i_{k}}}$が互いに素である場合、システムは一意の解S ₀ mod を持ちます。${\displaystyle m_{i_{1}}\cdots m_{i_{k}}}$我々のシェアの構成により、秘密SはS0のm0_を法とする還元である。

Mignotte ( k , n ) -閾値秘密分散方式は、 k未満のシェアのセットが秘密に関する情報を含んでいるという意味で完全ではないことに注意することが重要です。Asmuth–Bloom 方式は完全です。αは秘密Sとは独立しており、

${\displaystyle \left.{\begin{array}{r}\prod _{i=n-k+2}^{n}m_{i}\\\alpha \end{array}}\right\}<{\frac {\prod _{i=1}^{k}m_{i}}{m_{0}}}}$

したがって、αは任意の整数を法とすることができる。

${\displaystyle \prod _{i=n-k+2}^{n}m_{i}.}$

このk − 1 個の法の積は、 n 個の中からk − 1個を選ぶ可能な積の中で最大であるため、 k − 1 個の同値性の任意の部分集合は、その積を法とする任意の整数になり得、Sからの情報は漏洩しません。

以下は、Asmuth–Bloom スキームの例です。実際的な目的のために、すべてのパラメータに小さな値を選択します。k = 3、n = 4 を選択します。互いに素な整数は次のようになります。${\displaystyle m_{0}=3,m_{1}=11,m_{2}=13,m_{3}=17}$そして${\displaystyle m_{4}=19}$それらはアスムート・ブルームの要求シーケンスを満たしている。${\displaystyle 3\cdot 17\cdot 19<11\cdot 13\cdot 17}$。

秘密のSは2だとしましょう。${\displaystyle \alpha =51}$アスムート・ブルーム方式の必要条件を満たす。$2+51\cdot 3=155$そして、整数 11、13、17、19 のそれぞれについてシェアを計算します。それらはそれぞれ 1、12、2、3 です。3 つのシェアの可能なセットを 1 つ考えます。4 つの可能な 3 つのシェアのセットの中から、セット{1、12、2}を取り、それが秘密S = 2を復元することを示します。次の合同式のシステムを考えます。

${\displaystyle {\begin{cases}x\equiv &1\ {\bmod {\ }}11\\x\equiv &12\ {\bmod {\ }}13\\x\equiv &2\ {\bmod {\ }}17\\\end{cases}}}$

システムを解くには、${\displaystyle M=11\cdot 13\cdot 17}$このようなシステムを解くための構成的アルゴリズムから、システムの解は次のようになることがわかります。${\displaystyle x_{0}=1\cdot e_{1}+12\cdot e_{2}+2\cdot e_{3}}$ここで、各e _{i は}次のように求められます。

ベズーの恒等式により、${\displaystyle (m_{i},M/m_{i})=1}$拡張ユークリッドアルゴリズムを用いて見つけることができる正の整数r _iとs _iが存在し、${\displaystyle r_{i}.m_{i}+s_{i}.M/m_{i}=1}$。 セット${\displaystyle e_{i}=s_{i}\cdot M/m_{i}}$。

アイデンティティから${\displaystyle 1=1\cdot 221-20\cdot 11=(-5)\cdot 187+72\cdot 13=5\cdot 143+(-42)\cdot 17}$私たちはそれを理解しています${\displaystyle e_{1}=221,e_{2}=-935,e_{3}=715}$、そしてモジュロの唯一の解${\displaystyle 11\cdot 13\cdot 17}$155です。最後に、${\displaystyle S=155\equiv 2\mod 3}$。