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

刘镇 等:安全随机数部分重用及在多接收方签密的应用 3247

空间用 keysp(k)表示;
*
k
k
(4) 选取 3 个抗碰撞的哈希函数(H 1 ,H 2 ,H 3 ),其中,H 1 :{0,1} {v:v{1,0,1} ,||v|| 1 ≤},H 2 :{0,1} keysp(k),
*
*
H 3 :{0,1} {0,1} (keysp(k)表示密钥空间,表示多次抛硬币得到的随机空间.设 keysp(k)和空间
大小分别为 f 1 与 f 2 ).
 Kgen(密钥生成算法).
(1) 选取矩阵 X  Rnd  kk q , E  Rnd  n k q , 要求 X 和 E 的所有分量大小都不超过 7,若不满足,则重新选择;
(2) 计算 B=AX+E(mod q);
(3) 返回发送方 S 的公私钥对(pk S =B S ,sk S =X S ),接收方 R 的公私钥对 pk R =B R ,sk R =X R .
 SC(sk S ,pk R ,m)(签密算法).
(1) 选取 y  Rnd D u k ;
(2) 计算 b=H 1 (Ay(mod q) d ,m)和 z=X S b+y,其中, x  (x  [ ] )/ 2 ,[ ] d 表示唯一的一个在区间(2 d1 ,
x
d
x
d 2 d 2
2 d1 ]中满足 x  [] (mod2 )x d 的整数;
2 d
,
(3) 计算 w=Az-B S b(mod q),如果 w 的某个分量 w i 不满足 |[ ] |w i 2 d ≤ 2 d  1  7 返回步骤(1)重新开始;
 D k ()z 
(4) 根据概率 min u ,1 保留(z,b);
 MD k ()  z
 , uX b 
S
k
(5) 选取随机数{0,1} ,计算   Enc H 2 () (, , );m zb
(6) 选取错误向量 e 1  Rnd D  n ,e 2  Rnd D  k , 令=H 3 (,),由的随机性选取错误向量 e 3  D  k , 计算:
T
v 1 T e T 1 A  e T 2 (mod ),q v T 2  e B R  T 3  q  e / 2 (mod );q

 
1
(7) 返回密文 c=(v 1 ,v 2 ,).
 DSC(pk S ,sk R ,c)(解签密算法).
(1) 计算  ( ,..., )  1    k  vX R  v T 2 (mod );q
T
1
(2) 对 i=1,…,k,如果 / 4, / 4],q 令  0; 否则,令 
[ q
1;
i
i
i
(3) 令;
(4) 计算 (, , )m zb  Dec ( );
H 2 ()
(5) 验证 b=H 1 (AzB S b(mod q) d ,m)以及||z|| 2 ≤U 是否成立:如果成立,则输出明文 m;否则,输出终止符号.
方案的正确性详见文献[18],下面我们给出安全性描述.
引理 3(保密安全性). 在随机预言机模型下,如果存在敌手 A,进行不多于 q SC 次签密询问、q DSC 次解签密询
问、 q 次预言机 H 1 询问、 q 次预言机 H 2 询问、 q 次预言机 H 3 询问,以不可忽略的优势 A 攻击上述标准
H 1 H 2 H 3
  q q q H  
签密方案的 IND-CCA2 安全性,那么存在敌手 B,以不可忽略的优势   1 q H 1  H 2  3  攻破判

B A  DSC  ≥ 2 k 2 1 f 2 2 f 
     
定性带差错的学习(LWE)问题 [18] .
路秀华等人已给出了方案保密性的可证明安全性,这里不再介绍,详见 LWWD16 定理 2.需要说明的是:在
签密算法 SC 的步骤(6)中,我们将错误向量 e 1 、e 2 的选取方式由原方案根据的随机性选取描述为随机选取,这
并不影响解密.由于是伪随机的,描述为随机选取不会降低方案的任何安全性.可以看出,它也不影响 LWWD16
定理 2 的证明过程.由于假定了 H 3 是一个随机预言机,在随机预言机模型下,=H 3 (,)的随机性与真随机是不可
区分的,因此,上述方式选取的错误向量 e 1 、e 2 与原方案的错误向量 e 1 、e 2 在随机预言机模型下是不可区分的,
即方案的安全性是等价的.由于 LWWD16 定理 2 并没有给出量化的优势,下面我们分析敌手 B 的优势量化.
从 LWWD16 定理 2 的证明过程可以看出:导致模拟不完美的唯一事件是合法密文在解签密询问时被拒绝,
k
它是由哈希函数(H 1 ,H 2 ,H 3 )的模拟引起的,其中,对 H 1 询问的模拟,该概率不会超过 q /2 ; 对 H 2 询问的模拟,该
H 1
1 f
2 f
概率不会超过 q /2 ; 对 H 3 询问的模拟,该概率不会超过 q /2 .对于 q DSC 次解签密询问来说,总概率不超过
H 2 H 3