Nexus Trimester - Shun Watanabe (Tokyo University of Agriculture and Technology) 3/3 | Tokyo

Information Theoretic Secrecy and Interactive Communication Shun Watanabe (Tokyo University of Agriculture and Technology) March 23, 2016 Abstract: Information theoretic secrecy refers to unconditional secrecy against a computationally unbounded adversary with any statistical procedure at his or her disposal. As is well-known, in absence of any additional resources, information theoretic secrecy is either not feasible from scratch. However, if the legitimate parties share some correlated randomness, many of the classical cryptographic primitives can be realized with information theoretic secrecy. Such correlated randomness can be accessed, for instance, from physical observations such as the fade of the wireless communication channel shared by the parties or can be purchased from trusted servers as in commodity-based cryptography. In this tutorial talk, we shall consider multiparty secret key agreement and secure multiparty (as well as two-party) computing problems, when the parties can access correlated randomness. In addition, the parties are allowed to communicate interactively over an authenticated, noiseless public channel. We will review the basic results that emerged over the last two decades in the information theory literature, which exhibit a close connection between secrecy generation and compression using interactive communication. The class of problems considered is very rich and connects to many basic problems in information theory, cryptography, and communication complexity. The list of topics to be covered include notions of secrecy, two party secret key agreement (information reconciliation and privacy amplification), multiparty secret key agreement and common randomness decomposition, two party secure computing, and multiparty secure computing with trusted parties. We shall also discuss some of our own results, namely a new upper bound for secret key length using interactive public communication and its role in characterising the minimum amount of communication needed for simulation of interactive protocols.