Databases are the backbone of enterprise computation, and they are fundamentally incompatible with encryption. Traditional databases require plaintext access to data for indexing, querying, and joining. Encrypt the data, and the database becomes a write-only vault. You can store encrypted records, but searching them requires decrypting every record and scanning in plaintext, defeating the purpose of encryption entirely.
This incompatibility has forced organizations into an uncomfortable choice: either keep sensitive data in plaintext databases (accepting the breach risk) or encrypt it and lose the ability to search (accepting the functionality loss). Most organizations choose plaintext databases because the business requires queryability. The result is that the most sensitive data in the enterprise, customer records, financial transactions, medical histories, sits in databases that decrypt everything for every query.
Fully homomorphic encryption breaks this compromise. With FHE, queries are evaluated on encrypted data without decryption. The database server processes encrypted queries against encrypted indexes and returns encrypted results. The server never sees the query content, the index values, or the result records. The business gets queryability. Security gets encryption. Both win.
How Encrypted Queries Work
An encrypted database query has three encrypted components: the query itself (what you are looking for), the database index (the structure that enables efficient search), and the result set (the records that match the query). In a fully encrypted query system, all three components remain encrypted throughout the query lifecycle.
The client encrypts the search term using FHE and sends the encrypted query to the database server. The server evaluates the encrypted query against the encrypted index using homomorphic operations. For an exact match query, this involves comparing the encrypted search term against each encrypted index entry using homomorphic equality testing. The comparison produces an encrypted boolean for each entry: encrypted-true for matches, encrypted-false for non-matches.
The encrypted boolean results are then used to select the matching encrypted records. This selection step uses homomorphic multiplication: multiply each record by its corresponding encrypted boolean, and sum the results. Matches contribute their encrypted record to the sum. Non-matches contribute encrypted zeros, which vanish in the sum. The server returns the aggregated encrypted result, and the client decrypts it to obtain the matching records.
This approach has a fundamental property: the server learns nothing about the query, the matching records, or even how many records matched. The computation is oblivious to the data it processes, treating every index entry and every record identically regardless of whether it matches.
Beyond Exact Match: Range and Similarity Queries
Exact match queries are the simplest encrypted query type, but real-world databases require more sophisticated query patterns. Range queries (find all records where a value falls between two bounds), similarity queries (find records close to a query point), and aggregation queries (compute statistics over matching records) are all essential for practical database usage.
Range queries on encrypted data use homomorphic comparison circuits. Given an encrypted lower bound and an encrypted upper bound, the circuit evaluates whether each encrypted index value falls within the range. The comparison is performed bit by bit on the encrypted representation, producing an encrypted boolean result. This is more computationally expensive than an exact match but follows the same oblivious evaluation pattern.
Similarity queries, essential for recommendation systems and approximate matching, use encrypted distance metrics. The encrypted query vector is compared against encrypted database vectors using homomorphic inner product computation. With 4096 SIMD slots, H33 can evaluate similarity between the query vector and 4096 database vectors simultaneously, making encrypted similarity search practical for moderate-sized databases.
Aggregation queries combine encrypted search with encrypted arithmetic. After identifying matching records homomorphically, the system can compute encrypted sums, averages, counts, and other aggregate statistics without revealing individual records. This enables privacy-preserving analytics on encrypted databases: compute business metrics without exposing the underlying data.
Private Information Retrieval
Standard encrypted queries protect the data content but can still leak access patterns. If the server observes which encrypted records are returned (even without knowing their content), it learns which index positions were accessed. Over time, access patterns reveal information about the query distribution, which can be correlated with external knowledge to infer query contents.
Private information retrieval (PIR) eliminates access pattern leakage entirely. In a PIR scheme, the server processes the query against the entire database obliviously, without learning which records matched. The server performs the same operations on every record, regardless of whether it matches the query. The computational cost is proportional to the database size (not the result size), but the privacy guarantee is absolute.
H33 implements PIR using FHE-based oblivious evaluation. The encrypted query is expanded into a selection vector with one encrypted element per database record. The selection vector contains encrypted-one at the position of the desired record and encrypted-zeros everywhere else. The server multiplies each record by its corresponding selection element and sums the products, producing the encrypted target record. Because every record participates in every query, the server cannot distinguish which record was selected.
The computational overhead of PIR is significant for large databases. A database with one million records requires one million homomorphic multiplications per query. H33 mitigates this through SIMD batching: with 4096 SIMD slots, a single ciphertext operation processes 4096 records simultaneously, reducing the effective cost by a factor of 4096. A million-record PIR query requires approximately 244 ciphertext operations rather than one million.
Encrypted Indexing Strategies
Efficient plaintext databases rely on indexing structures (B-trees, hash tables, inverted indexes) to avoid scanning every record for every query. Encrypted databases need analogous structures that work on ciphertexts.
Encrypted B-trees maintain the tree structure in plaintext (since the structure does not reveal data values) but encrypt the key values at each node. Traversing the tree requires homomorphic comparison at each level, comparing the encrypted search key against the encrypted node key to determine which branch to follow. The tree depth is logarithmic in the database size, so the number of homomorphic comparisons per query is logarithmic rather than linear.
Encrypted hash indexes compute the hash function homomorphically on the encrypted search key, producing an encrypted hash value that maps to a bucket. Within the bucket, exact match comparison narrows to the target record. This approach reduces the oblivious scan from the full database to a single bucket, dramatically reducing query cost for exact match lookups.
H33's encrypted search infrastructure selects the indexing strategy based on the query pattern and database characteristics. Exact match queries use encrypted hash indexes. Range queries use encrypted B-trees. Similarity queries use encrypted locality-sensitive hashing. The selection is automatic and transparent to the application developer.
Use Cases for Encrypted Search
Law enforcement and intelligence agencies need to search databases of sensitive records without revealing what they are searching for. An analyst searching for a specific name in a counterterrorism database does not want the database operator to know which name was queried, because the query itself is sensitive intelligence. Encrypted search enables this pattern: the database operator facilitates the search without learning the search terms or results.
Healthcare organizations need to search patient databases for clinical trials, research cohorts, and diagnostic patterns. HIPAA restricts who can access patient records and for what purpose. Encrypted search enables researchers to identify patients matching study criteria without accessing individual patient records. The database returns encrypted aggregate counts or anonymized cohort identifiers, never plaintext patient data.
Financial institutions need to search transaction databases for compliance screening, fraud detection, and sanctions checking. Searching for a sanctioned entity's name in a transaction database reveals the entity being investigated. Encrypted search enables compliance teams to screen transactions without revealing the sanctions list to the transaction database operator.
Cloud database services can offer encrypted search as a premium feature. Customers upload encrypted databases and submit encrypted queries. The cloud service evaluates queries without accessing plaintext data, eliminating the trust requirement that currently prevents organizations from storing their most sensitive data in the cloud.
Performance and Scale
Encrypted database queries are inherently more expensive than plaintext queries. The overhead comes from two sources: the computational cost of homomorphic operations and the ciphertext expansion that increases data transfer.
For small to medium databases (up to millions of records), H33's encrypted search is practical for interactive use. SIMD batching with 4096 slots amortizes the per-record cost, and encrypted indexing reduces the number of records that must be scanned. A hundred-thousand-record database with an encrypted hash index can answer exact match queries with latency measured in tens of milliseconds.
For large databases (billions of records), hybrid approaches combine encrypted search with other privacy techniques. The database is partitioned, and coarse-grained filtering is performed with lightweight techniques (like encrypted Bloom filters) to identify candidate partitions. Fine-grained FHE search is then applied only to the candidate partitions, reducing the computational cost to a practical level.
H33's production pipeline, processing 2,293,766 operations per second at 38 microseconds per operation, provides the raw computational throughput to make encrypted search viable at scale. The challenge is not raw throughput but efficient query planning that minimizes the number of homomorphic operations per query. This is where encrypted indexing and query optimization create the most value.
Encrypted database search is the next frontier after encrypted computation. Organizations have accepted that computation can happen on encrypted data. The next step is accepting that search, the most fundamental database operation, can also happen on encrypted data. H33 is building the infrastructure to make that step practical.