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

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

4.3.2 PRRU-MM-MR 签密方案的构造
对于上述标准签密方案=(Gen,Kgen,SC,DSC)和安全参数 k,设 n()为某个多项式,接收方个数为自然数
N=n(k),定义 M=(Gen,Kgen,MSC,DSC)是相应的 PRRU-MM-MR 签密方案,发送方公私钥对(pk S ,sk S ),接收方公钥
向量 PK  ( pk , pk ,..., pk ), 明文向量 M=(m 1 ,m 2 ,…,m N ),其中,m i Mspc(parm)(1≤i≤N)为发送方 S 发送给接
R 1 R R 2 R N
收方 R i 的消息,参数生成算法 Gen,密钥生成算法 Kgen 以及解签密算法 DSC 与方案相同,签密算法 MSC 的构
造如下.
(1) 计算(pk S ,sk S ) Rnd Kgen(parm);
(2) 对于 i=1,2,…,N,计算 (pk ,sk )  Kgen (parm
);
i R i R Rnd
(3) 设 r  (, )r r  ( , ),ee 其中,(e 1 ,e 2 )的选取同 SC 算法;
1 2 1 2
(4) 对 i=1,2,…,N,选择 r  (, ,y  e ), 其中,(y i , i ,e 3i )的选取同 SC 算法.令 r  ( ,,, ,ee y  e ), 计算:

i R i i 3i i R 1 2 i i 3i
c  (,vv , )  SC (sk pk ,m r );
,
,
i 1 2i i S i R i i R
(5) 返回 C=(v 1 ,v 21 , 1 ,v 22 , 2 ,…,v 2N , N ).
发送方 S 将密文广播给接收方,对 i=1,2,…,N,每个接收方 R i 获得自己的密文(c i =(v 1 ,v 2i , i )).
上述构造的多接收方签密方案是基于定义 5 描述的基于标准签密方案重用部分随机数来构造多接收方签
密方案的通用方法构造的,由标准签密方案可得 DSC(pk S ,sk R ,c)=m,即上述 PRRU-MM-MR 签密方案满足正
确性,下面我们分析方案的安全性.
4.3.3 安全性
定理 6(保密安全性). 在随机预言机模型下,如果存在敌手 MA,进行不多于 q MSC 次签密询问、q DSC 次解签
密询问、q 次预言机 H 1 询问、q H 2 次预言机 H 2 询问、q H 3 次预言机 H 3 询问,以不可忽略的优势 MA 攻击上述
H
1

PRRU-MM-MR 签密方案 M的 IND-CCA2 安全性,那么存在敌手 B,以不可忽略的优势 B ≥ MA 1 q
N DSC
 q H 1 q H 2  q H  3   攻破判定性 LWE 问题.
 2 k   2 1 f 2 2 f    
证明:由定理 5 可得,上述多接收签密方案 M所基于的标准签密方案是可再生的.由保密再生性定理 1,如
果标准签密方案是可再生的签密方案,那么对于相应的多接收方签密方案 M的任意多项式时间敌手 MA,存
-CCA
在着一个多项式时间敌手 A,对于任意安全参数 k,满足  MA  Adv N M  -MR ,MA 2 ()k ≤ N Adv  CCA 2 ( ).k 然后,由引理 3 可
, A
得,方案是 IND-CCA2 安全的.如果存在敌手 A,以不可忽略的优势   Adv CCA 2 ()k 攻击上述标准签密方案的

A
, A
  q q q H  

IND-CCA2 安全性,那么存在敌手 B,以不可忽略的优势  B  A  1 q DSC  ≥ H k 1  H 2  2 f  3  攻破判定性带差错的
   2 2 1 f 2   
 q q q H       q q q H  

学习(LWE)问题.综合可得  B  A  1 q DSC  ≥ H 1  H 2  3 2 f  MA  1 q DSC  ≥ H 1  H 2  2 f  3 ,  上 述 PRRU-
 
 2 k 2 1 f 2    N     2 k 2 1 f 2    
MM-MR 签密方案 M的 IND-CCA2 的安全性得证. □
定理 7(不可伪造安全性). 在随机预言机模型下,如果存在伪造者 MFA,进行不多于 q MSC 次签密询问、q DSC
次解签密询问、 q 次预言机 H 1 询问、 q 次预言机 H 2 询问、 q 次预言机 H 3 询问,以不可忽略的优势 MFA
H 1 H 2 H 3

攻击上述 PRRU-MM-MR 签密方案 M的 euf-CMA 安全性,那么存在敌手 FB,以不可忽略的优势 FB ≥ MFA
N
 qq 1 
SC H
 1 k 1  2  攻破 SIS 问题.
 2 2  k
证明:由定理 5 可得,上述多接收签密方案 M所基于的标准签密方案是可再生的.再由不可伪造再生性定
理 2 可得:如果是可再生的,那么对于相应的多接收方签密方案 M的任意多项式时间伪造者 FA,存在着一个多
项式时间伪造者 FR,对于任意安全参数 k,满足  MFA  Adv M  NMR ,FA ()k ≤ N Adv  CMA ().k 然后,由引理 4 可得,方案
-CMA
-
,FR