Efficient and secure encryption key rotation is a longstanding issue with respect to storing sensitive data in the cloud, one that Stanford University Professor Dan Boneh has been studying for years. He presented some of his most recent findings at Upgrade 2020, the NTT Research Summit.

Normally, a user would simply encrypt the file, upload it to the cloud and retain the key, meaning only the user can decrypt the file. But a common requirement with encryption is key rotation. This involves taking a ciphertext and re-encrypting it with a different key, without changing the underlying data.

Key rotation is required or recommended under certain standards, including NIST 800-57 Recommendation for Key Management and the Payment Card Industry Data Security Standard (PCI DSS). It’s also a good way to give people access to data for only a certain period of time.

Boneh, who heads the applied cryptography group and co-directs the computer security lab at Stanford, said two options for addressing the cloud encryption problem come immediately to mind:

1. Download the entire dataset, decrypt it using the existing key, re-encrypt with a new key and upload it back to the cloud. “That works, but is very expensive,” Boneh said, given you have to move potentially huge amounts of data in and out of the cloud.

2. The other option is to send old and new keys to the cloud provider and have it de-crypt and re-encrypt. While that also works, it’s insecure because the provider can see the data in the clear.

A better option is updatable encryption. This involves taking old and new encryption keys and combining them using a re-key generation algorithm. Such algorithms create a short key that’s a combination of the old and new keys. You can then send that key to the cloud and the provider uses it to re-encrypt the ciphertext, without ever seeing it in the clear.

That’s not exactly a new concept. Boneh was part of a team that wrote a paper on it, “Key Homomorphic PRFs and Their Applications,” for the CRYPTO 2013 conference (a full version of which was published in 2014). Others have also worked on the topic since.

In his recent work, Boneh and several of his students – Saba Eskandarian, Sam Kim and Maurice Shih – set out to look at more efficient constructions for updatable encryption using key homomorphic PRFs (pseudorandom functions).

Key homomorphic PRFs are useful for updatable encryption because the re-encryption key is the sum of the old key and the new key. They can be constructed such that cloud providers can transform ciphertext from an encryption under one key to an encryption under another key.

In his work, Boneh was particularly interested in key homomorphic PRFs that come from lattices, and whether his team could optimize the operation to get a very fast updatable encryption scheme. “The answer is yes we can,” he said.

He then compared that method to one using nested construction and simple symmetric encryption.

“What we showed was that the nested construction is the best we have, as long as the number of key rotations is not too high,” he said.

The reason for this has to do with the way the symmetric system works, which is basically by creating many layers of encryption. Each of them has to be decrypted during every re-encryption process, so it slows down over time. The crossover point is about 50 re-encryptions; after that, the lattice approach will be a better choice.

“If in the lifetime of the ciphertext you expect fewer than 50 encryptions, you might as well use the symmetric nested system,” Boneh said. “But if you’re doing frequent re-encryptions, say weekly, you might end up with many more re-encryptions, in which case the lattice-based key homomorphic scheme is the best updatable system we have today.”

For the full transcript of Dan Boneh’s presentation, click here.

Watch Dan Boneh’s full presentation below.