Paper 2020/1173

Equipping Public-Key Cryptographic Primitives with Watermarking (or: A Hole Is to Watermark)

Ryo Nishimaki


Program watermarking enables users to embed an arbitrary string called a mark into a program while preserving the functionality of the program. Adversaries cannot remove the mark without destroying the functionality. Although there exist generic constructions of watermarking schemes for public-key cryptographic (PKC) primitives, those schemes are constructed from scratch and not efficient. In this work, we present a general framework to equip a broad class of PKC primitives with an efficient watermarking scheme. The class consists of PKC primitives that have a canonical all-but-one (ABO) reduction. Canonical ABO reductions are standard techniques to prove selective security of PKC primitives, where adversaries must commit a target attribute at the beginning of the security game. Thus, we can obtain watermarking schemes for many existing efficient PKC schemes from standard cryptographic assumptions via our framework. Most well-known selectively secure PKC schemes have canonical ABO reductions. Notably, we can achieve watermarking for public-key encryption whose ciphertexts and secret-keys are constant-size, and that is chosen-ciphertext secure. Our approach accommodates the canonical ABO reduction technique to the puncturable pseudorandom function (PRF) technique, which is used to achieve watermarkable PRFs. We find that canonical ABO reductions are compatible with such puncturable PRF-based watermarking schemes.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in TCC 2020
watermarkingpublic-key cryptographyall-but-one reduction
Contact author(s)
ryo nishimaki @ gmail com
2020-09-25: received
Short URL
Creative Commons Attribution


      author = {Ryo Nishimaki},
      title = {Equipping Public-Key Cryptographic Primitives with Watermarking (or: A Hole Is to Watermark)},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1173},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.