Paper 2024/158

HiSE: Hierarchical (Threshold) Symmetric-key Encryption

Abstract

Threshold symmetric encryption (TSE) [DiSE, CCS 2018], provides a practical decentralized solution for symmetric encryption by distributing the secret-key at all times, thus avoiding a single point of attack or failure. TSE was further enhanced [ATSE, CCS 2021] by an amortization which enables a ``more privileged'' client to encrypt bulk records by interacting only once with the key servers, while decryption must be performed individually for each record, potentially by a ``less privileged'' client. However, a typical enterprise generates data once and queries it several times for various data analysis; i.e., enterprise workloads are often decryption heavy! ATSE does not meet the bar for this setting because of linear interaction / computation (in the number of records to be decrypted) -- our experiments show that ATSE provides a sub-par throughput of a few hundred records/sec. Our work starts with an observation that a large and useful class of analytics queries access some time-windowed sequence of database records (e.g. log entries or user transactions). Can we offer faster decryption for such access patterns, without compromising the benefits of prior schemes? To that end, we build a new TSE scheme that allows for both encryption and decryption with flexible granularity, in that a client's interactions with the key servers is at most logarithmic in the number of records. Our idea is to employ a binary-tree structure, where one interaction is needed to decrypt all ciphertexts in a sub-tree, and thus only log-many for any arbitrary sub-sequence. Our scheme incorporates ideas from binary-tree encryption by Canetti et al. [Eurocrypt 2003] and carefully combines that with Merkle-tree commitments. We show that our scheme satisfies all essential TSE properties, such as correctness, privacy and authenticity for our notion, formalized as hierarchical threshold symmetric-key encryption (HiSE). Our analysis relies on a well-known XDH assumption and a new assumption, that we call $\ell$-masked BDDH, over asymmetric bilinear pairing in the programmable random oracle model. We also show that our new assumption holds in the generic group model. Our extensive implementation shows 10-65$\times$ improvement in latency and throughput over ATSE. HiSE can decrypt over 6K records/sec on server-grade hardware, but the logarithmic overhead in encryption (not decryption) only lets us encrypt up to 3K records/sec (about 4.5x slowdown) and incurs roughly 500 bytes of ciphertext expansion per record -- while reducing this penalty is an important future work, we believe HiSE offers an acceptable practical trade-off in practice.