Cryptology ePrint Archive: Report 2020/524

Efficient Signatures on Randomizable Ciphertexts

Balthazar Bauer and Georg Fuchsbauer

Abstract: Randomizable encryption lets anyone randomize a ciphertext so it is distributed like a fresh encryption of the same plaintext. Signatures on randomizable ciphertexts (SoRC), introduced by Blazy et al. (PKC'11), let one adapt a signature on a ciphertext to a randomization of the latter. Since signatures can only be adapted to ciphertexts that encrypt the same message as the signed ciphertext, signatures obliviously authenticate plaintexts. SoRC have been used as a building block in e-voting, blind signatures and (delegatable) anonymous credentials.

We observe that SoRC can be seen as signatures on equivalence classes (JoC'19), another primitive with many applications to anonymous authentication, and that SoRC provide better anonymity guarantees. We first strengthen the unforgeability notion for SoRC and then give a scheme that provably achieves it in the generic group model. Signatures in our scheme consist of only 4 bilinear-group elements, which is considerably more efficient than prior schemes.

Category / Keywords: public-key cryptography / anonymity, digital signatures

Date: received 5 May 2020, last revised 6 May 2020

Contact author: georg fuchsbauer at tuwien ac at

Available format(s): PDF | BibTeX Citation

Version: 20200506:093038 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]