How to Reduce your Enemy’s Information (extended abstract)

If no eavesdropping occurred over the private channel, it is possible for Alice and Bob to publicly verify that no transmission errors nor tampering occurred either. with a 2−K error probability, and end up with an entirely secret final string that is only K bits shorter than the original private transmission. This is optimal. A somewhat shorter common string, on which Eve still has no information, can also be obtained with high probability despite transmission errors over the private channel.If partial eavesdropping occurred over the private channel, leaking up to K bits of information to Eve, in Shannon’s sense, it is still possible for Alice and Bob to publicly verify that no transmission errors nor tampering occurred, with a 2−L error probability, and end up with a final string that is K+L+S bits shorter than the original private transmission, on which Eve has less than 2−s/ln2 bit of information. Here again, transmission errors can be handled at the cost of reducing some more the length of the final common string.Finally, if partial eavesdropping over the private channel is restricted to K physical bits secretly chosen by Eve, it becomes possible again for Alice and Bob to verify with high probability that no errors nor tampering occurred, and end up with a new string on which Eve has no information whatsoever. However, the new string is substantially shorter than if Alice and Bob had tolerated knowledge by Eve of an arbitrarily small fraction of one bit of information.