Abstract: Randomizable encryption allows anyone to transform a ciphertext into a fresh ciphertext of the same message. Analogously, a randomizable signature can be transformed into a new signature on the same message. We combine randomizable encryption and signature to get commutativity: given a ciphertext CM on a message M, the signer can sign the ciphertext CM into SC which can thereafter be seen as an encryption CS of the signature S of the message M, since the owner of the decryption key can extract a signature S on the plaintext M from SC. Signature and encryption thus commute. Furthermore, given the signature on the ciphertext anyone, knowing neither the signing key nor the encrypted message, can randomize the ciphertext and adapt the signature to the fresh encryption, thus maintaining public verifiability. We first show how such a primitive can help to construct a non-interactive receipt-free universally verifiable e-voting scheme. Besides, our primitive also yields an efficient round-optimal blind signature scheme. Then, we instantiate this primitive by combining classical tools, such as the ElGamal encryption, Waters' signature and Groth-Sahai proofs. The security relies on classical assumptions only.
This is a joint work with Olivier Blazy, Georg Fuchsbauer and Damien Vergnaud.