We introduce a framework for rigorous comparison of explicit binary pebbling algorithms, including simple speed-1 binary pebbling, Jakobsson's speed-2 binary pebbling, and our optimal binary pebbling algorithm. Explicit schedules describe for each pebble exactly how many hashes need to be performed in each round. The optimal schedule turns out to be essentially unique and exhibits a nice recursive structure, which allows for fully optimized implementations that can readily be deployed. In particular, we develop the first in-place implementations with minimal storage overhead (essentially, storing only hash values), and fast implementations with minimal computational overhead. Moreover, we show that our approach is not limited to hash chains of length $n=2^k$, but accommodates hash chains of arbitrary length $n\geq1$, without incurring any overhead. Finally, we show how to run a cascade of pebbling algorithms along with a bootstrapping technique, facilitating sequential reversal of an unlimited number of hash chains growing in length up to a given bound.
Category / Keywords: public-key cryptography / hash chains, pebbling, in-place algorithms, lightweight cryptography, post-quantum cryptography, hash-based signatures, one-way function Original Publication (in the same form): Financial Crypto 2016 Date: received 11 May 2014, last revised 1 Aug 2016 Contact author: berry at win tue nl Available format(s): PDF | BibTeX Citation Note: Sample code available at http://www.win.tue.nl/~berry/pebbling/ Version: 20160801:112646 (All versions of this report) Short URL: ia.cr/2014/329 Discussion forum: Show discussion | Start new discussion