Paper 2022/1213

Nostradamus goes Quantum

Barbara Jiabao Benedikt, TU Darmstadt
Marc Fischlin, TU Darmstadt
Moritz Huppert, TU Darmstadt
Abstract

In the Nostradamus attack, introduced by Kelsey and Kohno (Eurocrypt 2006), the adversary has to commit to a hash value y of an iterated hash function H such that, when later given a message prefix P, the adversary is able to find a suitable "suffix explanation" S with H(P||S)=y. Kelsey and Kohno show a herding attack with $2^{2n/3}$ evaluations of the compression function of H (with n bits output and state), locating the attack between preimage attacks and collision search in terms of complexity. Here we investigate the security of Nostradamus attacks for quantum adversaries. We present a quantum herding algorithm for the Nostradamus problem making approximately $\sqrt[3]{n}\cdot 2^{3n/7}$ compression function evaluations, significantly improving over the classical bound. We also prove that quantum herding attacks cannot do better than $2^{3n/7}$ evaluations for random compression functions, showing that our algorithm is (essentially) optimal. We also discuss a slightly less tight bound of roughly $2^{3n/7-s}$ for general Nostradamus attacks against random compression functions, where s is the maximal block length of the adversarially chosen suffix S.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
A minor revision of an IACR publication in ASIACRYPT 2022
Keywords
Hash function herding attack lower bound Nostradamus quantum Grover
Contact author(s)
barbara_jiabao benedikt @ tu-darmstadt de
marc fischlin @ tu-darmstadt de
moritz huppert @ proton me
History
2022-09-14: approved
2022-09-13: received
See all versions
Short URL
https://ia.cr/2022/1213
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1213,
      author = {Barbara Jiabao Benedikt and Marc Fischlin and Moritz Huppert},
      title = {Nostradamus goes Quantum},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1213},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1213}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.