Paper 2018/986

Watermarking PRFs from Lattices: Stronger Security via Extractable PRFs

Sam Kim and David J. Wu

Abstract

A software watermarking scheme enables one to embed a "mark" (i.e., a message) within a program while preserving the program's functionality. Moreover, there is an extraction algorithm that recovers an embedded message from a program. The main security goal is that it should be difficult to remove the watermark without destroying the functionality of the program. Existing constructions of watermarking focus on watermarking cryptographic functions like pseudorandom functions (PRFs); even in this setting, realizing watermarking from standard assumptions remains difficult. The first lattice-based construction of secret-key watermarking due to Kim and Wu (CRYPTO 2017) only ensures mark-unremovability against an adversary who does not have access to the mark-extraction oracle. The construction of Quach et al. (TCC 2018) achieves the stronger notion of mark-unremovability even if the adversary can make extraction queries, but has the drawback that the watermarking authority (who holds the watermarking secret key) can break pseudorandomness of all PRF keys in the family (including unmarked keys). In this work, we construct new lattice-based secret-key watermarking schemes for PRFs that both provide unremovability against adversaries that have access to the mark-extraction oracle and offer a strong and meaningful notion of pseudorandomness even against the watermarking authority (i.e., the outputs of unmarked keys are pseudorandom almost everywhere). Moreover, security of several of our schemes can be based on the hardness of computing nearly polynomial approximations to worst-case lattice problems. This is a qualitatively weaker assumption than that needed for existing lattice-based constructions of watermarking (that support message-embedding), all of which require quasi-polynomial approximation factors. Our constructions rely on a new cryptographic primitive called an extractable PRF, which may be of independent interest.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in CRYPTO 2019
Keywords
watermarkinglatticesPRFs
Contact author(s)
skim13 @ cs stanford edu
History
2019-05-31: revised
2018-10-18: received
See all versions
Short URL
https://ia.cr/2018/986
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/986,
      author = {Sam Kim and David J.  Wu},
      title = {Watermarking PRFs from Lattices: Stronger Security via Extractable PRFs},
      howpublished = {Cryptology ePrint Archive, Paper 2018/986},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/986}},
      url = {https://eprint.iacr.org/2018/986}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.