CryptoDB
Private Locally Decodable Codes
Authors: | |
---|---|
Download: | |
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. |
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 }