Elastic Poll

Elastic poll is a web app that allows organizing single-choice and multi-choice polls that combine privacy and universal verifiability with the help of applied cryptography.

The polling process consists of 4 stages: specifying a poll, selecting participants, submitting votes and tallying results. Because of serverless nature of the app, there is no tamper-proof bulletin board available to all participants where these stages are performed. As such, participants need to use an external bulletin of their choosing. A Telegram group or a Slack channel should do at least for toy use cases (a paranoid option would be a public blockchain). The app does provide reference values allowing to understand whether the necessary data is synced among participants.

Voting

The app uses ElGamal encryption to encrypt votes. A Boolean vote (i.e., 0 or 1) is encrypted separately for each option for the shared tallying key (see below how this key is constructed). The app uses Ristretto255, a prime-order elliptic curve group obtained by transforming Curve25519, as a prime-order group underpinning ElGamal encryption.

Together with the option ciphertexts, a vote contains a zero-knowledge proof that each of them encrypts 0 or 1; this proof is based on Borromean ring signatures by Maxwell and Poelstra, repurposed to work on ElGamal ciphertexts instead of public keys. See RingProof docs from the elastic-elgamal crate for more technical details how this proof is constructed and verified.

For single-choice polls, the vote additionally contains a zero-knowledge proof that exactly 1 option is selected, i.e., the option ciphertexts sum up to a ciphertext of 1. This is a standard discrete log equality proof (aka Chaum–Pedersen protocol). For multi-choice polls, this proof is not necessary.

ElGamal encryption is additively homomorphic; the sum of ciphertexts for the same public key encrypts the sum of the corresponding plaintexts for the same key. As such, vote tallying is straightforward – the ciphertexts are added for each option and then decrypted, allowing to restore the number of votes submitted for each option. It is possible to prove the validity of decryption without disclosing the (private) decryption key. Indeed, it suffices to provide a single group element – the result of the Diffie–Hellman exchange between the decryption key and the random group element from the ElGamal ciphertext. The validity of this element can be proven via a standard discrete log equality proof.

Participants

All participants are simultaneously both voters and talliers. A participant can skip voting, but cannot skip tallying (i.e., involvement of all talliers is required to determine final results). If any tallier refuses to cooperate, the poll is stalled indefinitely.

Such design is motivated by 2 factors:

• Simplicity of initialization: N-of-N tallier scheme is significantly easier to initialize than a generic M-of-N scheme. The latter would require performing a verifiable secret sharing or distributed key generation protocol.
• Strong privacy guarantees: It is impossible to decrypt any separate vote without the voter’s consent.

Each participant has a Ristretto255 keypair to sign their votes (i.e., prove that the vote comes from an eligible voter), and to submit a tallying share. Tallying shares do not need additional authentication since they contain a sufficient zero-knowledge proof of authenticity.

When combined, shares from all participants (and no less than all participants!) would allow to decrypt vote results. The shared public key used to encrypt votes is the simple sum of all participants’ public keys. Correspondingly, tallying shares (i.e., a vector of Diffie–Hellman combinations of the participant’s private key with the random elements of all the tallied option ciphertexts) are combined by summing as well. To prevent rogue key attacks, a participant application contains, along with a public key, a zero-knowledge proof of ownership of the corresponding secret key.