一句话：提出软硬件协同设计，用数据打包与闪存内处理加速同态加密字符串匹配。
针对同态加密字符串匹配因复杂同态操作和密文膨胀导致的高延迟与数据移动瓶颈，论文提出 CIPHERMATCH。该方法改进现有 HE 方案的数据打包，降低加密后内存占用，并仅使用同态加法完成安全字符串匹配；进一步设计基于 NAND 闪存的 in-flash processing 架构，利用阵列级与位级并行加速同态加法。评估涵盖 DNA 精确匹配与加密数据库搜索两个案例。纯软件版本相比最先进软件基线性能提升 42.9 倍、能耗降低 17.6 倍；与 IFP 集成后相比纯软件 CIPHERMATCH 性能提升 136.9 倍、能耗降低 256.4 倍。
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. CIPHERMATCH improves the software-based data packing scheme of an existing HE scheme and performs secure string matching using only homomorphic addition. This packing method reduces the memory footprint after encryption and improves the performance of the algorithm. To reduce the data movement overhead, we design an IFP architecture to accelerate homomorphic addition by leveraging the array-level and bit-level parallelism of NAND-flash-based solid-state drives (SSDs). 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.9× and 17.6×, respectively, compared to the state-of-the-art software baseline. Integrating CIPHERMATCH with IFP improves performance and reduces energy consumption by 136.9× and 256.4×, respectively, compared to the software-based CIPHERMATCH implementation.
@inproceedings{abs-2503-08968,
title = {CIPHERMATCH: Accelerating Homomorphic Encryption-Based String Matching via Memory-Efficient Data Packing and In-Flash Processing},
author = {Mayank Kabra and Rakesh Nadig and Harshita Gupta and Rahul Bera and Manos Frouzakis and Vamanan Arulchelvan and Yu Liang and Haiyu Mao and Mohammad Sadrosadati and Onur Mutlu},
booktitle = {ASPLOS},
year = {2025},
doi = {10.1145/3676641.3716251}
}