Advertisement

Batch Verification with DSA-Type Digital Signatures for Ubiquitous Computing

  • Seungwon Lee
  • Seongje Cho
  • Jongmoo Choi
  • Yookun Cho
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3802)

Abstract

We propose a new method for verifying bad signature in a batch instance of DSA-type digital signatures when there is one bad signature in the batch. The proposed method can verify and identify a bad signature using two modular exponentiations and \(n + 3\sqrt{n}/2\) modular multiplications where n is the number of signatures in the batch instance. Simulation results show our method reduces considerably the number of modular multiplications compared with the existing methods.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Pastuszak, J., Michalek, D., Pieprzyk, J., Seberry, J.: Identification of bad signatures in batches. In: Imai, H., Zheng, Y. (eds.) PKC 2000. LNCS, vol. 1751. Springer, Heidelberg (2000)CrossRefGoogle Scholar
  2. 2.
    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)CrossRefGoogle Scholar
  3. 3.
    Berlekamp, E.: Algebraic Coding Theory. McGraw-Hill, New York (1968)zbMATHGoogle Scholar
  4. 4.
    Harn, L.: Batch verifying multiple dsa-type digital signatures. In: Electronics Letters, pp. 870–871 (1998)Google Scholar
  5. 5.
    Bellare, M., Garay, J., 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)CrossRefGoogle Scholar
  6. 6.
    Teske, E.: Computing discrete logarithms with the parallelized kangaroo method. Discrete Applied Mathematics 130, 61–82 (2003)zbMATHCrossRefMathSciNetGoogle Scholar
  7. 7.
    Buchmann, J., Jacobson, M., Teske, E.: On some computational problems in finite abelian groups. Mathematics of Computation 66, 1663–1687 (1997)zbMATHCrossRefMathSciNetGoogle Scholar
  8. 8.
    Bellare, M., Garay, J.A., Rabin, T.: Batch verification with applications to cryptography and checking. In: Lucchesi, C.L., Moura, A.V. (eds.) LATIN 1998. LNCS, vol. 1380, p. 170. Springer, Heidelberg (1998)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Seungwon Lee
    • 1
  • Seongje Cho
    • 2
  • Jongmoo Choi
    • 2
  • Yookun Cho
    • 1
  1. 1.School of Computer Science and EngineeringSeoul National UniversitySeoulKorea
  2. 2.Division of Information and Computer ScienceDankook UniversitySeoulKorea

Personalised recommendations