A vote-buying attack prevention tactic in MACI

This idea comes from Kirill here: https://forum.clr.fund/t/making-contributions-to-a-funding-round/22/29

We would like to prevent the first-message vote-buying attack in MACI which looks like this:

1. Eve promises Alice a bribe and gives Alice a public key pk. Eve knows the corresponding private key sk.
2. Alice signs up to MACI using pk.
3. The signup period ends and the voting period starts.
4. Eve uses sk to vote for her preferred options and pays Alice the bribe.

The tactic which helps to prevent the attack is as such:

1. Eve promises Alice a bribe and gives Alice a public key pk. Eve knows the corresponding private key sk.
2. Alice signs up to MACI using pk.
3. The signup period ends and the Special Coordinator Key-Change Period ("special period") starts.
4. Alice sends the coordinator (Charlie) a key-change message.
5. Charlie checks the message and sees that it is only a key-change message. Charlie publishes this message. The contract accepts Charlie's transaction and nobody else's during this period.
6. The special period ends and the voting period starts.

Questions from WJ:

1. What if Alice doesn't have sk? Without it, she can't sign the key-change message.

Nonetheless, if there is a default UI which generates the keys, this method is still useful as most users will use it and will have access to their sk. A briber would have to force the victim to use an alternative UI, interact with the MACI contract directly, or use some other means to execute the attack.

Double key signature?

If we assume that the user won't share their ethereum private key, can we use that assumption to prove the knowledge of the EdDSA private key?
For example, if a user has an Ethereum private key K1 and EdDSA private key K2, is it possible to compute something like a signature which would require both private keys: P(K1, K2)?
So if the briber would know only K2, he wouldn't be able to produce a valid signature for sign-up and will be forced to reveal K2 to the user.

1. Alice has an Ethereum private key K1
2. Eve wants Alice to sign up with EdDSA private key K2. But Eve doesn't want Alice to know K2. How can we prevent Eve from succeeding?

Attempt 1

1. Alice has K1. We assume that Alice never shares K1 with anybody.
2. Alice generates an EdDSA secret key K2. The public key is P2. We assume that the coordinator cannot know K2, or they could cast fraud votes.
3. Alice signs some data d using K2: eddsa_sig = eddsa_sign(K2, d)
4. Alice signs hash(ecdsa_sig) with K1: ecdsa_sig = ecdsa_sign(K1, eddsa_sig)
5. Alice sends ecdsa_sig, eddsa_sig, and P2 to the coordinator.
6. The coordinator runs (off-chain):

alice_address = ecrecover(hash(eddsa_sig), ecdsa_sig)
valid = verify_eddsa(eddsa_sig, P2, d)

Now the coordinator knows that Alice knows K1. But Eve could have asked Alice to hash and sign eddsa_sig. So the coordinator can't tell whether Alice really knows K2.

A big piece of the problem is that Alice cannot directly share K2 with the coordinator, and Eve could give Alice something to sign with K2.