Steganography and Collusion in Cryptographic Protocols

Steganography, the hiding of covert messages inside innocuous communication, is an ac-tive area of cryptographic research. Recent research has shown that provably undetectable steganography is possible in a wide variety of settings. We believe that the existence of such undetectable steganography will have far reaching implications. In this thesis, we investi-gate the impact of steganography on the design of cryptographic protocols. In particular, we show that that all existing cryptographic protocols allow malicious players to collude and coordinate their actions by steganographicly hiding covert messages inside legitimate protocol traffic. Such collusion is devastating in many settings, and thus we argue that it's elimination is an important direction for cryptographic research. Defeating such steganographic collusion requires not only new cryptographic protocols, but also a new notion of protocol security. Traditional notions of protocol security attempt to minimize the injuries to privacy and correctness inflicted by malicious participants who collude during run-time. They do not, however, prevent malicious parties from colluding and coordinating their actions in the first place! We therefore put forward the notion of