Paper 2017/380

Watermarking Cryptographic Functionalities from Standard Lattice Assumptions

Sam Kim and David J. Wu


A software watermarking scheme allows one to embed a "mark" into a program without significantly altering the behavior of the program. Moreover, it should be difficult to remove the watermark without destroying the functionality of the program. Recently, Cohen et al. (STOC 2016) and Boneh et al. (PKC 2017) showed how to watermark cryptographic functions such as PRFs using indistinguishability obfuscation. Notably, in their constructions, the watermark remains intact even against arbitrary removal strategies. A natural question is whether we can build watermarking schemes from standard assumptions that achieve this strong mark-unremovability property. We give the first construction of a watermarkable family of PRFs that satisfy this strong mark-unremovability property from standard lattice assumptions (namely, the learning with errors (LWE) and the one-dimensional short integer solution (SIS) problems). As part of our construction, we introduce a new cryptographic primitive called a translucent PRF. Next, we give a concrete construction of a translucent PRF family from standard lattice assumptions. Finally, we show that using our new lattice-based translucent PRFs, we obtain the first watermarkable family of PRFs with strong unremovability against arbitrary strategies from standard assumptions.

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2017
watermarkingpseudorandom functionsconstrained PRFslattices
Contact author(s)
skim13 @ cs stanford edu
2017-06-02: last of 2 revisions
2017-05-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sam Kim and David J.  Wu},
      title = {Watermarking Cryptographic Functionalities from Standard Lattice Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2017/380},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.