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.

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 followi=
ng properties:
1) Our Public-Key Encryption is semantically secure under a certain number-=
theoretic hardness assumption (a specific variant of the $\Phi$-hiding assu=
mption). 2) Our Public-Key Encryption function has \emph{constant expansion=
}: it maps plaintexts of length $n$ (for any $n$ polynomial in $k$, where $=
k$ is a security parameter) to ciphertexts of size $\O(n+k)$. The size of o=
ur Public Key is also linear, $\O(n+k)$. 3) Our Public-Key Encryption is al=
so a \emph{constant rate} binary error-correcting code against any polynomi=
al-time Adversary. That is, we allow a polynomial-time Adversary to read th=
e 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 makin=
g a mistake on \emph{any} bit of the plaintext with only a negligible in $k=
$ error probability. 4) Our Decoding algorithm has a {\bf Local Decodabilit=
y} property. That is, given a corrupted ciphertext of $E(x)$ the decryption=
algorithm, for any $1 \le i \le n$ can recover the $i$'th bit of $x$ (i.e.=
, $x_i$) with overwhelming probability reading at most $\O(k^2)$ bits of th=
e corrupted ciphertext and performing computation \emph{ polynomial in $k$ =
}. Thus, for large plaintext messages (specifically for $|x| =3D \omega(k^{=
2+\epsilon})$), our Public Key Decryption algorithm can decode and error-co=
rrect any $x_i$ computation sublinear in $|x|$.

We believe that the tools and techniques developed in this paper will be of=
independent interest in other settings.=20

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 $\Phi$-hiding assumption).

Our Public-Key Encryption function has \emph{constant expansion}: it maps plaintexts of length $n$ (for any $n$ polynomial in $k$, where $k$ is a
security parameter) to ciphertexts of size $\O(n+k)$. The size of our Public Key is also linear in $n$ and $k$.
Our Public-Key Encryption is also a \emph{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 {\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.

Our Decoding algorithm has a {\bf Local Decodability} property. That is, given a corrupted ciphertext of $E(x)$ the decryption algorithm, for any $1 \le i \le n$ can recover the $i$'th bit of $x$ (i.e., $x_i$) with
overwhelming probability reading at most $\O(k^2)$ bits of the corrupted ciphertext and performing computation \emph{ polynomial in $k$ }.
Thus, for large plaintext messages, our Public Key Decryption algorithm can decode and error-correct any $x_i$ with sublinear (in $|x|$) computation.

We believe that the tools and techniques developed in this paper will be of independent interest in other settings.

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:
\begin{itemize}
\item
Our Public-Key Encryption is semantically secure under a certain number-theoretic hardness assumption
(a specific variant of the $\Phi$-hiding assumption).
\item
Our Public-Key Encryption function has \emph{constant expansion}: it maps plaintexts of length $n$ (for any $n$ polynomial in $k$, where $k$ is a
security parameter) to ciphertexts of size $\O(n+k)$.
The size of our Public Key is also linear in $n$ and $k$.
\item
Our Public-Key Encryption is also a \emph{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 {\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.
\item Our Decoding algorithm has a {\bf Local Decodability} property. That is, given a corrupted ciphertext of $E(x)$
the decryption algorithm, for any $1 \le i \le n$ can recover the $i$'th bit of $x$ (i.e., $x_i$) with
overwhelming probability reading at most $\O(k^2)$ bits of the corrupted ciphertext and performing computation polynomial in $k$.
Thus, for large plaintext messages,
out Public Key Decryption algorithm can decode and error-correct any $x_i$ with sublinear (in $|x|$) computation.
\end{itemize}
We believe that the tools and techniques developed in this paper will be of independent interest in other settings.