Daresnot

electronic voting with time limited privacy Link to heading

Cory Doctorow’s Walkaway, was my favorite novel of 2018. For a long time science fiction felt dated to me, everything I read felt stale. The real world had become far weirder and felt more futuristic. I’ve always particularly liked the sort of sci-fi that grapples with the big ideas. The sort that analyzes the hopes and anxieties of the present by telling stories about the future. Sometime in late 00s it felt like sci-fi gave up on these kinds of stories and settled for comfortable genre stories. It was like no one could properly integrate smartphones, ubiquitous mass surveillance, and the sheer weirdness of the current media environment into their storytelling. (Except maybe Warren Ellis and Charlie Stross, but they had done it a decade earlier and moved on to other things.) Then I read Walkaway and it felt new. The book really gets hold of a big idea and wrestles it to the ground.

  • How would society react if it were on the verge of material abundance?
  • How would you build a new society if all things were fungible, if wealth as we know it, just didn’t matter?

In a way it also felt very old. It’s like a modern version of The Dispossessed. Doctorow create his version of the Anarresti, the Walkaways. Walkaways secede from regular society and turn their back on it to find their own way of living in this world of material abundance. Walkaway culture is open source culture and maker culture, so it’s philosophy is embodied more in tools than texts. These tools are described through out the book. One of them is Dare Snot, an anonymous voting system for controversial issues.

The core idea was that radical or difficult ideas were held back by the thought that no one else had them. The fear of isolation led people to stay “in the closet” about their ideas, making them “the love that dare not speak its name”. So lovedaresnot (shortened to “Dare Snot”) gave you a way to find out if anyone else felt the same, without forcing you to out yourself.

Anyone could put a question — a Snot Dare — up, like “Do you think we should turf that sexist asshole?” People who secretly agreed signed the question with a one time key that they didn’t have to reveal until a pre-specified number of votes were on record. Then the system broadcast a message telling signers to come back with their signing keys and de-anonymize themselves, escrowing the results until a critical mass of signers had decloaked. Quick as you could say “I am Spartacus,” consensus plopped out of the system.

I read this and thought, “This is a terrible idea!”.

  • How do you stop people from shill voting?

    If somebody put up something I didn't like I'd just spam fake votes 
to trigger the reveal message.

  • Who generates the one-time key?

    If it's a central server, then wow, that's a huge incentive to pwn 
that thing, or at least cheat and take a peak.

  • What do you do when the assholes show up and post issues like:

    Who thinks Dave is a fat, ugly, poedophile and should just kill himself already?

  • What if the voters don’t come back to reveal their votes?

  • and so forth…

Maybe it is a terrible idea. Maybe it’s not. Maybe Cory’s already thought about this. Maybe he’s talked it through with folks that are smarter and more knowledgable than me like security experts and cryptographers. Maybe the version in the book is incomplete because it’s a novel, not a paper on voting systems.

So, I decided to treat it as charitably as possible. I’ll assume it works and try to figure out how it could work. It will be a fun challenge. (Aside: One of the my favorite examples of this exercise is Goblins, the Fungal Body Politic. Goblins only make sense if they are a fungus.) So here I go, doing something you really shouldn’t do, trying to design my own secure protocols. It’s not rolling your own crypto bad, but it’s definite land war in Asia territory.

Vizzini in the battle of wits

DISCLAIMERS Link to heading

  1. I am not a cryptography expert.
  2. There is no implementation yet.
  3. It has only been attacked and debugged in conversations with a few other people and in my own head.
  4. I purposefully did not search for an existing solution in the literature. I was more interested in the puzzle than using the end product. So, if I propose something that someone else has already thought of just tell me. I’ll be happy to hear it. It means I’m on the right track.
  5. I purposefully avoided homomorphic encryption because I don’t understand it well enough to know how using it might affect verifiability.

The Protocol as described in the novel Link to heading

  1. An issue to be voted upon is declared. It is a yes/no proposition.
  2. Voters who agree with the proposition generate a one-time symmetric encryption key.
  3. They then generate a digital signature using a known public/private key pair. That they’ve registered with a key server or otherwise claimed as identifying them.
  4. They encrypt this signature with the public key they generated in step #2.
  5. They post this key to the server.
  6. They monitor the issue and watch for the signal to decloak.
  7. When the signal is sent they transmit their one-time key to the server.
  8. The server waits until a sufficient number of keys have been received, then reveals the votes.

This has obvious problems Link to heading

Problem #1: Shills Link to heading

Problem #2: OpSec Link to heading

Problem #3: Trust Link to heading

Problem #4: WHAT IF NO ONE COMES BACK? Link to heading

Summary of the limitations of original formulation Link to heading

  • Binary questions
  • Voter defection
    • not deanonymizing
    • voting multiple times
  • How can you trust the central system?

Reformulating the protocol Link to heading

Properties of Voting Systems: Choose 3 Link to heading

  1. Integrity - correctness of the vote count
  2. Authenticity - proof of voter identity
  3. Verifiability - validation of the vote count afterward
  4. Confidentiality - privacy for voters

Problem Statement: To design a voting system with Link to heading

  • Integrity - Accurate vote count
  • Authenticity - Protection against double voting and shill voting
  • Verifiability - Votes can be validated and linked to voters afterward
  • Confidentiality - Votes are secret while voting, public afterward

…and you don’t have to trust a central authority.

Requirements Link to heading

  • Arbitrary consensus calculation, not everyone has to vote.
  • Proof against arbiter defection
  • Proof against voter defection
    • Lying about votes
    • Failing to reveal votes

My Solution Link to heading

My Solution which won’t fit on a slide. An issue is posted and options for voting are set.

  1. The set of eligible voters (V) is defined.
  2. A minimum quorum (Q) to decide the issue is chosen. Q <= V
  3. A minimum number of returning voters (R) is declared. R <= Q
  4. A voter generates a symmetric key (VOTEKEY) and a vote message.
  5. They encrypt the vote message with VOTEKEY and a salt and digitally sign the crypt text.
  6. They split the key into V-1 shares using Shamir’s Secret Sharing with R shares needed to reassemble.
  7. They encrypt one share for each other voter using that voter’s public key.
  8. They post the votes and the shares publicly.
  9. When a quorum is reached users decrypt their key shares and post them publicly.
  10. Once R voters post their shares all votes are decrypted.

Attack Vectors Link to heading

  • Walking the social graph
  • Timing
  • Arbiter snooping

Known Attacks Link to heading

  • Shill attack
  • pwning the server
  • Reliance on voter OpSec
Limitations Link to heading
  • Only yes/no propositions can be voted on.
Flaws Link to heading
  • Shill attack
  • pwning the server
  • Reliance on voter OpSec

TODO: Transcibe new protocols here Link to heading