CWI Cryptology Group

Abstract: Consider a scenario where A and B are connected by n different channels and A wishes to communicate a message to B securely in presence of an adversary. By securely communicating a message we mean that the message is not revealed to the adversary, that the message is correctly received by B and that B does not accept an incorrect message. Of the n channels, the adversary may control t channels (A and B do not know which t channels the adversary controls) and he may have unbounded computing power. This problem is known as the problem of secure message transmission. Shamir sharing gives a scheme where one can tolerate up to t<n/3 channels being controlled by an adversary and where the communication is only in one direction, namely from A to B. It is easily established that this bound is tight when there is unidirectional communication from A to B. An important discovery was made by Danny Dolev, Cynthia Dwrok, Orli Waarts and Moti Yung in 1993 when they pointed out that one can tolerate up to t<n/2 channels being controlled by an adversary if one allows A and B to interact. In this talk we look at some of the recent ideas involved in solving this problem efficiently. Here efficiency is measured in the number of "rounds" of communication between A and B and in the total number of bits exchanged between A and B.