We show that slightly relaxing the functionality requirement gives us strong positive results for watermarking. Namely, instead of requiring the marked program to agree with the original unmarked program on {\em all inputs}, we require only that they agree on a large fraction of inputs. With this relaxation in mind, our contributions are as follows.
1. We define publicly verifiable watermarking where marking a program requires a secret key, but anyone can verify that a program is marked. The handful of existing watermarking schemes are secretly verifiable, and moreover, satisfy only a weak definition where the adversary is restricted in the type of unmarked programs it is allowed to produce (Naccache, Shamir and Stern, PKC 1999; Nishimaki, EUROCRYPT 2013). Moreover, our definition requires security against chosen program attacks, where an adversary has access to an oracle that marks programs of her choice.
2. We construct a publicly verifiable watermarking scheme for any family of puncturable pseudo-random functions (PPRF), assuming indistinguishability obfuscation and injective one-way functions.
Complementing our positive result, we show that there are pseudo-random functions which cannot be watermarked, even in a very weak setting. As a corollary, we demonstrate the first family of PRFs that are not point-puncturable.
Category / Keywords: public-key cryptography / indistingushability obfuscation, watermarking, puncturable PRFs Date: received 22 Apr 2015, last revised 26 May 2015 Contact author: aloni at mit edu Available format(s): PDF | BibTeX Citation Note: Added construction of ``unwatermarkable'' families of PRFs. Version: 20150527:043823 (All versions of this report) Short URL: ia.cr/2015/373 Discussion forum: Show discussion | Start new discussion