MAYA: A Short Shuffle Argument With Fast Verification

Authors: Thi Van Thao Doan, Olivier Pereira, and Thomas Peters

Affiliation: UCLouvain, B-1348 Louvain-la-Neuve, Belgium

Published at: 33rd ACM Conference on Computer and Communications Security (CCS'26), to appear.

Abstract

Shuffle arguments dominate the audit data in end-to-end verifiable elections when homomorphic tallying is not applicable. Deployed mixnets in countries like Australia, Estonia, Israel, Norway, Spain, and Switzerland produce proofs that scale linearly, reaching gigabytes for millions of ciphertexts. MAYA achieves O(log n) communication complexity with a transparent setup requiring no trusted parameters.

Download

Download PDF

Citation

@inproceedings{maya2026,
  title     = {MAYA: A Short Shuffle Argument With Fast Verification},
  author    = {Doan, Thi Van Thao and Pereira, Olivier and Peters, Thomas},
  booktitle = {Proceedings of the 2026 ACM SIGSAC Conference on Computer
               and Communications Security (CCS '26)},
  publisher = {ACM},
  year      = {2026}
}

Key Contributions

  1. Computational parameter optimization (k=4 folding factor)
  2. Iterative padding with bounded overhead
  3. Aggregated argument batching (1.5x reduction in recursive prover time)
  4. Bridged consistency for aggregated commitments
  5. Production-scale evaluation on Ristretto255 and P-256

The performance figures shown on this website (see the home page) are better than those reported in the CCS ‘26 paper. The protocol itself is unchanged; the improvements come from implementation optimizations made after the paper was written.