韩益亮

（武警工程大学 密码工程学院，陕西 西安710086）

0 引言

近年来，量子计算理论与量子计算机不断取得新的进展，现代公钥密码面临的威胁日益严峻。由于对抗量子密码的迫切需求，在2006年比利时召开的第一届国际抗量子密码学会议上，多变量公钥密码、基于格的密码、基于纠错码的密码和基于散列函数的签名等被作为抗量子攻击的候选方案。相比于其他抗量子密码，多变量公钥密码的研究起步相对较早，现已有较多成熟的多变量公钥密码算法。多变量公钥密码的安全性是建立在有限域上多元非线性方程组的求解问题上的。该问题的最普通形式即：求解在只有两个元素的有限域上的二次方程组，这被证明是一个NP困难问题。在这个问题的求解上，量子计算机比起传统电子计算机也并没有明显的优势，多变量公钥密码可以良好地抵抗量子计算。它相比于其他抗量子密码具有加解密速度快、消耗资源少的优良特点，但是其公钥尺寸一般较大。

1 多变量公钥密码研究现状

多变量公钥密码系统[1-3]的研究，最早在1984年Ong和 Schnorr发表的文章[4]中就有所涉及。而从完整体制的角度来讲，文献[5]提出的MI（或称为C*）加密体制才算是真正意义上的多变量公钥密码系统，MI方案的提出开启了多变量公钥密码研究和发展的大门。

虽然在1995年，Patarin提出的线性化方程攻击攻破了MI体制，但在此之后又产生了很多新方案。1996年Patarin在攻破MI方案后，提出了隐藏域方程（Hidden Field Equation，HFE）方 案[6]， 但 是 紧 接 着HFE方案又被Kipnis和Shamir[7]分析证明不安全。……