検証可能な秘密共有

暗号学では、プレイヤーが自分の秘密分散が一貫していることを検証できる補助情報が含まれている場合、秘密分散方式は検証可能である。より正式には、検証可能な秘密分散は、ディーラーが悪意を持っていたとしても、プレイヤーが後で再構築できる明確に定義された秘密があることを保証する。（標準的な秘密分散では、ディーラーは正直であると想定されている。）[ 1 ]^検証 可能な秘密分散（VSS）の概念は、1985年にBenny Chor、Shafi Goldwasser、Silvio Micali、Baruch Awerbuchによって初めて導入された。^[2]

VSS プロトコルでは、秘密を共有したい特定のプレーヤーはディーラーと呼ばれます。プロトコルは、共有フェーズと再構築フェーズの 2 つのフェーズで構成されます。

共有:最初はディーラーが秘密の入力を保持し、各プレイヤーは独立したランダムな入力を保持します。共有フェーズは複数のラウンドで構成される場合があります。各ラウンドで、各プレイヤーは他のプレイヤーに非公開でメッセージを送信したり、メッセージをブロードキャストしたりできます。プレイヤーが送信またはブロードキャストする各メッセージは、その入力、ランダムな入力、および前のラウンドで他のプレイヤーから受信したメッセージによって決定されます。

再構築:このフェーズでは、各プレーヤーが共有フェーズからの全体的なビューを提供し、再構築関数が適用されてプロトコルの出力として取得されます。

Oded Goldreich による別の定義では、VSS は、何らかの (検証不可能な) 秘密共有スキームに対応するランダム化された機能を計算するための安全なマルチパーティ プロトコルであると定義されています。この定義は他の定義よりも強力であり、一般的な安全なマルチパーティ計算のコンテキストで使用するのに非常に便利です。

検証可能な秘密共有は、安全なマルチパーティ計算にとって重要です。マルチパーティ計算は、通常、入力の秘密共有を作成し、その共有を操作して何らかの関数を計算することによって実現されます。「アクティブな」敵対者 (つまり、ノードを破壊してプロトコルから逸脱させる敵対者) に対処するには、秘密共有スキームが検証可能で、逸脱したノードがプロトコルから逸脱するのを防ぐ必要があります。

単純なVSS方式の一般的な例としては、ポール・フェルドマンによるプロトコル^[3]がある。これは、シャミアの秘密分散方式と、特定の準同型性を満たす暗号化方式（必ずしもすべての準同型暗号化方式が満たすわけではない）を組み合わせたものである。

以下の説明は一般的な考え方を示していますが、そのままでは安全ではありません。(特に、公開された値g ^{s は}ディーラーの秘密sに関する情報を漏らすことに注意してください。)

まず、素数位数qの巡回群Gと、Gの生成元g が、システムパラメータとして公開的に選択される。群G は、この群内で離散対数の計算が困難になるように選択する必要がある。（通常、( Z / p Z ) ^×の位数qの部分群を取ります。ここで、q はp − 1を割り切る素数です。）

次にディーラーは、Z _qの係数を持つt次ランダム多項式 P を計算し (秘密に保持し)、 P (0) = sとなるようにします(ここでsは秘密です)。n人の各株主は、 qを法とする値P (1)、...、P ( n )を受け取ります。t + 1 人の株主は、 qを法とする多項式補間を使用して秘密s を復元できますが、最大でt人の株主のどのセットも復元できません (実際、この時点では、最大でt人の株主のどのセットもsに関する情報を持っていません)。

ここまでは、まさにシャミアの方式です。これらのシェアを検証可能にするために、ディーラーはコミットメントを P モジュロ q の係数に分配します。P ( x ) = s + a 1 x + ... + a t x t の場合、与える必要があるコミットメント_は次のよう_になり^ます。

• c ₀ = g ^s、
• c ₁ = g ^{a ₁}、
• ...
• c _t = g ^{a _t} .

これらが与えられれば、どの当事者も自分の取り分を検証できる。例えば、v = P ( i ) modulo qを検証するには、当事者iは以下をチェックできる。

${\displaystyle g^{v}=c_{0}c_{1}^{i}c_{2}^{i^{2}}\cdots c_{t}^{i^{t}}=\prod _{j=0}^{t}c_{j}^{i^{j}}=\prod _{j=0}^{t}g^{a_{j}i^{j}}=g^{\sum _{j=0}^{t}a_{j}i^{j}}=g^{P(i)}}$。

この方式は、せいぜい計算能力が制限された敵、つまり離散対数の計算が困難であることに対して安全である。ペダーセンは後に、ディーラーの計算能力が無制限であっても秘​​密に関する情報が漏洩しない 方式^{[4]を提案した。}

n株がそれぞれの保有者に配布されると、各保有者はすべての株が集合的にt一貫性があることを検証できる必要があります(つまり、 n株の任意のサブセットt は、秘密を漏らすことなく、同じ正しい多項式を生成します)。

シャミアの秘密分散法では、点の補間によって最大でd = t − 1 の多項式次数が生成される場合にのみ、分散はt整合になります。 ${\displaystyle s_{1},s_{2},...,s_{n}}$${\displaystyle (1,s_{1}),(2,s_{2}),...,(n,s_{n})}$

この観察に基づくと、ベナローのプロトコルは、株主が必要な検証を実行すると同時に、ディーラーの信頼性と誠実性も検証できることが示されます。

2 つ目の観察結果は、 2 つの多項式FとGの和の次数がt以下である場合、 FとGの両方の次数がt以下であるか、 FとGの両方の次数がtより大きいということです。この主張は、多項式関数の準同型性により明らかです。例:

ケース1:

${\displaystyle f_{1}=3x}$、、 ​ ${\displaystyle f_{2}=11x^{6}}$${\displaystyle t=6}$

ケース2:

${\displaystyle f_{1}=18x^{7}}$、、 ​ ${\displaystyle f_{2}=-18x^{7}}$${\displaystyle t=6}$

キャンセルしたケース：

${\displaystyle f_{1}=2x^{2}+3x^{3}}$、、 ​ ${\displaystyle f_{2}=x+x^{7}}$${\displaystyle t=6}$

インタラクティブな証明:
次の 5 つの手順により、株主に対するディーラーの誠実性が検証されます。

• ディーラーは多項式P を選択し、シェアを分配します（シャミアの秘密分散法に従って）。
• ディーラーは、非常に大きな数（k ）のt次のランダム多項式を構築し、シェアを分配します。${\displaystyle P_{1},...,P_{k}}$
• 株主は、m < k多項式のランダムなサブセットを選択します。
• ディーラーは、選択されたm個の多項式のシェアと残りのk − m個の合計の合計を公開し、結果もシェアします。${\displaystyle P_{i_{1}},...,P_{i_{m}}}$${\displaystyle P+\textstyle \sum _{j={m+1}}^{k}P_{j}}$
• 各シェアホルダーまたは検証者は、公開されたすべての多項式がt次であり、自身の既知のシェアに対応していることを確認します。

秘密は安全に保たれ、漏洩することはありません。

これらの 5 つのステップは、ディーラーの整合性に関する高い確率の結果を達成するために、少数の反復で実行されます。

診断 1:多項式の次数がt以下であり、ディーラーが他の多項式を公開するため(ステップ 4)、多項式Pの次数はt以下である必要があります(2 番目の観察ケース 1、これらのステップが異なる反復で繰り返される場合の高さの確率)。 ${\displaystyle P+\textstyle \sum _{j={m+1}}^{k}P_{j}}$${\displaystyle P_{i_{1}},...,P_{i_{m}}}$

診断 2:問題のパラメータの 1 つは、検証しようとしている秘密を公開しないようにすることです。このプロパティは、代数準同型を使用して検証を実行することで維持されます。(最大t 次までのランダムな多項式のセットと、 Pと最大t次までの他の多項式の合計のセットを組み合わせても、Pに関する有用な情報は得られません。)

検証可能な秘密共有は、エンドツーエンドの監査可能な投票システムを構築するために使用できます。

検証可能な秘密共有の技術を使用すると、ここで説明する選挙の問題を解決することができます。

選挙問題では、各有権者は 0 (反対) または 1 (賛成) のいずれかに投票でき、すべての投票の合計によって選挙の結果が決まります。選挙を実行するには、次の条件が満たされていることを確認する必要があります。

• 有権者のプライバシーは侵害されるべきではない。
• 選挙管理者は、有権者が不正行為を行っていないことを確認する必要があります。

検証可能な秘密共有を使用する場合、n 人の投票者によって 1 人の選挙管理者が置き換えられます。各投票者は、自分の秘密投票の 1 票を n 人の投票者全員に分配します。この方法では、投票者のプライバシーが保護され、最初の条件が満たされます。

多項式P を発見するのに十分なk < n 人の投票者が存在する場合、選挙結果の再構築は簡単です。

対話型証明は、投票シェアの検証を可能にするために、若干一般化することができます。各投票者は、対話型証明の 5 つの手順を使用して、投票係に対して自分の投票が正当であることを証明します (秘密シェアの配布フェーズで)。

VSS プロトコルのラウンド複雑度は、共有フェーズでの通信ラウンド数として定義されます。再構築は常に 1 ラウンドで実行できます。プレーヤーの数に関係なく、 t > 1の 1 ラウンド VSS は存在しません。完全に安全 (計算困難性の仮定に依存しない) かつ効率的 (多項式時間) な VSS プロトコルの境界を以下に示します。

• 秘密共有
• 安全なマルチパーティ計算
• 公開検証可能な秘密共有
• 検証可能なコンピューティング

• T. Rabinおよび M. Ben-Or、「検証可能な秘密共有と正直な多数決によるマルチパーティ プロトコル」。第 21 回 ACM コンピューティング理論シンポジウムの議事録 (米国ワシントン州シアトル、1989 年 5 月 14 ～ 17 日)。doi : 10.1145/73007.73014
• Rosario Gennaro、Yuval Ishai、Eyal Kushilevitz、Tal Rabin、「検証可能な秘密共有とセキュアマルチキャストのラウンド複雑性」。第 33 回 ACM コンピューティング理論シンポジウムの議事録 (ギリシャ、ヘルソニソス、ページ: 580 - 589、2001 年)
• Matthias Fitzi、Juan Garay、Shyamnath Gollakota、C. Pandu Rangan、Kannan Srinathan、ラウンド最適かつ効率的な検証可能な秘密共有。暗号理論、第 3 回暗号理論カンファレンス、TCC 2006、(米国ニューヨーク州ニューヨーク、2006 年 3 月 4 ～ 7 日)
• Oded Goldreich、セキュアなマルチパーティ計算
• Josh Cohen Benaloh、「秘密共有準同型: 秘密の共有の保持」、暗号学の進歩に関する議事録、CRYPTO '86、pp. 251–260、1987 年