CryptoDB
Quantum Attacks on Hash Constructions with Low Quantum Random Access Memory
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | ASIACRYPT 2023 |
| 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. |
BibTeX
@inproceedings{asiacrypt-2023-33383,
title={Quantum Attacks on Hash Constructions with Low Quantum Random Access Memory},
publisher={Springer-Verlag},
author={Xiaoyang Dong and Shun Li and Phuong Pham and Guoyan Zhang},
year=2023
}