秘密共有

秘密共有(秘密分割とも呼ばれる) とは、秘密について理解可能な情報を誰も保持しないが、十分な数の個人が「共有」を組み合わせると秘密を再構築できるような方法で、グループ内で秘密を配布する方法を指します。安全でない秘密共有では、攻撃者は共有ごとにより多くの情報を得ることができますが、安全な秘密共有は「すべてかゼロか」です (「すべて」は必要な数の共有を意味します)。

秘密分散方式の 1 つのタイプでは、ディーラーが1 人、プレーヤーがn 人います。ディーラーはプレーヤーに秘密の分け前を与えますが、特定の条件が満たされた場合のみ、プレーヤーは分け前から秘密を復元できます。ディーラーは、各プレーヤーに分け前を与えることで、t (しきい値) 以上のプレーヤーのグループは一緒に秘密を復元できますが、 t未満のプレーヤーのグループは復元できないようにします。このようなシステムは、( t、n )しきい値方式と呼ばれます ( ( n、t )しきい値方式と記述されることもあります)。

秘密分散法は1979年に アディ・シャミア^[1]とジョージ・ブラックリー^{[2]によって独立して発明されました。}

秘密分散方式は、機密性が高く、非常に重要な情報を保存するのに最適です。例としては、 暗号化キー、ミサイル発射コード、番号付き銀行口座などがあります。これらの情報は、漏洩すると悲惨な結果を招く可能性があるため、機密性が非常に高く保たれる必要がありますが、紛失しないことも重要です。従来の暗号化方法は、高いレベルの機密性と信頼性を同時に達成するのには適していません。これは、暗号化キーを保存するときに、最大限の機密性を得るためにキーの単一のコピーを 1 つの場所に保管するか、信頼性を高めるためにキーの複数のコピーを異なる場所に保管するかを選択しなければならないためです。複数のコピーを保存してキーの信頼性を高めると、追加の攻撃ベクトルが作成されて機密性が低下します。コピーが悪人の手に渡る機会が増えます。秘密分散方式はこの問題に対処し、任意のレベルの機密性と信頼性を実現できます。^[3]

秘密共有により、秘密の配布者はグループを「全体として」信頼できるようになります。従来、秘密をグループに渡して保管するには、配布者がグループの全メンバーを完全に信頼する必要がありました。秘密共有スキームにより、配布者は、常に全メンバーを信頼できない場合でも、秘密をグループに安全に保管できます。裏切り者の数が秘密を再構築するために必要な臨界数を超えない限り、秘密は安全です。

秘密共有スキームはクラウド コンピューティング環境で重要です。しきい値秘密共有メカニズムによって、キーを多数のサーバーに配布できます。キーは必要に応じて再構築されます。

秘密共有は、リンクが盗聴される可能性のあるセンサー ネットワークにも提案されています^{[誰によって? ] 。共有されたデータを送信すると、盗聴者の作業が困難になります。 [引用が必要]}このような環境でのセキュリティは、共有の構築方法を継続的に変更することによって強化できます^{[方法] 。 [引用が必要]}

安全な秘密分散方式では、 t個未満のシェアを持つ人が持つ秘密に関する情報は、0 個のシェアを持つ人と同じになるようにシェアを配布します。

たとえば、秘密フレーズ「password」が「pa––––––」、「––ss––––」、「––––wo––」、および「––––––rd」というシェアに分割される秘密分散方式を考えてみましょう。シェアが 0 の人は、パスワードが 8 文字で構成されているということしか知らないため、26 ^{8 = 2080 億通りの組み合わせの中からパスワードを推測する必要があります。一方、シェアが 1 の人は、26 6} = 3 億 800 万通りの組み合わせの中から 6 文字だけを推測すればよく、共謀する人が増えるにつれて、この組み合わせは増えていきます。したがって、このシステムは「安全な」秘密分散方式ではありません。なぜなら、t未満の秘密シェアを持つプレーヤーは、必要なシェアをすべて取得する必要なく、内部の秘密を取得する問題を軽減できるからです。

対照的に、秘密共有スキームについて考えてみましょう。ここで、Xは共有される秘密、P _iは公開非対称暗号化キー、Q _{i は}対応する秘密キーです。各プレーヤーJには、 { P ₁ ( P ₂ (...( P _N ( X )))), Q _j }が提供されます。このスキームでは、秘密キー 1 を持つプレーヤーは誰でも暗号化の外側のレイヤーを削除でき、キー 1 と 2 を持つプレーヤーは第 1 レイヤーと第 2 レイヤーを削除できます。以下同様に続きます。N 個未満のキーを持つプレーヤーは、対応する秘密キーを持たない公開キーで暗号化された BLOB を最初に復号化しなければ、秘密 X に完全に到達することはありません。これは現在、計算上実行不可能であると考えられている問題です。さらに、N 個の秘密キーをすべて持つユーザーは、すべての外側のレイヤーを復号化して秘密X を取得できるため、このシステムは安全な秘密配布システムであることがわかります。

いくつかの秘密共有方式は情報理論的に安全であると言われており、そのように証明できるが、他の方式では、効率性の向上のためにこの無条件の安全性を放棄しながら、他の一般的な暗号プリミティブと同程度に安全であると見なされるだけの安全性を維持している。たとえば、秘密をそれぞれ 128 ビットのエントロピーを持つ共有で保護できるようにするかもしれない。これは、各共有は、平均サイズ 2 ¹²⁷の総当たり攻撃を必要とする、考えられるあらゆる今日の敵を阻止するのに十分であると考えられるためである。

すべての無条件に安全な秘密共有方式に共通する制限がある: ^{[引用が必要]}

• 秘密の各シェアは、少なくとも秘密自体と同じ大きさでなければなりません。この結果は情報理論に基づいていますが、直感的に理解できます。t − 1 個のシェアが与えられた場合、秘密に関する情報はまったく決定できません。したがって、最終的なシェアには、秘密自体と同じ量の情報が含まれている必要があります。この制限を回避するには、共有する前に秘密を最初に圧縮する方法がありますが、多くの秘密 (たとえばキー) は高品質のランダム データのように見え、圧縮が難しいため、これは不可能な場合がよくあります。
• すべての秘密共有方式では、共有を構成するためにランダム ビットを使用します。 ^{[引用が必要]しきい値}t個の共有を持つ 1 ビットの秘密共有を配布するには、t − 1 個のランダムビットが必要です。^{[引用が必要]} bビットの秘密を配布するには、 ( t − 1) × bビットのエントロピーが必要です。 ^{[引用が必要]}

注: n は、シェアが分配される「プレーヤー」の総数であり、t は秘密を明かすために必要なプレーヤーの最小数です。

t = 1 の秘密共有は簡単です。秘密はn 人の参加者全員に簡単に配布できます。

t = nの場合、秘密を回復するためにすべての共有が必要となる、 いくつかの( t、n )秘密共有方式があります。

1. 秘密を任意の長さの2進数sとしてエンコードします。各プレイヤーi（iはプレイヤーの総数より1少ない）に、sと同じ長さのランダムな2進数p _{i を}与えます。シェアを持たないプレイヤーには、p _n = s ⊕ p ₁ ⊕ p ₂ ⊕ ... ⊕ p _{n −1}として計算されたシェアを与えます。ここで、 ⊕ はビットごとの排他的論理和を表します。秘密は、すべてのプレイヤーの番号（p _i、1 ≤ i ≤ n）のビットごとの排他的論理和です。
2. 代わりに、(1) は任意のグループ内の二項演算を使用して実行できます。たとえば、加算が 2 ³²を法とする整数の巡回グループを考えます。これは、バイナリオーバーフローを破棄して加算が定義された 32 ビット整数に対応します。秘密s は、 M 個の 32 ビット整数のベクトルに分割でき、これをv _secretと呼びます。次に、プレーヤーの( n − 1)にそれぞれ、均一な確率分布から独立して抽出されたM 個の 32 ビット整数のベクトルが与えられ、プレーヤーi はv _{i を}受け取ります。残りのプレーヤーには、 v _n = v _secret − v ₁ − v ₂ − ... − v _{n −1}が与えられます。秘密ベクトルは、すべてのプレーヤーのベクトルを合計することで復元できます。

困難^{[明確化が必要]は、安全性を維持しながら、} n個のシェアすべてを必要としないスキームを作成することにあります。

スペース効率が問題にならない場合は、単純なt = nスキームを使用して、各サブセットにスキームを適用するだけで、任意のプレイヤーのサブセットに秘密を明らかにすることができます。たとえば、アリス、ボブ、キャロルの 3 人のプレイヤーのうちの 2 人に秘密s を明らかにするには、 sに対して 3 つの ( ) つの異なるt = n = 2秘密シェアを作成し、アリスとボブ、アリスとキャロル、ボブとキャロルに 3 セットの 2 つのシェアを渡します。 ${\displaystyle {\binom {3}{2}}}$

たとえば、ある会社の取締役会が秘密の製法を守りたいと考えているとします。社長は必要に応じて製法にアクセスできる必要がありますが、緊急時には 12 人の取締役のうち 3 人が協力して秘密の製法を解読できます。これを実現する方法の 1 つは、t = 3およびn = 15の秘密共有方式です。この場合、社長に 3 つのシェアが与えられ、各取締役に 1 つのシェアが与えられます。

単純なアプローチは、サブセットの数が増えるにつれてすぐに非現実的になります。たとえば、100 人のプレーヤーのうち 50 人に秘密を明かす場合、スキームを作成し、各プレーヤーが各スキームごとに異なる共有セットを維持する必要があります。最悪の場合、増加は指数関数的になります。このため、しきい値のプレーヤーと秘密を効率的に共有できるスキームが求められています。 ${\displaystyle {\binom {100}{50}}\approx 1.009\times 10^{29}}$${\displaystyle {\binom {99}{49}}\approx 5.04\times 10^{28}}$

この方式では、n個のシェアのうちt 個を使用して秘密を復元できます。このシステムは、 t個の点のそれぞれが多項式上に存在するような、t − 1次多項式を一意に構築できるという考えに基づいています。直線を定義するには 2 点、2 次曲線を完全に定義するには 3 点、3 次曲線を定義するには 4 点、というように点が必要です。つまり、t − 1次多項式を定義するにはt 個の点が必要です。この方法では、秘密を最初の係数として、残りの係数をランダムに選択して、t − 1次多項式を作成します。次に、曲線上のn 個の点を見つけて、各プレーヤーに 1 つずつ渡します。n人のプレーヤーのうち少なくともt 人が自分の点を明らかにすると、最初の係数が秘密である( t − 1)次の多項式を当てはめるのに十分な情報が得られます。

同一平面上の2 本の平行でない直線は、ちょうど 1 点で交差します。空間内の 3 本の平行でない平面は、ちょうど 1 点で交差します。より一般的には、任意のn個の平行でない( n − 1)次元超平面は、特定の点で交差します。秘密は、交差点の任意の 1 つの座標としてエンコードできます。秘密がすべての座標を使用してエンコードされている場合 (座標がランダムであっても)、インサイダー ( ( n − 1)次元超平面の 1 つ以上を所有している人) は、秘密が自分の平面上にあるはずであることを知っているため、秘密に関する情報を得ることができます。インサイダーが秘密について部外者よりも多くの知識を得ることができる場合、システムはもはや情報理論的セキュリティを備えていません。n 個の座標のうちの 1 つだけが使用されている場合、インサイダーは部外者と同じことしか知りません (つまり、2 次元システムのx軸上に秘密がなければならないこと)。各プレーヤーには、超平面を定義するのに十分な情報が与えられます。平面の交差点を計算し、その交差点の指定された座標を取得することで、秘密が復元されます。

Blakley の方式は Shamir の方式よりも空間効率が悪い。Shamir のシェアはそれぞれ元の秘密と同じ大きさであるのに対し、Blakley のシェアはt倍大きい ( tはプレイヤーの閾値数)。Blakley の方式は、シェアとして使用できる平面に制限を追加することで強化できる。結果として得られる方式は Shamir の多項式システムと同等である。

中国剰余定理は秘密分散法にも使用できます。これは、 が与えられた場合に、多数の互いに素な整数の組を法として数S を一意に決定する方法を提供するためです。中国剰余定理を利用する秘密分散法には、ミニョットのスキームとアスマス・ブルームのスキームの 2 つがあります。これらはしきい値秘密分散法であり、シェアは整数 を法とする縮小によって生成され、秘密は基本的に中国剰余定理を使用して合同系を解くことによって復元されます。 ${\displaystyle m_{1},m_{2},...,m_{k}}$${\displaystyle S<\prod _{i=1}^{k}m_{i}}$${\displaystyle m_{i}}$

プレイヤーが自分のシェアを安全でないコンピュータ サーバーに保存すると、攻撃者が侵入してシェアを盗む可能性があります。秘密を変更するのが現実的でない場合は、侵害されていない (シャミア スタイルの) シェアを更新できます。ディーラーは定数項 0 の新しいランダム多項式を生成し、残りの各プレイヤーに対して新しい順序付きペアを計算します。このペアでは、古いペアと新しいペアの x 座標は同じです。各プレイヤーは、古い y 座標と新しい y 座標を互いに加算し、その結果を秘密の新しい y 座標として保存します。

攻撃者が蓄積した更新されていないシェアはすべて無効になります。攻撃者は、しきい値に達するのに十分な数の他の更新されていないシェアを見つける場合にのみ、秘密を復元できます。プレイヤーが古いシェアを削除したため、この状況は発生しないはずです。さらに、更新ファイルにはランダムな情報しか含まれていないため、攻撃者は更新ファイルから元の秘密に関する情報を復元することはできません。

ディーラーはアップデートを配布する際にしきい値を変更できますが、期限切れのシェアを保持しているプレイヤーには常に注意する必要があります。

プレイヤーは、他のシェアにアクセスするために自分のシェアについて嘘をつく可能性があります。検証可能な秘密共有(VSS) スキームを使用すると、プレイヤーは、他のプレイヤーが自分のシェアの内容について嘘をついていないことを、妥当なエラー確率まで確信できます。このようなスキームは従来の方法では計算できません。プレイヤーは、正確に何を加算および乗算するかを誰にも知らせずに、集団で数字を加算および乗算する必要があります。Tal Rabinと Michael Ben-Or は、マルチパーティ コンピューティング(MPC)システムを考案しました。このシステムでは、たとえそれらのプレイヤーが、公開された情報に応じてリアルタイムで戦略を変更できる「適応型」攻撃者によって調整されていたとしても、ディーラーまたはしきい値のプレイヤー数の 3 分の 1 までのプレイヤーの不正をプレイヤーが検出できます。

無条件に安全な秘密共有方式の欠点は、共有の保存と転送に、秘密のサイズと共有の数を掛け合わせた量のストレージと帯域幅のリソースが必要になることです。秘密のサイズがかなり大きく、たとえば 1 GB で、共有の数が 10 の場合、共有者は 10 GB のデータを保存する必要があります。無条件のセキュリティ要件を放棄することで、秘密共有方式の効率を大幅に向上させる代替技術が提案されています。

こうした技術の 1 つである秘密分散法^{[4] は}、ラビンの情報分散アルゴリズム^[5] (IDA) とシャミールの秘密分散法を組み合わせたものである。データはまず、対称暗号化アルゴリズムを使用してランダムに生成されたキーで暗号化される。次に、このデータはラビンの IDA を使用して N 個の断片に分割される。この IDA は秘密分散法と同様にしきい値が設定されており、秘密分散法とは異なり、結果として得られるデータのサイズは (断片の数 / しきい値) 倍に増加する。たとえば、しきい値が 10 で、IDA によって生成された断片の数が 15 の場合、すべての断片の合計サイズは (15/10) つまり元の入力の 1.5 倍になる。この場合、この方式は、シャミールの方式をデータに直接適用した場合よりも 10 倍効率的である。秘密分散法の最終ステップを簡単に説明すると、シャミア秘密分散法を使用してランダムに生成された対称キー (通常は 16 ～ 32 バイト程度) のシェアを生成し、各シェア所有者に 1 つのシェアと 1 つのフラグメントを付与します。

^{AONT-RS [6]}として知られる関連するアプローチは、 IDAの前処理ステップとしてデータにAll-or-nothing変換を 適用します。All-or-nothing変換は、しきい値未満のシェア数ではデータを復号化するのに不十分であることを保証します。

情報理論的に安全なk -of- n秘密分散方式では、各シェアのサイズが少なくとも秘密自体のサイズであるn 個のシェアが生成され、必要なストレージの合計は秘密の少なくともn倍になります。Matthew K. FranklinとMoti Yungによって設計された多重秘密分散では、^[7]多項式ホスト秘密の複数の点が使用され、この方法はコーディングからマルチパーティ計算まで、さまざまなアプリケーションで有用であることがわかりました。Abhishek Parakh とSubhash Kakによって考案された空間効率の高い秘密分散では、各シェアのサイズはおおよそ秘密をk − 1で割ったサイズです。^[8]

この方式は、反復多項式補間を利用しており、Web 上や センサー ネットワークでの安全な情報分散に応用できる可能性があります。この方法は、有限体の多項式の根を含むデータ分割に基づいています。^[9]関連する空間効率の高い秘密共有方式のいくつかの脆弱性は、後で指摘されました。^{[10]彼らは、配布される}k 個の秘密が本質的にk − 1未満の次数の多項式から生成される場合、補間法に基づく方式を使用して( k、n )方式を実装できないこと、共有される秘密がすべて同じである場合、この方式は機能しないなどを示しています。^[11]

秘密共有方式は、複数のサーバーで秘密を安全に保護し、複数のサーバーで障害が発生しても復元可能な状態を維持できます。ディーラーは複数の異なる参加者として行動し、参加者間でシェアを分配します。各シェアは異なるサーバーに保存されますが、ディーラーは、少なくともt 個のシェアを復元できる限り、複数のサーバーが故障しても秘密を復元できます。ただし、 1 つのサーバーに侵入したクラッカーは、各サーバーに保存されているシェアがt個未満である限り、秘密を知ることはできません。

これはワシントン大学のVanishコンピュータ プロジェクトの主要な概念の 1 つであり、ランダム キーを使用してデータを暗号化し、そのキーをP2Pネットワーク内の複数のノードに秘密として配布します。メッセージを復号化するには、ネットワーク上の少なくともt 個のノードにアクセスできる必要があります。この特定のプロジェクトの原則は、ネットワーク上の秘密共有ノードの数は時間の経過とともに自然に減少し、その結果、秘密が最終的に消滅するというものです。ただし、ネットワークはシビル攻撃に対して脆弱であるため、Vanish は安全ではありません。^[12]

いつでもコンテンツを解読するのに十分な情報を持っている株主は、X のコピーを取得して保存することができます。したがって、Vanish などのツールや技術は、一定期間後に独自のシステム内でデータを回復不可能にすることができますが、悪意のあるユーザーがデータを見た後、そのデータを強制的に削除することはできません。これは、デジタル著作権管理の主な難問の 1 つです。

ディーラーは、元の秘密を復元するために必要なt 個のシェアを 1 人の受信者に送信することができます。攻撃者は、秘密を復元するためにすべてのt 個のシェアを傍受する必要がありますが、これは、特にシェアが異なるメディアを使用して送信されている場合 (たとえば、一部はインターネット経由で、一部はCDで郵送される場合) 、1 つのファイルを傍受するよりも困難な作業です。

大きな秘密の場合、秘密を暗号化してから秘密共有を使用してキーを配布する方が効率的である可能性があります。

秘密共有は、安全なマルチパーティ計算のためのいくつかのプロトコルにおいて重要な基本要素です。秘密共有は、システム内のユーザー認証にも使用できます。^[13]

• Ubuntu マニュアルページ: gfshare – GF(28) におけるシャミア秘密分散法の説明
• シャミールとブレイクリーの計画の説明
• PGP（およびその他の？）パスフレーズを復元するための秘密共有の使用に関する特許米国特許 6,662,299
• 秘密共有スキームに関する参考文献
• Wayback Machineの Shared Secret を使用したコード署名システム(2008 年 2 月 14 日アーカイブ)
• Beimel, Amos (2011) 「秘密共有スキーム: 調査」(PDF)。