論文翻訳: Practical Threshold Signatures

Abstract

RSA しきい値署名スキームを提示する。このスキームは以下の特性を持つ:

1. RSA 問題が困難であると仮定すると、ランダムオラクルモデルでは偽造不可能で堅牢である;
2. 署名分散 (signature share) の生成と検証は完全に非インタラクティブである;
3. 個々の署名分散のサイズは RSA モジュラスのサイズの定数倍に制限される。

Table of Contents

1. Abstract
2. 1 導入
   1. 過去の研究
   2. 構成
3. 2 システムモデルとセキュリティ要件
4. 3 プロトコル1: 非常にシンプルな RSA しきい値スキーム
5. 4 プロトコル1のセキュリティ分析
6. 5 プロトコル2: \(k\ge t+1\) 時の修正とセキュリティ分析
7. Acknowledgments
8. References
9. 参照

1 導入

\(k\)-\(l\) しきい値署名スキームは \(l\) 個のうち任意の \(k\) 個のプレーヤーの部分集合で署名を生成可能にするプロトコルであるが、\(k\) より少ないプレーヤーがプロトコルに参加しても有効な署名を生成することはできない。この偽造不可能特性 (non-forgeability property) は \(k\) 未満のプレーヤーのある部分集合に悪意があり共謀していたとしても維持される。一部のプレーヤーに悪意があったとしても有用であるようなしきい値署名のスキームは、堅牢 (robust) でもあるべきであり、悪意のあるプレーヤーが悪意のないプレーヤーの署名生成を阻害できないことを意味している。

しきい値署名スキームの概念は広く研究されてきた。しかしながら、過去に提案されたすべてのスキームには少なくとも次のような問題が存在する:

1. ランダムオラクルモデルであってもスキームに厳密なセキュリティ上の証明がない;
2. 署名分散の生成および/または検証がインタラクティブであり、さらに同期通信ネットワークを必要とする;
3. 個々の署名分散サイズはプレーヤーの数に対して線形増加する。

この状況を正すために、我々は次の特徴を備えた新しいしきい値 RSA 署名スキームを提示する。

1. RSA 問題が困難であると仮定すると、ランダムオラクルモデルでは偽造不可能であり堅牢である;
2. 署名分散の生成と検証は完全に非インタラクティブである;
3. 個々の署名分散サイズは RSA モジュラスのサイズの定数倍に制限される。

公開鍵と検証アルゴリズムの形式が通常の RSA 署名と同じであるという意味で、結果として生成される署名は完全に標準的な "ハッシュと反転" (hash and invert) RSA 署名であることを強調する。ただしキーにはいくつかの制限がある; つまり、暗号化指数 (public exponent) は \(l\) を超える素数でなければならず、モジュラスは 2 つの "強い" 素数積でなければならない。

我々のスキームは非常に単純であり、このようなスキームの提案や分析が過去になされていないことは驚くべきことである。

我々はまた、悪意を持つプレーヤーの最大数に特定のしきい値 \(t\) があり、最小の定足数を意味する別のしきい値 \(k\) があると想定した、より洗練されたしきい値署名スキームの概念を検討する。特定のメッセージに署名されているという事実は、少なくとも \(k-t\) 個の悪意を持たないプレーヤーが署名を承認したことを意味している。

しきい値署名スキームの過去の調査では常に (明示的または暗黙的に) \(k=t+1\) と想定されていた。我々はより一般的な \(k\gt t+1\) 設定も調査する。この一般化は、悪意のない参加者が必ずしも署名内容に同意するわけではないが、多数の当事者が特定の署名を承認したことを証明する場合に役に立つ。特に、非同期ネットワークのビザンチン合意プロトコルで送信されるメッセージを削減するために、\(k=l-t\) と \(t \lt l/3\) のしきい値署名を活用することができる。この詳細は [CKS00] で検討されている。

非同期ビザンチン合意への適用は実際にこの問題を研究する我々の動機であり、署名プロトコルが非インタラクティブであるという要件の主な理由である。しきい値署名に関するこれまでのほとんどの研究は、同期ネットワークを備えたモデルを想定しており、全てのプレーヤーが何らかの方法で同時に特定のメッセージ上で署名プロトコルを開始することに同意している。非同期ビザンチン合意を実装する場合、明らかにこのようなモデルで作業することはできない。

我々の "デュアルパラメータ" (dual-parameter) しきい値スキームの概念は単一パラメータしきい値スキームより強力なセキュリティ保障を提供する。さらに後者のようなスキームは実際の構築や分析がより困難であることを強調する。我々のデュアルパラメータしきい値スキームの概念をしきい値暗号の文献 (例えば [MS95]) にしばしば登場する弱い概念と混同すべきではない。このような弱い概念では暗号の再構成アルゴリズムは \(k'\) 個の分散を必要とするパラメータ \(k'\gt t\) が存在するが、一人の正直な参加者だけが分散を明らかにするだけでセキュリティ保障は失われる。我々の概念は \(k-t\) の正直な参加者が彼らの分散を明かさない限りセキュリティは失われない。

我々は "静的な破壊モデル" (static corruption model) を使用する: 攻撃者は攻撃前にどのプレーヤーを破損させるかを決めなければならない。これは過去のしきい値署名の研究と同様であり、(明示的または暗黙的に) 静的な破壊を想定してる。

我々の基本的なスキームである Protocol 1 は、RSA の仮定の下でランダムオラクルモデルにおいて \(k=t+1\) の場合に安全であることが証明できる。

我々はより一般的な設定 \(k \ge t+1\) で使用する別のスキームである Protocol 2 を示す。Protocol 2 は RSA の仮定の下での \(k=t+1\) の場合と、追加の仮定、つまり Decision Diffie-Hellman の適切な変種の仮定の下での \(k \gt t+1\) の場合で ─ 同じくランダムオラクルモデルにおいて ─ 安全であることが証明できる。

既に述べたように、セキュリティに関する我々の証明は、いわゆる "ランダムオラクルモデル" (random oracle model) で有効である。このモデルでは暗号論的ハッシュ関数がランダムオラクルに置き換えられる。このモデルは Fiat and Shamir [FS87] によって非公式に使用され、後に形式化され Bellare and Rogaway [BR93] で完全に明らかにされ、その後に多数の論文で使用された。

Protocol 1 では、通常の RSA 署名が安全であるという仮定があれば、堅牢性に対してランダムオラクルのみを必要とする。事実、Gennaro ら [GJKR96a] はランダムオラクルに頼ることなく分析することのできる非インタラクティブ分散検証スキームを提示している。我々が提案するものの代わりに分析でランダムオラクルを回避するこのような検証スキームを使用することができるが、これには実用面で特定の欠点があり、署名を分散する送信者と受信者の間に特別な関係を必要とする。または、単純なインタラクティブ分散検証スキームを使用できる。結果として得られる署名スキームはもはや完全に非インタラクティブではなくなるが、プレーヤー間の調整や同期は必要なくなる。これらは非常に簡単であるためここでは詳しく説明しない。

Protocol 2 の分析ではランダムオラクルモデルをより基本的な方法で使用する。これは必然的のようであったが、Protocol 2 の設計にはいくつかの自由度を取り入れ、実際に Protocol 1 より若干シンプルでより効果的となっている。従って \(k=t+1\) であっても Protocol 2 は Protocol 1 の魅力的な実用代替となる可能性がある。

我々は、ランダムオラクルモデルの安全性証明を、システムを破壊することができないという強力なエビデンスを提供するヒューリスティックな引数と見なしている。全てが平等であるため、ランダムオラクルモデルでのセキュリティ証明は "現実の世界" でのセキュリティ証明ほどではないが、全く証明がないより遙かに優れている。とにかく、通常の RSA 署名のセキュリティを正当化する唯一の方法であることから、ランダムオラクルモデルを使用することは不合理ではないようである。

過去の研究

Desmedt [Des87] はしきい値署名のより一般的な概念を導入している。Desmedt and Frankel [DF89] は "秘密分散" (secret sharing) [Sha79]、つまり有限体上の多項式補間に基づく、堅牢ではないしきい値 ElGamal スキーム [ElG85] を提示している。これらのスキームはサイズの小さな分散だが同期インタラクションを必要とする。Harn [Har94] は小さな分散サイズで堅牢なしきい値 ElGamal スキームを示しているが、ここでも同期インタラクションが必要となる。上記スキームの両方のセキュリティは十分な方法で厳密に分析できるようだが、どちらの論文でもこれは行われていない。Gennaro ら [GJKR96b] は分散サイズが小さい堅牢なしきい値 DSS スキームを提示したが、これも同期インタラクションを必要とする; 彼らは厳密なセキュリティ分析も提供している。

上記スキームは全てインタラクティブである。確かに、離散対数に基づく任意のしきい値署名スキームはインタラクティブであるように見受けられる。そのような署名スキームはランダム化されるため、署名者は乱数を共同で生成する必要があり、明らかにインタラクティブの必要がある。

Desmedt and Frankel は [DF89] の中でしきい値 RSA [RSA78] 署名スキームの設計の問題にも簡単に触れ、係数環 \(\vector{Z}_{\phi(n)}\) 上の多項式補間がいささか扱いにくいという事実から生じるいくつかの技術的な障害があることを指摘している。ここで \(n\) は RSA モジュラスであり \(\phi\) はオイラー係数関数である。その後 Desmedt and Frankel [DF91] は再びしきい値 RSA の問題に戻り、非インタラクティブで小さな分散サイズの堅牢ではないしきい値 RSA スキームを提示したがセキュリティ分析は行われなかった。Frankel and Desmedt [FD92] の結果はこれら [DF91] の結果を拡張し、小さな分散サイズで堅牢でないしきい値 RSA スキームに対するセキュリティ証明を提供しているが、同期インタラクションを必要とする。その後 De Santis ら [DDFY94] は [FD92] のスキームの (これもまた堅牢でない) バリエーションを提示した。これは (プレーヤーの数に応じて線形に成長する) 大きな分散サイズとインタラクションをトレードした。[FD92] と [DDFY94] の両方は \(\vector{Z}_{\phi(n)}[X]/(\Phi_q(X))\) 上で動作することにより \(\vector{Z}_{\phi(n)}\) 上の多項式補間の問題を回避した。ここで \(\Phi_q(X)\) は \(q\) 番目の (\(\bmod \phi(n)\) を取る) 循環多項式、\(q\) は \(l\) より大きい素数である。これは標準の秘密分散技術を直接適用できるため便利だが、インタラクションもしくは大きな分散サイズのどちらかを必要とする遙かに複雑なスキームに繋がる。

Gennaro ら [GJKR96a] は RSA しきい値システムを堅牢にするいくつかの一般的な手法を示している。

その後、Frankel ら [FGMY97b, FGMY97a] と Rabin [Rab98] は小さな分散サイズだが同期インタラクションを必要とする堅牢なしきい値 RSA スキームを提案し厳密に分析した。これらの論文は "\(\vector{Z}_{\phi(n)}\) 問題の補間" (interpolation over \(\vector{Z}_{\phi(n)}\) problem) に対して異なるアプローチを採用し、"秘密分散" のレイヤーを追加することでそれを回避し、インタラクションと複雑性を大幅に増やしている。これらのスキームには他の特徴もある。つまり "プロアクティブセキュリティ" (pro-active security) として知られているタイプのセキュリティを提供するがここでは取り上げない。

後述するように "\(\vector{Z}_{\phi(n)}\) 問題の補間" は実際には全く問題ではない ─ 非常に簡単で証明可能なセキュアしきい値 RSA スキームを得るために軽微な技術的問題を回避することは全く簡単である。堅牢性を必要としないのであればランダムオラクルさえも必要としない。我々は RSA 署名スキーム自体が安全であると想定している。

構成

§2 ではシステムモデルとしきい値署名のセキュリティ要件について説明する。§3 では Protocol 1 について説明する。§4 では \(k=t+1\) の場合の Protocol 1 を分析する。§5 では Protocol 2 を提示し、より一般的な場合である \(k \ge t+1\) を分析する。

2 システムモデルとセキュリティ要件

The Participants. インデックスが\(1, \ldots, l\) の \(l\) 個のプレーヤー集合と信頼できるディーラー (trusted dealer)、敵対者 (adversary) が存在する。また署名検証アルゴリズム (signature verification algorithm)、分散検証アルゴリズム (share verification algorithm)、分散結合アルゴリズム (share combining algorithm) も存在する。

2 つのパラメータが存在する:

唯一の要件は \(k \ge t+1\) および \(l - t \gt k\) であることである。

The Action. ゲームの開始時、敵対者は破損させる \(t\) 個のプレーヤーの部分集合を選択する。

ディーリングフェーズ (dealing phase) では、ディーラーは公開鍵 \(PK\) とともに秘密鍵分散 \(SK_1,\ldots,SK_l\)、検証鍵 \(VK, VK_1,\ldots,VK_l\) を生成する。敵対者は破損させるプレーヤーの秘密鍵分散とともに公開鍵と検証鍵を取得する。

ディーリングフェーズのあと、敵対者は破損していないプレーヤーに自分の選択したメッセージへの署名リクエストを送信する。そのようなリクエストに応じて、プレーヤーは指定されたメッセージの署名分散 (signature share) を出力する。

Robustness and Combining Shares. 署名検証アルゴリズムは公開鍵と共にメッセージと署名を入力として受け取り署名が有効かを判断する。署名分散検証アルゴリズムは \(PK\), \(VK\), \(VK_i\) と共にプレーヤー \(i\) からのメッセージ上の署名分散とメッセージを入力として受け取り、署名分散が有効かを判断する。分散結合アルゴリズムは入力として公開鍵、(おそらく) 検証鍵とともにメッセージとメッセージ上の \(k\) 個の有効な署名分散を受け取り、メッセージ上に有効な署名を出力する。

Non-forgeability. 敵対者がゲームの終わりに少なくとも \(k-t\) 個の破損していないプレーヤーへ署名リクエストとして送信されなかったメッセージに有効な署名を出力した場合、我々は敵対者が署名を偽造した (forges a signature) と表現する。敵対者が署名を偽造することが計算上実行不可能な場合、しきい値署名スキームは偽造不可能 (non-forgeable) であると表現する。

Discussion. このモデルでは署名分散の生成と検証が完全に非インタラクティブであることを明示的に要求していることに注意。

また 2 つの独立したパラメータ \(t\) と \(k\) を持つことにも注意。Introduction で述べたようにしきい値署名に関する以前の調査では \(k=t+1\) のケースのみが扱われていた。この場合、偽造不可能性要件は単に破損していないプレーヤーに署名を求めなかった場合に署名が偽造されることを述べている。見て分かるように \(k\gt t+1\) の場合に偽造不可能性を達成することは \(k=t+1\) の場合よりも困難である。単純化のため我々は \(k=t+1\) の場合から始める。

3 プロトコル1: 非常にシンプルな RSA しきい値スキーム

Protocol 1 について説明する。\(k=t+1\) については次のセクションで分析される。

The Dealer. ディーラーは等しい長さ (例えば 512 bit) の 2 つの大きな素数 \(p\) と \(q\) をランダムに選択する。ここで \(p=2p'+1\), \(q=2q'+1\) であり、\(p'\), \(q'\) 自体は素数である。RSA モジュラスは \(n=pq\) である。\(m=p'q'\) とする。ディーラーはまた素数 \(e\lt l\) となる RSA 公開指数 \(e\) を選択する。

公開鍵は \(PK=(n,e)\) である。

次に、ディーラーは \(de \equiv 1\) となるように \(d \in \vector{Z}\) を計算する。ディーラーは \(a_0 = d\) を設定し \(1\le i \le k-1\) に対して \(\{0,\ldots,m-1\}\) からランダムに \(a_i\) を選択する。数列 \(a_0,\ldots,a_{k-1}\) は多項式 \(f(X) = \sum_{i=0}^{k-1} a_i X^i \in \vector{Z}[X]\) を定義する。

\(1 \le i \le l\) に対してディーラーは \[ \begin{equation} s_i = f(i) \bmod m \label{private_key_share} \end{equation} \] を算出する。この数値 \(s_i\) はプレーヤー \(i\) の秘密鍵分散 \(SK_i\) である。

\(\vector{Z}_n^*\) 内の二乗 (square) の部分群を \(Q_n\) で示す。

次に、ディーラーはランダムな \(v \in Q_n\) を選択し、\(1 \le i \le l\) に対して \(v_i=v^{S_i} \in Q_n\) を計算する。これらの要素は \(VK=v\) と \(VK_i=v_i\) の検証鍵を定義する。

いくつかの予備的観察. \(\vector{Z}_n^* \simeq \vector{Z}_m \times \vector{Z}_2 \times \vector{Z}_2\) であることに注意。\(J_n\) をヤコビ記号 \((x|n)=1\) をもつ要素 \(x \in \vector{Z}_n^*\) の部分群を示すとすると \(Q_n \subset J_n \subset \vector{Z}_n^*\) となる; さらに \(Q_n\) は \(m\) 次の巡回であり、\(J_n\) は \(2m\) 次の巡回である。また \(-1 \in J_n \backslash Q_n\) である。

一般的に、全ての群計算は \(Q_n\) で行われ、対応する指数演算は \(\vector{Z}_m\) で行われることを保証する。\(m=p'q'\) は小さな素因数を持たないためこれは便利である。

ディーラーは \(v \in Q_n\) をランダムに選択するため \(v\) が \(Q_n\) を生成すると仮定できる。なぜならこれがほとんど無視できる確率でしか起きないためだ。このため値 \(v_i\) は値 \(s_i \bmod m\) を完全に決定する。

\(\{0,\ldots,l\}\) における任意の \(k\) 点の部分集合に対して、これらの点における \(f(X)\) の \(m\) の余剰値は \(f(X)\) の \(m\) の余剰値の係数を一意に決定し、従って \(\{0,\ldots,l\}\) における他の点の \(m\) 余剰における \(f(X)\) の \(m\) 余剰値を決定する。これは、対応する Vandermonde 行列の行列式が \(m\) に対して相対的に素数であるため、その行列が可逆な \(m\) 余剰であるという事実から導かれる。

これより、\(\{1,\ldots,l\}\) における \(k-1\) 個の点の任意の部分集合に対して、\(f(X)\) の \(m\) の余剰値の分布は一様であり、相互に独立していることとなる。

\(\Delta=l!\) とする。\(\{0,\ldots,l\}\) における \(k\) 個の点の任意の部分集合 \(S\) と、任意の \(i \in \{0,\ldots,l\} \backslash S\)、\(j \in S\) に対して、以下を定義することができる。\begin{equation} \lambda_{i,j}^S = \Delta \frac{\prod_{j' \in S \backslash \{j\}}(i-j')}{\prod_{j'\in S \backslash \{j\}}(j-j')} \in \vector{Z} \end{equation}

これらの値は標準的なラグランジュ補間式から導出される。分母が \(j! (l-j)!\) を除算しさらに \(l!\) を除算するためこれらは明らかに整数となる。これらの値の計算が容易であることも明かである。ラグランジュ補間式から以下の式が得られる: \begin{equation} \Delta \cdot f(i) \equiv \sum_{j \in S} \lambda_{i,j}^S f(j) \bmod m \end{equation}

有効な署名. 次に、有効な署名の外観について説明する。メッセージを \(\vector{Z}_n^*\) の要素にマッピングするハッシュ関数 \(H\) を必要とする。\(x=H(M)\) の場合、\(M\) の有効な署名は \(y^e =x\) となるような \(y \in \vector{Z}_n^*\) である。これは単なる古典的な RSA 署名である。

署名分散の生成. メッセージ \(M\) の署名分散がどのように生成されるかを説明する。\(x=H(M)\) とする。プレーヤー \(i\) の署名分散は \begin{equation} x_i = x^{2 \Delta_{S_i}} \in Q_n \end{equation} および "正当性の証明" (proof of correctness) で構成される。

正当性の証明は基本的に \(x_i^2\) の底 \begin{equation} \tilde{x} = x^{4\Delta} \end{equation} に対する離散対数が、\(v_i\) の底 \(v\) に対する離散対数と同じであることの証明に過ぎない。このため、Chaum and Pederson [CP92] によるよく知られたインタラクティブプロトコルを簡単に適用することができる。チャレンジを作成するためにハッシュ関数を使用することで我々はこのプロトコルを "壊し" て非インタラクティブにする ─ これはランダムオラクルモデルが必要とされてくるところである。我々はまた次数の不明な群 \(Q_n\) で作業しているという事実に対処する必要がある。しかし、これは十分に大きな整数を扱うだけで簡単に対処することができる。

ここで詳細について。\(L(n)\) を \(n\) のビット長とする。\(H'\) をハッシュ関数とし、その出力を \(L_1\)-bit 整数とする。ここで \(L_1\) はセカンダリセキュリティパラメータ (\(L_1=128\) など) である。正当性の証明を構築するために、プレーヤー \(i\) は乱数 \(r \in \{0, \ldots, 2^{L(n)+2L_1}-1\}\) を選択し \[ v'=v^4, x'=\tilde{x}^r, c=H'(v,\tilde{x},v_i,x_i^2,v',x'), z=s_i c+r \] を計算する。正当性の証明は \((z,c)\) である。

この正当性の証明を検証するために \[ c = H'(v, \tilde{x}, v_i, x_i^2, v^z v_i^{-c}, \tilde{x}^z x_i^{-2c}) \] であることを確認する。\(x_i\) ではなく \(x_i^2\) で作業する理由は、\(x_i\) が二乗であると想定されているにもかかわらずこれを簡単に検証できないためである。このため、我々は健全性を確保するために作業する必要がある \(Q_n\) で作業していることを確実にする。

分散の結合. 我々は次に、どのようにして署名分散を結合するかを説明する。プレーヤーの集合 \(S\) から有効な分散を持っていると仮定する。ここで \(S=\{i_1,\ldots,i_k\} \subset \{1,\ldots,l\}\) である。

\(x=H(M) \in \vector{Z}_n^*\) とし、\(x_{i_j}^2 = x^{4\Delta s_{i_j}}\) と仮定する。次に分散を結合するために \[ w = x_{i_1}^{2\lambda_{0,i_1}^S} \cdots x_{i_k}^{2\lambda_{0,i_k}^S} \] を計算する。ここで \(\lambda\) は (2) で定義された整数である。(3) より \(w^e = w^{e'}\) が得られる。ここで \begin{equation} e' = 4 \Delta^2 \end{equation} \(\gcd(e',e) = 1\) より、標準的なアルゴリズム \(y=w^a x^b\) を使用して \(y^e=x\) であるような \(y\) を計算するのは簡単である: ここで \(a\) と \(b\) は \(e'a + eb = 1\) となるような整数である。これらは \(e'\) と \(e\) の拡張ユークリッドアルゴリズムから得ることができる。

4 プロトコル1のセキュリティ分析

定理 1 . 標準の RSA 署名スキームがセキュアであると仮定すると、\(k=t+1\) での \(H'\) のランダムオラクルモデルでは、Protocol 1 は (堅牢で偽造不可能な) セキュアなしきい値署名スキームである。

我々は、敵対者が破損していないプレーヤーに署名分散を要求する場合にのみ使用する RSA 署名オラクルへのアクセスを得ているときの敵対者のビューをシミュレートする方法を示す。

\(i_1,\ldots,i_{k-1}\) を破損したプレーヤーの集合とする。全ての \(1 \le i \le l\) に対して \(s_i \equiv f(i) \bmod m\) であり、\(d \equiv f(0) \bmod m\) であることを思い出そう。

敵対者のビューをシミュレートするためには破損したプレーヤーの集合に属している \(s_{i_j}\) を集合 \(\{0,\cdots,\lfloor n/4 \rfloor - 1\}\) からランダムに選択する。我々は破損したプレーヤーの秘密鍵分散が集合 \(\{0,\ldots,m-1\}\) の乱数であることを既に論議している。\[ n/4 - m = (p' + q') / 2 + 1/4 = O(n^{1/2}) \] であり、これから一様分布 \(\{0,\ldots,\lfloor n/4 \rfloor -1\}\) と一様分布 \(\{0,\ldots,m-1\}\) 間の統計的距離が \(O(n^{-1/2})\) であることを簡単な計算により示す。

これらの \(s_{i_j}\) が選択されると故障していないプレーヤーに対する値 \(s_i\) も \(m\) 余剰として完全に決定されるが、簡単に計算することはできない。ただし、\(y^e=x\) の \(x,y \in \vector{Z}_n^*\) が与えられると、破損していないプレーヤーの \(x_i = x^{2 \Delta s_i}\) を \[ x_i = y^{2(\lambda_{i,0}^S + e(\lambda_{i,i_1}^S s_{i_1} + \cdots + \lambda_{i,i_{k-1}}^S s_{i_{k-1}}))} \] として簡単に計算できる。ここで \(S=\{0,i_1,\ldots,i_{k-1}\}\) である。これは (3) に従う。

この方法を使って我々は値 \(v, v_1, \ldots, v_l\) を生成することができ、標準 RSA 署名が与えられると任意の署名の任意の分散 \(x_i\) を生成することもできる。

この論議は、我々が分散 \(x_i\) を \(x^{2s_i}\) ではなく \(x^{2\Delta s_i}\) と定義した理由を表している。これと同じ考え方は検証可能な秘密分散の異なる問題だが関連している文脈で Feldman [Fel87] によって使用された。

"正当性の証明" に関しては、健全性と統計的なゼロ知識を得るためにハッシュ関数 \(H'\) のランダムオラクルモデルを呼び出すことができる。これは非常に簡単だが詳細をスケッチする。

まず健全性について考える。我々は敵対者が不正な分散から正当性の証明を構築することが無視できる確率にしかならないことを示したいと思う。有効な証明 \((z,c)\) と共に \(x\) と \(x_i\) が与えられたとする。\(c=H'(v,\tilde{x},v_i,x_i^2,v',x')\) であり、ここで \[ \tilde{x} = x^{4\Delta}, \ v' = v^z v_i^{-c}, \ x' = \tilde{x}^z x_i^{-2c} \] である。ここで \(\tilde{x}, v_i, x_i^2, v', x'\) は \(Q_n\) にあることが容易に分かり、\(v\) が \(Q_n\) を生成すると仮定する。従っていくつかの整数 \(\alpha, \beta\ \gamma, \delta\) に対して \[ \tilde{x} = v^\alpha, \ v_i = v^{S_i}, \ x_i^2 = v^\beta, \ v' = v^\gamma, \ x' = v^\delta \] となる。さらに \[ z - cs_i \equiv \gamma \bmod m \ \ \mbox{and} \ \ z \alpha - c \beta \equiv \delta \bmod m \] である。最初の式に \(\alpha\) を乗算し 2 番目の式を引くと \begin{equation} c(\beta - s_i \alpha) \equiv \alpha \gamma - \delta \bmod m \end{equation} である。ここで分散は \[ \begin{equation} \beta \equiv s_i \alpha \bmod m \end{equation} \] の場合にのみ正しい。条件 (8) の維持に失敗した場合、\(\bmod p'\) や \(\bmod q'\) の維持にも失敗していなければならないため、(7) はこれらの素数の一つを \(c\) 余剰として一意に決定する。しかし、ランダム男ラウルモデルでは \(c\) の分布は均一であり、ハッシュ関数への入力とは無関係であるため、この発生は無視できる確率である。

次にゼロ知識のシミュレーション可能性を考える。我々は値 \(s_i\) を知らなくても敵対者のビューをシミュレートするシミュレータを構築することができる。このビューには敵対者がオラクルを照会した時点でのランダムオラクルの値が含まれているため、シミュレータは完全にランダムオラクル役となる。オラクルが特定の点を事前に定義されていないのであれば、シミュレータはそれをランダムな値として定義し、敵対者がランダムオラクルに要求するときはどのような場合でも敵対者に値を返す。故障していないプレーヤーが与えられた \(x\), \(x_i\) に対する正当性の証明を生成することになっている場合、シミュレータはランダムに \(c \in \{0,\ldots,2^{L_1}-1\}\) と \(z \in \{0,\ldots,2^{L(n)+2L_1}-1\}\) を選択し、与えられた \(x\) と \(x_i\) に対して \((v,\tilde{x},v_i,x_i^2,v^z v_i^{-C},\tilde{x}^z x_i^{-2c})\) でのランダムオラクルの値を \(c\) と定義する。無視できる確率を除いて、シミュレータはこのポイントでのランダムオラクルを事前に定義していなかったため、今は自由に定義できる。証明は \((z,c)\) である。このシミュレータによって生成された分布が統計的に完全に近いことを検証するのは簡単である。

健全性から、我々はしきい値署名スキームの堅牢性を得た。ゼロ知識と上記の論議から標準 RSA 署名スキームがセキュアであるとの仮定の上でしきい値署名スキームの偽造不可能性、つまり、適用選択メッセージ攻撃 (adaptive chosen message attack) に対して実在的に偽造不可能であることを得た。この最後の仮定はさらに正当化することができる ([BR93] 参照): \(H\) に対するランダムオラクルモデルでは、この仮定は RSA 仮定に従う ─ 与えられた乱数 \(x \in \vector{Z}_n^*\) で \(y^e=x\) となるような \(y\) を算出することは困難である。

5 プロトコル2: \(k\ge t+1\) 時の修正とセキュリティ分析

我々はここで Protocol 2 を提示しその \(k \gt t+1\) 時のセキュリティを分析する。我々の Protocol 2 の分析では、ランダムオラクルモデルを基本的な方法で使用する必要がある。そのため、Protocol 1 よりも若干シンプルでより効果的なスキームを得るためにランダムオラクルモデルを十分に活用する。

Protocol 2 は Protocol 1 を以下のように修正することによって得られる。

ディーラーは秘密鍵分散 \(s_i\) を (\(\ref{private_key_share}\)) のように算出する代わりに \[ s_i = f(i) \Delta^{-1} \bmod m \] と計算する。

検証鍵 \(VK\) にヤコビ記号 \((u|n)=-1\) を持つ要素 \(u \in \vector{Z}_n^*\) を追加する。ヤコビ記号は効率的に計算でき、このような \(u\) は乱択で見つけることができる点に注意。

次に、分散の生成アルゴリズムを以下のように書き換える。\(\hat{x}=H(M)\) とする。\[ x = \left\{ \begin{array}{ll} \hat{x} & \ \ \mbox{if} \ (\hat{x}|n) = 1; \\ \hat{x} u^e & \ \ \mbox{if} \ (\hat{x}|n) = -1 \end{array} \right. \] これにより \(x\) のヤコビ記号を 1 にする。分散の生成、検証、結合のアルゴリズムは、以下の単純化を行うことを除いて、この \(x\) の新しい値を使って以前と同様に実行される: 我々は ((4), (5), (6) で定義されている) \(x_i\), \(\tilde{x}\) と \(e'\) を \[ x_i = x^{2s_i}, \ \hat{x} = x^4, \ e' = 4 \] と定義する。

従って、分散の生成や結合アルゴリズムにおけるやや "人工的" な \(\Delta\) の出現を排除する。

元々の分散の結合アルゴリズムは \(y^e=x\) となるような \(y\) を生成する。もし \(x=\hat{x} u^e\) なら \(H(M)\) の \(e\) 番目の根を得ることで \(y\) を \(u\) で割ることができるため標準 RSA 署名を取得できる。

これで Protocol 2 の説明は完了である。

Protocol 2 のセキュリティを分析するには \(H\) のランダムオラクルモデルで作業する必要があるだろう。作成する必要がある難易度の仮定は以下の通り:

• RSA 仮定 ─ ランダムな \(x \in \vector{Z}_n^*\) が与えられた場合 \(y^e=x\) となるような \(y\) を算出するのが困難;
• Decision Deffie-Hellman (DDH) 仮定 ─ \(g^a\), \(h^b\) を伴うランダムな \(g\), \(h \in Q_n\) が与えられた場合、\(a \equiv b \bmod m\) かどうかを判断することが困難

DDH 仮定をもう少し正確に行う。\(h \in Q_n\), \(a, b \in \vector{Z}_m\) と \(c \in \{0,1\}\) に対して \[ F(h,a,b,c) = \left\{ \begin{array}{ll} h^a & \ \ \mbox{if} c=0; \\ h^b & \ \ \mbox{if} c=1 \end{array} \right. \] と定義する。DDH 仮定では、上記のようならランダムな \(g \in Q_n\) およびランダムな \(h, a, b, c\) について、与えられた \(g\), \(h\), \(g^a\), \(F(h,a,b,c)\) から \(c\) を算出することは困難 ─ 無視できるエラー確率 ─ であると述べている。

これは平均的なケースでの複雑性を仮定していることに注意。標準の "ランダム自己集約" (random self reduction) 議論 [Sta96, NR97] より、入力が "\(g\) と \(h\) が \(Q_n\) 生成し \(\gcd(a-b,m) \notin \{p',q'\}\)" と制限されていることによって提供される最悪ケースの複雑性の仮定と同等である。

群 \(Q_n\) には小さな素因数 [Sho97] がないことから DDH は合理的な仮定であることに注意。

標準の "ハイブリッド" 論議 ([NR97] 参照) により、上記の DDH 仮定は以下と等価である: 分布 \[ (g, g^{a_1}, \ldots, g^{a_s}; h, h^{a_1}, \ldots, h^{a_s}) \] と \[ (g, g^{a_1}, \ldots, g^{a_s}; h, h^{b_1}, \ldots, h^{b_s}) \] は計算上区分できない。ここで \(s\) は任意の (小さな) 数値、\(g\) と \(h\) は \(Q_n\) のランダムな要素、\(a_i\) と \(b_i\) は \(m\) 余剰とする乱数である。DDH のランダムな自己循環性特性を使用して同様の等価性を証明することが可能であることに注意 ([Sho99] または [BBM00] 参照)。

定理 2 . \(H\) と \(H'\) のランダムオラクルモデルにおいて RSA と DDH が仮定されているならば Protocol 2 は \(k \ge t+1\) でセキュアなしきい値署名スキーム (堅牢で偽造不可能) である; さらに \(k = t+1\) の場合、RSA 仮定単独で同じことが言える。

堅牢特性の証明は前述と同様に行われる。ここでは偽造不可能性の証明にフォーカスする。

DDH 仮定を必要とする理由は次の通り: \(k \gt t+1\) の場合、一部の正直なプレーヤーは "ターゲット" メッセージの分散を生成しなければならず、この場合 "ダミー" 分散を生成できるように DDH が必要である。

\(H\) のランダムオラクルモデルを使用すると、これらの出力が正しい分布を持つ限り、シミュレータは \(H\) の出力を都合が良いように選択することができるだろう。

ここで一連のシミュレータについて説明する。

第一シミュレータ. 前のセクションで行ったように、シミュレータは破損したプレーヤー \(s_{i_1},\ldots,s_{i_t}\) の分散を \(\{0,\ldots,\lfloor n/4 \rfloor -1\}\) から選んだ乱数として選択する。

\(g, g_{i_{t+1}},\ldots,g_{i_{k-1}}\) を \(Q_n\) のランダム要素とする。ここで \(i_{t+1},\ldots,i_{k-1}\) は破損していないプレーヤーの任意のインデックスである。我々はこれらの群要素が全て \(Q_n\) に対する生成元であると仮定する。これはほとんど無視できる確率の場合である。方程式 \(g_{i_j}=g^{s_{i_j}}\) により、値 \(g, g_{i_{t+1}},\ldots,g_{i_{k-1}}\) は暗に \(m\) を法とする \(s_{i_{t+1}},\ldots,s_{i_{k-1}}\) を定義する。

次に分布 \[ \hat{x},x_1,\ldots,x_l \] からサンプリングする方法を示す。\(r \in \{0,\ldots,\lfloor n/4 \rfloor-1\}\) と \(b_1,b_2 \in \{0,1\}\) をランダムに選択する。\(\hat{x}=(g^r)^{\Delta^2 e}u^{-b_1 e} (-1)^{b_2}\) とし、対応する値 \(x\) を \((g^r)^{\Delta^2 e} (-1)^{b_2}\) と定義する。破損していないプレーヤー \(i_j \in \{i_{t+1},\ldots,i_{k-1}\}\) の一つに対して \(x_{s_j}=(g_{i_j}^r)^{2\Delta^2 e}\) を持つ。それ以外の故障していないプレーヤー \(i\) に対して \(x_i\) は \[ x_i = (g^r)^{2 (\lambda_{i,0}^S + \Delta e(\lambda_{i,i_1}^S s_{i_1} + \cdots + \lambda_{i,i_t}^S s_{i_t}))} (g_{i_{t+1}}^r)^{2 \Delta e \lambda_{i,i_{t+1}}^S} \cdots (g_{i_{k-1}}^r)^{2\Delta e \lambda_{i,i_{k-1}}^S} \] ここで \(S=\{0,i_1,\ldots,i_{k-1}\}\) である。繰り返すが、これは (3) からである。

我々はこの方法で値を生成して \(\hat{x}\) がランダムオラクル \(H\) の出力となるようにすることができる。また、基本的に同じ方法で検証鍵 \(v,v_1,\ldots,v_l\) も生成することができる。

このシミュレータは、全てのランダムオラクルクエリーに対してこの方法で \(\hat{x}\) を生成するため、このシミュレータで RSA 問題を破ることはできないだろう (これは最初のステップに過ぎない)。

このシミュレーションが統計定期に完全に近いことが簡単に分かる。注目すべき 1 つのことは \(\hat{x}\) は \(\vector{Z}_n^*\) でほぼ均一に分布していることである。この証明は、\(a\in\{0,\ldots,m-1\}\) と \(b_1,b_2\in\{0,1\}\) に対して \(\vector{Z}_n^*\) の全ての要素が \(g^a u^{-eb_1}(-1)^{b_2}\) として一意に表現できるという事実を利用している。

第二シミュレータ. このシミュレータは次の点を除いて最初のものと同じである。\(g,g_{i_{t+1}},\ldots,g_{i_{k-1}}\) および \(h,h_{i_{t+1}},\ldots,h_{i_{k-1}}\) を \(Q_n\) のランダムな要素とする。このシミュレータはどのメッセージが敵対者によって偽造されたかを "推測" する; つまり、偽造されたメッセージはランダムオラクルへの入力であり、シミュレータはこれらのクエリの一つが "ターゲット" メッセージであることを推測するだけである。

ターゲットメッセージに対して \(\hat{x},x_1,\ldots,x_l\) を生成するときに、シミュレータが計算において \(g^r,g_{i_{t+1}}^r,\ldots,g_{i_{k-1}}^r\) の代わりに値 \(h,h_{i_{t+1}},\ldots,h_{i_{k-1}}\) を使用して同じ計算を実行することを除いて、全てが前述と同じである。

このシミュレーションはもはや現実のゲームと統計的に見分けが付かなくなったが、ここでは DDH 仮定を用いる。この仮定の下では、敵対者は無視できない確率でメッセージを偽造し、そのメッセージが選択されたターゲットとなるだろう。

分散の "正当性の証明" は以前と同じように \(H'\) のランダムオラクルモデルを使用してシミュレートできることに注意。"証明された" というステートメントが偽であるという事実は興味深いが、重要ではない。

第三のシミュレータ. このシミュレータは愚痴の点を除いて第一と同じである。\(z\) を \(\vector{Z}_n^*\) のランダムな要素とする。ターゲットメッセージのハッシュ値に対してシミュレータは \(\hat{x}=z\) を設定する。また、敵対者は任意の破損していないプレーヤーからターゲットメッセージの署名分散 \(x_i\) を要求するたびに、敵対者は単純にランダムな二次余剰を出力する。"正当性の証明" は以前と同じようにシミュレートできる。敵対者が攻撃メッセージ上で \(k-t-1\) を超える署名分散を要求した場合、シミュレータは単純に停止しエラーを報告する。

このシミュレーションの分布は敵対者がターゲットメッセージの分散を過剰に要求しない限り第二シミュレーションの分布と同じことが容易に分かる。実際、第二シミュレータがターゲットメッセージ上で破損していないプレーヤーから署名分散 \(x_i\) を構築する方法のため、それらの \(k-t-1\) の任意のサブセットは \(Q_n\) で均一に分布し、敵対者のビューにおいて他の全ての変数から独立している。従って、敵対者は無視できない確率でターゲットメッセージ上に署名を偽造するだろう。これは特に、敵がそれほど多くの分散を要求しないことを意味している。さらに、この署名を偽造した場合、敵が \(\vector{Z}_n^*\) の \(z\) の \(e) 番目の根を計算しているということは RSA 仮定と矛盾する。

定理の証明を完了するために、単純に \(k=t+1\) の場合は、上記の論議において DDH は全く必要としていないことに注意。

Acknowledgments

Thanks to Rosario Gennaro for suggesting improvements to a previous version of the paper.

References

1. [BBM00]. M. Bellare, A. Boldyreva, and S. Micali. Public-key encryption in a multi-user setting: security proofs and improvements. In Advances in Cryptology–Eurocrypt 2000, pages 259–274, 2000.
2. [BR93] M. Bellare and P. Rogaway. Random oracles are practical: a paradigm for designing efficient protocols. In First ACM Conference on Computer and Communications Security, pages 62–73, 1993.
3. [CKS00] C. Cachin, K. Kursawe, and V. Shoup. Random oracles in Constantinople: practical asynchronous Byzantine agreement using cryptography. Manuscript, 2000.
4. [CP92] D. Chaum and T. Pedersen. Wallet databases with observers. In Advances in Cryptology–Crypto ’92, pages 89–105, 1992.
5. [DDFY94] A. De Santis, Y. Desmedt, Y. Frankel, and M. Yung. How to share a function securely. In 26th Annual ACM Symposium on Theory of Computing, pages 522–533, 1994.
6. [Des87] Y. Desmedt. Society and group oriented cryptography: a new concept. In Advances in Cryptology–Crypto ’87, pages 120–127, 1987.
7. [DF89] Y. Desmedt and Y. Frankel. Threshold cryptosystems. In Advances in Cryptology–Crypto ’89, pages 307–315, 1989.
8. [DF91] Y. Desmedt and Y. Frankel. Shared generation of authenticators and signatures. In Advances in Cryptology–Crypto ’91, pages 457–569, 1991.
9. [ElG85] T. ElGamal. A public key cryptosystem and signature scheme based on discrete logarithms. IEEE Trans. Inform. Theory, 31:469–472, 1985.
10. [FD92] Y. Frankel and Y. Desmedt. Parallel reliable threshold multisignature. Technical Report TR-92-04-02, Univ. of Wisconsin–Milwaukee, 1992.
11. [Fel87] P. Feldman. A practical scheme for non-interactive verifiable secret sharing. In 28th Annual Symposium on Foundations of Computer Science, pages 427–437, 1987.
12. [FGMY97a] Y. Frankel, P. Gemmall, P. MacKenzie, and M. Yung. Optimal-resilience proactive public-key cryptosystems. In 38th Annual Symposium on Foundations of Computer Science, 1997.
13. [FGMY97b] Y. Frankel, P. Gemmall, P. MacKenzie, and M. Yung. Proactive RSA. In Advances in Cryptology–Crypto ’97, 1997.
14. [FS87] A. Fiat and A. Shamir. How to prove yourself: practical solutions to identification and signature problems. In Advances in Cryptology–Crypto ’86, Springer LNCS 263, pages 186–194, 1987.
15. [GJKR96a] R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Robust and efficient sharing of RSA functions. In Advances in Cryptology–Crypto ’96, pages 157–172, 1996.
16. [GJKR96b] R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Robust threshold DSS. In Advances in Cryptology–Eurocrypt ’96, pages 354–371, 1996.
17. [Har94] L. Harn. Group-oriented (t, n) threshold digitial signature scheme and digital multisignature. IEE Proc.-Comput. Digit. Tech., 141(5):307–313, 1994.
18. [MS95] S. Micali and R. Sidney. A simple method for generating and sharing pseudo-random functions, with applications to Clipper-like key escrow systems. In Advances in Cryptology–Crypto ’95, pages 185–196, 1995.
19. [NR97] M. Naor and O. Reingold. Number-theoretic constructions of efficient pseudo-random functions. In 38th Annual Symposium on Foundations of Computer Science, 1997.
20. [Rab98] T. Rabin. A simplified approach to threshold and proactive RSA. In Advances in Cryptology–Crypto ’98, 1998.
21. [RSA78] R. L. Rivest, A. Shamir, and L. M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, pages 120–126, 1978.
22. [Sha79] A. Shamir. How to share a secret. Communications of the ACM, 22:612–613, 1979.
23. [Sho97] V. Shoup. Lower bounds for discrete logarithms and related problems. In Advances in Cryptology–Eurocrypt ’97, 1997.
24. [Sho99] V. Shoup. On formal models for secure key exchange. IBM Research Report RZ 3120, April 1999.
25. [Sta96] M. Stadler. Publicly verifiable secret sharing. In Advances in Cryptology–Eurocrypt ’96, pages 190–199, 1996.

参照

RSA に基づく非インタラクティブな署名分散の方法についての 1999 年の論文。

• Victor Shoup (2000) Practical Threshold Signatures