第 5 期吕立群, 等 : 基于多线性映射的低开销 BEPM 方案 627 加密在数字版权管理付费电视卫星通信电视电话会议以及无线传感网络中有着广泛的应用 [2]. 广播加密虽然有效地实现了一对多的加密通信, 但在日常应用中为保护用户的隐私还需要广播者与用户之间进行一对一的通信. 为此, 文献

Size: px

Start display at page:

Download "第 5 期吕立群, 等 : 基于多线性映射的低开销 BEPM 方案 627 加密在数字版权管理付费电视卫星通信电视电话会议以及无线传感网络中有着广泛的应用 [2]. 广播加密虽然有效地实现了一对多的加密通信, 但在日常应用中为保护用户的隐私还需要广播者与用户之间进行一对一的通信. 为此, 文献"

桧斡季
5 years ago
Views:

1 第 35 卷第 5 期 2017 年 9 月应用科学学报 JOURNAL OF APPLIED SCIENCES Electronics and Information Engineering Vol. 35 No. 5 Sept DOI: /j.issn 基于多线性映射的低开销 BEPM 方案吕立群, 杨晓元, 汪晶晶, 程璐武警工程大学电子技术系, 西安摘要 : 针对目前带个人信息的广播加密 (broadcast encryption with personalized message, BEPM) 方案参数过大的问题, 综合利用广播加密与密钥封装方法及多线性映射的特性, 构造了一种低开销的 BEPM 方案, 其密文长度与用户的私钥长度均为常数, 公钥长度仅为 O(lb N). 该方案具有完全抗合谋攻击的特性与标准模型下的选择明文安全性, 且加解密效率高, 可应用于付费电视等诸多领域. 关键词 : 广播加密 ; 低开销 ; 多线性映射中图分类号 :TP309 文章编号 : (2017) Low Overhead Broadcast Encryption with Personalized Message Based on Multilinear Maps LÜ Li-qun, YANG Xiao-yuan, WANG Jing-jing, CHENG Lu Department of Electronic Technology, Engineering College of CAPF, Xi an , China Abstract: Current schemes of broadcast encryption with personalized message (BEPM) require exceedingly large parameters. To deal with the problem, a low-overhead BEPM scheme is constructed by comprehensively using broadcast encryption, key encapsulation, and characteristics of multilinear maps. The ciphertext and private key size of each user are constant, and the public key size is only in the order of O(lb N). The proposed scheme is also fully collusion resistant and can achieve chosen plaintext completely in the standard model. The scheme is safe and effective, and widely applicable in many fields such as pay TV. Keywords: broadcast encryption, low-overhead, multilinear map 广播加密最先由 Fiat 与 Naor 提出, 是一种面向多接收者的秘密通信方式 [1]. 在一般的广播加密系统中, 广播者首先选择一个能解密广播加密信息的授权用户集合 S, 然后对广播加密的对称密钥 K 进行加密得到广播密文头 H dr, 最后根据对称密钥 K 加密待广播的消息并由广播信道发布出去. 只有授权用户集合 S 中的用户才能利用其私钥进行解密得到广播消息. 若所有非授权用户合谋也无法解密广播信息, 则该广播加密系统具有完全抗合谋特性. 广播收稿日期 : ; 修订日期 : 基金项目 : 国家自然科学基金 (No , No ) 资助作者通信 : 杨晓元, 教授, 博导, 研究方向 : 信息安全密码学, xyyangwj@126.com

2 第 5 期吕立群, 等 : 基于多线性映射的低开销 BEPM 方案 627 加密在数字版权管理付费电视卫星通信电视电话会议以及无线传感网络中有着广泛的应用 [2]. 广播加密虽然有效地实现了一对多的加密通信, 但在日常应用中为保护用户的隐私还需要广播者与用户之间进行一对一的通信. 为此, 文献 [3] 提出了可发送私人信息的广播加密方案 (broadcast encryption with personalized message, BEPM). 该方案既能发送广播加密信息以实现一对多的安全通信, 又能向每个用户发送秘密信息而实现用户的隐私保护, 还能有效地应用于付费电视的条件接收系统 (conditional access system, CAS) 中 [4]. 在 CAS 中, 广播者需向用户发送权限控制消息 (entitlement control message, ECM) 与权限管理消息 (entitlement management message, EMM) 两种加密信息. ECM 是指所有付费电视用户接收的共同信息需要利用广播加密进行传输, 而 EMM 是指每个用户的订阅信息需要每个用户的私人密钥进行加密传输. BEPM 同样可应用于医疗系统, 对于病人的病历等敏感信息, 医院需要利用每个病人的私人密钥进行加密传输来保护病人的隐私 ; 对于其他如医生的出诊信息等, 则可用广播的形式发送给所有病人. 此外,BEPM 还广泛应用于无线传感网络中的用户密钥分配网络中文件的访问控制等, 因此构造低开销的 BEPM 方案是有实际应用价值的. Fiat 与 Naor 在 1994 年首先提出了广播加密的概念 [1], 随后一系列广播加密方案被提出 [5-8], 其密文长度均与用户数目呈线性关系. 文献 [9] 利用双线性对构造了 BGW 方案, 其密文长度与用户私钥长度均为常数, 但其公钥长度与用户数目呈线性关系. 为降低公钥开销, 文献 [10] 利用多线性映射构造了低开销的广播加密方案, 在保证其密文与用户私钥长度均为常数的前提下能使公钥长度仅为 O(lb N). 其他如基于身份的广播加密方案可撤销的广播加密方案等也相继被提出 [11-13], 但均不能有效地实现个人秘密信息的传输. 直至 2010 年, 文献 [3] 首次提出了 BEPM 方案才实现了灵活的广播加密方式, 但其公钥长度为 3N+2 个群元素, 其中 N 为广播用户的数目. 文献 [14] 利用多线性映射构造了一个基于身份的 BEPM 方案, 但其公钥长度仍为 O(lb N), 因此设计低开销的 BEPM 方案仍然值得进一步研究. 本文利用多线性映射构造了一种基于身份的 BEPM 方案, 并在标准模型下证明了该方案具有选择明文安全性和完全抗合谋的特性, 其密文与用户的私钥长度均为常数, 公钥长度降至 O(lb N). 1 预备知识 1.1 多线性映射假设存在一个群生成算法以安全参数 λ 和所要生成群的数目 n 为输入, 生成一个群组 {G 1, G 2,, G n }, 每个群的阶为 P, 群 G i 的生成元为 g i. 如果存在这样一个映射集合 {e i,j : G i G j G i+j } 满足以下条件 : 1) 双线性 e ij (g a i, gb j ) = gab i+j, 其中 a, b Z P ; 2) 非退化性对于每个正确的 i 和 j, 都有 e ij (g i, g j ) = g ij ; 3) 可计算性群组里的所有映射均可被有效计算. 那么群组 {G 1, G 2,, G n } 就是一个多线性映射群. 1.2 多线性判定 Diffie-Hellman 假设指数扩展定义 1 令 (p, G 1,, G, e) 为与安全参数 λ 相关的多线性群系统,g i 为群 G i 的生

3 628 应用科学学报第 35 卷成元, 随机选择 α, t Z P, 计算 X i = g α(2i ) 1 (i = 0,, n),v = gl t. 多线性判定 Diffie-Hellman 指数扩展 (multilinear decisional Diffie-Hellman exponent, MDDHE) 假设为给定元组 D = ({X i } i [0,n], V ) 以及 T G, 判断 T = g tα(2n 1) 或 T R G. 算法 A 在安全参数 λ 条件下解决 MDDHE 假设的优势定义为 A MDDHE dv (λ) = P r [A(D, T = g tα(2n 1) ) = 1] P r [A(D, T R G ) = 1] (1) 定义 2 MDDHE 假设指出, 任意的多项式时间算法 A 解决 MDDHE 问题的优势为 A MDDHE dv (λ) < ɛ. 1.3 基于身份的 BEPM 的定义一个基于身份的 BEPM 可由以下 4 个算法来描述 : 1) 系统建立算法 Setup Setup (λ, I) 以安全参数 λ 和用户的身份空间 I 为输入, 输出系统公钥 P K 和主私钥 M SK. 2) 私钥生成算法 KeyGen KeyGen (P K, M K, I) 以系统公钥 P K 主私钥 M SK 用户身份 I I 作为输入, 输出对应的私钥 S KI. 3) 广播加密算法 Enc Enc (P K, S) 以系统公钥 P K 和授权接收者身份集合 S 作为输入, 计算 (H dr, K, K ID ), 其中 K 用来加密广播信息,K I 用来加密个人信息, 最终广播 (H dr, C, C I (I S)) 4) 广播解密算法 Dec Dec (P K, I, S KI, H dr, S) 以系统公钥 P K 用户身份 I 用户私钥 S KI 广播数据头 H dr 以及接收者身份集合 S 作为输入, 若 I S, 则算法输出 (K, K I ), 随后分别利用 K 与 K I 对相应的密文进行解密, 恢复出明文. 基于身份的 BEPM 方案需满足解密一致性, 即对任意 (P K, M SK ) Setup(λ, I) S KI KeyGen(P K, M SK, I) (H dr, K, K I ) Enc(P K, S) 若 I S, 则有 (K, K I ) Dec(P K, I, S KI, H dr, S). 1.4 基于身份的 BEPM 方案模型基于身份的 BEPM 方案主要分为广播信息的加解密与私人信息的加解密两部分, 在一种广播系统中实现一对多的安全通信与用户的隐私保护两种功能, 其模型如图 1 所示. 1.5 基于身份的 BEPM 方案安全模型基于身份的 BEPM 方案的选择明文安全模型可用攻击者 A 与挑战者进行的攻击游戏来描述. 游戏过程由下列 5 个阶段构成 : 1) 初始化阶段攻击者 A 向挑战者输出所需挑战的身份集合 S. 2) 系统建立阶段挑战者运行 (P K, M SK ) Setup(λ, I), 保留主私钥 M SK, 而将公钥 P K 发送给攻击者 A. 3) 私钥生成询问攻击者 A 可对任意的 I / S 进行私钥询问, 挑战者运行 S KI KeyGen(P K, M SK, I) 后将私钥 S KI 发送给攻击者 A. 4) 挑战阶段当攻击者决定结束私钥生成询问阶段时, 挑战者运行 (H dr, K, K I ) Enc(P K, S), 获得挑战广播数据头 H dr 与挑战对称密钥 (K 0, {K I } I S ). 挑战者选取 {b I } I S,

4 第 5 期吕立群, 等 : 基于多线性映射的低开销 BEPM 方案 629 b {0, 1}, 若 b = 0, b I = 0, 则挑战者将 (H dr, K 0, K I ) 发送给攻击者 A; 若 b = 1, b I = 0, 则挑战者随机选取 K 1 与 K I 发送给攻击者 A. 图 1 基于身份的 BEPM 方案模型 Figure 1 Identity-based BEPM scheme model 攻击者 A 可继续进行私钥生成询问, 挑战者运行 S KI KeyGen(P K, M SK, I) 后将私钥 S KI 发送给攻击者 A. 5) 猜测阶段最终攻击者 A 输出猜测 b 和 {b I } I S, 若 b = b, b I = b I, 则表示攻击者 A 赢得游戏. 以 S 表示集合 S 中元素的总数目, 此时攻击者赢得攻击游戏的优势可表示为 A BEPM dv (λ) = P r [(b = b) (b I = b I ) I S ] S (2) 定义 3 对于任意多项式时间的攻击者 A, 可针对给定的基于身份的 BEPM 方案进行上述攻击游戏. 如果攻击者 A 赢得攻击游戏的优势满足 A BEPM dv (λ) ò, 其中 ò 为与安全参数相关的概率可忽略函数, 那么称此系统是 statically CPA 安全的. 2 方案构造新方案构造如下 : 1) 初始化 (n, l) 输入参数生成多线性群组 (G 1,, G l,, G ), 群的阶为 p, 群 G i 的生成元为 g i, 用户身份 I I, 身份长度为 n, 汉明重量为 l, 且 l < n. 随机选取 γ Z P, 计算 Y = g γ n 1 ; 随机选

5 630 应用科学学报第 35 卷取 α Z P, 令 X i = g α(2i ) n 1) 1, i = 0,, n, W = g α(2 ; 随机选择 (b 1,0, b 1,1 ),, (b n,0, b n,1 ) Z 2 P, 令 B i,β =g b i,β 1, 其中 i [1, n], β [0, 1], 故系统公钥 P K ={W, Y, {X i } i {0,,n} (B 1,0, B 1,1 ),, (B n,0, B n,1 )}, 系统主私钥 M SK = {α, γ, (b 1,0, b 1,1 ),, (b n,0, b n,1 )}. 2) 私钥生成 (P K, M SK, I) 输入系统参数和身份信息 I =(i d1,, i dn ), 计算身份 I 对应的私钥为 S KI =(S KI1, S KI2 ), 其中 u = n i=1 2 idi. 设 Z u = gn 1 αu = e(gl αu, g n l 1 ),Z u = gl αu = e(x 1,, X l ). 对于身份 I = (i d1,, i dn ), 其汉明重量为 l, 故仅有 l 个 i di 为 1, 对应 l 个 X i, 可设为 (X 1,, X l ), i [1,n] b i,id i n 1. 于是可得 S KI1 = Zu γ = g γαu n 1,S KI2 = g 3) 加密 (I, P K ) 输入系统参数身份信息 I, 随机选取 t Z P, 计算 K =W t = g tα(2n 1) (3) K I =e(b 1,id1,, B n,idn, g l 1 ) t = g t i [1,n] b i,id i (4) H dr =(C 0, C 1 ) = (g t l, (Y g α(2n 1 u) n 1 ) t ) = (gl t n 1 u), g t(γ+α(2 ) n 1 ) (5) 然后分别利用 K 与 K I 对广播信息与私人信息进行对称加密, 得到对应的密文 C 与 C I. 4) 解密 (P K, I, S KI, C, C I ) 输入系统参数用户私钥密文 H dr 等, 计算 e(z K = u, C 1 ) 1 j+u) e(s KI1 j S,j u gα(2n n 1, C 0 ) (6) K I =e(s KI2, C 0 ) = g t i [1,n] b i,id i (7) 用户分别利用 K 与 K I 对广播加密信息 C 与私人加密信息 C I 进行对称解密, 得到对应的信息. 3 方案分析 3.1 解密一致性本节将通过计算来确保任意授权用户均可以采用上述解密算法解密广播密文而获得消息, 即阐述本方案解密算法的解密一致性 e(z K = u, C 1 ) 1 j+u) e(s KI1 j S,j u gα(2n n 1, C 0 ) = e(g αu l n 1 u), g t(γ+α(2 ) n 1 ) e(g γαu + j S,j u α(2n 1 j+u) n 1, g t l ) (8) = g tα(2n 1) i [1,n] K I = e(s KI2, C 0 ) = e(g b i,id i n 1, gl t ) = g t i [1,n] b i,id i (9)

6 第 5 期吕立群, 等 : 基于多线性映射的低开销 BEPM 方案安全性分析定义 3 若 MDDHE 假设在多线性群系统 (p, G 1,, G, e) 条件下成立, 那么所构造的基于身份的 BEPM 方案就是 statically CPA 安全的. 证明假设存在一个攻击算法 A 可以以不可忽略的优势攻破所构造的 BEPM 方案的 statically CPA 安全性, 则利用 A 可以构造一个仿真算法 B 能够以不可忽略的优势攻破 MDDHE 假设. 算法 A 与 B 的交互如下 : 2) 系统建立由仿真算法 B 构造一个多线性映射系统 (p, G 1,, G, e), 随机选择 α Z P 以及 t Z P, 计算系统公共参数如下 :X i = g1 α2i (i = 0,, n),v = gl t,k = g tα(2n 1) 或 K 为群 G 中的随机元素. A 向 B 提交准备挑战的身份集合 S [1, 2 n 2], 并且 S 中身份的汉明重量均为 l. B 随机选择 r Z P, 计算 Y = gn 1/ r g α(2n 1 u) n 1 = g γ n 1, 由此可得 γ = r α 2n 1 u. u S u S B 同样可计算 W = e(x 0, X 1,, X n, g l 1 ) = g α2n 1, 即随机选择 b 1,, b n, c 1,, c n Z P, 计算 B i,0 = g ci 1, B i,1 = g bi 1, i [1, n], 最后将公钥 P K = {W, Y, {X i } i {0,,n} (B 1,0, B 1,1 ),, (B n,0, B n,1 )} 发送给 A. 2) 私钥生成询问攻击者 A 对任意的汉明重量为 l 的身份 ID / S 进行私钥生成询问, 算法 B 计算 S KID1 =g rαu n 1/ j S g α(2n 1 j+u) n 1 =g γαu n 1,S KID2 =e(b 1,id1,, B j 1,idj 1, B j+1,idj+1,, B n,idn ) bj, 故 S KI = (S KI1, S KI2 ), 最终 B 将身份 I 对应的私钥 S KI 发送给攻击者 A. 3) 挑战阶段攻击者 A 要求对密文进行挑战, 于是 B 计算广播密文头 H dr = (V, e(v, n 1 u) ) g n 1 l ) r ) = (gl t, gt(γ+ u S α(2 n 1 ) 并发送给 A. B 随机选择 b {0, 1}, 若 b = 0, 则 B 计算 K = g tα(2n 1) ; 若 b = 1, 则 B 随机选择一个密钥 K G. 同样 B 为用户 I S 随机 i [1,n] 选择 b I {0, 1}, 若 b I = 0, 则 B 计算 K I = e(v, g b i,id i n 1 ) = g t i [1,n] b i,id i ; 若 b I = 1, 则 B 随机选择一个私人密钥 K I G. 最终 B 回应攻击者 A 的挑战 (H dr, K, {K I } I S ), 显然 B 的回应 (H dr, K, {K I } I S ) 是合法而有效的, 因此 B 完美地仿真了攻击者 A 对 BEPM 方案的攻击. 4) 猜测阶段攻击者 A 输出对 b 的猜测 b 以及对 {b I } I S 的猜测 {b I } I S. 当 {b I } I S = {b I } I S 且 b =b 时, 意味着攻击者 A 赢得了游戏. A win 表示攻击者 A 能够正确猜测 b 与 {b I } I S, B win 可以表示仿真算法 B 能够解决 MDDHE 假设, S 表示集合 S 中所有元素的数量. 因此, 若 K 与 {K I } I S 均正确, 那么事件 B win 发生的概率为 P r [B win ] = P r [B win A win ]P r [A win ] + P r [B win A win ]P r [A win ] = 1 (1/2 1/2 S + ɛ) + 1/2 (1 (1/2 1/2 S + ɛ)) = 1/4 + 1/2 S + 1/2 + ɛ/2 (10) 同样, 若 K 与 {K I } I S 均为群 G 中的随机元素, 即攻击者 A 没有优势 ò 来猜测 b 与 {b I } I S, 那么事件 B win 发生的概率为 P r[b win ] = P r [B win A win ]P r [A win ] + P r [B win A win ]P r [A win ] = 1 (1/2 1/2 S ) + 1/2 (1 (1/2 1/2 S )) = 1/4 + 1/2 S + 1/2 (11) 因此, 仿真算法 B 解决 MDDHE 假设的优势为 P r [B win ] P r[b win ] = ɛ/2. 若攻击算法 A 有不可忽略的优势攻破所构造的 BEPM 方案, 那么仿真算法 B 有不可忽略的优势解决 MDDHE 假设.

7 632 应用科学学报第 35 卷 3.3 抗合谋特性分析在安全性证明过程中, 攻击者可以获取任意用户 u / S 的私钥, 但不能获取所挑战的 H dr 对应的明文. 这意味着任意的合谋者没有正确的私钥, 因此任意数量的合谋者都不能获取正确的信息, 表明新方案具有完全抗合谋的特性. 3.4 效率分析本节将所构造方案与已有的 BEPM 方案进行效率对比来分析新方案的性能, 主要比较公钥长度密文长度主私钥长度用户私钥长度以及加解密时的运算量, 所得结果如表 1 所示. 表 1 与已有方案的性能比较 Table 1 Comparison with the existing scheme performance 方案公钥密文 H dr 主私钥用户私加密解密是否为长度长度长度钥长度运算运算 BEPM 文献 [3] 3N+2 2 N exp 3pair 是文献 [14] N + lbn N exp 3pair 是文献 [10] 2lbN (n+2)exp (n+2)pair 否本文 3lbN+2 2 2lbN exp 3pair 是在表 1 中,N 为广播用户的总数目,pair 和 exp 分别表示加解密时的双线性对运算和指数运算. 因为乘法运算的开销远小于双线性对运算和指数运算的开销, 所以计算开销时忽略乘法运算而仅考虑指数运算与双线性对运算. 由表 1 可以看出 : 与文献 [10] 相比, 新方案在增加少量公私钥长度的基础上实现了 BEPM 方案的功能, 并且降低了广播系统的加密开销与用户的解密开销 ; 与文献 [3,14] 相比, 所构造方案在保证密文长度与用户私钥长度均为常数加解密仅做常数次运算的基础上能使系统的公钥长度分别由 3N+2 与 N + lbn + 2 降低至 3lbN + 2, 系统主私钥长度也由 O(N) 降低至 O(lbN). 4 结语本文构造了一个低开销的基于身份的 BEPM 方案, 并在标准模型下证明了方案的选择明文安全性. 与传统的广播加密方案相比, 该方案不但在较低的公私钥开销情况下实现了私人秘密信息的发送, 而且满足完全抗合谋特性, 是一种安全高效的方案, 适合在实际通信中使用. 参考文献 : [1] Fiat A, Naor M. Broadcast encryption [C]//Annual International Cryptology Conference. Berlin Heidelberg: Springer, 1993: [2] Zou X, Xiang J. Dynamic broadcast encryption scheme with revoking user [J]. Wuhan University Journal of Natural Sciences, 2013, 18(6): [3] Ohtake G, Hanaoka G, Ogawa K. Efficient broadcast encryption with personalized messages [C]//International Conference on Provable Security. Berlin Heidelberg: Springer, 2010: [4] Yoshimura T. Conditional access system for digital broadcasting in Japan [J]. Proceedings of the IEEE, 2006, 94(1): [5] Dodis Y, Fazio N. Public key broadcast encryption for stateless receivers [C]//ACM Workshop on Digital Rights Management. Berlin Heidelberg: Springer, 2002:

8 第 5 期吕立群, 等 : 基于多线性映射的低开销 BEPM 方案 633 [6] Dodis Y, Fazio N. Public key trace and revoke scheme secure against adaptive chosen ciphertext attack [J]. Lecture Notes in Computer Science, 2003, 2567: [7] Goodrich M T, Sun J Z, Tamassia R. Efficient tree-based revocation in groups of low-state devices [C]//Annual International Cryptology Conference. Berlin Heidelberg: Springer, 2004: [8] Halevy D, Shamir A. The LSD broadcast encryption scheme [J]. Lecture Notes in Computer Science, 2002, 2442: [9] Boneh D, Gentry C, Waters B. Collusion resistant broadcast encryption with short ciphertexts and private keys [C]//Annual International Cryptology Conference. Berlin Heidelberg: Springer, 2005: [10] Boneh D, Waters B, Zhandry M. Low overhead broadcast encryption from multilinear maps [C]//International Cryptology Conference. Berlin Heidelberg: Springer, 2014: [11] Delerablée C. Identity-based broadcast encryption with constant size ciphertexts and private keys [C]//International Conference on the Theory and Application of Cryptology and Information Security. Berlin Heidelberg: Springer, 2007: [12] Ren Y, Wang S, Zhang X. Non-interactive dynamic identity-based broadcast encryption without random oracles [C]//International Conference on Information and Communications Security. Berlin Heidelberg: Springer, 2012: [13] Park S, Lee K, Lee D H. New constructions of revocable identity-based encryption from multilinear maps [J]. IEEE Transactions on Information Forensics and Security, 2015, 10(8): [14] Xu K, Liao Y, Qiao L, Liu Z, Yang X. An identity-based (IDB) broadcast encryption scheme with personalized messages (BEPM) [J]. PloS one, 2015, 10(12): e ( 编辑 : 秦巍 )

科研信息化技术与应用,2015, 6 (1) of identity and the framework of identity management, this paper analyses the development trend of Identity Management

科研信息化技术与应用,2015, 6 (1) of identity and the framework of identity management, this paper analyses the development trend of Identity Management 科研信息化技术与应用 2015, 6(1): 41 49 应用 / APPLICATION 身份管理发展趋势和中国科学院身份管理系统薛聪 1,2, 向继 1 1, 高能 1. 中国科学院信息工程研究所信息安全国家重点实验室, 北京 100093 2. 中国科学院大学, 北京