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 Original Publication (with major differences): IACR-CRYPTO-2014 Date: received 3 Feb 2014, last revised 13 Jun 2014 Contact author: cpeikert at cc gatech edu Available format(s): PDF | BibTeX Citation Note: Small updates corresponding to Crypto'14 final submission. Version: 20140614:003227 (All versions of this report) Short URL: ia.cr/2014/074 Discussion forum: Show discussion | Start new discussion