Fast Plaintext-Ciphertext Matrix Multiplication from Additively Homomorphic Encryption

• URL: http://arxiv.org/abs/2504.14497v1
• Date: Sun, 20 Apr 2025 05:28:46 GMT
• Title: Fast Plaintext-Ciphertext Matrix Multiplication from Additively Homomorphic Encryption
• Authors: Krishna Sai Tarun Ramapragada, Utsav Banerjee,
• Abstract summary: Plaintext-ciphertext matrix multiplication is an indispensable tool in privacy-preserving computations.<n>We propose an efficient PC-MM from unpacked additively homomorphic encryption schemes.<n>Our proposed approach achieves up to an order of magnitude speedup compared to state-of-the-art for large matrices with relatively small element bit-widths.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Plaintext-ciphertext matrix multiplication (PC-MM) is an indispensable tool in privacy-preserving computations such as secure machine learning and encrypted signal processing. While there are many established algorithms for plaintext-plaintext matrix multiplication, efficiently computing plaintext-ciphertext (and ciphertext-ciphertext) matrix multiplication is an active area of research which has received a lot of attention. Recent literature have explored various techniques for privacy-preserving matrix multiplication using fully homomorphic encryption (FHE) schemes with ciphertext packing and Single Instruction Multiple Data (SIMD) processing. On the other hand, there hasn't been any attempt to speed up PC-MM using unpacked additively homomorphic encryption (AHE) schemes beyond the schoolbook method and Strassen's algorithm for matrix multiplication. In this work, we propose an efficient PC-MM from unpacked AHE, which applies Cussen's compression-reconstruction algorithm for plaintext-plaintext matrix multiplication in the encrypted setting. We experimentally validate our proposed technique using a concrete instantiation with the additively homomorphic elliptic curve ElGamal encryption scheme and its software implementation on a Raspberry Pi 5 edge computing platform. Our proposed approach achieves up to an order of magnitude speedup compared to state-of-the-art for large matrices with relatively small element bit-widths. Extensive measurement results demonstrate that our fast PC-MM is an excellent candidate for efficient privacy-preserving computation even in resource-constrained environments.

Related papers

• CIPHERMATCH: Accelerating Homomorphic Encryption-Based String Matching via Memory-Efficient Data Packing and In-Flash Processing [8.114331115730021]
  Homomorphic encryption (HE) allows secure computation on encrypted data without revealing the original data. Many cloud computing applications (e.g., DNA read mapping, biometric matching, web search) use exact string matching as a key operation. Prior string matching algorithms that use homomorphic encryption are limited by high computational latency.
  arXiv  Detail & Related papers  (2025-03-12T00:25:58Z)
• 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. This work explores a more efficient alternative: using additively homomorphic encryption (AHE) for privacy-preserving similarity search. 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)
• Improving Algorithmic Efficiency using Cryptography [11.496343300483904]
  We show how to use cryptography to improve the time complexity of solving computational problems.<n>We show that under standard cryptographic assumptions, we can design algorithms that are faster than existing ones.
  arXiv  Detail & Related papers  (2025-02-18T17:08:59Z)
• Cryptanalysis via Machine Learning Based Information Theoretic Metrics [58.96805474751668]
  We propose two novel applications of machine learning (ML) algorithms to perform cryptanalysis on any cryptosystem.<n>These algorithms can be readily applied in an audit setting to evaluate the robustness of a cryptosystem.<n>We show that our classification model correctly identifies the encryption schemes that are not IND-CPA secure, such as DES, RSA, and AES ECB, with high accuracy.
  arXiv  Detail & Related papers  (2025-01-25T04:53:36Z)
• Three-Input Ciphertext Multiplication for Homomorphic Encryption [6.390468088226496]
  Homomorphic encryption (HE) allows computations directly on ciphertexts. HE is essential to privacy-preserving computing, such as neural network inference, medical diagnosis, and financial data analysis. This paper proposes 3-input ciphertext multiplication to reduce complexity of computations.
  arXiv  Detail & Related papers  (2024-10-17T13:40:49Z)
• High-Performance Privacy-Preserving Matrix Completion for Trajectory Recovery [0.897780713904412]
  We propose a high-performance method for privacy-preserving matrix completion. The results of numerical experiments reveal that the proposed method is faster than other algorithms.
  arXiv  Detail & Related papers  (2024-05-09T14:12:41Z)
• 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)
• Encrypted Dynamic Control exploiting Limited Number of Multiplications and a Method using RLWE-based Cryptosystem [0.3749861135832073]
  We present a method to encrypt dynamic controllers that can be implemented through most homomorphic encryption schemes. As a result, the encrypted controller involves only a limited number of homomorphic multiplications on every encrypted data. We propose a customization of the method for Ring Learning With Errors (RLWE)-based cryptosystems, where a vector of messages can be encrypted into a single ciphertext.
  arXiv  Detail & Related papers  (2023-07-07T08:24:48Z)
• Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes [59.55193427277134]
  Reed-Muller (RM) codes achieve the capacity of general binary-input memoryless symmetric channels. RM codes only admit limited sets of rates. Efficient decoders are available for RM codes at finite lengths.
  arXiv  Detail & Related papers  (2023-01-16T04:11:14Z)
• Batch-efficient EigenDecomposition for Small and Medium Matrices [65.67315418971688]
  EigenDecomposition (ED) is at the heart of many computer vision algorithms and applications. We propose a QR-based ED method dedicated to the application scenarios of computer vision.
  arXiv  Detail & Related papers  (2022-07-09T09:14:12Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  We introduce a new inference scheme that avoids explicit construction of the covariance matrix. Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm. On several simulations, our method scales better than existing approaches in computation time and memory.
  arXiv  Detail & Related papers  (2022-02-25T16:35:26Z)
• Sparsifying Parity-Check Matrices [60.28601275219819]
  We consider the problem of minimizing the number of one-entries in parity-check matrices. In the maximum-likelihood (ML) decoding method, the number of ones in PCMs is directly related to the time required to decode messages. We propose a simple matrix row manipulation which alters the PCM, but not the code itself.
  arXiv  Detail & Related papers  (2020-05-08T05:51:40Z)
• Fast Generalized Matrix Regression with Applications in Machine Learning [46.79740387890322]
  We propose a fast generalized matrix regression algorithm (Fast GMR) which utilizes sketching technique to solve the GMR problem efficiently. We apply the Fast GMR algorithm to the symmetric positive definite matrix approximation and single pass singular value decomposition.
  arXiv  Detail & Related papers  (2019-12-27T07:03:37Z)

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.