TL;DR
This paper introduces Amortized Threshold Symmetric-key Encryption (ATSE), a novel cryptographic scheme that allows a "privileged" client to encrypt large groups of messages with a single interaction with key management servers. This significantly improves efficiency for bulk data encryption compared to existing threshold encryption methods, while maintaining strong security guarantees for individual message decryption.
What Problem Does This Paper Address?
Modern enterprises handle massive amounts of data that require robust encryption for security. Traditional key management systems often rely on Hardware Security Modules (HSMs), which can face scalability, availability, and cost issues. Threshold cryptography offers a decentralized alternative where secret keys are split among multiple servers, requiring a threshold number of them to perform cryptographic operations.
The paper builds upon prior work on Distributed Symmetric-key Encryption (DiSE), which introduced Threshold Symmetric-key Encryption (TSE). While DiSE ensures strong security, its requirement for a separate interaction with servers for each encryption and decryption operation becomes a performance bottleneck when dealing with large datasets. This is particularly problematic for write-heavy applications like payment gateways that encrypt numerous transactions daily. The core challenge is to achieve the efficiency of bulk encryption without compromising the fine-grained access control and security guarantees of individual message decryption.
Methods
The authors propose Amortized Threshold Symmetric-key Encryption (ATSE) by introducing a new cryptographic primitive called Flexible Threshold Key-Derivation (FTKD).
- FTKD: This primitive allows a client to derive pseudorandom keys in different modes. A "privileged" client can use a group of messages to derive a common group-specific key through a single interaction with servers. This group key can then be used to derive individual message-specific keys locally. Crucially, FTKD ensures that even if a client only has access to a partial key, they cannot derive information about other messages.
- ATSE Construction: The ATSE scheme leverages FTKD and a group commitment scheme (based on Merkle trees) to achieve its goals.
- Encryption: A privileged client encrypts a group of messages by first creating a Merkle tree commitment to the entire group. This commitment, along with the client's identity, is used to interact with a threshold number of servers to derive a group-specific key. This group key is then used locally to derive individual message-specific keys, which are used to encrypt the messages. The ciphertext includes the group commitment, a path in the Merkle tree, and the encrypted message.
- Decryption: An unprivileged client decrypts a single message by interacting with a threshold number of servers to derive the message-specific key directly from the ciphertext components. This interaction is necessary for fine-grained access control.
The authors also formalize security notions for ATSE, including correctness, message privacy, and authenticity, and provide proofs based on standard cryptographic assumptions like the Bilinear Decisional Diffie-Hellman (BDDH) assumption.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Amortization is Key: The core insight is that for bulk encryption, the expensive server interaction can be "amortized" over many messages. This drastically reduces the per-message overhead.
- Privileged vs. Unprivileged Clients: The scheme cleverly distinguishes between clients that can perform bulk operations (privileged, with more trust) and those that only decrypt individual messages (unprivileged, with stricter access control).
- FTKD as a Building Block: The introduction of FTKD is a significant contribution, enabling flexible key derivation for different granularities (group vs. individual messages) within a threshold setting.
- Merkle Trees for Group Commitments: Using Merkle trees for group commitments provides the necessary structure to bind a group of messages together while allowing individual message verification.
- Efficiency Gains: The paper demonstrates substantial performance improvements, particularly in latency and throughput, for bulk encryption scenarios.
Key Results
The paper presents experimental results showing significant performance improvements for ATSE compared to a batched DiSE implementation:
- Latency: ATSE achieves significantly lower latency when encrypting large groups of messages (e.g., 10K messages), with improvements of 12x-42x over DiSE. For single messages, ATSE has slightly higher latency due to the additional bilinear pairing.
- Throughput: ATSE achieves throughputs over 23K encryptions/sec, an order of magnitude improvement over DiSE for bulk operations.
- Network Independence: For bulk encryption, ATSE's performance is largely unaffected by network latency (LAN, WAN, GEO), making it suitable for geo-distributed deployments.
- Bandwidth: ATSE offers a significant reduction in bandwidth requirements compared to DiSE, especially for large numbers of messages.
Limitations and Future Work
- Strong Correctness Requirement: The authors emphasize that for their use case of massive data encryption, "strong correctness" is crucial. This ensures that even with malicious servers, an honest decryption will always yield the correct plaintext, not an error. Their construction relies on a strongly secure FTKD to achieve this.
- Ciphertext Expansion: The ATSE ciphertext includes a Merkle proof, leading to an increase in size that depends on the number of messages in the group. The authors suggest this can be mitigated by compressing the stored representation.
- Duplication Prevention: While the scheme prevents arbitrary duplication of ciphertexts, fully protecting against all forms of duplication (especially in the context of CPA-security) is left as an open question.
- FTKD Applications: The authors suggest that their FTKD primitive might have applications beyond ATSE, such as in identity-based threshold symmetric encryption.
Summary updated