Batch Verification of ECDSA Signatures

详细信息    查看全文

• 作者：Sabyasachi Karati (1) skarati@cse.iitkgp.ernet.in
  Abhijit Das (1) abhij@cse.iitkgp.ernet.in
  Dipanwita Roychowdhury (1) drc@cse.iitkgp.ernet.in
  Bhargav Bellur (2) bhargav_bellur@yahoo.com
  Debojyoti Bhattacharya (2) Debojyoti.bhattacharya@gmail.com
  Aravind Iyer (2) aravind.iyer@gm.com
• 关键词：Digital Signatures – ; Elliptic Curves – ; ECDSA – ; ECDSA* – ; Batch Verification – ; Modular Square Root – ; Symbolic Computation – ; Linearization
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7374
• 期：1
• 页码：1-18
• 全文大小：320.1 KB
• 参考文献：1. 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)
  2. ANSI, Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA), ANSI X9.62, approved January 7 (1999)
  3. 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)
  4. Harn, L.: Batch verifying multiple RSA digital signatures. Electronics Letters 34(12), 1219–1220 (1998)
  5. Hwang, M.-S., Lin, I.-C., Hwang, K.-F.: Cryptanalysis of the Batch Verifying Multiple RSA Digital Signatures. Informatica 11(1), 15–19 (2000)
  6. Johnson, D., Menezes, A.: The Elliptic Curve Digital Signature Algorithm (ECDSA). International Journal on Information Security 1, 36–63 (2001)
  7. 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)
  8. NIST, Digital Signature Standard (DSS) (2006), http://csrc.nist.gov/publications/drafts/fips_186-3/Draft-FIPS-186-3%20_March2006.pdf
  9. NIST, Recommended elliptic curves for federal government use (July 1999), http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf
  10. NIST, Secure Hash Standard (SHS) (2007), http://csrc.nist.gov/publications/drafts/fips_180-3/draft_fips-180-3_June-08-2007.pdf
  11. PARI Group, PARI/GP Development Headquarters (2003-2008), http://pari.math.u-bordeaux.fr/
  12. Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and pubic-key cryptosystem. Communications of the ACM 2, 120–126 (1978)
  13. Shanks, D.: Five number theoretic algorithms. In: Proceedings of the Second Manitoba Conference on Numerical Mathematics, pp. 51–70 (1973)
• 作者单位：1. Department of Computer Science and Engineering, Indian Institute of Technology, Kharagpur, India2. General Motors Technical Centre India, India Science Lab, Bangalore, India
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

In this paper, we study several algorithms for batch verification of ECDSA signatures. The first of these algorithms is based upon the naive idea of taking square roots in the underlying field. We also propose two new and efficient algorithms which replace square-root computations by symbolic manipulations. Experiments carried out on NIST prime curves demonstrate a maximum speedup of above six over individual verification if all the signatures in the batch belong to the same signer, and a maximum speedup of about two if the signatures in the batch belong to different signers, both achieved by a fast variant of our second symbolic-manipulation algorithm. In terms of security, all the studied algorithms are equivalent to standard ECDSA* batch verification. These algorithms are practical only for small (≤ 8) batch sizes. To the best of our knowledge, this is the first reported study on the batch verification of original ECDSA signatures.