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

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

(1) 若δ=σ,根据去盲化过程,有:
2
2
δ′/e =σ′/e .
根据签名过程,有:
2
2
δ′=sk(eH(m||m′))′=e sk(H(m||m′))′,σ′=sk(eH(m||m′))=e sk(H(m||m′)),
则:
2
2
2
2
e sk(H(m||m′))′/e =e sk(H(m||m′))/e ,sk(H(m||m′))′=sk(H(m||m′)).
−1
−1
−1
若想要上式成立,那么敌手 A 必须得到签名者 B 的私钥{L ,G ,S }.由于 h 是一个保密的单向不可逆哈希
−1
−1
−1
−1
−1
−1
−1
函数,所以通过 h L 和 h N 求得 L 和 N 是不可行的,由 N G S 得到 N ,G ,S 是不可行的,这相当于解决
IP 困难问题.
(2) 若δ≠σ,根据去盲化过程,有:
2
2
δ′/e ≠σ′/e .
根据签名过程,有:
2
2
2
2
e sk(H(m||m′))′/e ≠e sk(H(m||m′))/e ,sk(H(m||m′))′≠sk(H(m||m′)).
通过上式可知,敌手 A 不可能伪造一个有效的签名.
综上所述,经过 t 次盲签名交互过程,所得到的有效签名δ j 和σ j 都通过验证,若想要签名δ j =σ j (j=1,2,…,t),则必
−1
−1
−1
−1
−1
−1
−1
−1
须得到签名者 B 的私钥{L ,G ,S }.由公钥 N G S,h L 和 h L 得到私钥{L ,G ,S },这相当于解决 IP 问题.
因此,敌手 A 无法以不可忽略的优势赢得挑战,假设不成立.从而证明了若 IP 问题在有限域 F 上是困难的,则所
构造的抗量子计算的多变量盲签名方案满足不可伪造性.证毕. □
• 证法 2
证明:对于一个消息 m,先对消息 m 增加几个随机比特 m′,假设对 m||m′进行盲签名交互过程,可以产生一个
有效的签名.分别用列表 L H ,L S 和 L V 记录 H 询问、签名询问和验证询问,所用列表初始均为空.最多可以执行 q
L H
次 H 询问、 q 次签名询问和 q 次验证询问.假设敌手 A 以不可忽略的优势ε成功伪造签名,则存在挑战者 C
S L V L
以不可忽略的优势ε′解决 IP 问题.
挑战者 C 运行系统初始化算法和密钥生成算法,将系统参数(F,p,l,r,n,H)和公钥发送给敌手 A.
(1) H 询问:当 A 向 C 请求关于 m||m′的 H 询问时,首先,C 查询列表 L H :若 L H 中存在相应的记录(m||m′,H),
r
则 C 直接返回结果 H 给 A;否则,C 随机选取 H∈F 发送给 A,同时将(m||m′,H)添加到列表 L H 中;
(2) 签名询问:当 A 向 C 请求关于 m||m′的签名询问时,首先,C 查询签名列表 L S :若 L S 中存在相应的记录,
则返回签名σ;否则,调用 H 询问(若在此询问之前,表中已经存在此询问记录,则伪造签名失败),再执行
盲签名算法得到签名σ,然后将此记录添加到签名列表 L S 中;
(3) 验证询问:当 A 向 C 请求关于 m||m′的验证询问时,首先,C 查询验证列表 L V :若 L V 中存在相应的记录,
则返回消息 m||m′;否则,执行验证算法得到 m||m′.再对 L H 进行查找:若存在相应的记录,则返回 m||m′;
否则,拒绝这个签名.
*
经过多次盲签名交互过程后,A 提交一个伪造的签名σ .
−1
*
−1
−1
通过上面的询问,如果敌手 A 想要伪造一个有效的签名σ ,他必须得到签名者 B 的私钥{L ,G ,S }.由
−1
−1
−1
−1
−1
N G S,h L 和 h N 得到私钥{L ,G ,S },这相当于解决 IP 问题.
我们用 E 1 和 E 2 表示敌手 A 伪造签名失败的事件.
1) E 1 :当在步骤(2)签名询问时,重新调用的 H 询问已经在步骤(1)中所记录,则伪造签名失败.这个优势为:
−
r
Pr[ ]E ≤ (q + q )2 ;
1 Ls L H
−
r
2) E 2 :当在步骤(3)验证询问时,拒绝了一个有效的签名.这个优势为 Pr[E ≤ q 2 .
]
2 V L
−
]
1
另外, Pr[E ≤ q 表示在步骤(3)签名询问阶段得到了一个有效签名的优势.Pr(E 4 )=ε表示敌手 A 成功伪造
3 s L
签名的优势.