Efficient constructions for one-way hash chains

Yih Chun Hu, Markus Jakobsson, Adrian Perrig

Research output: Contribution to journalConference article

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 over-head 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 log 2(n) for the product of pervalue 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.

Original languageEnglish (US)
Pages (from-to)423-441
Number of pages19
JournalLecture Notes in Computer Science
Volume3531
StatePublished - Oct 17 2005
Externally publishedYes
EventThird International Conference on Applied Cryptography and Network Security, ACNS 2005 - New York, NY, United States
Duration: Jun 7 2005Jun 10 2005

    Fingerprint

Keywords

  • Broadcast authentication
  • Efficient constructions
  • One-way hash chains

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this