Paper 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.

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.