Paper 2017/100

Private Puncturable PRFs From Standard Lattice Assumptions

Dan Boneh, Sam Kim, and Hart Montgomery


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.

Available format(s)
Publication info
A major revision of an IACR publication in EUROCRYPT 2017
pseudorandom functionslatticesconstrained PRFspuncturable PRFs
Contact author(s)
skim13 @ cs stanford edu
2017-02-15: last of 3 revisions
2017-02-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dan Boneh and Sam Kim and Hart Montgomery},
      title = {Private Puncturable {PRFs} From Standard Lattice Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2017/100},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.