Hermes: Efficient and Secure Multi-Writer Encrypted Database

Hermes: Efficient and Secure Multi-Writer Encrypted Database

Speakers: Tung Le, Vina Tech; Thang Hoang

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=V6FHsl-RxMo

Overview

In an era increasingly reliant on cloud services for data storage and collaboration, ensuring both data utility and privacy remains a paramount challenge. The talk "Hermes: Efficient and Secure Multi-Writer Encrypted Database" by Tung Le from Vina Tech, co-authored with his advisor Thang Hoang, introduces a groundbreaking solution designed to address this critical balance. Hermes presents a novel multi-writer searchable encrypted database that significantly advances the state-of-the-art in searchable encryption, particularly within the hybrid searchable encryption (HSSE) paradigm.

The core problem Hermes tackles is the inherent conflict between data encryption, which protects confidentiality, and the need for practical operations like searching and querying over that data. While existing searchable encryption schemes offer partial solutions, they often suffer from critical drawbacks such as vulnerability to keyword guessing attacks, inefficient search complexity, or high overhead associated with maintaining privacy. Hermes offers a robust and performant alternative, delivering enhanced security guarantees against sophisticated attacks, dramatically improved search speeds, and a more efficient mechanism for ensuring forward privacy, making it a pivotal development for secure cloud data management.

This work is crucial for any organization or individual leveraging cloud platforms for data storage and sharing, especially in multi-user environments where different parties contribute data. By enabling efficient searching over encrypted data without compromising privacy or incurring prohibitive performance costs, Hermes paves the way for broader adoption of secure cloud computing. It particularly benefits scenarios requiring collaborative data input and secure retrieval, offering a practical and cryptographically sound approach to safeguarding sensitive information against semi-honest adversaries while retaining essential functionality.

Background

▶ Watch: Challenges with existing Hybrid Searchable Encryption (HSSE) (3:40)

The pervasive adoption of cloud computing has revolutionized data storage and sharing, offering unparalleled scalability and accessibility. However, this convenience comes with significant privacy implications, as sensitive user data is entrusted to third-party cloud providers. While encryption is the standard defense for data confidentiality, it traditionally renders data opaque to operations like searching and querying, severely limiting its utility. Cryptographic tools like Multi-Client Oblivious RAM (OAM) or Fully Homomorphic Encryption (FHE) can enable computations on encrypted data, but their computational overhead is often prohibitively high for practical applications.

The field of searchable encryption (SE), which has been under development since the early 2000s, offers a more practical approach to performing searches over encrypted data. SE schemes generally fall into two main categories, each with distinct advantages and disadvantages:

1. Dynamic Searchable Symmetric Encryption (DSSE):

• Pros: DSSE schemes rely on an encrypted search index, pre-built to facilitate efficient searching. This typically results in sublinear search complexity relative to the database size. Furthermore, DSSE schemes often achieve forward privacy, meaning that new updates do not reveal information about past searches. This is usually managed by the user maintaining an up-to-date counter state for update tokens.
• Cons: A significant limitation of DSSE is its primary focus on single-user settings. When extended to multi-user environments, it often necessitates that all users in the system are fully trusted, which is an unrealistic assumption in many real-world scenarios.

1. Public Key Searchable Encryption (PKSE):

• Pros: PKSE is inherently designed to support multi-writer scenarios, making it suitable for applications like encrypted email where multiple senders contribute data to a single receiver. A key advantage is that the reader (receiver) does not need to distribute a secret key to the writers (senders), and writers do not require synchronous communication with the reader to begin contributing data.
• Cons: The primary drawback of PKSE is its typically linear search complexity with respect to the database size, making it inefficient for large datasets. Moreover, achieving forward privacy in PKSE is considerably more challenging because there is no direct communication channel between the reader and writers, preventing writers from knowing the current search state needed to generate evolving update tokens.

In 2022, a new model emerged to bridge the gap between DSSE and PKSE, known as Hybrid Searchable Encryption (HSSE). The goal of HSSE is to combine the best features of both worlds:

• It aims for sublinear search complexity, specifically linear in the number of keywords and the number of updates associated with a target keyword.
• It supports epoch-based forward privacy, offering a mechanism to protect the confidentiality of future updates.
• Crucially, HSSE supports multi-writer functionality by leveraging a cryptographic primitive called ID Coupling Key Aggregate Encryption (ICKE). With ICKE, writers only need the public key of the reader to encrypt and contribute data, eliminating the need for synchronous communication.

Despite these advancements, the state-of-the-art HSSE schemes still presented notable disadvantages that Hermes directly addresses:

1. Vulnerability to Keyword Guessing Attacks: Existing HSSE schemes can be susceptible to adversaries attempting to guess keywords, potentially compromising privacy.
2. Search Complexity Limitations: While sublinear in database size, the search complexity of HSSE remained linear in the total number of keywords. For databases with a vast vocabulary, this still resulted in significant search latency.
3. High Writer Overhead for Privacy: To ensure forward privacy, writers in existing HSSE schemes were often required to periodically rebuild their search indexes, incurring substantial computational and communication overhead.

Hermes was developed specifically to overcome these three critical limitations, pushing the boundaries of efficient and secure multi-writer encrypted databases.

Key Findings

▶ Watch: Preventing keyword guessing attacks with Hidden ID ICKE (4:50)

Hermes represents a significant leap forward in the design and implementation of multi-writer searchable encrypted databases, addressing the most pressing limitations of prior art, particularly state-of-the-art Hybrid Searchable Encryption (HSSE) schemes. The core findings and contributions of Hermes can be summarized across three fundamental aspects: enhanced security, optimized search performance, and efficient privacy maintenance.

First, Hermes achieves a crucial security upgrade by providing robust protection against keyword guessing attacks. Previous HSSE schemes, while offering other benefits, were vulnerable to adversaries attempting to deduce encrypted keywords by observing ciphertext properties or interaction patterns. Hermes introduces a novel cryptographic primitive that embeds a writer-specific secret into ciphertexts, effectively preventing adversaries from crafting valid ciphertexts for brute-force decryption attempts. This significantly elevates the security posture of the encrypted database, making it suitable for more sensitive applications.

Second, the project delivers a dramatic improvement in search complexity. Where existing HSSE schemes suffered from search latency that was linear in the total number of keywords in the database, Hermes achieves a sublinear search complexity that is significantly more efficient. Through a clever strategy of recursive keyword partitioning, the search complexity is optimized to O(log² N / log log N), where N is the total number of keywords. This represents an order-of-magnitude improvement, making searches over very large keyword sets practical and fast. The talk highlights that Hermes is "up to two orders of magnitude faster" for keyword search performance compared to the previous state-of-the-art, a truly remarkable acceleration.

Third, Hermes innovates in how forward privacy is maintained, drastically reducing the associated overhead. Traditional approaches often required costly and frequent index rebuilds on the writer side, which was a significant operational burden. Hermes introduces an epoch-based forward privacy mechanism using a tree-based epoch encoding scheme. This method ensures that decryption keys generated at a specific epoch cannot decrypt ciphertexts from future epochs, thereby guaranteeing forward privacy without the need for periodic index rebuilds. This efficiency gain is substantial, with Hermes executing updates 4 to 17 times faster than previous forward private HSSE schemes, leading to significantly lower overhead for writers and a more practical system overall.

In summary, Hermes delivers a multi-writer searchable encrypted database that is not only more secure against prevalent attacks but also vastly more efficient in both search and update operations. These key findings collectively establish Hermes as a superior solution for secure, collaborative data management in untrusted cloud environments.

Technical Deep Dive

▶ Watch: Achieving forward privacy via epoch encoding (6:10)

The technical innovations behind Hermes are built upon a sophisticated understanding of cryptographic primitives and clever algorithmic design, specifically targeting the identified weaknesses in existing Hybrid Searchable Encryption (HSSE) schemes.

System and Threat Model

Hermes operates within a well-defined system and threat model, similar to that of HSSE. The system comprises:

• An honest reader who possesses a public and private key pair. This reader is the ultimate recipient and searcher of data.
• An arbitrary number of writers, some of whom may be corrupt. These writers contribute and share data with the reader. Each writer maintains an independent database.
• An untrusted server which stores the encrypted data from all writers and executes queries initiated by both the reader and writers.

The adversary in this model is assumed to be semi-honest, meaning it follows the protocol specifications but attempts to learn as much information as possible from observed data and interactions. The primary goal is to ensure data confidentiality and searchability while protecting against such an adversary.

Preventing Keyword Guessing Attacks via Hidden ID Coupling Key Aggregate Encryption

A critical vulnerability in prior HSSE schemes stemmed from their reliance on ID Coupling Key Aggregate Encryption (ICKE). While ICKE enables the key aggregate property—where a single decryption key can decrypt ciphertexts from various writers—it inadvertently created an opening for keyword guessing attacks. An adversary could potentially craft ciphertexts for known keywords and attempt to decrypt them, thereby inferring the underlying keywords.

Hermes addresses this by introducing a new primitive called Hidden ID Coupling Key Aggregate Encryption (Hidden ICKE). The core idea is to embed a unique secret value from each writer directly into their ciphertexts. This makes it impossible for an adversary, who does not possess this secret, to create valid ciphertexts that would interact correctly with the decryption process.

The challenge in implementing Hidden ICKE is to achieve this security enhancement while preserving the crucial key aggregate property needed for confined search across multiple writers. Hermes achieves this by securely setting up correlations between any two writers. While the intricate mathematical details are deferred to the paper, the high-level mechanism ensures that:

• The confidentiality and anonymity of the ciphertexts are maintained.
• The hidden ID for the aggregated key ensures that the origin of a ciphertext cannot be trivially linked back to a specific writer without proper authorization, further bolstering privacy.

By preventing adversaries from generating valid "test" ciphertexts, Hidden ICKE effectively thwarts keyword guessing attacks, significantly enhancing the overall security of the system.

Achieving Forward Privacy via Epoch Encoding

Existing HSSE schemes often required writers to periodically rebuild their search indexes to ensure forward privacy—the property that past searches or decryption keys reveal no information about future updates. This rebuilding process incurred substantial overhead, making the system less practical.

Hermes introduces an innovative tree-based epoch encoding mechanism to achieve forward privacy efficiently, eliminating the need for costly rebuilds. The concept can be visualized using a hierarchical binary tree structure. For instance, a three-level binary tree can encode up to seven distinct epochs, where each path (e.g., "1" for left branch, "2" for right branch) uniquely identifies an epoch.

Here's how it works:

• Each epoch is associated with a unique gamma set (Γ). The values within this set are used when a writer creates a ciphertext for that specific epoch.
• When the reader generates a decryption key for a particular epoch, this key is constructed using values from the prefix set (P). The prefix set for an epoch consists of all node values along the path from the root of the tree down to the current epoch's node.
• The cryptographic design ensures a specific relationship: for any epoch E_current, the gamma sets of all previous epochs (E_past < E_current) will contain some value that is also present in the prefix set of E_current. Conversely, the gamma sets of any future epochs (E_future > E_current) will not contain any value present in the prefix set of E_current.
• Consequently, a decryption key created at E_current can successfully decrypt ciphertexts generated in E_current or any E_past, but it cannot decrypt ciphertexts from E_future. This mechanism effectively "cuts off" access to future data, thereby guaranteeing forward privacy without requiring writers to re-index their entire database.

The primary trade-off for this efficiency is an increase in capacity, as the tree depth (denoted by lambda) influences the size of the gamma and prefix sets. However, this is a manageable cost compared to the computational burden of periodic index rebuilds.

Optimizing Search Complexity via Keyword Partitioning

A significant performance bottleneck in prior HSSE schemes was that search complexity, while sublinear in database size, remained linear in the total number of keywords (N). This meant that for each search token, the system would execute a matching decryption operation for every single keyword in the database, leading to slow searches in keyword-rich environments.

Hermes tackles this by employing a sophisticated keyword partitioning strategy to reduce search complexity from linear to sublinear. The core idea is to hierarchically organize keywords, allowing for more targeted searches.

The process involves:

1. Initial Partitioning: The entire set of keywords (N) is divided into approximately sqrt(N) partitions. Each of these partitions, in turn, contains roughly sqrt(N) keyword items.
2. Two-Phase Search Tokens: To perform a search, two distinct search tokens are generated:

• One token is used for partition matching, identifying which of the sqrt(N) partitions are relevant to the query.
• The second token is then used for keyword matching within the identified relevant partitions.

By doing so, the search complexity is reduced from O(N) to O(sqrt(N)).

1. Recursive Partitioning for Further Optimization: If the size of the partitions after the initial step is still deemed too large (e.g., for extremely large N), this partitioning strategy can be applied recursively. The process continues until each final partition contains a manageable number of items, typically around log N keywords.

This recursive approach leads to a highly optimized search complexity of O(log² N / log log N).

The trade-off for this dramatic improvement in search speed is a proportional increase in the size of the search token, which grows based on the number of partitioning levels. However, the performance benefits, particularly for large keyword sets, far outweigh this increase in token size.

Collectively, these three technical innovations—Hidden ICKE, tree-based epoch encoding, and recursive keyword partitioning—form the bedrock of Hermes, enabling it to deliver a multi-writer encrypted database that is both highly secure and exceptionally efficient.

Demo / Proof of Concept

▶ Watch: Optimizing search complexity to sublinear via partitioning (8:00)

While the presentation did not include a live demonstration or a detailed walkthrough of a proof-of-concept setup, the speaker provided compelling performance comparisons that serve as empirical validation of Hermes's design superiority. These comparisons were made against "forward private hybrid search encryption," which represents the state-of-the-art prior to Hermes.

The key performance metrics highlighted were:

• Keyword Search Performance: Hermes demonstrated a remarkable improvement, achieving up to two orders of magnitude faster search times. This means Hermes can perform searches up to 100 times quicker than its predecessors, directly validating the effectiveness of its optimized search complexity via keyword partitioning.
• Update Performance: For operations involving data updates, Hermes significantly reduced the overhead on the writer side. It was shown to execute updates 4 to 17 times faster than the compared scheme. This substantial improvement is attributed to Hermes's innovative epoch encoding method for forward privacy, which eliminates the need for costly periodic index rebuilds.

These quantitative results provide strong evidence that Hermes not only enhances security but also delivers substantial practical performance gains, making it a viable and attractive solution for real-world applications.

Defensive Implications

▶ Watch: Hermes performance and security comparison (9:20)

The advancements introduced by Hermes have profound implications for organizations and individuals seeking to secure their data in multi-writer cloud environments. For defenders (security architects, data privacy officers, system administrators), Hermes offers a blueprint and a compelling set of features to consider when designing or evaluating secure cloud storage solutions.

1. Mitigation of Keyword Guessing Attacks: The most immediate defensive implication is the enhanced protection against keyword guessing attacks. Organizations can adopt searchable encryption solutions incorporating principles like Hidden ID Coupling Key Aggregate Encryption (Hidden ICKE) to prevent adversaries from inferring sensitive keywords through brute-force or dictionary attacks. This is crucial for data types where keywords themselves might be sensitive (e.g., patient names, project codenames).

1. Efficient Forward Privacy: The tree-based epoch encoding mechanism for forward privacy is a game-changer. Defenders no longer have to choose between robust forward privacy and prohibitive operational overhead (due to frequent index rebuilds). They can now implement systems that guarantee future data confidentiality without imposing a heavy burden on writers or requiring complex, resource-intensive maintenance schedules. This simplifies compliance with data retention and privacy regulations.

1. Scalable and Performant Search: The optimized sublinear search complexity (O(log² N / log log N)) means that encrypted databases can scale to accommodate vast numbers of keywords without suffering from crippling search latency. Defenders can confidently deploy Hermes-like solutions in applications requiring fast retrieval over large, collaborative datasets, such as enterprise document management systems, secure communication platforms, or medical record databases. The demonstrated performance gains (up to 100x faster search) translate directly into improved user experience and operational efficiency.

1. Multi-Writer Collaboration with Strong Guarantees: Hermes provides a secure foundation for multi-writer scenarios where multiple parties contribute data to a shared, encrypted repository. This enables collaborative workflows without the need for complex key distribution or synchronization protocols among writers, which simplifies security management and reduces the attack surface. Defenders should prioritize solutions that offer robust multi-writer support with cryptographic assurances like those provided by Hermes.

1. Informed Solution Evaluation: When selecting encrypted database solutions, defenders should move beyond basic encryption capabilities and scrutinize the specific security guarantees and performance characteristics. Key questions to ask include: Is the solution vulnerable to keyword guessing attacks? How does it handle forward privacy, and what is the associated overhead? What is the search complexity for large datasets? Hermes provides a benchmark for what is achievable in these areas.

In essence, Hermes empowers defenders to implement more secure, more efficient, and more scalable encrypted database systems, striking a better balance between data privacy and practical utility in the cloud.

Key Takeaways

• Hermes is a novel multi-writer searchable encrypted database that significantly advances the state-of-the-art in hybrid searchable encryption (HSSE).
• It achieves robust security against keyword guessing attacks through the introduction of Hidden ID Coupling Key Aggregate Encryption (Hidden ICKE), embedding writer-specific secrets into ciphertexts.
• Search complexity is dramatically optimized to O(log² N / log log N) (where N is the number of keywords) via a recursive keyword partitioning strategy, leading to up to two orders of magnitude faster search performance.
• Forward privacy is ensured efficiently using a tree-based epoch encoding mechanism, eliminating the need for costly periodic index rebuilds and resulting in 4 to 17 times faster update operations.
• Hermes provides a practical and cryptographically sound solution for secure, collaborative data storage in untrusted cloud environments, balancing confidentiality, multi-writer support, and efficient searchability.
• The work addresses key drawbacks of previous HSSE schemes, making it a superior choice for organizations requiring high security and performance for encrypted cloud data.

About the Speaker(s)

Tung Le is a researcher from Vina Tech who presented the work on Hermes. His presentation clearly articulated the technical challenges in searchable encryption and the innovative solutions proposed by Hermes.

Thang Hoang is Tung Le's advisor and a co-author of the Hermes paper. As an advisor, Thang Hoang played a crucial role in guiding the research and development of this advanced multi-writer encrypted database system.