International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Private Locally Decodable Codes

Authors:
Rafail Ostrovsky
Omkant Pandey
Amit Sahai
Download:
URL: http://eprint.iacr.org/2007/025
Search ePrint
Search Google
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
}