Cryptology ePrint Archive: Report 2019/492

Decisional second-preimage resistance: When does SPR imply PRE?

Daniel J. Bernstein and Andreas Hülsing

Abstract: There is a well-known gap between second-preimage resistance and preimage resistance for length-preserving hash functions. This paper introduces a simple concept that fills this gap. One consequence of this concept is that tight reductions can remove interactivity for multi-target length-preserving preimage problems, such as the problems that appear in analyzing hash-based signature systems. Previous reduction techniques applied to only a negligible fraction of all length-preserving hash functions, presumably excluding all off-the-shelf hash functions.

Category / Keywords: foundations / cryptographic hash functions, preimage resistance, second-preimage resistance, provable security, tight reductions, multi-target attacks, hash-based signatures

Original Publication (with minor differences): IACR-ASIACRYPT-2019

Date: received 13 May 2019, last revised 23 Sep 2019

Contact author: authorcontact-dspr at box cr yp to

Available format(s): PDF | BibTeX Citation

Version: 20190923:182351 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]