Near Optimal Probabilistic Constructions of Frameproof Codes

Frameproof codes are a class of secure codes that were originally introduced in the pioneering work of Boneh and Shaw in the context of digital fingerprinting. They can be used to enhance the security and credibility of digital contents. Let <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M_c,l(q)</i> denote the largest cardinality of a q-ary c-frameproof code with length l. Based on an intriguing observation that relates <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M_c,l(q)</i> to the renowned Erdős Matching Conjecture in extremal set theory, in 2003, Blackburn posed an open problem on the precise value of the limit <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R_c,l</i> = lim<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">_q</i>→∞ <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M_c,l(q)</i> /<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q⌈l/c⌉</i>. By combining several ideas from the probabilistic method, we present a lower bound for <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M_c,l(q)</i>, which, together with an upper bound of Blackburn, completely determines <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R_c,l</i> for <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">all</i> fixed <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">c, l</i>, and resolves the above open problem in the full generality. We also present an improved upper bound for <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M_c,l(q)</i>.