Paper 2014/074
New and Improved KeyHomomorphic Pseudorandom Functions
Abhishek Banerjee and Chris Peikert
Abstract
A \emph{keyhomomorphic} pseudorandom function (PRF) family $\set{F_{s} \colon D \to R}$ allows one to efficiently compute the value $F_{s+t}(x)$ given $F_{s}(x)$ and $F_{t}(x)$. Such functions have many applications, such as distributing the operation of a keydistribution center and updatable symmetric encryption. The only known construction of keyhomomorphic PRFs without random oracles, due to Boneh \etal (CRYPTO~2013), is based on the learning with errors (\lwe) problem and hence on worstcase lattice problems. However, the security proof relies on a very strong \lwe assumption (i.e., very large approximation factors), and hence has quite inefficient parameter sizes and runtimes. In this work we give new constructions of keyhomomorphic PRFs that are based on much weaker \lwe assumptions, are much more efficient in time and space, and are still highly parallel. More specifically, we improve the \lwe approximation factor from exponential in the input length to exponential in its \emph{logarithm} (or less). For input length~$\lambda$ and~$2^{\lambda}$ security against known lattice algorithms, we improve the key size from~$\lambda^{3}$ to~$\lambda$ bits, the public parameters from~$\lambda^{6}$ to~$\lambda^{2}$ bits, and the runtime from~$\lambda^{7}$ to~$\lambda^{\omega+1}$ bit operations (ignoring polylogarithmic factors in~$\lambda$), where $\omega \in [2,2.373]$ is the exponent of matrix multiplication. In addition, we give even more efficient ring\lwebased constructions whose key sizes, public parameters, and \emph{incremental} runtimes on consecutive inputs are all \emph{quasilinear}~$\Otil(\lambda)$, which is optimal up to polylogarithmic factors. To our knowledge, these are the first \emph{lowdepth} PRFs (whether key homomorphic or not) enjoying any of these efficiency measures together with nontrivial proofs of~$2^{\lambda}$ security under any conventional assumption.
Note: Small updates corresponding to Crypto'14 final submission.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A major revision of an IACR publication in CRYPTO 2014
 Keywords
 pseudorandom functionskey homomorphismlearning with errorslattices
 Contact author(s)
 cpeikert @ cc gatech edu
 History
 20140614: last of 2 revisions
 20140204: received
 See all versions
 Short URL
 https://ia.cr/2014/074
 License

CC BY
BibTeX
@misc{cryptoeprint:2014/074, author = {Abhishek Banerjee and Chris Peikert}, title = {New and Improved KeyHomomorphic Pseudorandom Functions}, howpublished = {Cryptology ePrint Archive, Paper 2014/074}, year = {2014}, note = {\url{https://eprint.iacr.org/2014/074}}, url = {https://eprint.iacr.org/2014/074} }