Private Locally Decodable Codes.
Rafail Ostrovsky, Omkant Pandey, 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 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 1/2. 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.
comment: ICALP 2007: 387-398
Fetch PostScript file of the paper Fetch PDF file of the paper
| Back to Publications List |