Page 312 - 《软件学报》2021年第9期

2936 Journal of Software 软件学报 Vol.32, No.9, September 2021

签名,也不确定什么时候他签署了这个签名,这种情况下就可以用到盲签名.盲签名可以理解为将需要签名的文
件放在装有复印纸的文件袋中,签名者看不到文件的具体内容,他只需要在文件袋上签名,这样签名可以通过复
印纸印在文件上.盲签名主要用于电子现金支付、电子投票等需要匿名性和认证性的应用场合中 [2−4] .自 1983
年以后,盲签名引起了广泛的关注,学者们也提出了众多盲签名方案 [5−7] ,但是目前大多数盲签名都是基于传统
公钥密码体制的 [8−10] .传统公钥密码体制的安全性主要依赖于大整数分解问题或离散对数问题的难解性.随着
量子计算 [11] 的发展,使得基于传统公钥密码体制的盲签名方案受到了严重威胁.为此,研究具有抗量子计算特性
的盲签名方案具有重要的意义.多变量公钥密码作为后量子密码的主要候选者之一,其安全性基于有限域上二
次多变量多项式方程组(multivariate quadratic,简称 MQ)问题和多项式同构(isomorphism of polynomials,简称
IP)问题的难解性,已有的量子算法目前还不能很好地解决 MQ 问题和 IP 问题.多变量公钥密码具有计算效率
高、运算速度快等优点,非常适用于计算能力有限的设备.文献[12,13]提出了多变量环签名方案;文献[14]运用公
平划分的思想,将文献[12]转化为多变量门限环签名方案;文献[15,16]提出了多变量代理签名方案;文献[17]提
出了多变量群签名方案;文献[18]提出了多变量盲签名方案,但是该方案运用传统的多变量签名模型,为了产生
一个有效的签名,采用了两个非满射中心映射,其只能应用在已知安全的多变量公钥密码体制下,而且安全性
低、计算效率低;文献[19]提出了一个交互式的多变量盲签名方案,但是其公钥长度和签名长度较大.
2009 年,Wang 等人 [20] 提出了一种多变量签名模型改进的方案,本质上是增加一个秘密仿射变换 M 来分离
签名私钥和验证公钥之间的线性关系.2012 年,Lu 等人 [21] 对 Wang 等人的方案进行了分析,指出:可以通过合法
用户的 r+1 个已知签名建立线性方程组,使 Wang 等人的方案转化为一般的签名方案,进而说明增加秘密仿射变
换 M 并不能提高原有签名方案的安全性.Lu 等人 [22] 提出使用非线性可逆变换 L 替代秘密仿射变换 M,减少签名
私钥和验证公钥的线性关系,提高了签名方案的安全性.Yasuda 等人 [23] 提出利用非满射中心映射构造多变量公
钥密码,具有隐藏代数矩阵和线性对等线性性质.
本文在盲签名和多变量公钥密码的理论基础上,借鉴文献[22]改进的多变量签名模型和文献[23]的非满射
中心映射,提出一种多变量公钥密码体制下的后量子盲签名方案.由于所提方案只有一个非满射中心映射,为了
使方案可以产生一个有效的签名,本文借鉴文献[24]对消息增加几个随机比特的思想.所提方案的公私钥之间
没有线性关系,使得盲签名的安全性得到提高.经过安全性分析,证明了该密码方案满足盲性、不可伪造性和不
可追踪性,而且计算效率高还能防御量子计算攻击.
1 预备知识

1.1 多变量公钥密码
多变量公钥密码的单向陷门函数形式是有限域 F 上的多变量二次多项式映射,公钥的一般形式如下:
P=(p 1 (x 1 ,x 2 ,…,x n ),…,p r (x 1 ,x 2 ,…,x n )).
每个方程 p i (i=1,2,…,r)是一个关于 x=(x 1 ,x 2 ,…,x n )的非线性二次方程:
n
pxx = γ x x + ∑ j k ∑ β x + α ,
(, ,..., ) :x
i 1 2 n ijk ij j i
j
1≤≤ k≤ n j= 1
其中,方程的系数γ ijk ,β ij ,α i ∈F(1≤i≤n,1≤j≤k≤n),变量 x j ,x k ∈F.多变量公钥密码的安全性主要依赖于 MQ 问题
和 IP 问题的难解性.
定义 1(MQ 问题). 给定有限域 F q (q 为有限域 F 的阶)中的 r 个 n 元方程式的非线性方程组:
p 1 (x 1 ,x 2 ,…,x n ),p 2 (x 1 ,x 2 ,…,x n )=…=p r (x 1 ,x 2 ,…,x n )=0.
求解该方程组的问题被称为 MQ 问题.已经证明 MQ 问题是非确定多项式(nondeterministic polynomials,简
称 NP)困难问题,即使是在最小的有限域 F 2 上.
定义 2(IP 问题). 设 P 和 Q 是有限域 F q 上随机选取的 r 个 n 元方程的多变量方程组,且 P 和 Q 同构,则有
P=T Q S,其中,T 和 S 分别为两个可逆仿射变换,则称寻找从 Q 到 P 同构的(T,S)问题为 IP 问题 [16] .