Saturday, May 31, 2008

Delegated Democracy - Part 4

I've been discussing delegated democracy with Coriolinus and Yev here and at Coriolinus's blog, and think I've got a good next iteration of the idea. The entire system as I originally proposed it was extremely overcomplicated, and now have a three-part process that I think cuts to the core of the idea.

Part one: Registration
  • Citizen enters the party HQ, checked for bugs & weapons.
  • Citizen registers, gets a username and provides a passphrase, then leaves.
  • Passphrase -> cryptographic hash function -> key generation function -> decode key, stored at party HQ.
  • Voters would also have the option of providing their own decode key directly, in the event that they want a higher entropy or don't trust the polling authority with their encode key.
Part two: Email
  • Citizen composes vote, then runs encryption program, entering passphrase, stored briefly in memory.
  • Passphrase -> cryptographic hash function -> key generation function -> encode key, stored briefly in memory.
  • Vote is encrypted with encode key, saved, then passphrase and key are wiped from memory.
    • The voters mentioned above who opted to provide their keys will skip straight to the encryption step.
  • Encrypted vote is emailed to party HQ.
Part three: Votes counted
  • Party HQ receives citizen's email.
  • Email is decrypted with decode key. If successful, this verifies the citizen's identity and that (s)he was not coerced.
  • Vote is added to tally for given question.
In essence, it is just an implementation of electronic direct democracy, but reduces the problems of
  • scale,
  • voter fatigue,
  • complexity, and
  • manipulation by time framing.
It does not address the problems of
  • demagoguery, which I think exists now in any form of democracy (direct or otherwise), and
  • self-interest, of which I also think everyone, including present-day politicians, is guilty.
People who do not have regular internet access would have the option of using several third parties to cast their votes for them, only one of which has the correct passphrase. This would allow for a great deal of automation, thus opening the doors to voting by phone, fax, snail mail, or in person at a third party location. Eventually the party could also support these alternative methods itself, and I think this idea could work for the elderly, disabled, or technologically disinclined.

Labels: , ,

12 Comments:

Blogger coriolinus said...

This system is functionally no different from one in which the user creates a username and password during voter registration, and votes in a secure HTTPS session.

You need to have a username component--it really doesn't matter if it's the voter's birth certificate name, their SSN, or whatever, just so long as it is likely unique and orthogonal to the secret component--to reduce the problems associated with hash collisions.

I still prefer a system in which the user just provides their own public key, if only because they will get more entropy into it than is possible using a key generated from a hash of a short phrase. The other drawback to using this system instead of a public-key-based one is that you lose the ability to prove to a third party that you voted in a particular way--an ability necessary for the trustworthy delegation of votes.

The case in which someone is standing with a gun to the voter's head and they need to enter a wrong password which nevertheless generates output seems implausible to me. More importantly, the solution proposed here is a transparent failure mode: any inadvertent typo in your passphrase means that you generate convincing-looking gibberish indistinguishable from your actual vote. This will result in a failure rate of people who think they voted but instead typoed. I don't like that.

3:18 PM, June 06, 2008  
Blogger Explodicle said...

I agree with the technical points, in that it is similar to HTTPS (with no confirmation) and that a username should be required. As for the providing your own key to ensure entropy, I don't see any reason why both options couldn't be available. I just think most people would prefer the passphrase. (The post has been updated accordingly.)

However, I don't see why it's so helpful that you prove to someone that you voted in a certain way. So what, if a famous person convinces 1000 people to vote Aye but secretly votes Nay? That's just one vote.

However, I think it is critical that we keep the ballot 100% secret. You might think it's a rare case, but there's no solid evidence to say how frequent it would become. I'm not just concerned with threats, but with bribes. In your recent post on the topic you suggested that the coercion problem can be solved by employing the police, and I find it unreasonable that we ask any officers to risk their lives fighting crime that is completely preventable. Not to mention that not all police everywhere are 100% trustworthy, reliable, and prompt.

7:47 PM, June 09, 2008  
Blogger coriolinus said...

However, I don't see why it's so helpful that you prove to someone that you voted in a certain way. So what, if a famous person convinces 1000 people to vote Aye but secretly votes Nay? That's just one vote.

That's not the issue. The issue here is establishing a trustworthy system for delegating one's vote. A public-key-based signature proves that I, the person you trust enough to delegate your vote to, voted this way; that it's not just some random git spoofing my email address. This automatic provability is what would make it easy to set up delegation software.

As far as keeping votes secret: anyone can encrypt their (signed) vote using the polling authority's public key. This keeps it a secret from everyone. If they want, they can encrypt it with the public key of everyone they send the vote to; this requires a bit more configuration* than just adding the email address to a broadcast list but keeps the vote from everyone except the recipients**. The only people they cannot keep it secret from are those people who use it as their delegation source. Again, in my opinion, this is not a bug it is a feature. I would not trust a delegated voting system in which I could not determine in which direction my own vote was cast.

-----
* i.e. individually encrypted personal emails

** Unless one of said recipients re-publishes the decrypted vote.

10:18 PM, June 09, 2008  
Blogger coriolinus said...

The beauty of public key encryption is that you never have to give anybody your secret passphrase. By giving your passphrase to a third party--even if you give several passphrases to several third parties, with only one being correct--you are opening up vulnerabilities: that third party could have a laptop stolen with their passphrase database. Or they could inadvertently employ an untrustworthy person who makes a personal copy of that database. Or they could just go rogue, sell the database, and retire to the Caribbean. It doesn't matter how an identity thief gets ahold of your secret and thereby your vote, only that the possibility is non-trivial. In the case of a third party which has thousands of passwords stored, many of which may be false, but many of which are sure to work, it is not inconceivable that someone may decide it is worth it to put considerable time and effort into illegally acquiring those thousands of votes. However, the only way for anyone to get thousands of secret keys is to steal the personal computers of thousands of voters--a much more challenging task.

On another topic, there is no system in place right now to prevent someone from bribing another person to vote in a certain way. There is no system which prevents someone from blackmailing voters into a particular vote, or from threatening to murder them or their family if they vote "badly." There is a measure of anonymity in the polling booth, but a sufficiently dedicated attacker could defeat that. The simplest method would be to volunteer at the polling station and insert some sort of hidden camera during setup.

You're proposing to set up a system by which we could prevent this. However, we'd be introducing new controls above and beyond those that are actually deemed necessary for the status quo. Moreover, those controls would guarantee that some voters' votes go uncounted. I don't have the statistics which tell the exact rate, but it'd be easy enough to determine experimentally: just have some large computing center compare the number of bad login attempts vs. valid ones.

I assert that it is important to ensure that everyone who wants to vote have the capability of doing so. Disenfranchising a person, even for a single vote, because they typoed while entering their password, seems like a very bad idea.

Given all that, I'd much rather that the behavior on a bad password entry be to ask the user to try again instead of failing silently.

10:48 PM, June 09, 2008  
Blogger Explodicle said...

I just realized a major flaw in my idea overnight: since the user can generate the decode key as well, that could be used to verify a vote before sending it in. :-P

Ok, I'm going to have to rethink this implementation. I still want better protections to the secret ballot, but I'm not going to argue for it until I have something more concrete.

8:34 AM, June 10, 2008  
Blogger Explodicle said...

I think I've got something good, but I don't have time to post it now. I'll go over it today and hopefully post later tonight.

Thanks for suffering a fool, by the way... it's very helpful to have feedback.

8:42 AM, June 10, 2008  
Blogger Explodicle said...

With regards to the issue I just mentioned, I agree now that we should use a system similar to the one you originally proposed, where you just encrypt with a public key provided by the polling authority. However, I would still want a passphrase included in the email, as well as a random nonce so results couldn't be duplicated.

The status quo you claim will be preserved does not exist because electronic voting is not widely used in the least. The examples I am drawing on are historical, and they are the reason we have a secret ballot in the first place. The hidden camera scenario you propose wouldn't catch individual targets, and it's the whole reason I mentioned the voters be checked for bugs. In the scenario you propose where someone steals a load of possible passphrases, there is no way for a buyer to determine whether or not every single one of those passphrases was just made up, and so the sale price would be prohibitively low. (In essence, it creates a huge information asymmetry failure in the black market for passphrases.)

I am also less concerned with disenfranchising voters who can't double-check their passwords than I am with preserving the liberty of those who type correctly. If you had an automated bot perform the action, you could do it once really carefully, and then go to the headquarters and look at your voting history just to make sure.

If you really think the polling authority should officially publish people's public keys so delegation can be certain, that's fine by me. However, I would also want non-human entitites (like corporations) to be able to register public keys as well. You shouldn't have to delegate to a human being.

6:00 PM, June 10, 2008  
Blogger coriolinus said...

I would still want a passphrase included in the email, as well as a random nonce so results couldn't be duplicated.

Just signing it with your private key proves that you personally generated that vote. As far as duplicate prevention, it's trivial for the polling authority to ensure that only one vote per user is counted, since this is all electronic. As far as duplication of results by someone eavesdropping on the message if you choose not to encrypt it, that doesn't work. If you haven't read it yet, take a look at Wikipedia's take on digital signatures.

The examples I am drawing on are historical, and they are the reason we have a secret ballot in the first place.

The only people who can't gain every benefit of the secret ballot are those who wish to be delegates. For them, just as for members of Congress, the public's right to know the voting records of their delegates trumps the delegate's right to a secret ballot.

In the scenario you propose where someone steals a load of possible passphrases, there is no way for a buyer to determine whether or not every single one of those passphrases was just made up, and so the sale price would be prohibitively low.

There is no way to tell which passwords are real, but the cost of simply generating and submitting votes based on all of them is near zero. It is possible to determine, based on the number of passwords in the stolen database, the number of voters using the system, and the average number of fake sources per voter, the number of real votes in the database to a high degree of confidence. The information asymmetry you posit doesn't actually exist.

If you had an automated bot perform the action, you could do it once really carefully, and then go to the headquarters and look at your voting history just to make sure.

If you have to go to party HQ and check your voting records in person, you have just negated the benefits of electronic voting. If it is possible to check your voting records remotely, you have just introduced a point of entry for vulnerabilities impacting any protections you may have used to ensure the secrecy of the ballot.

If you really think the polling authority should officially publish people's public keys so delegation can be certain, that's fine by me. However, I would also want non-human entitites (like corporations) to be able to register public keys as well.

Having the certificate authority publish peoples' public keys isn't really necessary to my plan, though if the submission of a public key is conducted with reasonable security, such a repository of trust might not be a bad idea. All that's necessary is that the polling authority trust that the public key they have from each voter belongs to that voter and not some man in the middle, and that the voter believe that the public key provided by the polling authority is also real. This is accomplished by having the voter show up in person to register and swap keys.

In general, even if the polling authority does not publish a register of public keys, there are a number of ways to for voters to ensure that the key they have for the person they want to use as a delegate is valid. These range from face-to-face key swaps, to the use of a certificate authority, or a web of trust.

I'd be fine with corporations publishing keys and acting as delegates--there's nothing in my scheme as written that actually prevents that. However, I strongly believe that they should not be able to vote in and of themselves; that is a right reserved to citizens. Corporations do not get that right.

6:40 PM, June 10, 2008  
Blogger Explodicle said...

Just signing it with your private key proves that you personally generated that vote.

Yes, but it does not prove that you have not been coerced. Protection from coercion is the only reason I want passphrases.

For them, just as for members of Congress, the public's right to know the voting records of their delegates trumps the delegate's right to a secret ballot.

The public gets to know how congress votes because they represent our interests. In a direct democracy everyone represents their own interests, and just because you suggest that others vote a certain way does not mean you should lose your right to privacy for your own vote. This is why senators do not have to disclose who they vote for in presidential elections - they are only representing themselves, not their constituency.

It is possible to determine, based on the number of passwords in the stolen database, the number of voters using the system, and the average number of fake sources per voter, the number of real votes in the database to a high degree of confidence.

I'm a little confused here, three questions:
1) How does the buyer of this list know it is not a complete fabrication?
2) How would anyone get this list in the first place? I'm assuming only the user would have a copy of his passphrase, with the authentication server only checking hashes once they come in.
3) How is scenario any less likely without the passphrases?

If you have to go to party HQ and check your voting records in person, you have just negated the benefits of electronic voting.

I'm saying you could optionally check it once, to make sure you have everything set up properly. That's a far cry from having to go in and vote every time.

Corporations do not get that right.

So, what's to stop me from setting up my own corporation solely to suggest votes without having to expose my own?

11:22 PM, June 10, 2008  
Blogger coriolinus said...

The public gets to know how congress votes because they represent our interests.

All that a delegated democracy is, is an informal, ad-hoc system of organizing a representative democracy within the basic framework of a direct democracy. By delegating your vote to a person, or a corporation, or whatever, that entity becomes your representative. As such, that entity's votes as your representative have to be available to you.

There is absolutely nothing preventing me from creating as many key pairs as I wanted. I could easily register to vote using a dedicated public key only for that purpose, and broadcast out votes to whoever chooses me as their delegate using a completely different key which I use to identify coriolinus. I could even email those votes to the party server; they'd just be ignored, as the software should be counting valid signatures for identifying its voters, and coriolinus isn't anywhere on the rolls.

By using two keys that way, someone who wanted could keep their own vote completely secret while still acting as a valid delegate. If someone were actually threatened, or suspected that they would suffer negative consequences if their actual voting record were brought to light, this would be a completely valid option. However, whatever negative consequences might happen if their personal vote were revealed would probably still happen if they personally vote secretly but publicly use the n votes delegated to them in some other manner. It is for this reason that I think blackmail, attempted bribery, threats, etc. should be a matter for the police: they are exactly as much a threat to this system as is the prospect of some miscreant attempting the same crime on a Senator.

I'm saying you could optionally check it once, to make sure you have everything set up properly.

You use the password in conflicting ways. On the one hand, it's stored on your computer and automatically applied to your votes; you just need to set it up and keep it going. In that case, it's useless, as it adds nothing to the process. On the other hand, you have to enter it manually each time, so that when threatened by some observer, you can generate a convincing non-vote to fool them. In that case, we have the transparent-failure issue, which remains to me a serious problem.

I'm a little confused here, three questions:
1) How does the buyer of this list know it is not a complete fabrication?
2) How would anyone get this list in the first place? I'm assuming only the user would have a copy of his passphrase, with the authentication server only checking hashes once they come in.
3) How is scenario any less likely without the passphrases?


1) Trust. In general, Crime Lord Alpha can trust that Underling Bravo will carry out his orders to go steal the password list at Public Repository November. Alpha has many spies and informants, and Bravo is scared shitless of him, so he can be reasonably sure that when Bravo reports "mission accomplished" and hands over a list of random data, he can be confident that Bravo didn't just set up a quick random number generator and let it run. Because of Alpha's stature, Nefarious Charlie is willing to pay Alpha the real money for the data.

The whole thing kind of mirrors the identity theft economy.

2) In the system as described in the root post, a voter's vote is only as secure as a single passphrase. The root post also describes third party voting assistance corporations accepting voting instructions by phone, fax, etc; in order for those businesses to function, they need to have the voter's passphrase. Therefore, there would exist at each of those third party corporations large databases of user/password combinations, some percentage of which are sure to be real. Those databases are the expected targets of thefts of this type.

3) In a purely public-key-based system, every voter is responsible for the generation and security of their private key. They should never give it to anyone. This precludes the possibility of forming third-party corporations offering voting by phone, but it also prevents the formation of databases which could be used to steal the voting identity of large numbers of people.

1:17 AM, June 11, 2008  
Blogger Explodicle said...

That's a good point. I think you're right about keeping your own private keys (and potentially passwords) private because of identity theft potential.

However, I still believe in the mandatory secret ballot. I've been thinking about the typo issue you mentioned, and there are a few ways to verify for the user without telling anyone else. For example, the hash of the passphrase could select and display a sentence from your favorite book. Enter a few fake ones beforehand and note the sentences, so when you're coerced you can say any one of them is your legitimate response. We can get around technical and usability issues without sacrificing the features our democracy already has.

11:24 PM, June 12, 2008  
Blogger Justin said...

I've been thinking about the security of a purely public-key based system versus lending someone your right to vote. The concern I have is that we need to rely on one of two groups for security:

A. The end users (voters). I do not believe the average person owns and maintains a secure computer, and they would need to run it frequently to avoid missing critical votes.

B. Third parties (delegates). It's possible for a corporation to securely store highly sought-after information. For example, there is a huge financial incentive to hack the Windows Update servers, or any of the Google Servers, but it just does not happen very frequently at all due to professional-quality security.

People who know what they're doing can still run the whole operation themselves; I just want people who can't afford computers, or the computer illiterate, to be able to let someone else handle it for them.

2:28 PM, January 11, 2009  

Post a Comment

<< Home