IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

On the saddle-point solution and the large-coalition behavior of fingerprinting games

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/16836

Files in this item

File Description Format
PDF Huang_Yen-Wei.pdf (680KB) (no description provided) PDF
Title: On the saddle-point solution and the large-coalition behavior of fingerprinting games
Author(s): Huang, Yen-Wei
Advisor(s): Moulin, Pierre
Department / Program: Electrical & Computer Eng
Discipline: Electrical & Computer Engr
Degree Granting Institution: University of Illinois at Urbana-Champaign
Degree: M.S.
Genre: Thesis
Subject(s): fingerprinting traitor tracing capacity game theory minimax theorem Jeffreys' prior saddle-point problems
Abstract: We study a fingerprinting game in which the number of colluders and the collusion channel are unknown. The encoder embeds fingerprints into a host sequence and provides the decoder with the capability to trace back pirated copies to the colluders. Fingerprinting capacity has recently been derived as the limit value of a sequence of maximin games with mutual information as their payoff functions. However, these games generally do not admit saddle-point solutions and are very hard to solve numerically. Here under the so-called Boneh-Shaw marking assumption, we reformulate the capacity as the value of a single two-person zero-sum game, and show that it is achieved by a saddle-point solution. If the maximal coalition size is $k$ and the fingerprinting alphabet is binary, we show that the capacity is in $\Theta(1/k^2)$. Furthermore, we prove rigorously that the asymptotic capacity is $1/(k^2 2 \ln2)$ and we confirm our earlier conjecture that Tardos' choice of the arcsine distribution asymptotically maximizes the mutual information payoff function while the interleaving attack minimizes it. Along with the asymptotic behavior, numerical solutions to the game for small $k$ are also presented.
Issue Date: 2010-08-20
URI: http://hdl.handle.net/2142/16836
Rights Information: Copyright 2010 Yen-Wei Huang
Date Available in IDEALS: 2010-08-20
Date Deposited: 2010-08
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 115
  • Downloads this Month: 1
  • Downloads Today: 0

Browse

My Account

Information

Access Key