Paper 2023/1286
Quantum Attacks on Hash Constructions with Low Quantum Random Access Memory
Abstract
At ASIACRYPT 2022, Benedikt, Fischlin, and Huppert proposed the quantum herding attacks on iterative hash functions for the first time. Their attack needs exponential quantum random access memory (qRAM), more precisely {$2^{0.43n}$} quantum accessible classical memory (QRACM). As the existence of large qRAM is questionable, Benedikt et al. leave an open question on building low-qRAM quantum herding attacks. In this paper, we answer this open question by building a quantum herding attack, where the time complexity is slightly increased from Benedikt et al.'s $2^{0.43n}$ to ours $2^{0.46n}$, but {it does not need qRAM anymore (abbreviated as no-qRAM)}. Besides, we also introduce various low-qRAM {or no-qRAM} quantum attacks on hash concatenation combiner, hash XOR combiner, Hash-Twice, and Zipper hash functions.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Published by the IACR in ASIACRYPT 2023
- Keywords
- Quantum CryptanalysisqRAMHerding AttackHash Combiner
- Contact author(s)
-
xiaoyangdong @ tsinghua edu cn
shun li @ ntu edu sg
pham0079 @ e ntu edu sg
guoyanzhang @ sdu edu cn - History
- 2023-09-13: revised
- 2023-08-28: received
- See all versions
- Short URL
- https://ia.cr/2023/1286
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1286,
author = {Xiaoyang Dong and Shun Li and Phuong Pham and Guoyan Zhang},
title = {Quantum Attacks on Hash Constructions with Low Quantum Random Access Memory},
howpublished = {Cryptology ePrint Archive, Paper 2023/1286},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/1286}},
url = {https://eprint.iacr.org/2023/1286}
}
