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

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

因此,挑战者 C 解决 IP 问题的优势是ε′=Pr[E 1 ∧E 2 ∧E 3 ∧E 4 ].又因为各事件之间是相互独立的,所以挑战者 C
解决 IP 问题的优势为
ε ⎛ q + q L ⎞ ⎛ q V L ⎞
E ⋅
ε = ′ Pr[E ∧ E ∧ E ∧ E = ] Pr[ ] Pr[E ⋅ ] Pr[E ⋅ ] Pr[E ]≥ ⎜ 1− S L H ⎟ ⎜ 1− .
1 2 3 4 1 2 3 4 q S L ⎝ 2 r ⎠ ⎝ 2 r ⎟ ⎠
可见,挑战者 C 无法以不可忽略的优势ε′解决 IP 问题.从而证明了如果 IP 问题在有限域 F 上是困难的,那
么所构造的抗量子计算的多变量盲签名方案满足不可伪造性.证毕. □
4.3 不可追踪性
定理 4. 本文提出的抗量子计算的多变量盲签名方案满足不可追踪性.
证明:利用第 1.2.2 节中的 Game3 安全模型证明所提方案满足不可追踪行性.下面介绍挑战者 C(模拟签名
者 B)和消息拥有者 O 的盲签名交互过程.
(1) O 通过运行系统初始化算法生成系统参数(F,p,l,r,n,H),同时,通过运行密钥生成算法生成签名的公私
钥对,并将系统参数和私钥发送给 C;
(2) 对消息 m 增加几个随机的比特 m′,假设对 m||m′进行盲签名交互过程可以产生一个有效的签名;
(3) O 随机选取两个等长的不同的盲因子 e 0 ∈F 和 e 1 ∈F;
(4) O 选择一个随机的比特值θ∈{0,1},然后计算 b θ =e θ H(m||m′)和 b 1−θ =e 1−θ H(m||m′),然后将 b θ 和 b 1−θ 以随机
顺序发送给 C;
(5) C 先后分别依次计算:
y = θ L − 1 (),b θ x = θ G − 1 (y θ ),σ θ S − 1 ( ),x θ y 1 θ − = L − 1 (b 1 θ − ),x 1 θ − = G − 1 (y 1 θ − ),σ′ ′ = 1 θ − = S − 1 (x 1 θ − ) ,
然后,先后发送盲签名 σ ′ 和σ ′ 1 θ− 给 O;
θ
(6) O 利用盲因子 e θ 和 e 1−θ 计算签名 σ θ σ = θ ′ /e 和 σ θ 2 1 θ− = σ 1 θ ′ − /e 1 θ 2 − ,并将σ θ 和σ 1−θ 先后发送给 C;
(7) C 输出一个θ的猜测值θ′∈{0,1}.
现在分析挑战者 C 猜对θ的概率.因为盲因子 e θ 和 e 1−θ 是消息拥有者 O 在有限域 F 上随机选取的,而且选取
的过程完全独立于消息 m||m′,因此盲因子 e θ 和 e 1−θ 、消息 m||m′、签名σ θ 和σ 1−θ 这三者之间完全相互独立.对于
挑战者 C,在不知道盲因子的条件下,无法将消息、盲签名、签名这三者联系起来.因此,即使 C 拥有无限的计算
能力,他猜对θ的概率只有 1/2,即 Pr(θ=θ′)=1/2,则挑战者 C 赢得挑战的优势是:
=
Adv Game 3 = |Pr(θ θ = ′ − ) 1/ 2 | 0 .
C
可见,挑战者 C 无法以不可忽略的优势赢得挑战.从而证明了所构造的抗量子计算的多变量盲签名方案满
足不可追踪性.证毕. □
5 效率分析

签名效率主要取决于签名的公钥长度、私钥长度和签名长度.本节依据这 3 个要素分析本文构造的抗量子
计算的多变量盲签名方案与类似方案的性能.由文献[24]和 L,N 的构造过程可知,对消息 m 增加几个随机的比特
−1
−1
m′和增加公钥 h N ,h L 并不影响整个盲签名交互过程的运算效率.表 1 从签名的公钥长度、私钥长度和签名
长度分析文献[18,19]和本文方案的效率.
表 1 中的 r 为多变量方程组的个数,n 为变量的个数.从表 1 可看出:由于本文方案只采用一个非满射中心映
射,所以和文献[18]相比,签名的私钥长度减少了 50%;与文献[19]相比,公钥长度和签名长度都有所减少.
Table 1 Comparison of efficiency
表 1 效率比较
方案 公钥长度 私钥长度 签名长度
方案[18] r(n+1)(n+2)/2bit 2(r(r+1)+n(n+1))bit nbit
2
方案[19] r(n+1)(n+2)/2+r(r +3r+2)/2bit r(r+1)+n(n+1)bit n+rbit
本文方案 r(n+1)(n+2)/2bit r(r+1)+n(n+1)bit nbit