Paper 2023/152

Almost Tightly-Secure Re-Randomizable and Replayable CCA-secure Public Key Encryption

Antonio Faonio, EURECOM
Dennis Hofheinz, ETH Zurich
Luigi Russo, EURECOM

Re-randomizable Replayable CCA-secure public key encryption (Rand-RCCA PKE) schemes guarantee security against chosen-ciphertext attacks while ensuring the useful property of re-randomizable ciphertexts. We introduce the notion of multi-user and multi-ciphertext Rand-RCCA PKE and we give the first construction of such a PKE scheme with an almost tight security reduction to a standard assumption. Our construction is structure preserving and can be instantiated over Type-1 pairing groups. Technically, our work borrows ideas from the state of the art Rand-RCCA PKE scheme of Faonio et al. (ASIACRYPT’19) and the adaptive partitioning technique of Hofheinz (EUROCRYPT’17). Additionally, we show (1) how to turn our scheme into a publicly-verifiable (pv) Rand-RCCA scheme and (2) that plugging our pv-Rand-RCCA PKE scheme into the MixNet protocol of Faonio et al. we can obtain the first almost tightly-secure MixNet protocol.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in PKC 2023
Contact author(s)
antonio faonio @ eurecom fr
hofheinz @ inf ethz ch
russol @ eurecom fr
2023-02-22: revised
2023-02-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Antonio Faonio and Dennis Hofheinz and Luigi Russo},
      title = {Almost Tightly-Secure Re-Randomizable and Replayable CCA-secure Public Key Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2023/152},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.