Existence and Algorithmic Construction of $q$-ary Secure Codes with List Decoding
Ling Li Jiang, Yujie Gu, Jinping Fan, Ying Miao · 2024
Secure codes with list decoding (SCLDs) were introduced due to their applications in collusion-resistant multimedia fingerprinting for copyright protection. A fundamental research problem is investigating the largest code rates and explicit constructions for SCLDs. So far, the largest code rates of SCLDs with length$n$have been investigated for asymptotically large alphabet size$q$, and explicit constructions of SCLDs are known for only a few specific cases. In this paper, we establish new lower bounds on the largest code rate of SCLDs for a broad range of alphabet size$q$by virtue of the Lovász local lemma, which particularly implies the known results when$q$is asymptotically large. Furthermore, we present a generic algorithmic construction for SCLDs by means of the Moser-Tardos algorithm and demonstrate its linear-time computational complexity.