Paper 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.

Note: We found a flaw that we could not fix (yet) thus we withdrew the paper. - The Rand-RCCA PKE scheme has been published at ACNS'20 under the name of "Improving the Efficiency of Re-Randomizable and Replayable CCA Secure Public Key Encryption", - The section on auditable protocols has been included in the full version of the paper "Structure-Preserving and Re-randomizable RCCA-secure Public Key Encryption and its Applications" (Eprint 2019/955 ).