Watermarking Public-Key Cryptographic Functionalities and Implementations

Foteini Baldimtsi, Aggelos Kiayias, Katerina Samari

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.
Original languageEnglish
Title of host publication20th Information Security Conference
PublisherSpringer, Cham
Number of pages18
ISBN (Electronic)978-3-319-69659-1
ISBN (Print)978-3-319-69658-4
Publication statusPublished - 2017
Event20th International Information Security Conference - Ho Chi Minh City, Viet Nam
Duration: 22 Nov 201724 Nov 2017

Publication series

NameLecture Notes in Computer Science (LNCS)
PublisherSpringer, Cham
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference20th International Information Security Conference
Abbreviated titleISC 2017
Country/TerritoryViet Nam
CityHo Chi Minh City
Internet address


Dive into the research topics of 'Watermarking Public-Key Cryptographic Functionalities and Implementations'. Together they form a unique fingerprint.

Cite this