A study of private information retrieval and related primitives.

In this thesis, we study four notions related to Private Information Retrieval (PIR), namely Extended Private Information Retrieval (EPIR), Locally Decodable Codes (LDCs), Distributed Oblivious Transfer (DOT) and Oblivious Linear Function Evaluation (OLFE). EPIR allows a user to evaluate a function on one of the data blocks of a server, in such a way that the server learns no information on neither the function nor the identity of the accessed data block, and the user cannot learn more information on the data blocks except the evaluation. Bringer and Chabanne (2009) proposed an EPIR protocol where the user's function is a polynomial over a finite field and the server's data blocks are elements of the field. In Chapter \ref{chap:EPIR}, we show that their protocol fails frequently when one coefficient of the user's polynomial is primitive in the finite field and the others belong to the prime subfield of the field. Our results call for new EPIR protocols that avoid the above deficiency. LDCs allow one to encode a message as a codeword such that each symbol of the message can be recovered by a probabilistic decoding algorithm which only looks at a small number of coordinates of the codeword, even if a constant fraction of the codeword has been corrupted. Efremenko (2009) proposed a framework for constructing constant-query LDCs of subexponential length. Within this framework, LDCs of query complexity as small as 3 can be obtained. These codes depend on composite numbers which have nice algebraic properties. In Chapter \ref{chap:LDC}, we present our discovery of a new class of algebraically nice numbers. In particular, we show that {\em Mersenne numbers} (numbers of the form $M_t=2^t-1$, where $t$ is a prime) which are products of two primes are algebraically nice. These numbers enable us to improve the known constructions of LDCs and PIR protocols. DOTs are oblivious transfers in the distributed setting where the receiver can learn a secret of the sender with the help of intermediate servers. Compared with the classical oblivious transfers, DOTs are computationally efficient and achieve information-theoretic privacy. However, the known DOT protocols have linear communication complexity between the receiver and servers, which may be prohibitive when the sender has a huge number of secrets. In Chapter \ref{chap:DOT}, we propose both a specific reduction from DOT to polynomial interpolation-based PIR and a general reduction from DOT to any PIR. Our reductions yield the first DOT protocols of sublinear communication complexity between the receiver and servers. OLFE is a cryptographic primitive between two parties where one party has a multivariate linear function and the other party wants to evaluate the function on a private input. In Chapter \ref{chap:OLFE}, we introduce this primitive and present its interesting applications in the cryptographic study and protocol design. We give an unconditionally secure and fully simulatable reduction from classical OT to OLFE. Specifically, we show that any classical OT can be unconditionally securely reduced to a number of invocations of a given OLFE except for a negligible failure probability. Using this reduction, we show that any classical OT can be efficiently reversed in the sense that the roles of the sender and the receiver are interchanged.DOCTOR OF PHILOSOPHY (SPMS