Russell Impagliazzo (UC San Diego)
Calvin Lab Room 116
Simultaneous Security and Reliability Amplification for a General Channel Model
We present a general notion of channel for cryptographic purposes, that can model either a (classical) physical channel or the consequences of a cryptographic protocol, or any hybrid. We consider simultaneous security and reliability amplification for such channels. We start with a channel where the intended receiver gets the transmitted bit except with some probability and the attacker can guess the transmitted bit except with a somewhat higher probability. We wish to use the channel to define one where the receiver gets the transmitted bit almost certainly while only neglible information is leaked to the attacker.
We show that simultaneous security and reliability amplification is not possible for the most general model of channel, but, at least for some values of the parameters, it is possible for a restricted class of channels that still includes both standard information-theoretic channels and keyless cryptographic protocols. Even in the restricted model, we require that for the original channel, the failure chance for the attacker must be a factor c more than that for the intended receiver. We show that for any c > 4, there is a one-way protocol (where the sender sends information to the receiver only) which achieves simultaneous secrecy and reliability.
From results of Holenstein and Renner, there are no such one-way protocols for c < 2. On the other hand, we also show that for c > 1.5, there are two-way protocols that achieve simultaneous secrecy and reliability. We propose using similar models to address other questions in the theory of cryptography, such as using noisy channels for secret agreement, trade-offs between reliability and security, and the equivalence of various notions of oblivious channels and secure computation.
Joint work with: Ragesh Jaiswal, Valentine Kabanets, Bruce M. Kapron, Valerie King, and Stefano Tessaro.