積極的な秘密共有

プロアクティブ秘密共有は、プロアクティブセキュリティプロトコルの基礎となる技術です。 これは、秘密共有スキームの分散キー（シェア）を定期的に更新する方法であり、攻撃者がシェアを危険にさらす時間が少なくなり、攻撃者がしきい値またはクォーラムグループ未満にアクセスする限り、システムが安全のままになります。これは、秘密の有効期間中にしきい値の数のシェアが危険にさらされると秘密が危険にさらされる非プロアクティブスキームとは対照的です。時間制約を考慮したモデルは、共有の冗長性によって時間領域（期間）への堅牢性が可能になるビザンチンフォールトトレランスの概念の拡張として最初に提案され、 1991年にラファエル・オストロフスキー氏とモティ・ヤング氏によって提案されました。 ^{[ 1 ]}この方法は、安全なマルチパーティコンピューティングやしきい値暗号システムの暗号プロトコルの分野で使用されています。

モチベーション

プレイヤー（共有秘密の保有者）が安全でないコンピュータサーバーに共有秘密を保管した場合、攻撃者が侵入して共有秘密を盗み出したり、盗まれたりする可能性があります。秘密を変更することは現実的ではないことが多いため、侵害されていない（正直な）（シャミア方式の）共有秘密は、同じ秘密を生成するように更新する必要がありますが、古い共有秘密は無効化されます。また、以前に破損したサーバーの共有秘密を回復する必要があり、回復を実行するには正直なサーバーのコミュニティが必要です。これにより、安全で回復可能な共有秘密、つまり安全で正しい秘密計算プロトコルの長期的な存続が保証されます。

サーバーの数やしきい値を変更しながら共有を維持する必要がある場合、共有回復を備えたプロアクティブ方式でこれが可能になります。これはもともとフランケルらによって示されました。^{[ 2 ] [ 3 ]}プロアクティブ秘密共有方式のように秘密（コードワード）を配布し、配布された共有を回復する機能は、2010年頃にストレージシステムで非常に必要とされていると認識され、それに応じて、符号理論家はこの方式の名前を変更し、さらに改良して、「再生成コード」および「ローカルで回復可能なコード」として形式化しました。

数学

^{これは[ 4 ]}の研究に多少倣ったものである。 シェアを更新するために、ディーラー（つまり、シェアを配布する人。分散システムでは参加者全員が一度に一人ずつ配布する）は、定数項ゼロの新しいランダム多項式を生成し、残りのプレイヤーそれぞれについて、古いペアと新しいペアのx座標が同じになるような新しい順序付きペアを計算する。各プレイヤーは、古いy座標と新しいy座標を互いに加算し、その結果を秘密の新しいy座標として保存する。

• ディーラーが1人の場合、ディーラーは閾値を とする次数体上のランダム多項式を構築します。ディーラーが複数人の場合、分散プロトコルが実行され、そのようなランダム多項式を安全に構築します。${\displaystyle k-1}$ ${\displaystyle k}$
• 各プレイヤーはシェアを獲得する。ここで、はプレイヤー数、は時間間隔におけるプレイヤーのシェアである。${\displaystyle x_{i}^{0}=f^{0}(i)}$ ${\displaystyle i\in \{1,...,n\}}$ ${\displaystyle n}$ ${\displaystyle x_{i}^{0}}$ ${\displaystyle i}$ ${\displaystyle 0}$
• 秘密はシェアの補間によって再構築できる${\displaystyle k}$
• シェアを更新するには、すべての当事者が次の形式のランダム多項式を構築する必要がある。${\displaystyle \delta _{i}(z)=\delta _{i,1}z^{1}+\delta _{i,2}z^{2}+...+\delta _{i,k}z^{k-1}}$
• 各プレイヤーは他のプレイヤー全員を送ります${\displaystyle i}$ ${\displaystyle u_{i,j}=\delta _{i}(j)}$
• 各プレイヤーは、シェアが有効な時間間隔によってシェアを更新します。${\displaystyle x_{i}^{t+1}=x_{i}^{t}+u_{1,i}^{t}+...+u_{n,i}^{t}}$ ${\displaystyle t}$

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

ディーラーはアップデートを配布する際に閾値数を変更できますが、期限切れのシェアを保持しているプレイヤーに常に注意を払う必要があります。^{[ 5 ]}ただし、元の方法ではサーバーのコミュニティに再共有ディーラーと失われたシェアの再生者になる能力が与えられているため、これはやや限定的な見方です。

例

以下の例では、シェアが2つあり、しきい値は2で、プレイヤーは2人、ディーラーは1人です。シェアと多項式は特定の期間のみ有効であるため、有効な期間は上付き文字で示されます。

• すべての当事者は有限体について同意する：${\displaystyle Z_{11}}$
• ディーラーは秘密を確立します:${\displaystyle s=6\in Z_{11}}$
• ディーラーは2 - 1次（閾値2）の ランダム多項式を構築する。${\displaystyle Z_{11}}$
  • ${\displaystyle f^{0}(x)=6+2\times x}$
  • 注記${\displaystyle f^{0}(0)=s=6}$
• プレイヤー1がシェアを獲得し、プレイヤー2がシェアを獲得する${\displaystyle x_{1}^{0}=f^{0}(1)=6+2\times 1=8}$ ${\displaystyle x_{2}^{0}=f^{0}(2)=6+2\times 2=10}$
• 秘密を再現するには、${\displaystyle x_{1}^{0}}$ ${\displaystyle x_{2}^{0}}$
  • は直線なので、点の傾きの形を使って補間することができる。${\displaystyle f^{0}(x)}$
  • ${\displaystyle m=(f^{0}(2)-f^{0}(1))/(2-1)=(x_{2}^{0}-x_{1}^{0})/(2-1)=(10-8)/(2-1)=2/1=2}$
  • ${\displaystyle b=f^{0}(1)-m=x_{1}^{0}-2=8-2=6}$
  • ${\displaystyle f^{0}(x)=b+m\times x=6+2\times x}$
  • ${\displaystyle f^{0}(0)=6+2\times 0=6=s}$
• シェアを更新するには、すべての当事者が自由係数がゼロと なるような1次のランダム多項式を構築する必要がある。
  • プレイヤー1の構築${\displaystyle \delta _{1}^{0}(z)=\delta _{1,1}^{0}\times z^{1}=2\times z^{1}}$
  • プレイヤー2の構築物${\displaystyle \delta _{2}^{0}(z)=\delta _{2,1}^{0}\times z^{1}=3\times z^{1}}$
• 各プレイヤーは多項式を評価し、他のプレイヤーと情報を共有する。
  • プレイヤー1は計算し、${\displaystyle u_{1,1}^{0}=\delta _{1}^{0}(1)=2}$ ${\displaystyle u_{1,2}^{0}=\delta _{1}^{0}(2)=4}$ ${\displaystyle Z_{11}}$
  • プレイヤー1がプレイヤー2に送る${\displaystyle u_{1,2}^{0}}$
  • プレイヤー2は計算し、${\displaystyle u_{2,1}^{0}=\delta _{2}^{0}(1)=3}$ ${\displaystyle u_{2,2}^{0}=\delta _{2}^{0}(2)=6}$ ${\displaystyle Z_{11}}$
  • プレイヤー2がプレイヤー1に送る${\displaystyle u_{2,1}^{0}}$
• 各プレイヤーは、自分のシェアを次のように更新します。${\displaystyle x_{i}^{1}=x_{i}^{0}+u_{1,i}^{0}+u_{2,i}^{0}}$
  • プレイヤー1は計算する${\displaystyle x_{1}^{1}=x_{1}^{0}+u_{1,1}^{0}+u_{2,1}^{0}=8+2+3=2\in Z_{11}}$
  • プレイヤー2は計算する${\displaystyle x_{2}^{1}=x_{2}^{0}+u_{1,2}^{0}+u_{2,2}^{0}=10+4+6=9\in Z_{11}}$
• 更新された共有が同じ元の秘密を生成することを確認する
  • とを使って多項式を再構築する${\displaystyle x_{1}^{1}}$ ${\displaystyle x_{2}^{1}}$ ${\displaystyle f^{1}(x)}$
  • は直線なので、点の傾きを使用できる。${\displaystyle f^{1}(x)}$
  • ${\displaystyle m=(f^{1}(2)-f^{1}(1))/(2-1)=(x_{2}^{1}-x_{1}{1})/(2-1)=(9-2)/(2-1)=7/1=7}$
  • ${\displaystyle b=f^{1}(1)-m=x_{1}^{1}-7=2-7=-5=6}$
  • ${\displaystyle f^{1}(x)=b+m\times x=6+7\times x}$
  • ${\displaystyle f^{1}(0)=6+7\times 0=6=s}$

参照

• キー（暗号化）
• 鍵生成
• 鍵配布
• 鍵管理
• シャミールの秘密分散

参考文献

1. ラファイル・オストロフスキー、モティ・ユン「モバイルウイルス攻撃への対処法（拡張要約）」PODC 1991: 51-59 [1]
2. ヤイル・フランケル、ピーター・ゲメル、フィリップ・D・マッケンジー、モティ・ヤング：最適耐性プロアクティブ公開鍵暗号システム。FOCS 1997：384-393 [2]
3. Krenn, Stephan; Loruenser, Thomas (2023). 『秘密分散入門：体系的な概要とプロトコル選択ガイド』 doi : 10.1007 /978-3-031-28161-7 . ISBN 978-3-031-28160-0。（ [3]でも入手可能）
4. Herzberg, Amir; Jarecki, Stanislaw; Hugo, Krawczyk; Yung, Moti (1995). 「プロアクティブ・シークレット・シェアリング、あるいは永続的な漏洩への対処法」 . CRYPTO '95: Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology . London, UK: Springer-Verlag. pp.  339– 352. ISBN 978-3-540-60221-7. 2010年6月14日閲覧。
5. Yevdokimov, Aleksey (2009). 「プロアクティブセキュリティの動的システム」2009年国際情報通信技術応用会議IEEE. pp.  1– 4. doi : 10.1109/ICAICT.2009.5372541 . ISBN 978-1-4244-4739-8. S2CID  11732393 .