**Semantically Secure Anonymity: Foundations of Re-encryption**

*Adam L. Young and Moti Yung*

**Abstract: **The notion of universal re-encryption is an established primitive
used in the design of many anonymity protocols. It allows anyone
to randomize a ciphertext without changing its size, without first
decrypting it, and without knowing who the receiver is (i.e., not
knowing the public key used to create it).
By design it prevents the randomized ciphertext from being
correlated with the original ciphertext.
We revisit and analyze the security
foundation of universal re-encryption and show a subtlety in it,
namely, that it does not require that the encryption function
achieve key anonymity. Recall that the encryption function is
different from the re-encryption function.
We demonstrate this subtlety by constructing a cryptosystem that satisfies the
established definition of a universal cryptosystem but that has an encryption
function that does not achieve key anonymity, thereby instantiating the gap in
the definition of security of universal re-encryption. We note that the
gap in the definition carries over to a set of applications
that rely on universal re-encryption, applications in the original
paper on universal re-encryption and also follow-on work.
This shows that the original definition needs to be corrected
and it shows that it had a knock-on
effect that negatively impacted security in later work.
We then introduce a new definition that includes
the properties that are needed for a re-encryption cryptosystem to achieve
key anonymity in both the encryption function and the re-encryption
function, building on Goldwasser and Micali's "semantic security" and
the original "key anonymity" notion of Bellare, Boldyreva, Desai, and Pointcheval.
Omitting any of the properties in our definition leads to a problem.
We also introduce a new generalization of the Decision
Diffie-Hellman (DDH) random self-reduction and use it, in turn, to prove
that the original ElGamal-based universal cryptosystem of Golle et al
is secure under our revised security definition.
We apply our new DDH reduction
technique to give the first proof in the standard model that ElGamal-based
incomparable public keys achieve key anonymity under DDH.
We present a novel secure Forward-Anonymous Batch Mix
as a new application.

**Category / Keywords: **public-key cryptography / probabilistic re-encryption, key anonymity, anonymous communication, semantic security, message indistinguishability, batch mix, DDH groups, cryptanalysis of provably secure cryptosystems

**Original Publication**** (with major differences): **Security and Cryptography for Networks---SCN 2018

**Date: **received 29 Mar 2016, last revised 13 Jul 2018

**Contact author: **ayoung235 at gmail com

**Available format(s): **PDF | BibTeX Citation

**Note: **Added need for anonymity definitions subsection, revised for 2-col format.

**Version: **20180713:111835 (All versions of this report)

**Short URL: **ia.cr/2016/341

[ Cryptology ePrint archive ]