Private Information Retrieval with limited server storage: combinatorics and coding theory

Private Information Retrieval (PIR) schemes operate in the following setting. Suppose a database is stored on one or more remote servers. A user wishes to retrieve a piece of information from the database, but does not wish the servers to know which piece is being retrieved. PIR schemes allow this goal to be achieved.

Classically, the aim of a good PIR scheme is to reduce the amount of communication between the user and each server. More recently, a breakthrough paper of Fazeli, Vardy and Yaakobi has shown that techniques from coding theory can be used to reduce the amount of storage needed by the servers, without increasing the communication complexity to impractical levels: each server need not store the whole database. This aspect will become increasingly important as the size of remotely stored databases increases.

The proposal aims to study the ramifications of this breakthrough result: to construct better PIR schemes; to understand the limitations of the new techniques; to apply these techniques to related areas. This forms a part of a long-running project by the Principal Investigator to apply techniques from combinatorics, coding theory and algebra to problems in cryptography. The proposal includes an 8-month visit of Prof. Tuvi Etzion (Technion) to the UK, and a one-day meeting in the summer of 2016 to raise the academic profile of this rapidly developing area.

In the short term, the impact of the research in this proposal is to the academic community. In the medium-term, the techniques (for enhancing privacy and reducing the need for storage) generated by this project will underpin real-world applications; their importance can only increase as the use of remote storage and of large databases becomes more prevalent. The efficient and secure use of distributed databases will contribute to the full spectrum of the Research Councils' definition of impact, including UK economic competitiveness (particularly in the digital economy), the effective delivery of public services (where large remotely-accessed databases are already used) and by enhancing quality of life by enabling new distributed applications. As well as the direct influence of the research itself, the project will enhance the community's awareness of the area's techniques and problems (via a one-day meeting, and associated collaborations). This background will benefit industry by training consulting academics, and researchers who move into associated industries.