Paper 2017/1117
Risky Traitor Tracing and New Differential Privacy Negative Results
Rishab Goyal, Venkata Koppula, Andrew Russell, and Brent Waters
Abstract
In this work we seek to construct collusionresistant traitor tracing systems with small ciphertexts from standard assumptions that also move toward practical efficiency. In our approach we will hold steadfast to the principle of collusion resistance, but relax the requirement on catching a traitor from a successful decoding algorithm. We define a $f$risky traitor tracing system as one where the probability of identifying a traitor is $f(\lambda,n)$ times the probability a successful box is produced. We then go on to show how to build such systems from prime order bilinear groups with assumptions close to those used in prior works. Our core system achieves, for any $k > 0$, $f(\lambda,n) \approx \frac{k}{n + k  1}$ where ciphertexts consists of $(k + 4)$ group elements and decryption requires $(k + 3)$ pairing operations. At first glance the utility of such a system might seem questionable since the $f$ we achieve for short ciphertexts is relatively small. Indeed an attacker in such a system can more likely than not get away with producing a decoding box. However, we believe this approach to be viable for four reasons: 1. A risky traitor tracing system will provide deterrence against risk averse attackers. In some settings the consequences of being caught might bear a high cost and an attacker will have to weigh his utility of producing a decryption $D$ box against the expected cost of being caught. 2. Consider a broadcast system where we want to support low overhead broadcast encrypted communications, but will periodically allow for a more expensive key refresh operation. We refer to an adversary produced algorithm that maintains the ability to decrypt across key refreshes as a persistent decoder. We show how if we employ a risky traitor tracing systems in this setting, even for a small $f$, we can amplify the chances of catching such a ``persistent decoder'' to be negligibly close to 1. 3. In certain resource constrained settings risky traitor tracing provides a best tracing effort where there are no other collusionresistant alternatives. For instance, suppose we had to support 100K users over a radio link that had just 10KB of additional resources for extra ciphertext overhead. None of the existing $\sqrt N$ bilinear map systems can fit in these constraints. On the other hand a risky traitor tracing system provides a spectrum of tracing probability versus overhead tradeoffs and can be configured to at least give some deterrence in this setting. 4. Finally, we can capture impossibility results for differential privacy from $\frac{1}{n}$risky traitor tracing. Since our ciphertexts are short ($O(\lambda)$), we get the negative result which matches what one would get plugging in the obfuscation based tracing system BonehZhandry (CRYPTO 2014) solution into the prior impossibility result of Dwork et al. (STOC 2009).
Note: Added a new framework for building risky traitor schemes as well as a construction from prime order bilinear groups.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 Traitor TracingDifferential Privacy
 Contact author(s)
 rgoyal @ cs utexas edu
 History
 20180227: last of 3 revisions
 20171124: received
 See all versions
 Short URL
 https://ia.cr/2017/1117
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/1117, author = {Rishab Goyal and Venkata Koppula and Andrew Russell and Brent Waters}, title = {Risky Traitor Tracing and New Differential Privacy Negative Results}, howpublished = {Cryptology ePrint Archive, Paper 2017/1117}, year = {2017}, note = {\url{https://eprint.iacr.org/2017/1117}}, url = {https://eprint.iacr.org/2017/1117} }