Cryptology ePrint Archive: Report 2021/703

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:

[ Cryptology ePrint archive ]