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

Daniel J. Bernstein, Andreas T. Hülsing

Research output: Other contributionAcademic

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.
Original languageEnglish
Number of pages36
Publication statusPublished - 2019

Fingerprint

Hash functions

Bibliographical note

https://eprint.iacr.org/2019/492

Cite this

@misc{d3a6d8ce46594a03a64e1544460c536a,
title = "Decisional second-preimage resistance: when does SPR imply PRE?",
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.",
author = "Bernstein, {Daniel J.} and H{\"u}lsing, {Andreas T.}",
note = "https://eprint.iacr.org/2019/492",
year = "2019",
language = "English",
type = "Other",

}

Decisional second-preimage resistance : when does SPR imply PRE? / Bernstein, Daniel J.; Hülsing, Andreas T.

36 p. 2019, .

Research output: Other contributionAcademic

TY - GEN

T1 - Decisional second-preimage resistance

T2 - when does SPR imply PRE?

AU - Bernstein, Daniel J.

AU - Hülsing, Andreas T.

N1 - https://eprint.iacr.org/2019/492

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

M3 - Other contribution

ER -