Toward provably robust watermarking

To appearWatermarking techniques are used to help identifying copies of publicly released information. They consist in applying a slight and secretmodification to the data before its release, in a way that should berobust, i.e. remain recognizable even in (reasonably) modifiedcopies of the data.In this paper, we present new results about the robustness of watermarking schemes against arbitrary attackers, and the formalization of those results in\coq. We used the \alea library, which formalizes probability theoryand models probabilistic programs using a simple monadic translation.This work illustrates the strengths and particularities of the inducedstyle of reasoning about probabilistic programs. Our technique for provingrobustness is adapted from methods commonly used for cryptographic protocols, and we discuss its relevance to the field of watermarking