On Collusion Security of Random Codes

Katsunari YOSHIOKA  Junji SHIKATA  Tsutomu MATSUMOTO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E88-A   No.1   pp.296-304
Publication Date: 2005/01/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Biometrics
fingerprinting,  watermarking,  traitor tracing,  collusion secure code,  

Full Text: PDF(427KB)
>>Buy this Article

Fingerprinting is a technique to add identifying marks to each copy of digital contents in order to enhance traceability to a distribution system. Collusion attacks, in which the attackers collect two or more fingerprinted copies and try to generate an untraceable copy, are considered to be a threat for the fingerprinting system. With the aim of enhancing collusion security to the fingerprinting system, several collusion secure codes, such as c-frameproof code, c-secure frameproof code and c-identifiable parent property code, have been proposed. Here, c indicates the maximum number of colluding users. However, a practical construction of the above codes is still an issue because of the tight restrictions originated from their combinatorial properties. In this paper, we introduce an evaluation of frameproof, secure frameproof, and identifiable parent property by the probability that a code has the required property. Then, we focus on random codes. For frameproof and secure frameproof properties, we estimate the average probability that random codes have the required property where the probability is taken over the random construction of codes and random construction of coalitions. For the estimation, we assume the uniform distribution of symbols of random codes and the symbols that the coalitions hold. Therefore, we clarify the adequacy of the assumptions by comparison with numerical results. The estimates and numerical results resemble, which implies the adequacy of the assumption at least in the range of the experiment.