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.