Advancements in Proxy Re-Encryption: Defining Security for wider Applications

In cryptographic schemes that use keys, security of the scheme as a whole depends on the security of the key. Our area of interest is in applications where the keys used to encrypt files need to be changed, particularly when those files are stored by third parties. Proxy Re-Encryption (PRE), originally introduced by Blaze, Bleumer, and Strauss in 1998, allows a proxy to transform ciphertexts encrypted under one public key into an encryption of the same message under a new public key without learning the message. This is achieved by sending the proxy an update token created using the current secret key and new public key.
The original motivation cited for PRE was email forwarding, as a means of Alice
sharing her encrypted emails with Bob. Access revocation, the other obvious application of PRE, was not considered, meaning many PRE schemes are unsuitable as a mechanism for mitigating key compromise. In this thesis, we take a fresh look at PRE, particularly its suitability in enforcing cryptographic access control and as a key rotation mechanism to enforce key life cycles.

In our first contribution, we consider a malicious proxy that seeks to perform unauthorised re-encryptions. We propose a number of security definitions concerning an adversary’s ability to perform a re-encryption not initiated by the client. One of these definitions is authenticated re-encryption, which allows the identity of the party who initiated the re-encryption to be verified, which is useful for verifying that access has been granted legitimately.

Our second contribution is to define post-compromise security for PRE. PRE schemes meeting this definition can be used for access revocation and key expiry. We create the strongest definition to date, whereby compromise of the old secret key, old ciphertext and update token cannot distinguish re-encrypted ciphertexts. We provide an efficient post-compromise secure PRE scheme using lattice-based cryptography.

Finally, we investigate PRE security with adaptive key corruptions. Most work on
PRE considers selective key corruptions, where key compromise happens before adversaries learn any challenges. Adaptive security, on the other hand, allows adversaries to corrupt keys at any point, as long as they do not corrupt any key that can be used to directly decrypt challenge ciphertexts. Existing work shows how adaptive security can be reached from selective security, but usually relies to some extent on needing to guess which keys will be corrupted in advance. This approach leads to a large security loss as the guess must be correct. We achieve tighter bounds by taking a different approach which extends observations already made in the literature to prove adaptive security at a much smaller loss, using previously undefined properties of PRE schemes.