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

In this paper, we propose a new approach for designing distributed systems to survive Internet catastrophes called informed replication, and demonstrate this approach with the design and evaluation of a cooperative backup system called the Phoenix Recovery Service. Informed replication uses a model of correlated failures to exploit software diversity. The key observation that makes our approach both feasible and practical is that Internet catastrophes result from shared vulnerabilities. By replicating a system service on hosts that do not have the same vulnerabilities, an Internet pathogen that exploits a vulnerability is unlikely to cause all replicas to fail. To characterize software diversity in an Internet setting, we measure the software diversity of host operating systems and network services in a large organization. We then use insights from our measurement study to develop and evaluate heuristics for computing replica sets that have a number of attractive features. Our heuristics provide excellent reliability guarantees, result in low degree of replication, limit the storage burden on each host in the system, and lend themselves to a fully distributed implementation. We then present the design and prototype implementation of Phoenix, and evaluate it on the PlanetLab testbed.

Pre-2018 CSE ID: CS2005-0816