Explore ElGamal Key Change Mechanism

[samajammin]

Creating this issue to track previous research & development efforts.

As of 2023-10-31, work has paused on this, but we hope to return to this work soon™

Summary

In MACI protocol a coordinator, under certain circumstances, can decrypt and associate voters with their respective votes. This vulnerability could potentially expose vote details to malicious actors if the coordinator keys becomes compromised. As part of our commitment to reinforce voter privacy in MACI, we have explored incorporating elgamal encryption and rerandomization techniques into the protocol to initiate key deactivation and create new keys. This innovative approach obfuscates any identifiable link to the previously deactivated key, providing unconditional voter privacy, even from the vote-tallying coordinator.

Elgamal Key Change Mechanism

In order to achieve full anonymity, we obscure the link between the deactivated and newly generated keys via combination of ElGamal encryption, rerandomization, nullifiers, and a new zero knowledge inclusion proof. Key deactivation adds a public key to a deactivated keys set on chain. The user sends a message for key deactivation to the smart contract, signed using the key that will be deactivated. The coordinator verifies the message and adds the key, along the status to the set of deactivated keys. The user then generates a new key, leveraging a proof of inclusion of the old public key in the set of deactivated keys obscuring any connection to the previously deactivated key.

the updated protocol would now be:

1. User Registration: This is a one-time initial procedure where the user registers their original public key (signUp).
2. Public Key Deactivation: During a specified rerandomization period, the user can deactivate their current public key.
3. New Key Generation: The user then registers a new public key, based on the old, deactivated one.
4. Voting: Finally, the user casts a vote by posting a message containing their new public key.

Next Steps

We are currently finishing the key deactivation/rerandomization circuit and MACI integrations and will continue to work on the tally generation and proofs to enable voting with the rerandomized keys. This is a significant milestone in our journey towards enhancing MACI’s privacy and scalability features.

Code / Tests : https://github.com/privacy-scaling-explorations/maci/pull/708 Docs: https://github.com/0x3327/maci/blob/feat/elgamal/docs/elgamal-general.md Spec: https://github.com/0x3327/maci/blob/feat/elgamal/docs/elgamal-flow.md Writeups: https://docs.google.com/document/d/1_Q8Xg60hqdVs2YicpZNEf9-sEr0i5snu3eZnKq-R6_A/edit?usp=sharing https://docs.google.com/document/d/1ihPs5z0XjaWqmPonfIPx4kH665WvoHrvOmsj866enjs/edit?usp=sharing https://docs.google.com/document/d/1EGukRM1EYH7zE5TsEvMDLCwnb6DpygNKiQw0ChUz-1c/edit?usp=sharing

[samajammin]

Linking the PRs related to these efforts here: https://github.com/privacy-scaling-explorations/maci/pulls?q=is%3Apr+label%3A%22El+Gamal%22+

Here's the feature branch (feat/elgamal): https://github.com/privacy-scaling-explorations/maci/tree/feat/elgamal

Specifically #718, #696, #695, #694, #694, #686, #684, #670

Eventually when we return to this work, we should break up this epic issue into more concrete issues 😄

[samajammin]

Relevant presentation: https://www.youtube.com/live/X54LaXfJTn4?si=rWsbmvbYFnlerF_z

[ctrlc03]

Closing this issue as the work has been superseded by the new https://3327.io grant work described here #1566. Follow the public board https://github.com/orgs/privacy-scaling-explorations/projects/40/views/20 for updates