Paper 2023/1165

On the Security of Universal Re-Encryption

Fabio Banfi, ETH Zurich
Ueli Maurer, ETH Zurich
Silvia Ritsch, Eindhoven University of Technology

A universal re-encryption (URE) scheme is a public-key encryption scheme enhanced with an algorithm that on input a ciphertext, outputs another ciphertext which is still a valid encryption of the underlying plaintext. Crucially, such a re-encryption algorithm does not need any key as input, but the ciphertext is guaranteed to be valid under the original key-pair. Therefore, URE schemes lend themselves naturally as building blocks of mixnets: A sender transmits the encryption of a message under the receivers public-key to a mixer, which re-encrypts it, and the receiver later retrieves the re-encrypted ciphertext, which will decrypt successfully to the original message. Young and Yung (SCN 2018) argued that the original definition of URE by Golle et al. (CT-RSA 2004) was flawed, because it did not consider anonymity of encryption. This motivated them to claim that they finally put URE on solid grounds by presenting four formal security notions which they argued a URE should satisfy. As our first contribution, we introduce a framework that allows to compactly define and relate security notions as substitutions of systems. Using such framework, as our second contribution we show that Young and Yung's four notions are not minimal, and therefore do not properly capture the essence of a secure URE scheme. We provide three definitions that imply (and are implied by) theirs. Using the constructive cryptography framework, our third contribution is to capture the essence of URE from an application point of view by providing a composable security notion that expresses the ideal use of URE in a mixnet. Finally, we show that the composable notion is implied by our three minimal notions.

Available format(s)
Public-key cryptography
Publication info
universal re-encryptionunlinkabilityanonymitycomposable security
Contact author(s)
fabio banfi @ inf ethz ch
maurer @ inf ethz ch
s ritsch @ tue nl
2023-07-30: approved
2023-07-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Fabio Banfi and Ueli Maurer and Silvia Ritsch},
      title = {On the Security of Universal Re-Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1165},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.