一种匿名的公钥叛逆者追踪方案

韩露露，何少芳，贺雅楠，李　春，伍晨迪

(湖南农业大学理学院，湖南 长沙 410128)



一种匿名的公钥叛逆者追踪方案

韩露露，何少芳*，贺雅楠，李春，伍晨迪

(湖南农业大学理学院，湖南 长沙 410128)

针对离散对数困难问题，提出一种匿名的公钥叛逆者追踪方案.该方案通过多项式与过滤函数来构建，能够在不更新其他合法用户私钥的前提下，实现完全撤销多个叛逆者或者完全恢复已撤销用户.当缴获盗版解码器时，只需通过一次输入输出即可确定叛逆者.由性能分析可知，该方案不仅具有用户的匿名安全性、不可否认性、完全撤销与恢复以及黑盒追踪的特点，还满足完全抗共谋性与抗线性组合攻击.

离散对数问题；叛逆者追踪；完全撤销性；完全可恢复性

加密数据(如付费电视系统、网上金融信息广播、在线数据库等)的安全分发是现代信息社会的一个重要问题.数据提供商DS通过广播信道向授权用户提供加密信息.授权用户先用私钥将加密数据包头中的会话密钥恢复,再利用得到的会议密钥解密数据.如果恶意的授权用户将自己的密钥泄露给别的非法用户使用,或者某些授权用户合谋制造出密钥给非法用户使用,那么这些恶意的授权用户就称为叛逆者,而非法用户称为盗版者,通过盗版者的解码器分析出叛逆者的工作称为叛逆者追踪.在这种应用场合,叛逆者追踪作为保障数据安全分发并保护数据提供商合法权益的手段,成为当前研究的热点[1].

叛逆者追踪的概念首先由Chor等人[2]提出，之后许多叛逆者追踪方案相继被提出来.从密码学角度来看，叛逆者追踪方案在加解密过程中可以运用多种加密算法.Boneh和Franklin[3]首次提出公钥叛逆者追踪方案,它解决了对称方案中存在的问题，但其实现效率不高.此后，设计以公钥为基础的叛逆者追踪方案成为研究的主要方向，各种以不同公钥加密体制为基础的叛逆者追踪方案被提了出来.文献[4]提出门限值为k的抗共谋方案，而文献[5]、[6]、[7]提出了具有完全抗共谋的叛逆者追踪方案，也就是说它不存在门限值的限制，但不能实现撤销性.文献[8]对文献[9]进行改进，提出了具有完全抗共谋性、完全撤销性和完全可恢复性的叛逆者追踪方案.文献[10]、[11]还分别提出了基于随机序列的公钥叛逆者追踪方案和基于EIGamal加密算法的匿名叛逆者追踪方案，它们都具有较好的安全性.

现有的叛逆者追踪方案重点研究抗共谋、撤销性、追踪性、安全性等多个方面，但是缺少对用户隐私性保护的考虑.保护用户隐私和叛逆者追踪不矛盾.事实上，平衡数字内容价值链中普通合法用户隐私性和盗版者的可追踪性是数字版权保护机制中应该考虑的另一个重要方面.受文献[8，9，12]的启发，本文基于离散对数问题以及利用类EIGamal加密体制提出一种匿名的公钥叛逆者追踪方案.该方案在没有可信第三方的参与下实现用户的身份验证与追踪，不仅具有用户的匿名安全性、不可否认性、防诬陷、可完全撤销与恢复、黑盒追踪等特点，还满足完全抗共谋性与抗线性组合攻击.

1　方案介绍

设p是一个大素数，q也是一个素数且满足q|p-1,q>n, 其中n为用户数目，g是Zq上的一个生成元.这样在p中计算以g为底的离散对数被认为是困难问题，其中p予以公开.

基于离散对数问题的叛逆者追踪方案利用多项式与过滤函数来构建.注册用户必须通过匿名验证以后才能得到私钥.当发现叛逆者或需要恢复已撤销用户时，它能够在不更新合法用户私钥的前提下，实现安全撤销多个叛逆者或者完全恢复已撤销用户.

1.1系统初始化

数据提供商在Zq上随机选择一个k次多项式f(x)=a0+a1x+…+akxk,k>N,N为最大用户数.称f(x)上对应的一个点(i,f(i)),i∈Zq{0}为一个份额.设Φ={(i‖f(i))|i∈Zq{0}}为已注册用户集合，且Φ满足对任意i≠j有f(i)≠f(j).除了另有说明，本文的所有算术运算都在Zq上.

1.2用户注册

当一个新用户ui申请注册时，DS随机选择一个没有被使用的份额(i,f(i))传送给用户ui作为他拥有的份额，并记录text=i‖f(i)‖ui，同时更新已注册用户集.用户ui保存拥有份额(i,f(i)).

1.3用户匿名验证

当注册用户ui(拥有份额(i,f(i)))欲从DS处购买信息产品时,任选Ai∈RZq{0} 并执行以下步骤进行匿名验证[10]:

Step1 用户ui计算gAi,gAif(i)，将订购单gAi‖gAif(i)发送给DS.

rj′*rj′-1= 1mod(q-1),rj*rj-1= 1mod(q-1)

(1)

并验证它们是否相等， 这是因为

((T1′)f2(i))r1′-1= (((gAi f(i))r1′)f2(i))r1′-1= gAi f3(i)(K(q-1) + 1)= gAi f3(i)K(q-1)*gAi f3(i)= gAi f3(i)

(2)

同理有：

(3)

若所有提取的部分通过相等的验证，则执行下一节的操作.

Step5 DS任选Ω={x1,x2,…,xk}，满足(xj,f(xj))∉Φ,j=1,2,…,k，利用接收到的gAi‖gAif(i)计算gAif(xj),j=1,2,…,k，发送x1‖gAif(x1)‖x2‖gAif(x2)‖…‖xk‖gAif(xk)‖gAif(i)给用户ui.

Step6 用户ui利用收到的k组数据(xj,gAif(xj)),j=1,2,…,k以及(i,gAif(i))，由Lagrange插值法得到

(4)

用户保存ki=gAif(0)并将其发送给DS.

Step7 DS计算gAif(0)=gAia0并将它与用户发来的gAif(0)比较，若相等则通过验证，DS更新text=i‖f(i)‖ui‖ki，若不相等则订购终止.

1.4密钥分发

y0=(gA)a0,y1=(gA)a1,…,yk=(gA)ak

(5)

公开pub={p,g,y0,…,yk}作为公钥，用户ui的私钥为(i,f(i),ki).

1.5加密算法

(6)

然后计算

C2=(M(y0)α,(y1)α,…,(yk)α)

(7)

发送广播消息(C1(x),C2).

1.6解密算法

(8)

(M×(y0)α×(y1)αi×…×(yk)αik)/(gAα)f(i)

=(M×(gAa0)α×(gAa1)αi×…×(gAak)αik)/(gAα)f(i)

=(M×(gAα)f(i))/(gAα)f(i)=M

(9)

1.7追踪算法

(10)

向解码器输入(C1(x),C2)，则解码器利用其解密密钥(i,f(i),ki)按照解密过程计算:

(11)

M'=(M×(y0)2α×(y1)2αi×…×(yk)2αik)/(gAα)f(i)

=(M×(gAa0)2α×(gAa1)2αi×…×(gAak)2αik)/(gAα)f(i)

=(M×(gA2α)f(i))/(gAα)f(i)=M(gAα)f(i)

(12)

DS根据输出的M'，计算M'×M-1=M(gAα)f(i)×M-1=(gAα)f(i)，对照保存的记录text，找到与之相对应的{i‖f(i)‖ui‖ki}，则可确定用户ui是叛逆者，此时该用户是不可否认的.

1.8撤销算法

(13)

然后计算

(14)

1.9恢复算法

2　性能分析

2.1用户匿名安全与不可否认性

DS要从订购单gAi‖gAif(i)中获取代表用户身份的的信息f(i)，其困难性相当于求解离散对数困难问题，因此用户的匿名安全是有保障的.正因为DS无法确定已订购的用户身份f(i)，也就无法陷害诚实用户，因此该方案又具有防诬陷性.此外，由于用户在订购信息产品时，需要随机选取Ai∈RZqackslash 0 ，因此DS要从已经保存的订购单中识别出属于同一用户的不同订购单，其困难性同样相当于求解离散对数问题.另一方面,由于Ai是用户ui私自选择的，且ki=gAif(0)为其私钥,一旦用户被判定为叛逆者则不可否认.

2.2完全抗共谋性

根据Lagrange插值公式，一个t阶多项式f(x)能利用t+1或大于t个的(xi,f(xi))重构.但在本文方案中，由于k次多项式f(x)=a0+a1x+…+akxk,k>N,N为最大用户数，即使所有用户合谋也不能重构f(x)，因此它具有完全抗共谋性.

2.3完全撤销性与完全恢复性

由加密算法与解密算法可知，若某些用户已通过撤销算法被撤销，则其ki不再包含于广播消息的C1(x)中，被撤销用户无法利用其密钥正确恢复明文，而其他用户利用原有私钥即可恢复明文.此外，由撤销算法可知，它不存在撤销门限，可一次完成对所有叛逆者的撤销，具有完全撤销性.另一方面，若要恢复被撤销用户，由恢复算法可知，只须将他们的kj加入C1(x)即可，其它用户不需更新私钥，因此该方案也具有完全恢复性.

2.4抗线性组合(凸组合)攻击

设f(i1),f(i2),…,f(ik)是k个用户的私钥，w=[u,w0,w1,…,wk]是向量v1,v2…,vk的任一线性组合，其中

v1=[f(i1),1,i1,i2,…,ik]

…

(15)

2.5黑盒追踪性

由追踪算法可知，当收缴到一个盗版解码器，不用打开它，只需通过一次输入输出即可确定出该盗版解码器所对应的叛逆者，即它具有黑盒追踪性.

3　总结

本文基于离散对数问题，提出一种匿名的公钥叛逆者追踪方案.该方案在没有可信第三方的参与下，实现了用户的身份验证与追踪.它利用多项式与过滤函数构建叛逆者追踪方案，当发现叛逆者或需要恢复已撤销用户时，它能够在不更新其他用户私钥的前提下，实现安全撤销多个叛逆者或者完全恢复已撤销用户.当缴获盗版解码器时，不用打开它，只要通过一次输入输出即可确定叛逆者.通过性能分析可知，该方案不仅具有用户匿名安全性与不可否认性，还具有完全可撤销与恢复性、黑盒追踪性，且还满足完全抗共谋性与抗线性组合攻击.

[1]张学军,周利华,王育民.一种抗共谋的非对称公钥叛逆者追踪方案[J].计算机科学,2006,(8):118-120.

[2]Chor B, Fiat A, Naor M. Tracing traitors[J]. IEEE Transactions on Information Theory, 1994, (6):257-270.

[3]Boneh D, Franklin F. An efficient public key traitor tracing scheme[A]. Proc. of CRYPTO’99, LNCS[C]. Springer-Verlag, 1999.

[4]Yuji W, Goichiro H, Hideki I. Efficient public key traitor tracing scheme [A]. Proc of CT-RSA 2001 [C].Berlin: Springer, 2001.

[5]Boneh D, Sahai A, Waters B. Ful collusion resistant traitor tracing with short ciphertexts and private keys[A].Proc of the 13thACM Conf on Computer and Communications Security[C]. New York: ACM, 2006.

[6]王青龙,杨波,韩臻,等.免共谋公钥叛逆者追踪方案[J].通信学报,2006,(12):6-9.

[7]Ya-Li Qi. An improved traitors tracing scheme against convex combination attack[A]. WISM 2011, CCIS 238[C]. Springer-Verlag, 2011.

[8]王晓明,姚国祥,廖志委.一个叛逆者追踪方案分析和改进[J].计算机研究与发展,2013,(10)：2092-2099.

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

[10]何少芳.一种基于随机序列的公钥叛逆者追踪方案[J]. 电子科技, 2016, (4):180-182.

[11]何少芳. 基于EIGamal加密算法的匿名叛逆者追踪方案[J]. 电子科技, 2016,(6):44-46.

[12]王青龙,杨波. 一种无第三方参与的匿名指纹方案[J].电子学报, 2005,(11):2063-2065.

(责任编校：晴川)

An Anonymous Public Key Traitor Tracing Scheme

HAN Lulu, HE Shaofang*, HE Yanan, LI Chun, WU Chendi

(College of Science, Hunan Agricultural University, Changsha Hunan 410128, China)

Based on the discrete log representation problem, an anonymous public key traitor tracing scheme is presented in this paper. This scheme employs the polynomial function and the filter function as the basic means of constructing the traitor tracing procedures, and it can safely revoke or recover the private keys of traitors without updating the private keys of other receivers. When a pirate decoder is confiscated, it only requires single input and output to decide the traitor. The analysis of performance shows that the proposed scheme has many advantages, such as anonymous safety of users, non-repudiation, full revocability, black-box traceability and full recoverability. Moreover, the scheme is able to achieve full collusion resistance and anti-linear-attack.

discrete log representation problem; traitor tracing; full revocability; full recoverability.

2016-09-11

湖南农业大学大学生创新性实验计划项目(批准号：XCX1572).

韩露露(1995— )，女，湖南长沙人，湖南农业大学理学院学生.研究方向：统计学.

TP393

A

1008-4681(2016)05-0062-04