We prove that if a linear error correcting code
mapping an n-bit message into an m-bit codeword
is such that a bit of the message can
be probabilistically reconstructed by looking at two entries of a
corrupted codeword, then m has to be exponentially large
in n. We also present several extensions of this result.
We then show a reduction from the complexity of one-round,
information-theoretic, Private Information Retrieval Systems (with
two servers) to Locally Decodable Codes, and conclude that if all
the servers' answers are linear combinations of the database
content, then the length of the user's query must be
at least about n / 2^a, where n is the size of the database
and a is the lenght of the answers provided by the servers.
Actually, 2^a can be replaced by O(a^k), where k is the number
of bit locations in the answer that are actually inspected
in the reconstruction.
Copyright. All Rights Reserved.