UCL Business PLC
In this paper, the authors introduce the notion of a Public-Key Encryption (PKE) scheme that is also a locally-decodable error-correcting code. In particular, they 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. They give a general construction of a PKLDC from any Semantically-Secure Public Key Encryption (SS-PKE) and any Private Information Retrieval (PIR) protocol.