Watermarking PRFs

The first watermarking scheme with provable security against arbitrary removal strategies is presented by Cohen et al. in [CHN + 16]. Specifically, they construct a watermarkable pseudorandom function (PRF) from indistinguishability obfuscation. In subsequent works [BLW17,KW17,QWZ18,YAL+18,KW19, YAL +19], watermarkable PRFs are constructed from either indistinguishability obfuscation or standard (lattice) assumptions. However, there is still a significant gap in security between the schemes constructed from indistinguishability obfuscation and those from standard assumptions.

In [CHN+16], Cohen et al. also construct watermarking schemes for public key encryption (PKE) and signature from their watermarkable PRFs. Subsequently, (stateful) watermarking schemes for PKE are constructed from any PKE scheme [BKS17]. Recently, in [GKM+19], Goyal et al. construct watermarking schemes for various public key cryptographic primitives with nearly all desired security properties from simple assumptions, such as the existence of one-way function, standard lattice assumptions, etc. This is achieved by a slight relaxation on the correctness of the watermarking scheme. More precisely, in their definition, a marked program is not required to approximately preserve the input/output behaviors of the original program, and instead, it is only required to preserve the “functionality” of the original program. For example, to mark a signing algorithm, it is sufficient that the marked program can still output valid signatures. Unfortunately, such relaxation is not applicable to watermarkable PRF, whose functionality is exactly specified by its input/output behaviors.

Watermarking PRFs

A watermarking scheme for a PRF family  consists of two main algorithms, namely, the marking algorithm and the extraction algorithm. The marking algorithm takes as input the mark key, a message, and a PRF key  and outputs a watermarked circuit, which evaluates  correctly on almost all inputs. The extraction algorithm takes as input the extraction key and a circuit, and outputs either a message or a symbol , which indicates that the circuit is unmarked.

The main security property of a watermarking scheme is unremovability, which requires that given a marked circuit  for a random PRF key (namely, the challenge key), the adversary is not able to remove or modify the embedded message (That is, the extraction algorithm should still output the original message when extracting a circuit created by the adversary. ) without altering the outputs of  on a significant fraction of inputs.

An additional security property is unforgeability, which prevents anyone without the mark key from generating a new watermarked circuit.

Besides, for watermarkable PRF, it is usually required to have pseudorandomness against the watermarking authority, i.e., the pseudorandomness holds against an adversary who possesses the mark key and the extraction key.

When defining security (either unremovability or unforgeability) for watermarking schemes, adversaries with different capabilities are considered. For example, if the adversary is allowed to access more than one marked circuit of the challenge key, the scheme is collusion resistant.

Moreover, we say that the scheme has security with marking (oracle) queries if the security is defined against an adversary who can obtain marked circuits of its generated keys and we say that the scheme has security with public marking if the adversary can obtain the mark key.

Besides, we say that the scheme has security with extraction (oracle) queries if the security is defined against an adversary who can obtain extraction results of its generated circuits and we say that the scheme has security with public extraction if the adversary can obtain the extraction key.

Prior works on watermarkable PRFs

Watermarkable PRF is first constructed by Cohen et al. in [CHN+16]. The scheme is constructed from indistin- guishability obfuscation and has unremovability with public extraction. Later, in [YAL+19], Yang et al. improve Cohen et al.’s scheme to achieve collusion resistance. Both constructions rely on the full power of indistinguishability obfuscation and it seems infeasible to instantiate them from standard assumptions.

Towards constructing watermarkable PRF from standard assumptions, Boneh et al. [BLW17] propose a new approach that builds watermarkable PRF from variants of constrained PRFs [BW13,KPTZ13,BGI14]. The schemes provided in [BLW17] still rely on the existence of indistinguishability obfuscation. Then, building on Boneh et al.’s framework, watermarkable PRFs from standard assumptions are developed. In [KW17], Kim and Wu present the first watermarkable PRF from standard assumptions. The scheme only achieves security with marking queries. Subsequently, in [QWZ18, KW19], watermarkable PRFs that have security with public marking and extraction queries are constructed. However, all of these constructions (from standard assumptions) fail to provide desirable security properties such as security with public extraction and collusion resistance.