Paper 2022/311

Unidirectional Updatable Encryption and Proxy Re-encryption from DDH or LWE

Peihan Miao, Sikhar Patranabis, and Gaven Watson


Updatable Encryption (UE) and Proxy Re-encryption (PRE) allow re-encrypting a ciphertext from one key to another in the symmetric-key and public-key settings, respectively, without decryption. A longstanding open question has been the following: do unidirectional UE and PRE schemes (where ciphertext re-encryption is permitted in only one direction) necessarily require stronger/more structured assumptions as compared to their bidirectional counterparts? Known constructions of UE and PRE seem to exemplify this “gap” – while bidirectional schemes can be realized as relatively simple extensions of public-key encryption from standard assumptions such as DDH or LWE, unidirectional schemes typically rely on stronger assumptions such as FHE or indistinguishability obfuscation (iO), or highly structured cryptographic tools such as bilinear maps or lattice trapdoors. In this paper, we bridge this gap by showing the first feasibility results for realizing unidirectional UE and PRE from a new generic primitive that we call Key and Plaintext Homomorphic Encryption (KPHE) – a public-key encryption scheme that supports additive homomorphisms on its plaintext and key spaces simultaneously. We show that KPHE can be instantiated from DDH or LWE. This yields, in particular, the first constructions of unidirectional UE and PRE from DDH, as well as the first constructions of unidirectional UE and PRE from LWE that do not resort to FHE or lattice trapdoors. Our constructions achieve the strongest notions of post-compromise security in the standard model. Our UE schemes also achieve “backwards-leak directionality” of key updates (a notion we discuss is equivalent, from a security perspective, to that of unidirectionality with no-key updates). Our results establish (somewhat surprisingly) that unidirectional UE and PRE schemes satisfying such strong security notions do not, in fact, require stronger/more structured cryptographic assumptions as compared to bidirectional schemes.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Updatable EncryptionProxy Re-encryptionUnidirectionalBackwards-Leak DirectionalityIND-HRA securityPost-Compromise SecurityKey and Plaintext Homomorphic Encryption
Contact author(s)
peihan @ uic edu
sikharpatranabis @ gmail com
gawatson @ visa com
2022-03-07: received
Short URL
Creative Commons Attribution-NonCommercial


      author = {Peihan Miao and Sikhar Patranabis and Gaven Watson},
      title = {Unidirectional  Updatable Encryption and Proxy Re-encryption from DDH or LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2022/311},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.