International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Simple Watermarking Pseudorandom Functions from Extractable Pseudorandom Generators

Authors:
Estuardo Alpirez Bock , Independent
Chris Brzuska , Aalto University
Russell W. F. Lai , Aalto University
Download:
DOI: 10.62056/aevur-10k
URL: https://cic.iacr.org//p/1/2/13
Search ePrint
Search Google
Abstract:

Watermarking pseudorandom functions (PRF) allow an authority to embed an unforgeable and unremovable watermark into a PRF while preserving its functionality. In this work, we extend the work of Kim and Wu [Crypto'19] who gave a simple two-step construction of watermarking PRFs from a class of extractable PRFs satisfying several other properties – first construct a mark-embedding scheme, and then upgrade it to a message-embedding scheme.

While the message-embedding scheme of Kim and Wu is based on complex homomorphic evaluation techniques, we observe that much simpler constructions can be obtained and from a wider range of assumptions, if we forego the strong requirement of security against the watermarking authority. Concretely, we introduce a new notion called extractable PRGs (xPRGs), from which extractable PRFs (without security against authorities) suitable for the Kim-Wu transformations can be simply obtained via the Goldreich-Goldwasser-Micali (GGM) construction. We provide simple constructions of xPRGs from a wide range of assumptions such as hardness of computational Diffie-Hellman (CDH) in the random oracle model, as well as LWE and RSA in the standard model.

BibTeX
@article{cic-2024-34406,
  title={Simple Watermarking Pseudorandom Functions from Extractable Pseudorandom Generators},
  journal={cic},
  publisher={International Association for Cryptologic Research},
  volume={1, Issue 2},
  url={https://cic.iacr.org//p/1/2/13},
  doi={10.62056/aevur-10k},
  author={Estuardo Alpirez Bock and Chris Brzuska and Russell W. F. Lai},
  year=2024
}