Efficient sequential aggregate signed data. (English) Zbl 1149.94326
Smart, Nigel (ed.), Advances in cryptology – EUROCRYPT 2008. 27th annual international conference on the theory and applications of cryptographic techniques, Istanbul, Turkey, April 13–17, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-78966-6/pbk). Lecture Notes in Computer Science 4965, 52-69 (2008).
Summary: We generalize the concept of sequential aggregate signatures (SAS), proposed by Lysyanskaya, Micali, Reyzin, and Shacham (LMRS) at Eurocrypt 2004, to a new primitive called sequential aggregate signed data (SASD) that tries to minimize the total amount of transmitted data, rather than just signature length. We present SAS and SASD schemes that offer numerous advantages over the LMRS scheme. Most importantly, our schemes can be instantiated with uncertified claw-free permutations, thereby allowing implementations based on low-exponent RSA and factoring, and drastically reducing signing and verification costs. Our schemes support aggregation of signatures under keys of different lengths, and the SASD scheme even has as little as 160 bits of bandwidth overhead. Finally, we present a multi-signed data scheme that, when compared to the state-of-the-art multi-signature schemes, is the first scheme with non-interactive signature generation not based on pairings. All of our constructions are proved secure in the random oracle model based on families of claw-free permutations.
For the entire collection see [Zbl 1133.94008].
For the entire collection see [Zbl 1133.94008].
References:
| [1] | Blum, M.; Feldman, P.; Micali, S., Non-interactive zero-knowledge and its applications, 20th ACM STOC, 103-112 (1988), New York: ACM Press, New York |
| [2] | Boneh, D.; Gentry, C.; Lynn, B.; Shacham, H.; Biham, E., Aggregate and verifiably encrypted signatures from bilinear maps, Advances in Cryptology - EUROCRPYT 2003, 416-432 (2003), Heidelberg: Springer, Heidelberg · Zbl 1038.94553 · doi:10.1007/3-540-39200-9_26 |
| [3] | Boldyreva, A.; Gentry, C.; O’Neill, A.; Yum, D. H., Ordered multisignatures and identity-based sequential aggregate signatures, with applications to secure routing, ACM CCS 2007, 276-285 (2007), New York: ACM Press, New York · doi:10.1145/1315245.1315280 |
| [4] | Bellare, M.; Neven, G., Multi-signatures in the plain public-key model and a general forking lemma, ACM CCS 2006, 390-399 (2006), New York: ACM Press, New York · doi:10.1145/1180405.1180453 |
| [5] | Bellare, M.; Neven, G.; Abe, M., Identity-based multi-signatures from RSA, Topics in Cryptology - CT-RSA 2007, 145-162 (2006), Heidelberg: Springer, Heidelberg · Zbl 1177.94181 · doi:10.1007/11967668_10 |
| [6] | Bellare, M.; Namprempre, C.; Neven, G.; Arge, L.; Cachin, C.; Jurdziński, T.; Tarlecki, A., Unrestricted aggregate signatures, Automata, Languages and Programming, 411-422 (2007), Heidelberg: Springer, Heidelberg · Zbl 1171.94363 · doi:10.1007/978-3-540-73420-8_37 |
| [7] | Boldyreva, A.; Desmedt, Y. G., Threshold signatures, multisignatures and blind signatures based on the gap-Diffie-Hellman-group signature scheme, Public Key Cryptography - PKC 2003, 31-46 (2002), Heidelberg: Springer, Heidelberg · Zbl 1033.94552 · doi:10.1007/3-540-36288-6_3 |
| [8] | Bellare, M.; Rogaway, P., Random oracles are practical: A paradigm for designing efficient protocols, ACM CCS 1993, 62-73 (1993), New York: ACM Press, New York · doi:10.1145/168588.168596 |
| [9] | Bellare, M.; Rogaway, P.; Maurer, U. M., The exact security of digital signatures: How to sign with RSA and Rabin, Advances in Cryptology - EUROCRYPT ’96, 399-416 (1996), Heidelberg: Springer, Heidelberg · Zbl 1304.94094 |
| [10] | Bellare, M.; Yung, M., Certifying permutations: Noninteractive zero-knowledge based on any trapdoor permutation, Journal of Cryptology, 9, 3, 149-166 (1996) · Zbl 0861.94013 · doi:10.1007/s001459900009 |
| [11] | Camenisch, J.; Michels, M.; Stern, J., Proving in zero-knowledge that a number is the product of two safe primes, Advances in Cryptology - EUROCRYPT ’99, 107-122 (1999), Heidelberg: Springer, Heidelberg · Zbl 0971.94009 |
| [12] | Coron, J.-S.; Bellare, M., On the exact security of full domain hash, Advances in Cryptology - CRYPTO 2000, 229-235 (2000), Heidelberg: Springer, Heidelberg · Zbl 0995.94533 · doi:10.1007/3-540-44598-6_14 |
| [13] | Catalano, D.; Pointcheval, D.; Pornin, T., Trapdoor hard-to-invert group isomorphisms and their application to password-based authentication, Journal of Cryptology, 20, 1, 115-149 (2007) · Zbl 1115.68072 · doi:10.1007/s00145-006-0431-8 |
| [14] | Gentry, C.; Ramzan, Z.; Yung, M.; Dodis, Y.; Kiayias, A.; Malkin, T. G., Identity-based aggregate signatures, Public Key Cryptography - PKC 2006, 257-273 (2006), Heidelberg: Springer, Heidelberg · Zbl 1151.94511 · doi:10.1007/11745853_17 |
| [15] | Hayashi, R.; Okamoto, T.; Tanaka, K.; Bao, F.; Deng, R.; Zhou, J., An RSA family of trap-door permutations with a common domain and its applications, Public Key Cryptography - PKC 2004, 291-304 (2004), Heidelberg: Springer, Heidelberg · Zbl 1198.94097 |
| [16] | Itakura, K.; Nakamura, K., A public-key cryptosystem suitable for digital multisignatures, NEC Research & Development, 71, 1-8 (1983) |
| [17] | Kent, S.; Lynn, C.; Seo, K., Secure border gateway protocol (S-BGP), IEEE JSAC, 18, 4, 582-592 (2000) |
| [18] | Katz, J.; Wang, N., Efficiency improvements for signature schemes with tight security reductions, ACM CCS 2003, 155-164 (2003), New York: ACM Press, New York · doi:10.1145/948109.948132 |
| [19] | Lysyanskaya, A.; Micali, S.; Reyzin, L.; Shacham, H.; Cachin, C.; Camenisch, J. L., Sequential aggregate signatures from trapdoor permutations, Advances in Cryptology - EUROCRYPT 2004, 74-90 (2004), Heidelberg: Springer, Heidelberg · Zbl 1122.94385 |
| [20] | Lu, S.; Ostrovsky, R.; Sahai, A.; Shacham, H.; Waters, B.; Vaudenay, S., Sequential aggregate signatures and multisignatures without random oracles, Advances in Cryptology - EUROCRYPT 2006, 465-485 (2006), Heidelberg: Springer, Heidelberg · Zbl 1140.94358 · doi:10.1007/11761679_28 |
| [21] | Neven, G.: Efficient sequential aggregate signed data. Cryptology ePrint Archive (2008) · Zbl 1149.94326 |
| [22] | Rivest, R. L.; Shamir, A.; Adleman, L. M., A method for obtaining digital signature and public-key cryptosystems, Communications of the Association for Computing Machinery, 21, 2, 120-126 (1978) · Zbl 0368.94005 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
