In this paper, we develop methods for constructing vote-buying/coercion attacks on end-to-end voting systems, and describe vote-buying/coercion attacks on three proposed end-to-end voting systems: Punchscan, Prêt-à-voter and ThreeBallot. We also demonstrate a different attack on Punchscan, which could permit corrupt election officials to change votes without detection in some cases. Additionally, we consider some generic attacks on end-to-end voting systems.
[pdf]For secure two-party and multi-party computation with abort, classification of which primitives are complete has been extensively studied in the literature. However, for fair secure computation, where (roughly speaking) either all parties learn the output or none do, the question of complete primitives has remained largely unstudied.
In this work, we initiate a rigorous study of completeness for primitives that allow fair computation. We show the following results:
A key way in which banks mitigate the effects of phishing is to remove fraudulent websites or suspend abusive domain names. This `take-down' is often subcontracted to specialist firms. Prior work has shown that these take-down companies refuse to share `feeds' of phishing website URLs with each other, and consequently, many phishing websites are not removed because the firm with the take-down contract remains unaware of their existence. The take-down companies are reticent to exchange feeds, fearing that competitors with less comprehensive lists might `free-ride' off their efforts by not investing resources to find new websites, as well as use the feeds to poach clients. In this paper, we propose the Phish Market protocol, which enables companies with less comprehensive feeds to learn about websites impersonating their own clients that are held by other firms. The protocol is designed so that the contributing firm is compensated only for those websites affecting its competitor's clients and only those previously unknown to the receiving firm. Crucially, the protocol does not reveal to the contributing firm which URLs are needed by the receiver, as this is viewed as sensitive information by take-down firms. Using complete lists of phishing URLs obtained from two large take-down companies, our elliptic-curve-based implementation added a negligible average 5 second delay to securely share URLs.
[pdf]There are many advantages to voting schemes in which voters rank all candidates in order, rather than just choosing their favourite. However, these schemes inherently suffer from a coercion problem when there are many candidates, because a coercer can demand a certain permutation from a voter and then check whether that permutation appears during tallying. Recently developed cryptographic voting protocols allow anyone to audit an election (universal verifiability), but existing systems are either not applicable to ranked voting at all, or reveal enough information about the ballots to make voter coercion possible.
We solve this problem for the popular single transferable vote (STV) ranked voting system, by constructing an algorithm for the verifiable tallying of encrypted votes. Our construction improves upon existing work because it extends to multiple-seat STV and reveals less information than other schemes. The protocol is based on verifiable shuffling of homomorphic encryptions, a well-studied primitive in the voting arena. Our protocol is efficient enough to be practical, even for a large election.
[pdf]We address one of the foundational problems in cryptography: the bias of coin-flipping protocols. Coin-flipping protocols allow mutually distrustful parties to generate a common unbiased random bit, guaranteeing that even if one of the parties is malicious, it cannot significantly bias the output of the honest party. A classical result by Cleve [STOC '86] showed that for any two-party $r$-round coin-flipping protocol there exists an efficient adversary that can bias the output of the honest party by $\Omega(1/r)$. However, the best previously known protocol only guarantees $O(1/\sqrt{r})$ bias, and the question of whether Cleve's bound is tight has remained open for more than twenty years.
In this paper we establish the optimal trade-off between the round complexity and the bias of two-party coin-flipping protocols. Under standard assumptions (the existence of oblivious transfer), we show that Cleve's lower bound is tight: we construct an $r$-round protocol with bias $O(1/r)$.
[pdf]Designing secure protocols in the Universal Composability (UC) framework confers many advantages. In particular, it allows the protocols to be securely used as building blocks in more complex protocols, and assists in understanding their security properties. Unfortunately, most existing models in which universally composable computation is possible (for useful functionalities) require a trusted setup stage. Recently, Katz [Eurocrypt '07] proposed an alternative to the trusted setup assumption: tamper-proof hardware. Instead of trusting a third party to correctly generate the setup information, each party can create its own hardware tokens, which it sends to the other parties. Each party is only required to trust that its own tokens are tamper-proof.
Katz designed a UC commitment protocol that requires both parties to generate hardware tokens. In addition, his protocol relies on a specific number-theoretic assumption. In this paper, we construct UC commitment protocols for “David” and “Goliath”: we only require a single party (Goliath) to be capable of generating tokens. We construct a version of the protocol that is secure for computationally unbounded parties, and a more efficient version that makes computational assumptions only about David (we require only the existence of a one-way function). Our protocols are simple enough to be performed by hand on David's side.
These properties may allow such protocols to be used in situations which are inherently asymmetric in real-life, especially those involving individuals versus large organizations. Classic examples include voting protocols (voters versus “the government”) and protocols involving private medical data (patients versus insurance-agencies or hospitals).
[pdf]In this paper we propose a new voting protocol with desirable security properties. The voting stage of the protocol can be performed by humans without computers; it provides every voter with the means to verify that all the votes were counted correctly (universal verifiability) while preserving ballot secrecy. The protocol has “everlasting privacy”: even a computationally unbounded adversary gains no information about specific votes from observing the protocol's output. Unlike previous protocols with these properties, this protocol distributes trust between two authorities: a single corrupt authority will not cause voter privacy to be breached. Finally, the protocol is receipt-free: a voter cannot prove how she voted even she wants to do so. We formally prove the security of the protocol in the Universal Composability framework, based on number-theoretic assumptions.
[pdf]Motivated by the challenging task of designing “secure” vote storage mechanisms, we deal with information storage mechanisms that operate in extremely hostile environments. In such environments, the majority of existing techniques for information storage and for security are susceptible to powerful adversarial attacks. In this setting, we propose a mechanism for storing a set of at most K elements from a large universe of size N on write-once memories in a manner that does not reveal the insertion order of the elements. We consider a standard model for write-once memories, in which the memory is initialized to the all 0's state, and the only operation allowed is flipping bits from 0 to 1. Whereas previously known constructions were either inefficient (required $\Theta(K^2)$ memory), randomized, or employed cryptographic techniques which are unlikely to be available in hostile environments, we eliminate each of these undesirable properties. The total amount of memory used by the mechanism is linear in the number of stored elements and poly-logarithmic in the size of the universe of elements.
In addition, we consider one of the classical distributed computing problems: conflict resolution in multiple-access channels. By establishing a tight connection with the basic building block of our mechanism, we construct the first deterministic and non-adaptive conflict resolution algorithm whose running time is optimal up to poly-logarithmic factors.
[pdf]We present the first universally verifiable voting scheme that can be based on a general assumption (existence of a non-interactive commitment scheme). Our scheme is also the first receipt-free scheme to give “everlasting privacy” for votes: even a computationally unbounded party does not gain any information about individual votes (other than what can be inferred from the final tally).
Our voting protocols are designed to be used in a “traditional” setting, in which voters cast their ballots in a private polling booth (which we model as an untappable channel between the voter and the tallying authority). Following in the footsteps of Chaum and Neff, our protocol ensures that the integrity of an election cannot be compromised even if the computers running it are all corrupt (although ballot secrecy may be violated in this case).
We give a generic voting protocol which we prove to be secure in the Universal Composability model, given that the underlying commitment is universally composable. We also propose a concrete implementation, based on the hardness of discrete log, that is more efficient.
[pdf]We propose simple, realistic protocols for polling that allow the responder to plausibly repudiate his response, while at the same time allow accurate statistical analysis of poll results. The protocols use simple physical objects (envelopes or scratch-off cards) and can be performed without the aid of computers.
One of the main innovations of this work is the use of techniques from theoretical cryptography to rigorously prove the security of a realistic, physical protocol. We show that, given a few properties of physical envelopes, the protocols are unconditionally secure in the universal composability framework.
[pdf]In this paper we attempt to formally study two very intuitive physical models: sealed envelopes and locked boxes, often used as illustrations for common cryptographic operations. We relax the security properties usually required from locked boxes (such as in bit-commitment protocols) and require only that a broken lock or torn envelope be identifiable to the original sender. Unlike the completely impregnable locked box, this functionality may be achievable in real life, where containers having this property are called “tamper-evident seals”. Another physical object with this property is the “scratch-off card”, often used in lottery tickets.
We consider three variations of tamper-evident seals, and show that under some conditions they can be used to implement oblivious transfer, bit-commitment and coin flipping. We also show a separation between the three models. Of particular interest, we give a strongly-fair coin flipping protocol with bias bounded by $O(1/r)$ (where r is the number of rounds), beating the best known bias in the standard model even with cryptographic assumptions.
[pdf]A timestamping scheme is a mechanism allowing one party, the “stamper”, to prove that it knew of a certain document at some earlier time. We say that such a scheme is passive if a stamper can stamp a document without communicating with any other player. The only communication performed is at validation time. Passive timestamping has many advantages, such as information theoretic privacy and enhanced robustness. Passive timestamping, however, is not possible against polynomial time adversaries that have unbounded (but polynomial) storage at their disposal. As a result, no passive timestamping schemes were constructed up to date.
We show that passive timestamping is possible in the Bounded Storage Model. I.e., where there is an upper bound on the amount of storage that the adversary has and all players have access to a long random string. To the best of our knowledge, this is the first example of a cryptographic task that is possible in the bounded storage model, but is impossible in the “standard cryptographic setting”, even assuming cryptographic assumptions.
We give an explicit construction that is secure against all bounded storage adversaries, and a significantly more efficient construction secure against all bounded storage adversaries that run in polynomial time.
[pdf]