Abstract
Multiple-time signatures are digital signature schemes where the signer is able to sign a predetermined number of messages. They are interesting cryptographic primitives because they allow to solve many important cryptographic problems, and at the same time offer substantial efficiency advantage over ordinary digital signature schemes like RSA. Multiple-time signature schemes have found numerous applications, in ordinary, on-line/off-line, forward-secure signatures, and multicast/stream authentication. We propose a multiple-time signature scheme with very efficient signing and verifying. Our construction is based on a combination of one-way functions and cover-free families, and it is secure against the adaptive chosen-message attack.
Chapter PDF
Similar content being viewed by others
References
Abdalla, M., Reyzin, L.: A new forward-secure digital signature scheme. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 116–129. Springer, Heidelberg (2000)
Bos, J.N.E., Chaum, D.: Provably unforgeable signature. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 1–14. Springer, Heidelberg (1993)
Bellare, M., Micali, S.: How to sign given any trapdoor function. Journal of Cryptology 39, 214–233 (1992)
Bellare, M., Miner, S.: A forward-secure digital signature scheme. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 431–448. Springer, Heidelberg (1999)
Ballare, M., Neven, S.G.: Transitive signatures based on factoring and RSA. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 314–397. Springer, Heidelberg (2002)
Bleichenbacher, D., Maurer, U.: Directed acyclic graphs, one-way functions and digital signatures. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 75–82. Springer, Heidelberg (1994)
Bleichenbacher, D., Maurer, U.: On the efficiency of one-time digital signatures. In: Kim, K.-c., Matsumoto, T. (eds.) ASIACRYPT 1996. LNCS, vol. 1163, pp. 145–158. Springer, Heidelberg (1996)
Bleichenbacher, D., Maurer, U.: Optimal tree-based one-time digital signature schemes. In: Puech, C., Reischuk, R. (eds.) STACS 1996. LNCS, vol. 1046, pp. 363–374. Springer, Heidelberg (1996)
Coppersmith, D., Jakobsson, M.: Almost optimal hash sequence traversal. In: Blaze, M. (ed.) FC 2002. LNCS, vol. 2357, Springer, Heidelberg (2003) (to appear)
Dwork, C., Naor, M.: An efficient existentially unforgeable signature scheme and its applications. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 234–246. Springer, Heidelberg (1994)
Erdös, P., Frankl, P., Furedi, Z.: Families of finite sets in which no set is covered by the union of r others. Israel Journal of Mathematics 51, 79–89 (1985)
Even, S., Goldreich, O., Micali, S.: On-line/off-line digital signatures. Journal of Cryptology 9, 35–67 (1996)
Goldwasser, S., Micali, S., Rivest, R.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on Computing 17, 281–308 (1988)
Hevia, A., Micciancio, D.: The provable security of graph-based one-time signatures and extensions to algebraic signature schemes. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 379–396. Springer, Heidelberg (2002)
Hu, Y.-C., Perrig, A., Johnson, D.B.: Packet Leashes: A defense against wormhole attacks in wireless Ad Hoc Networks. In: Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM 2003 (2003)
Jakobsson, M.: Fractal hash sequence representation and traversal. In: Proceedings of the IEEE International Symposium on Information Theory (ISIT 2002), pp. 437–444 (2002)
Kumar, R., Rajagopalan, S., Sahai, A.: Coding constructions for blacklist in problems without computational assumptions. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 609–623. Springer, Heidelberg (1999)
Lamport, L.: Constructing digital signatures from a one way function, Technical Report CSL-98, SRI International (1979)
Lamport, L.: Password authentication with insecure communication. Communication of the ACM 24(11), 770–772 (1981)
Merkle, R.C.: A digital signature based on a conventional function. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 369–378. Springer, Heidelberg (1988)
Merkle, R.C.: A certified digital signature. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 218–238. Springer, Heidelberg (1990)
Niederreiter, H., Xing, C.P.: Rational Points on Curves over Finite Fields: Theory and Applications. Cambridge University Press, Cambridge (2001), LMS 285
Perrig, A.: The BiBa one-time signature and broadcast authentication. In: Eighth ACM Conference on Computer and Communication Security, pp. 28–37. ACM, New York (2001)
Rabin, M.O.: Digitalized signatures, Foundations of Secure Communication, pp. 155–168. Academic Press, London (1978)
Reyzin, L., Reyzin, N.: Better than BiBa: Short one -time signatures with fast signing and verifying. In: Batten, L.M., Seberry, J. (eds.) ACISP 2002. LNCS, vol. 2384, pp. 144–153. Springer, Heidelberg (2002)
Rivest, R., Shamir, A.: PayWord and MicroMint: two simple micro payment schemes, Tech. Rep., MIT Lab. for Computer Science (1996)
Rohatgi, P.: A compact and fast hybrid signature scheme for multicast packet authentication. In: 6th ACM conference on Computer and Communication Security, pp. 93–100 (1999)
Stichtenoth, H.: Algebraic function fields and codes. Springer, Berlin (1993)
Stinson, D.R.: Cryptography: theory and practice. CRC Press, Boca Raton (1995)
Stinson, D.R., Wei, R., Zhu, L.: Some new bounds for cover-free families. Journal of Combinatorial Theory, A 90, 224–234 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pieprzyk, J., Wang, H., Xing, C. (2004). Multiple-Time Signature Schemes against Adaptive Chosen Message Attacks. In: Matsui, M., Zuccherato, R.J. (eds) Selected Areas in Cryptography. SAC 2003. Lecture Notes in Computer Science, vol 3006. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24654-1_7
Download citation
DOI: https://doi.org/10.1007/978-3-540-24654-1_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21370-3
Online ISBN: 978-3-540-24654-1
eBook Packages: Springer Book Archive