Can a zero knowledge proof of voting be made using a trusted auth server (without client side crypto)?

Question

Questions:

1. Can one implement a secure voting system having all the features described below?
   • e.g. without disclosing any individual's vote to the government server (or the third party), preserving all the desired criteria of a ZKP vote, etc.
2. Are there any other security issues to consider in this kind of system, and how would you solve them?

Motivation

I would like to have a secure online voting system that

• does not rely on a crypto chip (like the German identity card), which is a huge barrier to deployment because it requires users to have special chip-reading hardware rather than just their ID card, nor similar barriers (e.g. most normal people cannot use self-managed PGP)
  • It needs to be usable by normal people, not just hackers or using special client-side software. More advanced functions like verifying a vote may require special software (so long as it could be done by any third party without more information than is publicly disclosed).
• can be decentralized, while preserving public proof that all participants in the decentralized vote are unique humans authorized to vote on that matter (i.e. without having to have a single party collect all the ZKP votes to ensure there is e.g. no double voting)
• does not provably disclose the person's vote to anyone, including the government auth server and any third party service (or client-side software) that they use to enter their vote
  • does allow the user to non-provably disclose their preferences to the third party, e.g. so that the third party can provide recommendations for good proxies

"Security"

Preemptively: "secure" here means "at least as secure as current voting methods", including vote by mail, not "perfectly secure against all possible attacks". However, it'd be good if attacks can be mitigated — e.g. if a TOTP ID card is stolen (and thus its signature revoked), it would be good to be able to invalidate that vote without knowing which vote it is.

For the purposes of this question, please don't derail to issues such as general website security, transport security, whether you trust the government to run such an auth server or have unique IDs, whether someone could steal your ID card and learn your password, etc, which are not unique to this issue.

My focus here is on the cryptographic question: can you have a ZKP of a vote, authenticated by a server trusted only to do authentication, without disclosing the vote to any of the intermediaries (etc.), and without requiring client-side crypto (like a cryptochip ID or a user-managed PGP key).

Background

Auth server

Suppose there is a government-operated server which:

1. Knows all of your officially registered information (i.e. anything on a driver's license, voter registration, etc)
2. Gives you a physical ID card (e.g. your driver's license), with an embedded TOTP display
   • the server should be able to revoke the TOTP by simply flagging it, with revocation being an in-person process with your local DMV or similar agency saying your card has been lost/stolen, as well as put a time limit on its authority (i.e. the expiration date of the card)
3. Allows you to authenticate to the server using your ID's TOTP + a password

4. Has an OpenID ish API, which permits third parties to request, and you to selectively authorize, any subset of the following information:

   • identification, such as any subset of:
     • a requester-unique, human-unique ID (basically, a non-reversible hash that proves to the third party that you are a unique human, but can't be associated with other sites' site-unique IDs)
       • sites wanting to correlate information on users would need to use a common requester (much like "single sign on" solutions), or at least a common pseudo-requester (e.g. for distributed votes on a single item, all sites cooperating on it could use a hash of the item being voted on as the 'requester'; for such situations, a site could request both an ID for their own persistent use, and one that's sharable on that issue)
     • name(s)
     • physical address (or subset thereof, e.g. county, city, or state only)
   • demographic information, such as any subset of:
     • gender
     • DOB
     • age
     • hair color
     • eye color
     • height
     • photograph
   • legal authority, such as any subset of:
     • voting endorsements (e.g. a list of jurisdictions in which you are registered to vote, parties with which you are registered, previous election participation history)
     • driving endorsements (e.g. car, motorcycle, truck etc)
     • police or government power endorsements (e.g. being a police officer, judge, district attorney, general attorney, etc)

   All such responses would also include a (site-specific) hash of the TOTP card used to sign it (for retroactively invalidating authentications made with stolen IDs).

   Again, note that you could authorize any subset of this information; e.g. if you want you can only authorize disclosure of a site-unique hash plus voting credentials, which provides the third party with only the bare minimum of "this is a unique human who is authorized to vote in districts XYZ".

5. Has an API allowing the third party to provide a blob (text or binary, which could also be just a hash) to the government server, and request that you sign it.

   When signing the provided blob (which would be displayed by the server), you could again authorize any of the above information to be part of the signature, as well as an optional timestamp.

   The signature itself could be use any number of methods.

   IMHO the simplest would be a government-managed PGP system, where the government owns a signing key for you associated with a given ID card, can revoke that key, signs that key using the key of the government agent who authenticated you, etc.

   The server would then just sign (using either your associated key or its own [if you're not disclosing your identity]) the tuple of (a) the blob plus (b) whatever information you choose to associate with that signing (in a standardized format).

Trust

Assume that this server is trusted only to provide authentication of someone's legal information (or human-uniqueness), and their authorization for government-related issues (e.g. voting power).

You do not necessarily trust this server to know what you may want your users to sign. E.g. it could be used to sign a private contract, by giving the server only a secure hash of the contract; then the user signs the hash, thereby signing the contract, without disclosing the contract to the government and without having to disclose more information than they want to the third party.

ZKP voting

Finally, suppose that you want a zero-knowledge-proof based voting system, in which:

1. Everyone knows who participated in the vote (and that they are authorized to participate in it)
2. Everyone can verify, in aggregate, that the vote count is correct — or in other words, can prove that each (anonymous) vote comes from a unique member of the public list of participants
   • This should work even for votes more complex than simple yes/no with deadline; e.g. ranked choice, percentage allocation among several choices, no deadline, can update/revoke a previously cast vote, etc.
3. A specific voter can verify that their own vote was correctly tallied
4. Nobody can prove which voter voted which way, even with the voter's cooperation (e.g. because the voter could easily lie about which vote is theirs)
5. Liquid democracy style proxies can be given a vote, and can in turn proxy to another proxy. (The proxies' votes are public, but not identified, so this is simply an adjunct system; votes for the proxy can be publicly traced to a vote for a final outcome.)
6. Can be operated by distributed services (which need to coordinate only on the topic of the vote and to share the )

I'm open to protocol suggestions other than ZKP per se; what I care about is simply the featureset above, and ZKP (as implemented by e.g. Helios Voting) is the only method I know of that satisfies them.

The problem is that all secure voting methods I've seen rely on client-side crypto (either client-managed PGP or a cryptochip ID), which is not feasible to roll out for use by normal users. I want something that everyone can use, but is still adequately secure.

Answer 1

A zero-knowledge proof is a proof of a "statement", in which one party (the prover) can convince another party (the verifier) that the statement is true, without disclosing any extra information. In Helios Voting, the protocol uses homomorphic encryption. A simplified description is the following:

• Each vote is represented as a 0 or a 1.
• The voter encrypts his vote with the "central public key".
• By the magic of the homomorphic encryption, encrypted votes can be added together: given E(v₁), E(v₂), E(v₃)..., one can compute E(v₁ + v₂ + v₃ + ...), i.e. the encryption of the sum of the votes, and that can be done without any knowledge of the private key.
• When the sum has been computed, it is decrypted, using the private key. The private key is split into several parts, and all key holders must cooperate in order to decrypt anything. If at least one of them is honest, he will refuse to participate in any decryption which is not a decryption of a sum of votes; in particular, he will prevent any decryption of an individual vote.

(Helios Voting actually uses ElGamal which is homomorphic for multiplication, not for addition, but that does not matter for this answer.)

ZKP are used here to show that the voter really encrypted a 0 or a 1, not another integer value. Indeed, a cheating user could try to encrypt, say, a 40, in order to "vote 40 times". The voter must then demonstrate that his encrypted vote is 0 or 1, not anything else, but without disclosing the actual vote. In other words, zero-knowloedge proofs support client-side cryptography. The ZKP is not "the" client-side crypto; it is an extra bit of mathematics which necessarily happens client-side, and which is merely related to the client-side encryption. This implies that if you do not want client-side crypto, the ZKP is not your primary problem; the vote encryption is.

---

If you do not want "client-side crypto" (except maybe a SSL tunnel between the client system and some server, i.e. mere transport), then any cryptography which must occur will have to occur on a server. This implies that the server to which the client is talking will necessarily learn the value of the user's vote. This is often considered a problem for voting systems: one property which is often required for voting systems is that no party other than the voter himself should be able to know the voter's vote.

However, if you are ready to tolerate that there may be some servers who can, technically, learn people's votes, but refrain from doing so (i.e. trusted servers), then your problem is solved: all you need is that the voter has a way to authenticate with one of these servers (TOTP will be handy for that), and let the server do all the required crypto magic.

Without a trusted server, and no client-side crypto, then you won't get far. Without a trusted server, you cannot tolerate that the vote value exits "as is" the voter's computer; but without client-side crypto, the vote value cannot exit the voter's computer except as a plain value immediately readable by whoever is at the other end of the connection.

TOTP is client-side cryptography, but it is not usable for anything else than authentication. Indeed, TOTP is a proof (not a ZK proof) of knowledge of some secret key, verifiable by systems who also know that key. The contents of the one-time password depend on the current time and the secret key, but not on anything else -- in particular, not on any vote value.

---

Some further notes:

• Client-side cryptography does not necessarily mean client-side storage of a private key. For client-side crypto, you need some code to run on the client computer, but that does not imply that the user must manage a key ring or something like that. In a Web-based context, code is often downloaded from a server (that's what Javascript is about...).

• In fact, a fundamental property of Internet-based system is that they are magical. By this, I mean that they do things "in the computer", which, for most people, is opaque and wizardly. As Arthur C. Clarke put it, computers are "beyond the magical horizon" of people. The average voter will not be able to verify anything about the correctness of the vote.

  This is why most votes still use paper and envelopes. People grasp paper. They can observe the vote proceedings, count the envelopes, witness their opening, and generically understand what is going on. This is what makes elections robust against attacks: many eyes.

  Under these conditions, the best that can be done in an electronic voting system is to make sure that if a fraud is attempted (by any "trusted server") then it will leave traces which will be at least potentially recoverable by knowledgeable experts. For instance, Internet-based voting in France (for French electors who do not live in France) uses a signed Java applet: that applet does the client-side crypto, and the protocol is such that as long as the applet implements it correctly, then vote values cannot be linked to voters, and the whole vote is secure and verifiable. But that's an applet: it was downloaded into the client system, and is still there, in the browser cache. And it is signed: if the applet was spiked, then it can still be decompiled (Java bytecode is not hard to reverse-engineer) and the signature will point back to the culprits. This implies that any wide-scale fraud would be likely to be discovered, or would be at least quite risky (and non-wide-scale frauds won't get the fraudster anywhere).

The French system might be a good example of what you want. Client-side crypto occurs without actual software installation (the applet mechanism is quite streamlined); conceptually, a pure Javascript version would be feasible, but we really want the code to leave traces on the client systems, with a signature so that any code alteration becomes risky. There is no storage of any secret on the client system. At the end of the voting procedure, the voter gets a receipt (which can be printed) which contains enough cryptographic information to allow for all ulterior cryptographic verifications. Voter authentication uses two automatically generated passwords obtained by mail (paper mail, not email); you could use TOTP for that, if voters have a TOTP-able device (which is your scenario).

Answer 2

As I read your question, I seemed to remember reading about numerous voting scenarios similar to that one in Chapter 6 of Applied Cryptography (Bruce Schneier). I would suggest you look in there for your answer.

Answer 3

It sounds like one question you're asking is:

"Can TOTP plus a password be sufficient to provide a zero knowledge proof"?

TOTP inherently uses a server "key" for authentication, and any privacy of that key is exposed on the server. You probably need something better than TOTP, and smarter hardware on the client side to accomplish what you need.

It also sounds like you're asking...

"How can you deploy easy to use 2 factor authentication, and re-use that technology to provide a ZKP?

All Crypto is is math. If you're deploying infrastructure that does "math",and your selection of math is TOTP, then I suspect there is something better you can use that will provide a ZKP.