Beyond Conventional Security in Sponge-Based Authenticated Encryption Modes

P. Jovanovic; A. Luykx; B. Mennink; Y. Sasaki; K. Yasuda 

The Sponge function is known to achieve 2c/2 security, where c is its capacity. This bound was carried over to its keyed variants, such as SpongeWrap, to achieve a min{2c/2,2 kappa} security bound, with kappa the key length. Similarly, many CAESAR competition submissions were designed to comply with the classical 2c/2 security bound. We show that Sponge-based constructions for authenticated encryption can achieve the significantly higher bound of min{2b/2,2c,2 kappa}, with b>c the permutation size, by proving that the CAESAR submission NORX achieves this bound. The proof relies on rigorous computation of multi-collision probabilities, which may be of independent interest. We additionally derive a generic attack based on multi-collisions that matches the bound. We show how to apply the proof to five other Sponge-based CAESAR submissions: Ascon, CBEAM/STRIBOB, ICEPOLE, Keyak, and two out of the three PRIMATEs. A direct application of the result shows that the parameter choices of some of these submissions are overly conservative. Simple tweaks render the schemes considerably more efficient without sacrificing security. We finally consider the remaining one of the three PRIMATEs, APE, and derive a blockwise adaptive attack in the nonce-respecting setting with complexity 2c/2, therewith demonstrating that the techniques cannot be applied to APE.

MorphIT: Morphing Packet Reports for Internet Transparency

G. Fragkouli; K. Argyraki; B. A. Ford 

Can we improve Internet transparency without worsening user anonymity? For a long time, researchers have been proposing transparency systems, where traffic reports produced at strategic network points help assess network behavior and verify service-level agreements or neutrality compliance. However, such reports necessarily reveal when certain traffic appeared at a certain network point, and this information could, in principle, be used to compromise low-latency anonymity networks like Tor. In this paper, we examine whether more Internet transparency necessarily means less anonymity. We start from the information that a basic transparency solution would publish about a network and study how that would impact the anonymity of the network’s users. Then we study how to change, in real time, the time granularity of traffic reports in order to preserve both user anonymity and report utility. We evaluate with real and synthetic data and show that our algorithm can offer a good anonymity/utility balance, even in adversarial scenarios where aggregates consist of very few flows.

On the Security of Two-Round Multi-Signatures

M. Drijvers; K. Edalatnejad; B. Ford; E. Kiltz; J. Loss et al. 

A multi-signature scheme allows a group of signers to collaboratively sign a message, creating a single signature that convinces a verifier that every individual signer approved the message. The increased interest in technologies to decentralize trust has triggered the proposal of highly efficient two-round Schnorr-based multi-signature schemes designed to scale up to thousands of signers, namely BCJ by Bagherzandi et al. (CCS 2008), MWLD by Ma et al. (DCC 2010), CoSi by Syta et al. (S&P 2016), and MuSig by Maxwell et al. (ePrint 2018). In this work, we point out serious security issues in all currently known two-round multi-signature schemes (without pairings). First, we prove that none of the schemes can be proved secure without radically departing from currently known techniques. Namely, we show that if the one-more discrete-logarithm problem is hard, then no algebraic reduction exists that proves any of these schemes secure under the discrete-logarithm or one-more discrete-logarithm problem. We point out subtle flaws in the published security proofs of the above schemes (except CoSi, which was not proved secure) to clarify the contradiction between our result and the existing proofs. Next, we describe practical sub exponential attacks on all schemes, providing further evidence to their insecurity. Being left without two-round multi-signature schemes, we present rnBCJ, a variant of the BCJ scheme that we prove secure under the discrete-logarithm assumption in the random-oracle model. Our experiments show that rni3CJ barely affects scalability compared to CoSi, allowing 16384 signers to collaboratively sign a message in about 2 seconds, making it a highly practical and provably secure alternative for large-scale deploy tents.

Methods and systems for secure data exchange

B. Ford; L. Gasser; E. Kokoris Kogias; P. Janovic 

The present invention concerns a computer-implemented method for secure data exchange between a sender (A) and a recipient (B), wherein the method is performed by the sender (A) and comprises encrypting data using a symmetric key k, creating a write transaction T W , wherein the write transaction T W comprises information usable to derive the symmetric key k and an access policy identifying the recipient (B) as being allowed to decrypt the encrypted data, providing the recipient (B) access to the encrypted data, and sending the write transaction T W to a first group of servers (AC) for being stored in a blockchain data structure maintained by the first group of servers (AC).

Reducing Metadata Leakage from Encrypted Files and Communication with PURBs

K. Nikitin; L. Barman; W. Lueks; M. J. Underwood; J-P. Hubaux 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 Padded Uniform Random Blobs or PURBs: ciphertexts indistinguishable from random bit strings to anyone without a decryption key. A PURB’s content leaks 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 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.

Rethinking General-Purpose Decentralized Computing

E. C. Alp; E. Kokoris-Kogias; G. Fragkouli; B. Ford 

While showing great promise, smart contracts are difficult to program correctly, as they need a deep understanding of cryptography and distributed algorithms, and offer limited functionality, as they have to be deterministic and cannot operate on secret data. In this paper we present Protean, a general-purpose decentralized computing platform that addresses these limitations by moving from a monolithic execution model, where all participating nodes store all the state and execute every computation, to a modular execution-model. Protean employs secure specialized modules, called functional units, for building decentralized applications that are currently insecure or impossible to implement with smart contracts. Each functional unit is a distributed system that provides a special-purpose functionality by exposing atomic transactions to the smart-contract developer. Combining these transactions into arbitrarily-defined workflows, developers can build a larger class of decentralized applications, such as provably-secure and fair lotteries or e-voting.

Channels: Horizontal Scaling and Confidentiality on Permissioned Blockchains with Application on Hyperledger Fabric

E. Androulaki; C. Cachin; A. De Caro; E. Kokoris Kogias 

OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding

E. Kokoris Kogias; P. S. Jovanovic; L. Gasser; N. Gailly; E. Syta et al. 

Designing a secure permissionless distributed ledger (blockchain) that performs on par with centralized payment processors, such as Visa, is a challenging task. Most existing distributed ledgers are unable to scale-out, i.e., to grow their total processing capacity with the number of validators; and those that do, compromise security or decentralization. We present OmniLedger, a novel scale-out distributed ledger that preserves longterm security under permissionless operation. It ensures security and correctness by using a bias-resistant public-randomness protocol for choosing large, statistically representative shards that process transactions, and by introducing an efficient crossshard commit protocol that atomically handles transactions affecting multiple shards. OmniLedger also optimizes performance via parallel intra-shard transaction processing, ledger pruning via collectively-signed state blocks, and low-latency “trust-butverify” validation for low-value transactions. An evaluation of our experimental prototype shows that OmniLedger’s throughput scales linearly in the number of active validators, supporting Visa-level workloads and beyond, while confirming typical transactions in under two seconds.

System and method for providing a collective decentralized authority for sharing sensitive data

B. Ford; J-P. Hubaux; P. Egger; J-L. Raisaro; Z. Huang 

A method of sharing private and/or sensitive data from plurality of data providers to a data user, the data user having a private key and a public key, the method comprising the steps of providing a first data set and encrypting the first data set at a terminal of a first data provider with a collective public key, providing a second data set and encrypting the second data set at a terminal of a second data provider with the collective public key, sending the encrypted data to a server from the plurality of servers, the plurality of servers forming together a collective and decentralized authority, decentralized aggregating the encrypted data of the first and second data providers by the plurality of servers, based on the homomorphic encryption scheme, to compute a first encrypted aggregated data set, modifying the encryption of the first encrypted aggregated data set from the encryption based on the collective public key to an encryption based on the public key of the data user to generate a second encrypted aggregated data set.

Systems and method for anonymous, low-latencey, tracking-resistant communications in a networked environment

B. Ford; L. Barman; J-P. Hubaux; I. Dacosta; J. Feigenbaum 

Exemplary embodiments of the present disclosure provide cryptographically-strong tracking protection with unnoticeable “single-hop” network latencies by leveraging a client-relay- server architecture, in which the clients, relays (trusted or untrusted), and trustee devices are configured to implement a distributed anonymity protocol where the anonymization function adds little to no latency to the network.

Cryptographically verifiable data structure having multi-hop forward and backwards links and associated systems and methods

B. Ford; L. Gasser; E. K. Kogias; P. Jovanovic 

Data storage and retrieval systems, methods, and computer-readable media utilize a cryptographically verifiable data structure that facilitates verification of a transaction in a decentralized peer-to-peer environment using multi-hop backwards and forwards links. Backward links are cryptographic hashes of past records. Forward links are cryptographic signatures of future records that are added retroactively to records once the target block has been appended to the data structure.

A Blockchain Consensus Protocol With Horizontal Scalability

K. Cong; Z. Ren; J. Pouwelse 

Blockchain technology has the potential to decentralise many traditionally centralised systems. However, scalability remains a key challenge. A horizontally scalable solution, where performance increases by adding more nodes, would move blockchain systems one step closer to ubiquitous use. We design a novel blockchain system called CHECO. Each node in our system maintains a personal hash chain, which only stores transactions that the node is involved in. A consensus is reached on special blocks called checkpoint blocks rather than on all transactions. Checkpoint blocks are effectively a hash pointer to the personal hash chains; thus a single checkpoint block may represent an arbitrarily large set of transactions. We introduce a validation protocol so that any node can check the validity of any transaction. Since transaction and validation protocols are point-to-point, we achieve horizontal scalability. We analytically evaluate our system and show a number of highly desirable correctness properties such as consensus on the validity of transactions. Further, we give a free and open-source implementation of CHECO and evaluate it experimentally. Our results show a strong indication of horizontal scalability.

Collaborative Filtering Under a Sybil Attack: Similarity Metrics do Matter!

A. Boutet; F. De Moor; D. Frey; R. Guerraoui; A-M. Kermarrec et al. 

Recommendation systems help users identify interesting content, but they also open new privacy threats. In this paper, we deeply analyze the effect of a Sybil attack that tries to infer information on users from a user-based collaborative-filtering recommendation systems. We discuss the impact of different similarity metrics used to identity users with similar tastes in the trade-off between recommendation quality and privacy. Finally, we propose and evaluate a novel similarity metric that combines the best of both worlds: a high recommendation quality with a low prediction accuracy for the attacker. Our results, on a state-of-the-art recommendation framework and on real datasets show that existing similarity metrics exhibit a wide range of behaviors in the presence of Sybil attacks, while our new similarity metric consistently achieves the best trade-off while outperforming state-of-the-art solutions.

A Scale-out Blockchain for Value Transfer with Spontaneous Sharding

Z. Ren; K. Cong; T. V. Aerts; B. A. P. de Jonge; A. F. Morais et al. 

In this paper, we show that the complete set of transactions is not a necessity for the prevention of double-spending if the properties of value transfers is fully explored. In other words, we show that a value-transfer ledger like Bitcoin has the potential to scale-out by its nature without sacrificing security or decentralization. Firstly, we give a formal definition for the value-transfer ledger and its distinct features from a generic database. Then, we introduce the blockchain structure with a shared main chain for consensus and an individual chain for each node for recording transactions. A locally executable validation scheme is proposed with uncompromising validity and consistency. A beneficial consequence of our design is that nodes will spontaneously try to reduce their transmission cost by only providing the transactions needed to show that their transactions are not double spend. As a result, the network is sharded as each node only acquires part of the transaction record and a scale-out throughput could be achieved, which we call “spontaneous sharding”.

Channels: Horizontal Scaling and Confidentiality on Permissioned Blockchains

E. Androulaki; C. Cachin; A. De Caro; E. Kokoris-Kogias 

Sharding, or partitioning the system’s state so that different subsets of participants handle it, is a proven approach to building distributed systems whose total capacity scales horizontally with the number of participants. Many distributed ledgers have adopted this approach to increase their performance, however, they focus on the permissionless setting that assumes the existence of a strong adversary. In this paper, we deploy channels for permissioned blockchains. Our first contribution is to adapt sharding on asset-management applications for the permissioned setting, while preserving liveness and safety even on transactions spanning across-channels. Our second contribution is to leverage channels as a confidentiality boundary, enabling different organizations and consortia to preserve their privacy within their channels and still be part of a bigger collaborative ecosystem. To make our system concrete we map it on top of Hyperledger Fabric.

OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding

E. Kokoris-Kogias; P. Jovanovic; L. Gasser; N. Gailly; E. Syta et al. 

Scalable Bias-Resistant Distributed Randomness

E. Syta; P. S. Jovanovic; E. Kokoris Kogias; N. Gailly; L. Gasser et al. 

Bias-resistant public randomness is a critical component in many (distributed) protocols. Existing solutions do not scale to hundreds or thousands of participants, as is needed in many decentralized systems. We propose two large-scale distributed protocols, RandHound and RandHerd, which provide publicly-verifiable, unpredictable, and unbiasable randomness against Byzantine adversaries. RandHound relies on an untrusted client to divide a set of randomness servers into groups for scalability, and it depends on the pigeonhole principle to ensure output integrity, even for non-random, adversarial group choices. RandHerd implements an efficient, decentralized randomness beacon. RandHerd is structurally similar to a BFT protocol, but uses RandHound in a one-time setup to arrange participants into verifiably unbiased random secret-sharing groups, which then repeatedly produce random output at predefined intervals. Our prototype demonstrates that RandHound and RandHerd achieve good performance across hundreds of participants while retaining a low failure probability by properly selecting protocol parameters, such as a group size and secret-sharing threshold. For example, when sharding 512 nodes into groups of 32, our experiments show that RandHound can produce fresh random output after 240 seconds. RandHerd, after a setup phase of 260 seconds, is able to generate fresh random output in intervals of approximately 6 seconds. For this configuration, both protocols operate at a failure probability of at most 0.08% against a Byzantine adversary.

CHAINIAC: Proactive Software-Update Transparency via Collectively Signed Skipchains and Verified Builds

K. Nikitin; E. Kokoris Kogias; P. S. Jovanovic; L. Gasser; N. Gailly et al. 

Software-update mechanisms are critical to the security of modern systems, but their typically centralized design presents a lucrative and frequently attacked target. In this work, we propose CHAINIAC, a decentralized software-update framework that eliminates single points of failure, enforces transparency, and provides efficient verifiability of integrity and authenticity for software-release processes. Independent witness servers collectively verify conformance of software updates to release policies, build verifiers validate the source-to-binary correspondence, and a tamper-proof release log stores collectively signed updates, thus ensuring that no release is accepted by clients before being widely disclosed and validated. The release log embodies a skipchain, a novel data structure, enabling arbitrarily out-of-date clients to efficiently validate updates and signing keys. Evaluation of our CHAINIAC prototype on reproducible Debian packages shows that the automated update process takes the average of 5 minutes per release for individual packages, and only 20 seconds for the aggregate timeline. We further evaluate the framework using real-world data from the PyPI package repository and show that it offers clients security comparable to verifying every single update themselves while consuming only one-fifth of the bandwidth and having a minimal computational overhead.

Axiom: DTLS-Based Secure IoT Group Communication

M. Tiloca; K. Nikitin; S. Raza 

This article presents Axiom, a DTLS-based approach to efficiently secure multicast group communication among IoT-constrained devices. Axiom provides an adaptation of the DTLS record layer, relies on key material commonly shared among the group members, and does not require one to perform any DTLS handshake. We made a proof-of-concept implementation of Axiom based on the tinyDTLS library for the Contiki OS and used it to experimentally evaluate performance of our approach on real IoT hardware. Results show that Axiom is affordable on resource-constrained platforms and performs significantly better than related alternative approaches.

The Honey Badger of BFT Protocols

A. MIller; Y. Xia; K. Croman; E. Shi; D. Song 

Keeping Authorities “Honest or Bust” with Decentralized Witness Cosigning

E. Syta; I. Tamas; D. Visher; D. Wolinsky; P. S. Jovanovic et al. 

Abstract—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-inthe-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.

Seeking Anonymity in an Internet Panopticon

J. Feigenbaum; B. Ford 

Internet, users often need to assume, by default, that their every statement or action online is monitored and tracked. The Dissent project at Yale University takes a collective approach to online anonymity, based on different algorithmic foundations from onion routing, offering concrete advantages, as well as some disadvantages. Dissent preserves maximum security provided only that not all of a group’s servers maliciously collude against their clients. In an honest- security model in which we assume each shuffler correctly follows the protocol the output from the last shuffler offers provable anonymity among all non-colluding clients, provided at least one of the shufflers keeps its random permutation secret. A substantial body of work addresses these vulnerabilities to such active attacks. Dissent addresses the jamming problem by implementing accountability mechanisms, allowing the group to revoke the anonymity of any peer found to be attempting to jam communication maliciously while preserving strong anonymity protection for peers who follow the rules. Dissent now adopts a client/multi-server model with trust split across multiple servers, preferably administered independently. More important in practice, Dissent’s client/multi-server coin-sharing design addresses network churn by making the composition of client ciphertexts independent of the set of other clients online in a given round.

Security Analysis of Accountable Anonymity in Dissent

E. Syta; A. Johnson; H. Corrigan-Gibbs; S-C. Weng; D. Wolinsky et al. 

Users often wish to communicate anonymously on the Internet, for example in group discussion or instant messaging forums. Existing solutions are vulnerable to misbehaving users, however, who may abuse their anonymity to disrupt communication. Dining Cryptographers Networks (DC-nets) leave groups vulnerable to denial-of-service and Sybil attacks, mix networks are difficult to protect against traffic analysis, and accountable voting schemes are unsuited to general anonymous messaging. DISSENT is the first general protocol offering provable anonymity and accountability for moderate-size groups, while efficiently handling unbalanced communication demands among users. We present an improved and hardened DISSENT protocol, define its precise security properties, and offer rigorous proofs of these properties. The improved protocol systematically addresses the delicate balance between provably hiding the identities of well-behaved users, while provably revealing the identities of disruptive users, a challenging task because many forms of misbehavior are inherently undetectable. The new protocol also addresses several non-trivial attacks on the original DISSENT protocol stemming from subtle design flaws.

Heading Off Correlated Failures through Independence-as-a-Service

E. Zhai; R. Chen; D. I. Wolinsky; B. Ford 

Today’s systems pervasively rely on redundancy to ensure reliability. In complex multi-layered hardware/software stacks, however – especially in the clouds where many independent businesses deploy interacting services on common infrastructure – seemingly independent systems may share deep, hidden dependencies, undermining redundancy efforts and introducing unanticipated correlated failures. Complementing existing post-failure forensics, we propose Independence-as-a-Service (or INDaaS), an architecture to audit the independence of redundant systems proactively, thus avoiding correlated failures. INDaaS first utilizes pluggable dependency acquisition modules to collect the structural dependency information (including network, hardware, and software dependencies) from a variety of sources. With this information, INDaaS then quantifies the independence of systems of interest using pluggable auditing modules, offering various performance, precision, and data secrecy tradeoffs. While the most general and efficient auditing modules assume the auditor is able to obtain all required information, INDaaS can employ private set intersection cardinality protocols to quantify the independence even across businesses unwilling to share their full structural information with anyone. We evaluate the practicality of INDaaS with three case studies via auditing realistic network, hardware, and software dependency structures.

Hang With Your Buddies to Resist Intersection Attacks

D. I. Wolinsky; E. Syta; B. Ford 

Some anonymity schemes, such as DC-nets and MIX cascades, can guarantee anonymity even against traffic analysis – provided messages are independent and unlinkable. Users in practice often desire 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 attempt to offer intersection attack resistant pseudonyms in practical anonymity systems. Buddies groups users dynamically into buddy sets, controlling message transmission to make buddies within a set behaviorally indistinguishable to a traffic-monitoring adversary. Intersection attack resistance does not come “for free,” of course, and Buddies offers users control over the inevitable tradeoffs between anonymity, latency, and the useful lifetime of a 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.

Proactively Accountable Anonymous Messaging in Verdict

H. Corrigan-Gibbs; D. I. Wolinsky; B. Ford 

Among anonymity systems, DC-nets have long held attraction for their resistance to traffic analysis attacks, but practical implementations remain vulnerable to internal disruption or “jamming” attacks, which require time-consuming detection procedures to resolve. 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 use zero-knowledge proofs of knowledge to 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 incur higher computational overheads due to the public-key cryptography involved, our experiments suggest that 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 misbehavior, speeding up previous detections schemes by two orders of magnitude.

GPUfs: Integrating a File System with GPUs

M. Silberstein; B. Ford; I. Keidar; E. Witchel 

As GPU hardware becomes increasingly general-purpose, it is quickly outgrowing the traditional, constrained GPU-as-coprocessor programming model. To make GPUs easier to program and improve their integration with operating systems, we propose making the host’s file system directly accessible to GPU code. GPUfs provides a POSIX-like API for GPU programs, exploits GPU parallelism for efficiency, and optimizes GPU file access by extending the host CPU’s buffer cache into GPU memory. Our experiments, based on a set of real benchmarks adapted to use our file system, demonstrate the feasibility and benefits of the GPUfs approach. For example, a self-contained GPU program that searches for a set of strings throughout the Linux kernel source tree runs over seven times faster than on an eight-core CPU.

Dissent in Numbers: Making Strong Anonymity Scale

D. I. Wolinsky; H. Corrigan-Gibbs; B. Ford 

Current anonymous communication systems make a trade-off between weak anonymity among many nodes, via onion routing, and strong anonymity among few nodes, via DC-nets. We develop novel techniques in Dissent, a practical group anonymity system, to increase by over two orders of magnitude the scalability of strong, traffic analysis resistant approaches. Dissent derives its scalability from a client/server architecture, in which many unreliable clients depend on a smaller and more robust, but administratively decentralized, set of servers. Clients trust only that at least one server in the set is honest, but need not know or choose which server to trust. Unlike the quadratic costs of prior peer-to-peer DC-nets schemes, Dissent’s client/server design makes communication and processing costs linear in the number of clients, and hence in anonymity set size. Further, Dissent’s servers can unilaterally ensure progress, even if clients respond slowly or disconnect at arbitrary times, ensuring robustness against client churn, tail latencies, and DoS attacks. On DeterLab, Dissent scales to 5,000 online participants with latencies as low as 600 milliseconds for 600-client groups. An anonymous Web browsing application also shows that Dissent’s performance suffices for interactive communication within smaller local-area groups.

Efficient System-Enforced Deterministic Parallelism

A. Aviram; S-C. Weng; S. Hu; B. Ford 

Deterministic execution offers many benefits for debugging, fault tolerance, and security. Current methods of executing parallel programs deterministically, however, often incur high costs, allow misbehaved software to defeat repeatability, and transform time-dependent races into input- or path-dependent races without eliminating them. We introduce a new parallel programming model addressing these issues, and use Determinator, a proof-of-concept OS, to demonstrate the model’s practicality. Determinator’s microkernel API provides only “shared-nothing” address spaces and deterministic interprocess communication primitives to make execution of all unprivileged code—well-behaved or not—precisely repeatable. Atop this microkernel, Determinator’s user-level runtime adapts optimistic replication techniques to offer a private workspace model for both thread-level and process-level parallel programing. This model avoids the introduction of read/write data races, and converts write/write races into reliably-detected conflicts. Coarse-grained parallel benchmarks perform and scale comparably to nondeterministic systems, on both multicore PCs and across nodes in a distributed cluster.

Dissent: Accountable Group Anonymity

H. Corrigan-Gibbs; B. Ford 

Users often wish to participate in online groups anonymously, but misbehaving users may abuse this anonymity to disrupt the group. Messaging protocols such as Mix-nets and DC-nets leave online groups vulnerable to denial-of-service and Sybil attacks, while accountable voting protocols are unusable or inefficient for general anonymous messaging. We present the first general messaging protocol that offers provable anonymity with accountability for moderate-size groups, and efficiently handles unbalanced loads where few members have much data to transmit in a given round. The N group members first cooperatively shuffle an N x N matrix of pseudorandom seeds, then use these seeds in N “pre-planned” DC-nets protocol runs. Each DC-nets run transmits the variable-length bulk data comprising one member’s message, using the minimum number of bits required for anonymity under our attack model. The protocol preserves message integrity and one-to-one correspondence between members and messages, makes denial-of-service attacks by members traceable to the culprit, and efficiently handles large and unbalanced message loads. A working prototype demonstrates the protocol’s practicality for anonymous messaging in groups of 40+ member nodes.

Delegative Democracy

B. A. Ford 

Delegative democracy is a new paradigm for democratic organization which emphasizes individually chosen vote transfers (“delegation”) over mass election. Delegative democracy combines the best elements of direct and representative democracy by replacing artificially imposed representation structures with an adaptive structure founded on real personal and group trust relationships. Delegative democracy empowers individuals and encourages widespread direct participation in a democratic organization, without unduly burdening or disenfranchising those members who, for lack of time, interest, or knowledge, would prefer to take a more passive role.