On the capacity and the zero-error capacity of k-resilient AND anti-collusion codes

Embedding anti-collusion fingerprinting codes to digital contents enables us to protect the digital contents from piracy. Recently, Trappe et al. proposed an anti-collusion code (AND-ACC) such that all the illegal users are exactly detected from a binary sequence obtained from AND of all the codewords of the illegal users, where the number of the illegal users is assumed to be less than or equal to a constant k ≥ 2. In this paper we focus on the AND-ACC and analyze the number of codewords M with increasing the codeword length n for an arbitrarily fixed k ≥ 2. First, we define the zero-error capacity C*_k of the AND-ACC and give a lower and an upper bounds of C*_k. The lower bound of C*_k is obtained by using a lemma used in a coding theorem on the identification codes. In addition, we extend the AND-ACC to the case where negligible detection error is permitted. We define the capacity C_k and give a lower and an upper bounds of C_k. These bounds are established by using techniques used for coding of a multiple-access channel.