Cryptology ePrint Archive: Report 2019/368

Strong Post-Compromise Secure Proxy Re-Encryption

Alex Davidson and Amit Deo and Ela Lee and Keith Martin

Abstract: 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.

Category / Keywords: public-key cryptography / Proxy re-encryption, key rotation, post-compromise security, lattice crypto

Original Publication (with minor differences): ACISP 2019: The 24th Australasian Conference on Information Security and Privacy

Date: received 5 Apr 2019, last revised 9 Apr 2020

Contact author: Ela Lee 2010 at live rhul ac uk

Available format(s): PDF | BibTeX Citation

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.

Version: 20200409:115021 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]