GitHub branch checks state

Egk Elliptic Curves Mixnet

last update 08/09/2024

Implementation of a mixnet using the ElectionGuard Kotlin Elliptical Curve library, and the Verificatum library. The mixnet uses the Terelius / Wikström (TW) mixnet algorithm, see egk mixnet maths for details. Note that paper's timings use the older integer group; the elliptic curve group is much faster.

This is part of VotingWork's cacvote project. It is not part of the ElectionGuard specification per se, but follows the ElectionGuard 2.0 specification wherever possible.

The implementation for Elliptical Curves (EC) is derived from the Verificatum library, including the option to use the Verificatum C library. See VCR License for the license for this part of the library.

Note that the EC implementation is not stable and may change in the future. However, other than different build instructions, this should not affect the API.

Also see: Workflow Notes

Egk Elliptic Curves Mixnet

Timing

Encrypting a ballot with 12 contests and 4 selections each (total of 60 encryptions) takes about 6 ms per ballot, using pre-computed tables for "fixed base acceleration". This does not appear to be using Montgomery forms for fast mod operation.

Mixing 1000 ballots of width 34 takes ~ 17 secs single threaded with good parallelization. Verification is 30-50% slower than the shuffle and proof, see plot.

Size

We use "point compression" on the elliptic curve ElementModP, so we only serialize the x and "sign of y" coordinates, giving a storage reduction of O(64/33) compared to serializing both coordinates, and O(512/33) compared to the integer group. To estimate the computational cost of storing just x and recomputing y: BallotReader reads 1000 ballots (width 34) in 235 msecs. If one computes y instead of reading it, it takes 1274 msecs. So, cost is ~ 1 sec for 34000 texts everytime you have to read the mixed ballots.

Currently we store the ballots in binary and the proofs in json in base64. For very large mixnets, you might want to store proofs as efficiently as possible, which argues for a protobuf option.

readMixnetBallots from working/public/mix1/Shuffled.bin nrows = 1000 width=34
BallotReader took 2352 msecs = .006917 msecs/text (340000 texts) = 235.2 msecs/trial for 10 trials
BallotReaderAlt took 12744 msecs = .03748 msecs/text (340000 texts) = 1274 msecs/trial for 10 trials

Download

cd <install-dir>
git clone https://github.com/JohnLCaron/egk-ec-mixnet.git
cd egk-mixnet

Build

Prerequisites: Java 21

To build the code:

./gradlew clean assemble
./gradlew uberJar

Rebuild

If the library has changed and you need to update it:

cd ~/dev/github/egk-ec-mixnet:
git fetch origin
git rebase origin/main

Then rebuild the code:

./gradlew clean assemble
./gradlew uberJar

Build the Verificatum C library using GMP (optional)

Follow the instructions in Egk-ec Getting Started

This is needed for good performance.

Complete Workflow for testing

~/dev/github/egk-ec-mixnet:$ ./scripts/completeWorkflow.sh working

Runs a complete test of the workflow and writes the output to whatever you set working to.

After running, examine the log file at egkMixnet.log.

Encryption Workflow for testing

Note that election_initialize.sh uses a manifest from src/test/data/mixnetInput. Change that to the correct manifest if needed.

You might want to first delete the log file at egkMixnet.log.

~/dev/github/egk-ec-mixnet:$ ./scripts/encryptionWorkflow.sh working

Runs a test of the encryption workflow and writes the output to whatever you set working to.

After running, examine the log file at egkMixnet.log.

Workflow components

electionguard

election-initialize.sh

Uses src/test/data/mixnetInput/manifest.json for the egk manifest. (Change in election-initialize.sh if you want)
Creates an egk configuration file with default election parameters. (Change in election-initialize.sh if you want)
Runs the egk keyceremony to create private egk directory.
Copies the public egk files to the public mixnet directory.

generate-and-encrypt-ballots.sh

Generates random plaintext ballots from the given manifest, and writes their encryptions to the public mixnet directory.
This is the main functionality that needs to be implemented by the election voting system. Likely the voting system will write the plaintext ballot to disk and call RunEncryptBallot.main() with appropriate parameters.

eg-tally.sh

Homomorphically accumulates digital ballots into an encrypted tally.

eg-tally-decrypt.sh

Uses trustee keys to decrypt the tally.

eg-verify.sh

Runs the egk verifier to do electionguard verification.

mixnet

mixnet-shuffle.sh

Shuffles the ballots using two shuffling phases, writes to the public mixnet directory.

mixnet-verify.sh

Runs the verifier on the mixnet proofs.

cacvote

table-mixnet.sh

From the last mix's ShuffledBallots, generate table of decrypted (K^sn) serial numbers and proofs.
This table is written to _working/public/decryptedsns.json.

table-pballot.sh

Simulate a table of paper ballot serial numbers and their physical locations.
Pass in "--missingPct percent" to simulate some percent of paper ballots were not received.
This table is written to _working/public/pballottable.json.

pballot-decrypt

From a paper ballot's serial number (psn), find the corresponding shuffled ballot and decrypt it.
Place decrypted ballot into _private/decryptedballots/ directory.
Use psn as the decrypted ballot id, and the filename is dballlot-psn.json.

verify-decryptions

Verify the proofs in the decrypted serial numbers (decrypted_sns.json).
Verify the decrypted ballot proofs.
If digital copies of the paper ballots are available, compare the ballot decryptions to the originals.

Directory file layout (strawman)

working/public
  encrypted_ballots/
    device1/
      eballot-id1.json
      eballot-id2.json
    device2/
      eballot-id1.json
      eballot-id2.json
    ...
  mix1/
    mix_config.json
    proof_of_shuffle.json
    ShuffledBallots.json
  mix2/
    mix_config.json
    proof_of_shuffle.json
    ShuffledBallots.json
  mixN/
    ...

  constants.json
  election_config.json
  election_initialized.json
  encrypted_tally.json
  manifest.json
  tally.json

  decrypted_sns.json
  pballot-table.json

working/private 
  input_ballots/ 
    pballot-id1.json
    pballot-id2.json
    ...
  trustees/
    decrypting_trustee-name1
    decrypting_trustee-name2
    ...
  decrypted_ballots/
    dballot-sn1.json
    dballot-sn2.json
    ...

JohnLCaron / egk-ec-mixnet

readme