Paper 2017/557

Watermarking Public-key Cryptographic Functionalities and Implementations

Foteini Baldimtsi, Aggelos Kiayias, and Katerina Samari


A watermarking scheme for a public-key cryptographic functionality enables the embedding of a mark in the instance of the secret-key algorithm such that the functionality of the original scheme is maintained, while it is infeasible for an adversary to remove the mark (unremovability) or mark a fresh object without the marking key (unforgeability). Cohen et al. [STOC'16] has provided constructions for watermarking arbitrary cryptographic functionalities; the resulting schemes rely on indistinguishability obfuscation (iO) and leave two important open questions: (i) the realization of both unremovability and unforgeability, and (ii) schemes the security of which reduces to simpler hardness assumptions than iO. In this paper we provide a new definitional framework that distinguishes between watermarking cryptographic functionalities and implementations (think of ElGamal encryption being an implementation of the encryption functionality), while at the same time provides a meaningful relaxation of the watermarking model that enables both unremovability and unforgeability under minimal hardness assumptions. In this way we can answer questions regarding the ability to watermark a given implementation of a cryptographic functionality which is more refined compared to the question of whether a watermarked implementation functionality exists. Taking advantage of our new formulation we present the first constructions for watermarking public key encryption that achieve both unremovability and unforgeability under minimal hardness assumptions. Our first construction enables the watermarking of any public-key encryption implementation assuming only the existence of one-way functions for private key detection. Our second construction is at the functionality level and uses a stronger assumption (existence of identity-based encryption (IBE)) but supports public detection of the watermark.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Major revision. 20th Information Security Conference, ISC 2017
watermarkingpublic -key encryptionunremovabilityunforgeability
Contact author(s)
ksamari @ di uoa gr
2017-10-26: revised
2017-06-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Foteini Baldimtsi and Aggelos Kiayias and Katerina Samari},
      title = {Watermarking Public-key Cryptographic Functionalities and Implementations},
      howpublished = {Cryptology ePrint Archive, Paper 2017/557},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.