5

I had this idea a few years ago and improved it today as I notice a hole or two. I believe I have the system down right but If there was a hole the first time there may be a hole this time. I believe the below will have a voter voting anonymously and impossible to tamper with unless the party handing out tickets give out more tickets than it should. What do you guys think?

Lets say there are many parties who track votes (simply known as party) and a verification-party who validate your identity and allows you to vote. Starting from the point the software knows you are validated it starts the verification-phase.

  • Connect and verify yourself to the verification-party. The voter should receive a ticket which is simply a signed GUID.

  • Parties will be contacted in a chain. If the order is randomize find out what the order is for the session

  • Generate X+1 public/private key pair where X is the number of parties. They should be unique and only to be used for this verification-phase. -edit- someone asked why. This is so if any link leaks data no other part of the chain can recognize it link since it has no matching data. Every step/link is encrypted with that party public key.

  • The voter send the signed ticket and 'encrypted data' to the first party. 'encrypted data' is a public key for that party + inner data which are for public keys for the next link in the chain.

  • Each party will check if the ticket is valid/signed by the previous party or verification-party if it is the first party. It will then decrypt the 'encrypted data' and take the voter public key which it keeps for the session.

  • The party will create a new ticket which is a new GUID and the remaining 'encrypted data' than and signs it. It hands it to the next party in the chain.

  • When the last party receives the ticket it will request a party-vote-ticket from each party (including itself). It will have two keys, one for itself one to give to each party. The party combines each of the party-vote-ticket and encrypts them with the voter public key for itself. The data is sent back up the chain

  • When each party receives the encrypted data it will use the public key the voter gave it before sending it up the chain.

The party-vote-ticket is simply a signed GUID which as i mention is encrypted with the voter public key.

The voter decrypts the data with each of its private keys and unlocks the vote-ticket to use in the next phase.

At a later time (minutes, hours, days) the voter may vote with the tickets. The following steps to vote are

  • Connect to any party with a block of data with a GUID
  • Each party will sign the GUID and send it to the next party.
  • The last party sees all the others have signed the GUID and it signs than sends the data back down the chain.
  • The voter now knows which party is last (even if its randomize) and been signed by each party. The voter can now trust the order since it is sign and will encrypt the vote-ticket + who the voter is voting for with the last party public key. The voter sends it through the chain.
  • The last party decrypts the data and duty is to send a copy to each party.

Some possible attacks

Identify The Voter

Looking at IP address: In both phase the data goes through each party before any data can be exchange or seen. This is to hide voters ip in the voting phase and disassociate the voter ID in the verification phase.

Data being passed in the Verification phase: The information one party gives to the next is a GUID which is different at each step and encrypted data (chained encrypted public keys). If there is a leak it won't matter because the encrypted data is different at each link in the chain thus no way to associate it with data elsewhere in the chain.

Time of voting: If a party notice only 1 voter has registered this minute and votes this minute it can be assumed the person who registered is the voter who voted. It is best to randomize the time voting and would be better if many/all Voters goes through the verification phase before going through the vote phase.

Vote Tampering

  • Changing votes: Because the voter has an anonymous ticket before voting all votes should be public and the voter should be able to check via GUID if the vote is correct with each party.
  • Repeat votes via reusing signed tickets: Since no one but the voter can see the ticket and no one can sign it this should be impossible. If a voter tries cheating and submitting multiple times ignore it. If the voter tries voting for someone else flag all votes as 'tampered' and record date/time with any other data the party wants.
  • Repeat votes with different tickets: This relies on the verification party not issuing more than one ticket to a person. Also each party should check if a ticket is correctly signed.
  • Voting for someone who has been verified but hasn't voted: Because each party encrypts its party-vote-ticket with the voter's public key no one but the voter should be able to see it. Again checking if it is signed is important.
  • Voting for someone who has not been verified and doesn't want to vote: This would be the issue of the verification party handing out tickets.
  • Parties Ignoring Votes: If a party is the last party and sees it does not like who the voter is voting for it may attempt to cheat by ignoring it. Again this is countered by the voter simply checking but also the voter can attempt to vote again using the keys as it was ignored the first time. A voter should be able to check if the vote went through within a minute or two even if the party decides not to real who the voter has voted for until a after the election.
Improve this question
8
  • 1
    I recommend looking into blind signatures.
    – CodesInChaos
    May 4, 2012 at 13:34
  • @CodeInChaos Interesting. I never heard of that. Thanks for telling me about it but are you suggesting I should change something here? I don't believe anything has to be signed blindly. I still need to separate the verification and the voting phase and I can't see what could change if I want to avoid parties seeing the voters IP address
    – Nick wheatley
    May 4, 2012 at 14:03
  • 2
    The descriptions is hard to follow. For example who is "you"? At first I thought it is the voter, but then the voter is named in item 4. For each list item, please make clear who is executing it.
    – Hendrik Brummermann
    May 4, 2012 at 16:56
  • 1
    What is the purpose of this voting system? I mean it is obvious that it fails the requirements set by the German constitutional court on political elections. But there might be some valid use for it. This might be related to the question: Who needs to trust whom?
    – Hendrik Brummermann
    May 4, 2012 at 16:58
  • 1
    Questions about protocols like this should be asked at crypto.stackexchange.com. But I'll start with your assumptions. Why assume no party will hand out more tickets than it should?
    – nealmcb
    May 4, 2012 at 18:45

4 Answers 4

Reset to default
5

This is too long for a comment, but I was asked for details.

The German constitutional ruled:

The usage of voting devices [...], is in compliance with the constitutional requirements only, if the essential steps of the voting and counting can be verified reliably and without expert knowledge.

Translation by me, see link for the original text).

The verdict was about simple voting computers, which have a series of buttons and a display to show the vote for confirmation.

It was impossible for voters to verify that the button they pressed and information they see on the display, is the information that is counted. Furthermore they cannot verify that there are no additional votes. The government tried to argue that the voting computers had been verified by an official institution and sealed to prevent manipulation.

The court made it clear that "verified by experts" is not good enough to fulfil the requirements for democratic elections.

Your proposal has several instances that require expert knowledge, as far as I understand it:

  • How can non-experts verify that keys are okay? (e. g. unique, non predictable, strong randomness, ...)
  • How can non-experts verify that the device is okay? (e. g. does not encrypt/sign something different from the user choice, does not transmit additional information, ...)
  • How can non-experts verify that the encryption step is okay?
  • How can non-experts verify that the signing step is okay?
  • How can non-experts verify that the signature verification step is okay?
  • ...

I think it is obvious where this is heading.

PS: How do you prevent voters from proofing to a seller, for which party they voted?

Improve this answer
6
  • Thanks for answering my question! Is electrics via computers (or digitally) legal? and if so are the users anonymous? It sounds like they are not and must use traditional paper votes. I always wondered if a location or two dumped half of the votes or tampered in another way in secret. I heard at one location voting for the city mayor they had a recount which led the other party as a winner but that was a recount and it the original did win but with a small margin. Although i dont think anything was tampered. It could happen simply by misreading/miscount or human error. /end-random-thoughts
    – user5575
    May 5, 2012 at 19:09
  • I wonder if this question technique can be used but making the information simpler or easier to understand for non expects. I can see some ways but op will probably post so i wonder if he comes up with the same ideas as me.
    – user5575
    May 5, 2012 at 19:13
  • That is very interesting. I have thought about how to present this to the users. Non-experts do not need to understand how the technology works. Its great the scope is limited to "voting and counting can be verified reliably and without expert knowledge". The counting is simply all parties making ticket-id (which are anonymous) with who they voted for public. One can simply see if their vote shows up to see that they indeed voted and counted towards the results.
    – Nick wheatley
    May 5, 2012 at 20:22
  • To make things simpler the party whos duty to send results to other parties can pick a GUID so each party can display the vote result as that instead of their unique party ticket id. As for the verficiation phase. Any software compatible with the protocol may be used although software could be used to identify you and track your information. But thats outside of the scope and doesn't affect your voting. Actually it could if...
    – Nick wheatley
    May 5, 2012 at 20:23
  • the same software is used it could lie behind your back and give you someone elses information who voted the way you wanted but use your ticket to vote for someone else. I guess now the problem is how do the software itself isn't cheating you. That is a good problem to think about. +1
    – Nick wheatley
    May 5, 2012 at 20:23
4

This scheme is much too complicated to evaluate on this board. Also, you did not provide some critical information that would be necessary (the application domain where it will be used, the level of security that is needed, the threat model, who is trusted and why that trust is justified).

So, instead, let me suggest some general principles for you:

  • There is a tremendous research literature on how to build secure, anonymous voting systems using various cryptographic protocols. Before trying to invent your own scheme, you should start by reading about what's been done before and figure out if those schemes or techniques would meet your needs.

  • Instead of posting a specific scheme, I think you'd have better luck if you posted the requirements and asked what would be the best way to solve those requirements.

  • The generally accepted criteria for evaluating these sorts of protocols is as follows:

    • They should be published in the peer-reviewed research literature.
    • They should come with a clear statement of the threat model, the security properties achieved, and a proof of security (a proof that those security properties are indeed achieved, under that threat model).
    • If you are using a non-standard protocol, it should be clear why you are not using an existing, vetted scheme.

    The requirement for a proof of security is a very important piece. Anyone can build a complicated protocol that they themselves can't see how to break -- but that doesn't mean it is secure. The trick is to build a protocol that no one else will be able to break ... and indeed, to build a protocol where there is a rational basis for confidence that no one will be able to break it. That's much harder, and that's why cryptographers typically expect and demand a proof of security.

Improve this answer
2
  • +1. Would you happen to know anywhere i may submit a paper?
    – Nick wheatley
    May 6, 2012 at 12:40
  • @Nickwheatley, sure! You could look at the following research conferences: EVT/WOTE, EVOTE, REVOTE, VoteID. Many of these are held once a year or once every other year. Also, conferences on cryptography and computer security might be other candidates. See also IAVOSS for more links. Make sure to read the research literature and previous proceedings before submitting.
    – D.W.
    May 6, 2012 at 21:23
3

This is very unclear.

Bullets 3-4-5 - who is generating the keypairs - what is being sent and encrypted to whom? I'm assuming the voter as he sends the "public key" to each party as encrypted data generated for that party + next links in the chain.

How do the parties decrypt the "encrypted data"? You need a private key to decrypt; and seemingly that is still only in possession by the voter who generated it. Also, why are you encrypting public keys? Public keys do not have to be kept private. I don't think you should be generating new X+1 keypairs for each vote -- that seems very excessive (keypair generation is slow and computationally expensive) - reasons why SSL and GPG only use keypairs at start of handshake and then switch to symmetric cipher.

Anyhow; I think the gist of your method is you have a cycle of collectors (say C1, C2, C3; you call parties), a token-issuer, and the voter (you). You verify your identity with the token issuer somehow (say photo ID, social security #, or something), they issue a 128-bit token to vote and mark your name off the 'given a token' list. C1, C2, C3 all have private keys (known only to them) and public keys known to everyone. You generate a one-time keypair for yourself, and sign your token. You encrypt a message to C1 with your signed token and your public key saying I'd like to vote soon, please give me a second token. They replicate these details with C2 and C3 somehow, and then give you back a second token that's encrypted with your public key. You use that second token to vote and your vote propagates along to the other collectors.

How do you know that your verification-party is the real verification party and not an imposter who collects verification details and goes to the real verification party to steal your vote?

What would prevent parties from recording extra data? What happens when one link in the chain goes down? Say DDOS attack? No votes can get recorded?

What would happen if C1 upon receiving your token, chooses to read the GUID from it, generate a fake-voter keypair and pretend to be you. That is they sign the token, register it and start passing it to the next user and then vote with it. Yes, you'd be able to see someone voted with your token differently (but not if they voted the way you would have); but you can't really do anything about it. (You could try to revote; but that would just invalidate both votes still denying your ability to vote).

Improve this answer
6
  • Bullet 3: I just state the voter generate the keys but the voter isn't sending it to anyone unless stated. They are used in the encrypted data step. Each party have a public available and thats how the voter encrypts each key to make 'encrypted data' in step 4. The party would use its private key to decrypt. Public keys is decrypted because otherwise it would be the same down the chain and final party can partner up with first party to associate the voter and the tickets.
    – Nick wheatley
    May 4, 2012 at 20:19
  • The entire data doesn't have to be encrypted with the public key. It just needs a way from hiding the next public key from the previous parties. Encrypting a key with the public key than encrypting the rest of data with the key is perfectly fine. Your gist of it is roughly correct. The verification-party is out of scope but it would have a public key which all parties know in advance to check if it is properly signed.
    – Nick wheatley
    May 4, 2012 at 20:26
  • I imagine if it is a real election you would get some kind of signed card and go to a building showing proper identification (like 2 gov issue id's) and get a token there which you use to start the process. It doesn't matter it depends what kind of election (if its a school it doesnt have to be that complex). The entire process I assume all parties record ALL the data it can get on you and at least one party is not in cahoots. If all parties are than it doesn't matter what you do anyways as they can all just claim they implement this and do something else.
    – Nick wheatley
    May 4, 2012 at 20:30
  • I also assumed no link will go down. If it does that pretty much stop things. I did try to have it load balance in both phases. But the verification phase the voter must know for at least that session. If C1 fakes you, you won't receive your tickets. Thats another reason who there is X+1 public keys. C1 can't see the public key you expect the data to be in. That would raise suspicion and have voters mad that something has been tampered. In voting phase C1 can't bc only the final party can see the vote tickets. In which case my question mentions. The voter would simply check and notice.
    – Nick wheatley
    May 4, 2012 at 20:38
  • Those are pretty good questions and thoughts! I actually didn't think about what happens if C1 tampers (but i did imagine leak or be cahoots with another party)
    – Nick wheatley
    May 4, 2012 at 20:41
2

I find this kind of end-to-end voter verifiable (E2E) system protocol fascinating. However, perhaps https://crypto.stackexchange.com/ would be a better place to discuss them.

I think the two most difficult criteria for such a system are:

  1. A voter is able to prove to himself that his selection was included in the final vote total.
  2. A voter must not be able to prove to a vote-buyer that he really did vote the way the vote-buyer wanted.

The most common way to accomplish (2) involves physical voting places, which allow observers to see that no bully is looking over the shoulder of the voter to confirm that the voter voted the way that the bully wanted. Alas, most physical voting places today use a protocol that fails (1).

While your system succeeds in (1), which already makes it better than many voting protocols, it appears to me that it fails (2). With this protocol, it's possible for an intimidated voter to send a copy of the decrypted vote-ticket GUID to a bully before the "voting phase" starts, and then later the bully can match that GUID to the published public votes to see how that voter really voted. Then the bully can reward those voters who voted the way the bully wanted, and punish any voters who refuse to hand over their decrypted vote-ticket GUID. (Or am I missing a critical feature of this protocol?)

Improve this answer
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .