Cryptology ePrint Archive: Report 2014/851

Near Optimal Rate Homomorphic Encryption for Branching Programs

Aggelos Kiayias and Nikos Leonardos and Helger Lipmaa and 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 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.

Category / Keywords: cryptographic protocols / branching programs, CPIR, homomorphic encryption, lower bounds, Puiseux series

Date: received 17 Oct 2014

Contact author: helger lipmaa at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20141022:163345 (All versions of this report)

Short URL: ia.cr/2014/851

Discussion forum: Show discussion | Start new discussion