CIPHERMATCH: Accelerating Homomorphic Encryption-Based String Matching via Memory-Efficient Data Packing and In-Flash Processing

Encryption that lets a cloud server search your data without ever decrypting it would solve a real problem for genomics and biometrics, except that searching a 32-byte database for a 32-bit pattern this way takes 6.6 seconds against 5.9 microseconds in the clear; CIPHERMATCH (ETH Zurich and King's College London) finds a way to do exact matching using only addition rather than multiplication, packs sixteen times more data into each encrypted value, and then does the addition inside the flash chips themselves so the enormous ciphertexts never have to move.

Why this problem is worth solving

The technique delivers exactly what is wanted and charges twice for it.

The size penalty is largely a consequence of a choice nobody was forced to make.

What people did before, and where it broke

• Encrypt each bit separately and use Boolean operations. Encrypt every bit into its own polynomial, then compute with homomorphic exclusive-nor and and. It handles any query length and keeps the accumulated noise controlled. Where it broke. Both costs at once. The encrypted form is over 200 times larger than the plaintext, and a single search must traverse that entire inflated database performing expensive operations on individually encrypted bits — measured as roughly 600 times slower than the arithmetic alternative.
• Pack several bits per polynomial and compute a Hamming distance. The arithmetic approach, which is much faster and much smaller because one ciphertext holds many bits. Where it broke. The distance formulation requires two homomorphic multiplications and three additions per comparison, and multiplication is the expensive operation — measured at 98.2 percent of the total latency. It also only supports particular query lengths.
• Return only the matching result rather than one ciphertext per chunk. A refinement addressing the fact that the previous approach returns as many ciphertexts as the database was split into, which does not scale. Where it broke. The circuit that achieves it needs multiplication, rotation and further operations, so the scalability is bought with even more latency.
• Add vectorised batching and compression on top. A further refinement improving throughput. Where it broke. The expensive operations remain, and query sizes are still constrained.
• Build a large accelerator with a big on-chip buffer. Published designs dedicate 180 to 512 megabytes of on-chip storage to avoid going off-chip. Where it broke. Even half a gigabyte is not enough for an encrypted database of any size, and increasing either on-chip storage or off-chip bandwidth further is expensive.
• Move the computation near main memory, or into the drive controller. Near-data processing to cut the movement cost. Where it broke. Placing it near memory still requires pulling the database off storage first, which dominates once it exceeds memory. Placing it in the drive controller is limited by flash channel bandwidth and by how much computation fits in the controller power budget.
• The gap. Everyone treated the packing scheme and the matching algorithm as separate from the hardware question. But the packing determines which operations the algorithm needs, the operations determine whether the work can be done in simple circuits, and only if it can does putting it inside the storage become possible.

How a search becomes an addition inside a flash chip

The idea

The size explosion was largely self-inflicted. The headline complaint about homomorphic encryption is that ciphertext dwarfs plaintext, and the figures quoted in the literature reach a thousandfold. But a large part of that is a packing decision rather than a property of the mathematics. Each coefficient of the plaintext polynomial in this scheme holds sixteen bits, and the prior state of the art placed exactly one bit in each, leaving fifteen sixteenths of the capacity empty before encryption even began. Filling them takes the increase from encryption down to a factor of four — and that residual four decomposes cleanly into two, from a plaintext becoming a ciphertext pair, and two more from the coefficient widening from sixteen bits to thirty-two. That is close to irreducible for this scheme. Getting more real work into each encrypted value, so that the fixed costs of encryption are amortised rather than paid per bit, is exactly the concern of the packing efficiency work covered elsewhere on this site.

Restating equality removes the operation that was 98 percent of the cost. The prior arithmetic formulation computes a Hamming distance between query and data, which needs two multiplications and three additions per comparison, and homomorphic multiplication is measured here at 98.2 percent of total latency. The replacement is a one-line observation about plaintext arithmetic: add a value to the bitwise complement of a pattern and you get all ones precisely when they are equal. Nothing about that requires multiplication, and because homomorphic addition is coefficient-wise it carries into the encrypted domain untouched — a comparison becomes a single homomorphic addition, and finding matches becomes checking the result against an encrypted all-ones polynomial. The packing is what makes it work, since sixteen bits sitting in one coefficient are exactly what the identity operates on. It also eliminates rotation, whose cost is the reason packed representations are awkward to compute with in the first place, as the vectorising compiler work covered elsewhere on this site explains at length.

Reducing the operation to addition is what makes the storage the right place to run it. This is the part where the algorithm and hardware arguments meet, and the order matters: the computation could only be moved into the flash chips because it had first been reduced to something simple enough to express there. A bit-serial addition is a sequence of and, or and exclusive-or operations, and a NAND flash chip already has the machinery — sensing and data latches that hold what a read produced, and, remarkably, an exclusive-or circuit that exists for scrambling data during writes and for error detection during factory testing. Reusing that circuit for arithmetic costs about 0.6 percent of the die area, all of it from making the latch transfers bidirectional. The payoff is the movement saved: for a 256 gigabyte encrypted database, computing in the drive cuts transfer latency by 94 percent while computing in main memory saves only 6, because the data has to come off the flash either way. Putting a cheap filtering operation inside the drive so that only results cross the interface is precisely the shape of the genome sequencing storage work covered elsewhere on this site.

Following one query into the flash array

Preparation happens on the client, so the server never sees the pattern. What reaches the server is a set of ciphertext polynomials that look like noise.

Why it works

• Filling the coefficients is nearly free and pays immediately. Each plaintext coefficient can hold sixteen bits and the prior scheme used one → packing them full shrinks the encrypted representation by the same factor → so both the storage and every byte of data movement fall by sixteen before any other optimisation applies.
• Equality has an additive formulation that survives encryption. Adding a value to the bitwise complement of a pattern gives all ones exactly when they match → homomorphic addition operates coefficient by coefficient, so the identity holds unchanged on ciphertext → which removes the multiplications that measurement attributes 98.2 percent of the latency to.
• Addition composes from operations flash chips can already perform. A bit-serial addition is a sequence of and, or and exclusive-or steps → sensing and data latches can be made to compute those with a small circuit change, and an exclusive-or already exists for scrambling and factory testing → so the arithmetic fits inside the chip rather than requiring a processor.
• Storing values sideways turns a read into a wide parallel operand fetch. Laid out conventionally, a coefficient occupies consecutive bits of one page → laid out vertically, one wordline read yields the same bit position from thousands of values → so the addition runs across the whole array at once and its cost scales with coefficient width rather than database size.
• Where the bottleneck sits depends entirely on whether the data fits in memory. Below the size of main memory a database can be loaded once and reused across queries → above it, every query pays to fetch from storage again → which is why computing in the drive cuts transfer latency by 94 percent at 256 gigabytes while computing in memory saves 6.

What it costs (trade-offs and scope)

• All the hardware results are simulated. The software implementation runs on a real processor, but the in-flash design, the processing-in-memory comparison and the in-drive-controller comparison are all modelled with an in-house simulator using latency and energy figures drawn from prior publications.
• The in-flash design only wins when the database exceeds main memory. Below 32 gigabytes, processing in external memory is 1.41 times faster, because the data can be loaded once and reused across queries. Above it the in-flash design wins by 8.29 times. The paper reports both.
• For a single large query it also loses. At 256-bit query sizes, processing in main memory is 1.21 times faster than in flash, because memory reads are simply quicker than flash reads and there is not enough work to amortise the difference.
• The headline 136.9 times is against the software version, not the best alternative. Averaged over query sizes the in-flash design beats processing in external memory by 1.4 times. The large multiplier compares against a processor doing the same algorithm.
• The search region costs drive capacity. It must be operated at one bit per cell for reliable bitwise operations, while the conventional region uses three. The paper lists this as an overhead without quantifying how much capacity is lost.
• Ordinary reads of the search region are slow. Because data is stored vertically, a page fault there requires reading many wordlines and transposing the result. The design leans on huge pages and a timeout in the fault handler to cope.
• Transposition is only free while flash stays slow. The software transposition takes 13.6 microseconds, comfortably hidden behind a 22.5 microsecond flash read — but the authors note that faster flash, at around 3 microseconds, would require adding a dedicated hardware unit.
• The operation supported is exact matching and nothing else. Genome read mapping is described in the paper itself as using a combination of exact and approximate matching; only the exact half is addressed.
• Both workloads are synthetic. A synthetic genome database and a synthetic encrypted database, with query counts and sizes swept rather than drawn from a real application trace.
• Encryption and encoding time is excluded from the measurements, which report only the time spent in homomorphic operations.
• The design rests on two prior in-flash proposals, contributing the bidirectional latch control on top of one and the reliable single-bit-per-cell programming from the other, so the 0.6 percent area figure is inherited rather than newly established.

The evaluation

Check yourself

Sources

The paper is “CIPHERMATCH: Accelerating Homomorphic Encryption-Based String Matching via Memory-Efficient Data Packing and In-Flash Processing” by Mayank Kabra, Rakesh Nadig, Harshita Gupta, Rahul Bera, Manos Frouzakis, Vamanan Arulchelvan, Yu Liang, Haiyu Mao, Mohammad Sadrosadati and Onur Mutlu, published at ASPLOS 2025, pages 111-130, DOI 10.1145/3676641.3716251. The authors are at ETH Zurich and King’s College London, and an extended version is available.

This explainer is written from the full 20-page text. Everything above comes from the paper’s own sections: the background on the encryption scheme with its ring parameters, key generation, encoding and coefficient-wise addition, the two prior approaches to secure string matching with their respective packing schemes and operation sets, and the internal organisation of a modern solid-state drive down to strings, wordlines, sub-blocks, planes, dies and channels along with sensing and data latches; the motivation comparing the two approaches on execution time, scalability, vectorisation support and query flexibility, with the measured comparison of a small encrypted search against its plaintext equivalent, the memory footprint figures, the 600 times gap between approaches, and the latency breakdown attributing 98.2 percent to multiplication; the data movement study measuring transfer latency to processor, memory and drive controller across database sizes from 8 to 256 gigabytes, and the survey of why existing accelerators and near-memory designs remain bottlenecked; the algorithm design covering the packing scheme with its derivation of the residual size factor, the additive matching identity, the match polynomial, and the client-server procedure for database preparation, query preparation with replication and shifting, and search; the hardware design covering the latch circuitry and the transistor additions enabling bidirectional transfer, the and, or and exclusive-or mechanisms including the reuse of existing scrambling and test circuitry, the bit-serial addition sequence, the vertical data layout, the drive partitioning into two regions, the new commands, the transposition and index generation units, and the handling of page faults; and the evaluation covering the real system and simulated configurations, both workloads, the software and hardware results across query and database sizes with their crossover points, and the overhead analysis for storage, area, transposition and index encryption.