Cryptology ePrint Archive: Report 2018/864

Optimistic Mixing, Revisited

Antonio Faonio and Dario Fiore

Abstract: Mixing Networks are protocols that allow a set of senders to send messages anonymously. Such protocols are fundamental building blocks to achieve privacy in a variety of applications, such as anonymous e-mail, anonymous payments, and electronic voting.

Back in 2002, Golle et al. proposed a new concept of mixing network, called optimistic mixing, that allows for fast mixing when all the parties execute the protocol honestly. If, on the other hand, one or more mix-servers cheat, then the attack is recognized and one can back up to a different, slow mix-net.

Unfortunately, Abe and Imai (ACISP'03) and independently Wikström (SAC'03) showed several major flaws in the optimistic protocol of Golle et al. In this work, we give another look at optimistic mixing networks. Our contribution is mainly threefold. First, we give formal definitions for optimistic mixing in the UC model. Second, we propose a compiler for obtaining a UC-secure mixing network by combining an optimistic mixing with a traditional mixing protocol as backup mixing. Third, we propose an efficient UC-secure realization of optimistic mixing based on the DDH assumption in the non-programmable random oracle model. As a key ingredient of our construction, we give a new randomizable replayable-CCA secure public key encryption (PKE) that outperforms in efficiency all previous schemes. We believe this result is of independent interest.

Category / Keywords: cryptographic protocols / Mix-Nets, Re-Randomizable Replayable CCA, UC-security

Date: received 13 Sep 2018

Contact author: antonio faonio at imdea org, dario fiore@imdea org

Available format(s): PDF | BibTeX Citation

Version: 20180922:180206 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]