Rafail Ostrovsky - Publications

Public-Key Locally-Decodable Codes.

Brett Hemenway, Rafail Ostrovsky


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