Verifiable Secret Sharing Scheme Using Merkle Tree

ISCEIC ‘2020 https://doi.org/10.1109/ISCEIC51027.2020.00008

概要 Shamir’s (k, n) Secret Sharing Scheme(Verifiable Secret Sharing)にMerkle Treeを適用することで、参加者間のシェアを検証し、偽のシェアを検証・排除した後に参加者が秘密を正しく再構成できるようにした

Share exchanges

• 非同期通信では、シェアはインターネット上でブロードキャストされる
• Merkle Treeを用いてシェアを検証したとしても、敵対者が他の誠実な参加者のシェアを取得し、単独で秘密を再構築することを防ぐことはできない
• ブロードキャストせずに、シェアとMerkle TreeのAuthentication Pathを交換しあう方式を用いれば解決できる
  • 各参加者は、シェアとAuthentication Pathを同時に2以上のプロセスに送ってはいけない
  • 例えば、k=4だとすると、4人の参加者を想定して、以下の順番の送りかたが考えられる
  1. P1 → P2 → P3 → P4 → P1
  2. P4 → P3 → P2 → P1 → P4
  3. P1 → P3、P2 → P4
  4. P3 → P1、P4→P2

  • 要はこういう感じで送りあえばOK

    • 

  • 全部のパスで検証に成功していたら、秘密は共有できる

• k*(k-1)回のシェア交換が必要
• 参加者の1/2(=k/2)が不正者だと詰む