International Association
for Cryptologic Research

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.