Paper 2015/1096

Watermarking Cryptographic Capabilities

Aloni Cohen, Justin Holmgren, Ryo Nishimaki, Vinod Vaikuntanathan, and Daniel Wichs


A watermarking scheme for programs embeds some information called a mark into a program while preserving its functionality. No adversary can remove the mark without damaging the functionality of the program. In this work, we study the problem of watermarking various cryptographic programs such as pseudorandom function (PRF) evaluation, decryption, and signing. For example, given a PRF F, we create a marked program C~ that evaluates F(). An adversary that gets C~ cannot come up with any program C* in which the mark is removed but which still evaluates the PRF correctly on even a small fraction of the inputs. The work of Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, and Yang (CRYPTO'01 and Journal of ACM 59(2)) shows that, assuming indistinguishability obfuscation (iO), such watermarking is impossible if the marked program C~ evaluates the original program with perfect correctness. In this work we show that, assuming iO, such watermarking is possible if the marked program C~ is allowed to err with even a negligible probability, which would be undetectable to the user. Our watermarking schemes are public key, meaning that we use a secret marking key to embed marks in programs, and a public detection key that allows anyone to detect marks in programs. Our schemes are secure against chosen program attacks where the adversary is given oracle access to the marking functionality. We emphasize that our security notion of watermark non-removability considers arbitrary adversarial strategies to modify the marked program, in contrast to the prior works (Nishimaki, EUROCRYPT '13).

Note: Added acknowledgements

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Major revision. STOC 2016
watermarkingindistingushability obfuscationpuncturable PRFs
Contact author(s)
nishimaki ryo @ lab ntt co jp
2016-02-08: last of 2 revisions
2015-11-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Aloni Cohen and Justin Holmgren and Ryo Nishimaki and Vinod Vaikuntanathan and Daniel Wichs},
      title = {Watermarking Cryptographic Capabilities},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1096},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.