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

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

他们的研究对象都是随机数全重用的情况.值得注意的是:随机数全重用和非随机数重用只是随机数重用的两
种情况,而另一种更常见的情况是随机数部分重用,当重用的随机数为空时,随机数重用退化称为非随机数重
用;当重用的随机数为方案中所有随机数时,随机数重用演化成随机数全重用;当重用的随机数为方案中的部分
随机数时,随机数重用称为随机数部分重用.
下面我们将随机数重用的安全理论丰富到另一种常见的情况,从随机数部分重用的角度,定义随机数部分
重用可再生的签密方案(即随机数部分重用的安全条件),给出并证明随机数部分重用可再生性定理(即基于可
再生签密方案构造的随机数部分重用的多接收方签密方案是安全的).
3.1 可再生的签密方案定义
从信息论上说,一个标准的签密方案可随机数部分重用的安全条件可描述为:已知发送方的公私钥对、一
个接收方公钥以及一个随机消息经该公钥加密生成的签密文,对于任意给定的另一个接收方公私钥对,可以构
造出任意其他消息的有效签密文,要求所构造的签密文与给定的签密密文重用部分相同的随机数.
定义 10(可再生的签密方案). 给定一个定义 1 的标准签密方案=(Gen,Kgen,SC,DSC)和一个多项式 n(),设
k 为安全参数,接收方个数为自然数 N=n(k).如果存在一个多项式时间再生算法 RP,输入一个发送方的私钥 sk S 、
一个接收方的公钥 pk R 、一个签密文 c(某个随机消息 m 经该公钥 pk R 生成的签密)、另一个随机消息 m、另一
个接收方的公私钥对(pk R ,sk R )以及部分随机数集合 r  R , 输出一个合法的签密文 c,则称签密方案是可再生的.
我们可以用以下实验来描述.
 Exp rep ,RP ().k

(1) parm Rnd Gen(k),(pk S ,sk S )(pk R ,sk R ) Rnd Kgen(parm),m Rnd Mspc(parm);
,
(2) r  (, ,..., )r r 2 r  d Rnd CoinsRu SC ( parm sk S );
1
(3) 对 i=1,2,…,N,选择 r   R (r (d  1) i ,r (d  2) i ,...,r i w )  Rnd CoinsNRu SC (parm sk pk R ) 令 r  R ( , )r r   R ( , ,..., ,r r 2 r d
,
,
S
1
,
r (d  1) i ,...,r i w ), 计算 c  SC (sk pk R , , , );m r r  R
S
(4) (pk R ,sk R ) Rnd Kgen(parm),m Rnd Mspc(parm);
,
,
(5) r  R Rnd CoinsNRu SC ( parm sk pk R  );
S
,
(6) 如果 SC (sk pk R ,m , ,r r  R )  RP (sk pk R , ,c pk R ,sk R ,m r  ,  R ), 返回 1;否则,返回 0.
,
S
S
如果存在一个概率多项式时间再生算法 RP 使上述实验以 1 的概率返回 1,则称签密方案是可再生的.特别
地,当 r  时,称是随机数全重用可再生的签密方案;当 r  r R 且 r   时,称是随机数部分重用可再生的



R
R
R
签密方案.
3.2 可再生性定理
如果一个标准签密方案是随机数部分重用可再生的,且是 IND-CPA(IND-CCA2)和 euf-CMA 安全的,那么
它也是 PRRU-IND-CPA(PRRU-IND-CCA2)和 PRRU-euf-CMA 安全的.下面我们用随机数部分重用可再生性定
理来描述.
定理 1(可再生保密安全性). 给定一个定义 1 的标准签密方案=(Gen,Kgen,SC,DSC)和一个多项式 n(),设 k
为安全参数,接收方个数为自然数 N=n(k),设 M=(Gen,Kgen,MSC,DSC)是相应的 PRRU-MM-MR 签密方案(见定
义 5).如果是可再生的签密方案(见定义 10),那么对于任意多项式时间敌手 MA,存在着一个多项式时间敌手 A,
对于任意安全参数 k 满足:
-attk
Adv M  N -MR ,MA ()k ≤ n ()k  Adv attk ,A ().k

证明:从保密性角度看,由于 IND-CCA2 是目前签密方案中最强的安全概念,一个 IND-CCA2 安全的签密方
案意味着也同时满足 IND-CPA 安全性.因此,定理证明时我们只考虑 IND-CCA2 安全性情况,IND-CPA 安全情
况也可同理得证.
设 MA 是一个多项式时间三阶敌手,可以攻击 PRRU-MM-MR 签密方案 M的 IND-CCA2 安全性,我们构造
一个三阶敌手 A,他将 MA 作为一个子过程调用(利用 MA 的知识)来攻击相应的标准签密方案的 IND-CCA2