Paper 2013/809

Riding the Saddle Point: asymptotics of the capacity-achieving simple decoder for bias-based traitor tracing

Sarah Ibrahimi, Boris Skoric, and Jan-Jaap Oosterwijk

Abstract

We study the asymptotic-capacity-achieving score function that was recently proposed by Oosterwijk et al. for bias-based traitor tracing codes. For the bias function we choose the Dirichlet distribution with a cutoff. Using Bernstein's inequality and Bennett's inequality, we upper bound the false positive and false negative error probabilities. From these bounds we derive sufficient conditions for the scheme parameters. We solve these conditions in the limit of large coalition size $c_0$ and obtain asymptotic solutions for the cutoff, the sufficient code length and the corresponding accusation threshold. The code length converges to its asymptote approximately as $c_0^{-1/2}$, which is faster than the $c_0^{-1/3}$ of Tardos' score function.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
traitor tracing
Contact author(s)
b skoric @ tue nl
History
2013-12-06: received
Short URL
https://ia.cr/2013/809
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/809,
      author = {Sarah Ibrahimi and Boris Skoric and Jan-Jaap Oosterwijk},
      title = {Riding the Saddle Point: asymptotics of the capacity-achieving simple decoder for bias-based traitor tracing},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/809},
      year = {2013},
      url = {https://eprint.iacr.org/2013/809}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.