版权保护中的组合安全码及相关问题_范金萍.pdf

中国科学:数学2023年第53卷第2期:123150SCIENTIA SINICA Mathematica综述英文引用格式:Fan J P,Gu Y J,Miao Y.Combinatorial secure codes for copyright protection and related problems(in Chinese).Sci Sin Math,2023,53:123150,doi:10.1360/SSM-2022-0079c 2022中国科学 杂志社版权保护中的组合安全码及相关问题献给朱烈教授80华诞范金萍1,顾玉杰2,缪莹31.上海师范大学数理学院,上海 200234;2.Faculty of Information Science and Electrical Engineering,Kyushu University,Fukuoka 819-0395,Japan;3.Faculty of Engineering,Information and Systems,University of Tsukuba,Ibaraki 305-8573,JapanE-mail:,guinf.kyushu-u.ac.jp,miaosk.tsukuba.ac.jp收稿日期:2022-04-30;接受日期:2022-07-22;网络出版日期:2022-09-28;*通信作者国家自然科学基金(批准号:12101414)和日本学术振兴会科研项目(批准号:21K13830 和 18H01133)资助项目摘要现代科技的快速发展给数据传播和流通提供了便捷,同时也对数据内容的版权保护构成了巨大的威胁.本文聚焦版权保护中的对抗合谋攻击的数学理论及其最新研究进展.针对广播加密和多媒体指纹识别等不同场景的应用,本文提出可追踪分配方案和防诬陷分配方案的统一的数学模型.在此基础上,本文介绍具体的可追踪组合安全码和防诬陷组合安全码,以及关于它们的最大码字个数的上下界和具体构造等研究的组合方法、最新结果和公开问题.此外,本文也将介绍版权保护与群试理论和多用户通信领域相关组合问题的联系.关键词版权保护组合安全码可追踪分配方案防诬陷分配方案集合系群试理论多用户通信MSC(2020)主题分类05B20,05D05,05D40,68P30,94A60,94B251版权保护中组合安全码的研究历史和发展1.1研究背景简介随着科学技术的发展,多媒体技术日益成熟,常见的视频和图片等多媒体内容在我们的日常生活中得到大量的流通和使用.然而,由于多媒体内容复制便利和传播手段简单等特点,授权用户(authorizeduser)在获取多媒体内容之后可能对内容进行复制并传播给非授权用户而从中获取利益.这种非法复制和传播的行为对多媒体内容的版权保护而言是极大的威胁和挑战.1994年,Chor等18首次在广播加密(broadcast encryption)的应用场景下提出了对抗合谋攻击(collusion attack)的可追踪分配方案的数学方法.拥有数据版权的发行商对数据进行加密并对密文进行广播,任何用户都可以收到广播的密文.一个授权用户在购买版权后会被分配到一个唯一的个人解范金萍等:版权保护中的组合安全码及相关问题密密钥,可以用来解密密文并得到原始数据.由于每个授权用户被分配到的个人解密密钥都具有唯一性和身份认证的性能,因而单个授权用户不会将个人解密密钥直接进行非法复制利用,但是多个授权用户会利用他们所拥有的不同的个人解密密钥进行合谋攻击,制造出一个海盗版(pirated copy)解密密钥,并进行非法使用或交易.Chor等18可追踪分配方案主要考虑如何合理地设计授权用户的个人解密密钥分配问题,以及在抓获海盗版解密密钥后如何快速地追踪到至少一名合谋攻击者的问题.1998年,Boneh和Shaw11提出了在广播加密应用场景下如何保护无辜用户(innocent user)不会被多个用户的合谋攻击者集团诬陷的问题.此外,近些年在多媒体传播等领域,基于数字水印(digitalwatermarking)技术,具有对抗合谋攻击能力的多媒体指纹识别码(multimedia fingerprinting codes)也相继被提出(参见文献65,88).值得注意的是,在广播加密和数字指纹识别(digital fingerprinting)等不同的应用场景下,授权用户的个人解密密钥或者数字指纹的分配方式不同,合谋者所采取的攻击方式也可能不同,因此已经存在的组合安全码(combinatorial secure codes)和集合系(set systems)等也不尽相同.在接下来的第1.2小节中,将针对这些不同应用场景中的对抗合谋攻击问题提出统一的数学刻画模型.1.2研究问题由于密钥/指纹分配方案需要满足的安全性不同,我们以如下的可追踪分配方案和防诬陷分配方案两大类来进行阐述.定义1.1(可追踪分配方案)一个拥有M个用户M:=1,2,.,M且能够防止至多t(6 M)个用户合谋攻击的可追踪分配方案是一个四元组(Enc,Tra;A,t),其中,(1)Enc:M n是一个密钥/指纹分配方案,其中为一个有限集合;(2)A:2n n是一个攻击策略,即合谋团体S M基于A可以制造出一个海盗版A(Enc(S)n,其中为一个集合,通常包含,且A(Enc(S)可以不唯一;(3)Tra:n 2M是一个追踪算法,即对于任何的至多t个合谋者S M以及海盗版A(Enc(S)n,满足Tra(A(Enc(S)不为空集,且Tra(A(Enc(S)S.上述可追踪分配方案可以保证至少追踪到部分或者全部的合谋攻击者,而接下来介绍的防诬陷分配方案将考虑一种相对较弱的安全性质,即它一般不具有可追踪能力,但是可以保证无辜的用户或者团体不被合谋攻击集团所构陷.定义1.2(防诬陷分配方案)一个拥有M个用户M且具有防诬陷性质的分配方案是一个四元组(Enc;A,t,s),其中,(1)Enc:M n是一个密钥/指纹分配方案,其中为一个有限集合;(2)A:2n n是一个攻击策略,即合谋团体S M基于A可以制造出一个海盗版A(Enc(S)n,其中为一个集合,通常包含,且A(Enc(S)可以不唯一;(3)Enc具有防诬陷性质,即对于任何不相交用户集合S,S M且|S|6 t,|S|6 s,以及他们能够制造的任何海盗版A(Enc(S),A(Enc(S),都有A(Enc(S)=A(Enc(S).从上述两个定义的描述中可以看出,一个可追踪分配方案一定具有防诬陷的性质,然而反之未必成立.组合安全码研究的核心问题如下:问题1.1设计可以容纳尽可能多的用户的可追踪分配方案和防诬陷分配方案,以及相应的高效快速的追踪/译码算法.124中国科学:数学第 53 卷第 2 期在下面的第1.4和1.5小节中,将参照定义1.1和1.2中的统一模型,分别对广播加密和多媒体指纹识别的应用场景进行介绍.为了叙述方便,首先列举本文使用的一些记号.1.3一些记号本文采用以下数学符号和定义:n:=1,2,.,n,2n:=X:X n表示n的幂集,(nw):=B n:|B|=w.Rn表示n维Euclid空间,Rn中任意两个点z与z之间的Euclid距离为z z.令n和q为正整数,Q=0,1,.,q 1,Qn=x=(x(1),x(2),.,x(n):x(i)Q,1 6 i 6 n为所有基于Q且长度为n的向量所构成的集合.对于x=(x(1),x(2),.,x(n)Qn和y=(y(1),y(2),.,y(n)Qn,x与y之间的Hamming距离定义为d(x,y):=|i n:x(i)=y(i)|,x与y之间的内积为=ni=1x(i)y(i).用C=c1,c2,.,cM Qn表示一个基于Q的码长为n、大小为M的q元码,记为(n,M,q)码,C中的每一个cj=(cj(1),cj(2),.,cj(n)称为码字.用B=B1,B2,.,BM(nw)表示一个(w,M,n)集合系,其中每一个Bj n被称为区组(block),且区组大小为|Bj|=w.对于任意的码C Qn,记C(i):=c(i)Q:c=(c(1),c(2),.,c(n)C(1 6 i 6 n)为码C的第i个分量的元素所构成的集合.对于任意的码C Qn,定义C的后代码(descendant code)为desc(C):=C(1)C(2)C(n)=(x(1),x(2),.,x(n)Qn:x(i)C(i),1 6 i 6 n.令t 2为正整数.对于任意w Qn,定义w在C中的限定父代码集(set of bounded parentcodes)为Pt(w):=C C:w desc(C),|C|6 t,其中,Pt(w)中的每一个C都是w在C中的一个限定父代码.令t 2为正整数.对于任意S Qn,定义S在C中的限定父代码集和父代码集(set of parentcodes)分别为Pt(S):=C C:desc(C)=S,|C|6 t,P(S):=C C:desc(C)=S,(1.1)其中,Pt(S)中的每一个C是C中能产生S的一个限定父代码,P(S)中的每一个C是C中能产生S的一个父代码.对于一个(n,M,q)码C,定义C的码率(code rate)为(logqM)/n.记M(n,q)为n长的q元码的最大码字个数,定义其最大渐近码率(largest asymptotic code rate)为R(q):=limsupnlogqM(n,q)n.对于两个关于正整数n取正值的函数f和g,如果limnf(n)g(n)=0,则记f=o(g);如果存在常数c和N,使得对于任意n N都有f(n)6 cg(n),则记f=O(g);如果存在常数c和N,使得对于任意n N都有f(n)cg(n),则记f=(g);如果f=O(g)与f=(g)同时成立,则记f=(g).125范金萍等:版权保护中的组合安全码及相关问题 Poly(n)表示关于变量n取正值的多项式函数.为避免记号混淆,需要指出Pt(w)与Pt(w)之间的区别:Pt(w)是后代码包含w的C的大小不超过t的子码的集合,而Pt(w)是后代码恰好是w的C的大小不超过t的子码的集合,它们之间的关系为Pt(w)Pt(w).1.4广播加密中的版权保护在广播加密的应用场景中,可追踪分配方案可以分为针对内容和针对密钥的加密83.下面对这两种情形进行具体说明.1.4.1针对内容加密的模型Chor等18可追踪分配方案考虑了对数据内容的加密.如图1所示,首先,原始数据内容被划分成n块,即data1,data2,.,datan;然后,数据发布者利用均匀且独立地随机(uniformly and independentlyat random)选取的qn个密钥Ki,j:i Q,j n,对这n块数据进行加密并广播,其中每块数据dataj被加密成q个备份:EKi,j(dataj):i Q.如果用户想要恢复原始数据内容,需要解密得到所有的n块数据.每个合法用户l M在付费后将被分配到一个码字cl=(cl(1),cl(2),.,cl(n)Qn,对应到一个个人解密密钥(Kcl(1),1,Kcl(2),2,.,Kcl(n),n),其中Kcl(j),j可以用来解密EKcl(j),j(dataj)得到第j块数据dataj(为了叙述方便,这里假设使用的是对称密钥加密,即加解密的密钥是相同的).此时,在定义1.1的模型下,密钥分配方案可以表述为Enc:M Qn.若不超过t个用户S M进行合谋攻击,则根据嵌入假设(marking assumption)11,他们可以制造出一个海盗版解密密钥(Kx(1),1,Kx(2),2,.,Kx(n),n),对应于A(Enc(S)(x(1),x(2),.,x(n)Qn:x(j)=cs(j),s S.换句话讲,海盗版解密密钥中用于对每块数据dataj解密的密钥必须由合谋团体S中的某一个合谋者来提供.在此攻击模型下,有如下两种经典的追踪算法:(T1)Chor等18,19提出了比较海盗版解密密钥A(Enc(S)和所有合法用户解密密钥的Ham