2024/02/12 by Miao Liu, Liu, Miao, Zengjiao Ma +3 · 1 citation
Computer Science · Engineering · #Advancements in Photolithography Techniques #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Numerical Methods and Algorithms
paper · pdf · doi:10.48550/arxiv.2402.07711
openalex publication_date 2024/02/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Mc,l(q) denote the largest cardinality of a q-ary c-frameproof code with length l. Based on an intriguing observation that relates Mc,l(q) 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 Rc,l=limq→∞\fracMc,l(q)q\lceil l/c \rceil. By combining several ideas from the probabilistic method, we present a lower bound for Mc,l(q), which, together with an upper bound of Blackburn, completely determines Rc,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 Mc,l(q).