{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T17:04:58Z","timestamp":1753895098099,"version":"3.41.2"},"reference-count":25,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,4,7]],"date-time":"2024-04-07T00:00:00Z","timestamp":1712448000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,6,3]]},"abstract":"<jats: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 \u2013 first construct a mark-embedding scheme, and then upgrade it to a message-embedding scheme.<\/jats:p>\n          <jats: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. <\/jats:p>","DOI":"10.62056\/aevur-10k","type":"journal-article","created":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T15:52:04Z","timestamp":1720453924000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["Simple Watermarking Pseudorandom Functions from Extractable Pseudorandom Generators"],"prefix":"10.62056","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8410-5488","authenticated-orcid":false,"given":"Estuardo","family":"Bock","sequence":"first","affiliation":[{"name":"Independent","place":["United Kingdom"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-7485-1217","authenticated-orcid":false,"given":"Chris","family":"Brzuska","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/020hwjq30","id-type":"ROR","asserted-by":"publisher"}],"name":"Aalto University","place":["Finland"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9126-1887","authenticated-orcid":false,"given":"Russell","family":"Lai","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/020hwjq30","id-type":"ROR","asserted-by":"publisher"}],"name":"Aalto University","place":["Finland"]}]}],"member":"48349","published-online":{"date-parts":[[2024,7,8]]},"reference":[{"key":"ref1:jacm\/BarakGIRSVY12","doi-asserted-by":"publisher","DOI":"10.1145\/2160158.2160159","article-title":"On the (im)possibility of obfuscating programs","volume":"59","author":"Boaz Barak","year":"2012","journal-title":"J. ACM"},{"key":"ref2:TCC:HopMolWag07","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1007\/978-3-540-70936-7_20","article-title":"From Weak to Strong Watermarking","volume-title":"TCC\u00a02007","volume":"4392","author":"Nicholas Hopper","year":"2007"},{"key":"ref3:STOC:CHNVW16","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/2897518.2897651","article-title":"Watermarking cryptographic capabilities","volume-title":"48th ACM STOC","author":"Aloni Cohen","year":"2016"},{"key":"ref4:C:KimWu17","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1007\/978-3-319-63688-7_17","article-title":"Watermarking Cryptographic Functionalities from Standard\n  Lattice Assumptions","volume-title":"CRYPTO\u00a02017, Part\u00a0I","volume":"10401","author":"Sam Kim","year":"2017"},{"key":"ref5:TCC:QuaWicZir18","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1007\/978-3-030-03810-6_24","article-title":"Watermarking PRFs Under Standard Assumptions: Public\n  Marking and Security with Extraction Queries","volume-title":"TCC\u00a02018, Part\u00a0II","volume":"11240","author":"Willy Quach","year":"2018"},{"key":"ref6:C:KimWu19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/978-3-030-26954-8_11","article-title":"Watermarking PRFs from Lattices: Stronger Security via\n  Extractable PRFs","volume-title":"CRYPTO\u00a02019, Part\u00a0III","volume":"11694","author":"Sam Kim","year":"2019"},{"key":"ref7:EC:BanPeiRos12","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1007\/978-3-642-29011-4_42","article-title":"Pseudorandom Functions and Lattices","volume-title":"EUROCRYPT\u00a02012","volume":"7237","author":"Abhishek Banerjee","year":"2012"},{"key":"ref8:TCC:BGMRR16","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/978-3-662-49096-9_9","article-title":"On the Hardness of Learning with Rounding over Small\n  Modulus","volume-title":"TCC\u00a02016-A, Part\u00a0I","volume":"9562","author":"Andrej Bogdanov","year":"2016"},{"key":"ref9:STOC:Regev05","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1145\/1060590.1060603","article-title":"On lattices, learning with errors, random linear codes, and\n  cryptography","volume-title":"37th ACM STOC","author":"Oded Regev","year":"2005"},{"key":"ref10:EC:BGGHNS14","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/978-3-642-55220-5_30","article-title":"Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE\n  and Compact Garbled Circuits","volume-title":"EUROCRYPT\u00a02014","volume":"8441","author":"Dan Boneh","year":"2014"},{"key":"ref11:C:GolGolMic84","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/3-540-39568-7_22","article-title":"On the Cryptographic Applications of Random Functions","volume-title":"CRYPTO'84","volume":"196","author":"Oded Goldreich","year":"1984"},{"key":"ref12:RSA:AABBM19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/978-3-030-12612-4_10","article-title":"Doubly Half-Injective PRGs for Incompressible White-Box\n  Cryptography","volume-title":"CT-RSA\u00a02019","volume":"11405","author":"Estuardo Alpirez Bock","year":"2019"},{"key":"ref13:AC:YALXY19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/978-3-030-34578-5_14","article-title":"Collusion Resistant Watermarking Schemes for Cryptographic\n  Functionalities","volume-title":"ASIACRYPT\u00a02019, Part\u00a0I","volume":"11921","author":"Rupeng Yang","year":"2019"},{"key":"ref14:C:YAYX20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"590","DOI":"10.1007\/978-3-030-56784-2_20","article-title":"Collusion Resistant Watermarkable PRFs from Standard\n  Assumptions","volume-title":"CRYPTO\u00a02020, Part\u00a0I","volume":"12170","author":"Rupeng Yang","year":"2020"},{"key":"ref15:AC:GKWW21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/978-3-030-92078-4_9","article-title":"Beyond Software Watermarking: Traitor-Tracing for\n  Pseudorandom Functions","volume-title":"ASIACRYPT\u00a02021, Part\u00a0III","volume":"13092","author":"Rishab Goyal","year":"2021"},{"key":"ref16:PKC:MaiWu22","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/978-3-030-97121-2_16","article-title":"Traceable PRFs: Full Collusion Resistance and Active\n  Security","volume-title":"PKC\u00a02022, Part\u00a0I","volume":"13177","author":"Sarasij Maitra","year":"2022"},{"key":"ref17:EC:MicPei12","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"700","DOI":"10.1007\/978-3-642-29011-4_41","article-title":"Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller","volume-title":"EUROCRYPT\u00a02012","volume":"7237","author":"Daniele Micciancio","year":"2012"},{"key":"ref18:AC:DGHLM19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1007\/978-3-030-34618-8_20","article-title":"Rate-1 Trapdoor Functions from the Diffie-Hellman\n  Problem","volume-title":"ASIACRYPT\u00a02019, Part\u00a0III","volume":"11923","author":"Nico D\u00f6ttling","year":"2019"},{"key":"ref19:CCS:BHKL13","doi-asserted-by":"publisher","first-page":"967","DOI":"10.1145\/2508859.2516734","article-title":"Elligator: elliptic-curve points indistinguishable from\n  uniform random strings","volume-title":"ACM CCS 2013","author":"Daniel J. Bernstein","year":"2013"},{"key":"ref20:C:BonFra01","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/3-540-44647-8_13","article-title":"Identity-Based Encryption from the Weil Pairing","volume-title":"CRYPTO\u00a02001","volume":"2139","author":"Dan Boneh","year":"2001"},{"key":"ref21:C:BelBolONe07","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/978-3-540-74143-5_30","article-title":"Deterministic and Efficiently Searchable Encryption","volume-title":"CRYPTO\u00a02007","volume":"4622","author":"Mihir Bellare","year":"2007"},{"key":"ref22:C:BolFehONe08","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/978-3-540-85174-5_19","article-title":"On Notions of Security for Deterministic Encryption, and\n  Efficient Constructions without Random Oracles","volume-title":"CRYPTO\u00a02008","volume":"5157","author":"Alexandra Boldyreva","year":"2008"},{"key":"ref23:SAC:ChuSte19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1007\/978-3-030-38471-5_28","article-title":"Towards Practical GGM-Based PRF from\n  (Module-)Learning-with-Rounding","volume-title":"SAC 2019","volume":"11959","author":"Chitchanok Chuengsatiansup","year":"2019"},{"key":"ref24:STOC:GolLev89","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1145\/73007.73010","article-title":"A Hard-Core Predicate for all One-Way Functions","volume-title":"21st ACM STOC","author":"Oded Goldreich","year":"1989"},{"key":"ref25:Goldreich01","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546891","volume-title":"Foundations of Cryptography: Basic Tools","volume":"1","author":"Oded Goldreich","year":"2001","ISBN":"https:\/\/id.crossref.org\/isbn\/9780511546891"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T21:26:56Z","timestamp":1733866016000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/2\/13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,8]]},"references-count":25,"URL":"https:\/\/doi.org\/10.62056\/aevur-10k","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"type":"electronic","value":"3006-5496"}],"subject":[],"published":{"date-parts":[[2024,7,8]]},"assertion":[{"value":"2024-04-07","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-03","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-2-37"}}