Watermarking and Traitor Tracing for PRFs

David Wu (University of Virginia) Lattices: Algorithms, Complexity, and Cryptography Seminar, Apr. 23, 2020 A software watermarking scheme provides a method to prevent unauthorized distribution of software. Specifically, watermarking schemes allow a user to embed an identifier into a piece of code such that the resulting program is nearly functionally-equivalent to the original program, and yet, it is difficult to remove the identifier without destroying the functionality of the program. Existing constructions of watermarking have focused primarily on watermarking pseudorandom functions (PRFs). In this talk, I will revisit the definitional foundations of software watermarking and highlight some of the limitations in the current formalization. I will then introduce a new notion of a "traceable PRF" which provides a similar functionality as a watermarkable PRF, but in a much stronger security model. I will also describe how to construct traceable PRFs from private constrained PRFs and then conclude the talk with a general overview of existing constructions of (private) constrained PRFs from lattices. Based primarily on a joint work with Rishab Goyal, Sam Kim, and Brent Waters.