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 line of 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}
}

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:
@inproceedings{KW17a,
  author     = {Sam Kim and David J. Wu},
  title      = {Watermarking Cryptographic Functionalities from Standard Lattice Assumptions},
  booktitle  = {{CRYPTO}},
  year       = {2017}
}

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}
}