Real-world election systems rarely fit the standard cryptographic model of a single list of ciphertexts encrypted under one public key. In practice, ciphertexts may need to remain grouped by precinct or municipality, different groups may use different encryption keys, and shuffling may be combined with partial decryption or secret exponentiation.
MAYAsk — MAYA Swiss-Knife — is the extended construction that accommodates these settings while preserving the properties of the base protocol. Specifically, it gives logarithmic-size arguments for block-respecting shuffles, shuffles of ciphertexts encrypted under different public keys, shuffles combined with partial decryption using a mixer’s secret-key share, and shuffles combined with secret exponentiation of selected ciphertext components. In all cases the resulting arguments retain logarithmic size in the number of ciphertexts, require a transparent setup, and have verification dominated by a single multi-scalar multiplication.
Extensions
Block permutations. Proves that ballots are shuffled strictly within their designated blocks — municipalities, precincts, or ballot styles — without crossing boundaries. Blocks may be uniform or of differing sizes.
Multiple keys. Supports federated settings where different districts encrypt ballots under entirely independent public keys.
Shuffle-and-exponentiate. Allows a mixer to apply a publicly anchored
secret exponentiation during the shuffle, as required by oblivious PRF
evaluation, plaintext-equivalence tests, and the DbleMixExp operation of
recent Swiss Post proposals.
Decryption mixnets. Enables each mix server to verifiably strip a layer of encryption while shuffling, removing the need for a separate decryption phase. Threshold key sharing is fully supported.
All four preserve MAYA’s $O(\log n)$ proof size. Adding block structures or multiple keys incurs essentially zero overhead compared to the base protocol; the decryption mixnet adds about 7% to multi-threaded prover time, and shuffle-and-exponentiate carries a moderate overhead from its extra exponentiation and doubled ciphertext count.
The paper is not yet publicly available. It will be linked here once it is.
Performance
| Scenario | n | Prover (s) | Verifier (s) |
|---|---|---|---|
| Π1: Uniform blocks, single key | |||
| 1k × 20 | 20k | 1.3 / 3.9 | 0.33 / 0.97 |
| 1k × 80 | 80k | 5.6 / 15.4 | 1.3 / 3.9 |
| 1k × 320 | 320k | 22.2 / 62.3 | 5.1 / 14.5 |
| 10k × 20 | 200k | 13.9 / 38.4 | 3.2 / 9.7 |
| 1 × 200k (MAYA) | 200k | 13.2 / 39.7 | 3.1 / 9.1 |
| 10k × 80 | 800k | 55.5 / 165.8 | 12.7 / 38.8 |
| 100k × 20 | 2M | 138.3 / 391.5 | 31.5 / 97.1 |
| Π2: Heterogeneous blocks, single key | |||
| 1k × [50, 150] | 200k | 13.5 / 44.4 | 3.1 / 9.1 |
| 20k × [2, 3, 5] | 200k | 13.7 / 44.4 | 3.1 / 9.2 |
| 80k × [3, 7] | 800k | 54.8 / 159.7 | 12.6 / 39.7 |
| Π3: Multiple keys | |||
| Key 1: 1k × [37, 63] Key 2: 500 × [149, 14, 37] | 200k | 13.2 / 38.6 | 3.2 / 10.4 |
| Key 1: 10k × [5] Key 2: 3.5k × [3, 7, 10] Key 3: 20k × [2, 2] | 200k | 13.7 / 40.23 | 3.1 / 9.75 |
| Keys 1–100: 1k × [2] | 200k | 13.6 / 40.19 | 2.3 / 9.68 |
| Π4: Decryption mixnet (one mixer) | |||
| 10k × 20 | 200k | 14.9 / 45.0 | 3.1 / 9.6 |
| Π5: Shuffle-and-exponentiate (DbleMixExp) | |||
| 5k × 20 | 200k | 8.9 / 27.6 | 2.5 / 7.2 |
| 10k × 20 | 400k | 19.5 / 55.1 | 5.0 / 14.4 |
Table 1. Performance of the MAYA extensions for a shuffle of n ciphertexts. Timings are measured end-to-end and in seconds as MT / ST. B × b: B blocks (e.g., districts) of b ciphertexts each. B × [b1, b2, …]: B groups, each partitioned into sub-blocks of sizes bj. For Π3, each entry describes an entity operating under an independent key with its own block structure. For Π4, we report one mix server’s shuffle-and-partial-decryption step. For Π5, n = 2Bb since each entry produces two ciphertexts (one per key).
All variants were implemented in Rust on top of the MAYA reference
implementation, using curve25519-dalek over Ristretto255 at 128-bit security
with folding factor k=4, on the hardware described on the
home page. Timings include all
cryptographic operations, CRS regeneration, and disk I/O.
The source code for all four extensions is at uclcrypto/maya_extensions, which is also the current MAYA implementation. See the Changelog.
Proof sizes remain logarithmic across all variants. At n = 200,000 the measured sizes are 6,176 bytes for the single-key variants Π1 and Π2; 6,272 bytes for two keys, growing by 96 bytes per additional key up to 15,680 bytes for 100 keys (Π3); 6,224 bytes for Π4; and 6,320 bytes for Π5. At n = 2,000,000 the Π1 proof is 7,328 bytes.