## Optimal Rate Private Information Retrieval from Homomorphic Encryption

Aggelos Kiayias, Nikos Leonardos, Helger Lipmaa, Kateryna Pavlyk and Qiang Tang. Optimal Rate Private Information Retrieval from Homomorphic Encryption. Proceedings on Privacy Enhancing Technologies, 2015 (2):222--243, 2015. De Gruyter Open.

File: [.pdf (684 KB)] recommended.

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$ computationally-private information retrieval (CPIR), oblivious transfer (OT), and strong conditional oblivious transfer (SCOT).The new protocols are based on an optimal-rate leveled homomorphic encryption scheme for \emph{large-output} 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 $\Theta (\log m)$-time algorithm to find an integer approximation to $s$.

Keywords: Branching programs, CPIR, homomorphic encryption, OT, Puiseux series, SCOT.

Authors:

Page by Helger Lipmaa. Send your inqueries to <helger.lipmaa>gmail.com.