Paper 2021/703

Quantum Multi-Collision Distinguishers

Zhenzhen Bao, Jian Guo, Shun Li, and Phuong Pham


In EUROCRYPT~2020, Hosoyamada and Sasaki find differential paths with probability $2^{-2n/3}$ can be useful in quantum collision attacks, v.s. $2^{-n/2}$ for classical collision attacks. This observation led to attacks for more rounds on some AES-like hash functions. In this paper, we quantize the multi-collision distinguisher proposed by Biryukov, Khovratovich, and Nikolic̈ at CRYPTO~2009, and propose quantum multi-collision distinguishers. Compared against the tight bound $2^{\frac{n}{2} \cdot(1-\frac{1}{2^{q}-1})}$ for quantum multi-collision on ideal functions by Liu and Zhang in EUROCRYPT~2019, we find the probability of useful differential paths can be as low as $2^{-n}$. This leads to even more attacked rounds than both classical multi-collision distinguishers and quantum collision attacks. To demonstrate the effectiveness, we applied the attack model to AES, Rijndael, and the post-quantum block cipher design Saturnin. Distinguishing attacks are found on the full version of AES-192, AES-256, Rijndael-128-160, and Rijndael-128-224. Other results include 8-round AES-128, 11-round Rijndael-160-192, 12-round Rijndael-160-256, and 10-round Saturnin-256.

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
post-quantum cryptographymulticollisionfree variableBHTrelated-key differential traildistinguisher
Contact author(s)
lishun93 @ sjtu edu cn
zzbao @ ntu edu sg
guojian @ ntu edu sg
pham0079 @ e ntu edu sg
2021-06-03: last of 2 revisions
2021-05-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zhenzhen Bao and Jian Guo and Shun Li and Phuong Pham},
      title = {Quantum Multi-Collision Distinguishers},
      howpublished = {Cryptology ePrint Archive, Paper 2021/703},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.