Abstract
One-way chains are an important cryptographic primitive in many security applications. As one-way chains are very efficient to verify, they recently became increasingly popular for designing security protocols for resource-constrained mobile devices and sensor networks, as their low-powered processors can compute a one-way function within milliseconds, but would require tens of seconds or up to minutes to generate or verify a traditional digital signature [6]. Recent sensor network security protocols thus extensively use one-way chains to design protocols that scale down to resource-constrained sensors [21,29]. Recently, researchers also proposed a variety of improvements to one-way hash chains to make storage and access more efficient [9,18,33], or to make setup and verification more efficient [17,21].
In this paper we present two new constructions for one-way hash chains, which significantly improve the efficiency of one-way chains. Our first construction, the Sandwich-chain, provides a smaller bandwidth overhead for one-way chain values, and enables efficient verification of one-way chain values if the trusted one-way chain value is far away. Our second construction, Comb Skipchain, features a new lower bound for one-way chains in terms of storage and traversal overhead. In fact previously, researchers [9] cite a lower bound of log2(n) for the product of per-value traversal overhead and memory requirements for one-dimensional chains. We show that one can achieve a lower bound by considering multi-dimensional chains. In particular, our two-dimensional construction requires O(log(n)) memory and O(1) traversal overhead, thereby improving on the one-dimensional bound. In addition, the setup cost for the one-way chain is in contrast only O(n/log(n)). Other benefits for both constructions include a faster verification step than the traditional hash chains provide; a verifier can “catch up” efficiently, after having missed some number of previously released hash values (for the Sandwich-chain); and resistance against DoS attacks on authentication values. Moreover, we describe fractal traversal schemes for our proposed structures, bringing down the traversal costs for our structure to the same as those of the simpler “traditional” hash chain.
Our new construction is orthogonal to most previously proposed techniques, and can be used in conjunction with techniques for efficient setup or verification of one-way chains.
Chapter PDF
Similar content being viewed by others
References
Aiello, W., Lodha, S., Ostrovsky, R.: Fast digital identity revocation. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, p. 137. Springer, Heidelberg (1998)
Anderson, R., Manifavas, H., Sutherland, C.: A practical electronic cash system. personal communication (December 1995)
Bellare, M., Kilian, J., Rogaway, P.: The security of cipher block chaining. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 341–358. Springer, Heidelberg (1994)
Bellare, M., Canetti, R., Krawczyk, H.: Keying hash functions for message authentication. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 1–15. Springer, Heidelberg (1996)
Brassard, G. (ed.): CRYPTO 1989. LNCS, vol. 435. Springer, Heidelberg (1990)
Brown, M., Cheung, D., Hankerson, D., Hernandez, J., Kirkup, M., Menezes, A.: PGP in constrained wireless devices. In: Proceedings of the 9th USENIX Security Symposium, USENIX, August 2000, pp. 247–261 (2000)
Cable Datacom News. Time warner division implements consumption caps, Published at http://www.cabledatacomnews.com/may03/may03-7.html
Cheung, S.: An efficient message authentication scheme for link state routing. In: 13th Annual Computer Security Applications Conference, pp. 90–98 (1997)
Coppersmith, D., Jakobsson, M.: Almost optimal hash sequence traversal. In: Proceedings of the Fourth Conference on Financial Cryptography (FC 2002). LNCS, Springer, Heidelberg (2002)
Even, S., Goldreich, O., Micali, S.: On-line/off-line digital signatures. In: Brassard [5], pp. 263–277
Fischlin, M.: Fast verification of hash chains. In: Okamoto, T. (ed.) CT-RSA 2004. LNCS, vol. 2964, pp. 339–352. Springer, Heidelberg (2004)
Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. Journal of the ACM 33(4), 792–807 (1986)
Haller, N.: The S/KEY one-time password system. RFC 1760, February 1995.
Hauser, R., Przygienda, A., Tsudik, G.: Reducing the cost of security in link state routing. In: Proceedings of the Symposium on Network and Distributed Systems Security (NDSS 1997), San Diego, California, February 1997, pp. 93–99. Internet Society (1997)
Hauser, R., Steiner, M., Waidner, M.: Micro-payments based on iKP. In: 14th Worldwide Congress on Computer and Communications Security Protection, June 1996, pp. 67–82. C.N.I.T Paris-La Defense, France (1996)
Hellman, M.: A cryptanalytic time-memory trade-off. IEEE Transactions on Information Theory 26(4), 401–406 (1980)
Hu, Y.-C., Perrig, A., Johnson, D.B.: Efficient security mechanisms for routing protocols. In: Network and Distributed System Security Symposium, NDSS 2003, February 2003, pp. 57–73 (2003)
Jakobsson, M.: Fractal hash sequence representation and traversal. In: Proceedings of the 2002 IEEE International Symposium on Information Theory (ISIT 2002), July 2002, pp. 437–444 (2002)
Kahn, J.M., Katz, R.H., Pister, K.S.: Mobile networking for smart dust. In: ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 1999), Seattle, WA (August 1999)
Lamport, L.: Password authentication with insecure communication. Communications of the ACM 24(11), 770–772 (1981)
Liu, D., Ning, P.: Efficient distribution of key cahin commitments for broadcast authentication in distributed sensor networks. In: Network and Distributed System Security Symposium, NDSS 2003, February 2003, pp. 263–276 (2003)
Lomas, M. (ed.): Security Protocols 1996. LNCS, vol. 1189. Springer, Heidelberg (1997)
Merkle, R.C.: A digital signature based on a conventional encryption 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 [5], pp. 218–238
Micali, S.: Efficient certificate revocation. Technical Report MIT/LCS/TM- 542b, Massachusetts Institute of Technology, Laboratory for Computer Science (March 1996), Technical memo
National Institute of Standards and Technology (NIST). Secure hash standard (May 1993), Federal Information Processing Standards (FIPS) Publication 180-1
Pedersen, T.P.: Electronic payments of small amounts. In: Lomas [22], pp. 59–68
Perrig, A., Canetti, R., Tygar, J.D., Song, D.X.: Efficient authentication and signing of multicast streams over lossy channels. In: IEEE Symposium on Security and Privacy (May 2000)
Perrig, A., Szewczyk, R., Wen, V., Culler, D., Tygar, J.D.: SPINS: Security protocols for sensor networks. Wireless Networks 8(5), 521–534 (2002)
Rivest, R.L.: The MD5 message-digest algorithm. Internet Request for Comment RFC 1321, Internet Engineering Task Force (April 1992)
Rivest, R.L., Shamir, A.: PayWord and MicroMint: Two simple micropayment schemes. In: Lomas [22], pp. 69 – 88
Rohatgi, P.: A compact and fast hybrid signature scheme for multicast packet. In: Tsudik, G. (ed.) Proceedings of the 6th ACM Conference on Computer and Communications Security, Singapore, November 1999, pp. 93–100. ACM Press, New York (1999)
Sella, Y.: On the computation-storage trade-offs of hash chain traversal. In: Wright, R.N. (ed.) FC 2003. LNCS, vol. 2742, pp. 270–285. Springer, Heidelberg (2003)
Zhang, K.: Efficient protocols for signing routing messages. In: Proceedings of the Symposium on Network and Distributed Systems Security (NDSS 1998), San Diego, California, March 1998, Internet Society (1998)
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
Hu, YC., Jakobsson, M., Perrig, A. (2005). Efficient Constructions for One-Way Hash Chains. In: Ioannidis, J., Keromytis, A., Yung, M. (eds) Applied Cryptography and Network Security. ACNS 2005. Lecture Notes in Computer Science, vol 3531. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11496137_29
Download citation
DOI: https://doi.org/10.1007/11496137_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26223-7
Online ISBN: 978-3-540-31542-1
eBook Packages: Computer ScienceComputer Science (R0)