IACR News item: 30 March 2016
Adam L. Young, Moti Yung
ePrint Report
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.
Additional news items may be found on the IACR news page.