Skip to Main content Skip to Navigation
Conference papers

Signatures on Randomizable Ciphertexts

Olivier Blazy 1, 2 Georg Fuchsbauer 3 David Pointcheval 1, 2 Damien Vergnaud 1, 2
1 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
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 signatures to a new primitive as follows: given a signature on a 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. Moreover, given the decryption key and a signature on a ciphertext, one can compute (``extract'') a signature on the encrypted plaintext. As adapting a signature to a randomized encryption contradicts the standard notion of unforgeability, we introduce a weaker notion stating that no adversary can, after querying signatures on ciphertexts of its choice, output a signature on an encryption of a new message. This is reasonable since, due to extractability, a signature on an encrypted message can be interpreted as an encrypted signature on the message. Using Groth-Sahai proofs and Waters signatures, we give several instantiations of our primitive and prove them secure under classical assumptions in the standard model and the CRS setting. As an application, we show how to construct an efficient non-interactive receipt-free universally verifiable e-voting scheme. In such a scheme a voter cannot prove what his vote was, which precludes vote selling. Besides, our primitive also yields an efficient round-optimal blind signature scheme based on standard assumptions, and namely for the classical Waters signature.
Document type :
Conference papers
Complete list of metadata
Contributor : David Pointcheval <>
Submitted on : Friday, December 3, 2010 - 10:14:51 AM
Last modification on : Thursday, July 1, 2021 - 5:58:06 PM

Links full text




Olivier Blazy, Georg Fuchsbauer, David Pointcheval, Damien Vergnaud. Signatures on Randomizable Ciphertexts. PKC 2011 - Proceedings of the 2011 International Conference on Practice and Theory in Public Key Cryptography, Mar 2011, Taormina, Italy. pp.403-422, ⟨10.1007/978-3-642-19379-8_25⟩. ⟨inria-00542643⟩



Record views