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 kx that enables one to evaluate the PRF at all points but one. The punctured key kx 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 kx completely reveals the punctured point x: given kx it is easy to determine x. A private puncturable PRF is one where kx 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.