UC San Diego

Electronic voting systems, chat rooms, and electronic auctions are well-known examples of systems that involve many people interacting at the same time in order to achieve a goal: cast a vote, discuss political ideas, and bid for an item. Yet, some security goals of these multi- party protocols have not been carefully examined as they should. For example, how different is protecting the anonymity of the sender -- as in an electronic election -- versus protecting the anonymity of both the sender and the receiver -- as in a political chat room? Or, can online surveys guarantee that participants do not influence each other's answers? This dissertation studies two of these properties: anonymity and independence of inputs. We first revisit the problem of anonymous communication, in which users wish to send messages to each other without revealing their identities. We propose a novel framework to organize and compare anonymity definitions. In this framework, we present simple and practical definitions for anonymous channels in the context of computational indistinguishability. The notions capture the intuitive properties of several known types of anonymous channels, and also model practical scenarios where information is leaked in the system. We also compare these notions showing how stronger notions can be built from weaker ones in a provably optimal way. With these tools, we revisit the security of previous popular anonymous channels protocols. In applications where multiple senders can broadcast messages at the same time (like electronic auctions or elections), it is often important to enforce the simultaneous transmission of messages, so that no sender can decide its broadcast message based on the values broadcast by other players. In the second part of the dissertation, we study the definitions of independence (or Simultaneous Broadcast) proposed in the literature, obtaining a full characterization of their applicability and relative strength. In particular, we show that the latest definition, under which the most (round) efficient solution was proven secure, is strictly weaker than the previous definitions. We thus reopen the problem of either proving the efficient solution satisfies the strongest definition of security or finding an alternative efficient protocol that does so. We conclude by addressing this last problem. We present a definition of simultaneous broadcast under the Universally Composable framework, and show that this stronger notion can be achieved by a computationally efficient, constant-round construction. Our construction builds on an existent adaptive verifiable secret sharing scheme, and does not resort to generic zero-knowledge proofs or commitment schemes present in previous solutions