Sunday, January 11, 2009

Delegated Democracy - Part 6

I've been working on that idea for an online delegated voting system. Here's what I've got so far:

Three groups
  • The polling authority would be in charge of the voting process, and in this case would be the party.
  • The voter decides which options they like best for a given vote, and either vote on their own or delegate a third party to do it for them.
  • The delegates can be people, computer programs, Google, whatever you want. All that matters is that they've been given authorization to vote on behalf of someone. If you vote on your own, you are your own delegate.
Two types of ballot
  • The blank ballot is effectively your power of attorney with regards to delegating your vote. If you want you can give it to someone else, or you can use it yourself to make filled ballots (see below). It consists of three bundled elements, together encrypted with the polling authority's public key:
  • A filled ballot is what is actually submitted to the polling authority, and it says who you are and how you vote. It consists of three bundled elements, together encrypted with the polling authority's public key:
    • A blank ballot,
    • The vote number, and
    • Ranked options for the vote.
When the polling authority receives a filled ballot, it publishes the rankings and a cryptographic hash of the (blank ballot + vote number). If the username and password are valid, it counts the vote towards the final results, otherwise it is not counted. When polling has closed, the winning options and close runners-up are published.

Since you know what your blank ballot is, you can check how your vote was used once it's published, and if it's different than what you expected due to a security breach, you or your delegate can send an email to the polling authority telling them to blacklist that particular blank ballot.

You'd have to be physically present at the polling authority headquarters when you chose your username and password, but other than that the whole thing could be done online.


Labels: ,


Blogger coriolinus said...

If you encrypt the blank ballot with the polling authority's public key, only the polling authority can decrypt it. If you encrypt it with the polling authority's private key, anyone can decrypt it. If you sign the blank with the polling authority's public key, only the polling authority can verify it. I assume that you mean to sign the blank ballot using the polling authority's private key, which would make brute-force attacks that much harder.

Is the vote number of the filled ballot the same as the nonce of the blank? That would make sense, but it's not clear from the current wording.

I note that you're sneaking in something that looks like instant runoff voting, or at least building support capability into the system. Good for you on that, but it suspect it will take an even larger legislation to change the way winners are calculated (as opposed to the scope of this project, which is just changing the way voters physically vote).

If the username and password are not valid, does the authority still publish the vote? If so, why?

I am not sure what you mean by 'it publishes the rankings.' Is this just that it updates the results in real time?

Overall, I like this system. It seems (from my knowledge of cryptography and comsec) to be the start a workable, secure system. The key thing to note about it is that it places complete responsibility for the security of the blank ballot on the individual voter. It works to give them a numbered stack of blank ballots on a thumbdrive when they register ("For this piece of legislation, please submit your vote on ballot #40782 from your stack..."), but if they ever email the blank to anyone, it's best to treat it as already breached. If the voter is already a member of any PKI, they can securely transmit their vote to a delegate of their choice. Or they can bring the thumbdrive over and transfer blank ballots as necessary. However, I worry that most voters just don't understand how security works, and have no interest in learning. Email will be used to transmit blanks, and when those votes are (at best) blacklisted or (at worst) corrupted en masse without detection until after the fact, people will blame the system and not the security-oblivious voters.

3:26 AM, January 16, 2009  
Blogger coriolinus said...

I just figured out what you were getting at, encrypting the blank ballot with the polling authority's public key. You're saying that the voter assembles the blank themself, then encrypts it to protect their password from their delegate. In fact, there is no particular reason to protect the nonce; there's no reason the polling authority couldn't set up a website with a dropdown "Select the issue you would like to vote on" and a button "Generate a nonce." Strike the first paragraph from my previous comment, and the bit about the thumbdrive from the last.

The intent of the second paragraph remains the same: I don't know how you're generating the vote number of the filled blank. Perhaps it's an ID pointing to the current issue at vote? That's only necessary though if nonces are issued in bulk at registration. Having voters generate them on demand removes the requirement for this field.

In order to blacklist a particular blank ballot, you have to end a filled ballot containing an identical blank and a special flag. If you can do it by email, it's not standardized: some people might say "Please blacklist this nonce," and others might say "Please do not count the vote I sent in last tuesday." Formalizing the format lets us automate things. Automation is particularly useful if you're running software such as that described below, which automatically sends out blank ballots to the appropriate delegates as new issues come in. You don't even to have to tell your delegate you want to vote this one personally; you just generate a revocation and a new ballot for yourself.

Some of the security issues I mentioned in the last paragraph of the previous comment are invalid; I hadn't fully figured out how you intended the system to work. However, some points still apply:

Each voter has to generate a blank ballot for each vote; they can't delegate anyone in perpetuity to vote for them on selected issues. This is really more a feature than a bug--it's easy to think of cases where this is the desired behavior--but if the intent of setting up a delegation system is to make a direct democracy easier, this neatly defeats that intent, as each voter still has to think about each issue at least to the point of generating a ballot for it. I suspect it is unwise to underestimate voter apathy.

The voter has to know enough about crypto to perform two encryptions: one, using the PA's key, to secure their blank ballot, and another to encrypt the ballot for transportation to their delegate of choice. Most users these days simply don't have that capability.

You've done a good job with this system keeping things defined as open interfaces such that people can use whatever software they like, or even hand-jam everything. However, people are like water on a hill: they choose the easiest path, even if that path is catastrophic. For this to work, good software has to be available for distribution by the time the first voter registers, to ensure that the easiest path is the correct one.

Such software would have to have certain characteristics. It must be open-source, to please the paranoid and the nerds. It must be free, because nobody will pay without marketing, and nobody will front for sufficient marketing. It must be in a platform-neutral language to avoid vendor lockin. It must be automatic, something the voter can leave in the background which will automatically generate ballots, perform the necessary encryption, and forward them as required. It must be configurable: "I the voter send issues most tagged as 'Civil Rights' to the ACLU and issues tagged as 'Internet' to the EFF." It should be social, so that interested users can participate: "I the voter see this issue and want to contribute the tags 'meta-government' and 'voting system'." It should be clever, resolving conflicts between differing tagsets and delegation priorities intelligently. It should be available at the voter registration station and online.

The software actually sounds like it might be a fun project to work on.

3:29 PM, January 16, 2009  
Blogger Justin said...

Answering questions in no order:

1. The nonce in the blank ballot is just to allow users to generate a whole bunch of them without having to change their password, and to make sure all of the blank ballots are the same size.

2. The vote number (which is separate from the nonce) is to keep track of which issue you're voting for. So, vote number 1 could be the budget, vote number 2 could be to approve a contract, etc. You could use the same blank ballot for many different vote numbers.

3. My plan is to start a local party and run under this platform, allowing voters to decide my actions. That way no laws would have to be passed, it could be implemented gradually, and we could use one of the many better voting systems than plurality.

4. The polling authority still publishes as normal even if the blank ballot is invalid - the only difference is that the vote doesn't count towards the final result. That way you and your delegate can both check to make sure your vote was counted with the rankings that were submitted, but no one but you knows if it's your real vote or not.

5. When I say "publishes the rankings", I mean the party will make public the choices that have been selected in the vote. So, one published vote would be:
* hash(blank ballot + vote number)
* first choice
* second choice
* third choice
* etc
All rankings could be published on the web. I think real-time publishing would be better, but it's not critical.

6. I agree that this will need some very user-friendly software to work... it's unreasonable to expect people to do all of this stuff manually. I also agree with all the requirements you mention. I'd rather implement minimal features first, and then release tagging and automatic filled ballot generation as separate programs. It would also be preferable if the whole thing could be done on a secure web page hosted by the polling authority, so you wouldn't need to own computer to participate.

12:01 PM, January 17, 2009  
Blogger coriolinus said...

Responding to your points in order:

1. Good consideration! I hadn't even thought to ensure that blanks are all identically sized, but it is a good idea. That said, it is probably a better idea to have the nonce also always be the same length, and just have the user software pad the blank with random numbers as necessary. Otherwise, an attacker using traffic analysis could notice the length of the nonce the user was requesting, and subtract that from the known blank ballot length to get the length of username+password. It's not a lot of information, but it does reduce their search space.

2. I don't think that's a good idea. If you allow the same blank to be used for multiple issues, the nonce is actually now a nmany. The only case identical blank ballots should be submitted is when a user wants to revoke a vote. If they arrive in other circumstances, the best action would be to revoke that vote anyway, and generate an email notifying the user that system security has been compromised and that their previous vote has been revoked and that they should try again. Also that they might want to consider changing their password. Nonces are free; there's no reason not to just generate a new one for every vote, and have the server software keep track of which nonce goes with which issue under consideration.

3. Good luck! It sounds like a very interesting project to be part of.

4. This bit of obfuscation is only really useful if people regularly generate fake votes. I guess you're saying that one feature of the voter program would be "Generate fake vote on this issue." Another would be the option to automatically generate n fake votes per real one, and send them all in simultaneously.

5. That makes sense. The only amendment I'd suggest would be to eliminate the vote number from the hash; I remain convinced that the vote number is unnecessary by virtue of being non-orthogonal.

6. The problem with starting minimal and then adding features as separate programs is that users hate that. In general, integration of related functionality into a unified program is desirable, as is maximal completion upon release. Including an auto-updater as part of the program does partially mitigate the issue of maximal completion, but the key thing here is that adding substantial new features like tagging would require noticeable UI changes. Most users get scared when the UI changes.

There are pros and cons to a web-based implementation. It'll be more expensive to write, but would provide better service to people without computers. There are other options to help those voters, but they feel like workarounds.

4:59 PM, January 17, 2009  
Blogger Justin said...

1. Why would the user have to request a nonce from the server? I was thinking they could just generate their own on the fly; the nonce would be the random padding you mention.

2. If a new blank ballot is required for every vote, but a user who doesn't own a computer wants to delegate their vote to someone indefinitely, their only option would be to give out their username and password. I'd rather avoid that, because then they'd have to change their password (by showing up in person) every time they wanted to switch delegates. What's wrong with using a nmany?

4. Why would extra fake votes be helpful?

5. The vote number in the hash is only helpful if blank ballots are used more than once, to keep outside observers from being able to match two votes on different issues as cast by the same person.

6. That's a good point. It's not like anyone would be forced to use our client if they didn't like it anyways.

5:03 AM, January 18, 2009  
Blogger coriolinus said...

1. Well, what's the purpose of the nonce? I see two: to identify to the vote server which issue this vote is supposed to deal with, and to uniquely identify a particular ballot for purposes of revocation / anonymous confirmation that the vote was posted correctly. For the first to work, it has to be a server-generated number. For the second, it has to be permanently, globally unique.

2. As for why a nmany is a bad idea, it's just that reuse throws the capabilities above out the window.

As for the rest, that's where I was going with the 'configurable' and 'automatic' mandatory aspects of the reference implementation. The precise use-case depends on how you've implemented things, but in general it breaks down as follows:

If the reference implementation of the voter software is a standalone program, things are simple. Every time the program starts, it checks for new issues which are still under consideration. If a new issue has tags it's been configured to forward to a particular delegate, it automatically generates the blank ballot (including encrypting it with the PA's public key), encrypts it again with the delegate's public key, and sends it off. As long as the program doesn't depend on an installation process, users can run it off a thumbdrive on a public computer without worrying about security.

If the reference implementation is web-based, things work about the same, except it all happens on the PA's servers. When a new issue is created, it loops through every user. If they've created filters to send issues like this to particular delegates, it goes through the whole ballot creation and double encryption process automatically.

You're right that it would be a terrible idea to encourage voters to give away their username and password. Luckily, that really isn't the only solution here.

4. You've expressly engineered the system such that nobody can tell if a particular vote is any voter's real one from public records. However, unless the default is to automatically generate fake votes, few enough people will generate them manually that if a vote can be traced to a particular user, it can be assumed to be their real one.

6:26 AM, January 18, 2009  
Blogger Justin said...

(Sorry it took me so long to reply)

You're taking this in an interesting direction; let me make sure I'm on the same page as you:

The voter logs on to the PA's website, and specifies a delegate (or multiple delegates based on tags). When an issue comes up, the PA sends a secure email (as outlined above) to the chosen delegate, who then sends another secure email back with the vote.

I'm OK with this so long as the PA queries all delegates the user has ever listed (even with an incorrect password) every time a vote comes up, only using the real delegate's vote for the final tally. There should be no way for a potentially coercive delegate to know whether or not someone has really selected them.

11:12 AM, January 24, 2009  
Blogger coriolinus said...

You're on the same page as me as far as how a web-based reference implementation would work. The only part I disagree with is generating emails to all former delegates of a voter. What the delegate receives is an email with a blank ballot: an already-encrypted packet that they can't decrypt, straight from the PA. They have no way to know whose blank that is. In fact, there needs to be additional information in the email for them to even know what issue they're supposed to be voting on with this ballot.

There are edge cases, where a delegate could figure things out by simply counting incoming: the first or last person to delegate them, or a case in which the delegate is in constant contact with everyone upstream of them. For those cases, it makes sense to give the voter a tickbox to generate a fake ballot to any delegate.

However, that is not the general case, and it doesn't need to be auto-enabled. Bandwidth still isn't free, and it offends my sense of elegance to generate more junk traffic than absolutely necessary.

The one concern I have is that even with a web-based reference implementation, we still have to leave room for people to write standalone programs. This pretty much amounts to having a RSS feed of issues, and some sort of interface for anyone anywhere on the web to supply an issue number and get a nonce in return, without necessarily going through a human-readable interface first.

11:42 PM, January 24, 2009  
Blogger James V said...

I apologize in advance if my words sound like an attack, they aren't meant to be that way. I am hoping for either clarification or to possibly bring something overlooked to the idea. Overall, I like the idea of the people themselves impacting legislature, but I'm not entirely sure this system is fully ironed out yet.
I don't like the whole 'delegate' idea. I don't mind having a computer program that you write yourself cast your own vote, but delegating your vote to another person shouldn't actually be called delegating, it should be called deferring because that is what it will turn in to.
Look at the current system of House of Reps. Basically, the House is supposed to represent the sentiments of the people for whom they were elected, but we all know that system failed. I seriously doubt that anyone not committed to the daily monitoring of political events knows what their Rep is actually doing, and how best they represent the interests of the people in their AOR, let alone even be able to name who their Rep is.
I see a similar problem with this system. If you do not trust yourself enough to cast a good vote, you could simply sign your vote over to a 'delegate' whom you trust to make that decision for you. Not necassarily a bad thing. Here is where it becomes a problem: We have ACORN, a corrupt voting group that has been accused of voter fraud and is little more than a covert extention of the Democratic party. Corrutption permeates this organization at every level. If ACORN suddenly found itself in the buisness of casting votes on legislation for others, they could concievably replace the House. This becomes a problem as the 'newness' of the system wears off and people stop monitoring what people are doing with their votes daily.
Rather by having each person register and vote (electronically is fine, through a governmental website) seems more prudent because those that are too lazy or choose not to vote will not have an effect on the outcome as they shouldn't.
I totally agree that the current system of government, and especially the legislation, has not only failed, but become tainted and corrupted and requires a reform in itself. I think this system whereby the hand of the American people are in direct access to what congress is actually doing is a good idea, and I like what I have read thus far, with the expection of the delegate idea. I think that it creates an unnecassary backdoor for corruption.

4:30 PM, June 15, 2009  

Post a Comment

<< Home