Private Constrained PRFs

A constrained pseudorandom function (PRF) is a PRF for which one can generate constrained keys that can only be used to evaluate the PRF on a subset of the domain. In this work, we introduce the notion of a private constrained PRF, which is a constrained PRF with the additional property that the constrained key also hides the constraint. In addition to giving constructions of private constrained PRFs, we also explore the connections between private constrained PRFs and other cryptographic primitives, such as watermarking and constrained invertible pseudorandom functions (IPFs).

Constraining Pseudorandom Functions Privately

Contributors: Dan Boneh, Kevin Lewi, and David J. Wu

Abstract:

In a constrained pseudorandom function (PRF), the master secret key can be used to derive constrained keys, where each constrained key k is constrained with respect to some Boolean circuit C. A constrained key k can be used to evaluate the PRF on all inputs x for which C(x) = 1. In almost all existing constrained PRF constructions, the constrained key k reveals its constraint C.

In this paper we introduce the concept of private constrained PRFs, which are constrained PRFs with the additional property that a constrained key does not reveal its constraint. Our main notion of privacy captures the intuition that an adversary, given a constrained key k for one of two circuits C0 and C1, is unable to tell which circuit is associated with the key k. We show that constrained PRFs have natural applications to searchable symmetric encryption, cryptographic watermarking, and much more.

To construct private constrained PRFs we first demonstrate that our strongest notions of privacy and functionality can be achieved using indistinguishability obfuscation. Then, for our main constructions, we build private constrained PRFs for bit-fixing constraints and for puncturing constraints from concrete algebraic assumptions.

Resources:

BibTeX:
@inproceedings{BLW17,
  author    = {Dan Boneh and Kevin Lewi and David J. Wu},
  title     = {Constraining Pseudorandom Functions Privately},
  booktitle = {International Conference on Practice and Theory in Public-Key Cryptography ({PKC})},
  year      = {2017}
}

Beyond Software Watermarking: Traitor-Tracing for Pseudorandom Functions

Contributors: Rishab Goyal, Sam Kim, Brent Waters, and David J. Wu

Abstract:

Software 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. Such schemes are often considered for proving software ownership or for digital rights management. Existing constructions of watermarking have focused primarily on watermarking pseudorandom functions (PRFs).

In this work, we revisit the definitional foundations of watermarking, and begin by highlighting a major flaw in existing security notions. Existing security notions for watermarking only require that the identifier be successfully extracted from programs that preserve the exact input/output behavior of the original program. In the context of PRFs, this means that an adversary that constructs a program which computes a quarter of the output bits of the PRF or that is able to distinguish the outputs of the PRF from random are considered to be outside the threat model. However, in any application (e.g., watermarking a decryption device or an authentication token) that relies on PRF security, an adversary that manages to predict a quarter of the bits or distinguishes the PRF outputs from random would be considered to have defeated the scheme. Thus, existing watermarking schemes provide very little security guarantee against realistic adversaries. None of the existing constructions of watermarkable PRFs would be able to extract the identifier from a program that only outputs a quarter of the bits of the PRF or one that perfectly distinguishes.

To address the shortcomings in existing watermarkable PRF definitions, we introduce a new primitive called a traceable PRF. Our definitions are inspired by similar definitions from public-key traitor tracing, and aim to capture a very robust set of adversaries: namely, any adversary that produces a useful distinguisher (i.e., a program that can break PRF security), can be traced to a specific identifier. We provide a general framework for constructing traceable PRFs via an intermediate primitive called private linear constrained PRFs. Finally, we show how to construct traceable PRFs from a similar set of assumptions previously used to realize software watermarking. Namely, we obtain a single-key traceable PRF from standard lattice assumptions and a fully collusion-resistant traceable PRF from indistinguishability obfuscation (together with injective one-way functions).

Resources:

BibTeX:
@inproceedings{GKWW21,
  author    = {Rishab Goyal and Sam Kim and Brent Waters and David J. Wu},
  title     = {Beyond Software Watermarking: Traitor-Tracing for Pseudorandom Functions},
  booktitle = {{ASIACRYPT}},
  year      = {2021}
}

Watermarking Cryptographic Functionalities from Standard Lattice Assumptions

Contributors: Sam Kim and David J. Wu

Abstract:

A software watermarking scheme allows one to embed a “mark” into a program without significantly altering the behavior of the program. Moreover, it should be difficult to remove the watermark without destroying the functionality of the program. Recently, Cohen et al. (STOC 2016) and Boneh et al. (PKC 2017) showed how to watermark cryptographic functions such as PRFs using the full power of general-purpose indistinguishability obfuscation. Notably, in their constructions, the watermark remains intact even against arbitrary removal strategies. A natural question is whether we can build watermarking schemes from standard assumptions that achieve this strong mark-unremovability property.

We give the first construction of a watermarkable family of PRFs that satisfy this strong mark-unremovability property from standard lattice assumptions (namely, the learning with errors (LWE) and the one-dimensional short integer solution (SIS) problems). As part of our construction, we introduce a new cryptographic primitive called a translucent PRF. Next, we give a concrete construction of a translucent PRF family from standard lattice assumptions. Finally, we show that using our new lattice-based translucent PRFs, we obtain the first watermarkable family of PRFs with strong unremovability against arbitrary strategies from standard assumptions.

Resources:

BibTeX (Conference):
@inproceedings{KW17,
  author     = {Sam Kim and David J. Wu},
  title      = {Watermarking Cryptographic Functionalities from Standard Lattice Assumptions},
  booktitle  = {{CRYPTO}},
  year       = {2017}
}
BibTeX (Journal):
@article{KW21,
  author     = {Sam Kim and David J. Wu},
  title      = {Watermarking Cryptographic Functionalities from Standard Lattice Assumptions},
  journal    = {J. Cryptology},
  volume     = {34},
  number     = {28},
  pages      = {1--76},
  year       = {2021}
}

Constrained Keys for Invertible Pseudorandom Functions

Contributors: Dan Boneh, Sam Kim, and David J. Wu

Abstract:

A constrained pseudorandom function (PRF) is a secure PRF for which one can generate constrained keys that can only be used to evaluate the PRF on a subset of the domain. Constrained PRFs are used widely, most notably in applications of indistinguishability obfuscation (iO). In this paper we show how to constrain an invertible PRF (IPF), which is significantly harder. An IPF is a secure injective PRF accompanied by an inversion algorithm. A constrained key for an IPF can only be used to evaluate the IPF on a subset S of the domain, and to invert the IPF on the image of S. We first define the notion of a constrained IPF and then give two main constructions: one for puncturing an IPF and the other for (single-key) circuit constraints. Both constructions rely on recent work on private constrained PRFs. We also show that constrained pseudorandom permutations for many classes of constraints are impossible under our definition.

Resources:

BibTeX:
@inproceedings{BKW17,
  author    = {Dan Boneh and Sam Kim and David J. Wu},
  title     = {Constrained Keys For Invertible Pseudorandom Functions},
  booktitle = {{TCC}},
  year      = {2017}
}