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

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

(1) 对 i=1,…,j1,j+1,…,N,判断:如果 i>l,令 mm i ;如果 i≤l 且 i≤j,令 mm 0i ;如果 i≤l 且 i>j,令 mm 1i .

选择 r  CoinsNRu (parm sk pk ), 然后计算 c  RP (sk pk , ,c pk ,sk ,m r   );
,
,
,
,
i R Rnd SC S i R i S R i R i R i R
(2) 令 C=(c 1 ,…,c j1 ,c,c j+1 ,…,c N );
1
,  

(3) b MA MSC ( ),RO ( ),DSC （） ,...,DSC l ( ) (Guess C ,State ) (要求不能询问 C的有关知识);
(4) 返回 b.
上述构造中,对敌手 A 来说,j=1,2,…,N 是等概率,在 MA 的挑战密文中,接收方 R j 的密文恰好是敌手 A 的挑
战密文,而方案 M的可再生性保证了挑战密文中所有 N 个密文使用了相同的部分随机数 .r 显然,实验
1 N
attkExp CCA 2-0 ()k 与实验 HBExpH j (k)是一致的,可以得出 Pr[attkExp CCA 2-0 ( ) k  0]   i . p


, A
, A
N i 1
1 N
CCA
同理,实验 attkExp  ,A 2-1 ()k 与实验 HBExpH j-1 (k)是一致的,可以得出 Pr[attkExp CCA 2-1 ( ) k  0]   p i 1 . 于

,A
N i 1
| p  p |
-CCA
是,我们可以计算 A 的优势 Adv CCA 2 ()k  n 0 , 从而可得 Adv M  N -MR ,MA 2 ()k  n ()k  Adv  CCA 2 ().k 由于敌手 A 将敌

,A
,A
N
手 MA 作为一个子过程调用,A 可以利用 MA 的所有知识,因此综合可得:
-
-attk
Adv M  NMR ,MA ()k ≤ n ()k  Adv attk , A ().k □

由上述定理 1 可知:如果标准签密方案是随机数部分重用可再生的,且是 IND-CPA(IND-CCA2)安全的,即
-attk
attk
-
攻击者 A 的优势 Adv  ,A ()k 可以忽略,那么对应的多接收方签密方案 M中,攻击者 MA 的优势 Adv NMR ,MA ()k ≤
M 
attk
() Adv
nk  , A ()k 也可以忽略.因此,采用定义 5 的方法基于标准方案构造的多接收方方案 M也是 IND-CPA
(IND-CCA2)安全的.
定理 2(可再生不可伪造安全性). 给定一个标准签密方案=(Gen,Kgen,SC,DSC)和一个多项式 n(),设 k 为安
全参数,接收方个数为自然数 N=n(k),M=(Gen,Kgen,MSC,DSC)是相应的 PRRU-MM-MR 签密方案.如果是可
再生的,那么对于任意多项式时间敌手 FA,存在着一个多项式时间敌手 FB,对任意安全参数 k,满足:
-CMA
-
Adv M  NMR ,FA ()k ≤ n ()k  Adv CMA ().k
,FR

证明:如果一个多项式时间伪造者 FA 可以伪造 M的签密文,我们构造一个伪造者 FR,他将实验的接收方 R
设置为 FA 伪造实验的接收方 R j ,并把 FA 作为一个子过程调用,攻击的不可伪造安全性.
 (State)FR(select,parm).
(1) parm Rnd Gen(k),(State)FA(select,N,parm),j Rnd (1,…,N);
(2) 选取:
CoinsKgen=(CoinsKgen 1 ,…,CoinsKgen j-1 ,CoinsKgen j+1 ,…,CoinsKgen N ),State(State,j,CoinsKgen);
(3) 返回 State
 (m,c)FB SC(),RO() (State,pk S ,pk R ,sk R ).
,
(1) 对于 i=1,…,j1,j+1,…,l,计算 (pk ,sk )  Kgen ( parm ,CoinsKgen ),( pk ,sk )  (pk sk ), 令:
i R i R Rnd i j R j R R R
PK R  (pk 1 R ,..., pk R N ),SK R  (sk 1 R ,...,sk R N );
,
(2) 计算(m i ,c i )F MSC(),RO() (pk S ,PK R ,SK R ),其中,i(1,2,…,N).如果满足 DSC RO () (,c pk sk i R )  m 且没有向
S
i
i
签密预言机 MSC()询问过 m i 的签密,选取 r  CoinsNRu ( parm sk pk ), 然后计算:
,
,

j R Rnd SC S j R
c  RP (sk pk , , c pk ,sk ,m r  );
,
,
j S i R i j R j R j j R
(3) 返回(m j ,c j ).
上述过程中,FA 如果赢得了游戏,输出一对合法的签密文(m i ,c i ).对于任意接收方 R j ,伪造者利用再生算法 RP
可以构造出一对合法的签密文(m j ,c j ),因此有 Pr[ForgeExp CMA 1 ( )1]... Pr[k    ForgeExp CMA N ( )1].k 


,FR
,FR
CMA
对 FR 的伪造实验 ForgeExp  ,FR j ()k 来说,伪造的签密文需要通过特定的一个接收方 R j 的验证才能赢得游
-CMA
-
戏;而对 FA 的伪造实验 ForgeExp NMR ,FA ()k 来说,伪造的签密文只要任意一个接收方通过验证即可赢得游戏,因
M 