Abstract
Sequential aggregate signature schemes allow n signers, in order, to sign a message each, at a lower total cost than the cost of n individual signatures. We present a sequential aggregate signature scheme based on trapdoor permutations (e.g., RSA). Unlike prior such proposals, our scheme does not require a signer to retrieve the keys of other signers and verify the aggregate-so-far before adding its own signature. Indeed, we do not even require a signer to know the public keys of other signers!
Moreover, for applications that require signers to verify the aggregate anyway, our schemes support lazy verification: a signer can add its own signature to an unverified aggregate and forward it along immediately, postponing verification until load permits or the necessary public keys are obtained. This is especially important for applications where signers must access a large, secure, and current cache of public keys in order to verify messages. The price we pay is that our signature grows slightly with the number of signers.
We report a technical analysis of our scheme (which is provably secure in the random oracle model), a detailed implementation-level specification, and implementation results based on RSA and OpenSSL. To evaluate the performance of our scheme, we focus on the target application of BGPsec (formerly known as Secure BGP), a protocol designed for securing the global Internet routing system. There is a particular need for lazy verification with BGPsec, since it is run on routers that must process signatures extremely quickly, while being able to access tens of thousands of public keys. We compare our scheme to the algorithms currently proposed for use in BGPsec, and find that our signatures are considerably shorter nonaggregate RSA (with the same sign and verify times) and have an order of magnitude faster verification than nonaggregate ECDSA, although ECDSA has shorter signatures when the number of signers is small.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ahn, J.H., Green, M., Hohenberger, S.: Synchronized aggregate signatures: new definitions, constructions and applications. In: ACM Conference on Computer and Communications Security (2010)
Bellare, M., Canetti, R., Krawczyk, H.: Keying Hash Functions for Message Authentication. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 1–15. Springer, Heidelberg (1996)
Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and Verifiably Encrypted Signatures from Bilinear Maps. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 416–432. Springer, Heidelberg (2003)
Boldyreva, A., Gentry, C., O’Neill, A., Yum, D.H.: Ordered multisignatures and identity-based sequential aggregate signatures, with applications to secure routing. In: ACM Conference on Computer and Communications Security, pp. 276–285. ACM (2007)
Brogle, K., Goldberg, S., Reyzin, L.: Implementation of sequential aggregate signatures with lazy verification (2011), http://www.cs.bu.edu/fac/goldbe/papers/bgpsec-sigs.html
Brogle, K., Goldberg, S., Reyzin, L.: Sequential aggregate signatures with lazy verification, Full version and implementation code (2011), http://www.cs.bu.edu/fac/goldbe/papers/bgpsec-sigs.html
Houidi, Z.B., Meulle, M., Teixeira, R.: Understanding slow bgp routing table transfers. In: Proc. ACM SIGCOMM Internet Measurement Conference, pp. 350–355. ACM, New York (2009)
Bagherzandi, A., Jarecki, S.: Identity-Based Aggregate and Multi-Signature Schemes Based on RSA. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 480–498. Springer, Heidelberg (2010)
Barreto, P.S.L.M., Naehrig, M.: Pairing-Friendly Elliptic Curves of Prime Order. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 319–331. Springer, Heidelberg (2006)
Bellare, M., Namprempre, C., Neven, G.: Unrestricted Aggregate Signatures. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 411–422. Springer, Heidelberg (2007)
Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: ACM Conference on Computer and Communications Security, pp. 62–73 (1993)
Bellare, M., Rogaway, P.: The Exact Security of Digital Signatures - How to Sign with RSA and Rabin. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 399–416. Springer, Heidelberg (1996)
Chatterjee, S., Hankerson, D., Knapp, E., Menezes, A.: Comparing two pairing-based aggregate signature schemes. Des. Codes Cryptography 55(2-3), 141–167 (2010)
The CIDR report, http://www.cidr-report.org
Cheng, X., Liu, J., Guo, L., Wang, X.: Identity-based multisignature and aggregate signature schemes from m-torsion groups. Journal of Electronics (China) 23(4) (July 2006)
Cheng, X., Liu, J., Wang, X.: Identity-Based Aggregate and Verifiably Encrypted Signatures from Bilinear Pairing. In: Gervasi, O., Gavrilova, M.L., Kumar, V., Laganá, A., Lee, H.P., Mun, Y., Taniar, D., Tan, C.J.K. (eds.) ICCSA 2005. LNCS, vol. 3483, pp. 1046–1054. Springer, Heidelberg (2005)
Coron, J.-S.: Optimal Security Proofs for PSS and Other Signature Schemes. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 272–287. Springer, Heidelberg (2002)
Chi, Y.-J., Oliveira, R., Zhang, L.: Cyclops: The Internet AS-level observatory. In: ACM SIGCOMM CCR (2008)
Chakrabarti, S., Chandrasekhar, S., Singhal, M., Calvert, K.L.: An efficient and scalable quasi-aggregate signature scheme based on lfsr sequences. IEEE Trans. Parallel Distrib. Syst. 20(7), 1059–1072 (2009)
Department of Homeland Security, Science and Technology Directorate, Cyber Security Division, Secure Protocols for Routing Infrastructure project. Personal Communication
Eikemeier, O., Fischlin, M., Götzmann, J.-F., Lehmann, A., Schröder, D., Schröder, P., Wagner, D.: History-Free Aggregate Message Authentication Codes. In: Garay, J.A., De Prisco, R. (eds.) SCN 2010. LNCS, vol. 6280, pp. 309–328. Springer, Heidelberg (2010)
Fischlin, M., Lehmann, A., Schröder, D.: History-free sequential aggregate signatures. Technical Report 2011/231, Cryptology ePrint archive (2011), http://eprint.iacr.org
Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM 33(4), 792–807 (1986)
Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17(2), 281–308 (1988)
Gentry, C., Ramzan, Z.: Identity-Based Aggregate Signatures. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006. LNCS, vol. 3958, pp. 257–273. Springer, Heidelberg (2006)
Herranz, J.: Deterministic identity-based signatures for partial aggregation. Comput. J. 49(3), 322–330 (2006)
Hwang, J.Y., Lee, D.H., Yung, M.: Universal forgery of the identity-based sequential aggregate signature scheme. In: Li, W., Susilo, W., Tupakula, U.K., Safavi-Naini, R., Varadharajan, V. (eds.) ASIACCS, pp. 157–160. ACM (2009)
Huston, G. (ed.): The Profile for Algorithms and Key Sizes for Use in the Resource Public Key Infrastructure (RPKI). IETF RFC 6485 (February 2012), http://tools.ietf.org/html/rfc6485
IEEE Std 1363-2000. IEEE standard specifications for public-key cryptography (2002)
Kent, S., Lynn, C., Seo, K.: Secure border gateway protocol (S-BGP). J. Selected Areas in Communications 18(4), 582–592 (2000)
Karpilovsky, E., Rexford, J.: Using forgetful routing to control bgp table size. In: Proceedings of the 2006 ACM CoNEXT Conference, CoNEXT 2006, pp. 2:1–2:12. ACM, New York (2006)
Katz, J., Wang, N.: Efficiency improvements for signature schemes with tight security reductions. In: Jajodia, S., Atluri, V., Jaeger, T. (eds.) ACM Conference on Computer and Communications Security, pp. 155–164. ACM (2003)
Lepinski, M. (ed.): BGPSEC Protocol Specification. IETF Network Working Group, Internet-Draft (July 2012), http://tools.ietf.org/html/draft-ietf-sidr-bgpsec-protocol-04
Lysyanskaya, A., Micali, S., Reyzin, L., Shacham, H.: Sequential Aggregate Signatures from Trapdoor Permutations. In: Cachin, C., Camenisch, J. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 74–90. Springer, Heidelberg (2004)
Lu, S., Ostrovsky, R., Sahai, A., Shacham, H., Waters, B.: Sequential Aggregate Signatures and Multisignatures Without Random Oracles. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 465–485. Springer, Heidelberg (2006)
Neven, G.: Efficient Sequential Aggregate Signed Data. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 52–69. Springer, Heidelberg (2008)
FIPS publication 186-3: Digital signature standard (DSS) (June 2009), http://csrc.nist.gov/publications/PubsFIPS.html
OpenSSL toolkit, http://openssl.org/
Rückert, M., Schröder, D.: Aggregate and Verifiably Encrypted Signatures from Multilinear Maps without Random Oracles. In: Park, J.H., Chen, H.-H., Atiquzzaman, M., Lee, C., Kim, T.-h., Yeo, S.-S. (eds.) ISA 2009. LNCS, vol. 5576, pp. 750–759. Springer, Heidelberg (2009)
Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)
PKCS #1: RSA Encryption Standard. Version 2.1. RSA Laboratories (June 2002), ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-1/pkcs-1v2-1.pdf
Michael Scott. MIRACL library (2011), http://www.shamus.ie/
Smith, P.: BGP routing table analysis (2012), http://thyme.rand.apnic.net/ . See historical data—e.g., APNIC analysis summary for (September 7, 2012), http://thyme.apnic.net/ap-data/2012/09/07/0400/mail-global
Sriram, K. (ed.): BGPSEC Design Choices and Summary of Supporting Discussions. The Internet Engineering Task Force (IETF) Network Working Group (July 2012), http://tools.ietf.org/html/draft-sriram-bgpsec-design-choices-02
Sharmila Deva Selvi, S., Sree Vivek, S., Shriram, J., Kalaivani, S., Pandu Rangan, C.: Security analysis of aggregate signature and batch verification signature schemes. Technical Report 2009/290, Cryptology ePrint archive (2009), http://eprint.iacr.org
Sharmila Deva Selvi, S., Sree Vivek, S., Shriram, J., Pandu Rangan, C.: Identity based partial aggregate signature scheme without pairing. Report 2010/461, Cryptology ePrint archive (2010), http://eprint.iacr.org
Vanstone, S.: Responses to NIST’s proposal. Communications of the ACM 35, 50–52 (1992)
Wen, Y., Ma, J.: An aggregate signature scheme with constant pairing operations. In: CSSE (3). IEEE Computer Society (2008)
Xu, J., Zhang, Z., Feng, D.: ID-Based Aggregate Signatures from Bilinear Pairings. In: Desmedt, Y.G., Wang, H., Mu, Y., Li, Y. (eds.) CANS 2005. LNCS, vol. 3810, pp. 110–119. Springer, Heidelberg (2005)
Yoon, H., Cheon, J.H., Kim, Y.: Batch Verifications with ID-Based Signatures. In: Park, C., Chee, S. (eds.) ICISC 2004. LNCS, vol. 3506, pp. 233–248. Springer, Heidelberg (2005)
Zhao, M., Smith, S.W., Nicol, D.M.: Aggregated path authentication for efficient BGP security. In: ACM Conference on Computer and Communications Security, pp. 128–138. ACM (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 International Association for Cryptologic Research
About this paper
Cite this paper
Brogle, K., Goldberg, S., Reyzin, L. (2012). Sequential Aggregate Signatures with Lazy Verification from Trapdoor Permutations. In: Wang, X., Sako, K. (eds) Advances in Cryptology – ASIACRYPT 2012. ASIACRYPT 2012. Lecture Notes in Computer Science, vol 7658. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34961-4_39
Download citation
DOI: https://doi.org/10.1007/978-3-642-34961-4_39
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34960-7
Online ISBN: 978-3-642-34961-4
eBook Packages: Computer ScienceComputer Science (R0)