Communications in Cryptology IACR CiC

Simple Watermarking Pseudorandom Functions from Extractable Pseudorandom Generators


Estuardo Alpirez Bock, Chris Brzuska, Russell W. F. Lai
Estuardo Alpirez Bock ORCID
Independent, United Kingdom
Chris Brzuska ORCID
Aalto University, Finland
chris dot brzuska at aalto dot fi
Russell W. F. Lai ORCID
Aalto University, Finland
russell dot lai at aalto dot fi


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.


Estuardo Alpirez Bock, Alessandro Amadori, Joppe W. Bos, Chris Brzuska, and Wil Michiels. Doubly Half-Injective PRGs for Incompressible White-Box Cryptography. In Mitsuru Matsui, editor, CT-RSA 2019, volume 11405 of LNCS, pages 189–209. March 2019. Springer, Heidelberg. DOI: 10.1007/978-3-030-12612-4_10
Mihir Bellare, Alexandra Boldyreva, and Adam O'Neill. Deterministic and Efficiently Searchable Encryption. In Alfred Menezes, editor, CRYPTO 2007, volume 4622 of LNCS, pages 535–552. August 2007. Springer, Heidelberg. DOI: 10.1007/978-3-540-74143-5_30
Dan Boneh and Matthew K. Franklin. Identity-Based Encryption from the Weil Pairing. In Joe Kilian, editor, CRYPTO 2001, volume 2139 of LNCS, pages 213–229. August 2001. Springer, Heidelberg. DOI: 10.1007/3-540-44647-8_13
Alexandra Boldyreva, Serge Fehr, and Adam O'Neill. On Notions of Security for Deterministic Encryption, and Efficient Constructions without Random Oracles. In David Wagner, editor, CRYPTO 2008, volume 5157 of LNCS, pages 335–359. August 2008. Springer, Heidelberg. DOI: 10.1007/978-3-540-85174-5_19
Dan Boneh, Craig Gentry, Sergey Gorbunov, Shai Halevi, Valeria Nikolaenko, Gil Segev, Vinod Vaikuntanathan, and Dhinakaran Vinayagamurthy. Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE and Compact Garbled Circuits. In Phong Q. Nguyen and Elisabeth Oswald, editors, EUROCRYPT 2014, volume 8441 of LNCS, pages 533–556. May 2014. Springer, Heidelberg. DOI: 10.1007/978-3-642-55220-5_30
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. J. ACM, 59(2):6:1–6:48, 2012. DOI: 10.1145/2160158.2160159
Andrej Bogdanov, Siyao Guo, Daniel Masny, Silas Richelson, and Alon Rosen. On the Hardness of Learning with Rounding over Small Modulus. In Eyal Kushilevitz and Tal Malkin, editors, TCC 2016-A, Part I, volume 9562 of LNCS, pages 209–224. January 2016. Springer, Heidelberg. DOI: 10.1007/978-3-662-49096-9_9
Daniel J. Bernstein, Mike Hamburg, Anna Krasnova, and Tanja Lange. Elligator: elliptic-curve points indistinguishable from uniform random strings. In Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, ACM CCS 2013, pages 967–980. November 2013. ACM Press. DOI: 10.1145/2508859.2516734
Abhishek Banerjee, Chris Peikert, and Alon Rosen. Pseudorandom Functions and Lattices. In David Pointcheval and Thomas Johansson, editors, EUROCRYPT 2012, volume 7237 of LNCS, pages 719–737. April 2012. Springer, Heidelberg. DOI: 10.1007/978-3-642-29011-4_42
Aloni Cohen, Justin Holmgren, Ryo Nishimaki, Vinod Vaikuntanathan, and Daniel Wichs. Watermarking cryptographic capabilities. In Daniel Wichs and Yishay Mansour, editors, 48th ACM STOC, pages 1115–1127. June 2016. ACM Press. DOI: 10.1145/2897518.2897651
Chitchanok Chuengsatiansup and Damien Stehlé. Towards Practical GGM-Based PRF from (Module-)Learning-with-Rounding. In Kenneth G. Paterson and Douglas Stebila, editors, SAC 2019, volume 11959 of LNCS, pages 693–713. August 2019. Springer, Heidelberg. DOI: 10.1007/978-3-030-38471-5_28
Nico Döttling, Sanjam Garg, Mohammad Hajiabadi, Kevin Liu, and Giulio Malavolta. Rate-1 Trapdoor Functions from the Diffie-Hellman Problem. In Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part III, volume 11923 of LNCS, pages 585–606. December 2019. Springer, Heidelberg. DOI: 10.1007/978-3-030-34618-8_20
Oded Goldreich, Shafi Goldwasser, and Silvio Micali. On the Cryptographic Applications of Random Functions. In G. R. Blakley and David Chaum, editors, CRYPTO'84, volume 196 of LNCS, pages 276–288. August 1984. Springer, Heidelberg. DOI: 10.1007/3-540-39568-7_22
Rishab Goyal, Sam Kim, Brent Waters, and David J. Wu. Beyond Software Watermarking: Traitor-Tracing for Pseudorandom Functions. In Mehdi Tibouchi and Huaxiong Wang, editors, ASIACRYPT 2021, Part III, volume 13092 of LNCS, pages 250–280. December 2021. Springer, Heidelberg. DOI: 10.1007/978-3-030-92078-4_9
Oded Goldreich and Leonid A. Levin. A Hard-Core Predicate for all One-Way Functions. In 21st ACM STOC, pages 25–32. May 1989. ACM Press. DOI: 10.1145/73007.73010
Oded Goldreich. Foundations of Cryptography: Basic Tools, volume 1. Cambridge University Press, Cambridge, UK 2001.
Nicholas Hopper, David Molnar, and David Wagner. From Weak to Strong Watermarking. In Salil P. Vadhan, editor, TCC 2007, volume 4392 of LNCS, pages 362–382. February 2007. Springer, Heidelberg. DOI: 10.1007/978-3-540-70936-7_20
Sam Kim and David J. Wu. Watermarking Cryptographic Functionalities from Standard Lattice Assumptions. In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017, Part I, volume 10401 of LNCS, pages 503–536. August 2017. Springer, Heidelberg. DOI: 10.1007/978-3-319-63688-7_17
Sam Kim and David J. Wu. Watermarking PRFs from Lattices: Stronger Security via Extractable PRFs. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part III, volume 11694 of LNCS, pages 335–366. August 2019. Springer, Heidelberg. DOI: 10.1007/978-3-030-26954-8_11
Daniele Micciancio and Chris Peikert. Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller. In David Pointcheval and Thomas Johansson, editors, EUROCRYPT 2012, volume 7237 of LNCS, pages 700–718. April 2012. Springer, Heidelberg. DOI: 10.1007/978-3-642-29011-4_41
Sarasij Maitra and David J. Wu. Traceable PRFs: Full Collusion Resistance and Active Security. In Goichiro Hanaoka, Junji Shikata, and Yohei Watanabe, editors, PKC 2022, Part I, volume 13177 of LNCS, pages 439–469. March 2022. Springer, Heidelberg. DOI: 10.1007/978-3-030-97121-2_16
Willy Quach, Daniel Wichs, and Giorgos Zirdelis. Watermarking PRFs Under Standard Assumptions: Public Marking and Security with Extraction Queries. In Amos Beimel and Stefan Dziembowski, editors, TCC 2018, Part II, volume 11240 of LNCS, pages 669–698. November 2018. Springer, Heidelberg. DOI: 10.1007/978-3-030-03810-6_24
Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Harold N. Gabow and Ronald Fagin, editors, 37th ACM STOC, pages 84–93. May 2005. ACM Press. DOI: 10.1145/1060590.1060603
Rupeng Yang, Man Ho Au, Junzuo Lai, Qiuliang Xu, and Zuoxia Yu. Collusion Resistant Watermarking Schemes for Cryptographic Functionalities. In Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part I, volume 11921 of LNCS, pages 371–398. December 2019. Springer, Heidelberg. DOI: 10.1007/978-3-030-34578-5_14
Rupeng Yang, Man Ho Au, Zuoxia Yu, and Qiuliang Xu. Collusion Resistant Watermarkable PRFs from Standard Assumptions. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part I, volume 12170 of LNCS, pages 590–620. August 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-56784-2_20

PDFPDF Open access

Submitted: 2024-04-07
Accepted: 2024-06-03
Published: 2024-07-08
How to cite

Estuardo Alpirez Bock, Chris Brzuska, and Russell W. F. Lai, "Simple Watermarking Pseudorandom Functions from Extractable Pseudorandom Generators," IACR Communications in Cryptology, vol. 1, no. 2, Jul 08, 2024, doi: 10.62056/aevur-10k.


Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.