**
Public-Key Locally-Decodable Codes.
**

*
Brett Hemenway, Rafail Ostrovsky
*

**
Abstract:
**

In this paper we introduce the notion of a Public-Key Encryption Scheme that is also a Locally-Decodable Error-Correcting Code (PKLDC). In particular, we allow any polynomial-time adversary
to read the entire ciphertext, and corrupt a constant fraction of the bits of the *entire* ciphertext. Nevertheless, the decoding algorithm can recover any bit of the plaintext with all
but negligible probability by reading only a sublinear number of bits of the (corrupted) ciphertext.
We give a general construction of a PKLDC from any Semantically-Secure Public Key Encryption (SS-PKE) and any Private Information Retrieval (PIR) protocol. Since Homomorphic encryption implies
PIR, we also show a reduction from any Homomorphic encryption protocol to PKLDC.
Applying our construction to the best known PIR protocol (that of Gentry and Ramzan), we obtain a PKLDC, which for messages of size n and security parameter
k achieves ciphertexts of size O(n), public key of size O(n+k),
and locality of size O(k^2). This means that for messages of length n = \omega(k^{2+\epsilon}),
we can decode a bit of the plaintext from a corrupted ciphertext while doing computation sublinear in n.

**comment:**
CRYPTO 2008: 126-143

Fetch PostScript file of the paper Fetch PDF file of the paper

Back to Publications List |