Abstract
With computer networks spreading into a variety of new environments, the need to authenticate and secure communication grows. Many of these new environments have particular requirements on the applicable cryptographic primitives. For instance, several applications require that communication overhead be small and that many messages be processed at the same time. In this paper we consider the suitability of public key signatures in the latter scenario. That is, we consider signatures that are 1) short and 2) where many signatures from (possibly) different signers on (possibly) different messages can be verified quickly.
We propose the first batch verifier for messages from many (certified) signers without random oracles and with a verification time where the dominant operation is independent of the number of signatures to verify. We further propose a new signature scheme with very short signatures, for which batch verification for many signers is also highly efficient. Prior work focused almost exclusively on batching signatures from the same signer. Combining our new signatures with the best known techniques for batching certificates from the same authority, we get a fast batch verifier for certificates and messages combined. Although our new signature scheme has some restrictions, it is the only solution, to our knowledge, that is a candidate for some pervasive communication applications.
Chapter PDF
Similar content being viewed by others
References
An, J.H., Dodis, Y., Rabin, T.: On the security of joint signature and encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 83–107. Springer, Heidelberg (2002)
Bellare, M., Garay, J.A., Rabin, T.: Fast batch verification for modular exponentiation and digital signatures. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 236–250. Springer, Heidelberg (1998)
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, Springer, Heidelberg (2003)
Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. J. Cryptology 17(4), 297–319 (2004)
Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 514–532. Springer, Heidelberg (2001)
Boyd, C., Pavlovski, C.: Attacking and repairing batch verification schemes. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 58–71. Springer, Heidelberg (2000)
Boyen, X., Waters, B.: Compact group signatures without random oracles. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 427–444. Springer, Heidelberg (2006)
Camenisch, J., Lysyanskaya, A.: Signature schemes and anonymous credentials from bilinear maps. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 56–72. Springer, Heidelberg (2004)
Canetti, R., Halevi, S., Katz, J.: A forward-secure public-key encryption scheme. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 255–271. Springer, Heidelberg (2003)
Cao, T., Lin, D., Xue, R.: Security analysis of some batch verifying signatures from pairings. International Journal of Network Security 3(2), 138–143 (2006)
Car 2 Car. Communication consortium, http://car-to-car.org
Cha, J.C., Cheon, J.H.: An identity-based signature from gap Diffie-Hellman groups. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 18–30. Springer, Heidelberg (2002)
Chatterjee, S., Sarkar, P.: Trading time for space: Towards an efficient IBE scheme with short(er) public parameters in the standard model. In: Won, D.H., Kim, S. (eds.) ICISC 2005. LNCS, vol. 3935, pp. 424–440. Springer, Heidelberg (2006)
Chen, L., Cheng, Z., Smart, N.: Identity-based key agreement protocols from pairings. Cryptology ePrint Archive: Report 2006/199 (2006)
Cheon, J.H., Kim, Y., Yoon, H.J.: A new ID-based signature with batch verification. Cryptology ePrint Archive: Report 2004/131 (2004)
Cui, S., Duan, P., Chan, C.W.: An efficient identity-based signature scheme with batch verifications. In: InfoScale ’06, p. 22 (2006)
Fiat, A.: Batch RSA. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 175–185. Springer, Heidelberg (1990)
Galbraith, S.D., Paterson, K.G., Smart, N.P.: Pairings for cryptographers. Cryptology ePrint Archive: Report 2006/165 (2006)
Gentry, C., Ramzan, Z.: Identity-based aggregate signatures. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T.G. (eds.) PKC 2006. LNCS, vol. 3958, pp. 257–273. Springer, Heidelberg (2006)
Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Computing 17(2) (1988)
Granger, R., Smart, N.: On computing products of pairings. Cryptology ePrint Archive: Report 2006/172 (2006)
Harn, L.: Batch verifying multiple DSA digital signatures. Electronics Letters 34(9), 870–871 (1998)
Harn, L.: Batch verifying multiple RSA digital signatures. Electronics Letters 34(12), 1219–1220 (1998)
Hoshino, F., Abe, M., Kobayashi, T.: Lenient/strict batch verification in several groups. In: Davida, G.I., Frankel, Y. (eds.) ISC 2001. LNCS, vol. 2200, pp. 81–94. Springer, Heidelberg (2001)
Hwang, M.-S., Lee, C.-C., Tang, Y.-L.: Two simple batch verifying multiple digital signatures. In: Qing, S., Okamoto, T., Zhou, J. (eds.) ICICS 2001. LNCS, vol. 2229, pp. 233–237. Springer, Heidelberg (2001)
Hwang, M.-S., Lin, I.-C., Hwang, K.-F.: Cryptanalysis of the batch verifying multiple RSA digital signatures. Informatica, Lith. Acad. Sci. 11(1), 15–19 (2000)
IEEE. 5.9 GHz Dedicated Short Range Communications, http://grouper.ieee.org/groups/scc32/dsrc
Koblitz, N., Menezes, A.: Pairing-based cryptography at high security levels. Cryptology ePrint Archive: Report 2005/076 (2005)
Laih, C.-S., Yen, S.-M.: Improved digital signature suitable for batch verification. IEEE Trans. Comput. 44(7), 957–959 (1995)
Lee, S., Cho, S., Choi, J., Cho, Y.: Efficient identification of bad signatures in RSA-type batch signature. IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences E89-A(1), 74–80 (2006)
Lim, C., Lee, P.: Security of interactive DSA batch verification. Electronics Letters 30(19), 1592–1593 (1994)
Lim, C.H.: Efficient multi-exponentation and application to batch verification of digital signatures (2000), http://dasan.sejong.ac.kr/~chlim/english_pub.html
Lysyanskaya, A., Rivest, R.L., Sahai, A., Wolf, S.: Pseudonym systems. In: Heys, H.M., Adams, C.M. (eds.) SAC 1999. LNCS, vol. 1758, pp. 184–199. Springer, Heidelberg (2000)
Naccache, D.: Secure and practical identity-based encryption. Cryptology ePrint Archive: Report 2005/369 (2005)
Naccache, D., M’Raïhi, D., Vaudenay, S., Raphaeli, D.: Can D.S.A. be improved? complexity trade-offs with the digital signature standard. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 77–85. Springer, Heidelberg (1995)
Raya, M., Hubaux, J.-P.: Securing vehicular ad hoc networks. Journal of Computer Security 15, 39–68 (2007)
SeVeCom. Security on the road, http://www.sevecom.org
Stanek, M.: Attacking LCCC batch verification of RSA signatures. Cryptology ePrint Archive: Report 2006/111 (2006)
Waters, B.: Efficient identity-based encryption without random oracles. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 114–127. Springer, Heidelberg (2005)
Yoon, H., Cheon, J.H., Kim, Y.-D.: Batch verifications with ID-based signatures. In: Park, C.-s., Chee, S. (eds.) ICISC 2004. LNCS, vol. 3506, pp. 233–248. Springer, Heidelberg (2005)
Zhang, F., Kim, K.: Efficient ID-based blind signature and proxy signature from bilinear pairings. In: Safavi-Naini, R., Seberry, J. (eds.) ACISP 2003. LNCS, vol. 2727, pp. 312–323. Springer, Heidelberg (2003)
Zhang, F., Safavi-Naini, R., Susilo, W.: Efficient verifiably encrypted signature and partially blind signature from bilinear pairings. In: Johansson, T., Maitra, S. (eds.) INDOCRYPT 2003. LNCS, vol. 2904, pp. 191–204. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Camenisch, J., Hohenberger, S., Pedersen, M.Ø. (2007). Batch Verification of Short Signatures. In: Naor, M. (eds) Advances in Cryptology - EUROCRYPT 2007. EUROCRYPT 2007. Lecture Notes in Computer Science, vol 4515. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72540-4_14
Download citation
DOI: https://doi.org/10.1007/978-3-540-72540-4_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72539-8
Online ISBN: 978-3-540-72540-4
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
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.