2
$\begingroup$

I have a group of $n$ people (say small constant). Each person votes for $A$ or $B$, and we want to know who won without knowing each individual's vote. How would one design a scheme for this?

  • My first idea was to use commitment scheme for everyone's input and open after, which obviously doesn't work since we know each person's vote afterwards.

  • Second idea is to have first person generate a large number and multiply by either $p$ or $p^2$, where $p$ is a random prime, and pass this along to the next (until the last person who reveals total, and first person will open commitment of the og number). This runs into the issue where either you have to commit each $p$ anyway or you can't publicly factor the resulting number.

  • Third idea is to assume MPC (which might even be too complicated for this) and compute the sum of inputs. Still doesn't quite work since a cheating voter can just input 2 instead of 1.

I'm not sure if there's some simple solution to this, or if someone can point me to some resources discussing this?

$\endgroup$
4
  • 2
    $\begingroup$ Securing votes is a typical MPC problem. So, if you search for it, you should find a lot of related work. I should start off by describing your requirements. For example, I'm not sure if you will allow a third trusted party, as you are considering in your 'second idea'. $\endgroup$ Commented Jun 8 at 15:33
  • $\begingroup$ no third party; that would be too easy.. (i don't think second idea had mention of third party) $\endgroup$
    – adbforlife
    Commented Jun 9 at 5:14
  • $\begingroup$ Look at the Helios that is the top most system that cryptographer's uses on their conference voting. $\endgroup$
    – kelalaka
    Commented Jun 9 at 8:10
  • $\begingroup$ For the MPC approach, you would have to use verifiable MPC, which can protect against malformed inputs. $\endgroup$
    – K.G.
    Commented Jun 9 at 12:26

3 Answers 3

1
$\begingroup$

This is known as boardroom voting.

Kulyk et al seems like a useful starting point.

Plain MPC could obviously be used for this, but in practice you often want a bit more (verifiability by outsiders, for example), so you would want to use more complicated MPC. In practice, a more bespoke protocol will probably make more sense.

Example: The simplest protocol I know, when you have a broadcast channel, is an ElGamal-based protocol. Consider first passive security.

  1. Each voter computes $y_i = g^{a_i}$ and broadcasts $y_i$. Once everyone has broadcast, the public key is $y = \prod_i y_i$.

  2. Then everyone encrypts their vote as $x_i = g^{r_i}$, $w_i = y^{r_i} v_i$ and broadcast $(x_i,w_i)$.

  3. Everyone computes $x = \prod_i x_i$, $w = \prod_i w_i$ and $z_i = x^{-a_i}$, and broadcast $z_i$.

  4. Finally, everyone computes $v = w \prod_i z_i = \prod_i v_i$. If we encoded YES as g and NO as 1, then the election outcome is $\log_g v$.

For active security, you add the usual NIZK arguments. You may also have to add a few commit-open rounds with an extractable commitment scheme (easy in ROM) to make the security proof go through, but I am not sure that you need that.

The transcript of the actively secure protocol is publicly verifiable.

If the broadcast channel is not authenticated, add signatures to taste.

$\endgroup$
3
  • $\begingroup$ I did have trouble with the bit about malicious adversaries. So under example scheme or others, would you essentially need to prove a statement of the form "there exists a value that is either 0 or 1 that makes my action legitimate"? And translate this to 3SAT and use the NIZK for NP problems? (I'm ok with NIZK being not proven secure or use interactive is fine too) $\endgroup$
    – adbforlife
    Commented Jun 11 at 3:44
  • $\begingroup$ of course, it would be great if there's a simpler ZK scheme for dealing with malicious $\endgroup$
    – adbforlife
    Commented Jun 11 at 3:47
  • $\begingroup$ @adbforlife No, you would not use generic NIZK. You have an efficient NIZK proving that something is an encryption of 1. (Pedersen's equality of d.log. proof.) That allows you to prove that something is an encryption of any message, since ElGamal is group-homomorphic. And then or-proofs for sigma protocols allow you to prove that something is an encryption of one of some specific set of messages. Likewise, there are efficient NIZKs to prove that you know your key material and that you have used it correctly. These are all very practical NIZKs. $\endgroup$
    – K.G.
    Commented Jun 11 at 9:35
1
$\begingroup$

As Mr fgrieu would testify, vote on paper or use coloured stones. SQL that...

$\endgroup$
0
$\begingroup$

Each voter creates a key pair, and announces their public key.

Each voter then signs a message containing their vote, using a Linkable Spontaneous Anonymous Group Signature.

An LSAG signature proves that the signature came from one of the announced public keys, but it is impossible to know which.

Because it is "linkable", a "linkability tag" is published as part of the signature. The public are unable to associate the tag with a particular public key. However, the signature mechanism forces the signer to announce the same tag every time they sign (otherwise the signature will not verify).

This means that it is not possible for any key pair to sign more than one vote without being detected.

Note that the votes should be submitted through an anonymous channel, to prevent the vote from being correlated to the voter via IP address or other means.

$\endgroup$
1
  • 2
    $\begingroup$ You should mention that this requires anonymous channels. In my experience, people find it easier to reason correctly about the "explicit cryptography" approach than the anonymous channel+blind signature approach. Anonymous channels are hard to implement and their properties often interact non-trivially with the voting protocol's security requirements. $\endgroup$
    – K.G.
    Commented Jun 9 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.