New upper bounds for parent-identifying codes and traceability codes

摘要

In the last two decades, parent-identifying codes and traceability codes are introduced to prevent copyrighted digital data from unauthorized use. They have important applications in the scenarios like digital fingerprinting and broadcast encryption schemes. A major open problem in this research area is to determine the upper bounds for the cardinalities of these codes. In this paper we will focus on this theme. Consider a code of length N which is defined over an alphabet of size q. Let and denote the maximal cardinalities of t-parent-identifying codes and t-traceability codes, respectively, where t is known as the strength of the codes. We show , where , and . This new bound improves two previously known bounds of Blackburn, and Alon and Stav. On the other hand, is still not known for almost all t. In 2010, Blackburn, Etzion and Ng asked whether or not, where c is a constant depending only on N, and they have shown the only known validity of this bound for . By using some complicated combinatorial counting arguments, we prove this bound for . This is the first non-trivial upper bound in the literature for traceability codes with strength three.