Publicly Verifiable Software Watermarking

Aloni Cohen; Justin Holmgren; Vinod Vaikuntanathan

Paper 2015/373

Publicly Verifiable Software Watermarking

Aloni Cohen, Justin Holmgren, and Vinod Vaikuntanathan

Abstract

Software Watermarking is the process of transforming a program into a functionally equivalent ``marked'' program in such a way that it is computationally hard to remove the mark without destroying functionality. Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan and Yang (CRYPTO 2001) defined software watermarking and showed that the existence of indistinguishability obfuscation implies that software watermarking is impossible. Given the recent candidate constructions of indistinguishability obfuscation, this result paints a bleak picture for the possibility of meaningful watermarking. 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.

Note: This work has since been improved, revised, and merged with Nishimaki-Wichs 2015 (2015/344). The merged version is 2015/1096.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: indistingushability obfuscation watermarking puncturable PRFs
Contact author(s): aloni @ mit edu
History: 2015-12-07: last of 3 revisions; 2015-04-24: received; See all versions
Short URL: https://ia.cr/2015/373
License: CC BY

BibTeX

@misc{cryptoeprint:2015/373,
      author = {Aloni Cohen and Justin Holmgren and Vinod Vaikuntanathan},
      title = {Publicly Verifiable Software Watermarking},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/373},
      year = {2015},
      url = {https://eprint.iacr.org/2015/373}
}