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

Daniel J. Bernstein, Andreas Hülsing

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

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
Title of host publicationAdvances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
EditorsSteven D. Galbraith, Shiho Moriai
Place of PublicationBerlin
PublisherSpringer
Chapter2
Pages33-62
Number of pages30
ISBN (Electronic)978-3-030-34618-8
ISBN (Print)978-3-030-34617-1
DOIs
Publication statusPublished - 22 Nov 2019
Event25th Annual International Conference on Theory and Application of Cryptology and Information Security, (ASIACRYPT 2019) - Kobe, Japan
Duration: 8 Dec 201912 Dec 2019

Publication series

NameLecture notes in computer science
Volume11923
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th Annual International Conference on Theory and Application of Cryptology and Information Security, (ASIACRYPT 2019)
CountryJapan
CityKobe
Period8/12/1912/12/19

Fingerprint

Hash functions

Keywords

  • Cryptographic hash functions
  • Hash-based signatures
  • Multi-target attacks
  • Preimage resistance
  • Provable security
  • Second-preimage resistance
  • Tight reductions

Cite this

Bernstein, D. J., & Hülsing, A. (2019). Decisional second-preimage resistance: when does SPR imply PRE? In S. D. Galbraith, & S. Moriai (Eds.), Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings (pp. 33-62). (Lecture notes in computer science; Vol. 11923). Berlin: Springer. https://doi.org/10.1007/978-3-030-34618-8_2
Bernstein, Daniel J. ; Hülsing, Andreas. / Decisional second-preimage resistance: when does SPR imply PRE?. Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. editor / Steven D. Galbraith ; Shiho Moriai. Berlin : Springer, 2019. pp. 33-62 (Lecture notes in computer science).
@inproceedings{ccf061cadf694cfda6d64e15c7be3cd0,
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.",
keywords = "Cryptographic hash functions, Hash-based signatures, Multi-target attacks, Preimage resistance, Provable security, Second-preimage resistance, Tight reductions",
author = "Bernstein, {Daniel J.} and Andreas H{\"u}lsing",
year = "2019",
month = "11",
day = "22",
doi = "10.1007/978-3-030-34618-8_2",
language = "English",
isbn = "978-3-030-34617-1",
series = "Lecture notes in computer science",
publisher = "Springer",
pages = "33--62",
editor = "Galbraith, {Steven D.} and Shiho Moriai",
booktitle = "Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings",
address = "Germany",

}

Bernstein, DJ & Hülsing, A 2019, Decisional second-preimage resistance: when does SPR imply PRE? in SD Galbraith & S Moriai (eds), Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Lecture notes in computer science, vol. 11923, Springer, Berlin, pp. 33-62, 25th Annual International Conference on Theory and Application of Cryptology and Information Security, (ASIACRYPT 2019), Kobe, Japan, 8/12/19. https://doi.org/10.1007/978-3-030-34618-8_2

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

Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. ed. / Steven D. Galbraith; Shiho Moriai. Berlin : Springer, 2019. p. 33-62 (Lecture notes in computer science; Vol. 11923).

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

TY - GEN

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

AU - Bernstein, Daniel J.

AU - Hülsing, Andreas

PY - 2019/11/22

Y1 - 2019/11/22

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.

KW - Cryptographic hash functions

KW - Hash-based signatures

KW - Multi-target attacks

KW - Preimage resistance

KW - Provable security

KW - Second-preimage resistance

KW - Tight reductions

UR - http://www.scopus.com/inward/record.url?scp=85077002538&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-34618-8_2

DO - 10.1007/978-3-030-34618-8_2

M3 - Conference contribution

SN - 978-3-030-34617-1

T3 - Lecture notes in computer science

SP - 33

EP - 62

BT - Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings

A2 - Galbraith, Steven D.

A2 - Moriai, Shiho

PB - Springer

CY - Berlin

ER -

Bernstein DJ, Hülsing A. Decisional second-preimage resistance: when does SPR imply PRE? In Galbraith SD, Moriai S, editors, Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Berlin: Springer. 2019. p. 33-62. (Lecture notes in computer science). https://doi.org/10.1007/978-3-030-34618-8_2