Watermarking PRFs under Standard Assumptions: Public Marking and Security with Extraction Queries

Willy Quach; Daniel Wichs; Giorgos Zirdelis

Paper 2018/906

Watermarking PRFs under Standard Assumptions: Public Marking and Security with Extraction Queries

Willy Quach, Daniel Wichs, and Giorgos Zirdelis

Abstract

A software watermarking scheme can embed some information called a mark into a program while preserving its functionality. No adversary can remove the mark without damaging the functionality of the program. Cohen et al. (STOC '16) gave the first positive results for watermarking, showing how to watermark certain pseudorandom function (PRF) families using indistinguishability obfuscation (iO). Their scheme has a secret marking procedure to embed marks in programs and a public extraction procedure to extract the marks from programs; security holds even against an attacker that has access to a marking oracle. Kim and Wu (CRYPTO '17) later constructed a PRF watermarking scheme under only the LWE assumption. In their scheme, both the marking and extraction procedures are secret, but security only holds against an attacker with access to a marking oracle but not an extraction oracle. In fact, it is possible to completely break the security of the latter scheme using extraction queries, which is a significant limitation in any foreseeable application. In this work, we construct a new PRF watermarking scheme with the following properties. * The marking procedure is public and therefore anyone can embed marks in PRFs from the family. Previously we had no such construction even using obfuscation. * The extraction key is secret, but marks remain unremovable even if the attacker has access to an extraction oracle. Previously we had no such construction under standard assumptions. * Our scheme is simple, uses generic components and can be instantiated under many different assumptions such as DDH, Factoring or LWE. The above benefits come with one caveat compared to prior work: the PRF family that we can watermark depends on the public parameters of the watermarking scheme and the watermarking authority has a secret key which can break the security of all of the PRFs in the family. Since the watermarking authority is usually assumed to be trusted, this caveat appears to be acceptable.

Metadata

Available format(s): PDF
Publication info: Published by the IACR in TCC 2018
Contact author(s): zirdelis g @ husky neu edu
History: 2018-09-26: revised; 2018-09-25: received; See all versions
Short URL: https://ia.cr/2018/906
License: CC BY

BibTeX

@misc{cryptoeprint:2018/906,
      author = {Willy Quach and Daniel Wichs and Giorgos Zirdelis},
      title = {Watermarking {PRFs} under Standard Assumptions: Public Marking and Security with Extraction Queries},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/906},
      year = {2018},
      url = {https://eprint.iacr.org/2018/906}
}