準同型秘密分散

暗号学において、準同型秘密分散法は、秘密が準同型暗号化によって暗号化される秘密分散アルゴリズムの一種です。準同型とは、ある代数構造を同じ型の別の代数構造に変換し、その構造が保持されることを意味します。重要なのは、元のデータに対するあらゆる種類の操作に対して、変換後のデータに対する対応する操作が存在するということです。[ 1 ]

技術

準同型秘密分散は、次のように秘密を複数の受信者に送信するために使用されます。

  1. 「秘密」を準同型写像を用いて変換する。これにより、秘密は操作や保存が容易な形式に変換されることが多い。特に、ステップ(2)で要求されるように、新しい形式を「分割」する自然な方法が存在する可能性がある。
  2. 変換された秘密を複数の部分に分割し、受信者ごとに1つずつ割り当てます。秘密は、すべての部分またはほとんどの部分を組み合わせた場合にのみ復元できるように分割する必要があります。（秘密分散を参照してください。）
  3. 秘密の一部を各受信者に配布します。
  4. 受信者の各部分を組み合わせて、変換された秘密を、おそらく指定された時間に復元します。
  5. 準同型性を逆転させて元の秘密を復元します。

例

あるコミュニティが分散型投票プロトコルを用いて選挙を実施したいが、投票集計者が結果について嘘をつかないようにしたいとします。シャミアの秘密分散法と呼ばれる準同型秘密分散法を用いることで、コミュニティの各メンバーは、複数の断片に分割されたフォームに投票を追加することができます。各断片は、異なる投票集計者に送信されます。各断片は、投票集計者が各断片への変更が全体にどのような影響を与えるかを予測できないように設計されているため、投票集計者が断片を改ざんすることを抑制します。すべての投票が受信されると、投票集計者はそれらを結合し、選挙の集計結果を復元します。

詳細には、次のような選挙があるとします。

  • 2つの可能な結果、つまり「はい」または「いいえ」。これらの結果をそれぞれ +1 と -1 で数値的に表します。
  • 投票を数える当局の数k 。
  • 投票を提出する投票者の数n。
  1. 事前に、各機関は公開可能な数値キーx kを生成します。
  2. 各投票者は、次の規則に従って多項式p nに自分の投票をエンコードします。多項式の次数はk − 1、定数項は +1 または -1 (「はい」に投票するか「いいえ」に投票するかに対応) のいずれか、その他の係数はランダムに生成される必要があります。
  3. 各有権者は、各権限の公開鍵x kにおける多項式p nの値を計算します。
    • これにより、各権限ごとに 1 ポイントずつ、kポイントが生成されます。
    • これらのk点は投票の「ピース」です。すべての点が分かれば、多項式p nを計算できます（したがって、投票者がどのように投票したかがわかります）。しかし、一部の点しか分かっていなければ、多項式を計算できません。（これは、次数( n − 1)の多項式を決定するにはn点必要だからです。2点あれば直線が、3点あれば放物線が決定されます。）
  4. 投票者は、各機関のキーを使用して生成された値を各機関に送信します。
  5. 各権限者は受け取った値を収集します。各権限者は各投票者から1つの値しか取得しないため、特定の投票者の多項式を見つけることはできません。さらに、提出された値を変更すると投票にどのような影響が出るかを予測することもできません。
  6. 投票者が投票を提出すると、各権限kは受け取ったすべての値の合計A kを計算して発表します。
  7. k個の合計A kがあり、それらを組み合わせると、一意の多項式P ( x ) が決まります。具体的には、すべての投票者多項式の合計、つまりP ( x ) = p 1 ( x ) + p 2 ( x ) + ... + p n ( x ) が決まります。
    • P ( x )の定数項は、実際にはすべての投票の合計です。なぜなら、 P ( x )の定数項は、個々のp nの定数項の合計だからです。
    • したがって、 P ( x )の定数項は、集計された選挙結果を提供します。つまり、正の場合、+1に投票した人の数が-1に投票した人の数より多く、負の場合、+1に投票した人の数が-1に投票した人の数より多くなります。
投票プロトコルを示す表
投票手順の図解。各列は特定の投票者の投票結果を表し、各行は特定の機関が受け取った投票結果を表します。

特徴

このプロトコルは、 k 個の当局のすべてが腐敗していない限り機能します。もし腐敗していた場合は、各当局が協力して各投票者のP ( x ) を再構築し、その後投票を変更することもできます。

プロトコルではt + 1 個の権限が完了する必要があるため、権限がN > t + 1 個ある場合、N − t − 1 個の権限が破損する可能性があり、これによりプロトコルに一定の堅牢性が与えられます。

プロトコルは投票者の ID (投票用紙とともに提出された ID) を管理するため、正当な投票者だけが投票したことを確認できます。

tに関する仮定のもとで:

  1. 投票用紙をIDまで遡って確認することはできないため、投票者のプライバシーは保護されます。
  2. 有権者は自分がどのように投票したかを証明することはできません。
  3. 投票を検証することは不可能です。

このプロトコルは、投票用紙の不正を暗黙的に防止します。これは、各当局が投票用紙の一部しか保有しておらず、その割合の変更が結果にどのような影響を与えるかを知らないため、当局が投票用紙を変更するインセンティブがないためです。

脆弱性

  • 投票者は自分の投票が正しく記録されたかどうか確信できません。
  • 当局は投票が合法かつ平等であったかどうか確信できません。たとえば、投票者は有効な選択肢ではない値（つまり、{-1, 1}の範囲外）（-20, 50など）を選択する可能性があり、その結果は投票者に有利になります。

参照

参考文献

  1. ^ Schoenmakers, Berry (1999). 「公開検証可能なシンプルな秘密分散法と電子投票への応用」. Advances in Cryptology — CRYPTO' 99. Lecture Notes in Computer Science. Vol. 1666. pp.  148– 164. CiteSeerX  10.1.1.102.9375 . doi : 10.1007/3-540-48405-1_10 . ISBN 978-3-540-66347-8。
「 https://en.wikipedia.org/w/index.php?title=Homomorphic_secret_sharing&oldid=1163912573」より取得