Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Batch Verification of Short Signatures

  • Conference paper

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 formany 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 thesame 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.

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

  1. 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)

    Chapter  Google Scholar 

  2. 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)

    Chapter  Google Scholar 

  3. 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)

    Chapter  Google Scholar 

  4. Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. J. Cryptology 17(4), 297–319 (2004)

    Article MATH MathSciNet  Google Scholar 

  5. 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)

    Chapter  Google Scholar 

  6. 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)

    Chapter  Google Scholar 

  7. 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)

    Chapter  Google Scholar 

  8. 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)

    Google Scholar 

  9. 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)

    Chapter  Google Scholar 

  10. 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)

    Google Scholar 

  11. Car 2 Car. Communication consortium,http://car-to-car.org

  12. 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)

    Google Scholar 

  13. 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)

    Chapter  Google Scholar 

  14. Chen, L., Cheng, Z., Smart, N.: Identity-based key agreement protocols from pairings. Cryptology ePrint Archive: Report 2006/199 (2006)

    Google Scholar 

  15. Cheon, J.H., Kim, Y., Yoon, H.J.: A new ID-based signature with batch verification. Cryptology ePrint Archive: Report 2004/131 (2004)

    Google Scholar 

  16. Cui, S., Duan, P., Chan, C.W.: An efficient identity-based signature scheme with batch verifications. In: InfoScale ’06, p. 22 (2006)

    Google Scholar 

  17. Fiat, A.: Batch RSA. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 175–185. Springer, Heidelberg (1990)

    Google Scholar 

  18. Galbraith, S.D., Paterson, K.G., Smart, N.P.: Pairings for cryptographers. Cryptology ePrint Archive: Report 2006/165 (2006)

    Google Scholar 

  19. 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)

    Chapter  Google Scholar 

  20. Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Computing 17(2) (1988)

    Google Scholar 

  21. Granger, R., Smart, N.: On computing products of pairings. Cryptology ePrint Archive: Report 2006/172 (2006)

    Google Scholar 

  22. Harn, L.: Batch verifying multiple DSA digital signatures. Electronics Letters 34(9), 870–871 (1998)

    Article  Google Scholar 

  23. Harn, L.: Batch verifying multiple RSA digital signatures. Electronics Letters 34(12), 1219–1220 (1998)

    Article  Google Scholar 

  24. 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)

    Chapter  Google Scholar 

  25. 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)

    Google Scholar 

  26. 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)

    MATH MathSciNet  Google Scholar 

  27. IEEE. 5.9 GHz Dedicated Short Range Communications,http://grouper.ieee.org/groups/scc32/dsrc

  28. Koblitz, N., Menezes, A.: Pairing-based cryptography at high security levels. Cryptology ePrint Archive: Report 2005/076 (2005)

    Google Scholar 

  29. Laih, C.-S., Yen, S.-M.: Improved digital signature suitable for batch verification. IEEE Trans. Comput. 44(7), 957–959 (1995)

    Article MATH  Google Scholar 

  30. 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)

    Article  Google Scholar 

  31. Lim, C., Lee, P.: Security of interactive DSA batch verification. Electronics Letters 30(19), 1592–1593 (1994)

    Article  Google Scholar 

  32. Lim, C.H.: Efficient multi-exponentation and application to batch verification of digital signatures (2000),http://dasan.sejong.ac.kr/~chlim/english_pub.html

  33. 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)

    Chapter  Google Scholar 

  34. Naccache, D.: Secure and practical identity-based encryption. Cryptology ePrint Archive: Report 2005/369 (2005)

    Google Scholar 

  35. 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)

    Chapter  Google Scholar 

  36. Raya, M., Hubaux, J.-P.: Securing vehicular ad hoc networks. Journal of Computer Security 15, 39–68 (2007)

    Google Scholar 

  37. SeVeCom. Security on the road,http://www.sevecom.org

  38. Stanek, M.: Attacking LCCC batch verification of RSA signatures. Cryptology ePrint Archive: Report 2006/111 (2006)

    Google Scholar 

  39. 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)

    Chapter  Google Scholar 

  40. 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)

    Chapter  Google Scholar 

  41. 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)

    Chapter  Google Scholar 

  42. 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)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. IBM Research, Zürich Research Laboratory, Switzerland

    Jan Camenisch

  2. The Johns Hopkins University,  

    Susan Hohenberger

  3. University of Aarhus,  

    Michael Østergaard Pedersen

Authors
  1. Jan Camenisch
  2. Susan Hohenberger
  3. Michael Østergaard Pedersen

Editor information

Editors and Affiliations

  1. Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel

    Moni Naor

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

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp