A Probabilistic Error-Correcting Scheme

S.  Decatur; O.  Goldreich; D.  Ron

Paper 1997/005

A Probabilistic Error-Correcting Scheme

S. Decatur, O. Goldreich, and D. Ron

Abstract

In the course of research in Computational Learning Theory, we found ourselves in need of an error-correcting encoding scheme for which few bits in the codeword yield no information about the plain message. Being unaware of a previous solution, we came-up with the scheme presented here. Since this scheme may be of interest to people working in Cryptography, we thought it may be worthwhile to ``publish'' this part of our work within the Cryptography community. Clearly, a scheme as described above cannot be deterministic. Thus, we introduce a probabilistic coding scheme which, in addition to the standard coding theoretic requirements, has the feature that any constant fraction of the bits in the (randomized) codeword yields no information about the message being encoded. This coding scheme is also used to obtain efficient constructions for the Wire-Tap Channel Problem.

Metadata

Available format(s): PS
Publication info: Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Contact author(s): oded @ theory lcs mit edu
History: 1997-04-21: received
Short URL: https://ia.cr/1997/005
License: CC BY

BibTeX

@misc{cryptoeprint:1997/005,
      author = {S.  Decatur and O.  Goldreich and D.  Ron},
      title = {A Probabilistic Error-Correcting Scheme},
      howpublished = {Cryptology {ePrint} Archive, Paper 1997/005},
      year = {1997},
      url = {https://eprint.iacr.org/1997/005}
}