Digital fingerprinting codes: problem statements, constructions, identification of traitors
Digital fingerprinting codes: problem statements, constructions, identification of traitors
复制标题
DOI：
10.1109/tit.2003.809570
复制
发表时间：
2003-04
期刊：
影响因子：
--
通讯作者：
A. Barg;G. Blakley;G. Kabatiansky
中科院分区：
文献类型：
--
作者：
A. Barg;G. Blakley;G. Kabatiansky
我们考虑了数字数据的一般指纹识别问题，在该问题下，用户联盟可以更改或擦除其副本中的一些比特，以创建非法副本。每个用户被分配一个指纹，它是大小为M(用户总数)和长度为n的指纹码中的一个字。我们提出了针对大小为t的联盟的安全的二进制指纹码，使得分发者(解码器)能够以错误概率exp(-/spl Omega/(N))从联盟中恢复至少一个用户，当M=exp(/spl Omega/(N))时。这是对提供不好于EXP(-/SPL Omega/(n/sup 1/2/))的差错概率的最佳已知方案的改进，并且对于大多数EXP(O(n/sup 1/2/))用户的该概率支持。码的构造复杂度是n中的多项式.我们还给出了这些构造的版本，它们给出了复杂性为poly(N)=PolyLog(M)的识别算法，改进了已知的/SPL Omega/(M)的复杂度.对于t=2的情况，我们构造了具有更强性能的指数大小的码，即对于这种码，分发者可以以概率1-exp(/SPL Omega/(N))从联盟中恢复两个用户，或者以概率1识别一个叛逆者。
We consider a general fingerprinting problem of digital data under which coalitions of users can alter or erase some bits in their copies in order to create an illegal copy. Each user is assigned a fingerprint which is a word in a fingerprinting code of size M (the total number of users) and length n. We present binary fingerprinting codes secure against size-t coalitions which enable the distributor (decoder) to recover at least one of the users from the coalition with probability of error exp(-/spl Omega/(n)) for M=exp(/spl Omega/(n)). This is an improvement over the best known schemes that provide the error probability no better than exp(-/spl Omega/(n/sup 1/2/)) and for this probability support at most exp(O(n/sup 1/2/)) users. The construction complexity of codes is polynomial in n. We also present versions of these constructions that afford identification algorithms of complexity poly(n)=polylog(M), improving over the best previously known complexity of /spl Omega/(M). For the case t=2, we construct codes of exponential size with even stronger performance, namely, for which the distributor can either recover both users from the coalition with probability 1-exp(/spl Omega/(n)), or identify one traitor with probability 1.