Abstract
We discuss various issues associated with signature schemes based solely upon hash functions. Such schemes are currently attractive in some limited applications, but their importance may increase if ever a practical quantum computer was built. We discuss issues related to both their implementation and their security. As far as we are aware this is the first complete treatment of practical implementations of hash based signature schemes in the literature.
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
ANSI X9.63. Public Key Cryptography for the Financial Services Industry: Key Agreement and Key Transport Using Elliptic Curve Cryptography (October 1999), Working Draft
Brassard, G., Høyer, P., Tapp, A.: Quantum cryptanalysis of hash and claw-free functions. In: Lucchesi, C.L., Moura, A.V. (eds.) LATIN 1998. LNCS, vol. 1380, pp. 163–169. Springer, Heidelberg (1998)
Bleichenbacher, D., Maurer, U.M.: 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.: 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)
Bleichenbacher, D., Maurer, U.: On the efficiency of one-time digital signature schemes. In: Kim, K.-c., Matsumoto, T. (eds.) ASIACRYPT 1996. LNCS, vol. 1163, pp. 145–158. Springer, Heidelberg (1996)
Buchmann, J., Coronado, C., Döring, M., Engelbert, D., Ludwig, C., Overbeck, R., Schmidt, A., Vollmer, U., Weinmann, R.-P.: Post-quantum signatures (2004) (Preprint)
Even, S., Goldreich, O., Micali, S.: On-line/off-line digital signatures. Journal of Cryptology 9(1), 35–67 (1996)
Håstad, J., Näslund, M.: Practical construction and analysis of pseudo-randomness primitives. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 442–459. Springer, Heidelberg (2001)
Hauser, R., Steiner, M., Waidner, M.: Micro-payments based on iKP. Technical report, IBM Research (1996)
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)
Lamport, L.: Constructing digital signatures from a one-way function. SRI International, CSL-98 (1979)
Levin, L.A.: One-way functions and pseudorandom generators. Combinatorica 7(4), 357–363 (1987)
Lipton, R.J., Ostrovsky, R.: Micro-payments via efficient coin-flipping. In: Hirschfeld, R. (ed.) FC 1998. LNCS, vol. 1465, pp. 1–15. Springer, Heidelberg (1998)
Lomas, M. (ed.): Security Protocols 1996. LNCS, vol. 1189. Springer, Heidelberg (1996)
Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: CRC-Handbook of Applied Cryptography. CRC Press, Boca Raton (1996)
Merkle, R.: A certified digital signature. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 218–238. Springer, Heidelberg (1990)
Mitzenmacher, M., Perrig, A.: Bounds and improvements for BiBa singature schemes. Technical report, Harvard University, Cambridge, Massachusetts (2002)
Pedersen, T.P.: Electronic payments of small amount. In: Lomas [14], pp. 59–68.
Perrig, A.: The BiBa one-time signature and broadcast authentication protocol. In: Reiter, M., Samarati, P. (eds.) CCS 2001, pp. 28–37. ACM Press, New York (2001)
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.L., Shamir, A.: PayWord and MicroMint: Two simple micropayment schemes. In: Lomas [14], pp. 69–78.
Simon, D.R.: Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 334–345. Springer, Heidelberg (1998)
Szydlo, M.: Merkle tree traversal in log space and time. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 541–554. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dods, C., Smart, N.P., Stam, M. (2005). Hash Based Digital Signature Schemes. In: Smart, N.P. (eds) Cryptography and Coding. Cryptography and Coding 2005. Lecture Notes in Computer Science, vol 3796. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11586821_8
Download citation
DOI: https://doi.org/10.1007/11586821_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30276-6
Online ISBN: 978-3-540-32418-8
eBook Packages: Computer ScienceComputer Science (R0)