Non-coercible voting with MPC operator

ln this text, I will propose an efficient non-coercible voting system with MPC process instead of an operator. It is largely motivated by MACI, however, there are also significant differences.

Design considerations

MACI has the following desirable properties:

• Soundness
• Privacy
• Non-coercibility

Soundness means that the outcome of the vote is always correct, i.e. no parties can cheat to meddle with the outcome of the vote.
Privacy means that everyone's votes are private by default.
Non-coercibility means that it is infeasible to prove how a participant voted.

Non-coercibility can not be enforced without an additional party, operator. With it, it is enforced using the ability to switch keys. My main goal will be having key-switch with minimal involvement from the operator, so it can be easily put into MPC.

I will mostly discuss the key-switch part, because "adding the votes" part is trivial in MPC.

---

We will build up from the following system which satisfies privacy and soundness, but without non-coercibility:

No key-switching system

Every user has a public key P_i, private key p_i, and a nullifier null_i = Hash(p_i).
Public keys are known and contained in some registry, zk proofs will typically use a Merkle tree of this registry.

To cast a vote, they publish the following data:
[X, Y, Z] = [enc(vote_i + | + salt), null_i, zk_i]

where
enc is an encryption with a public key of the operator
vote_i is their vote (here and further we assume that it is some kind of vector that can be added linearly)
zk_i is a zk-snark proving the following predicate: "there exists P_i in a registry such that I have corresponding private key p_i and Hash(p_i) = null_i and X = enc(vote_i + | + salt) where vote_i is a correct vote for user P_i"

Operator then must do the following: remove votes with coinciding nullifiers, decrypt and add everything up.

In principle, this system can even be made operator-less by just broadcasting votes in the open.

This system is clearly coercible, because user can reveal their vote, but it is private - if user does not reveal their vote deliberately, it remains anonymous.

---

Let's build this up to the naive key-switching system (which will still be coercible, but will the necessary intuition).

Naive key-switching

Let's define the chain of private keys as follows: p_i⁰ = p_i, p_i^k+1=Hash₂(p_i^k). Here, Hash₂ is some different independent hash function.

Now, lets modify the previous system in a following way. We will dynamically update the list of all already sent transactions on-chain (assuming here that the smart contract will just not take transactions with duplicate nullifiers).

The data in the transaction will now look as follows:

[X, X', Y, Z, W] = [enc(vote_i^k + | + salt), enc(vote_i^k-1 + | + salt₂), null_i^k, enc_{P_i}(vote_i^k + | + k + | p_i), zk_i^k]

First notable difference is that we also broadcast the encryption of the vote, concatenated with its index k, with our own private key p_i. This is necessary to guarantee that the user has an access to their own previous vote, to invalidate it in future.

The proof is also slightly more involved. There are two cases:

• either k=0, in which case the statement is the same (with trivial modifications), and an additional requirement that Z is the correct encryption of user's vote.
• or k>0, in which case it also says that there exists an already submitted transaction, Z of which decrypts via p_i into a correct vote_i^k-1 + | + k-1.

Basically, that means that a user (even anyone who has a private key) can send a new transaction which is linked to the previous one, and subtracts the previous vote before adding a new one.

The system still can function without operator if X, X' are sent as cleartext, but then the fact which votes were taken back and in what order will be clear to everyone.

This system is kind of pointless, still, because it is coercible: an adversary can require user to reveal their nullifiers null_i^k = Hash(p_i^k) (and prove in zk they are correct), and then check that no new votes in the same chain occur.

---

Now, my idea is to ensure that an adversary can not learn nullifiers. This is the only place where MPC is necessary.

Non-coercible key-switching

We will assume there is a collection of operators, with public keys O_j. I will work in 1-of-n trust assumption and n-of-n liveness assumption, but it can be modified if necessary. Denote as O = O₁ + … + O_n

Now, suppose these operators have enc_O(x + | + salt). Assume that there is an MPC protocol, which calculates some secret function F(x) (only requirements are - it is pseudorandom, and it should be easily calculatable in MPC; multiplying a point of an elliptic curve by a secret scalar will work in this context).
// Kobi calls a similar thing "oblivios pseudorandom function". Main point is that adversary will not be able to replay it, hence "oblivious".

We will also require another MPC protocol, which checks whether a secret value x belongs to a public set S.

We also denote as enc_mall some malleable encryption (with O being public key). We will use it to keep track of "double spent" votes without revealing the fact that they were double spent to an adversary.

The following modification is done to the previous protocol:

Users publish the following:

[X^k, Y^k, Z^k, D^k, Q^k] = [enc(vote_i^k - vote_i-1^k + | + salt), enc(null_i^k + | + salt₂), enc_{P_i}(vote_i^k + | + k + | p_i), D^k, zk_i^k]

Where D^k is either enc_mall(1) for k=0, or re-encryption of W^k-1 of a vote it refers to (see further).

Modification is done to zero knowledge proof to ensure formation correctness.

Now, MPC calculates F(null_i^k), and checks whether it belongs to the set of already revealed salted nullifiers (it should take logarithmic time).

The tuple [X, Y, Z, W, F] is then constructed.

In case F(null_i^k) is new, F = F(null_i^k) and W is a re-encryption of D.

In case it is a double spend, F = random well formed nullifier, and W = enc_mall(0)

This tuple is added to the list of votes.

This is good - an adversary will not be able to learn whether the vote is taken back or not.

During vote tallying, the coefficients from W are multiplied by votes, therefore removing any double spent votes and all votes derived from them.

Racing ?

It might be possible to send an adversary some information which does not include private key, yet allows them to construct a valid vote. Then, user will be forced to race an adversary.

If such attack is feasible, I suggest the cryptoeconomic mitigation, similar to private key selling: anyone who is able to submit a correct transaction should be able to steal a security deposit.

This is doable:

1. To prevent frontrun, transactions are submitted in a commit - reveal pattern: i.e., they are first committed, and then revealed in a further block.
2. The transaction can be submitted in a slashing mode, in which case it is still processed normally. In case it is accepted, the nullifier is added to the list of known nullifiers, but tx is not added to the list against which the Merkle proofs are done. Instead, it will be processed separately, just by subtracting vote_i^k-1, but not adding a new vote.
3. After the end of the voting process, the same mechanism is used to get security deposits back.

Downside if MPC suddenly drops liveness, everyone's security deposits will be locked up. I do not think this kind of attack is counterable (either here or in MACI //it exists in MACI in a similar way) without such restriction.