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

3246 Journal of Software 软件学报 Vol.32, No.10, October 2021

-CMA
此, Pr[ForgeExp N M  -MR ,FA ( )1]k   N j 1 Pr[ForgeExp CMA j ( ) 1]k    N Pr[ForgeExp CMA ( )1].k  又由于 FR 把 FA 作为子


,FR
,FR
过程调用,则可以利用 FA 的所有知识,综合可得:
-CMA
-
Adv M  NMR ,FA ( )k ≤ n ()k  Adv CMA ().k □
,FR

由上述定理 2 可知:如果标准签密方案是随机数部分重用可再生的,且是 euf-CMA 安全的,即伪造者 FR
CMA
-
-CMA
的优势 Adv  ,FR ()k 是可以忽略的,那么对应的多接收方签密方案 M中,伪造者 FA 的优势 Adv NMR ,FA ()k ≤
M 
() Adv
nk CMA ( )k 也是可以忽略的.因此,采用定义 5 的方法基于标准方案构造的多接收方签密方案 M也是

,FR
euf-CMA 安全的.
4 基于格的随机数部分重用 MM-MR 签密方案
本节主要采用随机数部分重用理论,证明路秀华等人(LWWD16) [18] 的无陷门格基签密方案=(Gen,Kgen,
SC,DSC)是随机数部分重用可再生的签密方案;然后,基于该方案构造一个 PRRU-MM-MR 签密方案,并证明方
案的安全性,分析方案在系统开销方面的节约.
4.1 格相关知识
4.1.1 格
n
设 n≥k>0,k 维格是 的一个子群,它包含 k 个线性独立的向量组{b 1 ,b 2 ,…,b k }=B 的所有线性组合,例如,
=(B)={Bx|x }.定义格的秩为 det( ( )) B det(B B 如果 q,那么 被称作 q-ary 格.
T
n
k
).
4.1.2 高斯分布
n
定义 11 [19] . 对于任意参数 s>0,我们定义 上中心为 c 的高斯函数:
n
2
2
x , s,c (x)=exp(||xc|| /s ).
当 s 和 c 省略时,表示它们分布取 0 和 1.
n
定义 12 [19] . 对于任意 c 、实数 s>0、n 维格,定义上的离散高斯分布:
x,D ,s,c (x)= s,c (x)/ s,c ().
4.1.3 困难问题
定义 13(LWE 分布) [20] . 设 q 为素数或素数的幂积,n 为正整数,为某一错误分布,向量 s  n q . 定义  q n  q
n
上的 LWE 分布 A s, =(a,b=a,s+e mod q),其中,e, a  是均匀随机选取的.
q
定义 14(判定性 LWE q,n,m, 问题) [20] . 对于 m 次独立抽样 (, )b a i i q n   q , 区分它们是从两个分布中的哪一
n
个抽样的:(1) LWE 分布 A s, ,其中,每次抽样 s  都相同;(2)  n q   q 上的均匀分布.
q
n

定义 15(小整数解 SIS n,q,,m 问题) [20] . 设 A  q nm 是由 m 次独立抽样 a i  组成的矩阵,找到一个非零的
q
m
整数向量 z ,其中,||z||<,满足:
Az  i  a i z  i  0  q .
4.2 LWWD16签密方案介绍
LWWD16 无陷门格基签密方案=(Gen,Kgen,SC,DSC)是一个四元组.
 Gen(系统初始化).
 
k
(1) 设 k 为安全参数,n=2k,参数使得不等式 2  ≥ 128 成立,选取小自然数 M(典型地可取 8)和 d(典型


地可取 24),参数 0<<1,模数 q≥2 ,令=q, u  7 , k U  14 (k  1);
d
(2) D  和 D u 是均值为 0、标准差分别为和 u 的高斯分布;
(3) 选取矩阵 A  Rnd  nk , 选取一个安全的对称加密算法(Enc key (),Dec key ()),其中,key 为对称密钥,密钥
q