Explicit optimal binary pebbling for one-way hash chain reversal

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)

Abstract

We present explicit optimal binary pebbling algorithms for reversing one-way hash chains. For a hash chain of length 2k, the number of hashes performed in each output round does not exceed ⌈k/2⌉, whereas the number of hash values stored (pebbles) 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 introduce a framework for rigorous comparison of explicit binary pebbling algorithms, including simple speed-1 binary pebbling, Jakob-sson’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 =2k, but accommodates hash chains of arbitrary length n ≥ 1, 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.

Original languageEnglish
Title of host publicationFinancial Cryptography and Data Security - 20th International Conference, FC 2016, Revised Selected Papers
EditorsBart Preneel, Jens Grossklags
PublisherSpringer
Pages299-320
Number of pages22
ISBN (Print)9783662549698
DOIs
Publication statusPublished - 2017
Event20th International Conference on Financial Cryptography and Data Security, FC 2016 - Christ Church, Barbados
Duration: 22 Feb 201626 Feb 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9603 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th International Conference on Financial Cryptography and Data Security, FC 2016
Country/TerritoryBarbados
CityChrist Church
Period22/02/1626/02/16

Bibliographical note

Publisher Copyright:
© International Financial Cryptography Association 2017.

Fingerprint

Dive into the research topics of 'Explicit optimal binary pebbling for one-way hash chain reversal'. Together they form a unique fingerprint.

Cite this