Lower bounds for collusion-secure fingerprinting
Lower bounds for collusion-secure fingerprinting
复制标题
共谋安全指纹识别的下限
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Adam D. Smith
中科院分区：
文献类型：
--
作者：
Chris Peikert;Abhi Shelat;Adam D. Smith
合谋安全指纹码是许多数字水印方案使用的重要原语[1,10,9]。Boneh和Shaw[3]为这些类型的代码定义了一个模型，并给出了一个明确的结构。他们的代码长度<i> 0 </i>(<i>c</i><sup>3</sup> log(l/ε))，并且在ε错误的情况下，对大小<i>c</i>的联盟具有安全性。Boneh和Shaw还给出了任意共谋安全码长度的下界Ω （<i>c</i><sup>3</sup>log(1/<i>c</i>ε)）。通过分析联合的加权抛硬币策略，给出了合谋安全码长度的新下界。为了说明我们的方法，我们给出了Boneh-Shaw构造不能渐近改进的一个简单证明。接下来，我们证明了一个一般下界：没有安全码的长度可以小于i>O</i>(<i>c</i><sup>2</sup> 10g (1/<i>c</i>ε))，这比之前已知的下界提高了一个因子<i>c</i>。特别地，我们证明了任何安全代码的长度为Ω（<i>c</i><sup>2</sup> log(1/<i>c</i>ε)），只要log(l/ε)≥<i>K</i> <i>K</i> log <i>c</i>，其中<i>K</i>是常数，<i>K</i>是代码中的列数（在某种意义上，是代码复杂性的度量）。最后，我们描述了构建包含[3]构造的指纹码的一般范例，并表明遵循此范例的安全代码不能具有长度<i>O</i>(（c<sup>3</sup>/log c) log(1/<i>c</i>ε)）遵循此（再次，通过显示大值ln（1/ε）的下界）。这表明，任何改进的尝试都应该指向我们范例之外的技术。
Collusion-secure fingerprinting codes are an important primitive used by many digital watermarking schemes [1, 10, 9]. Boneh and Shaw [3] define a model for these types of codes and present an explicit construction. Their code has length <i>O</i>(<i>c</i><sup>3</sup> log(l/ε)) and attains security against coalitions of size <i>c</i> with ε error. Boneh and Shaw also present a lower bound of Ω (<i>c</i><sup>3</sup>log(1/<i>c</i>ε)) on the length of any collusion-secure code.We give new lower bounds on the length of collusion-secure codes by analyzing a weighted coinflipping strategy for the coalition. As an illustration of our methods, we give a simple proof that the Boneh-Shaw construction cannot be asymptotically improved. Next, we prove a general lower bound: no secure code can have length <i>O</i>(<i>c</i><sup>2</sup>1og(1/<i>c</i>ε)), which improves the previous known bound by a factor of <i>c</i>. In particular, we show that any secure code will have length Ω(<i>c</i><sup>2</sup> log(1/<i>c</i>ε)) as long as log(l/ε) ≥ <i>K</i> <i>k</i> log <i>c</i>, where <i>K</i> is a constant and <i>k</i> is the number of columns in the code (in some sense, a measure of the code's complexity). Finally, we describe a general paradigm for constructing fingerprinting codes which encompasses the construction of [3], and show that no secure code that follows this paradigm can have length <i>O</i>((c<sup>3</sup>/log c) log(1/<i>c</i>ε)) follows this (again, by showing a lower bound for large values of ln(1/ε)). This suggests that any attempts at improvement should be directed toward techniques that lie outside our paradigm.