Paper 2022/877

A New Approach to the Constant-Round Re-encryption Mix-Net

Abstract

The re-encryption mix-net (RMN) is a basic cryptographic tool that is widely used in the privacy protection domain and requires anonymity support; for example, it is used in electronic voting, web browsing, and location systems. To protect information about the relationship between senders and messages, a number of mix servers in RMNs shuffle and forward a list of input ciphertexts in a cascading manner. The output of the last mix server is decrypted to yield the set of original messages. The main downside of this approach is that the mixing process requires a number of rounds that is linear in the number of mix servers. This implies that a long round delay would cause network latency, which can dominate local computational latencies. To minimize the effect of network latency, RMN protocols with constant round complexity are more desirable. In this work, we propose a new RMN protocol that runs in $O(1)$ rounds in the number of mix servers and that UC-realizes a hybrid model with access to some functionalities for secure communication and zero-knowledge proof (ZKP). Interestingly, because our protocol does not require a ZKP protocol for a verifiable shuffle, we also achieve a considerable efficiency gain in terms of computation cost. Our main tools are secret sharing and an ElGamal encryption that is extended in the sense that it works on a multiplicative group under field extension. Importantly, this extended ElGamal encryption scheme acquires a new capability: it can efficiently decompose a decrypted message into unique values. We provide a detailed report on the theoretical performance and security analysis of this method.