  A new computational private information retrieval (PIR) scheme based on
random linear codes is presented. A matrix of messages from a McEliece scheme
is used to query the server with carefully chosen errors. The server responds
with the sum of the scalar multiple of the rows of the query matrix and the
files. The user recovers the desired file by erasure decoding the response.
Contrary to code-based cryptographic systems, the scheme presented here enables
to use truly random codes, not only codes disguised as such. Further, we show
the relation to the so-called error subspace search problem and quotient error
search problem, which we assume to be difficult, and show that the scheme is
secure against attacks based on solving these problems.
