Cryptology ePrint Archive: Report 2019/1275

Updatable Oblivious Key Management for Storage Systems

Stanislaw Jarecki and Hugo Krawczyk and Jason Resch

Abstract: We introduce Oblivious Key Management Systems (KMS) as a more secure alternative to traditional wrapping-based KMS that form the backbone of key management in large-scale data storage deployments. The new system, that builds on Oblivious Pseudorandom Functions (OPRF), hides keys and object identifiers from the KMS, offers unconditional security for key transport, provides key verifiability, reduces storage, and more. Further, we show how to provide all these features in a distributed threshold implementation that enhances protection against server compromise.

We extend this system with updatable encryption capability that supports key updates (known as key rotation) so that upon the periodic change of OPRF keys by the KMS server, a very efficient update procedure allows a client of the KMS service to non-interactively update all its encrypted data to be decryptable only by the new key. This enhances security with forward and post-compromise security, namely, security against future and past compromises, respectively, of the client's OPRF keys held by the KMS. Additionally, and in contrast to traditional KMS, our solution supports public key encryption and dispenses with any interaction with the KMS for data encryption (only decryption by the client requires such communication).

Our solutions build on recent work on updatable encryption but with significant enhancements applicable to the remote KMS setting. In addition to the critical security improvements, our designs are highly efficient and ready for use in practice. We report on experimental implementation and performance.

Category / Keywords: cryptographic protocols / Key management, Oblivious PRF, updatable encryption

Original Publication (with minor differences): 2019 ACM SIGSAC Conference on Computer and Communications Security (CCS’19). ACM, 2019.

Date: received 3 Nov 2019

Contact author: hugokraw at gmail com

Available format(s): PDF | BibTeX Citation

Note: This is a full version of [32] that appeared in the 2019 ACM SIGSAC Conference on Computer and Communications Security (CCS’19). A preliminary treatment of the material in this paper appeared in

Version: 20191105:082341 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]