Simple Watermarking Pseudorandom Functions from Extractable Pseudorandom Generators

Estuardo Alpirez Bock; Chris Brzuska; Russell W. F. Lai

doi:10.62056/aevur-10k

Simple Watermarking Pseudorandom Functions from Extractable Pseudorandom Generators

Authors

Estuardo Alpirez Bock, Chris Brzuska, Russell W. F. Lai

Estuardo Alpirez Bock

Independent, United Kingdom

Chris Brzuska

Aalto University, Finland
chris dot brzuska at aalto dot fi

Russell W. F. Lai

Aalto University, Finland
russell dot lai at aalto dot fi

Keywords: watermarking extractable pseudorandom function extractable pseudorandom generator

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.

References

[AAB⁺19]

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

Google Scholar ePrint

[BBO07]

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

Google Scholar ePrint

[BF01]

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

Google Scholar ePrint

[BFO08]

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

Google Scholar ePrint

[BGG⁺14]

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

Google Scholar ePrint

[BGI⁺12]

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

Google Scholar ePrint

[BGM⁺16]

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

Google Scholar ePrint

[BHKL13]

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

Google Scholar ePrint

[BPR12]

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

Google Scholar ePrint

[CHN⁺16]

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

Google Scholar ePrint

[CS19]

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

Google Scholar ePrint

[DGH⁺19]

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

Google Scholar ePrint

[GGM84]

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

Google Scholar ePrint

[GKWW21]

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

Google Scholar ePrint

[GL89]

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

Google Scholar ePrint

[Gol01]

Oded Goldreich. Foundations of Cryptography: Basic Tools, volume 1. Cambridge University Press, Cambridge, UK 2001.

Google Scholar ePrint

[HMW07]

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

Google Scholar ePrint

[KW17]

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

Google Scholar ePrint

[KW19]

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

Google Scholar ePrint

[MP12]

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

Google Scholar ePrint

[MW22]

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

Google Scholar ePrint

[QWZ18]

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

Google Scholar ePrint

[Reg05]

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

Google Scholar ePrint

[YAL⁺19]

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

Google Scholar ePrint

[YAYX20]

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

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/aevur-10k

History

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.

License

Copyright is held by the author(s)

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

@article{CiC-1-2-13,
    author = "Bock, Estuardo Alpirez and Brzuska, Chris and Lai, Russell W. F.",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Simple Watermarking Pseudorandom Functions from Extractable Pseudorandom Generators",
    volume = "1",
    number = "2",
    date = "2024-07-08",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/aevur-10k"
}

TY - JOUR
AU - Bock, Estuardo
AU - Brzuska, Chris
AU - Lai, Russell
PY  - 2024
TI  - Simple Watermarking Pseudorandom Functions from Extractable Pseudorandom Generators
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 2
DO  - 10.62056/aevur-10k
UR  - https://doi.org/10.62056/aevur-10k
AB  - <p>  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.</p><p>  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. </p>
ER  -

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.