Paper 2022/311

Unidirectional Updatable Encryption and Proxy Re-encryption from DDH

Peihan Miao, Brown University
Sikhar Patranabis, IBM Research - India
Gaven Watson, Meta
Abstract

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. This yields the first constructions of unidirectional UE and PRE from DDH. 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.

Note: This the full version of a paper to appear at IACR PKC 2023. This version of the paper contains edits to the introduction and extended discussions based on feedback from the anonymous reviewers of IACR PKC 2023, whom we thank for their insightful comments and suggestions. Also, in this version, we choose to focus on the DDH-based construction of KPHE and the corresponding realizations of unidirectional UE and PRE, while dropping the LWE-based realizations.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in PKC 2023
Keywords
Updatable EncryptionProxy Re-encryptionUnidirectionalPost-Compromise SecurityHomomorphic Encryption
Contact author(s)
peihan_miao @ brown edu
sikharpatranabis @ gmail com
gavenjwatson @ gmail com
History
2023-04-20: last of 2 revisions
2022-03-07: received
See all versions
Short URL
https://ia.cr/2022/311
License
Creative Commons Attribution-NonCommercial
CC BY-NC

BibTeX

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