Verifiable proof of shuffle for anonymous voting

[Prathyushmnchla]

There are 3 main approaches to on chain voting anonymity. In my understanding this how each works.
I could be wrong as I am just learning. But it initiates the conversation

1. Homomorphic encryption.

Users submit encrypted votes with proof of validity. It is sent to group of trusted authorities.

The trusted authorities compute the requisite function using addition and multiplicative structure of underlying cryptographic primitives. The authorities then decrypt it. In my understanding so far it requires a group of trusted parties to decrypt.
If any one authority does not follow the protocol the decryption cannot happen. And if all authorities collude votes are revealed.
You can complement it with threshold signatures but I don't know the details.

2. Ring signatures.

Ring signatures allow for signatures where you cannot Identify which signee signed it.
It is spontaneous and requires no setup. You user can pick any signatures and generate a ring signature.
You can further implement linkability and tag linkability, and traceability functions.
(not strictly necessary for ring signatures)

• Linkability allows for seeing if the same user signed the same message twice.
• Tag linkability allows to reveal votes if two messages were sent on the tag.
• Tags allow for issue based anonymity,
• Traceability allows for tracing the public key under certain specific conditions(not sure exact)

There are 2 attack vectors, if the blockchain start accepting ring signatures it becomes vulnerable to ddos attacks, because ring signatures take time to verify and anonymity prevents easy checking against a ledger with funds.

If the block chain does not accept ring signatures, then user must submit the signature using his private key and anonymity is lost.

Traceable Ring Signature

3. Private key shuffling.

This takes as input a set of public keys and anyone can take the keys and generate a new shuffle.

The shuffler submits a valid non interactive proof of shuffle, which can be verified on chain
(or in principle can be challenged on chain if compute cost is a problem)

After a number number shuffles, the user can sign with anonymized keys.

Efficient Zero-Knowledge Argument for Correctness of a Shuffle
MixEth: efficient, trustless coin mixing service for Ethereum

4. Shuffling in my opinion is the better approach. You can build ring signatures after verifiable shuffling of signatures for using features like tag linking.
   Main reasons are,

• The setup is highly interactive. If any one does not trust all previous shufflers, they can shuffle themselves.
• You can build other structures on top this such a tag likability and homomorphic encryption.
• the code can be easily modified for k-anonymizing transactions
• The governance wallet can transfer funds to the anonymized addressed and the anonymized addresses can spend on governance related tasks.
• (an alternative proposed was one time use submission keys built natively into Rchain, that can work well with such shuffling protocol.)

These are all expensive computations, works for atleast small groups.

[Prathyushmnchla]

One of the draw backs of shuffling is that, you have to redo it when you remove users.

Addition is not a major issue I believe.