Fingerprinting Code

Fingerprinting Codes were first introduced by [BS98]. A Fingerprinting Code is describes a process to produce codewords for users. If a group of these users collude to adversarially produce a new codeword, then a fingerprinting code guarantees that the distributor can trace the new word back to these colluders with high probability.

Formal Definition

For fingerprinting codes, it is useful to define the descendents function $desc(\cdot )$ which maps subsets of codewords in $\Sigma ^{\ell }$ to other subsets in the same space. Formally,

$desc(\{x_{1},\ldots ,x_{c}\})=\{y\in \Sigma ^{\ell }:\forall i\in [\ell ]\exists j\in [c],y[i]=x_{j}[i]\}.$

In english this means, if index $i$ as character $\sigma$, then there must be some $x_{j}$ which also has that character at index $i$. This captures the idea that a group of colluding pirates may be able to selectively choose their codewords, but they cannot forge characters at indices they didn't have access to.

Syntax

A fingerprinting code is a tuple of functions $({\mathsf {Gen}},{\mathsf {Trace}})$ with respect to a keyspace ${\mathcal {K}}$, alphabet $\Sigma$, number of users $n$, and codeword length $\ell =\ell (\varepsilon ,c)$ which depends on the error threshold such that:

• ${\mathsf {Gen}}(\varepsilon ,c)\to (k,x_{1},\ldots ,x_{n})$ is a randomized algorithm that takes an error threshold, $0\leq \varepsilon \leq 1$ and integer $1\leq c\leq n$, and generates a secret key $k\in {\mathcal {K}}$ an $n$ codewords where each $x_{i}\in \Sigma ^{\ell }$.
• ${\mathsf {Trace}}(k,y)\to S$ is a deterministic algorithm that takes as input a key $k$ and any string $y\in \Sigma ^{\ell }$, and outputs a subset $S\subseteq [n]$ of accused users.

Note: The fingerprinting code functions are not strictly "efficient," since for example ${\mathsf {Gen}}$ can take in $O(\log n)$ bits and outputs $\Omega (n)$ bits. However, we generally require that both functions run in time that is polynomial in $n$ and $\log |\Sigma |$.

Correctness

A fingerprinting code is correct if for any $0\leq \varepsilon \leq 1$, set of colluding users $C\subseteq [n]$, and $y\in desc(\{x_{i}:i\in C\})$, we have that

$\Pr[{\mathsf {Trace}}(k,y)\not \subseteq C\lor {\mathsf {Trace}}(k,y)=\emptyset ]\leq \varepsilon ,$

where $(k,x_{1},\ldots ,x_{n})\gets {\mathsf {Gen}}(\varepsilon ,|C|)$.

In more plain English, this definition means that the fingerprinting code is useful and correct with probability at least $1-\varepsilon$ as long as code generation is given the maximum size of the possible collusion as input. The first condition in the probability means that the trace does not accuse an innocent (non-colluding) user. The second condition makes sure that the trace algorithm does at least accuse some user though.

Note: One can also define fingerprinting codes with respect to a security parameter $1^{\lambda }$ and require error that is negligible in the security parameter. But, this follows immediately from the above definition by setting $\varepsilon =2^{-\lambda }$.

Robust Fingerprinting Codes

TODO - syntax changes and security definition

Impossibilities

• TODO - fingerprinting bounds

Constructions

• TODO - Tardos and others

Related Primitives

• Traceability Codes