Cryptology ePrint Archive: Report 2014/329

Explicit Optimal Binary Pebbling for One-Way Hash Chain Reversal

Berry Schoenmakers

Abstract: We present explicit optimal binary pebbling algorithms for reversing one-way hash chains. For a hash chain of length $2^k$, the number of hashes performed per output round is at most $\lceil \tfrac{k}{2}\rceil$, whereas the number of hash values stored throughout is at most $k$. This is optimal for binary pebbling algorithms characterized by the property that the midpoint of the hash chain is computed just once and stored until it is output, and that this property applies recursively to both halves of the hash chain.

We develop a framework for easy comparison of explicit binary pebbling algorithms, including simple speed-1 binary pebbles, Jakobsson's binary speed-2 pebbles, and our optimal binary pebbles. Explicit schedules describe for each pebble exactly how many hashes need to be performed in each round. The optimal schedule exhibits a nice recursive structure, which allows fully optimized implementations that can readily be deployed. In particular, we develop in-place implementations with minimal storage overhead (essentially, storing only hash values), and fast implementations with minimal computational overhead.

Category / Keywords: public-key cryptography / hash chains, pebbling, in-place algorithms, lightweight cryptography, post-quantum cryptography, one-way function

Date: received 11 May 2014, last revised 23 May 2014

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: 20140523:133804 (All versions of this report)

Short URL: ia.cr/2014/329

Discussion forum: Show discussion | Start new discussion