Paper 2007/083

Public Key Encryption Which is Simultaneously a Locally-Decodable Error-Correcting Code

Brett Hemenway and 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 essence, this is a protocol that is semantically-secure in the standard sense, but possesses the additional property that it is a binary error-correcting locally-decodable code against any polynomial-time Adversary. That is, we allow a polynomial-time Adversary to read the entire ciphertext, perform any polynomial-time computation and change an arbitrary (i.e. adversarially chosen) constant fraction of {\em all} bits of the ciphertext. The goal of the Adversary is to cause error in decoding any bit of the plaintext. Nevertheless, the decoding algorithm can decode {\bf all} bits of the plaintext (given the corrupted ciphertext) while making a mistake on \emph{any} bit of the plaintext with only a negligible in $k$ error probability. In addition, the decoding algorithm has a {\bf Local Decodability} property. That is, given a corrupted ciphertext of $E(x)$ the decoding algorithm, for any $1 \le i \le n$, can recover the $i$'th bit of the plaintext $x$ with overwhelming probability reading a sublinear (in $|x|$) number of bits of the corrupted ciphertext and performing computation polynomial in the security parameter $k$. We present a general reduction from any semantically-secure encryption protocol and any computational Private Information Retrieval (PIR) protocol to a PKLDC. In particular, since it was shown that homomorphic encryption implies PIR, we give a general reduction from any semantically-secure homomorphic encryption protocol to a 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 bit of the plaintext from a corrupted ciphertext while doing computation sublinear in $n$. We emphasize that this protocol achieves codewords that are only a \emph{constant} times larger than the underlying plaintext, while the best known locally-decodable codes (due to Yekhanin) have codewords that are only slightly subexponential in the length of the plaintext. In addition, we believe that the tools and techniques developed in this paper will be of independent interest in other settings as well.

Note: Applied construction in a more general setting.