## Cryptology ePrint Archive: Report 2014/074

**New and Improved Key-Homomorphic Pseudorandom Functions**

*Abhishek Banerjee and Chris Peikert*

**Abstract: **A \emph{key-homomorphic} 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
key-distribution center and updatable symmetric encryption. The only
known construction of key-homomorphic PRFs without random oracles, due
to Boneh \etal (CRYPTO~2013), is based on the learning with errors
(\lwe) problem and hence on worst-case 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 key-homomorphic 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-\lwe-based constructions
whose key sizes, public parameters, and \emph{incremental} runtimes on
consecutive inputs are all \emph{quasi-linear}~$\Otil(\lambda)$, which
is optimal up to polylogarithmic factors. To our knowledge, these are
the first \emph{low-depth} PRFs (whether key homomorphic or not)
enjoying any of these efficiency measures together with nontrivial
proofs of~$2^{\lambda}$ security under any conventional assumption.

**Category / Keywords: **foundations / pseudorandom functions, key homomorphism, learning with errors, lattices

**Date: **received 3 Feb 2014

**Contact author: **cpeikert at cc gatech edu

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

**Version: **20140204:170151 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]