Advanced Data Security: Challenges of Encrypted Database Indexing and Secure Retrieval with Datasafe

Our previous article, Understanding the Problem of Data at Rest, explored how Datasafe provides end-to-end encryption, modular storage backend support, and secure file sharing. In pursuit of securing sensitive information, encrypting data at rest is an essential strategy. However, encryption introduces its own set of challenges, particularly when it comes to efficient data access and management. This article dives into the complexities of managing encrypted data, focusing on indexing, lookups, and maintaining integrity constraints while exploring innovative solutions such as the concept of realms in encrypted data systems.

The Challenges of Encrypted Data

Encrypted databases protect data against unauthorized access, even if the physical medium is compromised. While encryption adds a robust security layer, it disrupts conventional database operations:

1. Indexing Challenges

• Indexes are essential for fast data retrieval. However, encrypting data obfuscates its content, rendering traditional indexing mechanisms ineffective.

• Encrypted data does not support direct indexing without leaking sensitive information about the data.

2. Lookup Issues

• Searching for specific records in encrypted databases requires decrypting large portions of data, which is computationally expensive and time-consuming.

• Traditional lookup operations such as SELECT  queries with conditions become infeasible without specialized techniques.

3. Integrity Constraints Between Records

• Relationships between records, such as foreign keys in relational databases, rely on shared identifiers. Encryption obscures these identifiers, breaking referential integrity.

• Maintaining integrity in encrypted databases requires additional mechanisms to validate relationships securely.

The Concept of Realms: A Solution for Consistency and Security

One innovative approach to addressing these challenges is the realm-based model. A realm is a self-contained unit of encryption that maintains internal consistency and supports explicit management of indexes and relationships.

1. What is a Realm?

• A realm is a cluster of encrypted records logically grouped based on their relationship or access pattern.

• Each realm has its encryption key, allowing for granular control over data access.

2. Benefits of Realms

• Efficient Indexing: Indexes can be explicitly built within a realm, ensuring fast access to related records without exposing data outside the realm.

• Scoped Consistency: Realms enforce integrity constraints internally, avoiding the complexities of cross-realm relationships.

• Access Control: Realm-specific keys allow fine-grained access management, ensuring that only authorized users can decrypt and manipulate the data.

Explicit Index Building at the Application Level

Traditional indexing is abstracted within database systems, but with encrypted databases, explicit indexing at the application level is necessary.

1. Custom Index Structures

• Applications can build indexes for encrypted data, storing metadata such as hash values or encrypted pointers.

• These indexes reside outside the encrypted realm but are secured to prevent leaking sensitive information.

2. Indexed Lookup with Encryption

• Encrypted indexes allow applications to locate records without decrypting the entire database.

• Hash-based indexing is one approach, where queries match hash values rather than plaintext data.

3. Balancing Security and Performance

• Explicit indexing introduces overhead at the application level, but it ensures that sensitive data remains protected.

Re-Imagining Integrity Constraints

Maintaining relationships between encrypted records requires rethinking traditional integrity constraint mechanisms.

1. Realm-Scoped Constraints

• Integrity constraints are enforced within realms, reducing the complexity of managing cross-realm relationships.

• For example, foreign keys in encrypted tables are replaced by application-managed references within the same realm.

2. Application-Level Constraint Validation

• Applications are responsible for validating relationships during operations like insertions or updates.

• Validation is performed using encrypted metadata or hashes stored alongside records.

3. Preventing Data Duplication and Inconsistency

• Explicit constraints ensure that records remain unique and consistent within their respective realms, mitigating risks introduced by encryption.

Datasafe Cli : Encrypted Indexing and Lookups

To illustrate these principles, let’s use Datasafe, an encrypted storage and access management tool. We will demonstrate how to:

1. Creating a user profile in Datasafe

2. Encrypting and storing indexed data

3. Performing a secure lookup using hashed indexing

1. Setting Up a User Profile in Datasafe

Download CLI executable:

1. MacOS native executable

2. Linux native executable

3. Windows executable (N/A yet), please use java version below

4. Java-based jar, requires JRE (1.8+), use java -jar datasafe-cli.jar to execute

(Files above are built from feature/datasafe-cli-w-s3 currently)
Next, create a credentials file with your user details:

Now, initialize the user profile:

This sets up an encrypted storage space for Alice.

2. Encrypting and Storing Indexed Data

To store data securely using an index, generate a hashed identifier for the record:

Now, encrypt and store the record using the hashed index:

3. Performing an Encrypted Lookup

To search for a record, hash the query and attempt to retrieve the indexed file