基于广播加密的多策略非对称叛逆者追踪方案

康桂花

(成都东软学院，成都，611844)

基于广播加密的多策略非对称叛逆者追踪方案

康桂花

(成都东软学院，成都，611844)

双线性映射叛逆者追踪方案不能抵抗叛逆者攻击，且计算量与用户数量相关，计算效率很低。为了减少计算量、存储量和通信量，提高安全性能，基于离散对数难题，提出多策略、多服务、非对称公钥叛逆者追踪方案，进行了安全性证明和效率分析。该方案通过改变门限值t实现了多策略广播，可灵活运用于不同的网络广播领域。分析表明，方案具有更高的计算效率和更短的密文长度，同时该方案被证明可实现面向多服务、抗共谋性、完全撤销性、完全可恢复性和黑盒追踪性。

叛逆者追踪;安全性分析;多策略;面向多服务;非对称公钥

0 引 言

随着计算机技术、数据通信技术和互联网的快速发展，社会对通信网络的依赖度越来越大，通过互联网提供的服务也越来越多。大部分网络应用和服务都是通过广播方式实现，如付费电视、金融信息服务、卫星通信、各行业内敏感数据库服务，比如银行内部的客户信用卡信息等。为了防止非授权用户非法窃取信息或得到服务，数据提供商(data supplier, DS)加密通过网络广播的消息，并将解密密钥提供给合法的授权用户。个别合法用户或合法用户们合谋(称为叛逆者)计算出新解密钥，或者将自己的解密钥，出售给非授权用户(称为盗版者)以获取利益。针对这种盗版行为，Chor等人[1]提出了叛逆者追踪的概念：通过分析盗版者的解码器追踪到至少一个叛逆者。叛逆者追踪可以有效打击盗版行为，极大地保护数据提供商的经济利益。

自Chor后，叛逆者追踪得到了更多学者的研究。其中具有风向标意义的是Boneh等人提出的公钥叛逆者追踪方案[2]，因为方案中DS发送的广播分组长度与用户数量无关。此后各种基于不同公钥密码体制的叛逆者方案被相继提了出来[3-14]。但是这些方案绝大多数都不能同时满足完全抗共谋性、黑盒追踪性、完全撤消性、完全可恢复性，而且其中大多数是基于双线性映射的[2-6,10,13-14]。相较与其他计算，双线性映射所需的计算量是比较大的(据统计，一个对运算大约相当于8个有限域上模幂运算的计算量[15])，而且这些方案中绝大多数都存在着计算量、密文长度随着用户数量增加而增加的缺陷。相较而言，基于大整数分解问题的叛逆者追踪方案[7-9,11]还比较少。文献[7-8]已经被证明是不安全的，文献[9]虽然可以实现完全抗共谋性，但不能实现可撤销性。王云等[10]于2012年提出了一个基于身份和双线性映射的、安全性基于有限域上离散对数问题和判定性问题的方案，但仍然无法克服一般基于身份密码体制方案的固有缺陷。张学军等[11]于2008年提出一个基于大整数分解难题的面向多服务的方案，该方案声称满足完全抗共谋性，且密文长度、密钥长度与用户数量无关，但2013年文献[12]给出了针对该方案的一种共谋攻击，证明了3个或3个以上合法用户可以合谋生成一个新的解密钥并逃避追踪。2009年王青龙等提出了一个基于双线性映射的具有完全抗共谋性、完全撤销性、完全恢复性的叛逆者追踪方案[13]，但被证明实际上该方案不能实现完全撤销性，即被撤销的用户仍然能够用原来的解密钥正确解密出密文[14]。

2013年，王晓明等[14]提出了新的基于双线性映射的叛逆者追踪方案(以下简称WXM方案)，该方案使用多项式和过滤函数构建，并具有完全抗共谋性、完全可恢复性、黑盒追踪性和完全撤销性。针对该方案提出一种攻击方法，使得任何一个叛逆者可以通过自己的解密钥构造出新的解码器提供给盗版者，但数据提供商无法通过追踪算法找出叛逆者，从而逃避追踪。

一般来说，付费电视、网络服务、行业内部数据库等基于广播的应用系统，其用户数量非常巨大，多则几百万人，少则几万人。但是，绝大多数典型追踪方案，或者公钥、密文长度与用户数成正比，或者构造多项式的次数≥用户数，这使得方案的计算量非常巨大，不能满足实际需求。

基于如上所述的原因，并针对文献[13-14]的安全性缺陷和大多数方案计算量过大的问题，本文提出了一个基于离散对数问题的、非对称公钥的、面向多服务、多策略的叛逆者追踪方案，进行了安全性分析和效率对比。与大多数方案相比，本文方案的安全性能和计算效率更高，有以下突出的优点：①多策略：通过改变门限值实现了多策略广播，可灵活应用于各种网络广播领域；②公钥长度、用户解密钥长度、广播密文长度均与用户数量无关；③方案采用二分法实现黑盒追踪；④完全抗共谋性：无论多少数量的用户共谋均不能构造出新的解密钥；⑤完全撤销性：只需要修改广播密文，不需要更新其他合法用户的解密钥，就可方便地撤销叛逆者用户，或者用户取消订阅服务；⑥完全可恢复性：对于已撤销用户，或取消订阅服务的用户，不需要更新其密钥就可恢复其解密能力或恢复订阅。在大多数应用场景中(如付费电视)，性质⑤和⑥非常实用。

1 针对WXM方案的安全性攻击

1.1 WXM方案

WXM方案的安全性基于离散对数难题和判定Diffie-Hellman难题[14]。方案简述如下。

1)系统设置。

设p,q是2个大素数，q|(p-1)，G1为q阶加法循环群，G为p-1阶乘法循环群，G2是G中阶为q的循环子群，P是G1上的本原元。e:G1×G1→G2是G1到G2的双线性映射，记g=e(P,P)。

DS随机选择α,X={x1,x2,…,xn}(n是已注册用户数,n

2)用户注册。

设用户Ui申请加入系统。DS为Ui任选一个未被分配的xi，计算

(1)

(xi,ki)就是Ui的解密钥，DS将其发送给Ui。

DS再随机选择一个多项式

(2)

DS利用(xi,f(xi))和(wi,f′(wi))(i=1,2,…,t)构造多项式

(3)

(3)式中，aij是fi(x)的系数。DS记录Ui和e(P,P)fi(x0)作为用户Ui的注册信息存放在身份数据库中。如果e(P,P)fi(x0)与某个已注册用户的对应记录相等则重新选择f′(x)。

3)加密算法。

c2=rP,c3=Me(P,rf(x0)P)

(4)

然后DS广播(c1(x),c2,c3)。

4)解密算法。

用户Ui接收到广播密文后，向解码器输入(c1(x),c2,c3)和公钥pub。

解码器使用解密钥(xi,ki)计算

c1(ki)=rα-1

(5)

记Lj为用{xi,w1,w2,…,wt}计算出f(x0)时点wj的Lagrange插值系数，则

(6)

(7)

(8)

5)追踪算法。

当DS收缴到一个盗版解码器后，设其解密钥为(xi,ki)，DS任选(xr,Mr,r)并计算

(9)

c2=rP,c3=Mre(P,rf(xr)P)

(10)

然后向盗版解码器输入(c1(x),c2,c3)和{x0,(wi,e(P,P)αf′(wi))(i=1,2,…,t)}，则解码器进行以下计算并输出M′

c1(ki)=rα-1，

(11)

(12)

(13)

(14)

DS根据M′计算

e(P,P)fi(x0)=[M′-1Mre(P,rf(xr)P)]r-1

(15)

将计算出的e(P,P)fi(x0)与数据库中记录相比较，找到对应的Ui，则Ui就是叛逆者。

6)撤销算法。

如果要撤销某些用户，DS只需要在广播消息时，将过滤函数c1(x)中与这些撤销用户Ui相对应的(x-ki)从乘积项中移除即可。

7)恢复算法。

如果需要恢复某些已撤销用户，DS只需要做撤销算法的逆操作，即将欲恢复用户Ui对应的(x-ki)再加入到c1(x)的乘积项中。

1.2 针对WXM方案的安全性攻击

WXM方案[14]声称至少可以追踪到一个叛逆者。本文给出一种攻击方法，可以使其无法追踪到叛逆者。

设用户Ui的解密钥为(xi,ki)。Ui进行如下操作。

1)利用某次接收到的广播消息(c1(x),c2,c3)，结合解密钥ki可以算出：rα-1=c1(ki)

通过比较多项式c1(x)的系数，可以得到其最高次项系数λ，通过把x=0代入多项式可以求出

(16)

2)重复自己接收到广播消息(c1(x),c2,c3)的解密过程，可以算出Lj，bi和

e(P,rf(x0)P)=e(P,kic2)bi=grf(x0)

(17)

因此：gαf(x0)=(grf(x0))(rα-1)-1modp

(18)

(19)

(20)

3.2)同正常解码器方法计算bi

(21)

(22)

3.3)修改解密密文计算公式

(23)

1.3 对WXM方案的分析

WXM方案同许多典型方案一样，存在相同效率上的缺陷。

2 新的多策略叛逆者追踪方案

针对目前大多数方案的计算量和通信量过大，计算效率低下的缺陷，提出多策略、多服务、非对称公钥的追踪方案。

现实社会中，不同广播系统的用户数量和用户重要性相差很大，需要区别对待。有些付费电视系统，用户量数以万计，有些广播系统、收费查询系统的安全性要求特别高。当用户数量特别大时，可以把他们按照地理位置再细分为若干个广播子系统，比如北京市的收费电视，可以再按宣武区、朝阳区等进一步划分为多个子区，每个子区分别发送不同广播密文的电视广播，而对安全性要求特别高的系统(如军事、金融系统)，则可以通过加大门限值，增大密钥长度、广播密文长度等方法，提供更高的安全保障。也就是说，不同广播系统需要采取不同的广播策略。

现有的许多方案都是对称公钥的，即DS知道被授权用户的解密钥，这样一来，即使发现叛逆者，DS也无法提供有效证据进行控诉，证明叛逆行为不是自己所为。本文利用不经意多项式估值协议(oblivious polynomial evaluation protocol, OPE)，提出一种非对称公钥方案，即用户的解密钥只有自己一方知道，从而方案具有不可否认性，使追踪更具有效力。

方案的参与者由三方组成：系统管理者SM、数据提供者DS、用户。方案由以下几个部分组成。

2.1 系统初始化

设广播系统将用户按区域划分为e个区(根据实际需要确定e，比如e=10)，每区采用一个广播策略，不同区域的广播策略是不同的，或者系统按照安全性要求的高低采用e个广播策略中的某一个策略，并定期变换策略。t1,t2,…,te是不同策略时的门限值，不妨设t1

系统管理者SM确定系统参数：

a0≡d1modq1,a0≡d2modq2, … ,

a0≡demodqe

4)SM构造te次多项式

f(x)=a0+a1x+…+atextemodQ

再计算每个策略l对应的tl次多项式

fl(x)=f(x)modql

5)在执行策略l的子系统，SM公布该策略的公钥(tl为策略l的门限)

下面以策略l为例说明方案。

2.2 服务注册

DS为服务W向SM注册：设W的说明文字为IDW，DS计算bW=h(IDW)作为对服务W的授权值并秘密发送给SM，bW必须由SM秘密保存，不能泄露。SM生成多项式Fl,W(x,y)=fl(x) +bWy。

2.3 用户注册

2.4 用户订阅服务

Ui向SM订阅服务W：Ui和SM执行OPE协议，得到自己订阅服务W的服务解密钥Ki,W=Fl,W(xi,σi)=fl(xi)+bWσi(modql)。因为执行OPE协议，SM得不到σi和Ki,W的任何信息。

当用户首次加入系统时，必须先注册再订阅服务，当他已订阅了一项服务再订阅另一项服务时，就不需再注册，只需执行2.4节算法即可。

2.5 广播加密

(24)

2.6 解密

1)用户Ui利用自己的解密钥(xi,σi,Ki,W)和数据头，先计算出

(25)

(26)

(26)式中：λj,λi是Lagrange插值系数。

易证，对于给定消息头和密文，任何合法的授权用户都可以正确解密出密文。

2.7 黑盒追踪

可以采用二分法确定叛逆者或叛逆者集合，且是黑盒追踪。

先将用户划分为若干个用户子集，每个子集的用户数≤门限tl，依次对用户子集进行追踪。不妨设被怀疑的用户子集U={U1,U2,…,Um1}(m1≤tl)。

2)将输入盗版解码器，其中，E(.)是对称加密算法，Es(M)是用密钥s对消息M进行加密。

3)如果输出的是消息M，则U中没有叛逆者，否则U中有叛逆者，这时可以将U按二分法划分为2个子集后进一步追查，直到找出叛逆者或叛逆者集合为止。

由追踪算法可知，本方案的门限值tl可以远远小于用户数，加上将用户分区，每区采用不同策略，就可以使广播多项式fl(x)的次数维持在一个相当小的整数值，从而大大减少了计算量，提高了效率。

2.8 用户撤销

如果要撤销某些用户的接收权，DS只需要将这些用户的身份信息xi加入到广播点集Y中，即

2.9 用户取消订阅

如果用户Ui要取消对服务W的订阅，类似于用户撤销算法，DS将用户的身份信息xi添加到广播点集Y中，用户就无法接收服务W的广播了。

2.10 恢复用户和用户恢复订阅

2.11 叛逆者人数超过门限时的撤销

当叛逆者人数超过门限值时，DS只需要重新选择一个门限值超过叛逆者人数的策略l′，即选择策略l′使其满足tl′>叛逆者人数，再按正常方式广播。此时SM要重新计算、公布公钥PK。

由2.8,2.9,2.10,2.11节可知，方案具有完全可恢复性、完全撤销性。

3 安全性分析和效率对比

3.1 安全性分析

定理1(安全性) 在离散对数困难问题假设下，方案能被攻击者正确解密的概率为(1/p+1/q)，是可以忽略的。方案是安全的。

证明假设非合法用户的攻击者，能从消息头解密出sW。设他的解密钥为(z1,z2,z3)，则有

z3=fl(z1) +bWz2(modql)

(27)

定理2(抗共谋性) 共谋用户数为k(k≥1)的某些合法用户通过共谋构造出一个新解密钥在计算上是不可行的，其计算复杂度等价于求解离散对数问题。方案具有完全抗共谋性。

证明先考虑k=1的情况。

假设有2个用户Ui,Uj合谋构造新解密钥。一方面，由解密钥等式构成的方程组为

有2个方程3个变量，无法解方程组从而求出fl(xi),fl(xj)。另一方面，如上所述，由公钥PK或广播密文构造新解密钥，等价于求解离散对数问题，在计算上是不可行的。

定理3黑盒追踪算法可以追踪到任何盗版者。

反之，如果U中没有叛逆者，盗版解码器的解密钥与U的份额{x1,x2,…,xm1}无关，那么就算测试消息头C中选用了点x1,x2,…,xm1，依然可以正确解密出密文M。当正确解密出M时，可以证明U中没有叛逆者。

在确定叛逆者所在子集后，运用二分法进一步缩小范围，可找出叛逆者集合。二分法的计算次数为lbm1(m1是集合U中元素的个数)，因此查找速度是非常快的。

3.2 效率对比

本文方案是多策略的，即在不同广播系统应用领域或不同用户区域，选用不同的门限值tl、素数ql、生成元gl。相比于一般方案，本方案的多项式次数tl(即门限值)是一个固定的常量，可以远远小于用户数n，且本文方案不含对运算。反观其他典型方案，包含O(n)个对运算，多项式的次数也为n。如果用户数n=10 000，则包含约10 000个对运算，多项式的次数为10 000次，计算效率非常低下。因此，本文方案明显地降低了计算量、存储量、通信量，大大提高了效率。

表1、表2列出了本文方案和其他3种典型方案的计算量和性能对比。表1只统计了加密和解密过程中(其他过程不经常发生)的对运算、模幂运算的次数，因为和它们相比，其他运算的耗时量可忽略不计。同等安全级别下，双线性对运算相对于其他运算(如模幂运算)是最耗时的，1个对运算约等于8个模幂运算[15]，因此应当尽量减少对运算的个数。设Pa表示1次对运算，E表示1次模幂运算，n，N，s分别表示用户数、最大用户数、大于N的一个整数，t,m,k为与用户数无关的整数，t是门限值，Y=pq为RSA中的模。|M|为整数M的比特位长度，len(G)为群G中元素的比特位长度。

由表1可知，由于本文方案没有对运算，其计算量远远小于文献[13-14]方案，略高于文献[11]。除了计算量上的优势，再考虑到密钥长度、广播密文长度、黑盒追踪效率，以及多策略、多服务、非对称密钥、完全可撤销性、完全可恢复性等安全性能，本文方案相比于其他方案都具有明显的优势。

表1 4种方案的计算量

表2 4种方案的性能对比

通过在Visual C++ 6.0中调用OpenSSL 1.0.0密码函数库，可以编程实现对本文方案的仿真实验。

仿真测试平台为Windows7, Intel Core4 CPU 4 GHz, 4 GB内存。不失一般性，设最大用户数N=200,用户数n=100,e=3,t1=5,t2=9,t3=12,s=202,会话密钥sW为128位。方案中的各项数据p,ql,gl,xi,σi,yi,sW等均随机生成。表3给出了方案运行5次的平均运行时间统计。

表3 本文方案主要阶段平均耗时统计(t3=12) (单位：s)

可以看出，方案在初始化阶段耗时较多，在广播加密和解密阶段耗时较少。由于初始化阶段在系统生命周期中只需运行一次，不会影响方案的后期运行效率，此外，其他阶段只在有需要时才运行，平时不会运行。因此表3的仿真结果表明方案是高效可行的。

不考虑其他阶段，只对广播加密、解密2个阶段统计运行时间并求和，本文方案与文献[14]的平均运行时间对比如表4所示(运行5次)。

表4 本文方案与文献[14]平均耗时对比(单位：s)

实验结果表明，相较于文献[14]，本文方案的计算时间显著减少，计算效率大幅提升。另外，从表4可以看出，门限值tl对方案运行时间有一定影响，门限值越大运行时间越长，但增加的运行时间可以接受(特别是CPU运算速度进一步提高的情况下)。在兼顾保障安全性、提高运行效率的情况下，tl的最佳值选取在[7,15]。

4 结束语

本文对WXM方案[14]进行了详细分析，发现该方案存在着无法追踪到叛逆者的安全性缺陷，用户只要对解密钥和解密算法进行简单改造即可逃避追踪，同时该方案和许多典型方案一样，计算量过大，计算效率很低。针对这些问题，本文提出了一个多策略可灵活应用于各种领域、面向多服务、非对称公钥叛逆者追踪方案。方案不仅克服了WXM方案的缺陷，还同时满足完全抗共谋性、黑盒追踪性、完全撤销性和完全可恢复性等安全性要求，采用二分法实现黑盒追踪，并通过非常简单的方法，实现了在撤销用户及恢复用户(或用户撤销及恢复服务)时的公钥、其他合法用户解密钥均不受影响的优点。与大多数方案相比，方案的计算效率更高，更灵活，并可广泛应用在不同领域，例如对计算效率和安全性要求更高的应用场景。

[1] CHOR B, FIAT A, NAOR M. Tracing traitors[C]∥Advances in Cryptology-CRYPT’94, Lecture Notes in Computer Science. Berlin: Springer, 1994, 257-270.

[2] BONEH D, FRANKLIN M. An efficient public key traitor tracing scheme[C] //Proc of CRYPTO’99. Berlin: Springer, 1999: 338-353.

[3] BONEH D, WATERS B. A fully collusion resistant broadcast, trace, and revoke system[C] //Proc of the 13th ACM Conference on Computer and Communications Security. Berlin: Springer, 2006, 211-220.

[4] FURUKAWA J, ATTRAPADUNG N. Fully collusion resistant black box traitor tracing revocable broadcast encryption with short private keys[C] //Proc of the 34th International Colloquium on Automata, Languages and Programming. Berlin: Springer, 2007: 496-508.

[5] GARG S, KUMARASUBRAMANIAN A, SAHAI A, et al. Building efficient fully collusion-resilient traitor tracing and revocation schemes[EB/OL]. [2012-06-01]. http://eprint.iacr.org/2009/532.pdf.

[6] PARK J H, LEE D H. Fully collusion-resistant traitor tracing scheme [EB/OL]. [2010-12-09]. http://protocol.korea.ac.kr/publication/Fully collusion-resistant traitor tracing scheme with shorter ciphertexts.pdf.

[7] 马华,曹正文.基于RSA加密算法的叛逆者追踪方案[J].西安电子科技大学学报,2004,31(4):611-613. MA Hua, CAO Zhengwen. A traitor tracing scheme based on RSA[J]. Journal of Xidian University, 2004, 31(4):611-613.

[8] 冯慧娟,马华,杨波.一种新的基于RSA加密算法的叛逆者追踪方案[J].计算机应用研究,2007,24(5):135-137. FENG Huijuan, MA Hua, YANG Bo. New traitor tracing scheme based on RSA[J]. Application Research of Computers, 2007, 24(5):135-137.

[9] 王青龙,杨波,韩臻，等.免共谋公钥叛逆者追踪方案[J].通信学报,2006, 27(12):6-9 WANG Qinglong, YANG Bo, HAN Zhen, et al. Collusion-free public-key traitor tracing scheme[J]. Journal on Communications, 2006, 27(12):6-9.

[10] 王云,芦殿军,张秉儒.基于身份的公钥叛逆者追踪方案[J].青海师范大学学报：自然科学版，2012(1): 31-35. WANG Yun, LU Dian jun, Zhang bing ru. A traitor tracing scheme based on bilinear map[J]. Journal of Qinghai Normal University：Natural Science, 2012(1): 31-35.

[11] 张学军.新的面向多服务的叛逆者追踪方案[J].电子科技大学学报, 2008, 37(3):404-407. ZHANG Xuejun. A new multi-services oriented traitor tracing scheme[J]. Journal of University of Electrical Science and Technology of China, 2008, 37(3):404-407.

[12] 王青龙,徐丽.两个叛逆者追踪方案的安全性分析[J].计算机工程与科学.2013, 35(6):78-81. WANG Qinglong, XU Li. Security analysis of two traitor tracing schemes[J]. Computer Engineering and Science, 2013, 35(6):78-81.

[13] 王青龙,韩臻,杨波.基于双线性映射的叛逆者追踪方案[J].计算机研究与发展,2009,46(3):384-389.

WANG Qinglong,HAN Zhen,YANG Bo.A traitor tracing scheme based on bilinear map[J].Journal of Computer Research and Development,2009,46(3):384-389.

[14] 王晓明,姚国祥,廖志委.一个叛逆者追踪方案分析和改进[J].计算机研究与发展,2013,50(10):2092-2099. WANG Xiaoming, YAO Guoxiang, LIAO Zhiwei, Cryptanalysis and Modification of a Traitor Tracing Scheme[J]. Journal of Computer Research and Development, 2013, 50(10): 2092-2099.

[15] KAWAHARA Y, TAKAGI T, OKAMOTO E. Efficient implementation of Tate Pairing on a Mobile Phone Using Java[C]∥Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2007: 396-405.

康桂花(1962-)，女，浙江东阳人，副教授，主要研究方向为信息安全、网络协议和计算机应用。E-mail: 841936744@qq.com。

(编辑：张 诚)

A multi-policy asymmetric traitor tracing scheme based on broadcast encryption

KANG Guihua

(Chengdu Neusoft University, Chengdu 611844, P.R. China)

It was found that the scheme could not resist collusion attack and is similar to most schemes, its efficiency is very low because of relating to the quantity of users. In order to improve safety performance and to reduce the amount of computation, storage, communication, based on discrete logarithm problem, a new multi-policy multi-service asymmetric public-key traitor tracing scheme is proposed. The new scheme can be used flexibly in all kinds of domain because multi-policy broadcast has been realized by using different threshold value t. Compared to most typical schemes, the scheme has higher computation efficiency and shorter cipher text length, it also has stronger safety features since multi-service oriented, collusion resistance, full revocation, full recoverability, and black-box traceability can be realized.

traitor tracing; security analysis; multi-policy; multi-service oriented; asymmetric public-key

10.3979/j.issn.1673-825X.2016.06.022

2016-02-18

2016-10-05

康桂花 841936744@qq.com

2015年度电子信息类专业教指委研究课题(2015-Y13)；四川省教育厅2014年度重点科研项目(14ZA0346；SCJG2014-741)；四川省教育厅2013年度科研项目(13ZB0483)

Foundation Items：The Research Project for Electronics and Information of Education Steering Committee (2015-Y13); The Key Research Project of Sichuan Education Department 2014(14ZA0346， SCJG2014-741); The Research Project of Sichuan Iducation Department 2013(132B0483)

TP309

A

1673-825X(2016)06-0883-09