CryptoDB
Public Key Encryption Which is Simultaneously a Locally-Decodable Error-Correcting Code
| Authors: | |
|---|---|
| Download: | |
| Abstract: | 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. |
BibTeX
@misc{eprint-2007-13365,
title={Public Key Encryption Which is Simultaneously a Locally-Decodable Error-Correcting Code},
booktitle={IACR Eprint archive},
keywords={public-key cryptography /},
url={http://eprint.iacr.org/2007/083},
note={ bretth@math.ucla.edu 13753 received 5 Mar 2007, last revised 28 Aug 2007},
author={Brett Hemenway and Rafail Ostrovsky},
year=2007
}