Source-linked AI summary
CIPHERMATCH: Accelerating Homomorphic Encryption-Based String Matching via Memory-Efficient Data Packing and In-Flash Processing
Mayank Kabra, Rakesh Nadig, Harshita Gupta, Rahul Bera, Manos Frouzakis, Vamanan Arulchelvan, Yu Liang, Haiyu Mao, Mohammad Sadrosadati, Onur Mutlu
TL;DR
Homomorphic string matching faces computational costs from complex operations and data-movement costs from large encrypted databases. CIPHERMATCH combines optimized packing and addition-only matching with in-flash processing; its software and IFP implementations report substantial performance and energy improvements across two case studies.
Problem
Prior HE-based string matching faces costly homomorphic operations and data movement of encrypted databases that can be much larger than plaintext data.
Source: §1 · pp. 1–2Method
CIPHERMATCH optimizes data packing, performs matching using only homomorphic addition, and uses an IFP architecture to reduce data movement.
Source: §1 · p. 2Results
42.9× performance and 17.6× energy improvements over the state-of-the-art software baseline; CM-IFP improves performance 136.9× and reduces energy consumption 256.4× versus CM-SW.
Source: §1 · p. 2Takeaways & Limitations
The paper demonstrates CIPHERMATCH in exact DNA string matching and encrypted database search using software and IFP implementations.
Source: §1 · p. 2Prior HE accelerators that compute in the SSD controller remain constrained by flash-memory bandwidth and controller compute capability and parallelism under power limits.
Source: §3.3 · p. 6
Abstract
from arXiv · showhide
Homomorphic encryption (HE) allows secure computation on encrypted data without revealing the original data, providing significant benefits for privacy-sensitive applications. Many cloud computing applications (e.g., DNA read mapping, biometric matching, web search) use exact string matching as a key operation. However, prior string matching algorithms that use homomorphic encryption are limited by high computational latency caused by the use of complex operations and data movement bottlenecks due to the large encrypted data size. In this work, we provide an efficient algorithm-hardware codesign to accelerate HE-based secure exact string matching. We propose CIPHERMATCH, which (i) reduces the increase in memory footprint after encryption using an optimized software-based data packing scheme, (ii) eliminates the use of costly homomorphic operations (e.g., multiplication and rotation), and (iii) reduces data movement by designing a new in-flash processing (IFP) architecture. We demonstrate the benefits of CIPHERMATCH using two case studies: (1) Exact DNA string matching and (2) encrypted database search. Our pure software-based CIPHERMATCH implementation that uses our memory-efficient data packing scheme improves performance and reduces energy consumption by 42.9X and 17.6X, respectively, compared to the state-of-the-art software baseline. Integrating CIPHERMATCH with IFP improves performance and reduces energy consumption by 136.9X and 256.4X, respectively, compared to the software-based CIPHERMATCH implementation.
1. Introduction
CIPHERMATCH addresses the computational and data-movement costs of homomorphic-encryption-based exact string matching with optimized packing, addition-only matching, and in-flash processing. Its software and IFP implementations are evaluated on DNA matching and encrypted database search.
1. Introduction
- HE supports computation on encrypted data without decryption, which is relevant to exact matching in privacy-sensitive applications such as DNA, biometrics, and databases.The introduction identifies shared-computing environments as a setting where sensitive data can be vulnerable to threats and leaks.Source: §1 · p. 1
- Prior arithmetic approaches reduce encrypted-data footprint but use costly multiplication and rotation, while moving encrypted databases can add substantial overhead.Encrypted databases can be up to 1000× larger than their unencrypted counterparts, and prior packing schemes also limit efficient use of near-data architectures.Source: §1 · pp. 1–2
- CIPHERMATCH optimizes arithmetic data packing, uses only homomorphic addition for matching, and moves computation into storage with a new IFP design.The IFP architecture accelerates homomorphic addition by exploiting NAND-flash array-level and bit-level parallelism.Source: §1 · p. 2
- 42.9× performance and 17.6× energy improvements over the state-of-the-art software baseline; CM-IFP improves performance 136.9× and reduces energy consumption 256.4× versus CM-SW.The evaluation uses exact DNA string matching and encrypted database search.Source: §1 · p. 2
- CIPHERMATCH presents IFP for HE operations and evaluates software and IFP implementations on DNA matching and encrypted database search.The paper characterizes its IFP design as the first to exploit in-flash processing for HE operations.Source: §1 · p. 2
2. Background
The background introduces HE and the BFV scheme, explains Boolean and arithmetic approaches to secure string matching, and describes NAND-flash and SSD organization.
2.1. Homomorphic Encryption
- HE permits computation on ciphertext without decryption; this work uses BFV, a Ring-LWE scheme operating on polynomial rings with parameters set for the security level.BFV represents plaintexts and ciphertexts in rings with different coefficient moduli.Source: §2.1 · p. 2
- BFV key generation produces secret and public keys, encoding maps a message to a plaintext polynomial, and encryption outputs a ciphertext pair.Homomorphic addition is coefficient-wise addition of corresponding ciphertext polynomials.Source: §2.1 · pp. 2–3
2.2. Secure String Matching Algorithm
- Exact string matching is used in databases and bioinformatics, while HE offers noninteractive encrypted search with low communication complexity and no data leakage beyond maximum data size.The passage contrasts these HE properties with leakage in searchable-encryption approaches.Source: §2.2 · p. 3
- The Boolean approach encrypts individual bits and uses homomorphic XNOR and AND, whereas the arithmetic approach packs multiple bits and uses multiplication and addition to compute Hamming distance.Boolean matching supports arbitrary query lengths; the arithmetic approach is limited to specific query lengths by its packing and computation constraints.Source: §2.2 · p. 3
2.3. Basics of NAND Flash Architecture
- NAND cells form strings, sub-blocks, blocks, planes, dies, and chips; wordlines connect cells at the same vertical position for concurrent operation.A plane shares bitlines, and multiple dies operate independently while sharing channel buses.Source: §2.3 · p. 3
- NAND reads use bitline precharge and a wordline read voltage, then latch the bitline value; SSDs combine a controller, flash controllers, DRAM, and a host interface.The SSD controller manages the flash translation layer, while DRAM caches logical-to-physical mappings and metadata.Source: §2.3 · pp. 3–4
m WL
Near-data processing performs computation where data resides, including in main memory or storage. The background describes storage-access bottlenecks and distinguishes in-storage from in-flash processing.
2.4. Near-Data Processing
- Near-data processing includes processing-in-memory approaches, such as PuM and PnM, and processing-in-storage approaches, such as ISP and IFP.PuM uses memory circuitry, while PnM adds processing elements inside or near main memory.Source: §2.4 · p. 4
- With growing datasets, PIM approaches can be bottlenecked by SSD access because loading application data from storage to main memory takes significant time.The passage identifies limited SSD I/O bandwidth and high access latency as contributing conditions.Source: §2.4 · p. 4
- ISP offloads tasks to an in-storage accelerator or SSD-controller cores, while IFP exploits NAND-flash cells and circuitry for massively parallel computation.The passage describes IFP benefits relative to ISP for applications using bulk-bitwise operations.Source: §2.4 · p. 4
- Prior NDP-based approaches have been proposed to accelerate HE by using NDP architectures’ parallelism and low-latency memory access.The passage directs readers to a later discussion of those approaches’ limitations.Source: §2.4 · p. 4
3. Motivation
The section motivates secure exact string matching by identifying computational costs, encrypted-data movement, and limitations in prior HE approaches. It proposes optimized packing and in-flash processing as responses to these challenges.
3.1. Limitations of Prior Approaches
- 600× higher execution time for the Boolean approach and 98.2% of arithmetic latency from multiplication motivate reducing costly HE operations.The comparison averages execution time across database sizes and query lengths; arithmetic packing also reduces encryption-related memory growth relative to Boolean encryption.Source: §3.1 · p. 5
3.2. Benefits of Near-Data Processing
- For a 256GB encrypted database, SSD-controller processing reduces data-transfer latency by 94%, versus 6% for DRAM processing.Across all database sizes, SSD-controller processing reduces transfer latency by over 80% compared with CPU processing.Source: §3.2 · p. 6, Figure 3 · p. 6
3.3. Limitations of Prior HE Accelerators
- Prior HE accelerators face limits from SSD-to-memory transfers, unoptimized data packing, flash bandwidth, and power-constrained controller compute.Existing on-chip storage may also be insufficient for string matching on large encrypted databases.Source: §3.3 · p. 6
3.4. Our Goal
- The proposed goal is an IFP-based hardware-software codesign combining memory-efficient packing, simpler homomorphic operations, and reduced data movement.The design seeks to enable bit-parallel operation while reducing costly homomorphic multiplication and exploiting computation near the data.Source: §3.4 · p. 6
4. CIPHERMATCH: Design
CIPHERMATCH’s design combines memory-efficient packing and addition-only encrypted string matching with in-flash processing and SSD integration. It performs search across parallel NAND wordlines, with SSD-controller transposition and match-index generation overlapped with flash reads.
4.1. Overview.
- CIPHERMATCH co-designs a memory-efficient packing scheme and addition-only secure matching algorithm with IFP and SSD system design to reduce encrypted-data footprint and data movement.The hardware includes IFP to accelerate matching and an end-to-end design for enabling CIPHERMATCH in SSDs.Source: §4.1 · p. 6
4.2. Algorithm Design.
- The algorithm is illustrated with n = 1024, q = 32, and t = 16, but can be adapted to any homomorphic-encryption parameters defined by HE standards.The plaintext polynomial has degree 1024 with 16-bit coefficients; encryption produces ciphertext polynomials with 32-bit coefficients.Source: §4.2 · pp. 6–7
4.2.1. Memory-Efficient Data Packing Scheme.
- Encrypted data is only 4× larger than plaintext, versus 64× for prior single-bit packing, a 16× reduction in memory overhead.The 4× increase comes from a 2× increase when plaintext becomes tuples and another 2× increase in ciphertext coefficient size; the comparison assumes maximum possible packed bits per plaintext coefficient.Source: §4.2.1 · p. 7
4.2.2. Secure String Matching Algorithm.
- CIPHERMATCH matches encrypted strings using homomorphic addition alone: it adds packed ciphertexts for the negated query and input, then identifies matches by comparing the result with an encrypted match polynomial.A matching coefficient indicates a match, and its position provides the location index.Source: §4.2.2 · p. 7
4.3. Hardware Design.
- CIPHERMATCH’s hardware design combines an IFP architecture for efficient bitwise operations and bit-serial homomorphic addition with end-to-end SSD integration.The IFP approach is designed to reduce the data-movement bottleneck.Source: §4.3 · p. 8
4.3.1. In-Flash Processing (IFP) Architecture.
- CIPHERMATCH’s IFP performs bit-serial homomorphic addition in flash using bitwise operations and latch transfers, with a vertical layout that keeps carry bits available across bit positions.It uses TLC NAND in SLC mode for reliable operations and performs the addition in latches, avoiding program/erase cycles in the flash array.Source: §4.3.1 · pp. 9–10
4.3.2. End-to-End System Design.
- The SSD system prepares encrypted queries and match polynomials at the client, runs a flash-command µ-program for homomorphic addition, and returns the match index to the client.The CIPHERMATCH storage region uses vertical data layout and SLC mode, with controller transposition and separate address mapping to support storage and host I/O.Source: §4.3.2 · pp. 10–11
- CIPHERMATCH uses parallel NAND wordlines for in-flash bop_add search and overlaps SSD-controller transposition and match-index generation with flash reads.Software transposition handles CM-read and CM-write operations and page faults at 4KB NAND-page granularity; its 13.6µs latency is below flash-read latency, while index generation is estimated at 3.42µs and can overlap sequential reads.Source: §4.3.2 · p. 11
5. Methodology
CIPHERMATCH is evaluated on a real CPU system and through simulation of compute-, memory-, storage-, and flash-centric designs. Workloads cover exact DNA matching and encrypted database search across varied query and database sizes.
5. Methodology
- The methodology combines real-system measurement of software CIPHERMATCH with simulation of its near-data-processing implementations.The real CPU system has six out-of-order cores, 32 GB DDR4-2400 memory, and a PCIe 4.0 NVMe SSD.Source: §5 · p. 11, §5.1 · p. 11
5.1. Real System Evaluation Methodology
- CM-SW is compared with Boolean and arithmetic approaches; execution time covers homomorphic operations, while energy is estimated from Intel RAPL power parameters and measured execution time.The comparison uses TFHE-rs for the Boolean approach and Microsoft SEAL for the arithmetic approach and CM-SW.Source: §5.1 · pp. 11–12
5.2. Simulation-Based Evaluation Methodology
- The simulations compare CM-SW, external-DRAM CM-PuM, SSD-internal-DRAM CM-PuM-SSD, and NAND-flash CM-IFP using models of computation and data-movement latency.CM-PuM uses SIMDRAM-based bit-serial addition; CM-IFP models flash operations, latch transfers, NAND reads, and controller tasks.Source: §5.2 · p. 12
5.3. Workloads
- The workloads include single-query DNA matching with 16–256-bit queries and 128 GB encrypted databases, plus 1,000-query database search across encrypted databases from 8 GB to 128 GB.The encrypted DNA workload starts from a 32 GB database; database-search workloads test cases where the encrypted data fits in DRAM and where it must be fetched from SSD.Source: §5.3 · p. 13
6. Evaluation
Across software and hardware evaluations, CIPHERMATCH outperforms prior approaches and its hardware implementations outperform CM-SW. CM-IFP provides the highest average performance across query and database sizes, with tradeoffs that depend on database capacity and query size.
6.1.1. Effect of Query Size.
- Across different query sizes, CM-SW outperforms arithmetic by 20.7–62.2× and Boolean approaches by 2.0×105–6.2×105×, according to the reported evaluation.CM-SW’s speedup over the arithmetic approach rises from 20.7× to 30.7× as query size increases from 16 bits to 32 bits.Source: §6.1.1 · p. 13
6.1.2. Effect of Database Size.
- 62.2–72.1× and 7.6×10^4–8.8×10^4×: CM-SW outperforms the arithmetic and Boolean approaches across encrypted database sizes.When the database exceeds 32 GB, CM-SW’s performance improvement reduces by 1.16× as per-query I/O transfers increase; prior approaches saturate memory footprint beyond external DRAM even for smaller databases.Source: Figure 9 · p. 13, §6.1.2 · p. 14
6.2.1. Effect of Query Size.
- 76.6–216.0×, 81.7–105.8×, and 26.4–53.9×: CM-IFP, CM-PuM-SSD, and CM-PuM outperform CM-SW across query sizes.CM-IFP outperforms CM-PuM-SSD by 2.89–4.03×, but for 256-bit queries CM-PuM achieves 1.21× higher performance than CM-IFP; CM-IFP has the highest average performance.Source: Figure 10 · p. 14, §6.2.1 · p. 14
- 156.2–454.5×, 49.1–111.8×, and 48.6–98.3×: CM-IFP, CM-PuM-SSD, and CM-PuM reduce energy consumption compared to CM-SW across query sizes.CM-IFP provides the highest average energy savings, while CM-PuM-SSD is 1.06× more energy efficient on average than CM-PuM.Source: Figure 11 · p. 14, §6.2.1 · p. 14
6.2.2. Effect of Database Size.
- 250.1–295.1×, 52.8–62.3×, and 35.6–353.4×: CM-IFP, CM-PuM-SSD, and CM-PuM outperform CM-SW across encrypted database sizes.For databases above 32 GB, CM-IFP achieves 8.29× higher performance than CM-PuM; CM-IFP has the highest average performance across database sizes.Source: Figure 12 · p. 14, §6.2.2 · pp. 14–15
6.3. Overhead Analysis of CM-IFP
- CM-IFP modifies NAND-flash peripheral circuitry with about 0.6% die-area overhead and uses 0.5 MB of SSD-internal DRAM for addition results plus less than 1 KB for its µ-program.The stated storage overhead also includes partitioning the SSD between SLC-mode CIPHERMATCH and conventional TLC-mode regions.Source: §6.3 · p. 15
7. Discussion
The discussion considers hardware acceleration for data transposition and secure transmission of match indices. It describes the implementation costs and the conditions under which dedicated transposition hardware may be useful.
7.1. Hardware-Based Data Transposition Unit
- A hardware transposition unit processes 4 KB in 158 ns and adds 0.24 mm²; it is proposed for flash technologies whose read latency falls enough that software transposition cannot be hidden.The existing software transposition can be overlapped with 22.5 µs flash reads; the paper cites 3 µs for Z-NAND as an example motivating acceleration.Source: §7.1 · p. 15
7.2. Mitigation Techniques for Privacy Concerns
- The SSD encrypts returned match indices with a 256-bit AES module; its key is transferred offline under public-key encryption so that key-transfer cost can be amortized.The AES unit encrypts 16 bytes in an estimated 12.6 ns and adds 0.13 mm².Source: §7.2 · p. 15
8. Related Work
CIPHERMATCH combines homomorphic encryption with software and hardware methods for secure string matching. The related work contrasts it with searchable-encryption and near-data-processing approaches.
8. Related Work
- CIPHERMATCH is presented as the first in-flash processing system designed to accelerate secure exact string matching.The paper compares its software and hardware implementations with Boolean and arithmetic HE-based approaches.Source: §8 · p. 15
- SSE-based string-matching schemes use conventional encryption techniques but exhibit leakage profiles that can leave them vulnerable to plaintext-recovery attacks.The passage contrasts this with HE, which it describes as based on strong mathematical foundations and proven secure.Source: §8 · p. 16
- Prior memory-centric HE processing can still move data from storage when datasets exceed main memory, while FPGA approaches near storage are described as constrained by computational capability and NAND-flash bandwidth.CIPHERMATCH instead performs homomorphic addition within NAND flash, reducing data movement while using array-level and bit-level parallelism.Source: §8 · p. 16
9. Conclusion
CIPHERMATCH combines memory-efficient data packing with in-flash processing to accelerate secure exact string matching. Its evaluation reports performance improvements and energy savings over state-of-the-art approaches.
9. Conclusion
- CIPHERMATCH’s packing scheme reduces encrypted-data memory footprint and eliminates costly homomorphic multiplication.The system’s two key components are the packing scheme and an in-flash processing architecture.Source: §9 · p. 16
- Its in-flash processing architecture exploits NAND-flash array-level and bit-level parallelism for parallel string matching through homomorphic computations.The architecture requires only small modifications to NAND flash chips in commodity SSDs.Source: §9 · p. 16
- CIPHERMATCH’s software-based and hardware-accelerated implementations provide performance improvements and energy savings over state-of-the-art approaches.Source: §9 · p. 16