IACR News item: 28 August 2023
Xiaoyang Dong, Shun Li, Phuong Pham, Guoyan Zhang
ePrint Report
At ASIACRYPT 2022, Benedikt, Fischlin, and Huppert proposed the quantum herding attacks on iterative hash functions for the first time. Their attack needs exponential size of quantum random access memory (qRAM). As the existence of large qRAM is questionable, Benedikt et al. left open question for 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 the size of qRAM is reduced from Benedikt et al.'s $2^{0.43n}$ to ours $\mathcal{O}(n)$. Besides, we also introduce various low-qRAM quantum attacks on hash concatenation combiner, hash XOR combiner, Hash-Twice, and Zipper hash functions.
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 the size of qRAM is reduced from Benedikt et al.'s $2^{0.43n}$ to ours $\mathcal{O}(n)$. Besides, we also introduce various low-qRAM quantum attacks on hash concatenation combiner, hash XOR combiner, Hash-Twice, and Zipper hash functions.
Additional news items may be found on the IACR news page.