Optimal Rate Private Information Retrieval from Homomorphic Encryption
Authors: Aggelos Kiayias (National and Kapodistrian University of Athens, Greece), Nikos Leonardos (Université Paris Diderot – Paris 7, France), Helger Lipmaa (University of Tartu, Estonia), Kateryna Pavlyk (University of Tartu, Estonia), Qiang Tang (University of Connecticut, USA)
Volume: 2015
Issue: 2
Pages: 222–243
DOI: https://doi.org/10.1515/popets-2015-0016
Abstract: We consider the problem of minimizing the communication in single-database private information retrieval protocols in the case where the length of the data to be transmitted is large. We present first rate-optimal protocols for 1-out-of-n computationallyprivate information retrieval (CPIR), oblivious transfer (OT), and strong conditional oblivious transfer (SCOT). These protocols are based on a new optimalrate leveled homomorphic encryption scheme for largeoutput polynomial-size branching programs, that might be of independent interest. The analysis of the new scheme is intricate: the optimal rate is achieved if a certain parameter s is set equal to the only positive root of a degree-(m + 1) polynomial, where m is the length of the branching program. We show, by using Galois theory, that even when m = 4, this polynomial cannot be solved in radicals. We employ the Newton-Puiseux algorithm to find a Puiseux series for s, and based on this, propose a Θ(log m)-time algorithm to find an integer approximation to s.
Keywords: Branching programs, CPIR, Galois theory, homomorphic encryption, OT, Puiseux series, SCOT
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.
