Multi-value private information retrieval with colluding databases via trace functions.

A classic t -private PIR (private information retrieval) scheme allows a user to retrieve one out of n values from k communicating replicated databases while any t of the k databases cannot identify the value being retrieved. However, in reality, the user may be more interested in retrieving multiple values simultaneously. This paper is devoted to the PIR problem with m retrieved values and k databases against t colluding databases (t -private MPIR) in the context of information-theoretic security. The relationship m ⩽ w (k - t) is derived, where w is the largest average amount of information got by the user from each of the k databases. When w = 1 , via trace functions in finite fields, a t -private MPIR scheme retrieving m = k - t values is presented with the complexity O (log n). Our scheme provides a lower complexity than those in the literature (the best known complexity for general t and k is a fractional power function of n). [ABSTRACT FROM AUTHOR]