Abstract
Batch verification is a method for verifying digital signatures at once. Batch verification can reduce the computational cost compared to that of verifying each signature one by one, and in particular, batch verification is especially appropriate for systems which are required to verify a large amount of signatures. However, in addition to the above requirement, several types of systems might also require verifying a limited number of digital signatures more and more efficiently in real-time. For this purpose, to improve the efficiency of verifying a limited number of signatures is presumably an important matter. This paper deals with the second requirement and proposes an efficient batch verification technique suitable for verifying a limited number of signatures in real-time. Our method can only be applied to elliptic curve based signatures, and uses one of the two special families of elliptic curves.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Antipa, A., Brown, D., Gallant, R., Lambert, R., Struik, R., Vanstone, S.: Accelerated Verification of ECDSA Signatures. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 307–318. Springer, Heidelberg (2006)
Brickell, E.F., Gordon, D.M., McCurley, K.S., Wilson, D.B.: Fast Exponentiation with Precomputation. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 200–207. Springer, Heidelberg (1993)
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), http://www-cse.ucsd.edu/users/mihir
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)
Camenisch, J., Hohenberger, S., Pedersen, M.Ø.: Batch Verification of Short Signatures. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 246–263. Springer, Heidelberg (2007)
Cheon, J.H., Lee, D.H.: Use of Sparse and/or Complex Exponents in Batch Verification of Exponentiations. IEEE Transactions on Computers 55(12), 1536–1542 (2006)
Coron, J.-S., Naccache, D.: On the Security of RSA Screening. In: Imai, H., Zheng, Y. (eds.) PKC 1999. LNCS, vol. 1560, pp. 197–203. Springer, Heidelberg (1999)
Cheon, J.H., Yi, J.H.: Fast Batch Verification of Multiple Signatures. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 442–457. Springer, Heidelberg (2007)
Guo, F., Mu, Y., Chen, Z.: Efficient Batch Verification of Short Signatures for a Single-Signer Setting without Random Oracles. In: Matsuura, K., Fujisaki, E. (eds.) IWSEC 2008. LNCS, vol. 5312, pp. 49–63. Springer, Heidelberg (2008)
Gallant, R.P., Lambert, R.J., Vanstone, S.A.: Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 190–200. Springer, Heidelberg (2001)
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)
Hankerson, D., Menezes, A., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer, New York (2004)
Harrison, K., Page, D., Smart, N.P.: Software Implementation of Finite Fields of Characteristic Three, for Use in Pairing-based Cryptosystems. LMS Journal of Computation and Mathematics 5(1), 181–193 (2002)
Hwang, M.S., Lee, C.C., Lu, E.J.: Cryptanalysis of the Batch Verifying Multiple DSA-Type Digital Signatures. Pakistan Journal of Applied Sciences 1(3), 287–288 (2001)
Hakuta, K., Katoh, Y., Sato, H., Takagi, T.: Batch Verification Suitable for Efficiently Verifying A Limited Number of Signatures. In: Preproceedings of the 15th Annual International Conference on Information Security and Cryptology, ICISC 2012 (2012)
Hakuta, K., Sato, H., Takagi, T.: Efficient arithmetic on subfield elliptic curves over small finite fields of odd characteristic. J. Math. Cryptol. 4(3), 199–238 (2010)
Hakuta, K., Sato, H., Takagi, T.: Explicit lower bound for the length of minimal weight τ-adic expansions on Koblitz curves. J. Math-for-Ind. 2A, 75–83 (2010)
Koblitz, N.: An Elliptic Curve Implementation of the Finite Field Digital Signature Algorithm. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 327–337. Springer, Heidelberg (1998)
National Institute for Standards and Technology, Digital Signature Standard (DSS), Federal Information Processing Standards Publication 186-3 (June 2009), http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
Lee, S., Cho, S., Choi, J., Cho, J.: Efficient Identification of Bad Signatures in RSA-Type Batch Signatures. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E89-A(1), 74–80 (2006)
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)
Pastuszak, J., Michałek, D., Pieprzyk, J., Seberry, J.: Identification of Bad Signatures in Batches. In: Imai, H., Zheng, Y. (eds.) PKC 2000. LNCS, vol. 1751, pp. 28–45. Springer, Heidelberg (2000)
Park, T.-J., Lee, M.-K., Park, K.: New Frobenius Expansions for Elliptic Curves with Efficient Endomorphisms. In: Lee, P.J., Lim, C.H. (eds.) ICISC 2002. LNCS, vol. 2587, pp. 264–282. Springer, Heidelberg (2003)
Silverman, J.H.: The Arithmetic of Elliptic Curves. GTM, vol. 106. Springer (1986)
Smart, N.P.: Elliptic Curve Cryptosystems over Small Fields of Odd Characteristic. Journal of Cryptology 12(2), 141–151 (1999)
Schnorr, C.P.: Efficient signature generation by smart cards. Journal of Cryptology 4(3), 161–174 (1991)
Solinas, J.A.: Efficient Arithmetic on Koblitz Curves. Des. Codes Cryptogr. 19(2-3), 195–249 (2000)
Stanek, M.: Attacking LCCC Batch Verification of RSA Signatures. International Journal of Network Security 6(2), 238–240 (2008)
Kumar, V., Madria, S.: Secure Data Aggregation in Wireless Sensor Networks. In: Hara, T., Zadorozhny, V.I., Buchmann, E. (eds.) Wireless Sensor Network Technologies for the Information Explosion Era. SCI, vol. 278, pp. 77–107. Springer, Heidelberg (2010)
Yen, S.M., Laih, C.S.: Improved Digital Signature Suitable for Batch Verification. IEEE Transactions on Computers 44(7), 957–959 (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hakuta, K., Katoh, Y., Sato, H., Takagi, T. (2013). Batch Verification Suitable for Efficiently Verifying a Limited Number of Signatures. In: Kwon, T., Lee, MK., Kwon, D. (eds) Information Security and Cryptology – ICISC 2012. ICISC 2012. Lecture Notes in Computer Science, vol 7839. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-37682-5_30
Download citation
DOI: https://doi.org/10.1007/978-3-642-37682-5_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-37681-8
Online ISBN: 978-3-642-37682-5
eBook Packages: Computer ScienceComputer Science (R0)