Abstract

The Russian Cards Problem has been extensively studied as an example of a problem of an unconditionally secure protocol where the sender and receiver are able to transmit secret information safely over a public non-secure channel without the secret being learned by a third party with access to the channel. Epistemic logic in general and public announcement logic in particular have been very useful in this study, as it involves careful analysis of subtle properties of nested knowledge. A long standing open problem is whether or not there exist protocols of length strictly greater than two for the original problem. In this paper we finally settle this problem, answering the question in the affirmative, by presenting a new solution to the original Russian Cards Problem that involves more than two steps. It starts with an initial announcement with so-called crossing hands, after which it is not common knowledge that the protocol can terminate in one more step.