乔帅庭，李益发，韩文报

（1.信息工程大学 四院，河南 郑州 450002；2. 数学工程与先进计算国家重点实验室，江苏 无锡 214125）

1 引言

二十一世纪是信息的时代，继电子信息科学技术之后，量子和生物等新型信息科学正在建立和发展。量子计算机的产生将会对目前广泛使用的基于离散对数（包括椭圆曲线上的离散对数）和大数分解的公钥密码体制构成潜在的威胁[1～3]。为此，基于抗量子的公钥密码体制成为密码学中一个研究的热点和重点[4]。多变量公钥密码系统作为一种能有效抵抗未来的基于量子计算机攻击方法的密码体制，在近二十几年受到越来越多的关注。

多变量公钥密码体制的安全性是基于有限域上多元非线性方程组的难解性[5]和多项式同构问题[6]。1988年，日本学者Matsumoto和Imai提出了第一个多变量公钥密码方案，即著名的Matsumoto-Imai(MI)方案[7]。该方案将“小域—大域”思想引入了多变量公钥密码方案，有较高的计算效率，在当时被认为是安全的。然而，1995年，Patarin等提出了针对MI方案的线性攻击[8]，攻破了原始的MI体制。为了抵抗线性攻击，Patarin等在2001年提出了FLASH方案[9]，Ding等人于2004年提出了PMI方案[10]，但都受到差分攻击的影响[11,12]。到目前为止，多变量公钥密码体制主要有5类方案[5]：MI方案、hidden field equation (HFE)方案、unbalanced oil andvinegar (UOV)方案、stepwise triangular systems (STS)方案和medium field equation (MFE)方案，但大部分不能同时用于加密和签名。近几年来，多变量公钥密码体制的研究一直是热点，相继出现了CyclicRainbow方案[13]、Double-Layer square方案[14]、Enhenced STS方案[15]等，它们在安全性上得到了不同程度的提高[16,17]。2011年，Wang等通过引入Hash认证技术、并结合传统Multivariate Quadratic（MQ）公钥密码算法，提出了一种扩展MQ公钥密码体制[18]，同时具备加密和签名功能。……