"Simultaneons security and reliability amplification for unknown channels"
Russell Impagliazzo
UCSD
Wednesday, May 29, 2013, 12:00 pm
EBU3B, Room 4262
Abstract:
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 security and reliability amplification for such channels: converting a channel where the intended receiver gets the bit sent only somewhat more reliably than the attacker can to one where the receiver gets the message sent almost surely, and the attacker has negligible advantage over guessing.
We show that even security amplification is not possible for a general such channel. However, adding an additional transparency axiom allows simultaneous security and reliability amplification when there is a sufficient gap between the failure probabilities of the intended receiver and adversary. The transparency axiom is always true in a purely information-theoretic setting, and true in cryptographic settings without input keys or set-up assumptions. Furthermore, any protocol constructed from transparent channels itself will satisfy transparency. This means that reductions using the axioms are composable, unlike for other restrictions of channels, such as memorylessness.
Say that there is a guarantee that the intended receiver can produce the sent bit with probability at least $1 - \alpha$, and that the attacker can guess the sent bit with probability at most $1- \beta$. We give a one-way protocol for transparent channels assuming $\beta > 3 \alpha$ and a two-way protocol for transparent channels assuming $\beta > 1.5 \alpha$.
Our general model may be useful for other situations involving reliability, authentication and secrecy in a network that acheives security through a combination of cryptographic and information-theoretic assumptions.
Joint work with Valentine Kabanets, Bruce M. Kapron, Valerie King and Stefano Tessaro