**Private Puncturable PRFs From Standard Lattice Assumptions**

*Dan Boneh and Sam Kim and Hart 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 {\em 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 1 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.

**Category / Keywords: **pseudorandom functions, lattices, constrained PRFs, puncturable PRFs

**Original Publication**** (with major differences): **IACR-EUROCRYPT-2017

**Date: **received 9 Feb 2017, last revised 15 Feb 2017

**Contact author: **skim13 at cs stanford edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20170215:192307 (All versions of this report)

**Short URL: **ia.cr/2017/100

[ Cryptology ePrint archive ]