计算机研究与发展

作者：张中亚,吴文玲,邹剑,

关键词：量子计算, Grover量子算法, BHT量子算法, 差分分析, EM结构,

量子算法的发展和应用对密码算法的设计和分析产生了深远的影响，其中Grover量子算法和Simon量子算法在密码安全性评估中应用较多，但作为生日碰撞攻击量子化的BHT(Brassard，H?yer，Tapp)量子算法，还没有得到具体应用，研究BHT量子算法对密码算法的分析具有重要意义.通过对多轮EM(Even，Mansour)结构进行分析，研究了经典条件和量子条件下的碰撞搜索算法与差分密钥恢复攻击的结合，对多轮EM结构进行了差分碰撞密钥恢复攻击，并从BHT量子算法的角度进行量子化.结果表明，经典条件下，当差分传递概率2-p≥2-n/2时，r轮EM结构的差分密钥恢复攻击时间复杂度从O(2p+n)降到O(2p+n/2)，速度快了2n/2倍.量子条件下，当差分传递概率2-p>2-n/3时，结合BHT量子算法的差分碰撞密钥恢复攻击时间复杂度要优于基于Grover量子算法的差分密钥恢复攻击，显示了BHT量子算法在具体密码分析中的有效性.

来源：2021年第12期

《计算机研究与发展》期刊编辑部

查看计算机研究与发展杂志2021年第12期