cover_image

Watermarking PRF

Kurt Pan XPTY
2020年12月12日 18:29

Note for [BLW 17 PKC] 6.1

Definitions

A watermarking scheme for programs consists of a marking algorithm, which takes as input a program and embeds a “mark” in it, and a verification algorithm that takes an arbitrary program and determines whether it has been marked.

The requirement is that a marked program should preserve the functionality of the original program on almost all inputs, but still be difficult for an adversary to remove the watermark without destroying the functionality.

The marking algorithm can be extended to embed a string into the program; correspondingly, the verification algorithm would extract the embedded string when run on a watermarked program. We say such schemes are message-embedding.[^2]

In a secretly-verifiable scheme, only the holder of a secret key can test if a program is watermarked. In the publicly-verifiable setting, anyone with the public parameters is able to test whether a program is watermarked or not.

Watermarkable Family of PRFs [^2]

The watermarking scheme we give is secretly-verifiable and supports message embedding, where the marking algorithm can embed a string into the program that can later be extracted by the verification algorithm.

For the security parameter  and a message space  a secretly-verifiable message-embedding watermarking scheme for a PRF with key-space  is a tuple of algorithms =(WM.Setup, WM.Mark, WM.Verify) with the following properties.

  • .
  •  outputs a PRF key  and a marked circuit 

Circuit Similarity

 : the two circuits agree on all but an  fraction of inputs.  : the two circuits differ on at least a  fraction of inputs.

Correctness

  • The key  is uniformly distributed over the key-space  of the PRF.
  •  with overwhelming probability

Watermarking security

Experiment : 

  • Marking oracle. On input a message  the challenger returns the pair  WM.Mark(msk, ) to 
  • Challenge oracle. On input a message  the challenger computes  WM.Mark(msk, ) but only returns  to 

Eventually,  outputs a circuit  and the challenger computes and outputs WM.Verify(msk,  ) which is also the output of the experiment, denoted as 

Unremoving Admissibility

  1.  only queries the challenge oracle once,

Unremovability

For all efficient and unremoving admissible adversaries ,  is negligible.

 -Unforging Admissibility

  1.  does not make any challenge oracle queries,
  2. For all  where  is the total number of marking queries the adversary makes  is the output of the marking oracle on the  query

 -Unforgeability

For all efficient and -unforging admissible adversaries , the probability  is negligible.

Construction

any private programmable PRFs  watermarkable PRFs

Intuitively, a programmable PRF is the same as a puncturable PRF except that the holder of the master secret key can also program the value at the punctured point. 

To mark a key  for a private programmable PRF , the marking algorithm first evaluates  at several (secret) points  to obtain values  The marking algorithm then derives a pseudorandom pair  from the values  and outputs a programmed key for msk with the value at  replaced by .

To test whether a circuit  is marked or not, the verification algorithm applies the same procedure as the marking algorithm to obtain a test point  The test algorithm then outputs "marked" if  and "unmarked" otherwise.

Privacy is crucial here because if the adversary knew the “reprogrammed” point , it can trivially remove the watermark by producing a circuit that simply changes the value at .

  • WM.Setup(). The setup algorithm chooses  and  uniformly at random and outputs 

  • WM.Mark(msk, ).

    • and outputs  where  .
    • The mark algorithm first parses msk 
    • It generates  pPRF.Setup(),
    • and then computes the point  and 
    • Then, it computes  pPRF.Program 

  • WM.Verify(msk, ).

    • and outputs  if  and  otherwise.
    • The verification algorithm first parses msk 
    • and then computes 
    • It then sets 

Correctness

If  is a secure  and  is a programmable  then the watermarking scheme  is correct.

Unremovability

If  is a secure  and  is a private programmable , then the watermarking scheme  is unremovable.

 -Unforgeability

If  is a secure  and  is a programmable  then for  poly  the watermarking scheme  is  -unforgeable.

Related work

[CHN+16] [^2] constructs publicly-verifiable watermarking for puncturable PRFs from indistinguishability obfuscation. They pursue the notion of approximate functionality-preserving for watermarking, where the watermarked program agrees with the original program on most inputs.

Barak et al. [BGI+12][^4] showed that assuming iO, perfectly functionality-preserving watermarking is impossible.

Cohen et al. [CHV15][^1] gave a construction from iO which achieves publicly-verifiable watermarking for relaxed notions of unremovability and unforgeability, namely where the adversary can only query the marking oracle before receiving the challenge program in the unremovability game and moreover, is only allowed to query the challenge oracle once (lunchtime unremovability).In addition, the adversary must submit a forged program which differs on the same set of inputs with respect to all programs submitted to the mark oracle in the unforgeability game.

Nishimaki and Wichs [NW15][^3] considered a relaxed notion of watermarking security for message-embedding schemes by considering “selective-message” security, where the adversary must commit to the message to be embedded into the challenge program before interacting with the mark oracle.

Consider a slightly weaker version of the mark oracle which takes as input a message and outputs a random program that embeds the message. Consider secretly-verifiable watermarking constructions while Cohen et al. and Nishimaki and Wichs focus on publically-verifiable constructions.

References

[^1]: [CHV15] Aloni Cohen, Justin Holmgren, and Vinod Vaikuntanathan. Publicly verifiable software watermarking. IACR Cryptology ePrint Archive, 2015:373, 2015.

[^2]: [CHN+16] Aloni Cohen, Justin Holmgren, Ryo Nishimaki, Vinod Vaikuntanathan, and Daniel Wichs. Watermarking cryptographic capabilities. In STOC, pages 1115–1127, 2016.

[^3]: [NW15] Ryo Nishimaki and Daniel Wichs. Watermarking cryptographic programs against arbitrary removal strategies. IACR Cryptology ePrint Archive, 2015:344, 2015.

[^4]: [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, 2012.