改进的五轮Grostl-512的量子碰撞攻击

Improved Quantum Collision Attack on 5-Round Grostl-512

量子算法在密码的差分分析中运用的重要性日益显现.在2020年亚密会上,董晓阳等给出了在敌手具有少量甚至不具备量子随机存取寄存器(quantum random access memory,qRAM)条件下如何实施AES类哈希函数的量子碰撞攻击,其中包括对入围SHA-3哈希函数设计竞赛决赛圈的5个算法之一的Grostl-512哈希函数的5轮量子碰撞攻击.通过进一步研究该5轮量子碰撞攻击,发现了一种针对5轮Grostl-512的新型量子碰撞攻击.利用振幅放大算法优化反弹攻击的搜索流程,使该攻击的量子复杂度较董晓阳等的攻击降低为原来的1/2^(24).

At ASIACRYPT 2020,Dong et al.introduced the quantum collision attacks on AES-like hash algorithms with few or even no quantum random access memory(qRAM),including a quantum collision attack on 5-round Grostl-512,one of the five finalists in the SHA-3 hash algorithm competition.By revisiting Dong et al.’s 5-round quantum collision attack on Grostl-512,this paper presents an improved quantum collision attack on Grostl-512,with quantum complexity being 1/2^(24) times that of the original attack.