Existence and Algorithmic Construction of $q$-ary Secure Codes with List Decoding

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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> have been investigated for asymptotically large alphabet size <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$q$</tex>, 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$q$</tex> by virtue of the Lovász local lemma, which particularly implies the known results when <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$q$</tex> 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.