Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
Private Locally Decodable Codes
verfasst von : Rafail Ostrovsky, Omkant Pandey, Amit Sahai
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
efficient
locally decodable codes with positive information rate and
low
(almost optimal) query complexity which can correctly decode any given bit of the message from constant channel error rate
ρ
. 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.