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

俞惠芳 等:抗量子计算的多变量盲签名方案 2939

1.4 Yasuda等人提出的非满射中心映射
2
设 r 是多变量方程组的个数,n 是变量的个数.这里的 r 和 n 均为有限的正整数,并且满足 n=z ,r=z(z+1)/2.
Yasuda 等人 [23] 利用非满射来构造多变量的中心映射,具体结构如下:

T
() =X XBA B X T ,
f
δ ,B δ

r
() : F →X n F 为多变量的非满射中心映射,X 是一个 z×z 的矩阵变量, B 是一个 z×z 的正规矩阵, A 是
其中, f
δ ,B δ
一个 z×z 的对称矩阵,上标 T 表示矩阵的转置.
2 方案实例
本节给出了一个具体的抗量子计算的多变量盲签名方案.详细算法细节如下所述.
1. 系统初始化(Setup)
l
生成系统参数(F,p,l,r,n,H),其中,F=GF(p )是特征为 p 的有限域,r 是多变量方程组的个数,n 是变量的个数,
r
*
哈希函数 H:{0,1} →F .这里的 p 是素数,l,r 和 n 均为有限的正整数.
2. 密钥生成(KeyGen)
−1
−1
−1
−1
−1
n
r
生成签名者 B 的私钥 sk:{L ,G ,S }和公钥 pk:{N G S,h L ,h N },公开公钥,其中,G:F →F 是非满射中
r
r
心映射,具体结构参照本文第 1.4 节和文献[23]中的 f δ,B .L:F →F 是随机选取的非线性可逆变换,N 和 S 分别是
n
r
r
n
F →F ,F →F 随机选取的可逆仿射变换,h 是一个保密的单向不可逆哈希函数.
3. 盲签名(BlindSIG)
(1) 对消息 m 增加几个随机比特 m′ [24] ;
下面介绍如何给消息 m 增加几个随机比特 m′:

a) 计算W = H (( )H m ⊕ ) S ,其中, S 为 r-bit 字符串,值为 00…00;
b) 令 m′=[W] 0→2 为 2-bit 字符串.
(2) 盲化(Blind):O 随机选取盲因子 e∈F,计算 b=eH(m||m′),将盲化后的消息 b 发送给 B;
−1
−1
−1
−1
−1
(3) 签名(Sign):B 收到 b 后,用私钥 sk:{L ,G ,S }依次计算 y=L (b),x=G (y),若 y 没有与之对应的原像 x,
−1
则返回步骤(1),并用 H(W)替换步骤 a)中的 W;否则继续计算σ′=S (x),然后将盲签名σ′发送给 O;
现在说明一下签名失败的概率:根据文献[24]的证明,对消息 m 增加几个随机比特 m′,在签名过程中,y 没有
与之对应的原像 x 的概率约为 2 −85 ,即签名失败的概率约为 2 −85 .这个概率是可以完全忽略不计的,因此对签名过
程的效率影响可以忽略不计.
−1
−1
(4) 去盲化(MoveBlind):O 收到 B 的盲签名σ′后,先验证 h N (N G S(σ′))=h L (b)是否成立:若成立,O 对盲
2
签名σ′去盲化处理,计算σ=σ′/e ,得到签名σ;否则,签名无效.
4. 验证(Verify)
−1
输入系统参数、消息 m||m′和 B 的公钥,验证者计算 h L (H(m||m′)),并用公钥 N G S 和 h N −1 验证等式
−1
−1
h L (H(m||m′))=h N (N G S(σ))是否成立:若等式成立,则签名有效;否则,签名无效.
3 正确性分析
根据第 1.2.1 节中盲签名的定义,只有合法的盲签名才能通过验证.在证明本文方案满足正确性之前,先介
绍用到的相关性质.
性质 1 [23] . 若一有限域 F,V 是有限域 F 上的 n 维向量空间.当映射ϕ:V→F 具有二次形式时,有:
2
ϕ(ax)=a ϕ(x),
其中,a∈F,x∈V.
定理 1. 本文提出的抗量子计算的多变量盲签名方案是正确的.
证明:对消息 m 增加几个随机比特 m′,假设对 m||m′进行盲签名交互过程,可以产生一个有效的签名.若接收