| Author | Benedikt, Barbara Jiabao; Fischlin, Marc; Huppert, Moritz |
|---|
| Date | 2022 |
|---|
| Type | Conference Proceedings |
|---|
| 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 22n/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 n−−√3⋅23n/7 compression function evaluations, significantly improving over the classical bound. We also prove that quantum herding attacks cannot do better than 23n/7 evaluations for random compression functions, showing that our algorithm is (essentially) optimal. We also discuss a slightly less tight bound of roughly 23n/7−s for general Nostradamus attacks against random compression functions, where s is the maximal block length of the adversarially chosen suffix S. |
|---|
| Conference | 28th International Conference on the Theory and Application of Cryptology and Information Security |
|---|
| Isbn | 978-3-031-22968-8 |
|---|
| Serie | Lecture Notes in Computer Science |
|---|
| In | Advances in Cryptology - ASIACRYPT 2022, p.583-613 |
|---|
| Publisher | Springer |
|---|
| Url | https://tubiblio.ulb.tu-darmstadt.de/id/eprint/138883 |
|---|
