Paper 2017/1201

Collusion Resistant Watermarking Schemes for Cryptographic Functionalities

Rupeng Yang and Man Ho Au and Junzuo Lai and Qiuliang Xu and Zuoxia Yu

Abstract

A cryptographic watermarking scheme embeds message into a program while preserving its functionality. Essential security of the watermarking schemes requires that no one could remove the marking message of a marked program without substantially changing its functionality. In practical applications, it is common to mark a program with multiple different messages, e.g. in the secret leaker tracing scenarios. Thus, it is usually required that the watermarking scheme should be secure against the “collusion attacks”, where the adversary can obtain multiple watermarked programs embedded with different messages for the same functionality. However, current works in this area have not formally considered this requirement. In this paper, we formally address the problem and give new security definition for watermarking schemes that captures the collusion attacks. Then we explore the existence of watermarking schemes secure under our new security defjnition: – On the negative side, we observe that all current watermarking schemes either do not support multi-message embedding inherently or are vulnerable to the collusion attacks. – On the positive side, we construct watermarking scheme secure against the collusion attacks for pseudorandom function (PRF). This is achieved by introducing a new message-embedding technique in the watermarking settings and is built on a newly presented primitive, namely, private multi-programmable PRF. Based on our watermarking scheme for PRF, we also construct watermarking schemes for various other cryptographic functionalities.