Paper 2019/368

Strong Post-Compromise Secure Proxy Re-Encryption

Alex Davidson, Amit Deo, Ela Lee, and Keith Martin


Proxy Re-Encryption (PRE), introduced by Bellare et. al, allows a ciphertext encrypted using a key pki to be re-encrypted by a third party so that it is an encryption of the same message under a new key pkj , without revealing the message. Post-Compromise Security (PCS) was first introduced for messaging protocols, and ensures that a ciphertext remains confidential even when past keys have been corrupted. We define PCS in the context of PRE, which ensures that an adversary cannot distinguish which ciphertext a re-encryption was created from even given the old secret key, potential old ciphertexts and update token used to perform the re-encryption. We argue that this formal notion accurately captures the most intuitive form of PCS. We give separating examples demonstrating how our definition is stronger than existing ones, before showing that PCS can be met using a combination of existing security definitions from the literature. In doing so, we show that there are existing PRE schemes that satisfy PCS. We also show that natural modifications of more practical PRE schemes can be shown to be PCS without relying on this combination of existing security definitions. Finally, we discuss the relationship between PCS with selective versus adaptive key corruptions, giving a theorem that shows how adaptive security can be met for certain re-encryption graphs.

Note: New revision makes the structure the same as the conference version, as well as addressing some errors. An overview of the changes is given in the introduction, and clear comments on specific changes are provided in the appropriate sections.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.ACISP 2019: The 24th Australasian Conference on Information Security and Privacy
Proxy re-encryptionkey rotationpost-compromise securitylattice crypto
Contact author(s)
Ela Lee 2010 @ live rhul ac uk
2020-04-09: last of 2 revisions
2019-04-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alex Davidson and Amit Deo and Ela Lee and Keith Martin},
      title = {Strong Post-Compromise Secure Proxy Re-Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2019/368},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.