How can I distribute a set of anonymous tokens digitally among a known limited population to do anonymous voting?

Question

TL:DR

How can I give a population of N people the chance to randomly pick one token each person guaranteeing those:

• Nobody knows noone else's token.
• Noone can pick more than one token.
• Every person may choose to pick a token or not.

So for N people, after the time window there are M picked tokens and N-M tokens left without picking and each participant has either 0 or either 1 token under his power.

Here the keypart is that "nobody else" does not only refer to the N-sized population allowed to vote but also includes "the organizers". For example identifying in a web and creating a random token could potentially result in a gray-hat sysadmin to log "who picks which token" and this violates the rules.

Details

We did this with the help of "physical paper". But I don't know how to emulate this digitally.

See the story: we regularly conduct anonymous polls within certain groups of people and the results are agreed to be binding. Say those people are for example employees discussing about auto-organization within a company. Or shareholders in a society that decide about a capital-raise. Or bosses in a family-held company deciding to fire one member of the family.

Because of the types of the questions, imagine we need confidentiality on the opinion of every single member. Still we need transparency and everyone know that the result has not been cheated.

The method we currently use allows these rules:

• Voters MUST be identified (much like in a real government election) to participate (closed cesus).
• Every participant MAY vote or not.
• Every participant MAY vote more than once to change their mind and change the previous vote.
• Every participant MUST NOT discover what other teammates voted unless the other party discloses his vote. This includes "even if Alice has friends in the system" she cannot discover what Bob voted.
• Every participant MUST be able to audit his own voting into the contribution total.

It's a closed census so the number of participants is limited and known at any given time.

How we did this during years?

For the sake of the example imagine this silly poll:

"Should we do a strike?"

• Yes, ASAP
• Yes, but first we need to clarify about the salary raise
• No

Every one of the 100 employees want to express their opinion, but they don't want the teammates to know their real opinion. They'll just fullow the strike if yes, and go to work if not.

How we did until now:

Tokenization part

1. We generate 100 random tokens and publish cyphered under private key.
2. We printed 100 random tokens in 100 separate papers and put them into an envelopes. One person holds the 100 envelopes.
3. Employees are given two time-windows (say "during today") to go and pick his token and "during today and tomorrow" to cast the vote.
4. Every employee chooses to go and pick one or not.
5. The first one goes and identifies. After identification is offered the set of 100 envelopes. The employee is enabled to shuffle if he wants. Then he picks a random one.
6. The second one goes and identifies. After, he is offered the 99 reminding envelopes and he picks one.
7. If all the the employees go to pick one, there will be 100 names in the identification registry and 0 reminding envelopes. Each employee may use it or not.
8. If any employee does not pick the envelope within the time window (say 85 picked and 15 did not pick) there will be 85 names in the identification list + 15 reminding tokens open.
9. After the timewindow is ended, we close the physical reminding envelopes.

Voting part

1. At this point every employee has a token who nobody else knows.
2. In a web they use the token as the "voter ID"
3. During the time-window, any voter-ID may re-cast the vote and the last one is the valid one.
4. After the voting time-window the poll is closed and nobody can cast a vote even if having a never-used paper-token.

Results part

1. After the voting is closed, the reminding tokens not used are open and introduced in the system.
2. The public key with respect the list of 100 tokens is disclosed and every person can decypher it, so now everyone knows "exactly" the 100 tokens issed initially and will recognize both the 15 non-picked tokens in that list and his own token.
3. The results are published in the form of a table with 2 columns: Token + Voting result

Therefore the result is something like this:

ATDER7 - Was not picked.
Z887OP - Picked, but did not cast a vote.
83KIER - Voted "Yes, ASAP"
UE87JY - Voted "Yes, ASAP"
IEOP91 - Voted "No"
[... list all tokens and results ...]
23GXQW - Was not picked.
87OKID - Voted "Yes, but first we need to clarify about the salary raise"

This guarantees that every employee can tell "yes, MY VOTE is in there contributing to the result" and every employee knows he's not cheated.

After that the "winner" option is taken as the rule and everybody agrees "this was the popular sentiment".

Big question

How can we replace the "token-assignation part" that we did with paper with a fully-digital result mechanism without composmising that the rules (ie: noone can pick 2 tokens, or even the system administrator may not know "who voted what", etc.).

Answer 1

Each voter generates their own EC key pair.

Each voter registers to vote by submitting their public key along with their real-world identity.

The set of all public keys registered to vote is shared with all voters.

To vote, each voter signs a message such as "Yes, ASAP" with a linkable ring signature, including all other registered voter public keys as other members of the ring.

Each linkable ring signature declares a "key image" as part of the signature. The key image is unique to the real signer, but no outside observer (without knowledge of the real signer's private key) can tell which ring member public key the key image belongs to.

The way key images work is that if the signer signs another message to submit another vote, they cannot avoid being forced to declare the same key image again with the signature (otherwise the signature will not verify).

Now, it's easy to see if anyone votes more than once, and to discard earlier votes if the voter recasts their vote (because the same key image will appear more than once). It's also easy to see how many unique key images have been submitted, and therefore how many unique voters voted.

All votes submitted can be shared with all participants, so that the signatures can be publicly verified and signed messages examined.

For future votes, only new participants need to register to vote. Then, the public keys of the new participants are distributed to all existing voters. Existing participants will use their existing key pairs to vote in future elections.

Note that since the same key images will appear in future elections, it will be possible to see how the same person voted across many elections (although no one will be able to know the real-world identity of any voter).

If this is undesirable, you should ask all participants to register fresh public keys for each new election. They can do this by simply submitting a fresh public key, and signing it with their old public key. The key image for the new public key will not be able to be linked to the key image of the old public key, so the re-registration submissions can be made public.