一种基于随机序列的公钥叛逆者追踪方案

何少芳

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



一种基于随机序列的公钥叛逆者追踪方案

何少芳

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

摘要基于离散对数困难问题,利用随机序列提出一种公钥叛逆者追踪方案。该方案采用多项式与过滤函数来构建,当缴获盗版解码器时,只需通过一次输入输出即可确定叛逆者。若需要撤销或恢复多个叛逆者时,其能在不更新其他合法用户私钥的前提下,实现完全撤销多个叛逆者或完全恢复已撤销用户。性能分析证明,该方案不仅存储、计算和通信开销低,还具有完全抗共谋性、完全撤销性与完全恢复性以及黑盒追踪的特点。

关键词离散对数问题;叛逆者追踪;完全撤销性;完全可恢复性;黑盒追踪

为了阻止未授权用户得到网上提供的服务,数据提供商(DS)需要对将要发布的广播信息进行加密处理,即通过广播信道向授权用户提供加密信息,并给每个授权用户分发个人解密密钥。若恶意的授权用户将自身的密钥泄露给别的非法用户使用,或某些授权用户合谋制造出密钥给非法用户使用,则这些恶意的授权用户就称为叛逆者,而非法用户称为盗版者,通过盗版者的解码器分析出叛逆者的工作称为叛逆者追踪[1]。为了解决叛逆者引起的问题,Chor等人[2]在1994年提出了叛逆者追踪的概念,其的基本思想为每个授权用户分发不同的解密密钥,若缴获盗版解码器,则通过输入输出之间的关系来确定解码中包含的解密密钥,从而确定叛逆者。这之后众多叛逆者追踪方案相继被提出。从密码学角度而言,叛逆者追踪方案在加解密过程中可运用多种加密算法。Boneh和Franklin首次提出公钥叛逆者追踪方案[3],其解决了对称方案中存在的问题,但其实现效率较低。此后,设计以公钥为基础的叛逆者追踪方案成为研究的主要方向,各种以不同公钥加密体制为基础的叛逆者追踪方案被提出。文献[4]提出门限值为k的抗共谋方案,而文献[5～6]提出了具有完全搞共谋的叛逆者追踪方案,即其不存在门限值的限制,但不能实现撤销性。文献[7]对文献[8]进行改进,提出了具有完全抗共谋性、完全撤销性和完全可恢复性的叛逆者追踪方案。具有短私钥的基于身份的叛逆者追踪(IBTT)结构首先由Abdalla 等人提出[9],其提供了基于身份加密的追踪能力。Boneh 等人则提出一种公钥叛逆者追踪方案,其能扩展成具有短密文的IBTT[10]。由于长私钥会增加安全存储的开销,而长密文需要更大的通信开销,Fuchun Guo等人提出一种同时具有短私钥和短密文的IBTT[11]。此外,文献[12]提出了基于消息的叛逆者追踪方案,其构建了一种具有最佳密文速率的消息可跟踪加密方案。

叛逆者追踪方案是打击和威慑数字产品盗版的有效方法,而其的研究重点是抗共谋性、撤销性、恢复性和追踪性等多个方面。基于随机序列并利用离散对数问题,本文提出一种公钥叛逆者追踪方案。该方案利用随机序列构建多个不同的多项式,并利用过滤函数实现多个用户的完全撤销与恢复,其不仅具有较低的存储、计算和通信开销,还满足完全抗共谋性、可完全撤销与恢复性以及黑盒追踪等。

1方案描述

基于随机序列、离散对数问题的叛逆者追踪方案利用多项式与过滤函数来构建。随机序列由用户注册时选择,基于其的DS可衍生出多个多项式,并由此计算生成注册用户的解密密钥。当发现叛逆者需要撤销这些用户或者需要恢复已撤销用户时,该方案能在不更新合法用户私钥的前提下,实现安全撤销多个叛逆者或者完全恢复已撤销用户。

1.1系统初始化

数据提供商在Zq上随机选择一个k次多项式

f(x)=a0+a1x+…+akxk,k>N

(1)

其中,N为最大用户数。除另有说明,本文的所有算术运算都在Zq上。

1.2用户注册

(2)

1.3密钥分发

1.4加密算法

1.5解密算法

用户ui接收到广播密文后,向解码器输入(C1(x),C2),解码器利用其解密密钥ki计算

(3)

C2/C1(ki)=(M(gA)α)/(gAα)=M

(4)

1.6追踪算法

(5)

(6)

(7)

1.7撤销算法

(8)

1.8恢复算法

2性能分析

2.1正确性

引理1若DS正确执行加密算法,给定广播密文(C1(x),C2),则所有合法用户均能成功恢复明文信息。

引理2若输入正确的广播信息(C1(x),C2),结合解码器中的解密密钥ki,则追踪算法可追踪任何叛逆者。

2.2存储、计算和通信开销

就存储开销而言,每个用户只需存储一个常量大小的个人解密密钥ki,存储开销较小。在加密算法中,方案的主要计算量为乘法和模指数计算,计算开销较低。而在通信开销方面,方案只需广播密文(C1(x),C2),通信开销也较少。因此,提出的方案在存储、计算和通信方面的开销均较低。

2.3完全抗共谋性

根据Lagrange插值公式,一个t阶多项式f(x)能利用t+1或>t个的(xi,f(xi))重构。但在本方案中,由于k次多项式

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

(9)

k>N,N为最大用户数,且DS利用用户选择的随机序列重新构建多项式fi(x),计算ki=gfi(i)并将其作为用户ui的个人解密密钥,用户ui要得到fi(i),其困难性相当于求解离散对数问题。因此,即使所有用户合谋也不能重构f(x),该方案具有完全抗共谋性。

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

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

2.5黑盒追踪性

由追踪算法可知,当收缴到一个盗版解码器时,无需将其打开,只需通过一次输入输出即可确定出该盗版解码器所对应的叛逆者,因此其具有黑盒追踪性。

2.6用户密钥的耐用性

用户密钥具有耐用性指的是当恢复用户或撤销用户时,无需改变原有用户的个人解密密钥。在本文方案中,公钥也无须改变,只需修改广播消息中的过滤函数即可。

假设用户集合Δ={ui1,ui2,…,uim},1≤m≤n已被撤销,其中的用户可能是叛逆者或是自愿离开系统,其持有的私钥对应为{ki1,ki2,…,kim},则DS只需进行如下操作:

(10)

计算

(11)

3结束语

本文基于随机序列与离散对数问题,提出一种公钥叛逆者追踪方案。该方案利用用户选择的随机序列构建新多项式,并利用该多项式计算生成用户个人解密密钥;在广播信息中,利用过滤函数实现叛逆者追踪、撤销和恢复用户。当需要撤销多个叛逆者或恢复已撤销的多个用户时,其能在不更新其他用户私钥的前提下,实现一次性安全撤销多个叛逆者或完全恢复已撤销用户。若缴获一个盗版解码器,无需将其打开,只需通过一次输入输出即可确定叛逆者。由性能分析可知,该方案不仅具有较低的存储、计算和通信开销,还具有完全撤销性、完全恢复性、黑盒追踪性以及完全抗共谋性。

参考文献

[1]Duong Hieu Phan,Viet Cuong Trinh.Identity-based trace and revoke schemes[C].Berlin Heidelberg:ProvSec 2011,LNCS 6980,2011.

[2]Chor B,Fiat A,Naor M.Tracing traitors[C].Germany:Advances in Cryptology-CRYPT’94,LNCS,Springer-Verlag,1994.

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

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

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

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

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

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

[9]Abdalla M,Dent A W,Malone-Lee J,et al.Identity-based traitor tracing[C].Heidelberg:PKC 2007,LNCS,Springer,2007.

[10]Boneh D,Naor M.Traitor tracing with constant size ciphertext[C].Sydney:ACM CCS 2008,2008.

[11]Guo Fuchun,Mu Yi,Willy Susilo.Identity-based traitor tracing with short private key and short ciphertext[C].Berlin Heidelberg:ESORICS 2012,LNCS 7459,Springer-Verlag,2012.

[12]Duong Hieu Phan,David Pointcheval,Mario Stefler.Message-based traitor tracing with optimal ciphertext rate[C].Berlin Heidelberg:LATINCRYPT 2012,LNCS 7533,Springer-Verlag,2012.

A Public Key Traitor Tracing Scheme Based on Random Sequence

HE Shaofang

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

AbstractBased on the discrete log representation problem and employing random sequence,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.When a pirate decoder is confiscated,single input and output suffices to decide the traitor.If it is necessary to revoke or recover traitors,the scheme can safely revoke or recover the private keys of traitors without updating the private keys of other receivers.The performance analysis shows that the proposed scheme not only has low cost of secure storage,calculation and communication,but also is capable of full collusion resistance,full revocability,full recoverability and black-box traceability.

Keywordsdiscrete log representation problem;traitor tracing;full revocability;full recoverability;black-box traceability

中图分类号TN918.4;TP393

文献标识码A

文章编号1007-7820(2016)04-180-04

doi:10.16180/j.cnki.issn1007-7820.2016.04.048

作者简介:何少芳(1980—),女,硕士,讲师。研究方向:信息安全。

基金项目:湖南省教育厅基金资助项目(13C394);湖南农业大学“大学生创新性实验计划基金资助项目”(XCX1572)

收稿日期:2015- 09- 07