美国国家标准与技术研究院（National Institute of Standards and Technology，NIST）于2016年面向全球征集抗量子密码算法标准。经过近一年的征集及形式审查，NIST于2017年12月公布了69个算法作为首轮候选算法。随后，NIST启动了对入选算法的评估工作。在组织人力对入选算法进行内部评估的同时，NIST也面向全球公开征集对这些算法的外部评估。密钥交换算法是非常重要的一类密码学算法，主要是为通信双方建立临时的通信密钥，在现实中有极为广泛的应用。设计抗量子的密钥交换算法，不仅在将来可以用于应对量子计算机的威胁，而且也有助于保护当下加密的通讯内容，即使在将来量子计算机出现后，依然不能够被破解。

HK17是由Hecht和Kamlofsky提交到NIST的密钥交换算法，其主要基于经典的Diffie-Hellman框架，并利用八元数等超复数，来实现密钥交换。八元数由Grave和Cayley分别于1844和1845年独立发明。设计者认为，由于八元数不满足交换性和结合律，因此对其密钥交换算法最好的攻击，是穷搜建立的临时密钥，而穷搜在经典计算机模型下复杂性可以达到O(p^8)，其中p为HK17所选取的有限域的大小。

然而，注意到每一个八元数都满足一个二次方程，Burnstein和Lange提出可以通过更有效的穷搜，将攻击复杂度从提交者声称的O(p^8)降到O(p)，但对于HK17的规模较大的参数，其攻击在现实中尚不能实现。特别是，HK17的所有操作可以在关于log p的多项式时间内完成，因此，理论上，Burnstein和Lange的攻击依然是指数时间攻击，只是降低了HK17算法的安全性，但不能彻底攻破。与此同时，潘彦斌等[1]独立给出了针对HK17的时间复杂度为O?(log p)的多项式时间攻击，主要做法是对八元数的每个坐标建立方程，再利用线性化的技术得到了有限域上具有4个未知数的8个线性方程，从而用有限域上线性方程组的求解来代替遍历，从而完全攻破了该密码算法。利用此方法，他们首次在现实中实现了对HK17所有参数下的成功攻击。

基于上述攻击，提交者主动撤回了HK17算法。

Haoyu Li,Renzhang Liu, Qutaibah M. Malluhi, Yanbin Pan, Yongge Wang, and Tianyuan Xie: Breaking HK17 in Practice. In Proc. Of ISIT 2019.

潘彦斌          panyanbin@amss.ac.cn