Welcome to the resource topic for 2014/851
Title:
Near Optimal Rate Homomorphic Encryption for Branching Programs
Authors: Aggelos Kiayias, Nikos Leonardos, Helger Lipmaa, Kateryna Pavlyk, 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.
ePrint: https://eprint.iacr.org/2014/851
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 .