Paper 2019/628

Watermarking Public-Key Cryptographic Primitives

Rishab Goyal, Sam Kim, Nathan Manohar, Brent Waters, and David J. Wu


A software watermarking scheme enables users to embed a message or mark within a program while preserving its functionality. Moreover, it is difficult for an adversary to remove a watermark from a marked program without corrupting its behavior. Existing constructions of software watermarking from standard assumptions have focused exclusively on watermarking pseudorandom functions (PRFs). In this work, we study watermarking public-key primitives such as the signing key of a digital signature scheme or the decryption key of a public-key (predicate) encryption scheme. While watermarking public-key primitives might seem more challenging than watermarking PRFs, we show how to construct watermarkable variants of these notions while only relying on standard, and oftentimes, minimal, assumptions. Our watermarkable signature scheme relies only on the minimal assumption that one-way functions exist and satisfies ideal properties such as public marking, public mark-extraction, and full collusion resistance. Our watermarkable public-key encryption schemes are built using techniques developed for the closely-related problem of traitor tracing. Notably, we obtain fully collusion resistant watermarkable attribute-based encryption in the private-key setting from the standard learning with errors assumption and a bounded collusion resistant watermarkable predicate encryption scheme with public mark-extraction and public marking from the minimal assumption that public-key encryption exists.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2019
watermarkingpublic-key primitives
Contact author(s)
rgoyal @ cs utexas edu
skim13 @ cs stanford edu
nmanohar @ cs ucla edu
bwaters @ cs utexas edu
dwu4 @ virginia edu
2019-09-08: revised
2019-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rishab Goyal and Sam Kim and Nathan Manohar and Brent Waters and David J.  Wu},
      title = {Watermarking Public-Key Cryptographic Primitives},
      howpublished = {Cryptology ePrint Archive, Paper 2019/628},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.