Helger Lipmaa's publications |

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.

- Aggelos Kiayias
- Nikos Leonardos
- Helger Lipmaa
- Kateryna Pavlyk
- Qiang Tang

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