International Association
for Cryptologic Research

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.