Paper 2023/848

Extending Updatable Encryption: Public Key, Tighter Security and Signed Ciphertexts

Chen Qian, Shandong University
Yao Jiang Galteland, Qredo
Gareth T. Davies, Bergische Universität Wuppertal

Updatable encryption is a useful primitive that enables key rotation for storing data on an untrusted storage provider without the leaking anything about the plaintext or the key. In this work, we make two contributions. Firstly, we extend updatable encryption to the public-key setting, providing its security model and three different efficient constructions. Using a public-key updatable encryption scheme, a user can receive messages directly in the cloud from multiple senders without revealing their secret key. Secondly, we add signatures on ciphertexts to guarantee plaintext integrity and authenticity. We call our new primitive \emph{Public-Key Signable Updatable Encryption} ($\mathsf{PSigUE}$). Our approach ensures that only legitimate ciphertexts are accepted by the server, and the adversary cannot compromise the message integrity in the database. We bypass the conflict between public integrity verification and the malleability that comes from the update functionality. We provide three pairing-based constructions of public-key signable updatable encryption. The first scheme, $\mathsf{PSigUE}_1$, is built using a dual-mode zero-knowledge proof of knowledge system under an assumption closely related to the $k$-linear assumption. The second scheme, $\mathsf{PSigUE}_2$, provides unlinkability in addition to public authenticity. In the third scheme, $\mathsf{PSigUE}_\mathsf{T}$, we achieve the tight security with respect of number of epochs. The construction of $\mathsf{PSigUE}_\mathsf{T}$ is inspired by tag-based tightly-secure PKE schemes.

Available format(s)
Cryptographic protocols
Publication info
Updatable EncryptionPublic KeySignature
Contact author(s)
chen qian @ sdu edu cn
yao jiang @ qredo com
davies @ uni-wuppertal de
2023-06-07: approved
2023-06-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Chen Qian and Yao Jiang Galteland and Gareth T. Davies},
      title = {Extending Updatable Encryption: Public Key, Tighter Security and Signed Ciphertexts},
      howpublished = {Cryptology ePrint Archive, Paper 2023/848},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.