## CryptoDB

### Paper: Private Locally Decodable Codes

Authors: Rafail Ostrovsky Omkant Pandey Amit Sahai URL: http://eprint.iacr.org/2007/025 Search ePrint Search Google 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.
##### BibTeX
@misc{eprint-2007-13307,
title={Private Locally Decodable Codes},
booktitle={IACR Eprint archive},
keywords={Computationally Bounded Adversarial Channels, Locally Decodable Codes, Coding Theory, Reed-Muller Codes},
url={http://eprint.iacr.org/2007/025},
note={ICALP 2007 omkant@cs.ucla.edu 13628 received 25 Jan 2007, last revised 24 Apr 2007},
author={Rafail Ostrovsky and Omkant Pandey and Amit Sahai},
year=2007
}