Public reporting burden for the collection of information is estimated to average 1 hour per response, including the time for reviewing instructions, searching existing data sources, gathering and maintaining the data needed, and completing and reviewing the collection of information. Send comments regarding this burden estimate or any other aspect of this collection of information, including suggestions for reducing this burden, to Washington Headquarters Services, Directorate for Information Operations and Reports, 1215 Jefferson Davis Highway, Suite 1204, Arlington VA 22202-4302. Respondents should be aware that notwithstanding any other provision of law, no person shall be subject to a penalty for failing to comply with a collection of information if it does not display a currently valid OMB control number. Keywords: One-way hash chains, efficient constructions, broadcast authentication. One-way chains are an important cryptographic primitive in many security applications. Lamport first proposed to use one-way chains for one-time password authentication [19] . Subsequently, researchers proposed one-way chains as a basic building block for digital cash, for extending the lifetime of digital certificates, for constructing one-time signatures, for packet authentication, etc. 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 [20, 28] . Recently, researchers also proposed a variety of improvements to one-way hash chains to make storage and access more efficient [9, 17, 32] , or to make setup and verification more efficient [16, 20] . 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 log 2 (n) for the product of per-value traversal overhead and memory requirements for onedimensional 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.
In particular, Hu et al. REF provide two different constructions of one-way hash chains, the Sandwich chain and the Comb Skipchain, which enable faster verification.
Efficient Constructions for One-way Hash Chains