2-Server PIR with sub-polynomial communication
This work addresses the efficiency of secure data retrieval in distributed systems, representing an incremental improvement by reducing server count in existing protocols.
The paper tackles the problem of reducing communication cost in 2-server Private Information Retrieval (PIR) schemes, achieving a total communication cost of n^{O(√(log log n / log n))}, which improves over the previous O(n^{1/3}) and matches known 3-server schemes.
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.