# Private Puncturable PRFs From Standard Lattice Assumptions

**Authors:**

*D. Boneh, S. Kim, and H. Montgomery*

** Abstract: **

A puncturable pseudorandom function (PRF) has a master key k that enables one to evaluate the PRF at all points of the domain, and has a punctured key k_{x} that enables one to evaluate the PRF at all points but one. The punctured key k_{x} reveals no information about the value of the PRF at the punctured point x. Punctured PRFs play an important role in cryptography, especially in applications of indistinguishability obfuscation. However, in previous constructions, the punctured key k_{x} completely reveals the punctured point x: given k_{x} it is easy to determine x. A *private* puncturable PRF is one where k_{x} reveals nothing about x. This concept was defined by Boneh, Lewi, and Wu, who showed the usefulness of private puncturing, and gave constructions based on multilinear maps. The question is whether private puncturing can be built from a standard (weaker) cryptographic assumption.

We construct the first privately puncturable PRF from standard lattice assumptions, namely from the hardness of learning with errors (LWE) and one dimensional short integer solutions (1D-SIS), which have connections to worst-case hardness of general lattice problems. Our starting point is the (non-private) PRF of Brakerski and Vaikuntanathan. We introduce a number of new techniques to enhance this PRF, from which we obtain a privately puncturable PRF. In addition, we also study the simulation based definition of private constrained PRFs for general circuits, and show that the definition is not satisfiable.

** Reference:**

In proceedings of Eurocrypt 2017, pp. 415-445.

**Full paper:**
pdf

**Related papers:**
See this paper and this paper.