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

• URL: http://arxiv.org/abs/2503.08968v1
• Date: Wed, 12 Mar 2025 00:25:58 GMT
• Title: CIPHERMATCH: Accelerating Homomorphic Encryption-Based String Matching via Memory-Efficient Data Packing and In-Flash Processing
• Authors: Mayank Kabra, Rakesh Nadig, Harshita Gupta, Rahul Bera, Manos Frouzakis, Vamanan Arulchelvan, Yu Liang, Haiyu Mao, Mohammad Sadrosadati, Onur Mutlu,
• Abstract summary: Homomorphic encryption (HE) allows secure computation on encrypted data without revealing the original data.<n>Many cloud computing applications (e.g., DNA read mapping, biometric matching, web search) use exact string matching as a key operation.<n>Prior string matching algorithms that use homomorphic encryption are limited by high computational latency.
• Score: 8.114331115730021
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Efficient Token Compression for Vision Transformer with Spatial Information Preserved [59.79302182800274]
  Token compression is essential for reducing the computational and memory requirements of transformer models. We propose an efficient and hardware-compatible token compression method called Prune and Merge.
  arXiv  Detail & Related papers  (2025-03-30T14:23:18Z)
• A Note on Efficient Privacy-Preserving Similarity Search for Encrypted Vectors [1.3824176915623292]
  Traditional approaches to vector similarity search over encrypted data rely on fully homomorphic encryption (FHE) to enable computation without decryption.<n>This work explores a more efficient alternative: using additively homomorphic encryption (AHE) for privacy-preserving similarity search.<n>We present an efficient algorithm for encrypted similarity search under AHE and analyze its error growth and security implications.
  arXiv  Detail & Related papers  (2025-02-20T06:07:04Z)
• Hades: Homomorphic Augmented Decryption for Efficient Symbol-comparison -- A Database's Perspective [1.3824176915623292]
  This paper introduces HADES, a novel cryptographic framework that enables efficient and secure comparisons on encrypted data.<n>Based on the Ring Learning with Errors (RLWE) problem, HADES provides CPA-security and incorporates perturbation-aware encryption to mitigate frequency-analysis attacks.
  arXiv  Detail & Related papers  (2024-12-28T02:47:14Z)
• Accelerating Error Correction Code Transformers [56.75773430667148]
  We introduce a novel acceleration method for transformer-based decoders. We achieve a 90% compression ratio and reduce arithmetic operation energy consumption by at least 224 times on modern hardware.
  arXiv  Detail & Related papers  (2024-10-08T11:07:55Z)
• PhD Forum: Efficient Privacy-Preserving Processing via Memory-Centric Computing [0.0]
  Homomorphic encryption (HE) and secure multi-party computation (SMPC) enhance data security by enabling processing on encrypted data. Existing approaches focus on improving computational overhead using specialized hardware. We propose a framework that uses recently available PIM hardware to achieve efficient privacy-preserving computation.
  arXiv  Detail & Related papers  (2024-09-25T09:37:50Z)
• A Method for Efficient Heterogeneous Parallel Compilation: A Cryptography Case Study [8.06660833012594]
  This paper introduces a novel MLIR-based dialect, named hyper, designed to optimize data management and parallel computation across diverse hardware architectures. We present HETOCompiler, a cryptography-focused compiler prototype that implements multiple hash algorithms and enables their execution on heterogeneous systems.
  arXiv  Detail & Related papers  (2024-07-12T15:12:51Z)
• NTTSuite: Number Theoretic Transform Benchmarks for Accelerating Encrypted Computation [2.704681057324485]
  Homomorphic encryption (HE) is a cryptographic system that enables computation directly on encrypted data. HE has seen little adoption due to extremely high computational overheads, rendering it impractical. We develop a benchmark suite, named NTTSuite, to enable researchers to better address these overheads. We find our implementation outperforms the state-of-the-art by 30%.
  arXiv  Detail & Related papers  (2024-05-18T17:44:17Z)
• Lightweight Cryptanalysis of IoT Encryption Algorithms : Is Quota Sampling the Answer? [0.0]
  Two well-known lightweight algorithms are SIMON and SIMECK which have been specifically designed for use on resource-constrained IoT devices. It is necessary to test these algorithms for resilience against differential cryptanalysis attacks. In this paper, we introduce Versatile Investigative Sampling Technique for Advanced Cryptanalysis.
  arXiv  Detail & Related papers  (2024-04-12T00:08:39Z)
• SOCI^+: An Enhanced Toolkit for Secure OutsourcedComputation on Integers [50.608828039206365]
  We propose SOCI+ which significantly improves the performance of SOCI. SOCI+ employs a novel (2, 2)-threshold Paillier cryptosystem with fast encryption and decryption as its cryptographic primitive. Compared with SOCI, our experimental evaluation shows that SOCI+ is up to 5.4 times more efficient in computation and 40% less in communication overhead.
  arXiv  Detail & Related papers  (2023-09-27T05:19:32Z)
• HUSP-SP: Faster Utility Mining on Sequence Data [48.0426095077918]
  High-utility sequential pattern mining (HUSPM) has emerged as an important topic due to its wide application and considerable popularity. We design a compact structure called sequence projection (seqPro) and propose an efficient algorithm, namely discovering high-utility sequential patterns with the seqPro structure (HUSP-SP) Experimental results on both synthetic and real-life datasets show that HUSP-SP can significantly outperform the state-of-the-art algorithms in terms of running time, memory usage, search space pruning efficiency, and scalability.
  arXiv  Detail & Related papers  (2022-12-29T10:56:17Z)
• Automatic and effective discovery of quantum kernels [41.61572387137452]
  Quantum computing can empower machine learning models by enabling kernel machines to leverage quantum kernels for representing similarity measures between data.<n>We present an approach to this problem, which employs optimization techniques, similar to those used in neural architecture search and AutoML.<n>The results obtained by testing our approach on a high-energy physics problem demonstrate that, in the best-case scenario, we can either match or improve testing accuracy with respect to the manual design approach.
  arXiv  Detail & Related papers  (2022-09-22T16:42:14Z)
• New Oracle-Efficient Algorithms for Private Synthetic Data Release [52.33506193761153]
  We present three new algorithms for constructing differentially private synthetic data. The algorithms satisfy differential privacy even in the worst case. Compared to the state-of-the-art method High-Dimensional Matrix Mechanism citeMcKennaMHM18, our algorithms provide better accuracy in the large workload.
  arXiv  Detail & Related papers  (2020-07-10T15:46:05Z)
• Faster Secure Data Mining via Distributed Homomorphic Encryption [108.77460689459247]
  Homomorphic Encryption (HE) is receiving more and more attention recently for its capability to do computations over the encrypted field. We propose a novel general distributed HE-based data mining framework towards one step of solving the scaling problem. We verify the efficiency and effectiveness of our new framework by testing over various data mining algorithms and benchmark data-sets.
  arXiv  Detail & Related papers  (2020-06-17T18:14:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.