Private Information Retrieval with non-MDS codes and small field sizes
Dr. Oliver Gnilke
Aalto University
In private information retrieval a user seeks to download a file from a database without having to reveal his interest in that file. The current setup considered assumes a distributed storage system on n servers, each receiving a request from the user. We allow for up to t of these servers to collude, that is to gather the received queries to determine the index i of the file of interest. The parameter of interest in these schemes is the PIR rate, i.e. the number of information symbols of file i that are retrieved over the number of informations symbols retrieved in total.
Several schemes for this scenarios, or variants, have been proposed, but most of them rely on using MDS codes. In the presented work we focus our attention on non-MDS codes over small fields, especially binary Reed-Muller codes. We show that for a [n,k] storage code C the same PIR rate as for [n,k] MDS codes can be achieved in many cases.
Oliver Gnilke is a postdoctoral researcher in the Algebra, Number Theory, and Applications Research Group at Aalto University. He received his PhD in mathematics from University College Dublin under the supervision of Prof. Marcus Greferath in 2015. His research interests include coding theory, discrete math, and their applications to security and privacy. Currently he is working on ring-linear codes, private information retrieval, wiretap codes, and design theory.