FR2.R3.2

Near optimal constructions of frameproof codes

Miao Liu, Zengjiao Ma, Chong Shangguan, Shandong University, China

Session:
Combinatorial Coding Theory 3

Track:
1: Algebraic Aspects of Coding Theory

Location:
Ypsilon IV-V-VI

Presentation Time:
Fri, 12 Jul, 11:50 - 12:10

Session Chair:
Hiram Lopez,
Abstract
"THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD." 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 content. Let $M_{c,l}(q)$ denote the largest cardinality of a $q$-ary $c$-frameproof code with length $l$. Based on an intriguing observation that relates $M_{c,l}(q)$ to the renowned Erd\H{o}s Matching Conjecture in extremal set theory, in 2003, Blackburn posed an open problem on the precise value of the limit $R_{c,l}=\lim_{q\rightarrow\infty}\frac{M_{c,l}(q)}{q^{\lc l/c \rc}}$. By combining several ideas from the probabilistic method, we present a lower bound for $M_{c,l}(q)$, which, together with an upper bound of Blackburn, completely determines $R_{c,l}$ for {\it all} fixed $c,l$, and resolves the above open problem in the full generality. We also present an improved upper bound for $M_{c,l}(q)$. (A full version of this paper will soon appear in arXiv.)
Resources