Public key encryption which is simultaneously a locally-decodable errorcorrecting code

In this paper, we introduce the notion of a Public-Key Encryption (PKE) Scheme that is also a Locally-Decodable Error-Correcting Code. In particular, our construction simultaneously satisfies all of the following properties: • Our Public-Key Encryption is semantically secure under a certain number-theoretic hardness assumption (a specific variant of the Φ-hiding assumption). • Our Public-Key Encryption function has constant expansion: it maps plaintexts of length n (for any n polynomial in k, where k is a security parameter) to ciphertexts of sizeO (n+ k). The size of our Public Key is also linear in n and k. • Our Public-Key Encryption is also a constant rate binary error-correcting 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 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) whil