論文翻訳: Aggregate and Verifiably Encrypted Signatures from Bilinear Maps

概要

集約署名スキーム (aggregate signature scheme) は集約をサポートする電子署名である: \(n\) 人の異なるユーザからの \(n\) 個の異なるメッセージに対して \(n\) 個の署名がある場合、これら全ての署名を一つの短い署名に集約することができる。この単一の署名 (および \(n\) 個の元のメッセージ) は \(n\) 人のユーザが自裁に \(n\) 個の元のメッセージに署名したことを検証者に保証する (つまりユーザ \(i\) は \(i=1,\ldots,n\) のメッセージ \(M_i\) に署名した)。この論文では集約署名の概念を紹介し、そのような署名のセキュリティモデルを提示し、集約署名のいくつかの適用を提供する。我々は最近の Boneh, Lynn および Shacham による双線形写像に基づいた短い署名スキームから効率的な集約署名を構築する。集約署名は (チェーン内のすべての署名を集約することにより) 証明書チェーンのサイズを削減し、SBGP といったセキュアルーティングプロトコルでメッセージサイズを削減するために役に立つ。また集約署名は検証可能に暗号化された署名を生成することも示す。このような署名によって、検証者は特定の暗号文 \(C\) が特定のメッセージ \(M\) の署名の暗号であることをテストすることができる。検証可能な暗号化署名は契約書名プロトコルで使用される。最後に、同様のアイディアを使用して短い署名スキームを拡張し、単純なリング署名を提供できることを示す。

Table of Contents

1. 概要
2. 1 導入
3. 2 Co-gap Diffie-Hellman に基づく署名スキーム
   1. 2.1 双線形写像
   2. 2.2 Co-GDH 署名スキーム
4. 3 Aggregate Signature [under construction]
   1. 3.1 Bilinear Aggregate Signatures
   2. 3.2 Aggregate Signature Security
5. 4 Verifiably Encrypted Signatures
   1. 4.1 Verifiably Encrypted Signature Security
   2. 4.2 Aggregate Extraction
   3. 4.3 Verifiably Encrypted Signatures via Aggregation
   4. 4.4 The Bilinear verifiably-Encrypted Signature Scheme
   5. 4.5 Observations on Verifiably Encrypted Signatures
6. 5 Ring Signatures
   1. 5.1 Ring Signatures
   2. 5.2 Bilinear Ring Signatures
   3. 5.3 Security
   4. 5.4 Observations on Ring Signatures
7. 6 結論
8. 謝辞
9. 参照
10. 翻訳抄

1 導入

現実世界のアプリケーションの多くには、多くの異なるユーザによって生成された多くの異なるメッセージの署名が含まれている。例えば深さ \(n\) の公開鍵基盤 (PKI) では各ユーザに \(n\) 個の証明書チェーンが与えられている。チェーンには \(n\) 個の個別の証明書に対する \(n\) 個の認証局 (CA) による \(n\) 個の署名が含まれている。同様にセキュア BGP プロトコル (SBGP) [17] では、ネットワーク内のある長さ \(n\) のパスを証明する \(n\) 個の署名リストを各ルータが受け取る。ルータはパス内の自分のセグメントに署名し、\(n+1\) 個の署名の結果リストを次のルーターに転送する。結果としてルーティングメッセージ内の署名の数はパスの長さに比例する。これらの両アプリケーションは個別のパーティによって発行された個別のメッセージ上で署名のリストを圧縮する方法によって恩恵を受けるだろう。具体的には、チェーン内の \(n\) 個の署名を単一の署名に圧縮することによって X.509 証明書チェーンを短縮することができる。

集約署名スキームによりそのような圧縮を正確に表現することができる。\(n\) 人のユーザのそれぞれが公開鍵と秘密鍵のペア \((PK_i,SK_i)\) を持つと仮定する。ユーザ \(u_i\) はメッセージ \(M_i\) に署名して署名 \(\sigma_i\) を取得する。そして全ての \(\sigma_1,\ldots,\sigma_n\) を入力として短く圧縮された署名 \(\sigma\) を出力するパブリックな集約アルゴリズム (public aggregation algorithm)が存在する。誰でも \(n\) 個の署名を集約することができる。つまり、署名 \(\sigma_1\), \(\sigma_2\) は \(\sigma_{12}\) に集約でき、\(\sigma_3\) を集約してさらに \(\sigma_{123}\) を得ることができる。証明書チェーンを集約する場合、各 CA は独自の署名をチェーンに対して段階的に集約することができる。また \(PK_1,\ldots,PK_n,M_1,\ldots,M_n\) と \(\sigma\) を取り集約署名が有効かどうかを判断する集約検証アルゴリズム (aggregate verification algorithm) も存在する。直感的なセキュリティ要件は \(\sigma\) を生成した集約者が全ての \(\sigma_1,\ldots,\sigma_n\) の全てを与えた場合にのみ集約署名 \(\sigma\) が有効であると宣言されることである。正確なセキュリティ定義はセクション 3.2 に記載されている。従って集約署名は多数のユーザによる様々なメッセージに対して一度に否認防止を提供する。

我々は Boneh, Lynn, Shacham (BLS) [7] による最近の短い署名に基づき集約署名を構築する。この署名スキームは、Decision Diffie-Hellman 問題 (DDH) は簡単だが Computational Diffie-Hellman 問題 (CDH) は困難な群で機能する。我々はそのような群を gap 群と呼ぶ [7,25]。最近そのようなギャップ群 [7,18,8,4] を使用したいくつかの構成があった。驚くべきことに、効率的な集約署名を構築するためには gap 群は不十分である。代わりに我々の構築では群のペア \(G_1\), \(G_T\) と双線形写像 \(e: G_1 \times G_1 \to G_T\) を使用する。ここで CDH は \(G_1\) において困難とする。Joux and Nguyen [16] は写像 \(e\) を使用して \(G_1\) において DDH を解決するために使用できることを示したため \(G_1\) は gap 群である。我々が効率的に集約署名を構築するためには双線形写像によって提供される追加の構造が必要である。従って、我々の構築では双線形写像が DDH を解決するための単純なアルゴリズムを超える追加機能を提供する例である。双線形写像は過去に three-way Deffie-Hellman [6], Identity-Based Encryption (IBE) [5], Hierarchical IBE [15,13] で使用された。

集約署名はマルチ署名 [19,24,23,4] に関係している。マルチ署名では、一連のユーザが全て同じメッセージに対して署名し結果的に単一の署名となる。最近、Micali ら [9] はマルチ署名のセキュリティモデルを定義し、いくつかの構造と適用を提供した。我々が考えている証明書チェーンや SBGP などの適用にはマルチ署名は不十分である。これらの適用では個別のメッセージに対する署名を集約できる必要がある。Boldyreva [4] は、一般的な gap 群が BLS 署名からマルチ署名を構築するのに十分であることを最近示していることに注意。前述のように、集約署名を取得するには双線形写像によって提供される追加の機能が必要である。

証明書チェーンを圧縮するための集約署名の適用は Micali and Rivest [20] によって提起された未解決の問題に関連している: 証明書チェーンといくつかの特別な追加署名が与えられた場合、チェーン内の中間リンクを切り取ることができるだろうか? 集約署名を使用すると追加の署名なしで証明書チェーンを圧縮できるが、検証者は依然としてチェーン内のすべての中間リンクを認識している必要がある。バッチ RSA [9] もある署名圧縮を提供するが、これは単一の署名者が作成した署名に対してのみである。

集約署名のさらなる適用として、セクション 4 では特定の集約署名スキームによって検証可能な単純な暗号化署名が生成されることを示している。これらの署名によってユーザ Alice は Bob に第三者の公開鍵を使用して暗号化されたメッセージ \(M\) の署名を与え、Bob は暗号化された署名が有効であることを確認することができる。検証可能な暗号化署名はフェアな交換を可能にするために楽観的な契約書名プロトコル [1,2] で使用されている。過去の構成 [1,26] では暗号化された署名を検証するためにゼロ知識証明を必要としていた。セクション 4 の検証可能な暗号化署名は短く効率的に検証することができる。結果として生じる契約書名プロトコルは [10] の意味で悪用されないことに注意。

これらのアイディアの第三の適用として、セクション 5 では双線形写像を使用した単純なリング署名 [27] を構築する。上記のように双線形写像を使用した構築は gap 群のみを使用する構築よりも簡単で効率的である。

2 Co-gap Diffie-Hellman に基づく署名スキーム

我々はまず双線形写像と Gap Diffie-Hellman 署名 [7] に関連するいくつかの概念を確認する。本論文では以下の表記を使用する:

1. \(G_1\) と \(G_2\) は素数位数 \(p\) の 2 つの (乗法) 巡回群である;
2. \(g_1\) は \(G_1\) の生成元、\(g_2\) は \(G_2\) の生成元である;
3. \(\varphi\) は \(\varphi(g_1)=g_2\) となるような \(G_1\) から \(G_2\) への計算可能な同型 (computable isomorphism) である; そして
4. \(e\) は前述のように \(e:G_1 \times G_2 \to G_T\) となる計算可能な双線形写像である。

同型 \(\varphi\) はセキュリティを証明するために最も重要である。議論を一般的にするために \(\varphi\) が存在し効率的に計算が可能であると単純に仮定する。\(G_1\), \(G_2\) が楕円曲線 \(E/\mathbb{F}_q\) 上の点の群の部分群である場合、曲線上のトレース写像をこの同型として使用することができる (我々は \(G_1 \subseteq E(\mathbb{F}_{q^r})\)、\(G_2 \subseteq E(\mathbb{F}_q)\) と仮定する)。

論文全体を通じて、すべての群 \(G_1\), \(G_2\), \(G_T\) が乗法群で素数位数 \(p\) であるような双線形写像 \(e:G_1 \times G_2 \to G_T\) について考える。\(G_1=G_2\) と設定することができるが、\(G_1 \neq G_2\) であるより一般的なケースを考慮し、Miyaji ら [21] によって定義された非超特異楕円曲線の特定のファミリーを使用できるようにする。これらの曲線からはとても短い署名 [7] を生じさせることができる。これは短い集約署名やリング署名などにつながる。\(G_1\neq G_2\) のケースを処理するために我々は co-CDH と co-DDH 問題 [7] を定義する。\(G_1=G_2\) の場合、これらの問題は標準の CDH と DDH 問題に収束する。従って、論文の残りの部分では任意の \(G_1\), \(G_2\) について扱うが、簡単のため読者は \(G_1=G_2\)、\(g_1=g_2\) であり \(\varphi\) は恒等写像と仮定することができる。この設定により CDH および DDH 問題の自然な一般化が得られる。

Computational Co-Diffie-Hellman

与えられた \(g_1, g_1^a \in G_1\) と \(h \in G_2\) に対して \(h^a \in G_2\) を計算する。

Decision Co-Diffie-Hellman

与えられた \(g_1, g_1^a \in G_1\) と \(h, h^b \in G_2\) に対して \(a=b\) であれば yes と出力しそうでなければ no と出力する。\(a=b\) のとき \((g_1, g_1^a, h, h^a)\) を co-Diffie-Hellman タプルと呼ぶ。

\(G_1=G_2\) および \(g_1=g_2\) の場合、これらの問題は標準的な CDH および DDH に収束する。次に、co-GDH gap 群を co-DDH は容易だが co-CDH は困難であるような群のペア \(G_1\) と \(G_2\) として定義する。

定義 1 . 群 \(G_1\) と \(G_2\) は、\(G_1\) 上での群作用、\(G_2\) 上での群作用および \(G_1\) から \(G_2\) への写像 \(\varphi\) がある時間単位で計算可能であり、\(G_1\) と \(G_2\) 上の Decision co-Diffie-Hellman がある時間単位で解ける場合、共に co-Diffie-Hellman に対する決定群である。

定義 2 . 群 \(G_1\) と \(G_2\) の Computational co-Diffie-Hellman 問題の解法におけるアルゴリズム \(\mathcal{A}\) の優位性は \[ {\sf Adv \ co\mbox{-}CDH}_{\mathcal{A}} \overset{\rm def}{=} {\rm Pr} \left[ \mathcal{A}(g_1, g_1^a, h) = h^a : a \overset{\rm R}{\leftarrow} \mathbb{Z}_p, h \overset{\rm R}{\leftarrow} G_2 \right] \] 確率は \(a\), \(h\) および \(\mathcal{A}\) のコイントスより優先される。アルゴリズム \(\mathcal{A}\) は、もし \(\mathcal{A}\) が最大 \(t\) 時間内に実行され、\({\sf Adv co\mbox{-}CDH}_{\mathcal{A}}\) が少なくとも \(\epsilon\) である場合、\(G_1\) と \(G_2\) 上の Computational co-Diffie-Hellman は \((t,\epsilon)\)-break する。群 \(G_1\) と \(G_2\) は、もしそれらが co-Diffie-Hellman の決定群であり、それらの上で Computational co-Diffie-Hellman を \((t,\epsilon)\)-break するアルゴリズムが存在しないのであれば、共に \((t,\epsilon)\)-co-GDH 群である。

2.1 双線形写像

\(G_1\) と \(G_2\) を前述のような 2 つの群とし、\(|G_1| = |G_2| = |G_T|\) となるような追加の群 \(G_T\) を導入する。双線形写像は以下の特性を持つ写像 \(e:G_1 \times G_2 \to G_T\) である:

1. 双線形: 全ての \(u \in G_1\), \(v \in G_2\) および \(a,b \in \mathbb{Z}\) に対して \(e(u^a,v^b) = e(u,v)^{ab}\) である。
2. 非縮退: \(e(g_1,g_2) \neq 1\)。

これらの特性はさらに 2 つを暗示する: 任意の \(u \in G_1\), \(v_1,v_2 \in G_2\) に対して \(e(u,v_1 v_2) = e(u,v_1) \cdot e(u,v_2)\); 任意の \(u,v \in G_1\) に対して \(e(u, \varphi(v)) = e(v,\varphi(u))\)。

定義 3 . 2 つの群 \(G_1\) と \(G_2\) は、どちらかに対する群作用がある時間単位で計算でき、\(G_1\) から \(G_2\) への写像 \(\varphi\) がある時間時間単位で計算でき、双線形写像 \(e:G_1 \times G_2 \to G_T\) が存在し、そして \(e\) がある時間単位で計算可能な場合、共に双線形群である。

定義 4 . 2 つの群 \(G_1\) と \(G_2\) は、それらが双線形群であり、それらの上で Computational co-Diffie-Hellman を \((t,\epsilon)\)-break するアルゴリズムが存在しなければ、共に co-Diffie-Hellman に対する \((t,\epsilon)\)-双線形群である。

Joux and Nguyen [16] は効率的に計算可能な双線形写像 \(e\) が decision co-Diffie-Hellman 問題を解くアルゴリズムを提供することを示した。タプル \((g_1,g_1^a,h,h^h)\) に対して \[ a = b \bmod p \ \ \Leftrightarrow \ \ e(g_1,h^b) = e(g_1^a,h) \] である。従って、もし 2 つの群 \(G_1\) と \(G_2\) が共に co-Diffie-Hellman に対する \((t,\epsilon)\)-双線形群であれば、それらはまた \((t/2,\epsilon)\)-co-GDH 群でもある。この逆はおそらく真ではない。

2.2 Co-GDH 署名スキーム

任意の gap 群に基づくことができる [7] の署名スキームを確認する。これは \({\it KeyGen}\), \({\it Sign}\) および \({\it Verify}\) で構成され、ランダムオラクル [3] と見なされるフルドメインハッシュ \(h:\{0,1\}^* \to G_2\) を使用する。

鍵生成

ランダムに \(x \overset{\rm R}{\leftarrow} \mathbb{Z}_p\) を選択し \(v \leftarrow g_1^x\) を計算する。公開鍵は \(v \in G_1\) であり秘密鍵は \(x \in \mathbb{Z}_p\) である。

署名

与えられた秘密鍵 \(x\) とメッセージ \(M \in \{0,1\}^*\) に対して \(h \leftarrow h(M)\) を計算する。ここで \(h \in G_2\) であり \(\sigma \leftarrow h^x\) である。署名は \(\sigma \in G_2\) である。

検証

与えられた公開鍵 \(v\)、メッセージ \(M\) および署名 \(\sigma\) に対して \(h \leftarrow h(M)\) を計算し \((g_1,v,h,\sigma)\) が有効な co-Diffie-Hellman タプルかどうかを検証する。

co-GDH 署名は \(G_2\) の単一の元である。特定の楕円曲線ではこれらの署名は非常に短く、同様のセキュリティを備えた DSA 署名の半分のサイズとなる。[7] の定理 1 は \(G_1\) と \(G_2\) が Diffie-Hellman の co-gap 群であると仮定したランダムオラクルモデルでの選択メッセージ攻撃 [14] の下でのスキームの実在的偽造性を証明している。

3 Aggregate Signature

3.1 Bilinear Aggregate Signatures

3.2 Aggregate Signature Security

4 Verifiably Encrypted Signatures

4.1 Verifiably Encrypted Signature Security

4.2 Aggregate Extraction

4.3 Verifiably Encrypted Signatures via Aggregation

4.4 The Bilinear verifiably-Encrypted Signature Scheme

4.5 Observations on Verifiably Encrypted Signatures

5 Ring Signatures

5.1 Ring Signatures

5.2 Bilinear Ring Signatures

5.3 Security

5.4 Observations on Ring Signatures

6 結論

我々は集約署名の概念を導入し双線形写像に基づいて効率的な集約署名スキームを構築した。鍵の生成、集約および検証はインタラクションを必要としない。我々は攻撃者に偽造のための公開鍵とメッセージの選択を与えるモデルにおいてシステムのセキュリティを証明した。セキュリティに対して、個別のメッセージ上の署名の集約である場合にのみ集約署名が有効であるという追加の制約を導入した。この制約は我々が考慮している適用にとっては自然に満たされている。

我々は集約署名の適用をいくつか提供した。例えば証明書チェーンのサイズを縮小し SBGP などのプロトコルの帯域幅を削減するために使用できる。また、特定の集約署名スキームが検証可能な暗号化署名と検証可能な暗号化秘密鍵を提供することも示した。

双線形写像 [7,18,8,4] を使用した過去の署名構築では gap Diffie-Hellman 群 (つまり DDH は簡単だが CDH は困難) のみを必要としていた。この論文の署名構成では双線形写像によって提供される追加の構造が必要である。これらの構造は双線形写像が一般的な gap Diffie-Hellman 群よりも多くのパワーを提供する例である。

謝辞

The authors thank Leonid Reyzin, Liqun Chen, and Cynthia Dwork for helpful discussions about this work. The first author is supported by darpa, the Packard foundation, and an nsf career award. The third and fourth authors are supported by darpa and nsf.

参照

1. N. Asokan, V. Shoup, and M. Waidner. Optimistic fair exchange of digital signatures. IEEE J. Selected Areas in Comm., 18(4):593–610, April 2000.
2. F. Bao, R. Deng, and W. Mao. Efficient and practical fair exchange protocols with offline TTP. In Proceedings of IEEE Symposium on Security and Privacy, pages 77–85, 1998.
3. M. Bellare and P. Rogaway. The exact security of digital signatures: How to sign with RSA and Rabin. In Proceedings of Eurocrypt ’96, volume 1070 of LNCS, pages 399–416. Springer-Verlag, 1996.
4. A. Boldyreva. Efficient threshold signature, multisignature and blind signature schemes based on the gap-Diffie-Hellman-group signature scheme. In Proceedings of PKC 2003, volume 2567 of LNCS, pages 31–46. Springer-Verlag, 2003.
5. D. Boneh and M. Franklin. Identity-based encryption from the Weil pairing. In Proceedings of Crypto 2001, volume 2139 of LNCS, pages 213–29. Springer-Verlag, 2001.
6. D. Boneh, C. Gentry, B. Lynn, and H. Shacham. Aggregate and verifiably encrypted signatures from bilinear maps. Cryptology ePrint Archive, Report 2002/175, 2002. http://eprint.iacr.org/.
7. D. Boneh, B. Lynn, and H. Shacham. Short signatures from the Weil pairing. In Proceedings of Asiacrypt 2001, volume 2248 of LNCS, pages 514–32. SpringerVerlag, 2001. Full paper: http://crypto.stanford.edu/˜dabo/pubs.html.
8. Y. Dodis. Efficient construction of (distributed) verifiable random functions. In Proceedings of PKC 2003, volume 2567 of LNCS, pages 1–17. Springer-Verlag, 2003.
9. A. Fiat. Batch RSA. In Proceedings of Crypto ’89, pages 175–185, 1989.
10. J. Garay, M. Jakobsson, and P. MacKenzie. Abuse-free optimistic contract signing. In Proceedings of Crypto ’99, volume 1666 of LNCS, pages 449–466. SpringerVerlag, 1999.
11. P. Gemmel. An introduction to threshold cryptography. RSA CryptoBytes, 2(3):7–12, 1997.
12. R. Gennaro, T. Rabin, S. Jarecki, and H. Krawczyk. Robust and efficient sharing of RSA functions. J. Cryptology, 13(2):273–300, 2000.
13. C. Gentry and A. Silverberg. Hierarchical ID-based cryptography. In Proceedings of Asiacrypt 2002, volume 2501 of LNCS, pages 548–66. Springer-Verlag, 2002.
14. S. Goldwasser, S. Micali, and R. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Computing, 17(2):281–308, 1988.
15. J. Horwitz and B. Lynn. Toward hierarchical identity-based encryption. In Proceedings of Eurocrypt 2002, volume 2332 of LNCS, pages 466–81. Springer-Verlag, 2002.
16. A. Joux. A one round protocol for tripartite Diffie-Hellman. In Proceedings of ANTS IV, volume 1838 of LNCS, pages 385–94. Springer-Verlag, 2000.
17. S. Kent, C. Lynn, and K. Seo. Secure border gateway protocol (Secure-BGP). IEEE J. Selected Areas in Comm., 18(4):582–92, April 2000.
18. A. Lysyanskaya. Unique signatures and verifiable random functions from the DHDDH separation. In Proceedings of Crypto 2002, volume 2442 of LNCS, pages 597–612. Springer-Verlag, 2002.
19. S. Micali, K. Ohta, and L. Reyzin. Accountable-subgroup multisignatures (extended abstract). In Proceedings of CCS 2001, pages 245–54. ACM Press, 2001.
20. S. Micali and R. Rivest. Transitive signature schemes. In Proceedings of RSA 2002, volume 2271 of LNCS, pages 236–43. Springer-Verlag, 2002.
21. A. Miyaji, M. Nakabayashi, and S. Takano. New explicit conditions of elliptic curve traces for FR-reduction. IEICE Trans. Fundamentals, E84-A(5):1234–43, May 2001.
22. M. Naor. Deniable ring authentication. In Proceedings of Crypto 2002, volume 2442 of LNCS, pages 481–98. Springer-Verlag, 2002.
23. K. Ohta and T. Okamoto. Multisignature schemes secure against active insider attacks. IEICE Trans. Fundamentals, E82-A(1):21–31, 1999.
24. T. Okamoto. A digital multisignature scheme using bijective public-key cryptosystems. ACM Trans. Computer Systems, 6(4):432–441, 1998.
25. T. Okamoto and D. Pointcheval. The gap problems: A new class of problems for the security of cryptographic primitives. In Proceedings of PKC 2001, volume 1992 of LNCS, pages 104–118. Springer-Verlag, 2001.
26. G. Poupard and J. Stern. Fair encryption of RSA keys. In Proceedings of Eurocrypt 2000, volume 1807 of LNCS, pages 172–89. Springer-Verlag, 2000.
27. R. Rivest, A. Shamir, and Y. Tauman. How to leak a secret. In Proceedings of Asiacrypt 2001, volume 2248 of LNCS, pages 552–65. Springer-Verlag, 2001.
28. F. Zhang and K. Kim. ID-based blind signature and ring signature from pairings. In Proceedings of Asiacrypt 2002, volume 2501 of LNCS, pages 533–47. Springer-Verlag, 2002.

翻訳抄

GAP Diffie-Hellman と双線形写像を使用して BLS 署名派生スキーム、集約署名、ブラインド署名、リング署名を紹介する 2003 年の論文。集約署名は異なるユーザによる異なるメッセージに対する署名を単一の署名に集約する

1. Dan Boneh, Craig Gentry, Ben Lynn and Hovav Shacham. Aggregate and Verifiably Encrypted Signatures from Bilinear Maps, EUROCRYPT 2003: Advances in Cryptology, pages 416-432. Springer-Verlag, 2003.