Public Key Encryption Which is Simultaneously a Locally-Decodable Error-Correcting Code
Brett Hemenway, Rafail Ostrovsky · 2007
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, per-form any polynomial-time computation and change an arbitrary (i.e. adversarially chosen) constant fraction of 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 all bits of the plaintext (given the corrupted ciphertext) while making a mistake on any bit of the plaintext with only a negligible in k error probability. In addition, the de-coding algorithm has a Local Decodability property. That is, given a corrupted ciphertext of E(x) the decoding algorithm, for any 1 ≤ i ≤ 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