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.