Private Locally Decodable Codes

Rafail Ostrovsky; Omkant Pandey; Amit Sahai

Paper 2007/025

Private Locally Decodable Codes

Rafail Ostrovsky, Omkant Pandey, and Amit Sahai

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.

Note: This is the full version of our paper which appears in ICALP 2007. This version also outdates all previous versions of our paper on eprint.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. ICALP 2007
Keywords: Computationally Bounded Adversarial Channels Locally Decodable Codes Coding Theory Reed-Muller Codes
Contact author(s): omkant @ cs ucla edu
History: 2007-04-25: last of 6 revisions; 2007-01-26: received; See all versions
Short URL: https://ia.cr/2007/025
License: CC BY

BibTeX

@misc{cryptoeprint:2007/025,
      author = {Rafail Ostrovsky and Omkant Pandey and Amit Sahai},
      title = {Private Locally Decodable Codes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2007/025},
      year = {2007},
      url = {https://eprint.iacr.org/2007/025}
}