Paper 2024/1503

Scalable Mixnets from Mercurial Signatures on Randomizable Ciphertexts

Masayuki Abe, NTT (Japan)
Masaya Nanri, Kyoto University
Miyako Ohkubo, National Institute of Information and Communications Technology
Octavio Perez Kempner, NTT (Japan)
Daniel Slamanig, Universität der Bundeswehr München
Mehdi Tibouchi, NTT (Japan)
Abstract

A mix network, or mixnet, is a cryptographic tool for anonymous routing, taking messages from multiple (identifiable) senders and delivering them in a randomly permuted order. Traditional mixnets employ encryption and proofs of correct shuffle to cut the link between each sender and their input. Hébant et al. (PKC '20) introduced a novel approach to scalable mixnets based on linearly homomorphic signatures. Unfortunately, their security model is too weak to support voting applications. Building upon their work, we leverage recent advances in equivalence class signatures, replacing linearly homomorphic signatures to obtain more efficient mixnets with security in a more robust model. More concretely, we introduce the notion of mercurial signatures on randomizable ciphertexts along with an efficient construction, which we use to build a scalable mixnet protocol suitable for voting. We compare our approach to other (scalable) mixnet approaches, implement our protocols, and provide concrete performance benchmarks. Our findings show our mixnet significantly outperforms existing alternatives in efficiency and scalability. Verifying the mixing process for 50k ciphertexts takes 135 seconds on a commodity laptop (without parallelization) when employing ten mixers.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Equivalence Class SignaturesMercurial SignaturesMixnetsVotingAnonymity
Contact author(s)
msyk abe @ ntt com
nanri masaya 26n @ st kyoto-u ac jp
m ohkubo @ nict go jp
octavio perezkempner @ ntt com
daniel slamanig @ unibw de
mehdi tibouchi @ ntt com
History
2024-09-30: approved
2024-09-25: received
See all versions
Short URL
https://ia.cr/2024/1503
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1503,
      author = {Masayuki Abe and Masaya Nanri and Miyako Ohkubo and Octavio Perez Kempner and Daniel Slamanig and Mehdi Tibouchi},
      title = {Scalable Mixnets from Mercurial Signatures on Randomizable Ciphertexts},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1503},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1503}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.