Binary Pebbling Algorithms for In-Place Reversal of One-Way Hash Chains
This addresses storage and computational efficiency for cryptographic applications like authentication and digital signatures, representing an incremental improvement over existing binary pebbling methods.
The paper tackles the problem of in-place reversal of one-way hash chains by presenting optimal binary pebbling algorithms, achieving at most ⌈k/2⌉ hashes per output round and at most k stored hash values for a chain of length 2^k.
We present optimal binary pebbling algorithms for in-place reversal (backward traversal) of one-way hash chains. For a hash chain of length $2^k$, the number of hashes performed in each output round does not exceed $\lceil k/2 \rceil$, whereas the number of hash values stored (pebbles) throughout is at most $k$. 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.