Paper 2014/851
Near Optimal Rate Homomorphic Encryption for Branching Programs
Aggelos Kiayias, Nikos Leonardos, Helger Lipmaa, Kateryna Pavlyk, and Qiang Tang
Abstract
We initiate the study of good rate homomorphic encryption schemes. Based on previous work on securely evaluating (binary I/O) branching programs, we propose a leveled homomorphic encryption scheme for {\em largeoutput} polynomialsize branching programs (which we call $\mathbf{L/poly}$) that possesses near optimalrate. The rate analysis of the new scheme is intricate: the best rate is achieved if a certain parameter $s$ is set equal to the only positive root of a degree$m$ polynomial, where $m$ is the length of the branching program. We employ the NewtonPuiseux algorithm to find a Puiseux series for this parameter, and based on this, propose a $\Theta (\log m)$time algorithm to find an integer approximation to $s$. We also describe a rateoptimal 1outof$n$ CPIR based on rateoptimal homomorphic encryption. In concrete terms, when applied to say, a movie database with $n = 2^{16}$ elements of $\ell = 3.8 \cdot 10^{9}$bits, the client can privately download a movie with a communication rate of almost $0.99$, hence sacrificing only about $1\%$ of bandwidth for privacy. We also analyze the optimality of the rate efficiency of our scheme in a novel model that may be of independent interest. Our $1$outof$n$ CPIR has rate $ 1 1.72 \sqrt{k / \ell} \cdot \log_{2} n + O_\ell(\ell^{1})$, while we show that no blackbox construction surpasses $1  \sqrt{k / \ell} (\log n/ \log \log n) + O_\ell(\ell^{1})$ in terms of rate, where $\ell$ is the length of the database elements and $k$ the security parameter.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint. MINOR revision.
 Keywords
 branching programsCPIRhomomorphic encryptionlower boundsPuiseux series
 Contact author(s)
 helger lipmaa @ gmail com
 History
 20141022: received
 Short URL
 https://ia.cr/2014/851
 License

CC BY
BibTeX
@misc{cryptoeprint:2014/851, author = {Aggelos Kiayias and Nikos Leonardos and Helger Lipmaa and Kateryna Pavlyk and Qiang Tang}, title = {Near Optimal Rate Homomorphic Encryption for Branching Programs}, howpublished = {Cryptology ePrint Archive, Paper 2014/851}, year = {2014}, note = {\url{https://eprint.iacr.org/2014/851}}, url = {https://eprint.iacr.org/2014/851} }