CRYPTO 2012: DAY 2

In the second section today Stefano Tessaro presented a joint work with Mihir Bellare and Alexander Vardy about semantic security for the wiretap channel. Introduced by Wyner in 1975 and then generalized by Csiszar and Korner in 1978, the wiretap channel is a setting  where one aims to obtain information-theoretic privacy of communicated data based uniquely on the physical assumption that the communication channel from sender to receiver (ChR) is less noisy than the communication channel from sender to adversary (ChA). In more details, we have a sender S that applies a randomized encryption function to a message M and sends the corresponding ciphertext C to a receiver R through a noisy channel ChR, so that R can decrypt C to recover the original message. The ciphertext C is also sent to an adversary using another noiser channel ChA. This physical assumption is the only assumption made: the encryption is keyless and the security is information-theoretic.
In the talk the channel is a randomized map Ch: {0,1} -----> {0,1}, that maps
bit to bit and then is extended to {0,1}^* via Ch(x1,....xn)=Ch(x1)....Ch(xn).
Two examples are the Clear Channel (Ch(b)=b) and the Binary Simmetric Channel with error probability p, BSCp. In his talk Stefano considered the setting where ChR=BSCp and ChA=BSCq, with p<q<=1/2, even the results of their paper are more general and can be used on a larger set of channel.
The rate R is defined as |M|/|C|, i.e. the ratio between the length of the message that is encrypted and the resulting ciphertext.
The goal of this scheme is to achieve privacy, correctness and rate of the scheme as high as possible.

There is a lot of work on this area,  and it has done  almost exclusively within the information  theory   and   coding   (I&C)  community and not within the cryptographic community. So if we look at this work in a cryptographic perspective, we find two major drawbacks:
1) improper privacy notions that are insufficient to provide security of applications and that only consider security for messages chosen uniformly at random
2) no polynomial -time schemes with optimal rate: the results are mostly non-constructive.

Then Stefano described how their paper bridges the gap between previous results on wiretap channel and modern cryptography. First they provide new security notions for defining privacy in the wiretap channel model: on one hand they adapt security notions that are used in the context of encryption, such as semantic security (SS) and distinguishing security (DS) to wiretap channel,  on the other hand they adapt existing notion from information theory, that they call mutual information security (MIS), to take into account arbitrary message distribution, and they prove that they are equivalent, connecting two different way of defining privacy. The second result is a concrete construction of first polynomial time scheme achieving these security notions with optimal rate.