Perfect Cryptographic Security from Partially Independent Channels
Ueli Maurer
Several protocols are presented that allow two parties Alice and Bob not sharing any secret information initially (except possibly a short key to be used for authentication) to generate a long shared secret key such that even an enemy Eve with unlimited computing power is unable to obtain a non-negligible amount of information (in Shannon's sense) about this key.
Two different models are considered. In a first model we assume that Alice can send information to Bob over a noisy main channel but that Eve is able to receive the same information over a parallel independent noisy channel from Alice to Eve. In a second, more general model we assume that Alice, Bob and Eve receive the output of a random source (e.g., a satellite broadcasting random bits) over three independent individual channels. The condition that the channels be independent can be replaced by the condition that they be independent only to a known, arbitrarily small degree.
We demonstrate that even when Eve's channel is superior (i.e., less noisy) to Alice's and Bob's channel(s), they can generate an information-theoretically secure secret key by communicating over a public (error-free) channel to which Eve is assumed to have unrestricted access. The results of this paper suggest to base the security of cryptographic systems on realistic statistical assumptions about the partial independence of two (three) channels and about a reasonable lower bound on the noise power on the enemy's channel, as an alternative to commonly used approaches based on an intractability hypothesis.
The paper suggests two general conclusions: (1) for cryptographic purposes, a given noisy communication channel should not be converted into an error-free channel (by means of error-correcting codes) on which a conventional cryptographic protocol is executed, but rather cryptographic coding and error-control coding should be combined, and (2) a mere difference in the signals received by the enemy and the legitimate receiver, but not necessarily with an advantage to the receiver (such as his sharing of a secret key with a sender or knowledge of a trapdoor), may be sufficient for achieving cryptographic security. This observation seems to have broader applications in cryptography.
BibTeX Citation
@inproceedings{Maurer91b,
author = {Ueli Maurer},
title = {Perfect Cryptographic Security from Partially Independent Channels},
booktitle = {Proc.~23rd ACM Symposium on Theory of Computing --- STOC~'91},
pages = {561--572},
year = {1991},
month = {8},
publisher = {ACM},
}