International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Private Locally Decodable Codes

Rafail Ostrovsky
Omkant Pandey
Amit Sahai
Search ePrint
Search Google
Abstract: We consider the problem of constructing efficient locally decodable codes in the presence of a computationally bounded adversary. Assuming the existence of one-way functions, we construct {\em efficient} locally decodable codes with positive information rate and \emph{low} (almost optimal) query complexity which can correctly decode any given bit of the message from constant channel error rate $\rho$. This compares favorably to our state of knowledge locally-decodable codes without cryptographic assumptions. For all our constructions, the probability for any polynomial-time adversary, that the decoding algorithm incorrectly decodes any bit of the message is negligible in the security parameter.
  title={Private Locally Decodable Codes},
  booktitle={IACR Eprint archive},
  keywords={Computationally Bounded Adversarial Channels, Locally Decodable Codes, Coding Theory, Reed-Muller Codes},
  note={ICALP 2007 13628 received 25 Jan 2007, last revised 24 Apr 2007},
  author={Rafail Ostrovsky and Omkant Pandey and Amit Sahai},