CLUE: Certificateless Updatable Encryption

We formalise certificateless public-key updatable encryption (CLUE), a primitive that has yet to be defined in the public-key updatable encryption (PKUE) literature. Traditionally, PKUE allows outsourcing ciphertext key rotation to an untrusted host using a special token such that the ciphertext is updated to a distinct period known as an epoch. Key to security, the host does not learn anything about the underlying plaintext. In practice, applying PKUE in a public key infrastructure (PKI) requires trust in a third party producing the epoch public and secret keys, which is a clear violation of privacy if the key generator behaves maliciously or is corrupted. In this paper, we are concerned with reducing the trust in the PKI key generator and our chosen solution is to formalise our novel CLUE primitive, from PKUE and certificateless public key encryption (CL-PKE) primitives, as well as a security framework for CLUE. Moreover, we modify the certificateless encryption scheme proposed by Libert et al. (PKC 2006) and demonstrate the provable security of our CLUE scheme. To do so, we follow the modular approach given by Klooss et al. (EUROCRYPT'19) to reduce the security analysis to the standard setting.