Shamir の秘密共有暗号アルゴリズムの紹介

Adi Shamir の Secret Sharingは、個別の関係者が株式を保有することで単一の秘密の所有権を共同で共有できるようにする暗号化アルゴリズムです。元のシークレットは、最小数の共有を使用することによってのみ再構築できます。これにより、さまざまな関係者が互いに完全に信頼する必要なく協力できます。

例題

例として、4 人家族全員が 1 つのビットコイン ウォレットを共有しているとします。このビットコイン ウォレットには、家族全員が共同所有する単一の秘密鍵が含まれています。単一のキーがあるため、家族の誰もがそのキーを使用してすべてのビットコインを使用できます。

家族には問題があります。それぞれがコピーを保持している場合、すべてのコインが盗まれるには、コピーの 1 つだけが侵害される必要があります。そのうちの 1 人だけが鍵を保持している場合、その人が鍵を紛失したり、他の家族と裏切ったりする可能性があります。

幸いなことに、家族の 1 人は暗号学者でもあります。元の鍵を単純に共有する代わりに、 SSS (シャミールの秘密共有) を使用します。家族は 4 つの共有を作成し、Bitcoin キーを元の秘密として 3 つのしきい値を設定します。現在、彼らの計画には次のプロパティがあります。

• 彼らはビットコインキーを一か所に保管していないため、盗むのが難しくなっています
• 家族のメンバーは協力してビットコインを使う必要があり、家族の 1 人が他の人を裏切ることはできません
• 家族の一員が死亡したり、分け前を失ったりしても、残りの 3 人のメンバーは引き続き鍵を再構築できます。

しきい値について

すべての Shamir 共有スキームには、共有の総数としきい値があります。しきい値は、元のシークレットを再構築するために必要な共有数です。たとえば、共有数が 5 でしきい値が 3 の場合、元のシークレットを計算するには、5 つの共有のうち 3 つだけが必要です。

数学 - 行

Shamir の秘密分散法で使用される基本的な数学的性質の 1 つは、次数k - 1 の多項式を定義するにはkポイントが必要であるという事実です。たとえば、次のようになります。

• 2 点間には 1 本の線しか引くことができません
• 同じ 3 点を通過できる放物線は 1 つだけです
• 同じ 4 点を通過する 3 次曲線は 1 つだけです
• 同じ点を通って無数の線を引くことができます
• 同じ2点を通って無数の放物線を描くことができます

数学 - ウォークスルー

シークレット 1954 ( S)を 4 ( n)の共有と 3 ( k)のしきい値で共有するスキームを構築しましょう。

まず、ランダムにk - 1 個の正の整数を選択します。この場合、正の整数は 2 個です。ランダムに 43 と 12 を選択します。

次に、次の形式の多項式を作成します。

 y = a0 + a1*x + a2*x^2

a0 はシークレットで、a1 と a2 はランダムに選択された整数です。残っているのは次のとおりです。

 y = 1954 + 43x + 12x^2

次に、この式を使用して、各参加者に与える 4 つのポイント (シェア) を作成します。

共有 1

(x, y) ここで x = 1

年 = 1954 + 43*1 + 12*1^2 = 2009

(1, 2009)

共有 2

(x, y) ここで x = 2

y = 1954 + 43*2 + 12*2^2 = 2088

(2,2088)

シェア 3

(x, y) ここで x = 3

y = 1954 + 43*3 + 12*3^2 = 2191

(3,2191)

共有 4

(x, y) ここで x = 4

y = 1954 + 43*4 + 12*4^2 = 2318

(4, 2318)

再建

スキームの各参加者は、1 つの(x,y)ポイント (1 つのシェア) を所有しています。しきい値を 3 に設定し、3 つの点が放物線 (次数 2 の多項式) を完全に定義することを思い出してください。つまり、3 点を使用すると、放物線を描き、a0 (秘密) を計算できます。株式 1、2、および 4 を制御していると仮定しましょう。

ステップ 1 - コントロールするポイント (シェア) をプロットする

ステップ 2 - 対応する放物線を描く

ステップ 3 - x=0の点を見つけます。そのy値は秘密です

私たちの場合、秘密は1954です。

実はそれほど単純ではありません。有限のフィールドが必要です。

上記の例はデモンストレーションには最適ですが、実際にはあまり安全ではありません。攻撃者が取得する共有ごとに、実際にはシークレットに関する情報をどんどん取得しています。 2 つの点は放物線を完全に説明するものではありませんが、それでも放物線に関する重要な情報が漏れています。

解決策は、有限体演算にあります。十分なサイズの有限体に関数をプロットすることにより、多項式のグラフはバラバラになり散らばってしまいます。つまり、攻撃者は基礎となる関数の経路について知識に基づいた推測を行うことができなくなります。

アディ・シャミール

Adi Shamir は、Shamir's Secret Sharing で有名なイスラエルの暗号学者ですが、インターネットの大部分が構築されている、広く使用されている RSA アルゴリズムの共同発明者でもあります。 Shamir はテルアビブで生まれ、そこの大学で数学の学士号を取得しました。その後、修士号と博士号を取得しました。 1975 年と 1977 年にそれぞれワイツマン研究所でコンピューター サイエンスの学位を取得しています。