Cryptology ePrint Archive: Report 2007/025

Private Locally Decodable Codes

Rafail Ostrovsky and 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.

Category / Keywords: Computationally Bounded Adversarial Channels, Locally Decodable Codes, Coding Theory, Reed-Muller Codes

Publication Info: ICALP 2007

Date: received 25 Jan 2007, last revised 24 Apr 2007

Contact author: omkant at cs ucla edu

Available formats: PDF | BibTeX Citation

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.

Version: 20070425:055934 (All versions of this report)

Discussion forum: Show discussion | Start new discussion