Traceable mixnets
Authors: Prashant Agrawal (CSE, IIT Delhi; CDAIS, Ashoka University), Abhinav Nakarmi (CSE, University of Michigan), Mahabir Prasad Jhanwar (CS and CDAIS, Ashoka University), Subodh Sharma (CSE, IIT Delhi), Subhashis Banerjee (CSE, IIT Delhi; CS and CDAIS, Ashoka University)
Volume: 2024
Issue: 2
Pages: 235–275
DOI: https://doi.org/10.56553/popets-2024-0049
Abstract: We introduce the notion of traceable mixnets. In a traditional mixnet, multiple mix-servers jointly permute and decrypt a list of ciphertexts to produce a list of plaintexts, along with a proof of correctness, such that the association between individual ciphertexts and plaintexts remains completely hidden. However, in many applications, the privacy-utility tradeoff requires answering some specific queries about this association, without revealing any information beyond the query result. We consider queries of the following types: a) given a ciphertext in the mixnet input list, whether it encrypts one of a given subset of plaintexts in the output list, and b) given a plaintext in the mixnet output list, whether it is a decryption of one of a given subset of ciphertexts in the input list. Traceable mixnets allow the mix-servers to jointly prove answers to the above queries to a querier such that neither the querier nor a threshold number of mix-servers learn any information beyond the query result. Further, if the querier is not corrupted, the corrupted mix-servers do not even learn the query result. We first comprehensively formalise these security properties of traceable mixnets and then propose a construction of traceable mixnets using novel distributed zero-knowledge proofs (ZKPs) of set membership and of a statement we call reverse set membership. Although set membership has been studied in the single-prover setting, the main challenge in our distributed setting lies in making sure that none of the mix-servers learn the association between ciphertexts and plaintexts during the proof. We implement our distributed ZKPs and show that they are faster than state-of-the-art by at least one order of magnitude.
Keywords: verifiable mixnets, traceability, distributed zero-knowledge proofs, set membership, reverse set membership
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
