Fingerprinting Capacity Under the Marking Assumption

Abstract

We study the maximum attainable rate or capacity of fingerprinting codes under the marking assumption. It is proved that capacity for fingerprinting against coalitions of size two and three over the binary alphabet satisfies 0.25 ≤ C <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2,2</sub> ≤ 0.322 and 0.083 ≤ C <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3,2</sub> ≤ 0.199 respectively. For coalitions of an arbitrary fixed size, we derive a closed-form upper bound on fingerprinting capacity in the binary case. Finally, for general alphabets, we establish upper bounds on the fingerprinting capacity involving only single-letter mutual information quantities.