Paper 2007/083
Public Key Encryption Which is Simultaneously a LocallyDecodable ErrorCorrecting Code
Brett Hemenway and Rafail Ostrovsky
Abstract
In this paper, we introduce the notion of a PublicKey Encryption Scheme that is also a LocallyDecodable ErrorCorrecting Code (PKLDC). In essence, this is a protocol that is semanticallysecure in the standard sense, but possesses the additional property that it is a binary errorcorrecting locallydecodable code against any polynomialtime Adversary. That is, we allow a polynomialtime Adversary to read the entire ciphertext, perform any polynomialtime 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 semanticallysecure 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 semanticallysecure 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 locallydecodable 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.
Note: Applied construction in a more general setting.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. A preliminary version of this work appeared in CRYPTO 2008
 Keywords
 Public Key CryptographyLocally Decodable CodesError Correcting CodesBounded Channel ModelChinese Remainder TheoremPrivate Information Retrieval
 Contact author(s)
 bhemen @ umich edu
 History
 20120322: last of 4 revisions
 20070305: received
 See all versions
 Short URL
 https://ia.cr/2007/083
 License

CC BY
BibTeX
@misc{cryptoeprint:2007/083, author = {Brett Hemenway and Rafail Ostrovsky}, title = {Public Key Encryption Which is Simultaneously a LocallyDecodable ErrorCorrecting Code}, howpublished = {Cryptology ePrint Archive, Paper 2007/083}, year = {2007}, note = {\url{https://eprint.iacr.org/2007/083}}, url = {https://eprint.iacr.org/2007/083} }