Optimal Rate Private Information Retrieval from Homomorphic Encryption

By Aggelos Kiayias, Nikos Leonardos, Helger Lipmaa, Kateryna Pavlyk, Qiang Tang. 2015

46 citations recorded by the source corpus.

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 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 Θ (logm)-time algorithm to find an integer approximation to s.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

PIR with Compressed Queries and Amortized Query Processing (2018, methodology): “On the other hand, CPIR protocols [4, 19, 22, 35, 40, 52, 53, 56, 57, 76] can be used with a database controlled by a single administrative domain (e.”
XPIR : Private Information Retrieval for Everyone (2016, background): “other optimizations, such as those proposed in [32, 36].”
A Simpler Rate-Optimal CPIR Protocol (2017, methodology): “For example, the optimal value of s in [10] is given by a series.”
This Paper Is Included in the Proceedings of the 12th Usenix Symposium on Operating Systems Design and Implementation (osdi '16). Unobservable Communication over Fully Untrusted Infrastructure Unobservable Communication over Fully Untrusted Infrastructure (unknown): “We focus on computational PIR (CPIR) schemes [10] [28] [30] [57] [58] [73] [77] [135] that hide users' access patterns under cryptographic hardness assumptions.”
Compressible FHE with Applications to PIR (2019, methodology): “See [KLL + 15,AMBFK16,LP17] for more motivating discussions.”
Communication-Computation Trade-offs in PIR (2019, methodology): “SealPIR requires only slightly more computation than XPIR but uses almost 1000 times less communication than XPIR (but does not achieve the almost optimal rate of the works [43, 49]).”
Polynomial Batch Codes for Efficient IT-PIR (2016, methodology): “We view these findings as a generalization and extension of Henry, Huang, and Goldberg’s multi-block IT-PIR queries [34], which are likewise constructed from ramp schemes.”