Page 276 - 《软件学报》2021年第10期

3248 Journal of Software 软件学报 Vol.32, No.10, October 2021

 q q q H    q q q H  

q DSC  H 1  H 2  2 f  3 .综合可得,敌手 B 的优势  B  A  1 q DSC  ≥ H 1  H 2  2 f  3 . 
 2 k 2 1 f 2     2 k 2 1 f 2   
引理 4(不可伪造安全性). 在随机预言机模型下,如果存在伪造者 FA,运行时间为 t FA ,进行不多于 q SC 次签密
询问、 q 次预言机 H 1 询问、 q H 2 次预言机 H 2 询问、 q H 3 次预言机 H 3 询问,在 ForgeExp CMA ()k 实验中,以不可

,FA
H
1
忽略的优势 FA 伪造一个上述标准签密方案的合法签密文,那么存在敌手 FB,以不可忽略的优势 FB ≥
 qq 1 
 FA  1 SC H 1  2  攻破小整数解(SIS)问题 [18] .
k
 2 2  k
路秀华等人已给出了方案不可伪造性的可证明安全性,这里不再介绍,详见 LWWD16定理 3.由于 LWWD16
定理 2 并没有给出量化的优势,下面我们分析敌手 FB 的量化优势.
k
在签密询问阶段,敌手 FB 应答失败的概率为 qq /2 ; 在解签密阶段,由于 FB 扮演真实解密者,他不能拒
SC H 1
绝一个合法的签密文.另外,伪造者 FA 在不经过询问的情况下,伪造一个合法密文的概率相当于猜测私钥的概
 qq 1 
2
率,大小为1/ 2 . 综合可得,敌手 FB 的优势  FB  FA  1 ≥ SC H 1  2  .
k
 2 k 2  k
4.3 PRRU-MM-MR签密方案
4.3.1 LWWD16 方案的可再生性
LWWD16 方案中,签密算法共包含 5 个随机数.不难看出,该方案并不满足随机数全重用的安全条件(典型
地,随机数在解签密过程中被接收方解密,如果重用该随机数,在考虑内部攻击的模型下,方案的安全性必然受
到影响).但是需要指出的是,该方案满足重用两个随机数的安全条件.下面我们基于随机数部分重用可再生的
签密方案的定义,证明该方案是随机数部分重用可再生的;并基于此标准签密方案构造一个 PRRU-MM-MR 签
密方案 M,通过重用部分随机数,该方案在不牺牲安全性的条件下节约了计算和通信开销.
定理 5. 对上述标准签密方案=(Gen,Kgen,SC,DSC),令 r  (, ),r ee 2  R ( , , ),y  e 3 那么是重用随机数 r 可再
1
生的.
证明:设一个发送方的私钥 sk S ,一个接收方的公钥 pk R ,一个签密文 c=(v 1 ,v 2 ,)(某个随机消息 m 经该公钥生
(, , ),  e
成的签密文),另一个随机消息 m,另一个接收方的公私钥对(pk R ,sk R )以及非重用部分随机数 r  y  3 下面

R
(, , ).
我们构造一个多项式时间再生算法 RP,输出一个合法签密文 c  vv 
1 2
,
 RPsk , pk , ,c pk ,sk ,m r   ).
(
S R R R R
(1) 选取 y  D k ;
Rnd u
(2) 计算 b=H 1 (Ay(mod q) d ,m),z=X S b+y;
(3) 计算 w=AzB S b(mod q),如果 w的某个分量 w 不满足 |[ ] |w i 2 d ≤ 2 d  1  7 返回步骤(1)重新开始;
,
i
 D k ()  z 
(4) 根据概率 min u ,1 保留(z,b);
 MD k ()   z
 , u Xb 
S 

(5) 选取随机数{0,1} ,计算  k Enc H 2 ()   (, , );m  zb 
(6) 令   ( ,..., ),  1  k 对 i=1,…,k,如果 i 0,   i   Rnd [ q   / 4 , q / 4 ]; 否则,  Rnd [q/2q/4,q/2+q/4],令:


 
i
  ( ,..., );  1   k 
(7) 计算  2 T   v   v X R (mod );q
T
1
(8) 返回密文 c (, , ).vv   2
1
根据上述 RP 的构造,显然有 DSC(pk S ,sk R ,c)=m,因此它是消息 m一个合法签密文,又签密文 c 与 c使用了
,
部分相同的随机数 ,r 综合可得 SC (sk pk R ,m , ,r r  R )  RP (sk pk R , ,c pk R ,sk R ,m r   , R ). 根据可再生的签密方案定
,
S
S
义 10 可得,是重用随机数 r 可再生的. □