Ari Feldman will present his preFPO on Friday September 2 at 2PM in Room 302 (note room). The members of his committee are: Ed Felten, advisor; Mike Freedman and Andrew Appel, readers; David Walker and Brian Kernighan, nonreaders. Everyone is invited to attend his talk. His abstract follows below. -------------------------------------------------- Title: Using Untrusted Resources Securely Abstract: In a myriad of applications, users depend on devices or services provided by third parties to perform functions that they cannot carry out themselves or that third parties can do better. For example, in public elections, voters cast their votes on voting machines or paper ballots provided by election officials because they do not have the means to prepare properly formatted ballots on their own. In addition, in applications from word processing to social networking, users are increasingly adopting services in which their data resides not on their own devices, but on servers run by third parties. Users are drawn to these services because they provide levels of availability, scalability, and accessibility that average users cannot match using only their own equipment. Unfortunately, depending on third parties has typically forced users to give up control over their data. They must rely on the third parties to preserve their data’s confidentiality and integrity, and a third party that is malicious or has been subject to attack or legal pressure can compromise them. Furthermore, users typically have little more than the third parties’ promises to assure them that their data is safe. In this dissertation, we aim to improve this situation. We present protocols and systems that allow users to utilize third-party resources while providing them with a means to verify that the third parties are performing their functions correctly so that they need not trust mere promises. Our work covers three areas: cryptographic voting, cloud-based group collaboration, and social networking. Our prior work shows that widely-deployed non-cryptographic voting systems can be infected with malicious software that changes votes, potentially without detection. Vulnerabilities of this kind inspired the development of cryptographic voting systems in which the encryption of every cast ballot is made public and the encrypted ballots can be tallied in a publicly-verifiable way. Although cryptographic voting has the potential to make elections more trustworthy, it still forces voters to depend on voting machines to encrypt their ballots. Indeed, we show that a malicious voting machine can compromise the secrecy of the ballot by manipulating the ciphertext of only a handful of the ballots that are made public. We then present a protocol that significantly reduces this threat by forcing voting machines to encrypt ballots using random values chosen in advance of the election and that provides a way for anyone to verify that the right random values were used for every ballot. For applications such as word processing and calendaring, users are increasingly adopting cloud deployment because it provides benefits such as scalability, high availability, global accessibility, and real-time group collaboration. Unfortunately, moving to the cloud currently comes at the cost of trusting the cloud provider with users’ data. To overcome this tradeoff, we present SPORC, a generic framework for building a wide variety of collaborative applications with untrusted servers. In SPORC, servers only observe encrypted data and cannot deviate from correct execution without being detected. SPORC allows concurrent, low-latency editing of shared state, permits disconnected operation, and supports dynamic access control even in the presence of concurrency. Current social networking applications also require users’ to trust service providers with the plaintext of their social interactions. In response, numerous works have proposed distributing users’ data across multiple servers controlled by different parties. But, unless users bear the burden of running their own servers, they are still forced to trust third parties. Instead, we present a social networking system that allows users’ data to be hosted entirely on untrusted servers while still protecting the data’s confidentiality and integrity. Our design includes novel data structures that support efficient membership operations even for large groups and provide strong protection against server equivocation for the append-only logs that social networking applications use extensively.