The following question is extremely broad and speculative, for which I apologize, but it strikes me as exceedingly important, so I will ask it nonetheless.

Suppose an event of global significance took place, like the detection of an Earth-threatening asteroid or an alien invasion, and humanity were to need to decide collectively how to respond to it. Suppose further -- as is quite likely -- that (a) some individual nation states (US, UK, RU, CN etc) would attempt to control the global response, but (b) citizens of other states would be skeptical of whether the "leader" states' proposals were in their own best interest. In such circumstances, existing political arrangements like the United Nations probably might not suffice to achieve a mechanism for arriving at a true "consensus" that would be (approximately) universally recognised as such. Is there a plausible cryptographic mechanism for conducting a global referendum that would be (approximately) universally recognised as legitimate?

Some of the issues that I am trying to get at:

  • What sort of cryptographic guarantee, if satisfied to a reasonable degree of certainty, would ensure "legitimacy"? A presumably-unattainable example illustrates what I mean: if a cryptographic protocol could ensure adherence to the principle of "one person one vote", while simultaneously permitting a sufficiently large fraction of the human population to vote, I would venture to guess that the outcome of the election would enjoy a certain degree of "universal" legitimacy.

  • Although a layman in cryptography, I'm still well aware that when I interact on the internet I "leak" some information that would suffice to identify me uniquely to a high degree of certainty. (My persistent logins, browser cookies, ...) What fraction of the human population could be identified uniquely, with what degree of certainty, using a cryptographic protocol that could ensure anyone can vote once and only once?

  • Can and should ordinary, run-of-the-mill elections like those held in the United States for selecting our President, be conducted online? If not, why not? In terms of provable (albeit probabilistic) guarantees about how electoral outcomes compare to the preferences of the electorate, are there any valid reasons to prefer paper ballots to electronic ones? If so, what infrastructure changes could be adopted that would allow us to leverage the efficiencies of online voting? Do we need an international public key infrastructure with private key issuance tied to state identities? Something else?


Regarding the 3rd part of your question, "Can and should ordinary, run of the mill elections be conducted online ..." - If one thinks of an election as a problem around the issue of preserving the privacy of many inputs (a people or population's votes) while correctly producing the right result (i.e. correctly tabulating the outcome of the election) and moreover, if you would like to do this without relying on a trusted central authority (like the election commission) - there are some central results in cryptography that prove the possibility of such a thing under different adversarial assumptions, starting with the landmark paper of Goldreich, Micali and Wigderson entitled "How to Play Any Mental Game - A Completeness Theorem for Protocols with Honest Majority" - this result falls under the general moniker of "Multi Party Computation" (MPC), and represents a provably positive result for MPC with honest majorities. Since this paper, MPC has evolved quite a bit and has been promoted, among other things, as a means for secure voting - the more recent SPDZ protocol of Damgard, Pastro, Smart and Zakarias is secure against "active static adversaries" and is able to tolerate corruption of up to n − 1 of the n parties involved in the computation. In terms of successful applications, the following outlines one of the first applications of MPC techniques (the Danish sugar beet auction) "https://www.cs.purdue.edu/homes/aliaga/cs197-10/papers/bogetoft.pdf"

  • $\begingroup$ Thanks! This is exactly the sort of answer I was hoping for -- providing references to literature on collective decisionmaking in the presence of adversaries. $\endgroup$ – Sam Lichtenstein Apr 19 '16 at 1:25
  • $\begingroup$ Since you seem to know something about multiparty computation, I'll ask the obvious follow-up question: what should we make, in practice, of such algorithms? So certain protocols provide certain guarantees... so what? Do you think these protocols are likely to be genuinely useful? Why or why not? A theoretical guarantee of tolerating corruption of n-1 our of n parties sounds pretty good! Why should I be skeptical of someone proposing to adopt such a mechanism for political purposes? If there is no legitimate mathematical objection, how can I in good conscience support any other system? $\endgroup$ – Sam Lichtenstein Apr 19 '16 at 1:29
  • $\begingroup$ That is to say, for any given system of voting, if a provably effective attack exists, I think it behooves the mathematically sophisticated community to publiciize the attack as much as possible. A vulnerability in the decisionmaking processs adopted by our leadership is a vulnerability to which literally everyone in our society is exposed. $\endgroup$ – Sam Lichtenstein Apr 19 '16 at 1:32
  • $\begingroup$ And if we can do better, by adopting a better set of institutions, then every moment we linger under obsolete institutions represents a wasted opportunity for improvement, when we could have done better. These instances undermine democracy itself. So why haven't we adopted the superior institutions yet? It's hard to credit any explanation other than corruption. $\endgroup$ – Sam Lichtenstein Apr 19 '16 at 1:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.