International Association for Cryptologic Research

International Association
for Cryptologic Research


Collusion Resistant Watermarkable PRFs from Standard Assumptions

Rupeng Yang , The University of Hong Kong
Man Ho Au , The University of Hong Kong
Zuoxia Yu , The University of Hong Kong
Qiuliang Xu , Shandong University
DOI: 10.1007/978-3-030-56784-2_20 (login may be required)
Search ePrint
Search Google
Conference: CRYPTO 2020
Abstract: A software watermarking scheme can embed a message into a program without significantly changing its functionality. Moreover, any attempt to remove the embedded message in a marked program will substantially change the functionality of the program. Prior constructions of watermarking schemes focus on watermarking cryptographic functions, such as pseudorandom function (PRF), public key encryption, etc. A natural security requirement for watermarking schemes is collusion resistance, where the adversary’s goal is to remove the embedded messages given multiple marked versions of the same program. Currently, this strong security guarantee has been achieved by watermarking schemes for public key cryptographic primitives from standard assumptions (Goyal et al., CRYPTO 2019) and by watermarking schemes for PRFs from indistinguishability obfuscation (Yang et al., ASIACRYPT 2019). However, no collusion resistant watermarking scheme for PRF from standard assumption is known. In this work, we solve this problem by presenting a generic construction that upgrades a watermarkable PRF without collusion resistance to a collusion resistant one. One appealing feature of our construction is that it can preserve the security properties of the original scheme. For example, if the original scheme has security with extraction queries, the new scheme is also secure with extraction queries. Besides, the new scheme can achieve unforgeability even if the original scheme does not provide this security property. Instantiating our construction with existing watermarking schemes for PRF, we obtain collusion resistant watermarkable PRFs from standard assumptions, offering various security properties.
Video from CRYPTO 2020
  title={Collusion Resistant Watermarkable PRFs from Standard Assumptions},
  author={Rupeng Yang and Man Ho Au and Zuoxia Yu and Qiuliang Xu},