Paper 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.
Metadata
- Available format(s)
- Category
- Secret-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- 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 - History
- 2021-06-03: last of 2 revisions
- 2021-05-28: received
- See all versions
- Short URL
- https://ia.cr/2021/703
- License
-
CC BY