**Quantum Multi-Collision Distinguishers**

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

**Abstract: **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.

**Category / Keywords: **secret-key cryptography / post-quantum cryptography, multicollision, free variable, BHT, related-key differential trail, distinguisher

**Date: **received 27 May 2021, last revised 3 Jun 2021

**Contact author: **lishun93 at sjtu edu cn, zzbao at ntu edu sg, guojian at ntu edu sg, pham0079 at e ntu edu sg

**Available format(s): **PDF | BibTeX Citation

**Version: **20210603:130918 (All versions of this report)

**Short URL: **ia.cr/2021/703

[ Cryptology ePrint archive ]