Daniel Wichs
New York University

From Weak to Strong Watermarking


The informal goal of a watermarking scheme is to ``mark'' a digital object,
such as a picture or video, in such a way that it is difficult for an adversary
to remove the mark without destroying the content of the object. Although there
has been considerable work proposing and breaking watermarking schemes, there
has been little attention given to the formal security goals of such a scheme.
In this work, we provide a new complexity-theoretic definition of security for
watermarking schemes. We describe some shortcomings of previous attempts at
defining watermarking security, and show that security under our definition also
implies security under previous definitions. We also propose two weaker security
conditions that seem to capture the security goals of practice-oriented work on
watermarking and show how schemes satisfying these weaker goals can be
strengthened to satisfy our definition.

Nicholas Hopper, David Molnar, and David Wagner