Welcome to the resource topic for 2014/074
Title:
New and Improved Key-Homomorphic Pseudorandom Functions
Authors: Abhishek Banerjee, 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.
ePrint: https://eprint.iacr.org/2014/074
Talk: https://www.youtube.com/watch?v=531k4JJgseM
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .