#  Secure Codes with List Decoding ††thanks:  Y. Gu is with the Faculty of
Information Science and Electrical Engineering, Kyushu University, Fukuoka,
Japan. (email<EMAIL_ADDRESS>I. Vorobyev is with Institute of
Communications Engineering, Technical University of Munich, Munich, Germany.
(email<EMAIL_ADDRESS>Y. Miao is with the Faculty of Engineering,
Information and Systems, University of Tsukuba, Ibaraki, Japan. (email:
<EMAIL_ADDRESS>This work was supported by RFBR and the National
Science Foundation of Bulgaria (NSFB) under Project No. 20-51-18002, by BMBF-
NEWCOM under Grant No. 16KIS1005, by JSPS under Grants No. 18H01133, No.
21K13830, and by Japan-Russia Research Cooperative Program between JSPS and
RFBR under Project No. JPJSBP 120204802. An earlier version of this paper was
presented in part at the IEEE International Symposium on Information Theory
(ISIT2022) [29].

Yujie Gu, Ilya Vorobyev, Ying Miao

###### Abstract

In this paper we consider combinatorial secure codes in traitor tracing for
protecting copyright of multimedia content. First, we introduce a new notion
of secure codes with list decoding (SCLDs) for collusion-resistant multimedia
fingerprinting, which includes many existing types of fingerprinting codes as
special cases. Next, we build efficient identifying algorithms for SCLDs with
complete traceability and establish bounds on its largest possible code rate.
In comparison with the existing fingerprinting codes, it is shown that SCLDs
have not only much more efficient traceability than separable codes but also a
much larger code rate than frameproof codes. As a byproduct, new bounds on the
largest code rate of binary separable codes are established as well.
Furthermore, a two-stage dynamic traitor tracing framework is proposed for
multimedia fingerprinting in the dynamic scenario, which could not only
efficiently achieve the complete traceability but also provide a much larger
capacity than the static scenario.

###### Index Terms:

Secure code, list decoding, dynamic traitor tracing, copyright protection,
binary code, code rate

##  I Introduction

The development and ubiquity of communication networks tremendously boost the
spread and utility of multimedia content, such as text, audio, images,
animations, and video, which, accordingly, stirs up the impending and
challenging task of guaranteeing that the multimedia content is utilized for
its intended purpose by authorized and legitimate consumers. For the sake of
holding back multimedia content from being maliciously redistributed, digital
fingerprinting has been proposed with the advantage that fingerprints can be
embedded in multimedia content through watermarking techniques [13] and the
malicious authorized consumers can be identified once they illegally use their
content for unintended purpose [5, 10].

The orthogonal modulation and code modulation are two typical methods of
embedding fingerprints into multimedia content [42]. This work is considered
with the latter code modulation scenario, which could accommodate more users
than the former orthogonal modulation with the same amount of orthogonal
signals [42] and is briefly reviewed as follows. Suppose the host signal is a
real vector $\mathbf{x}\in\mathbb{R}^{m}$ of length $m$. In code modulation,
there are $n$ orthonormal basis signals
$\\{\mathbf{u}_{i}\in\mathbb{R}^{m}:1\leq i\leq n\\}$ which are typically not
known to the users, and a watermark signal, or a fingerprint, $\mathbf{w}_{j}$
is generated in the way that
$\mathbf{w}_{j}=\sum_{i=1}^{n}\mathbf{c}_{j}(i)\mathbf{u}_{i}$ where
$\mathbf{c}_{j}(i)\in\\{0,1\\}$ according to the on-off keying (OOK)
modulation. Accordingly user $j$ will be allocated a fingerprinted signal copy
$\mathbf{y}_{j}=\mathbf{x}+\mathbf{w}_{j}$ of $\mathbf{x}$, which is feasible
due to the fact that multimedia data is perceptually insensitive to minor
perturbation in the data values [42]. It is readily seen that there is a one-
to-one correspondence between the authorized user $j$ and fingerprint
$\mathbf{w}_{j}$, or equivalently the coefficient vector
$\mathbf{c}_{j}=(\mathbf{c}_{j}(1),\ldots,\mathbf{c}_{j}(n))\in\\{0,1\\}^{n}$.
Accordingly, all $M$ authorized users are associated with a collection of
fingerprints $\\{\mathbf{c}_{j}\in\\{0,1\\}^{n}:1\leq j\leq M\\}$. Regarding
the collusion attacks, as pointed out in [42], since different bits of
fingerprints that are additively embedded in multimedia may not be easily
identifiable and arbitrarily manipulated, thereby linear collusion attacks
such as averaging several fingerprinted signals are often more feasible for
multimedia. In a linear attack, a coalition consisting of a set of malicious
authorized users $J\subseteq\\{1,\ldots,M\\}$ creates a forged copy
$\hat{\mathbf{y}}$ by taking a linear combination of their copies
$\mathbf{y}_{j}$, namely,

$\displaystyle\hat{\mathbf{y}}=\sum_{j\in
J}\lambda_{j}\mathbf{y}_{j}=\sum_{j\in
J}\lambda_{j}(\mathbf{x}+\mathbf{w}_{j})=\mathbf{x}+\sum_{j\in
J}\lambda_{j}\mathbf{w}_{j}=\mathbf{x}+\sum_{i=1}^{n}\bigg{(}\sum_{j\in
J}\lambda_{j}\mathbf{c}_{j}(i)\bigg{)}\mathbf{u}_{i}$ (1)

where $\lambda_{j}$ are some real-valued coefficients such that
$0<\lambda_{j}<1$ and $\sum_{j\in J}\lambda_{j}=1$. In particular, if
$\lambda_{j}=1/|J|$ for all $j\in J$, it is called an averaging attack. The
traceability refers to that once the forged copy $\hat{\mathbf{y}}$ is
captured, partial or all of the colluders/traitors in $J$ would be identified.
In particular, if all colluders in $J$ could be identified, it is referred to
as the complete traceability. In the identifying phase, the useful information
can be extracted from the captured $\hat{\mathbf{y}}$ via the inner product
$\langle\hat{\mathbf{y}},\mathbf{u}_{i}\rangle=\sum_{j\in
J}\lambda_{j}\mathbf{c}_{j}(i)$ for all $1\leq i\leq n$. It is easily verified
that $\langle\hat{\mathbf{y}},\mathbf{u}_{i}\rangle\in[0,1]$ and

  * •

$\langle\hat{\mathbf{y}},\mathbf{u}_{i}\rangle=0\ \text{implies}\
\\{\mathbf{c}_{j}(i):j\in J\\}=\\{0\\}$;

  * •

$\langle\hat{\mathbf{y}},\mathbf{u}_{i}\rangle=1\ \text{implies}\
\\{\mathbf{c}_{j}(i):j\in J\\}=\\{1\\}$;

  * •

$\langle\hat{\mathbf{y}},\mathbf{u}_{i}\rangle\in(0,1)\ \text{implies}\
\\{\mathbf{c}_{j}(i):j\in J\\}=\\{0,1\\}$.

The yielded vector $\big{(}\\{\mathbf{c}_{j}(1):j\in
J\\},\ldots,\\{\mathbf{c}_{j}(n):j\in J\\}\big{)}$ is termed as the evidence
vector or descendant code of $J$ and will be used in the identifying/decoding
algorithms, whose precise definition is referred to Section II as well. In
terms of the anti-collusion fingerprinting, it is desirable to design a
multimedia fingerprinting code which is a collection of fingerprints
$\\{\mathbf{c}_{j}:1\leq j\leq M\\}$ with efficient (partial or complete)
traceability. This setting is typically referred to as the static model of
traitor tracing, with particular applications to electronic data distribution
systems.

On the other hand, Fiat and Tassa [22, 23] introduced the concept of dynamic
traitor tracing, which has numerous practical applications in protecting
intellectual rights of streaming data in broadband multicast systems. The
dynamic traitor tracing typically allows to identify all the traitors in
several stages; and in each stage, one could exploit the feedback from the
previous and adapt the tracing strategies accordingly, see [2, 32, 37] for
example. Correspondingly, it allows the usage of several (different)
secure/fingerprinting codes on the fly, which typically could accommodate much
more users and/or provide more efficient traitor tracing in comparison with
the static system.

In the literature, several classes of combinatorial multimedia fingerprinting
codes have been proposed, which are briefly reviewed as follows. In 1998,
Boneh and Shaw [5] defined the $t$-frameproof codes, which could be utilized
to trace back to all traitors in linear time $O(nM)$ where $n$ and $M$ are the
length and the size of the code, respectively. Note that the definition of
$t$-frameproof codes coincides with $(t,1)$-separating codes, considered in
[26, 38, 39] much earlier. Later in order to neutralize the averaging attack
in multimedia fingerprinting, the AND anti-collusion code [42], the logical
anti-collusion code (i.e. binary separable codes) [8], and strongly separable
codes [31] have been introduced respectively, which all could guarantee the
complete traceability and have been studied in e.g. [24, 28, 45, 46].
Recently, signature codes with complete traceability for collusion-resistant
multimedia fingerprinting have been investigated in [17, 19], which are shown
to be essentially equivalent to uniquely decodable codebooks for weighted
binary adder channel communication. In addition, signature codes with noise
have been discussed in [17, 18, 19, 44] as well.

The list decoding technique has been applied to the traitor tracing problem
(see e.g. [1, 15, 20, 21, 41]), while the application model therein is related
but different with this paper. In [16], the authors constructed multimedia
fingerprinting codes with efficient decoding but rather small code rate, which
is based on the code concatenation together with the fast list decoding of
Reed-Solomon codes with large distance. So far, all the existing applications
of list decoding in traitor tracing are to construct certain types of
fingerprinting codes by means of error-correcting codes with large Hamming
distance and the concatenation construction, whereby the decoding analyses
typically rely on the efficient list decoding algorithms of Reed-Solomon codes
or algebraic-geometry codes (see e.g. [30]). In contrast to these known
results, this work initially develops the list decoding property directly from
the underlying traitor tracing model instead of taking error-correcting codes
as an intermediary, and the list decoding here naturally goes beyond the
Hamming metric according to the practical model.

In this paper, first, we introduce the notion of secure codes with list
decoding (SCLDs) for collusion-resistant multimedia fingerprinting, which
integrates the idea of list decoding into anti-collusion secure codes and
hereby leads to efficient identifying algorithms. It is shown that SCLDs
include many existing fingerprinting codes as special cases. Next, we build a
two-step identifying algorithm for SCLDs and show that it could have the
complete traceability as frameproof codes, which, however, is much more
efficient than the traitor tracing based on the existing separable codes. On
the other hand, we establish bounds on the code rates of binary and $q$-ary
SCLDs respectively, which show that SCLDs could have a much larger code rate
than the existing frameproof codes. As a byproduct, we provide new lower
bounds on the largest code rate of binary separable codes. In addition, some
explicit constructions for SCLDs and efficient decoding algorithms for certain
SCLDs with algebraic structures are provided as well. Furthermore, we discuss
the dynamic multimedia fingerprinting and establish a two-stage dynamic
traitor tracing framework based on the list decoding property, which provides
not only efficient decoding but also much larger code rate (i.e. accommodate
much more users) than the static scenario.

The paper is organized as follows. Section II presents the notations and
definitions of codes. Section III exhibits the decoding algorithm for SCLDs.
Section IV establishes bounds on the code rates of binary SCLDs with large
list size and binary separable codes. Section V provides a lower bound on the
largest code rate of binary SCLDs with constant list size. Section VI
establishes bounds for $q$-ary SCLDs. Section VII presents some explicit
constructions of SCLDs and the corresponding efficient decoding algorithm.
Section VIII discusses the dynamic two-stage traitor tracing. Finally Section
IX concludes this paper.

##  II Preliminaries

To define the codes, we first introduce some notations. Let $n,q,M$ be
positive integers and $Q\triangleq\\{0,1,\ldots,q-1\\}$ be an alphabet of size
$|Q|=q$. For a prime power $q$, let $\text{GF}(q)$ denote the finite field of
order $q$. Denote $[M]\triangleq\\{1,2,\ldots,M\\}$. A set of $M$ vectors
$\mathcal{C}=\\{\mathbf{c}_{1},\mathbf{c}_{2},\ldots,\mathbf{c}_{M}\\}\subseteq
Q^{n}$ is called an $(n,M,q)$ code and each
$\mathbf{c}_{i}=(\mathbf{c}_{i}(1),\mathbf{c}_{i}(2),\ldots,\mathbf{c}_{i}(n))\in
Q^{n}$ is called a codeword of length $n$. An $(n,M,q)$ code is also called a
$q$-ary code with length $n$ and size (or cardinality) $M$. The rate of an
$(n,M,q)$ code $\mathcal{C}$ is $R(\mathcal{C})=(\log_{q}M)/n$.

For code $\mathcal{C}\subseteq Q^{n}$, we define the $i$th projection of
$\mathcal{C}$ as

$\mathcal{C}(i)=\\{\mathbf{c}(i)\in Q:\mathbf{c}\in\mathcal{C}\\},\ 1\leq
i\leq n.$

The descendant code or evidence vector of $\mathcal{C}$ is defined as

$\text{desc}(\mathcal{C})=(\mathcal{C}(1),\ldots,\mathcal{C}(n))\in\mathcal{P}(Q)^{n},$

where $\mathcal{P}(Q)^{n}=\mathcal{P}(Q)\times\cdots\times\mathcal{P}(Q)$ and
$\mathcal{P}(Q)$ is the power set of $Q$, i.e.
$\mathcal{P}(Q)\triangleq\\{Q_{0}:Q_{0}\subseteq Q\\}.$ For instance, if
$\mathcal{C}=\\{(0,1,0),(0,0,1),(0,1,2)\\}$, then
$\text{desc}(\mathcal{C})=(\\{0\\},\\{0,1\\},\\{0,1,2\\})$. In particular, let

$\displaystyle\text{Desc}_{t}(\mathcal{C})=\\{\text{desc}(\mathcal{C}_{0}):\mathcal{C}_{0}\subseteq\mathcal{C},1\leq|\mathcal{C}_{0}|\leq
t\\}.$

For any $\mathbf{a}\in Q^{n}$ and $\mathbf{b}\in\mathcal{P}(Q)^{n}$, we say
that $\mathbf{a}$ is covered by $\mathbf{b}$, denoted by
$\mathbf{a}\preceq\mathbf{b}$, if and only if $\mathbf{a}(i)\in\mathbf{b}(i)$
for all $i\in[n]$.

###  II-A Secure code with list decoding

First we introduce the notion of secure codes with list decoding.

######  Definition 1.

Suppose that $\mathcal{C}=\\{\mathbf{c}_{1},\ldots,\mathbf{c}_{M}\\}\subseteq
Q^{n}$ is an $(n,M,q)$ code and $t\geq 2$, $t\leq L\leq M$ are integers. Then
$\mathcal{C}$ is a $\bar{t}$-secure code with list decoding, or
$\bar{t}$-SCLD$(n,M,q;L)$, if

  * (1)

for all distinct $\mathcal{C}_{1},\mathcal{C}_{2}\subseteq\mathcal{C}$ with
$|\mathcal{C}_{1}|\leq t$ and $|\mathcal{C}_{2}|\leq t$, we have
$\text{desc}(\mathcal{C}_{1})\neq\text{desc}(\mathcal{C}_{2})$;

  * (2)

for any evidence vector $\mathbf{d}\in\text{Desc}_{t}(\mathcal{C})$, there are
at most $L$ codewords covered by $\mathbf{d}$, namely

$\text{Res}_{\mathcal{C}}(\mathbf{d})\triangleq|\\{\mathbf{c}\in\mathcal{C}:\mathbf{c}\preceq\mathbf{d}\\}|\leq
L.$

We remark that the condition (1) of Definition 1 guarantees the complete
traceability of the secure code; the condition (2) indicates the list decoding
of the secure code, which could induce efficient traitor tracing based on a
two-step decoding (see our Algorithm 1). We illustrate this new concept with
two small examples.

######  Example 1.

It is readily checked that

  1. 1)

$\mathcal{C}_{1}=\\{(0,0,1),(1,0,1),(1,1,0)\\}\subseteq\\{0,1\\}^{3}$ is a
$\bar{2}$-SCLD$(3,3,2;3)$; and

  2. 2)

$\mathcal{C}_{2}=\\{(0,0,0),(1,0,0),(0,1,0),(0,0,1)\\}\subseteq\\{0,1\\}^{3}$
is a $\bar{2}$-SCLD$(3,4,2;3)$.

Note that in $\mathcal{C}_{1}$ the list size $L=M=t+1=3$, while in
$\mathcal{C}_{2}$ the list size $L=M-1=t+1=3$.

It is worth noting that SCLDs can be seen as a unified concept of multimedia
fingerprinting codes with complete traceability in terms of the list size.
Recall three classes of existing codes from [5, 8, 40].

######  Definition 2.

Suppose that $\mathcal{C}=\\{\mathbf{c}_{1},\ldots,\mathbf{c}_{M}\\}\subseteq
Q^{n}$ is an $(n,M,q)$ code and $t\geq 2$ is an integer. Then

  1. 1)

$\mathcal{C}$ is a $t$-frameproof code, or $t$-FPC$(n,M,q)$, if for any
$\mathcal{C}_{0}\subseteq\mathcal{C}$ such that $|\mathcal{C}_{0}|=t$ and any
$\mathbf{a}\in\mathcal{C}\setminus\mathcal{C}_{0}$, it holds that
$\mathbf{a}\npreceq\text{desc}(\mathcal{C}_{0})$;

  2. 2)

$\mathcal{C}$ is a $\bar{t}$-separable code, or $\bar{t}$-SC$(n,M,q)$, if for
all distinct $\mathcal{C}_{1},\mathcal{C}_{2}\subseteq\mathcal{C}$ with
$|\mathcal{C}_{1}|\leq t$ and $|\mathcal{C}_{2}|\leq t$, we have
$\text{desc}(\mathcal{C}_{1})\neq\text{desc}(\mathcal{C}_{2})$.

  3. 3)

$\mathcal{C}$ is a $t$-hypercode with list decoding, or $t$-HLD$(n,M,q;$ $L)$,
if for any $\mathcal{C}_{0}\subseteq\mathcal{C}$ such that
$|\mathcal{C}_{0}|=t$, and $\mathbf{d}=\text{desc}(\mathcal{C}_{0})$, we also
have

$\text{Res}_{\mathcal{C}}(\mathbf{d})=|\\{\mathbf{c}\in\mathcal{C}:\mathbf{c}\preceq\mathbf{d}\\}|\leq
L.$

It is readily verified from the above definitions that a $t$-HLD$(n,M,q;L)$
implies a $t^{\prime}$-HLD$(n,M,q;L)$ for any $t^{\prime}\leq t$, and $t$-FPCs
and $\bar{t}$-SCs are in fact special cases of $\bar{t}$-SCLDs. More
precisely, we have the followings immediately.

######  Lemma 1.

Let $t,n,q,M,L$ be positive integers such that $M\geq L\geq t$, then the
followings hold.

  1. 1)

A $t$-FPC$(n,M,q)$ is equivalent to a $\bar{t}$-SCLD$(n,M,q;t)$.

  2. 2)

A $\bar{t}$-SC$(n,M,q)$ is equivalent to a $\bar{t}$-SCLD$(n,M,q;M)$.

  3. 3)

Let $\mathcal{C}$ be an $(n,M,q)$ code. Then $\mathcal{C}$ is a
$\bar{t}$-SCLD$(n,M,q;L)$ if and only if $\mathcal{C}$ is a
$\bar{t}$-SC$(n,M,q)$ and a $t$-HLD$(n,M,q;L)$ simultaneously.

  4. 4)

A $\bar{t}$-SCLD$(n,M,q;L)$ is a $\bar{t}$-SCLD$(n,M,q;L^{\prime})$ for any
$L\leq L^{\prime}\leq M$.

###  II-B Code rate

Let $M_{\rm FPC}(t,n,q)$, $M_{\rm SCLD}(\bar{t},n,q;L)$, $M_{\rm
HLD}(t,n,q;L)$, $M_{\rm SC}(\bar{t},n,q)$ denote the largest cardinality of a
$q$-ary $t$-FPC, $\bar{t}$-SCLD, $t$-HLD, $\bar{t}$-SC of length $n$,
respectively.

According to practical applications [42], binary fingerprinting codes are
typically desired. It is well known that, by Forney concatenation [25], binary
codes can be derived from general $q$-ary codes as well. Hence in what follows
we will consider the following two typical scenarios.

  * •

For binary codes, denote their largest asymptotic code rates as

$\displaystyle R_{\rm FPC}(t)$
$\displaystyle=\limsup_{n\to\infty}\frac{\log_{2}M_{\rm FPC}(t,n,2)}{n},$
$\displaystyle R_{\rm SCLD}(\bar{t};L)$
$\displaystyle=\limsup_{n\to\infty}\frac{\log_{2}M_{\rm
SCLD}(\bar{t},n,2;L)}{n},$ $\displaystyle R_{\rm HLD}(t;L)$
$\displaystyle=\limsup_{n\to\infty}\frac{\log_{2}M_{\rm HLD}(t,n,2;L)}{n},$
$\displaystyle R_{\rm SC}(\bar{t})$
$\displaystyle=\limsup_{n\to\infty}\frac{\log_{2}M_{\rm SC}(\bar{t},n,2)}{n}.$

  * •

For $q$-ary codes of length $n$, denote their largest asymptotic code rates as

$\displaystyle R_{\rm FPC}(t,n)$
$\displaystyle=\limsup_{q\to\infty}\frac{\log_{q}M_{\rm FPC}(t,n,q)}{n},$
$\displaystyle R_{\rm SCLD}(\bar{t},n;L)$
$\displaystyle=\limsup_{q\to\infty}\frac{\log_{q}M_{\rm
SCLD}(\bar{t},n,q;L)}{n},$ $\displaystyle R_{\rm HLD}(t,n;L)$
$\displaystyle=\limsup_{q\to\infty}\frac{\log_{q}M_{\rm HLD}(t,n,q;L)}{n},$
$\displaystyle R_{\rm SC}(\bar{t},n)$
$\displaystyle=\limsup_{q\to\infty}\frac{\log_{q}M_{\rm SC}(\bar{t},n,q)}{n}.$

According to Lemma 1, we immediately have the following consequences.

######  Corollary 1.

Let $t,n,L,L^{\prime}$ be integers such that $2\leq t\leq L\leq L^{\prime}\leq
M$, where $M$ is the cardinality of the code. Then we have

  * 1)

$R_{\rm FPC}(t)\leq R_{\rm SCLD}(\bar{t};L)\leq\min\\{R_{\rm
SC}(\bar{t}),R_{\rm HLD}(t;L)\\}$.

  * 2)

$R_{\rm FPC}(t,n)\leq R_{\rm SCLD}(\bar{t},n;L)\leq R_{\rm SC}(\bar{t},n)$.

  * 3)

$R_{\rm SCLD}(\bar{t},n;L)\leq R_{\rm SCLD}(\bar{t},n;L^{\prime})$.

We summarize the state-of-the-art bounds for FPCs, HLDs, SCs and the new
bounds for SCLDs in the case when the alphabet size $q$ is sufficiently large
in Table I.

TABLE I:  Asymptotic code rates of $q$-ary FPCs, SCLDs, HLDs, SCs as $q\to\infty$ | $R_{\rm FPC}(t,n)$ | $R_{\rm SCLD}(\bar{t},n;L)$ | $R_{\rm HLD}(t,n;L)$ | $R_{\rm SC}(\bar{t},n)$
---|---|---|---|---
Code Rate | $=\frac{\lceil n/t\rceil}{n}$ | $\geq\begin{cases}2/3&\text{if $t=2$, $L\geq 3$}\\\ 1/(t-1)&\text{if $t>2$, $L\geq t+1$}\end{cases}$ | $\geq\frac{L-t+1}{L}$ | $\geq\begin{cases}2/3&\text{if $t=2$}\\\ 1/(t-1)&\text{if $t>2$}\end{cases}$
$\leq\begin{cases}\lceil 2n/3\rceil/n&\text{if $t=2$}\\\ \lceil n/(t-1)\rceil/n&\text{if $t>2$}\end{cases}$ | $\leq\frac{(L-t+1)\lceil(n/L\rceil}{n}$ | $\leq\begin{cases}\lceil 2n/3\rceil/n&\text{if $t=2$}\\\ \lceil n/(t-1)\rceil/n&\text{if $t>2$}\end{cases}$
Reference | [3, 11] | Theorem 5, [4, 27] | [14, 40] | [4, 27]

##  III Identifying algorithm for SCLDs

In this section we present a two-step identifying algorithm for SCLDs and
discuss its performance in comparison with the existing FPCs and SCs. A
similar idea was used in the context of union-free codes for non-adaptive
group testing as well [43].

######  Theorem 1.

A $\bar{t}$-SCLD$(n,M,q;L)$ has an identifying algorithm with complete
traceability and $O\big{(}\max\\{nM,nL^{t}\\}\big{)}$ time complexity.

###### Proof:

The identifying algorithm for a $\bar{t}$-SCLD$(n,M,q;L)$ can be done as
Algorithm 1, where

  * •

the time cost of Step 1 is $O(nM)$ and $|\mathcal{W}|\leq L$;

  * •

the time cost of Step 2 is $O(n|\mathcal{W}|^{t})=O(nL^{t}).$

Algorithm 1 Identifying algorithm for $\bar{t}$-SCLDs

Input: $\bar{t}$-SCLD code $\mathcal{C}$; the evidence vector
$\mathbf{d}\in\text{Desc}_{t}(\mathcal{C})$
Output: the set of all traitors $\mathcal{T}$

1:$\mathcal{T}=\emptyset$, $\mathcal{W}=\emptyset$. $\triangleright$
Initialize the candidate sets

2:for each $\mathbf{c}\in\mathcal{C}$ do $\triangleright$ Step 1

3: if $\mathbf{c}\preceq\mathbf{d}$ then

4: $\mathcal{W}=\mathcal{W}\cup\\{\mathbf{c}\\}$;

5: end if

6:end for

7:for each subset $\mathcal{S}\subseteq\mathcal{W}$ of size at most $t$ do
$\triangleright$ Step 2

8: if $\text{desc}(\mathcal{S})==\mathbf{d}$ then

9: $\mathcal{T}=\mathcal{S}$;

10: output $\mathcal{T}$;

11: end if

12:end for

Therefore the total time cost of Algorithm 1 is $O(\max\\{nM,nL^{t}\\})$.
Furthermore, according to Definition 1 of SCLDs, the true coalition set
$\mathcal{T}$, after Step 1, is a subset of $\mathcal{W}$, and could be
exactly identified after Step 2. That is, Algorithm 1 for SCLDs is with
complete traceability, as desired. ∎

By taking $L=\lfloor M^{1/t}\rfloor$ in Theorem 1, we have an immediate
corollary.

######  Corollary 2.

A $\bar{t}$-SCLD$\big{(}n,M,q;\lfloor M^{1/t}\rfloor\big{)}$ has an
identifying algorithm with complete traceability and $O(nM)$ time complexity.

Recall the traitor tracing of FPCs and SCs from [8].

######  Lemma 2 ([8]).

  1. 1)

A $t$-FPC$(n,M,q)$ has an identifying algorithm with complete traceability and
$O(nM)$ time complexity.

  2. 2)

A $\bar{t}$-SC$(n,M,q)$ has an identifying algorithm with complete
traceability and $O(nM^{t})$ time complexity.

It is readily seen from Corollary 2 and Lemma 2 that the newly proposed SCLDs
could have the same traceability as FPCs, which is much more efficient than
that of SCs. In the next section, we will show that SCLDs could have a much
larger code rate than FPCs.

##  IV Bounds for binary $\bar{t}$-SCLDs

In this section we establish bounds on the largest asymptotic code rate of
binary SCs, HLDs, and SCLDs, respectively.

###  IV-A Lower bounds for binary SCs, SCLDs, HLDs

According to Theorem 1, it is desirable to consider the case of list size
$L=M^{\alpha}$ with $\alpha\in[0,1]$. To simplify the notation, we use
$M^{(\alpha)}_{\rm SCLD}(\bar{t},n,q)$ and $M^{(\alpha)}_{\rm HLD}(t,n,q)$ to
denote the largest cardinality of a $q$-ary $\bar{t}$-SCLD and a $t$-HLD with
length $n$ and list size $L=M^{\alpha}$, respectively, where $M$ is the
corresponding code size. Accordingly we denote their largest asymptotic binary
code rates as

$\displaystyle R^{(\alpha)}_{\rm SCLD}(\bar{t})$
$\displaystyle=\limsup_{n\to\infty}\frac{\log_{2}M^{(\alpha)}_{\rm
SCLD}(\bar{t},n,2)}{n},$ (2) $\displaystyle R^{(\alpha)}_{\rm HLD}(t)$
$\displaystyle=\limsup_{n\to\infty}\frac{\log_{2}M^{(\alpha)}_{\rm
HLD}(t,n,2)}{n}.$ (3)

Now we establish the following lower bounds for SCs, HLDs, and SCLDs using
random coding with expurgation. Let
$h(x)\triangleq-x\log_{2}(x)-(1-x)\log_{2}(1-x)$ be the binary entropy
function.

######  Theorem 2.

  1. 1)

$R_{\rm SC}(\bar{t})\geq\max\limits_{p\in(0,1)}\underline{R}_{\rm SC}(t,p)$,
where

$\displaystyle\underline{R}_{\rm
SC}(t,p)\triangleq\min\limits_{\begin{subarray}{c}1\leq t_{1}\leq t_{2}\leq
t,\\\ 0\leq m\leq t_{1},\\\ m\neq
t_{2}\end{subarray}}\left(\frac{-\log_{2}(1-P_{g}(t_{1},t_{2},m))}{t_{1}+t_{2}-m-1}\right),$
(4)

and

$\displaystyle P_{g}(t_{1},t_{2},m)\triangleq
p^{t_{1}}+p^{t_{2}}+(1-p)^{t_{1}}+(1-p)^{t_{2}}-2p^{t_{1}+t_{2}-m}-2(1-p)^{t_{1}+t_{2}-m}\
\ \ \text{for}\ m>0,$ $\displaystyle P_{g}(t_{1},t_{2},0)\triangleq
1-p^{t_{1}+t_{2}}-(1-p)^{t_{1}+t_{2}}-(1-p^{t_{1}}-(1-p)^{t_{1}})(1-p^{t_{2}}-(1-p)^{t_{2}}).$

  2. 2)

For any $\alpha\in(0,1)$, we have $R^{(\alpha)}_{\rm
HLD}(t)\geq\max\limits_{p\in(0,1)}\underline{R}^{(\alpha)}_{\rm HLD}(t,p)$,
where

$\underline{R}^{(\alpha)}_{\rm
HLD}(t,p)\triangleq\frac{h(p)-tph(1/t)}{1-\alpha}.$ (5)

  3. 3)

For any $\alpha\in(0,1)$, we have $R^{(\alpha)}_{\rm
SCLD}(\bar{t})\geq\max\limits_{p\in(0,1)}\min\\{\underline{R}_{\rm
SC}(t,p),\underline{R}^{(\alpha)}_{\rm HLD}(t,p)\\}$.

###### Proof:

Let $\mathcal{C}=\\{\bm{c}_{1},\bm{c}_{2},\ldots,\bm{c}_{M}\\}$ be a
collection of $M$ binary vectors of length $n$, in which each coordinate
$\bm{c}_{i}(j)$ is chosen from $\\{0,1\\}$ independently at random and equals
$1$ with probability $p$, where $p\in(0,1)$. This random ensemble will be used
in the following arguments for all three claims.

1) Consider the requirements of a $\bar{t}$-SC. A pair of distinct index sets
$I_{1}\subseteq[M]$, $I_{2}\subseteq[M]$, $|I_{1}|=t_{1}$, $|I_{2}|=t_{2}$,
$|I_{1}\cap I_{2}|=m$, $1\leq t_{1},t_{2}\leq t$, is called a bad
$(t_{1},t_{2},m)$-pair if $\text{desc}(\\{\bm{c}_{i}:i\in
I_{1}\\})=\text{desc}(\\{\bm{c}_{i}:i\in I_{2}\\})$. For notation simplicity,
we denote $\mathcal{C}_{I}=\\{\bm{c}_{i}:i\in I\\}\subseteq\mathcal{C}$ for
any $I\subseteq[M]$.

Next we estimate the expectation $E_{1}$ of the number of bad
$(t_{1},t_{2},m)$-pairs for all $(t_{1},t_{2},m)\in\Xi$ where

$\displaystyle\Xi\triangleq\\{(t_{1},t_{2},m):1\leq t_{1}\leq t_{2}\leq
t,0\leq m\leq t_{1},m\neq t_{2}\\}.$ (6)

To that end, denote

$\displaystyle\mathcal{B}(t_{1},t_{2},m)\triangleq\\{(I_{1},I_{2}):\ $
$\displaystyle
I_{1}\subseteq[M],I_{2}\subseteq[M],|I_{1}|=t_{1},|I_{2}|=t_{2},|I_{1}\cap
I_{2}|=m\\}.$

Clearly, $|\mathcal{B}(t_{1},t_{2},m)|\leq M^{t_{1}+t_{2}-m}$. Let
$P_{g}(t_{1},t_{2},m)$ denote the probability that $\mathcal{C}_{I_{1}}(i)$
and $\mathcal{C}_{I_{2}}(i)$ are different for an arbitrarily row $i$, where
$(I_{1},I_{2})\in\mathcal{B}(t_{1},t_{2},m)$. Then for any
$(I_{1},I_{2})\in\mathcal{B}(t_{1},t_{2},m)$, the probability of that
$(I_{1},I_{2})$ is bad is $(1-P_{g}(t_{1},t_{2},m))^{n}$. Now we compute
$P_{g}(t_{1},t_{2},m)$ by discussing the following two cases.

Case 1.  Consider the case of that the intersection $I_{1}\cap I_{2}$ is not
empty, i.e. $m>0$. If $\mathcal{C}_{I_{1}}(i)\neq\mathcal{C}_{I_{2}}(i)$, then
there are four possible options:

  * •

$\mathcal{C}_{I_{1}}(i)=\\{1\\}$, $\mathcal{C}_{I_{2}}(i)=\\{0,1\\}$;

  * •

$\mathcal{C}_{I_{1}}(i)=\\{0\\}$, $\mathcal{C}_{I_{2}}(i)=\\{0,1\\}$;

  * •

$\mathcal{C}_{I_{1}}(i)=\\{0,1\\}$, $\mathcal{C}_{I_{2}}(i)=\\{1\\}$;

  * •

$\mathcal{C}_{I_{1}}(i)=\\{0,1\\}$, $\mathcal{C}_{I_{2}}(i)=\\{0\\}$.

The corresponding probabilities for these four cases are:

  * •

$p^{t_{1}}(1-p^{t_{2}-m})$;

  * •

$(1-p)^{t_{1}}(1-(1-p)^{t_{2}-m})$;

  * •

$p^{t_{2}}(1-p^{t_{1}-m})$;

  * •

$(1-p)^{t_{2}}(1-(1-p)^{t_{1}-m})$.

The total probability $P_{g}(t_{1},t_{2},m)$ for $m>0$ is the sum of these
probabilities

$\displaystyle P_{g}(t_{1},t_{2},m)$
$\displaystyle=p^{t_{1}}+p^{t_{2}}+(1-p)^{t_{1}}+(1-p)^{t_{2}}-2p^{t_{1}+t_{2}-m}-2(1-p)^{t_{1}+t_{2}-m}.$

Case 2. Now consider the case of $I_{1}\cap I_{2}=\emptyset$, i.e. $m=0$. We
have

$P_{g}(t_{1},t_{2},0)=1-P_{\rm bad}(t_{1},t_{2})$

where $P_{\rm bad}(t_{1},t_{2})$ is the probability of
$\mathcal{C}_{I_{1}}(i)$ and $\mathcal{C}_{I_{2}}(i)$ coincide in coordinate
$i$. Similar to Case 1, we obtain

$\displaystyle P_{\rm bad}(t_{1},t_{2})$
$\displaystyle=p^{t_{1}+t_{2}}+(1-p)^{t_{1}+t_{2}}+(1-p^{t_{1}}-(1-p)^{t_{1}})(1-p^{t_{2}}-(1-p)^{t_{2}}).$

Based on the above, the expectation $E_{1}$ is

$\displaystyle E_{1}$
$\displaystyle=\sum\limits_{(t_{1},t_{2},m)\in\Xi}|\mathcal{B}(t_{1},t_{2},m)|(1-P_{g}(t_{1},t_{2},m))^{n}$
$\displaystyle\leq\sum\limits_{(t_{1},t_{2},m)\in\Xi}M^{t_{1}+t_{2}-m}(1-P_{g}(t_{1},t_{2},m))^{n}.$

Next we choose parameters $p\in(0,1)$ and $M=2^{nR}$ in such way that
$E_{1}<cM/(n+1)$ for an arbitrary constant $c>0$ and sufficiently large $n$.
Actually this can be satisfied if $R<\underline{R}_{\rm SC}(t,p)$ for
$p\in(0,1)$, where $\underline{R}_{\rm SC}(t,p)$ is defined in (4). Take
$c=1/4$. Then we remove one element from each bad pair. Note that there are no
repeated vectors left since their corresponding indices have been removed as
bad $(1,1,0)$-pairs. Then we can conclude that the obtained code is indeed a
$\bar{t}$-SC with size greater than $M/2$ and the rate at least
$\log_{2}(M/2)/n=R-o(1)$ as $n\to\infty$.

2) Now we consider for a HLD. Recall the randomly generated $\mathcal{C}$.

  * •

We call a vector $\bm{c}_{i}$ bad if its weight is not equal to $\lfloor
p(n+1)\rfloor$; otherwise call it good. Denote the set of all good vectors
$\bm{c}_{i}\in\mathcal{C}$ as $\mathcal{C}_{0}$. Let $E_{2}$ denote the
mathematical expectation of the number of bad vectors in $\mathcal{C}$.

  * •

For $\mathcal{C}_{0}^{\prime}\subseteq\mathcal{C}_{0}$ such that
$|\mathcal{C}_{0}^{\prime}|=t$, the subset $\mathcal{C}_{0}^{\prime}$ is
called a bad set if the size of
$\text{Res}_{\mathcal{C}_{0}}(\text{desc}(\mathcal{C}_{0}^{\prime}))$ is
greater than $L^{\prime}$, where $L^{\prime}=(\frac{M}{2n+2})^{\alpha}$. Let
$E_{3}$ denote the mathematical expectation of the number of bad sets in
$\mathcal{C}_{0}$.

Next we estimate $E_{2}$ and $E_{3}$ as follows.

(i) Consider $E_{2}$. The weight of a vector $\bm{c}\in\mathcal{C}$ can be
seen as a random variable following the Binomial distribution with parameter
$n$ and $p$, i.e. $B(n,p)$. It is known that the mode (i.e. the most frequent
value) of $B(n,p)$ is $\lfloor p(n+1)\rfloor$. Since there are totally $n+1$
possible weights, the probability that a vector $\bm{c}$ is good (i.e. with
weight $\lfloor p(n+1)\rfloor$) is no less than the average $1/(n+1)$. Hence,
the mathematical expectation $E_{2}$ of the number of bad vectors is at most
$Mn/(n+1)$.

(ii) Consider $E_{3}$. First we compute the probability that one good vector
$\bm{c}\in\mathcal{C}_{0}$ is covered by a fixed evidence vector
$\bm{d}=\text{desc}(\mathcal{C}^{\prime}_{0})$, where
$\mathcal{C}^{\prime}_{0}\subseteq\mathcal{C}_{0}$,
$|\mathcal{C}^{\prime}_{0}|=t$ and $\bm{c}\notin\mathcal{C}^{\prime}_{0}$.
Note that the number of coordinates $i$ such that $1\in\bm{d}(i)$ is at most
$t\lfloor p(n+1)\rfloor$. Therefore, the probability that
$\bm{c}\preceq\bm{d}$ can be upper bounded as

$\text{Pr}(\bm{c}\preceq\bm{d})\leq\frac{\binom{t\lfloor
p(n+1)\rfloor}{\lfloor p(n+1)\rfloor}}{\binom{n}{\lfloor
p(n+1)\rfloor}}=2^{n(tph(1/t)-h(p)+o(1))}$

as $n\to\infty$. If there exist more than
$L^{\prime}=(\frac{M}{2n+2})^{\alpha}$ vectors in $\mathcal{C}_{0}$ that are
covered by $\bm{d}$, then there exists a set of exactly $L^{\prime}-t$ vectors
in $\mathcal{C}_{0}\setminus\mathcal{C}_{0}^{\prime}$ that are covered by
$\bm{d}$. Therefore, the probability that $\bm{d}$ covers more than
$L^{\prime}$ vectors in $\mathcal{C}_{0}$ is less than

$\displaystyle\binom{|\mathcal{C}_{0}\setminus\mathcal{C}_{0}^{\prime}|}{L^{\prime}-t}2^{n(tph(1/t)-h(p)+o(1))(L^{\prime}-t)}$
$\displaystyle\leq\binom{M}{L^{\prime}-t}2^{n(tph(1/t)-h(p)+o(1))(L^{\prime}-t)}$
$\displaystyle\leq\frac{M^{L^{\prime}-t}}{(L^{\prime}-t)!}\left(M^{R^{-1}(tph(1/t)-h(p)+o(1))}\right)^{L^{\prime}}$
$\displaystyle\leq\frac{M^{L^{\prime}-t}}{(L^{\prime})^{-t}(L^{\prime})!}\left(M^{R^{-1}(tph(1/t)-h(p)+o(1))}\right)^{L^{\prime}}$
$\displaystyle\leq\frac{e^{L^{\prime}}M^{L^{\prime}-t}}{(L^{\prime})^{L^{\prime}-t}}\left(M^{R^{-1}(tph(1/t)-h(p)+o(1))}\right)^{L^{\prime}}$
$\displaystyle=M^{L^{\prime}(1-\log_{M}L^{\prime}+R^{-1}(tph(1/t)-h(p)+o(1)))}.$

Take $R<\underline{R}^{(\alpha)}_{\rm HLD}(t,p)$, where
$\underline{R}^{(\alpha)}_{\rm HLD}(t,p)$ is defined in (5). For any such $R$
the probability that $\bm{d}$ covers more than $L^{\prime}$ vectors in
$\mathcal{C}_{0}$ is at most $M^{L^{\prime}(-\varepsilon+o(1))}$ for some
positive $\varepsilon$.

Then the mathematical expectation $E_{3}$ is at most

$E_{3}<\binom{|\mathcal{C}_{0}|}{t}M^{L^{\prime}(-\varepsilon+o(1))}<M/(4n+4)$

for large enough $n$.

Delete all bad vectors and one vector from each bad set. The obtained code is
a $t$-HLD with list size $L^{\prime}$ and cardinality $\geq\frac{M}{2n+2}$.
Delete some additional vectors to obtain a code of size exactly
$M^{\prime}=\frac{M}{2n+2}$. The final code is a $t$-HLD with list size
$L^{\prime}=(M^{\prime})^{\alpha}$ and rate
$\frac{1}{n}\log_{2}\frac{M}{2n+2}=R-o(1)$ as $n\to\infty$.

3) Now we consider the requirements for SCLD based on the previous discussions
on SC and HLD. Recall the same random ensemble $\mathcal{C}$. According to the
arguments of the previous two claims, if we take

$R\leq\min\\{\underline{R}_{\rm SC}(t,p),\underline{R}^{(\alpha)}_{\rm
HLD}(t,p)\\}$

then it holds that

$E_{1}<M/(4n+4);\;E_{2}\leq Mn/(n+1);\;E_{3}<M/(4n+4),$

which implies $E_{1}+E_{2}+E_{3}<M-M/(2n+2).$

Remove all bad vectors, one vector from each bad pair, and one vector from
each bad set. The obtained code is a $\bar{t}$-SC and simultaneously a
$t$-HLD, which, according to Lemma 1, is in fact a $\bar{t}$-SCLD, with code
size $M^{\prime}=M/(2n+2)$ and list size $L^{\prime}=(M^{\prime})^{\alpha}$.
The code rate is at least $n^{-1}\log_{2}\frac{M}{2n+2}=R-o(1)$ as
$n\to\infty$. The theorem is proved. ∎

Based on the above Theorem 2, we alternatively have the following lower bound
for HLDs.

######  Theorem 3.

Let $t\geq 2$ be a positive integer and $0<\alpha<1$ be a constant. Then

$R^{(\alpha)}_{\rm
HLD}(t)\geq\frac{1}{1-\alpha}\bigg{[}h\bigg{(}\frac{1}{2^{th(1/t)}+1}\bigg{)}-\frac{th(1/t)}{2^{th(1/t)}+1}\bigg{]}.$
(7)

Furthermore, if $t$ is sufficiently large, we have

$\displaystyle R^{(\alpha)}_{\rm
HLD}(t)\geq\frac{\log_{2}e}{et(1-\alpha)}(1+o(1))\approx\frac{0.530738}{t(1-\alpha)}(1+o(1)),\quad(t\to\infty).$
(8)

###### Proof:

Recall from Theorem 2 that

$R^{(\alpha)}_{\rm
HLD}(t)\geq\max\limits_{p\in(0,1)}\frac{h(p)-tph(1/t)}{1-\alpha}.$ (9)

Let $F(p,t)\triangleq h(p)-tph(1/t)$. Then

$\displaystyle\frac{\partial F(p,t)}{\partial
p}=\log_{2}\bigg{(}\frac{1-p}{p}\bigg{)}-th(1/t).$

Setting $\frac{\partial F(p,t)}{\partial p}=0$ gives
$p^{*}=\frac{1}{2^{th(1/t)}+1}$. Clearly $0<p^{*}<1$. Then plugging $p=p^{*}$
into (9) yields the bound (7).

Next we consider the case when $t$ is sufficiently large. Taking
$p=\frac{1}{et}$, where $e\approx 2.71828$ is the Euler’s number, into
$F(p,t)$ yields

$\displaystyle F\bigg{(}p=\frac{1}{et},t\bigg{)}$
$\displaystyle=h\bigg{(}\frac{1}{et}\bigg{)}-\frac{1}{e}h\bigg{(}\frac{1}{t}\bigg{)}$
$\displaystyle=-\frac{1}{et}\log_{2}\bigg{(}\frac{1}{et}\bigg{)}-\bigg{(}1-\frac{1}{et}\bigg{)}\log_{2}\bigg{(}1-\frac{1}{et}\bigg{)}+\frac{1}{et}\log_{2}\bigg{(}\frac{1}{t}\bigg{)}+\frac{1}{e}\bigg{(}1-\frac{1}{t}\bigg{)}\log_{2}\bigg{(}1-\frac{1}{t}\bigg{)}$
$\displaystyle=\frac{1}{et}\log_{2}e-\bigg{(}1-\frac{1}{et}\bigg{)}\log_{2}\bigg{(}1-\frac{1}{et}\bigg{)}+\frac{1}{e}\bigg{(}1-\frac{1}{t}\bigg{)}\log_{2}\bigg{(}1-\frac{1}{t}\bigg{)}$
$\displaystyle=\frac{1}{et}\log_{2}e+\log_{2}e\cdot\bigg{(}1-\frac{1}{et}\bigg{)}\bigg{[}\frac{1}{et}+\frac{1}{2(et)^{2}}+\cdots\bigg{]}-\frac{\log_{2}e}{e}\cdot\bigg{(}1-\frac{1}{t}\bigg{)}\bigg{[}\frac{1}{t}+\frac{1}{2t^{2}}+\cdots\bigg{]}$
$\displaystyle=\frac{1}{et}\log_{2}e+\frac{\log_{2}e}{et}-\frac{\log_{2}e}{e}\cdot\frac{1}{t}+o\bigg{(}\frac{1}{t}\bigg{)}$
$\displaystyle=\frac{1}{et}\log_{2}e\cdot(1+o(1)),$

where the fourth equality follows from the Taylor series that
$\ln(1-x)=-\sum^{\infty}_{n=1}\frac{x^{n}}{n}=-x-\frac{x^{2}}{2}-\cdots$ for
any $x\in[-1,1]$. Hence we conclude that

$\displaystyle R^{(\alpha)}_{\rm
HLD}(t)\geq\max\limits_{p\in(0,1)}\frac{F(p,t)}{1-\alpha}\geq\frac{F(p=\frac{1}{et},t)}{1-\alpha}=\frac{\log_{2}e}{et(1-\alpha)}\cdot(1+o(1))\approx\frac{0.530738}{t(1-\alpha)}(1+o(1)),\quad(t\to\infty)$

as desired. ∎

It is worth noting that the case when $\alpha\to 0$ and $t$ goes to infinity
implies that the list size $L$ also goes to infinity, whereas the list size
$L\ll M$ where $M$ is the corresponding code cardinality. For this particular
case, the above Theorem 3 indicates that $\lim_{\alpha\to 0}R^{(\alpha)}_{\rm
HLD}(t)\geq\frac{0.530738}{t}(1+o(1))$, which coincides with the bound derived
in [40, Theorem 3].

###  IV-B Remarks

Table II illustrates numerical values of the state-of-the-art lower bounds on
the largest code rates of binary SCs, FPCs, SCLDs, in which the values in bold
are derived from Theorem 2; $R_{\rm SC}(\bar{2})$ is from [34]; $R_{\rm
FPC}(2)$ is from [36]; and $R_{\rm FPC}(t)$ for $t>2$ is from [40].

TABLE II: Lower bounds from Theorem 2 and [34, 36, 40] $t$ | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---
$R_{\rm SC}(\bar{t})\geq$ | 0.5 | 0.13834 | 0.06198 | 0.03138 | 0.02003
$R^{(1/t)}_{\rm SCLD}(\bar{t})\geq$ | 0.44452 | 0.13205 | 0.05770 | 0.03105 | 0.01997
$R_{\rm FPC}(t)\geq$ | 0.20756 | 0.07999 | 0.04392 | 0.02794 | 0.01936

It is worth noting that the bounds for $R^{(1/t)}_{\rm SCLD}(\bar{t})$ and
$R_{\rm SC}(\bar{t})$ are quite close, and much larger than $R_{\rm FPC}(t)$
(in particular, when $t$ is small). Together with the discussions in Section
III, we conclude that SCLDs have not only much more efficient traceability
than SCs but also much larger code rate than FPCs.

##  V Bounds for binary $\bar{t}$-SCLDs with constant list size

In this section we consider the existence of binary SCLDs with constant list
size. In particular, we establish a lower bound on the largest asymptotic code
rate of SCLDs with constant list size. In contrast to the previous Section IV
considering very large list size, we need to execute more careful analyses for
the case with constant list size here. The following Markov’s inequality and
Hoeffding’s inequality will be exploited.

######  Lemma 3 (e.g. [9]).

Let $Y$ be a random variables such that $Y\geq 0$, and $Z_{1},\ldots,Z_{N}$ be
independent random variables such that $a_{i}\leq Z_{i}\leq b_{i}$ for all
$i\in[N]$. Let $S_{N}=Z_{1}+\cdots+Z_{N}$. For any $\gamma>0$, we have

  1. 1.

$\text{Pr}(Y\geq\gamma)\leq\frac{\mathbb{E}[Y]}{\gamma}$ (Markov’s
inequality);

  2. 2.

$\text{Pr}(|S_{N}-\mathbb{E}[S_{N}]|\geq\gamma)\leq
2\cdot\text{exp}\Big{(}-\frac{2\gamma^{2}}{\sum_{i=1}^{N}(b_{i}-a_{i})^{2}}\Big{)}$
(Hoeffding’s inequality),

where $\mathbb{E}[Y]$ is the expectation of $Y$.

######  Theorem 4.

Let $t\geq 2$ be a positive integer. Then

$\displaystyle R_{\rm
SCLD}(\bar{t};L)\geq\max\limits_{p\in(0,1/2]}\min\big{\\{}\underline{R}_{\rm
SC}(t,p),\underline{R}_{\rm HLD}(t,p,L)\big{\\}},$ (10)

where $\underline{R}_{\rm SC}(t,p)$ is defined in (4) and

$\displaystyle\underline{R}_{\rm HLD}(t,p,L)$ $\displaystyle\triangleq
h(p)+\frac{B(t,p,L)}{L}$ (11) $\displaystyle B(t,p,L)$
$\displaystyle=p\log_{2}\left(\frac{q_{1}(t,L,1-z)}{q_{1}(t,L,1-z)+q_{2}(t,L,1-z)}\right)+(1-p)\log_{2}\left(\frac{q_{1}(t,L,z)}{q_{1}(t,L,z)+q_{2}(t,L,z)}\right)$
(12) $\displaystyle q_{1}(t,L,z)$ $\displaystyle=z^{t}(z-z^{t})^{L-t+1}$ (13)
$\displaystyle q_{2}(t,L,z)$
$\displaystyle=(z-z^{t})(1-z^{t}-(1-z)^{t})^{L-t+1}$ (14)

and $z\in(0,1)$ is a unique root of the equation

$\displaystyle
p(q_{1}(t,L,z)+q_{2}(t,L,z))=(1-p)(q_{1}(t,L,1-z)+q_{2}(t,L,1-z)).$ (15)

###### Proof:

Let $\mathcal{C}=\\{\bm{c}_{1},\bm{c}_{2},\ldots,\bm{c}_{M}\\}$ be a
collection of $M=2^{nR}$ binary vectors of length $n$, in which each
coordinate $\bm{c}_{i}(j)$ is chosen from $\\{0,1\\}$ independently at random
and equals $1$ with probability $p$, where $p\in(0,1/2]$. We now aim to remove
some vectors, which violate the definition of SCLD, from $\mathcal{C}$. To
that end, we define bad items as follows.

  * •

Call a pair of distinct index sets $(I_{1},I_{2})$, where $I_{1}\subseteq[M]$,
$I_{2}\subseteq[M]$, $|I_{1}|=t_{1}$, $|I_{2}|=t_{2}$, $|I_{1}\cap I_{2}|=m$,
$1\leq t_{1},t_{2}\leq t$, a bad $(t_{1},t_{2},m)$-pair if
$\text{desc}(\\{\bm{c}_{i}:i\in I_{1}\\})=\text{desc}(\\{\bm{c}_{i}:i\in
I_{2}\\})$. Denote the number of bad $(t_{1},t_{2},m)$-pairs for all
$(t_{1},t_{2},m)\in\Xi$ as $X_{1}$, where $\Xi$ is defined as (6).

  * •

Call a vector $\bm{c}_{i}$ bad if its weight is not equal to $\lfloor
p(n+1)\rfloor$; otherwise, call it good. Denote the set of all good vectors
$\bm{c}_{i}$ in $\mathcal{C}$ as $\mathcal{C}_{0}$. Clearly
$\mathcal{C}_{0}\subseteq\mathcal{C}$. Denote the number of good vectors in
$\mathcal{C}$ as $X_{2}$ and $X_{2}=|\mathcal{C}_{0}|$.

  * •

Call a pair of distinct sets $(\mathcal{C}_{1},\mathcal{C}_{2})$, where
$\mathcal{C}_{1},\mathcal{C}_{2}\subseteq\mathcal{C}_{0}$,
$|\mathcal{C}_{1}|=t$, $|\mathcal{C}_{2}|=L+1$, bad if
$\text{desc}(\mathcal{C}_{1})$ covers all codewords from $\mathcal{C}_{2}$.
Denote the number of bad pairs of sets in $\mathcal{C}_{0}$ as $X_{3}$.

Now we would like to prove the following three claims.

######  Claim 1.

$\text{Pr}\Big{(}X_{1}<\frac{M}{16(n+1)}\Big{)}>\frac{3}{4}$.

In fact, the code $\mathcal{C}$ is the same random code as in the proof of
Theorem 2, where we estimated the mathematical expectation of the number of
bad $(t_{1},t_{2},m)$-pairs as $\mathbb{E}[X_{1}]<cM/(n+1)$ in the case that
$R<\underline{R}_{\rm SC}(t,p)$ for an arbitrary constant $c$ and large enough
$n$. Here we take $c=1/64$. Then we obtain

$\displaystyle\text{Pr}\Big{(}X_{1}<\frac{M}{16(n+1)}\Big{)}=1-\text{Pr}\Big{(}X_{1}\geq\frac{M}{16(n+1)}\Big{)}\geq
1-\frac{\mathbb{E}[X_{1}]}{\frac{M}{16(n+1)}}>1-\frac{\frac{M}{64(n+1)}}{\frac{M}{16(n+1)}}=\frac{3}{4}$

where the first inequality follows from the Markov’s inequality in Lemma 3.
This proves Claim 1.

######  Claim 2.

$\text{Pr}\Big{(}X_{2}\geq\frac{M}{2(n+1)}\Big{)}=1-o(1)$ as $n\to\infty$.

In fact, recall that, in the proof of Theorem 2, we showed that the
probability that a vector is good is at least $1/(n+1)$. It implies that the
expectation of the number of good vectors $\mathbb{E}[X_{2}]\geq M/(n+1)$.
Thus

$\displaystyle\text{Pr}\Big{(}X_{2}<\frac{M}{2(n+1)}\Big{)}\leq\text{Pr}\Big{(}|X_{2}-\mathbb{E}[X_{2}]|\geq\frac{M}{2(n+1)}\Big{)}\leq
2\exp\left(-\frac{M}{2(n+1)^{2}}\right)$ (16)

where the second inequality follows from the Hoeffding’s inequality in Lemma
3. Now we have

$\displaystyle\text{Pr}\Big{(}X_{2}\geq\frac{M}{2(n+1)}\Big{)}=1-\text{Pr}\Big{(}X_{2}<\frac{M}{2(n+1)}\Big{)}\geq
1-2\exp\left(-\frac{M}{2(n+1)^{2}}\right)=1-o(1)\quad(n\to\infty)$

where the inequality follows from (16). This proves Claim 2.

######  Claim 3.

$\text{Pr}\Big{(}X_{3}<\frac{3X_{2}}{4}\Big{)}\geq\frac{1}{3}$.

In fact, notice that the code $\mathcal{C}_{0}$ consisting of all good vectors
from $\mathcal{C}$ can be seen as a random code with a fixed weight $\lfloor
p(n+1)\rfloor$ and cardinality $|\mathcal{C}_{0}|=X_{2}$, whose distribution
is the same as in the case when every codeword is taken independently and
equiprobably from the set of all vectors of weight $\lfloor p(n+1)\rfloor$.
This fact coincides with the assumption in the proof of [40, Theorem 3], where
a fixed weight ensemble was considered as well. It was shown in [40, Theorem
3] that if the code rate $R_{\mathcal{C}_{0}}=\frac{1}{n}\log_{2}(X_{2})$ of
$\mathcal{C}_{0}$ is smaller than $\underline{R}_{\rm HLD}(t,p,L)$, where
$\underline{R}_{\rm HLD}(t,p,L)$ is defined from (11)-(15), then the
mathematical expectation of the number $X_{3}$ of bad pairs of sets satisfies
$\mathbb{E}[X_{3}]\leq X_{2}/2$ for large enough $n$. Thus we have

$\displaystyle\text{Pr}\Big{(}X_{3}<\frac{3X_{2}}{4}\Big{)}=1-\text{Pr}\Big{(}X_{3}\geq\frac{3X_{2}}{4}\Big{)}\geq
1-\frac{\mathbb{E}[X_{3}]}{\frac{3X_{2}}{4}}\geq
1-\frac{\frac{X_{2}}{2}}{\frac{3X_{2}}{4}}=\frac{1}{3}$

where the first inequality follows from the Markov’s inequality in Lemma 3.
This proves Claim 3.

Based on Claims 1-3, we conclude that if $R<\min\big{\\{}\underline{R}_{\rm
SC}(t,p),\underline{R}_{\rm HLD}(t,p,L)\big{\\}}$, with positive probability
all three conditions below could be satisfied:

$\displaystyle X_{1}<\frac{M}{16(n+1)}\ \ \text{and}\ \
X_{2}\geq\frac{M}{2(n+1)}\ \ \text{and}\ \ X_{3}<\frac{3X_{2}}{4}.$

By this, from the code $\mathcal{C}_{0}$ we delete one vector from each bad
pair of sets and one vector from each bad $(t_{1},t_{2},m)$-pair for all
$(t_{1},t_{2},m)\in\Xi$. It is easily verified that the resulting code is a
$\bar{t}$-SCLD$\big{(}n,M_{0},2;L)$ with code size

$M_{0}\geq
X_{2}-X_{1}-X_{3}>\frac{X_{2}}{4}-X_{1}>\frac{M}{8(n+1)}-\frac{M}{16(n+1)}=\frac{M}{16(n+1)}$

and code rate $\frac{1}{n}\log_{2}M_{0}\geq R+o(1)$ as $n\to\infty$. This
completes the proof of Theorem 4. ∎

Table III illustrates the numerical calculation results for $t=2,3$ from
Theorem 4. It is worth noting from the case $t=3$ that even the list size is
not sufficiently large, the code rate of binary SCLDs is very good already, in
comparison with Table II concerning asymptotically large list size. In the
next Section VI, we will show this interesting phenomenon is more manifest for
$q$-ary SCLDs with sufficiently large alphabet size $q$.

TABLE III: Lower bounds for binary SCLDs with constant list size via Theorem 4 $(t,L)$ | $(2,3)$ | $(2,4)$ | $(2,5)$ | $(2,6)$ | $(2,7)$
---|---|---|---|---|---
$R_{\rm SCLD}(\bar{t},L)\geq$ | $0.245655$ | $0.263492$ | $0.274428$ | $0.281927$ | $0.287402$
$(t,L)$ | $(3,4)$ | $(3,5)$ | $(3,6)$ | $(3,7)$ | $(3,8)$
$R_{\rm SCLD}(\bar{t},L)\geq$ | $0.115118$ | $0.126598$ | $0.129504$ | $0.130385$ | $0.130601$

##  VI Bounds for $q$-ary SCLDs

In this section we provide lower bounds for the largest possible code rate of
$q$-ary SCLDs with large $q$. Interestingly, our bound for $q$-ary SCLDs
matches the (almost optimal) bound of $q$-ary SCs, which implies that the
established $q$-ary SCLDs are almost optimal as well. Precisely, we prove the
following theorem.

######  Theorem 5.

Let $t,n,L$ be positive integers. Then

$R_{\rm SCLD}(\bar{t},n;L)\geq\begin{cases}2/3&\text{if $t=2$ and $L\geq
3$,}\\\ 1/(t-1)&\text{if $t>2$ and $L\geq t+1$}.\end{cases}$

###### Proof:

Let $\mathcal{C}=\\{\bm{c}_{1},\bm{c}_{2},\ldots,\bm{c}_{M}\\}$ be a
collection of $M=\varepsilon(n,t)q^{nR_{\delta}}$ $q$-ary vectors of length
$n$, in which each coordinate $\bm{c}_{i}(j)$ is chosen independently at
random and equal to $k$ with probability $1/q$ for each $k\in Q$,
$\varepsilon(n,t)$ is a sufficiently small positive constant less than $1$
depending only on $n$ and $t$, and

$R_{\delta}=\begin{cases}2/3-\delta&\text{if $t=2$, }\\\
1/(t-1)-\delta&\text{if $t>2$}\end{cases}$ (17)

for an arbitrary small $\delta>0$. Next we discuss the two requirements of
SCLD in Definition 1.

(I) Consider the first requirement of the separable property. We use the
following result from [4].

######  Claim 4 ([4, Theorems 4 and 5]).

For arbitrary small $\delta>0$ and sufficiently small $0<\varepsilon(n,t)<1$
there exists a random set $\mathcal{C}^{\prime}\subseteq\mathcal{C}$ such that

  * •

for all distinct
$\mathcal{C}_{1},\mathcal{C}_{2}\subseteq\mathcal{C}^{\prime}$ with
$|\mathcal{C}_{1}|\leq t$ and $|\mathcal{C}_{2}|\leq t$, it holds that
$\text{desc}(\mathcal{C}_{1})\neq\text{desc}(\mathcal{C}_{2})$; and

  * •

the expectation of $|\mathcal{C}^{\prime}|$ is at least $\kappa
q^{nR_{\delta}}$, where $\kappa$ is any positive constant less than
${\varepsilon}-{\varepsilon}^{2}{\kappa}^{\prime}$, and ${\kappa}^{\prime}$ is
a constant depending only on $n$ and $t$.

In other words, it is possible to remove a small number of vectors (in
$\mathcal{C}\setminus\mathcal{C}^{\prime}$) from $\mathcal{C}$ such that the
set of remained vectors $\mathcal{C}^{\prime}\subseteq\mathcal{C}$ meets the
first requirement of SCLD in Definition 1.

(II) We now consider the second requirement of SCLD in Definition 1. For
$\mathcal{C}_{0}\subseteq\mathcal{C}$, $|\mathcal{C}_{0}|=t$, we call
$\mathcal{C}_{0}$ a bad set if

$|\text{Res}_{\mathcal{C}}(\text{desc}(\mathcal{C}_{0}))|>L.$

Let $E$ denote the expectation of the number of bad sets in $\mathcal{C}$. We
are going to estimate $E$.

Consider a fixed evidence vector $\mathbf{d}$ produced by a coalition of $t$
colluders holding fingerprints in $\mathcal{C}$. The probability of that
$\mathbf{d}$ covers more than $L$ vectors in $\mathcal{C}$ is upper bounded by

$\displaystyle\binom{M}{L+1-t}(t/q)^{n(L+1-t)}$
$\displaystyle\leq\frac{M^{L+1-t}}{(L+1-t)!}q^{n(\log_{q}t-1)(L+1-t)}$
$\displaystyle\leq\frac{M^{L+1-t}}{(L+1-t)!}\Big{(}\frac{M}{\varepsilon}\Big{)}^{R_{\delta}^{-1}(\log_{q}t-1)(L+1-t)}$
$\displaystyle\leq\Big{(}\frac{M}{\varepsilon}\Big{)}^{(L+1-t)(1+R_{\delta}^{-1}(\log_{q}t-1))}/(L+1-t)!.$

By the linearity of expectation, the expectation $E$ of the number of bad sets
is at most

$E<M^{t}\Big{(}\frac{M}{{\varepsilon}}\Big{)}^{(L+1-t)(1+R_{\delta}^{-1}(\log_{q}t-1))}/(L+1-t)!$

Specifically, we have the following for an arbitrary small $\delta>0$:

  * •

For $t=2$, $R_{\delta}=2/3-\delta$, $L=3$, and $q>2^{\frac{2}{3\delta}}$, we
obtain

$E<\frac{1}{2}\Big{(}\frac{M}{\varepsilon}\Big{)}^{4+2\frac{\log_{q}2-1}{2/3-\delta}}=o(M)=o(q^{nR_{\delta}}).$

  * •

For $t>2$, $R_{\delta}=\frac{1}{t-1}-\delta$, $L=t+1$, and
$q>t^{\frac{2t-2}{t-3+(t^{2}-1)\delta}}$, we have

$\displaystyle E$
$\displaystyle<\frac{1}{2}\Big{(}\frac{M}{\varepsilon}\Big{)}^{t+2+2\frac{\log_{q}t-1}{1/(t-1)-\delta}}=o(M)=o(q^{nR_{\delta}}).$

Based on (I) and (II), we remove the vectors in
$\mathcal{C}\setminus\mathcal{C}^{\prime}$ and also remove a vector from each
bad set in $\mathcal{C}$. It is easily verified the obtained code is a
$\bar{t}$-SCLD, and the expectation of code size is at least $\kappa
q^{nR_{\delta}}(1-o(1))$. Therefore, together with Lemma 1, we conclude that
there exists a $\bar{t}$-SCLD$(n,M^{\prime},q;L)$ with $L\geq t+1$ and
$M^{\prime}\geq\kappa^{\prime}q^{nR_{\delta}}$, where $\kappa^{\prime}$ is a
constant depending only on $n$ and $t$. In other words, we have shown that the
code rate of $q$-ary $\bar{t}$-SCLD codes is at least $R_{\delta}$ for any
$\delta>0$. Taking limit as $\delta\to 0$ we complete the proof. ∎

It is quite remarkable that the code rate of SCLDs in Theorem 5 achieves the
best-known (and almost optimal) code rate of SCs [4, 27]. Also we notice an
intriguing property that the list size in $\bar{t}$-SCLDs just needs to be a
little bit larger than $t$, i.e. $L\geq t+1$. Together with Section III, we
conclude that SCLDs could have not only the same code rate as SCs for large
$q$ but also much more efficient decoding than SCs.

##  VII Constructions for SCLDs

In this section, we provide explicit constructions for SCLDs and discuss their
corresponding identifying algorithms.

###  VII-A SCLDs from generalized packings

Since the code length of a $\bar{t}$-SCLD corresponds to the number of
orthonormal basis signals in the multimedia content, and the code size
corresponds to the number of authorized users, it is thus desirable to
construct $\bar{t}$-SCLDs with large code size while keeping their lengths
short. In this subsection, we construct $\bar{2}$-SCLD$(2,M,q^{\prime};3)$
from a combinatorial structure called generalized packings [12].

######  Definition 3.

Let $K$ be a subset of nonnegative integers, and let $v,b$ be two positive
integers. A generalized $(v,b,K,1)$ packing is a set system $(X,{\cal B})$
where $X$ is a set of $v$ elements and ${\cal B}$ is a set of $b$ subsets of
$X$ called blocks that satisfy

  1. 1)

$|B|\in K$ for any $B\in{\cal B}$;

  2. 2)

every pair of distinct elements of $X$ occurs in at most one block of ${\cal
B}$.

In a generalized $(v,b,K,1)$ packing, if $K=\\{k\\}$ for some $k>1$ and every
pair of distinct elements of $X$ occurs in exactly one block, then it is
usually called a balanced incomplete block design, or briefly $(v,k,1)$-BIBD.
A $(q^{2}+q+1,q+1,1)$-BIBD with $q\geq 2$ corresponds to a projective plane of
order $q$.

######  Construction 1.

Let $(X,{\cal B})$ be a generalized $(v,v,K,1)$ packing with
$X=\\{0,1,\ldots,v-1\\}$ and ${\cal B}=\\{B_{0},B_{1},\ldots,$ $B_{v-1}\\}$.
Then ${\cal C}=C_{0}\cup C_{1}\cup\cdots\cup C_{v-1}$, with
$C_{i}=\\{(i,b):b\in B_{i}\\}$ if $B_{i}\neq\emptyset$ and $C_{i}=\emptyset$
if $B_{i}=\emptyset$, is a $\bar{2}$-SCLD$(2,M,v;3)$ defined over $X$ with
$M=|B_{0}|+|B_{1}|+\cdots+|B_{v-1}|$.

###### Proof:

It is shown in [7] that ${\cal C}$ is a $\bar{2}$-SC$(2,M,v)$ defined over $X$
with $M=|B_{0}|+|B_{1}|+\cdots+|B_{v-1}|$. To prove its list size is $3$,
notice that $\text{desc}(\\{(i,a),(j,b)\\})$ cannot cover any additional
codeword if $i=j$, and covers at most one codeword $(i,b)$ or $(j,a)$ if
$i\neq j$, but not both. Otherwise, $\text{desc}(\\{(i,a),(j,b)\\})$ would be
equal to $\text{desc}(\\{(i,b),(j,a)\\})$, a contradiction to the fact that
${\cal C}$ is a $\bar{2}$-SC$(2,M,v)$. This completes the proof. ∎

As an immediate consequence of Construction 1, we have the following.

######  Corollary 3.

For any prime power $q$, there exist

  1. 1)

a $\bar{2}$-SCLD$(2,(q+1)(q^{2}+q+1),q^{2}+q+1;3)$;

  2. 2)

a $\bar{2}$-SCLD$(2,q^{3}+2q^{2},q^{2}+q;3)$.

###### Proof:

Claim 1) follows from the well-known fact that there exists a projective plane
of order $q$ if $q$ is a prime power [12]. Delete one block from a projective
plane and an element from this block, we obtain a generalized
$(q^{2}+q,q^{2}+q,\\{q,q+1\\},1)$ packing with $q$ blocks of size $q$ and
$q^{2}$ blocks of size $q+1$. This gives a
$\bar{2}$-SCLD$(2,q^{3}+2q^{2},q^{2}+q;3)$, as desired. ∎

According to Lemma 1, the largest code size of $\bar{t}$-SCLDs can be upper
bounded by that of $\bar{t}$-SCs. By [7], we conclude that the above two
$\bar{2}$-SCLDs of length $2$ have the largest possible code size,
respectively, given the alphabet size.

###  VII-B A concatenated construction

In this subsection, we provide a concatenated construction which allows to
derive SCLDs with small alphabet size from SCLDs with large alphabet size
(e.g. the constructions in Section VII-A).

######  Construction 2.

Let $2\leq q\leq q^{\prime}$ be two integers. Let ${\mathcal{A}}$ be a
$t$-FPC$(n_{1},q^{\prime},q)$ over the alphabet $Q$ and ${\mathcal{B}}$ be a
$\bar{t}$-SCLD$(n_{2},M,q^{\prime};L)$ over the alphabet $Q^{\prime}$. Define
a bijection $\phi:Q^{\prime}\to{\mathcal{A}}$. Let ${\mathcal{C}}$ be the code
defined by

$\displaystyle\Phi:{\mathcal{B}}$ $\displaystyle\to{\mathcal{C}}$
$\displaystyle{\bf b}=({\bf b}(1),\ldots,{\bf b}(n_{1}))$
$\displaystyle\mapsto\Phi({\bf b})=(\phi({\bf b}(1)),\ldots,\phi({\bf
b}(n_{1}))).$

Then ${\mathcal{C}}$ is a $\bar{t}$-SCLD$(n_{1}n_{2},M,q;L)$ over $Q$.

###### Proof:

It is obvious that ${\mathcal{C}}$ is an $(n_{1}n_{2},M,q)$ code over $Q$.
Since any $t$-FPC is a $\bar{t}$-SC, by [8, Lemma 5.4], we know that
${\mathcal{C}}$ is a $\bar{t}$-SC$(n_{1}n_{2},M,q)$. It suffices to show that
${\mathcal{C}}$ is also a $t$-HLD$(n_{1}n_{2},M,q;L)$. Notice that
${\mathcal{A}}$ is a $t$-FPC$(n_{1},q^{\prime},q)$ so that no codeword outside
a coalition can be covered by the descendant code of the coalition, we know
that any coalition $\\{\Phi({\bf b}_{1}),\ldots,\Phi({\bf b}_{s})\\}$, $s\leq
t$, in ${\mathcal{C}}$ corresponds exactly to a coalition $\\{{\bf
b}_{1},\ldots,{\bf b}_{s}\\}$ in ${\mathcal{B}}$. This implies that there are
at most $L$ codewords in ${\mathcal{C}}$ covered by $\text{desc}(\\{\Phi({\bf
b}_{1}),\ldots,\Phi({\bf b}_{s})\\})$, i.e., ${\mathcal{C}}$ is a
$t$-HLD$(n_{1}n_{2},M,q;L)$. According to Lemma 1, the conclusion follows. ∎

In order to use Construction 2 to derive SCLDs, we recall two known
constructions of frameproof codes as follows.

######  Construction 3 ([3]).

Let $l\geq 2$ and $t\geq 2$ be two integers, and $q\geq l$ be a prime power.
Let ${\alpha}_{1},{\alpha}_{2},\ldots,{\alpha}_{l}\in\text{GF}(q)$ be
distinct. Define a code ${\mathcal{C}}$ over $\text{GF}(q)$ by

${\mathcal{C}}=\\{(f({\alpha}_{1}),f({\alpha}_{2}),\ldots,f({\alpha}_{l})):f\in\text{GF}(q)[x]{\rm\
and\ deg}(f)<\lceil l/t\rceil\\}.$

Then ${\mathcal{C}}$ is a $t$-FPC$(l,q^{\lceil l/t\rceil},q)$.

######  Construction 4 ([3]).

Let $l\geq 4$ be an even integer. Let $m\geq l+1$ be a prime power and
$q=m^{2}+1$. Let
${\beta}_{0},{\beta}_{1},{\alpha}_{1},{\alpha}_{2},\ldots,{\alpha}_{l-1}\in\text{GF}(m)$
be distinct. Define

$\displaystyle{\mathcal{C}}_{1}$
$\displaystyle=\Big{\\{}(\infty,(f({\alpha}_{1}),g({\alpha}_{1})),\ldots,(f({\alpha}_{l-1}),g({\alpha}_{l-1})):f,g\in\text{GF}(m)[x],{\rm\
deg}(f)=\frac{l}{2}-1,{\rm deg}(g)\leq\frac{l}{2}-1\Big{\\}},$
$\displaystyle{\mathcal{C}}_{2}$
$\displaystyle=\Big{\\{}\big{(}(t({\beta}_{0}),t({\beta}_{1})),(s({\alpha}_{1}),t({\alpha}_{1})),\ldots,(s({\alpha}_{l-1}),t({\alpha}_{l-1}))\big{)}:s,t\in\text{GF}(m)[x],{\rm\
deg}(s)\leq\frac{l}{2}-2,{\rm deg}(t)\leq\frac{l}{2}\Big{\\}}.$

Then the code ${\mathcal{C}}={\mathcal{C}}_{1}\cup{\mathcal{C}}_{2}$ is a
$2$-FPC$(l,2(q-1)^{l/2}(1-1/(2\sqrt{q-1}),q)$ defined over
$F=\\{\infty\\}\cup(\text{GF}(m))^{2}$.

Apply Construction 2 with Corollary 3 and Constructions 3, 4, we immediately
obtain the followings.

######  Corollary 4.

Let $n$ be a prime power.

  1. 1)

For any integer $l\geq 2$, there exists a
$\bar{2}$-SCLD$(2l,(n+1)(n^{2}+n+1),q;3)$ for any prime power $q$ such that
$q\geq l$ and $q^{\lceil l/2\rceil}\geq n^{2}+n+1$.

  2. 2)

For any even $l\geq 4$, there exists a
$\bar{2}$-SCLD$(2l,(n+1)(n^{2}+n+1),q;3)$ for any $q=m^{2}+1$ where $m\geq
l+1$ is a prime power such that $2(q-1)^{l/2}(1-1/(2\sqrt{q-1}))\geq
n^{2}+n+1$.

  3. 3)

For any integer $l\geq 2$, there exists a
$\bar{2}$-SCLD$(2l,n^{3}+2n^{2},q;3)$ for any prime power $q$ such that $q\geq
l$ and $q^{\lceil l/2\rceil}\geq n^{2}+n$.

  4. 4)

For any even $l\geq 4$, there exists a $\bar{2}$-SCLD$(2l,n^{3}+2n^{2},q;3)$
for any $q=m^{2}+1$ where $m\geq l+1$ is a prime power such that
$2(q-1)^{l/2}(1-1/(2\sqrt{q-1}))\geq n^{2}+n$.

###  VII-C An algebraic construction with efficient decoding

In this subsection we show an algebraic construction for binary
$\bar{2}$-SCLDs with both of a high code rate and an efficient identifying
algorithm in time $O(\operatorname{polylog}(M))$. The following construction
is originally from [34].

######  Construction 5 ([34]).

Let $l\geq 2$ be an integer. For each element $\mathbf{x}\in\text{GF}(2^{l})$,
$\mathbf{x}$ can be represented as a binary vector of length $l$ [33]. Define
a binary code $\mathcal{C}$ as

$\displaystyle\mathcal{C}=\\{(\mathbf{x},\mathbf{x^{3}}):\,\mathbf{x}\in\text{GF}(2^{l})\\}.$

Then $\mathcal{C}$ is a $\bar{2}$-SCLD$(2l,2^{l},2;2^{l})$.

It is readily seen that the above $\bar{2}$-SCLDs with list size $L=M=2^{l}$
has code rate $1/2$, which is larger than the code rate obtained from the
random coding method in Theorem 2. Notably, we find that the $\bar{2}$-SCLDs
via Construction 5 could perform identification very efficiently as follows.

######  Theorem 6.

For a $\bar{2}$-SCLD$(n,M,2;M)$ derived from Construction 5, there exists an
identifying algorithm with time complexity
$O(\operatorname{poly}(n))=O(\operatorname{polylog}(M))$.

Algorithm 2 A solution for the quadratic equation (19) over $\text{GF}(2^{l})$
[6]

Input: a primitive element $\omega$ of $\text{GF}(2^{l})$ such that the trace
of $\omega$ equals to $1$, i.e. $\sum\limits_{i=0}^{l-1}\omega^{2^{i}}=1$;
the constant term $k=\mathbf{1}+\mathbf{v}/\mathbf{u^{3}}\in\text{GF}(2^{l})$

1:if $l\pmod{2}==1$ then $\triangleright$ Case 1

2: $\mathbf{z}=\sum\limits_{i=0}^{(l-1)/2}k^{2^{2i}}$

3:else

4: $T(k)=\sum\limits_{i=0}^{(l-2)/2}k^{2^{2i}}$

5:end if

6:if $l\pmod{4}==2$ and $T(k)==0$ then $\triangleright$ Case 2

7: $\mathbf{z}=\sum\limits_{i=0}^{(l-6)/4}(k+k^{2})^{2^{2+4i}}$

8:else if $l\pmod{4}==2$ and $T(k)==1$ then $\triangleright$ Case 3

9:
$\mathbf{z}=\omega^{(2^{l}-1)/3}+\sum\limits_{i=0}^{(l-6)/4}(k+k^{2})^{2^{2+4i}}$

10:else if $l\pmod{4}==0$ and $T(k)==1$ then $\triangleright$ Case 4

11:
$S=\sum\limits_{j=1}^{l/4-1}\sum\limits_{i=j}^{l/4-1}k^{2^{2i-1+l/2}+2^{2j-2}}$

12:
$\mathbf{z}=S+S^{2}+k^{2^{l-1}}\bigg{(}1+\sum\limits_{i=0}^{l/4-1}k^{2^{2i+l/2}}\bigg{)}$

13:else if $l\pmod{4}==0$ and $T(k)==0$ then $\triangleright$ Case 5

14:
$S_{1}=\sum\limits_{j=1}^{l/4-1}\sum\limits_{i=j}^{l/4-1}(\omega+\omega^{2}+k)^{2^{2i-1+l/2}+2^{2j-2}}$

15:
$\mathbf{z}=\omega+S_{1}+S_{1}^{2}+(\omega+\omega^{2}+k)^{2^{l-1}}\bigg{(}1+\sum\limits_{i=0}^{l/4-1}(\omega+\omega^{2}+k)^{2^{2i+l/2}}\bigg{)}$

16:end if

Output: a solution $\mathbf{z}\in\text{GF}(2^{l})$ for equation (19)

###### Proof:

Let
$\mathcal{C}=\\{(\mathbf{x},\mathbf{x^{3}}):\,\mathbf{x}\in\text{GF}(2^{l})\\}$
be a $\bar{2}$-SCLD$(n,M,2;M)$ derived from Construction 5 with $n=2l$ and
$M=2^{l}$. For any coalition of size two, say $(\mathbf{x},\mathbf{x^{3}})$
and $(\mathbf{y},\mathbf{y^{3}})$ with
$\mathbf{x}\neq\mathbf{y}\in\text{GF}(2^{l})$, their evidence vector $\bm{d}$
implies $(\mathbf{u},\mathbf{v})$, $\mathbf{u},\mathbf{v}\in\text{GF}(2^{l})$,
such that

$\displaystyle\mathbf{x}+\mathbf{y}=\mathbf{u}\quad\text{and}\quad\mathbf{x^{3}}+\mathbf{y^{3}}=\mathbf{v},$
(18)

where $\mathbf{u}(i)=1$ if $\mathbf{d}(i)=\\{0,1\\}$, $\mathbf{u}(i)=0$ if
$\mathbf{d}(i)=\\{0\\}$ or $\\{1\\}$, and $\mathbf{v}(i)=1$ if
$\mathbf{d}(l+i)=\\{0,1\\}$, $\mathbf{v}(i)=0$ if $\mathbf{d}(l+i)=\\{0\\}$ or
$\\{1\\}$ for $1\leq i\leq l$. Clearly, $\mathbf{u}\neq 0$. The identifying
aims to find the solutions $\mathbf{x}$ and $\mathbf{y}$ using
$\mathbf{u},\mathbf{v}$ in (18). To that end, we first note that (18) can be
transferred to
$\mathbf{x^{2}}+\mathbf{u}\cdot\mathbf{x}+\mathbf{u^{2}}+\mathbf{v}/\mathbf{u}=\mathbf{0}.$
Let $\mathbf{z}=\mathbf{x}/\mathbf{u}$. Then we have

$\displaystyle\mathbf{z^{2}}+\mathbf{z}+\mathbf{1}+\mathbf{v}/\mathbf{u^{3}}=0.$
(19)

Next we show that one solution of (19) in $\text{GF}(2^{l})$ could be
determined by means of Algorithm 2, in which we use a result that
$\text{GF}(2^{l})$ contains a primitive element of $trace$ equal to $1$ from
[35, Theorem 2] as well.

Indeed, Algorithm 2 can determine a solution $\mathbf{z}$ of quadratic
equation (19) in time $O(\operatorname{poly}(l))$. Together with the relation
$\mathbf{x}=\mathbf{u}\cdot\mathbf{z}$ and the symmetry of $\mathbf{x}$ and
$\mathbf{y}$, the solution of (18) can be determined. In other words, the
decoding of $\mathcal{C}$ (based on Algorithm 2) can be done in time
$O(\operatorname{poly}(l))=O(\operatorname{poly}(n))=O(\operatorname{polylog}(M))$,
as required. ∎

##  VIII Two-stage dynamic traitor tracing

In this section we discuss the two-stage traitor tracing for the dynamic
scenario. In particular, we establish a two-stage dynamic traitor tracing
framework based on HLDs and SCLDs. It is shown that it could provide not only
more efficient decoding algorithms but also much larger code rate (i.e.
accommodate more users) than SCLDs in the static scenario.

######  Theorem 7.

Let $t$ be a positive integer and the number of traitors be no more than $t$.
There exists a two-stage dynamic traitor tracing scheme accommodating
$M=\Omega(2^{nR_{\rm TDTT}(\alpha,\beta,t)})$ users and with complete
traceability in time $O(nM^{\max\\{1,\alpha\beta t\\}})$, where $R_{\rm
TDTT}(\alpha,\beta,t)=\frac{1}{2}R^{(\alpha)}_{\rm HLD}(t)$ and
$0\leq\alpha,\beta\leq 1$ such that $\alpha\cdot R^{(\alpha)}_{\rm HLD}(t)\leq
R^{(\beta)}_{\rm SCLD}(\bar{t})$.

###### Proof:

Suppose the total number of authorized users is $M$ and the total number of
traitors is at most $t$, where $t\leq M$. We build a two-stage traitor tracing
scheme as in Algorithm 3.

Algorithm 3 Two-stage dynamic traitor tracing algorithm

Input: $t$-HLD code $\mathcal{C}=\\{\bm{c}_{1},\ldots,\bm{c}_{M}\\}$ with list
size $L^{(1)}=M^{\alpha}$; the evidence vector
$\mathbf{d}^{(1)}\in\mathcal{P}(Q)^{n}$ $\triangleright$ Stage 1

1:$\mathcal{T}=\emptyset$, $\mathcal{W}=\emptyset$. $\triangleright$
Initialize the candidate sets

2:for each $j\in[M]$ do

3: if $\mathbf{c}_{j}\preceq\mathbf{{d}}^{(1)}$ then

4: $\mathcal{W}=\mathcal{W}\cup\\{j\\}$;

5: end if

6:end for

Output: the index set $\mathcal{W}$
Input: $\bar{t}$-SCLD code
$\mathcal{C}=\\{\bm{c}_{1},\ldots,\bm{c}_{|\mathcal{W}|}\\}$ with list size
$L^{(2)}=|\mathcal{W}|^{\beta}$; the evidence vector
$\mathbf{d}^{(2)}\in\mathcal{P}(Q)^{n}$ $\triangleright$ Stage 2

1:execute the two steps as in Algorithm 1 for SCLD

Output: the set of all traitors $\mathcal{T}$

In the first stage, we exploit a binary $t$-HLD$(n_{0},M,2;L^{(1)})$ with the
list size $L^{(1)}=M^{\alpha}$, where $0\leq\alpha\leq 1$ is a constant and
will be decided later. Correspondingly, the code size
$M=2^{n_{0}R^{(\alpha)}_{\rm HLD}(t)}$, where $R^{(\alpha)}_{\rm HLD}(t)$ is
defined as in (3). According to the first half (i.e. Stage 1) of Algorithm 3,
given an evidence vector $\mathbf{d}^{(1)}$ generated by the collusion attack,
a subset of users indexed by $\mathcal{W}$ could be identified in time
$O(n_{0}M)$. By the definition of $t$-HLD, the size of $\mathcal{W}$ is upper
bounded by $L^{(1)}=M^{\alpha}$ and all the traitors are in $\mathcal{W}$. In
other words, in this stage we rule out some innocent users and narrow down the
search space for the next stage such that all the traitors are in
$\mathcal{W}$, which correspondingly conduces to further efficiently identify
all exact traitors.

In the second stage, we employ a binary
$\bar{t}$-SCLD$(n_{0},|\mathcal{W}|,2;L^{(2)})$ with the list size
$L^{(2)}=|\mathcal{W}|^{\beta}$ where $0\leq\beta\leq 1$ is a constant and
will be decided later. According to the latter part of Algorithm 3
(equivalently, Algorithm 1) and Theorem 1, given an evidence vector
$\mathbf{d}^{(2)}$ generated by the collusion attack, all the traitors could
be traced back in time
$O\big{(}\max\\{n_{0}|\mathcal{W}|,n_{0}|\mathcal{W}|^{\beta
t}\\}\big{)}=O\big{(}n_{0}M^{\max\\{\alpha,\alpha\beta t\\}}\big{)}$.

Let $n=2n_{0}$. Based on the foregoing, the total time cost of Algorithm 3 is
$O\big{(}nM^{\max\\{1,\alpha\beta t\\}}\big{)}$, and the code rate
(correspondingly, user capacity) of this two-stage dynamic traitor tracing is

$\displaystyle R_{\rm
TDTT}(\alpha,\beta,t)=\limsup_{n\to\infty}\frac{\log_{2}M}{n}=\limsup_{n_{0}\to\infty}\frac{\log_{2}2^{n_{0}R^{(\alpha)}_{\rm
HLD}(t)}}{2n_{0}}=\frac{1}{2}R^{(\alpha)}_{\rm HLD}(t).$ (20)

Notice that in order to guarantee the existence of the corresponding
$\bar{t}$-SCLD in the second stage, it is required that

$|\mathcal{W}|\leq M^{\alpha}=2^{\alpha\cdot n_{0}R^{(\alpha)}_{\rm
HLD}(t)}\leq 2^{n_{0}R^{(\beta)}_{\rm SCLD}(\bar{t})}.$

In other words, $\alpha$ and $\beta$ need to satisfy $\alpha\cdot
R^{(\alpha)}_{\rm HLD}(t)\leq R^{(\beta)}_{\rm SCLD}(\bar{t})$. Therefore the
theorem follows. ∎

It is worth noting from Theorem 7 that the choice of $\alpha,\beta$ plays an
important role in finding a trade-off between the code rate (i.e. user
capacity) and the tracing/identifying time complexity of two-stage dynamic
traitor tracing. Roughly, if $\alpha$ and $\beta$ are larger (smaller), the
code rate $R_{\rm TDTT}$ would be larger (smaller) while the identifying time
complexity would be higher (lower). To see their performance precisely, we
discuss two intriguing cases as below.

Case 1. To find the largest code rate $R_{\rm TDTT}$ without concerning the
tracing time complexity. To that end, we can set $\beta=1$ since $R_{\rm
TDTT}(\alpha,\beta,t)$ is a non-decreasing function of $\beta\in[0,1]$.
Accordingly, for each $t$, we aim to explore the optimum value of

$\displaystyle\max\ \frac{1}{2}R^{(\alpha)}_{\rm HLD}(t)\text{\ \ subject to\
}\ \alpha\cdot R^{(\alpha)}_{\rm HLD}(t)\leq R^{(\beta)}_{\rm SCLD}(\bar{t}),\
\ \beta=1,\ \ 0<\alpha<1.$ (21)

The Table IV illustrates the numerical lower bounds for $R_{\rm TDTT}$ via
(21) together with Theorem 2, as well as its comparison with the code rates of
SCLDs in the case when they have the same decoding complexity. It is easily
seen that under the same complete traceability requirement, two-stage dynamic
traitor tracing could have much larger code rate (i.e. accommodate much more
users) than SCLDs.

TABLE IV: Lower bounds for TDTTs, SCLDs when $\beta=1$ $(\alpha,\beta,t)$ | $(0.40606,1,3)$ | $(0.29257,1,4)$ | $(0.21608,1,5)$
---|---|---|---
$R_{\rm TDTT}(\alpha,\beta,t)$ | $0.16778$ | $0.10224$ | $0.07245$
$R^{(\alpha)}_{\rm SCLD}(\bar{t})$ | $0.13258$ | $0.05783$ | $0.03106$
decoding cost | $O(nM^{1.21818})$ | $O(nM^{1.17028})$ | $O(nM^{1.08040})$

Case 2. To find the largest code rate $R_{\rm TDTT}$ with tracing time
complexity $O(nM)$. From Theorem 7, it is seen that the time cost of two-stage
traitor tracing is $O(nM^{\max\\{1,\alpha\beta t\\}})$, which takes the
minimum value $O(nM)$ if $\alpha\beta\leq 1/t$. Since $R_{\rm
TDTT}(\alpha,\beta,t)$ is a non-decreasing function of $\alpha,\beta\in[0,1]$,
we may consider the case when $\alpha\beta=1/t$ to explore the largest
possible code rate. Accordingly, for each $t$, we aim to find the optimum
value of

$\displaystyle\max\ \frac{1}{2}R^{(\alpha)}_{\rm HLD}(t)\text{\ \ subject to\
}\ \alpha\cdot R^{(\alpha)}_{\rm HLD}(t)\leq R^{(\beta)}_{\rm SCLD}(\bar{t}),\
\ \alpha\beta=1/t,\ \ 0<\alpha,\beta<1.$ (22)

The Table V illustrates the numerical lower bounds for $R_{\rm TDTT}$ from
(22) and Theorem 2. A comparison between SCLDs and two-stage dynamic traitor
tracing under the same decoding cost $O(nM)$ in Table V shows that two-stage
dynamic traitor tracing could have much larger code rate (i.e. accommodate
much more users) than SCLDs.

TABLE V: Lower bounds for TDTTs, SCLDs when $\alpha\beta=1/t$ $(\alpha,\beta,t)$ | $(0.40406,0.82496,3)$ | $(0.29107,0.85890,4)$ | $(0.21508,0.92989,5)$
---|---|---|---
$R_{\rm TDTT}(\alpha,\beta,t)$ | $0.16722$ | $0.10202$ | $0.07236$
$R^{(1/t)}_{\rm SCLD}(\bar{t})$ | $0.13205$ | $0.05770$ | $0.03105$
decoding cost | $O(nM)$ | $O(nM)$ | $O(nM)$

##  IX Conclusion

In this paper we investigated combinatorial secure codes for traitor tracing.
We initially integrated the list decoding idea directly into the practical
model of traitor tracing with multimedia fingerprinting and proposed the
notion of secure codes with list decoding (SCLDs). It is shown that SCLDs can
be seen as a unified concept in the sense that it could include many existing
fingerprinting codes as special cases. We established efficient
decoding/identifying algorithms and bounds on the largest possible code rate
for SCLDs, which indicate that SCLDs could outperform the existing
fingerprinting codes in terms of the decoding efficiency and/or the code rate.
Furthermore, we proposed a two-stage traitor tracing framework for the dynamic
scenario and showed that it has not only fast decoding but also much larger
code rate than the static scenario. In the future work, it would be
interesting to further improve the code rates and explore more explicit
constructions for the binary SCLDs.

## Acknowledgment

Y. Gu would like to thank Prof. Tsuyoshi Takagi for inspirational suggestions
on the study of traitor tracing with list decoding at an early stage, thank
Prof. Minoru Kuribayashi for insightful comments on Section VIII, and thank
Prof. Shuichi Kawano for stimulating discussions.

## References

  * [1] A. Barg and G. Kabatiansky, “A class of i.p.p. codes with efficient identification,” _Journal of Complexity_ , vol. 20, no. 2-3, pp. 137–147, 2004.
  * [2] O. Berkman, M. Parnas, and J. Sgall, “Efficient dynamic traitor tracing,” _SIAM Journal on Computing_ , vol. 30, no. 6, pp. 1802–1828, 2001.
  * [3] S. R. Blackburn, “Frameproof codes,” _SIAM J. Discrete Math._ , vol. 16, no. 3, pp. 499–510, 2003.
  * [4] ——, “Probabilistic existence results for separable codes,” _IEEE Transactions on Information Theory_ , vol. 61, no. 11, pp. 5822–5827, 2015.
  * [5] D. Boneh and J. Shaw, “Collusion-secure fingerprinting for digital data,” _IEEE Transactions on Information Theory_ , vol. 44, no. 5, pp. 1897–1905, 1998.
  * [6] C.-L. Chen, “Formulas for the solutions of quadratic equations over $\text{GF}(2^{m})$,” _IEEE Transactions on Information Theory_ , vol. IT-28, no. 5, pp. 792–794, 1982.
  * [7] M. Cheng, L. Ji, and Y. Miao, “Separable codes,” _IEEE Transactions on Information Theory_ , vol. 58, no. 3, pp. 1791–1803, 2012.
  * [8] M. Cheng and Y. Miao, “On anti-collusion codes and detection algorithms for multimedia fingerprinting,” _IEEE Transactions on Information Theory_ , vol. 57, no. 7, pp. 4843–4851, 2011.
  * [9] H. Chernoff, “A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations,” _The Annals of Mathematical Statistics_ , pp. 493–507, 1952.
  * [10] B. Chor, A. Fiat, and M. Naor, “Tracing traitors,” in _Annual International Cryptology Conference (CRYPTO)_. Springer, 1994, pp. 257–270.
  * [11] G. D. Cohen and H. G. Schaathun, _Asymptotic overview on separating codes_. Citeseer, 2003, no. 248.
  * [12] C. J. Colbourn, _Handbook of Combinatorial Designs_. CRC press, 2010.
  * [13] I. J. Cox, M. L. Miller, J. A. Bloom, and C. Honsinger, _Digital watermarking_. Springer, 2002, vol. 53.
  * [14] A. D’yachkov, N. Polyanskii, V. Shchukin, and I. Vorobyev, “Separable codes for the symmetric multiple-access channel,” _IEEE Transactions on Information Theory_ , vol. 65, no. 6, pp. 3738–3750, 2019.
  * [15] E. Egorova, M. Fernandez, and G. Kabatiansky, “A construction of traceability set systems with polynomial tracing algorithm,” in _IEEE International Symposium on Information Theory (ISIT)_ , 2019, pp. 2739–2742.
  * [16] E. Egorova, M. Fernandez, G. Kabatiansky, and M. H. Lee, “Signature codes for the a-channel and collusion-secure multimedia fingerprinting codes,” in _IEEE International Symposium on Information Theory (ISIT)_ , 2016, pp. 3043–3047.
  * [17] ——, “Signature codes for weighted noisy adder channel, multimedia fingerprinting and compressed sensing,” _Designs, Codes and Cryptography_ , vol. 87, no. 2, pp. 455–462, 2019.
  * [18] E. E. Egorova, M. Fernandez, G. A. Kabatiansky, and Y. Miao, “Existence and construction of complete traceability multimedia fingerprinting codes resistant to averaging attack and adversarial noise,” _Problems of Information Transmission_ , vol. 56, no. 4, pp. 388–398, 2020.
  * [19] J. Fan, Y. Gu, M. Hachimori, and Y. Miao, “Signature codes for weighted binary adder channel and multimedia fingerprinting,” _IEEE Transactions on Information Theory_ , vol. 67, no. 1, pp. 200–216, 2020.
  * [20] M. Fernandez, J. Moreira, and M. Soriano, “Identifying traitors using the Koetter-Vardy algorithm,” _IEEE Transactions on Information Theory_ , vol. 57, no. 2, pp. 692–704, 2011.
  * [21] M. Fernandez and M. Soriano, “Identification of traitors in algebraic-geometric traceability codes,” _IEEE Transactions on Signal Processing_ , vol. 52, no. 10, pp. 3073–3077, 2004.
  * [22] A. Fiat and T. Tassa, “Dynamic traitor tracing,” in _Annual International Cryptology Conference (CRYPTO)_. Springer, 1999, pp. 354–371.
  * [23] ——, “Dynamic traitor tracing,” _Journal of Cryptology_ , vol. 14, no. 3, pp. 211–223, 2001.
  * [24] S. D. Fiore and M. Dalai, “A note on $\bar{2}$-separable codes and $\emph{B}_{2}$ codes,” _Discrete Mathematics_ , vol. 345, no. 3, p. 112751, 2022.
  * [25] G. D. Forney, “Concatenated codes.” 1965.
  * [26] A. D. Friedman, R. L. Graham, and J. D. Ullman, “Universal single transition time asynchronous state assignments,” _IEEE Transactions on Computers_ , vol. 100, no. 6, pp. 541–547, 1969.
  * [27] F. Gao and G. Ge, “New bounds on separable codes for multimedia fingerprinting,” _IEEE Transactions on Information Theory_ , vol. 60, no. 9, pp. 5257–5262, 2014.
  * [28] Y. Gu, J. Fan, and Y. Miao, “Improved bounds for separable codes and $\emph{B}_{2}$ codes,” _IEEE Communications Letters_ , vol. 24, pp. 15–19, 2020.
  * [29] Y. Gu, I. Vorobyev, and Y. Miao, “Secure codes with list decoding,” in _IEEE International Symposium on Information Theory (ISIT)_ , 2022, pp. 2350–2355.
  * [30] V. Guruswami and M. Sudan, “Improved decoding of Reed-Solomon and algebraic-geometric codes,” in _Proceedings 39th Annual Symposium on Foundations of Computer Science (FOCS)_ , 1998, pp. 28–37.
  * [31] J. Jiang, M. Cheng, and Y. Miao, “Strongly separable codes,” _Designs, Codes and Cryptography_ , vol. 79, no. 2, pp. 303–318, 2016.
  * [32] T. Laarhoven, J. Doumen, P. Roelse, B. Škorić, and B. de Weger, “Dynamic Tardos traitor tracing schemes,” _IEEE Transactions on Information Theory_ , vol. 59, no. 7, pp. 4230–4242, 2013.
  * [33] R. Lidl and H. Niederreiter, _Finite Fields_. Cambridge Univ. Press, 2003.
  * [34] B. Lindström, “Determination of two vectors from the sum,” _Journal of Combinatorial Theory_ , vol. 6, no. 4, pp. 402–407, 1969.
  * [35] O. Moreno, “On primitive elements of trace equal to $1$ in $\text{GF}(2^{m})$,” _Discrete Mathematics_ , vol. 41, pp. 53–56, 1982.
  * [36] H. Randriambololona, “$(2,1)$-separating systems beyond the probabilistic bound,” _Israel Journal of Mathematics_ , vol. 195, pp. 171–186, 2013.
  * [37] R. Safavi-Naini and Y. Wang, “Sequential traitor tracing,” _IEEE Transactions on Information Theory_ , vol. 49, no. 5, pp. 1319–1326, 2003.
  * [38] Y. L. Sagalovich, “A method for increasing the reliability of finite automata,” _Problemy Peredachi Informatsii_ , vol. 1, no. 2, pp. 27–35, 1965\.
  * [39] ——, “Separaring systems,” _Problemy Peredachi Informatsii_ , vol. 30, no. 2, pp. 14–35, 1994.
  * [40] V. Y. Shchukin, “List decoding for a multiple access hyperchannel,” _Problems of Information Transmission_ , vol. 52, no. 4, pp. 329–343, 2016\.
  * [41] A. Silverberg, J. Staddon, and J. L. Walker, “Efficient traitor tracing algorithms using list decoding,” in _International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT)_. Springer, 2001, pp. 175–192.
  * [42] W. Trappe, M. Wu, Z. J. Wang, and K. R. Liu, “Anti-collusion fingerprinting for multimedia,” _IEEE Transactions on Signal Processing_ , vol. 51, no. 4, pp. 1069–1087, 2003.
  * [43] I. Vorobyev, “Fast decoding of union-free codes,” in _2021 XVII International Symposium “Problems of Redundancy in Information and Control Systems” (REDUNDANCY)_. IEEE, 2021, pp. 106–109.
  * [44] ——, “Complete traceability multimedia fingerprinting codes resistant to averaging attack and adversarial noise with optimal rate,” _Designs, Codes and Cryptography_ , pp. 1–9, 2022.
  * [45] X. Wang, “Improved upper bounds for parent-identifying set systems and separable codes,” _Designs, Codes and Cryptography_ , vol. 89, no. 1, pp. 91–104, 2021.
  * [46] Y. Yang, Y. Zhang, and G. Ge, “New lower bounds for secure codes and related hash families: A hypergraph theoretical approach,” _IEEE Transactions on Information Theory_ , vol. 63, no. 4, pp. 2446–2453, 2017.