Contact: Mahdi Cheraghchi
Room: BC 148
Tel: 021 6931316
Email: mahdi [dot] cheraghchi [at] epfl [dot] ch
In the “Private Information Retrieval (PIR)” problem, a database is shared between several servers. The goal is to query the database for a particular piece of information without giving any of the servers a clue on what information we are actually interested in. If there was only one server, the only solution would be to acquire the whole database and then keep the relevant information. But it turns out that with more than one server (that do not communicate with each other), one can do much better.
This problem is closely related to a fundamental problem in theoretical computer science and coding theory, namely, Locally Decodable Codes (LDC). An LDC is an error correcting code with the property that, given a possibly corrupted encoded message, one can decode any particular bit of the sent message (with high confidence) by reading the received sequence only at a small number of (random) coordinates.
The aim of this project is to study and understand the major results on the two aforementioned problems and their connections. The project is suitable for Masters students with a theoretical interest. It may or may not involve computer programming, depending on the student's preference.