Paper 2014/851

Near Optimal Rate Homomorphic Encryption for Branching Programs

Aggelos Kiayias, Nikos Leonardos, Helger Lipmaa, Kateryna Pavlyk, and Qiang Tang


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 large-output} polynomial-size branching programs (which we call $\mathbf{L/poly}$) that possesses near optimal-rate. 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 Newton-Puiseux 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 rate-optimal 1-out-of-$n$ CPIR based on rate-optimal 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$-out-of-$n$ CPIR has rate $ 1- 1.72 \sqrt{k / \ell} \cdot \log_{2} n + O_\ell(\ell^{-1})$, while we show that no black-box 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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
branching programsCPIRhomomorphic encryptionlower boundsPuiseux series
Contact author(s)
helger lipmaa @ gmail com
2014-10-22: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.