Efficient Constructions for One-way Hash Chains
CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE
Pagination or Media Count:
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 cite a lower bound of log2n 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 Ologn memory and O1 traversal overhead, thereby improving on the one-dimensional bound. In addition, the setup cost for the one-way chain is in contrast only Onlogn. 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.
- Computer Systems Management and Standards