View article

In the course of research in computational learning theory, we found ourselves in need of an error-correcting encoding scheme for which relatively 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.

Clearly, a scheme as postulated above cannot be deterministic. Thus, we introduce a probabilistic coding scheme that, 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.