Fingerprinting Code

From Cryptology City
Revision as of 02:33, 21 July 2024 by Axhoover (talk | contribs) (→‎Correctness)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search


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 which maps subsets of codewords in to other subsets in the same space. Formally,

In english this means, if index as character , then there must be some which also has that character at index . 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 with respect to a keyspace , alphabet , number of users , and codeword length which depends on the error threshold such that:

  • is a randomized algorithm that takes an error threshold, and integer , and generates a secret key an codewords where each .
  • is a deterministic algorithm that takes as input a key and any string , and outputs a subset of accused users.

Note: The fingerprinting code functions are not strictly "efficient," since for example can take in bits and outputs bits. However, we generally require that both functions run in time that is polynomial in and .

Correctness

A fingerprinting code is correct if for any , set of colluding users , and , we have that

where .

In more plain English, this definition means that the fingerprinting code is useful and correct with probability at least 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 and require error that is negligible in the security parameter. But, this follows immediately from the above definition by setting .

Robust Fingerprinting Codes

TODO - syntax changes and security definition

Impossibilities

  • TODO - fingerprinting bounds

Constructions

  • TODO - Tardos and others

Related Primitives