Cryptology ePrint Archive: Report 2016/341
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
decrypting it, and without knowing the receiver's public key.
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 that to date it has not had a satisfactory definition of security, in spite of
its numerous uses.
We then analyze the anonymity arguments for the ElGamal-based
universal cryptosystem and show that it has not been proven
to be anonymous under DDH (and does not meet the standards of modern cryptography), and that such a proof is non-trivial given existing reduction techniques.
This analysis is a type of cryptanalysis of provably secure systems,
where reductions and exact assumptions have certain gaps in them that
need to be detected and corrected.
The notion of an incomparable public key cryptosystem is closely related to universal re-encryption; we similarly cryptanalyze the security foundation of the ElGamal-based incomparable public key cryptosystem as well and show that it was not proven to be secure.
To correct the lack of foundation, we introduce a definition of what
properties are needed for a re-encryption cryptosystem that needs to provide anonymity.
We then introduce a new generalization of the well-known Decision
Diffie-Hellman (DDH) random self-reduction and use it, in turn, to prove that the ElGamal-based universal cryptosystem is secure under DDH. We apply our new DDH reduction technique to incomparable public key systems as well and prove that it is secure.
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
Date: received 29 Mar 2016, last revised 23 May 2016
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: 20160524:013234 (All versions of this report)
Short URL: ia.cr/2016/341
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]