Paper 2022/876

Watermarkable Public key Encryption With Efficient Extraction Under Standard Assumptions

Foteini Baldimtsi, George Mason University
Aggelos Kiayias, University of Edinburgh and IOG
Katerina Samari, Hypertech Energy Labs

The current state of the art in watermarked public-key encryption schemes under standard cryptographic assumptions suggests that extracting the embedded message requires either linear time in the number of marked keys or the a-priori knowledge of the marked key employed in the decoder. We present the first scheme that obviates these restrictions in the secret-key marking model, i.e., the setting where extraction is performed using a private extraction key. Our construction offers constant time extraction complexity with constant size keys and ciphertexts and is secure under standard assumptions, namely the Decisional Composite Residuosity Assumption [Eurocrypt '99] and the Decisional Diffie Hellman in prime order subgroups of  square higher order residues.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. SCN 2022
cryptographic watermarking
Contact author(s)
foteini @ gmu edu
Aggelos Kiayias @ ed ac uk
k samari @ hypertech gr
2022-07-07: approved
2022-07-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Foteini Baldimtsi and Aggelos Kiayias and Katerina Samari},
      title = {Watermarkable Public key Encryption With Efficient Extraction Under Standard Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2022/876},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.