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
EventThird International Conference on Applied Cryptography and Network Security, ACNS 2005 - New York, NY, United States
Duration: Jun 7 2005Jun 10 2005

Fingerprint

Hash Chain
Network protocols
Sensor networks
Data storage equipment
Electronic document identification systems
Network security
Security Protocols
Mobile devices
Sandwich
Fractals
Authentication
Lower bound
Costs
Sensor Networks
Bandwidth
Verify
Sensors
One-way Function
Setup Cost
Resources

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Efficient constructions for one-way hash chains. / Hu, Yih Chun; Jakobsson, Markus; Perrig, Adrian.

In: Lecture Notes in Computer Science, Vol. 3531, 17.10.2005, p. 423-441.

Research output: Contribution to journalConference article

Hu, YC, Jakobsson, M & Perrig, A 2005, 'Efficient constructions for one-way hash chains', Lecture Notes in Computer Science, vol. 3531, pp. 423-441.
Hu, Yih Chun ; Jakobsson, Markus ; Perrig, Adrian. / Efficient constructions for one-way hash chains. In: Lecture Notes in Computer Science. 2005 ; Vol. 3531. pp. 423-441.
@article{7644bbebd1e14aff85c45bd7b7b738ca,
title = "Efficient constructions for one-way hash chains",
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.",
keywords = "Broadcast authentication, Efficient constructions, One-way hash chains",
author = "Hu, {Yih Chun} and Markus Jakobsson and Adrian Perrig",
year = "2005",
month = "10",
day = "17",
language = "English (US)",
volume = "3531",
pages = "423--441",
journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
issn = "0302-9743",
publisher = "Springer Verlag",

}

TY - JOUR

T1 - Efficient constructions for one-way hash chains

AU - Hu, Yih Chun

AU - Jakobsson, Markus

AU - Perrig, Adrian

PY - 2005/10/17

Y1 - 2005/10/17

N2 - 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.

AB - 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.

KW - Broadcast authentication

KW - Efficient constructions

KW - One-way hash chains

UR - http://www.scopus.com/inward/record.url?scp=26444506296&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=26444506296&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:26444506296

VL - 3531

SP - 423

EP - 441

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SN - 0302-9743

ER -