## 2-Server PIR with sub-polynomial communication

by Zeev Dvir and Sivakanth Gopi

#### Oded's comments

This is a fantastic result and I am posting it before reading the proof.
It presents a 2-server PIR with communication complexity $n^{o(1)}$,
improving over the two-decades old 2-server PIR of
communication complexity $n^{1/3}$.
Specifically, the communication complexity is $n^{\epsilon(n)}$,
where $\epsilon(n)=(\log n)^{-(0.5-o(1))}$.

#### The original abstract

A 2-server Private Information Retrieval (PIR) scheme allows a user to
retrieve the $i$th bit of an $n$-bit database replicated among two servers
(which do not communicate) while not revealing any information about $i$ to
either server. In this work we construct a 1-round 2-server PIR with total
communication cost $n^{O({\sqrt{\log\log n/\log n}})}$. This improves over
the currently known 2-server protocols which require $O(n^{1/3})$
communication and matches the communication cost of known 3-server PIR
schemes. Our improvement comes from reducing the number of servers in
existing protocols, based on Matching Vector Codes, from 3 or 4 servers
to 2. This is achieved by viewing these protocols in an algebraic way
(using polynomial interpolation) and extending them using partial
derivatives.

See ECCC TR14-094.

Back to
list of Oded's choices.