Revision #3 Authors: Brett Hemenway, Rafail Ostrovsky

Accepted on: 19th February 2008 00:00

Downloads: 2609

Keywords:

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.

Revision #2 Authors: Brett Hemenway, Rafail Ostrovsky

Accepted on: 8th February 2008 00:00

Downloads: 2642

Keywords:

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

Revision #1 Authors: Brett Hemenway, Rafail Ostrovsky

Accepted on: 28th August 2007 00:00

Downloads: 2479

Keywords:

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.

TR07-021 Authors: Brett Hemenway, Rafail Ostrovsky

Publication: 13th March 2007 06:03

Downloads: 2619

Keywords:

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.