1
$\begingroup$

Assume a voting with delegates, where each delegate's vote $v_i \in \{-1,1\}$ has a certain weight $w_i$ depending on the number of people who elected the delegate.

Is there a way to calculate the sum of votes $\sum_{i} v_i w_i$ without revealing $w_i$?

$\endgroup$
1
$\begingroup$

One approach might be the usage of a homomorphic cryptosystem like the Paillier cryptosystem, while the specific protocol properties depend on your use case.

For more detailed description of Paillier system, I refer to https://de.wikipedia.org/wiki/Paillier-Kryptosystem and limit my answer to a possible protocol application to achieve your goal.

Due to the homomorphic properties of the Paillier system, we are able to:

  1. Add different plaintext by multiple their ciphertexts $Dec_k(Enc_k(m_1,r_1) \cdot Enc_k(m_2, r_2))= m_1+m_2 \mod n$
  2. Multiply an encrypted plaintext by raising the ciphertext to $k$: $Dec_k(Enc_k(m_1,r_1)^k) = k \cdot m_1 \mod n$

As an example let us assume the following setup:

  • Common party $C_1$ knows all weights $w_i$ and calculates the result $\lambda=\sum_i v_i w_i$ without knowing the delegates votes
  • Common party $C_2$ generates the private and public keys for the Paillier encryption.
  • Each delegate shares an encrypted and authenticated channel with each common party.

In the interests of simplification, I neglect the method, how to achieve this secure channel. You can use a protocol for authenticated key exchange and an and for transport security of your choice to achieve the confidentiality and integrity of the messages.

Now we can define the protocol as follows:

$C_2$ generates one key pair for this election and sends the public key to all delegates.

  1. $ C_2\xrightarrow{k_{pub}}Delegate_i$

$D_i$ Encrypts its vote with the public key and send it to $C_1$. Since $C_1$ does not know the secret key, it gains no knowledge over the delegates vote.

  1. $ D_i\xrightarrow{\overline{v_i}=Enc_{k_{pub}}(v_i)}C_1$

$C_1$ can weight each vote by raise the encrypted vote to the power of $w_i$ and calculate the election result $\lambda$:

3.1 $Enc_{k_{pub}}(w_i \cdot v_i) ={\overline{v_i}}^{w_i}$ (2. homomorphic property mentioned above)

3.2 $\overline{\lambda}=\prod_{i} {\overline{v_i}}^{w_i} = \prod_i Enc_{k_{pub}}(w_i \cdot v_i) = Enc_{k_{pub}}(\sum_i w_i \cdot v_i)$ (1. homomorphic property mentioned above)

$C_1$ send the result to $C_2$

  1. $ C_1\xrightarrow{\overline{\lambda}}C_2$

$C_2$ can decrypt it and publish the election result:

  1. $\lambda = Dec_{k_{priv}}(\overline{\lambda})$

This approach is a common application of shared knowledge: The common party $C_1$ knows the weights and can compute the result without knowing the votes, while all other parties have no knowledge over the weights. There are, of course, many other ways to achieve your goal, e.g. encrypt the weights and raise them by the delegates vote, but I hope, the concept has become clear.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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