王后珍，蔡鑫伟，郭岩，张焕国

（1.武汉大学国家网络安全学院，湖北 武汉 430072；2.密码科学技术国家重点实验室，北京 100878）

1 引言

Goldwasser、Micali 等[1]给出了零知识身份认证的定义，其含义是P试图使V相信其掌握某个知识，或证明论断的正确性，但在该过程中V或第三方无法获得任何与知识相关的内容。整个交互过程的关键即如何做到使V无法获取与知识本身相关的任何信息。自从身份认证协议概念提出后，先后涌现了大批零知识身份认证协议，其中最具代表性协议包括FS 协议[2]、GQ 协议[3]以及Schnorr 协议[4]等。它们的安全性主要基于数论困难问题，如大整数因子分解问题（IFP,integer factorization problem）或有限域上的离散对数问题（DLP,discrete logarithm problem）。

Shor[5]在1994年设计了一种能够以多项式时间复杂度求解IFP和DLP的量子专用算法，也就是说，一旦造出可实用的量子计算机，基于上述数学困难问题设计的密码算法容易遭受攻击。现今密码学领域越来越重视抗量子计算密码的研究与探索，而且一些国家或组织正在积极开展抗量子计算密码算法的标准化工作[6]。

目前，已有的抗量子身份认证密码方案主要如下。1993 年美密会上，Stern[7]基于Syndrome Decoding 问题构造的认证密码方案。后来，文献[8-9]在Stern 方案的基础上做了进一步的优化，减小了Stern 方案的公钥尺寸，减少了交互过程中的数据传递量，并提升了协议的安全性。上述方案均是在有限域F2上设计的，而文献[10]则将上述方案拓展到有限域Fq上（q为素数）。2001 年亚密会上，Courtois[11]基于矩阵最小秩问题提出零知识认证协议；2011 年美密会上，Sakumoto 和Shirai 等[12]基于MQ 问题成功设计出安全实用的零知识认证协议。……