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

刘镇  等:安全随机数部分重用及在多接收方签密的应用                                                      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
   266   267   268   269   270   271   272   273   274   275   276