[Resource Topic] 1997/005: A Probabilistic Error-Correcting Scheme

Welcome to the resource topic for 1997/005

A Probabilistic Error-Correcting Scheme

Authors: S. Decatur, O. Goldreich, D. Ron


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.

ePrint: https://eprint.iacr.org/1997/005

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .