Bryan Ford

Louis-Henri Merino, Simone Colombo, Rene Reyes et al.

Online voting is convenient and flexible, but amplifies the risks of voter coercion and vote buying. One promising mitigation strategy enables voters to give a coercer fake voting credentials, which silently cast votes that do not count. Current systems along these lines make problematic assumptions about credential issuance, however, such as strong trust in a registrar and/or in voter-controlled hardware, or expecting voters to interact with multiple registrars. Votegral is the first coercion-resistant voting architecture that leverages the physical security of in-person registration to address these credential-issuance challenges, amortizing the convenience costs of in-person registration by reusing credentials across successive elections. Votegral's registration component, TRIP, gives voters a kiosk in a privacy booth with which to print real and fake credentials on paper, eliminating dependence on trusted hardware in credential issuance. The voter learns and can verify in the privacy booth which credential is real, but real and fake credentials thereafter appear indistinguishable to others. Only voters actually under coercion, a hopefully-rare case, need to trust the kiosk. To achieve verifiability, each paper credential encodes an interactive zero-knowledge proof, which is sound in real credentials but unsound in fake credentials. Voters observe the difference in the order of printing steps, but need not understand the technical details. Experimental results with our prototype suggest that Votegral is practical and sufficiently scalable for real-world elections. User-visible latency of credential issuance in TRIP is at most 19.7 seconds even on resource-constrained kiosk hardware. A companion usability study indicates that TRIP's usability is competitive with other e-voting systems, and formal proofs support TRIP's combination of coercion-resistance and verifiability.

Bryan Ford

Digital identity seems like a prerequisite for digital democracy: how can we ensure "one person, one vote" online without identifying voters? But digital identity solutions - ID checking, biometrics, self-sovereign identity, and trust networks - all present flaws, leaving users vulnerable to exclusion, identity loss or theft, and coercion. These flaws may be insurmountable because digital identity is a cart pulling the horse. We cannot achieve digital identity secure enough for the weight of digital democracy, until we build it on a solid foundation of "digital personhood." While identity is about distinguishing one person from another through attributes or affiliations, personhood is about giving all real people inalienable digital participation rights independent of identity, including protection against erosion of their democratic rights through identity loss, theft, coercion, or fakery. We explore and analyze alternative approaches to "proof of personhood" that may provide this missing foundation. Pseudonym parties marry the transparency of periodic physical-world events with the power of digital tokens between events. These tokens represent limited-term but renewable claims usable for purposes such as online voting or liquid democracy, sampled juries or deliberative polls, abuse-resistant social communication, or minting universal basic income in a permissionless cryptocurrency. Enhancing pseudonym parties to provide participants a moment of enforced physical security and privacy can address coercion and vote-buying risks that plague today's E-voting systems. We also examine other proposed approaches to proof of personhood, some of which offer conveniences such as all-online participation. These alternatives currently fall short of satisfying all the key digital personhood goals, unfortunately, but offer valuable insights into the challenges we face.

Bryan Ford

Classical monetary systems regularly subject the most vulnerable majority of the world's population to debilitating financial shocks, and have manifestly allowed uncontrolled global inequality over the long term. Given these basic failures, how can we avoid asking whether mainstream macroeconomic principles are actually compatible with democratic principles such as equality or the protection of human rights and dignity? This idea paper takes a constructive look at this question, by exploring how alternate monetary principles might result in a form of money more compatible with democratic principles -- dare we call it "democratic money"? In this alternative macroeconomic philosophy, both the supply of and the demand for money must be rooted in people, so as to give all people both equal opportunities for economic participation. Money must be designed around equality, not only across all people alive at a given moment, but also across past and future generations of people, guaranteeing that our descendants cannot be enslaved by their ancestors' economic luck or misfortune. Democratic money must reliably give all people a means to enable everyday commerce, investment, and value creation in good times and bad, and must impose hard limits on financial inequality. Democratic money must itself be governed democratically, and must economically facilitate the needs of citizens in a democracy for trustworthy and unbiased information with which to make wise collective decisions. An intriguing approach to implementing and deploying democratic money is via a cryptocurrency built on a proof-of-personhood foundation, giving each opt-in human participant one equal unit of stake. Such a cryptocurrency would have both interesting similarities to, and important differences from, a Universal Basic Income (UBI) denominated in an existing currency.

Bryan Ford, Rainer Böhme

We outline a metacircular argument explaining why it is rational to be irrational when attacking open-world decentralized systems, and why systems whose security depend on rationality assumptions are insecure.

Bryan Ford

Consensus protocols for asynchronous networks are usually complex and inefficient, leading practical systems to rely on synchronous protocols. This paper attempts to simplify asynchronous consensus by building atop a novel threshold logical clock abstraction, which enables upper layers to operate as if on a synchronous network. This approach yields an asynchronous consensus protocol for fail-stop nodes that may be simpler and more robust than Paxos and its leader-based variants, requiring no common coins and achieving consensus in a constant expected number of rounds. The same approach can be strengthened against Byzantine failures by building on well-established techniques such as tamper-evident logging and gossip, accountable state machines, threshold signatures and witness cosigning, and verifiable secret sharing. This combination of existing abstractions and threshold logical clocks yields a modular, cleanly-layered approach to building practical and efficient Byzantine consensus, distributed key generation, time, timestamping, and randomness beacons, and other critical services.

Kirill Nikitin, Ludovic Barman, Wouter Lueks et al.

Most encrypted data formats leak metadata via their plaintext headers, such as format version, encryption schemes used, number of recipients who can decrypt the data, and even the recipients' identities. This leakage can pose security and privacy risks to users, e.g., by revealing the full membership of a group of collaborators from a single encrypted e-mail, or by enabling an eavesdropper to fingerprint the precise encryption software version and configuration the sender used. We propose that future encrypted data formats improve security and privacy hygiene by producing $\textit{Padded Uniform Random Blobs}$ or PURBs: ciphertexts indistinguishable from random bit strings to anyone without a decryption key. A PURB's content leaks $\textit{nothing at all}$, even the application that created it, and is padded such that even its length leaks as little as possible. Encoding and decoding ciphertexts with $\textit{no}$ cleartext markers presents efficiency challenges, however. We present cryptographically agile encodings enabling legitimate recipients to decrypt a PURB efficiently, even when encrypted for any number of recipients' public keys and/or passwords, and when these public keys are from different cryptographic suites. PURBs employ Padmé, a~novel padding scheme that limits information leakage via ciphertexts of maximum length $M$ to a practical optimum of $O(\log \log M)$ bits, comparable to padding to a power of two, but with lower overhead of at most $12\%$ and decreasing with larger payloads.

Ludovic Barman, Italo Dacosta, Mahdi Zamani et al.

Organizational networks are vulnerable to traffic-analysis attacks that enable adversaries to infer sensitive information from the network traffic - even if encryption is used. Typical anonymous communication networks are tailored to the Internet and are poorly suited for organizational networks. We present PriFi, an anonymous communication protocol for LANs, which protects users against eavesdroppers and provides high-performance traffic-analysis resistance. PriFi builds on Dining Cryptographers networks but reduces the high communication latency of prior work via a new client/relay/server architecture, in which a client's packets remain on their usual network path without additional hops, and in which a set of remote servers assist the anonymization process without adding latency. PriFi also solves the challenge of equivocation attacks, which are not addressed by related works, by encrypting the traffic based on the communication history. Our evaluation shows that PriFi introduces a small latency overhead (~100ms for 100 clients) and is compatible with delay-sensitive applications such as VoIP.

Albert Kwon, Henry Corrigan-Gibbs, Srinivas Devadas et al.

Atom is an anonymous messaging system that protects against traffic-analysis attacks. Unlike many prior systems, each Atom server touches only a small fraction of the total messages routed through the network. As a result, the system's capacity scales near-linearly with the number of servers. At the same time, each Atom user benefits from "best possible" anonymity: a user is anonymous among all honest users of the system, against an active adversary who controls the entire network, a portion of the system's servers, and any number of malicious users. The architectural ideas behind Atom have been known in theory, but putting them into practice requires new techniques for (1) avoiding the reliance on heavy general-purpose multi-party computation protocols, (2) defeating active attacks by malicious servers at minimal performance cost, and (3) handling server failure and churn. Atom is most suitable for sending a large number of short messages, as in a microblogging application or a high-security communication bootstrapping ("dialing") for private messaging systems. We show that, on a heterogeneous network of 1,024 servers, Atom can transit a million Tweet-length messages in 28 minutes. This is over 23x faster than prior systems with similar privacy guarantees.

Aaron Segal, Joan Feigenbaum, Bryan Ford

The question of how government agencies can acquire actionable, useful information about legitimate but unknown targets without intruding upon the electronic activity of innocent parties is extremely important. We address this question by providing experimental evidence that actionable, useful information can indeed be obtained in a manner that preserves the privacy of innocent parties and that holds government agencies accountable. In particular, we present practical, privacy-preserving protocols for two operations that law-enforcement and intelligence agencies have used effectively: set intersection and contact chaining. Experiments with our protocols suggest that privacy-preserving contact chaining can perform a 3-hop privacy-preserving graph traversal producing 27,000 ciphertexts in under two minutes. These ciphertexts are usable in turn via privacy-preserving set intersection to pinpoint potential unknown targets within a body of 150,000 total ciphertexts within 10 minutes, without exposing personal information about non-targets.

Eleftherios Kokoris-Kogias, Philipp Jovanovic, Nicolas Gailly et al.

While showing great promise, Bitcoin requires users to wait tens of minutes for transactions to commit, and even then, offering only probabilistic guarantees. This paper introduces ByzCoin, a novel Byzantine consensus protocol that leverages scalable collective signing to commit Bitcoin transactions irreversibly within seconds. ByzCoin achieves Byzantine consensus while preserving Bitcoin's open membership by dynamically forming hash power-proportionate consensus groups that represent recently-successful block miners. ByzCoin employs communication trees to optimize transaction commitment and verification under normal operation while guaranteeing safety and liveness under Byzantine faults, up to a near-optimal tolerance of f faulty group members among 3f + 2 total. ByzCoin mitigates double spending and selfish mining attacks by producing collectively signed transaction blocks within one minute of transaction submission. Tree-structured communication further reduces this latency to less than 30 seconds. Due to these optimizations, ByzCoin achieves a throughput higher than PayPal currently handles, with a confirmation latency of 15-20 seconds.

Ewa Syta, Iulia Tamas, Dylan Visher et al.

The secret keys of critical network authorities - such as time, name, certificate, and software update services - represent high-value targets for hackers, criminals, and spy agencies wishing to use these keys secretly to compromise other hosts. To protect authorities and their clients proactively from undetected exploits and misuse, we introduce CoSi, a scalable witness cosigning protocol ensuring that every authoritative statement is validated and publicly logged by a diverse group of witnesses before any client will accept it. A statement S collectively signed by W witnesses assures clients that S has been seen, and not immediately found erroneous, by those W observers. Even if S is compromised in a fashion not readily detectable by the witnesses, CoSi still guarantees S's exposure to public scrutiny, forcing secrecy-minded attackers to risk that the compromise will soon be detected by one of the W witnesses. Because clients can verify collective signatures efficiently without communication, CoSi protects clients' privacy, and offers the first transparency mechanism effective against persistent man-in-the-middle attackers who control a victim's Internet access, the authority's secret key, and several witnesses' secret keys. CoSi builds on existing cryptographic multisignature methods, scaling them to support thousands of witnesses via signature aggregation over efficient communication trees. A working prototype demonstrates CoSi in the context of timestamping and logging authorities, enabling groups of over 8,000 distributed witnesses to cosign authoritative statements in under two seconds.

John Maheswaran, Daniel Jackowitz, David Isaac Wolinsky et al.

Social networking sites supporting federated identities offer a convenient and increasingly popular mechanism for cross-site authentication. Unfortunately, they also exacerbate many privacy and tracking risks. We propose Crypto-Book, an anonymizing layer enabling cross-site authentication while reducing these risks. Crypto-Book relies on a set of independently managed servers that collectively assign each social network identity a public/private keypair. Only an identity's owner learns all the private key shares, and can therefore construct the private key, while all participants can obtain any user's public key, even if the corresponding private key has yet to be retrieved. Having obtained an appropriate key set, a user can then leverage anonymous authentication techniques such as linkable ring signatures to log into third-party web sites while preserving privacy. We have implemented a prototype of Crypto-Book and demonstrate its use with three applications: a Wiki system, an anonymous group communication system, and a whistleblower submission system. Our results show that for anonymity sets of size 100, Crypto-Book login takes 0.56s for signature generation by the client, 0.38s for signature verification on the server, and requires 5.6KB of communication bandwidth.

Joan Feigenbaum, Bryan Ford

Obtaining and maintaining anonymity on the Internet is challenging. The state of the art in deployed tools, such as Tor, uses onion routing (OR) to relay encrypted connections on a detour passing through randomly chosen relays scattered around the Internet. Unfortunately, OR is known to be vulnerable at least in principle to several classes of attacks for which no solution is known or believed to be forthcoming soon. Current approaches to anonymity also appear unable to offer accurate, principled measurement of the level or quality of anonymity a user might obtain. Toward this end, we offer a high-level view of the Dissent project, the first systematic effort to build a practical anonymity system based purely on foundations that offer measurable and formally provable anonymity properties. Dissent builds on two key pre-existing primitives - verifiable shuffles and dining cryptographers - but for the first time shows how to scale such techniques to offer measurable anonymity guarantees to thousands of participants. Further, Dissent represents the first anonymity system designed from the ground up to incorporate some systematic countermeasure for each of the major classes of known vulnerabilities in existing approaches, including global traffic analysis, active attacks, and intersection attacks. Finally, because no anonymity protocol alone can address risks such as software exploits or accidental self-identification, we introduce WiNon, an experimental operating system architecture to harden the uses of anonymity tools such as Tor and Dissent against such attacks.

David Isaac Wolinsky, Bryan Ford

Despite the attempts of well-designed anonymous communication tools to protect users from tracking or identification, flaws in surrounding software (such as web browsers) and mistakes in configuration may leak the user's identity. We introduce Nymix, an anonymity-centric operating system architecture designed "top-to-bottom" to strengthen identity- and tracking-protection. Nymix's core contribution is OS support for nym-browsing: independent, parallel, and ephemeral web sessions. Each web session, or pseudonym, runs in a unique virtual machine (VM) instance evolving from a common base state with support for long-lived sessions which can be anonymously stored to the cloud, avoiding de-anonymization despite potential confiscation or theft. Nymix allows a user to safely browse the Web using various different transports simultaneously through a pluggable communication model that supports Tor, Dissent, and a private browsing mode. In evaluations, Nymix consumes 600 MB per nymbox and loads within 15 to 25 seconds.

Henry Corrigan-Gibbs, Wendy Mu, Dan Boneh et al.

The security of any cryptosystem relies on the secrecy of the system's secret keys. Yet, recent experimental work demonstrates that tens of thousands of devices on the Internet use RSA and DSA secrets drawn from a small pool of candidate values. As a result, an adversary can derive the device's secret keys without breaking the underlying cryptosystem. We introduce a new threat model, under which there is a systemic solution to such randomness flaws. In our model, when a device generates a cryptographic key, it incorporates some random values from an entropy authority into its cryptographic secrets and then proves to the authority, using zero-knowledge-proof techniques, that it performed this operation correctly. By presenting an entropy-authority-signed public-key certificate to a third party (like a certificate authority or SSH client), the device can demonstrate that its public key incorporates randomness from the authority and is therefore drawn from a large pool of candidate values. Where possible, our protocol protects against eavesdroppers, entropy authority misbehavior, and devices attempting to discredit the entropy authority. To demonstrate the practicality of our protocol, we have implemented and evaluated its performance on a commodity wireless home router. When running on a home router, our protocol incurs a 2.1x slowdown over conventional RSA key generation and it incurs a 4.4x slowdown over conventional EC-DSA key generation.

Henry Corrigan-Gibbs, Bryan Ford

We present the design and prototype implementation of ConScript, a framework for using JavaScript to allow casual Web users to participate in an anonymous communication system. When a Web user visits a cooperative Web site, the site serves a JavaScript application that instructs the browser to create and submit "dummy" messages into the anonymity system. Users who want to send non-dummy messages through the anonymity system use a browser plug-in to replace these dummy messages with real messages. Creating such conscripted anonymity sets can increase the anonymity set size available to users of remailer, e-voting, and verifiable shuffle-style anonymity systems. We outline ConScript's architecture, we address a number of potential attacks against ConScript, and we discuss the ethical issues related to deploying such a system. Our implementation results demonstrate the practicality of ConScript: a workstation running our ConScript prototype JavaScript client generates a dummy message for a mix-net in 81 milliseconds and it generates a dummy message for a DoS-resistant DC-net in 156 milliseconds.

David Isaac Wolinsky, Ewa Syta, Bryan Ford

Some anonymity schemes might in principle protect users from pervasive network surveillance - but only if all messages are independent and unlinkable. Users in practice often need pseudonymity - sending messages intentionally linkable to each other but not to the sender - but pseudonymity in dynamic networks exposes users to intersection attacks. We present Buddies, the first systematic design for intersection attack resistance in practical anonymity systems. Buddies groups users dynamically into buddy sets, controlling message transmission to make buddies within a set behaviorally indistinguishable under traffic analysis. To manage the inevitable tradeoffs between anonymity guarantees and communication responsiveness, Buddies enables users to select independent attack mitigation policies for each pseudonym. Using trace-based simulations and a working prototype, we find that Buddies can guarantee non-trivial anonymity set sizes in realistic chat/microblogging scenarios, for both short-lived and long-lived pseudonyms.

Henry Corrigan-Gibbs, David Isaac Wolinsky, Bryan Ford

The DC-nets approach to anonymity has long held attraction for its strength against traffic analysis, but practical implementations remain vulnerable to internal disruption or "jamming" attacks requiring time-consuming tracing procedures to address. We present Verdict, the first practical anonymous group communication system built using proactively verifiable DC-nets: participants use public key cryptography to construct DC-net ciphertexts, and knowledge proofs to detect and detect and exclude misbehavior before disruption. We compare three alternative constructions for verifiable DC-nets, one using bilinear maps and two based on simpler ElGamal encryption. While verifiable DC-nets incurs higher computation overheads due to the public-key cryptography involved, our experiments suggest Verdict is practical for anonymous group messaging or microblogging applications, supporting groups of 100 clients at 1 second per round or 1000 clients at 10 seconds per round. Furthermore, we show how existing symmetric-key DC-nets can "fall back" to a verifiable DC-net to quickly identify mis- behavior improving previous detections schemes by two orders of magnitude than previous approaches.

Bryan Ford

The cloud model's dependence on massive parallelism and resource sharing exacerbates the security challenge of timing side-channels. Timing Information Flow Control (TIFC) is a novel adaptation of IFC techniques that may offer a way to reason about, and ultimately control, the flow of sensitive information through systems via timing channels. With TIFC, objects such as files, messages, and processes carry not just content labels describing the ownership of the object's "bits," but also timing labels describing information contained in timing events affecting the object, such as process creation/termination or message reception. With two system design tools-deterministic execution and pacing queues-TIFC enables the construction of "timing-hardened" cloud infrastructure that permits statistical multiplexing, while aggregating and rate-limiting timing information leakage between hosted computations.

Bryan Ford

Cloud computing is appealing from management and efficiency perspectives, but brings risks both known and unknown. Well-known and hotly-debated information security risks, due to software vulnerabilities, insider attacks, and side-channels for example, may be only the "tip of the iceberg." As diverse, independently developed cloud services share ever more fluidly and aggressively multiplexed hardware resource pools, unpredictable interactions between load-balancing and other reactive mechanisms could lead to dynamic instabilities or "meltdowns." Non-transparent layering structures, where alternative cloud services may appear independent but share deep, hidden resource dependencies, may create unexpected and potentially catastrophic failure correlations, reminiscent of financial industry crashes. Finally, cloud computing exacerbates already-difficult digital preservation challenges, because only the provider of a cloud-based application or service can archive a "live," functional copy of a cloud artifact and its data for long-term cultural preservation. This paper explores these largely unrecognized risks, making the case that we should study them before our socioeconomic fabric becomes inextricably dependent on a convenient but potentially unstable computing model.