Fast Plaintext-Ciphertext Matrix Multiplication from Additively Homomorphic Encryption
Authors
Krishna Sai Tarun Ramapragada, Utsav Banerjee
Krishna Sai Tarun Ramapragada
Electronic Systems Engineering, Indian Institute of Science, Bengaluru, India
krishnasai at iisc dot ac dot in
krishnasai at iisc dot ac dot in
Utsav Banerjee
Electronic Systems Engineering, Indian Institute of Science, Bengaluru, India
utsav at iisc dot ac dot in
utsav at iisc dot ac dot in
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.
References
[AAUC18]
Abbas Acar, Hidayet Aksu, A. Selcuk Uluagac, and Mauro Conti. A Survey on Homomorphic Encryption Schemes: Theory and Implementation. ACM Computing Surveys, 51(4):1-35, 2018. DOI: 10.1145/3214303
[AB22]
Faiek Ahsan and Utsav Banerjee. Embedded Software Implementation of Privacy Preserving Matrix Computation using Elliptic Curve Cryptography for IoT Applications. In IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS). 2022. DOI: 10.1109/ANTS56424.2022.10227758
[ABDCP15]
Michel Abdalla, Florian Bourse, Angelo De Caro, and David Pointcheval. Simple Functional Encryption Schemes for Inner Products. In IACR International Workshop on Public Key Cryptography (PKC), pages 733-751. 2015. DOI: 10.1007/978-3-662-46447-2_33
[ALS16]
Shweta Agrawal, Benoît Libert, and Damien Stehlé. Fully Secure Functional Encryption for Inner Products, From Standard Assumptions. In Annual International Cryptology Conference (CRYPTO), pages 333-362. 2016. DOI: 10.1007/978-3-662-53015-3_12
[AR24]
Aikata Aikata and Sujoy Sinha Roy. Secure and Efficient Outsourced Matrix Multiplication with Homomorphic Encryption. In International Conference on Cryptology in India (Indocrypt), pages 51-74. 2024. DOI: 10.1007/978-3-031-80308-6_3
[Ban23]
Utsav Banerjee. Privacy-Preserving Edge Computing from Pairing-Based Inner Product Functional Encryption. In IEEE Global Communications Conference (GLOBECOM), pages 2184-2189. 2023. DOI: 10.1109/GLOBECOM54140.2023.10436785
[BCH+24]
Youngjin Bae, Jung Hee Cheon, Guillaume Hanrot, Jai Hyun Park, and Damien Stehlé. Plaintext-Ciphertext Matrix Multiplication and FHE Bootstrapping: Fast and Fused. In Annual International Cryptology Conference (CRYPTO), pages 387-421. 2024. DOI: 10.1007/978-3-031-68382-4_12
[BGH13]
Zvika Brakerski, Craig Gentry, and Shai Halevi. Packed Ciphertexts in LWE-based Homomorphic Encryption. In International Conference on Practice and Theory in Public-Key Cryptography (PKC), pages 1-13. 2013. DOI: 10.1007/978-3-642-36362-7_1
[BGV14]
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) Fully Homomorphic Encryption without Bootstrapping. ACM Transactions on Computation Theory, 6(3):1-36, 2014. DOI: 10.1145/2633600
[BJK15]
Allison Bishop, Abhishek Jain, and Lucas Kowalczyk. Function-Hiding Inner Product Encryption. In International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT), pages 470-491. 2015. DOI: 10.1007/978-3-662-48797-6_20
[BL24]
Daniel J. Bernstein and Tanja Lange. Explicit-Formulas Database. 2024.
[BSS99]
Ian F. Blake, Gadiel Seroussi, and Nigel Smart. Elliptic Curves in Cryptography, volume 265. Cambridge University Press 1999. DOI: 10.1017/cbo9781107360211
[BSS05]
Ian F. Blake, Gadiel Seroussi, and Nigel Smart. Advances in Elliptic Curve Cryptography, volume 317. Cambridge University Press 2005. DOI: 10.1017/cbo9780511546570
[CKKS17]
Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic Encryption for Arithmetic of Approximate Numbers. In International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), pages 409-437. 2017. DOI: 10.1007/978-3-319-70694-8_15
[CKR+20]
Hao Chen, Miran Kim, Ilya Razenshteyn, Dragos Rotaru, Yongsoo Song, and Sameer Wagh. Maliciously Secure Matrix Multiplication with Applications to Private Deep Learning. In International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT), pages 31-59. 2020. DOI: 10.1007/978-3-030-64840-4_2
[CLRS09]
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 3rd edition. 2009.
[CMAK23]
Shuangyi Chen, Anuja Modi, Shweta Agrawal, and Ashish Khisti. Quadratic Functional Encryption for Secure Training in Vertical Federated Learning. In IEEE International Symposium on Information Theory (ISIT), pages 60-65. 2023. DOI: 10.1109/ISIT54713.2023.10206955
[CU23]
Daniel Cussen and Jeffrey D. Ullman. Matrix Multiplication Using Only Addition. arXiv preprint arXiv:2307.01415. 2023.
[DDM16]
Pratish Datta, Ratna Dutta, and Sourav Mukhopadhyay. Functional Encryption for Inner Product with Full Function Privacy. In IACR International Conference on Practice and Theory in Public-Key Cryptography (PKC), pages 164-195. 2016. DOI: 10.1007/978-3-662-49384-7_7
[DDQ07]
Guerric Meurice De Dormale and Jean-Jacques Quisquater. High-Speed Hardware Implementations of Elliptic Curve Cryptography: A Survey. Journal of Systems Architecture, 53(2-3):72-84, 2007. DOI: 10.1016/j.sysarc.2006.09.002
[DGG+23]
Yuanchao Ding, Hua Guo, Yewei Guan, Weixin Liu, Jiarong Huo, Zhenyu Guan, and Xiyong Zhang. East: Efficient and Accurate Secure Transformer Framework for Inference. arXiv preprint arXiv:2308.09923. 2023.
[ElG85]
Taher ElGamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory, 31(4):469-472, 1985. DOI: 10.1109/TIT.1985.1057074
[FCE+23]
David Froelicher, Hyunghoon Cho, Manaswitha Edupalli, Joao Sa Sousa, Jean-Philippe Bossuat, Apostolos Pyrgelis, Juan R. Troncoso-Pastoriza, Bonnie Berger, and Jean-Pierre Hubaux. Scalable and Privacy-Preserving Federated Principal Component Analysis. In IEEE Symposium on Security and Privacy (SP), pages 1908-1925. 2023. DOI: 10.1109/SP46215.2023.10179350
[FGDM+10]
Junfeng Fan, Xu Guo, Elke De Mulder, Patrick Schaumont, Bart Preneel, and Ingrid Verbauwhede. State-of-the-Art of Secure ECC Implementations: A Survey on Known Side-Channel Attacks and Countermeasures. In IEEE International Symposium on Hardware-Oriented Security and Trust (HOST), pages 76-87. 2010. DOI: 10.1109/HST.2010.5513110
[FV12]
Junfeng Fan and Frederik Vercauteren. Somewhat Practical Fully Homomorphic Encryption. Cryptology ePrint Archive, Paper 2012/144. 2012.
[Gen09]
Craig Gentry. Fully Homomorphic Encryption using Ideal Lattices. In Annual ACM Symposium on Theory of Computing (STOC), pages 169-178. 2009. DOI: 10.1145/1536414.1536440
[GM82]
Shafi Goldwasser and Silvio Micali. Probabilistic Encryption & How To Play Mental Poker Keeping Secret All Partial Information. In Annual ACM Symposium on Theory of Computing (STOC), pages 365-377. 1982. DOI: 10.1145/3335741.3335749
[GQH+24]
Yang Gao, Gang Quan, Soamar Homsi, Wujie Wen, and Liqiang Wang. Secure and Efficient General Matrix Multiplication on Cloud using Homomorphic Encryption. The Journal of Supercomputing, 80(18):26394-26434, 2024. DOI: 10.1007/s11227-024-06428-8
[Gri17]
Alexey Grigorev. ML Wiki: Matrix-Matrix Multiplication. 2017.
[GSW13]
Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In Annual Cryptology Conference (CRYPTO), pages 75-92. 2013. DOI: 10.1007/978-3-642-40041-4_5
[HCJG24]
Seungwan Hong, Yoolim A. Choi, Daniel S. Joo, and Gamze Gürsoy. Privacy-Preserving Model Evaluation for Logistic and Linear Regression using Homomorphically Encrypted Genotype Data. Journal of Biomedical Informatics, 156:104678, 2024. DOI: https://doi.org/10.1016/j.jbi.2024.104678
[HHW+23]
Zhicong Huang, Cheng Hong, Chenkai Weng, Wen-jie Lu, and Hunter Qu. More Efficient Secure Matrix Multiplication for Unbalanced Recommender Systems. IEEE Transactions on Dependable and Secure Computing, 20(1):551-562, 2023. DOI: 10.1109/TDSC.2021.3139318
[HLC+22]
Meng Hao, Hongwei Li, Hanxiao Chen, Pengzhi Xing, Guowen Xu, and Tianwei Zhang. Iron: Private Inference on Transformers. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pages 15718-15731. 2022.
[HMV06]
Darrel R. Hankerson, Alfred J. Menezes, and Scott A. Vanstone. Guide to Elliptic Curve Cryptography. Springer Science & Business Media 2006. DOI: 10.1007/b97644
[Hor14]
Mark Horowitz. Computing's Energy Problem (and what we can do about it). In IEEE International Solid-State Circuits Conference (ISSCC), pages 10-14. 2014. DOI: 10.1109/ISSCC.2014.6757323
[HS14]
Shai Halevi and Victor Shoup. Algorithms in HElib. In Annual Cryptology Conference (CRYPTO), pages 554-571. 2014. DOI: 10.1007/978-3-662-44371-2_31
[HZ23]
Hai Huang and Haoran Zong. Secure Matrix Multiplication based on Fully Homomorphic Encryption. The Journal of Supercomputing, 79(5):5064-5085, 2023. DOI: 10.1007/s11227-022-04850-4
[ILP24]
Rares Ifrim, Dumitrel Loghin, and Decebal Popescu. A Systematic Review of Fast, Scalable, and Efficient Hardware Implementations of Elliptic Curve Cryptography for Blockchain. ACM Transactions on Reconfigurable Technology and Systems, 17(4):1-33, 2024. DOI: 10.1145/3696422
[JKLS18]
Xiaoqian Jiang, Miran Kim, Kristin Lauter, and Yongsoo Song. Secure Outsourced Matrix Computation and Application to Neural Networks. In ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 1209-1222. 2018. DOI: 10.1145/3243734.3243837
[JLK+22]
Jaehee Jang, Younho Lee, Andrey Kim, Byunggook Na, Donggeon Yhee, Byounghan Lee, Jung Hee Cheon, and Sungroh Yoon. Privacy-Preserving Deep Sequential Model with Matrix Homomorphic Encryption. In ACM on Asia Conference on Computer and Communications Security (ASIA CCS), pages 377-391. 2022. DOI: 10.1145/3488932.3523253
[Joy03]
Marc Joye. Elliptic Curves and Side-Channel Analysis. ST Journal of System Research, 4(1):17-21, 2003.
[JVC18]
Chiraag Juvekar, Vinod Vaikuntanathan, and Anantha Chandrakasan. GAZELLE: A Low Latency Framework for Secure Neural Network Inference. In USENIX Security Symposium, pages 1651-1669. 2018.
[JY02]
Marc Joye and Sung-Ming Yen. The Montgomery Powering Ladder. In International Workshop on Cryptographic Hardware and Embedded Systems (CHES), pages 291-302. 2002. DOI: 10.1007/3-540-36400-5_22
[KLM+18]
Sam Kim, Kevin Lewi, Avradip Mandal, Hart Montgomery, Arnab Roy, and David J Wu. Function-Hiding Inner Product Encryption Is Practical. In Security and Cryptography for Networks (SCN), pages 544-562. 2018. DOI: 10.1007/978-3-319-98113-0_29
[LCFS17]
Damien Ligier, Sergiu Carpov, Caroline Fontaine, and Renaud Sirdey. Privacy Preserving Data Classification using Inner-Product Functional Encryption. In International Conference on Information Systems Security and Privacy (ICISSP), pages 423-430. 2017. DOI: 10.5220/0006206704230430
[LKS17]
Wen-jie Lu, Shohei Kawasaki, and Jun Sakuma. Using Fully Homomorphic Encryption for Statistical Analysis of Categorical, Ordinal and Numerical Data. In Network and Distributed System Security Symposium (NDSS). 2017. DOI: 10.14722/ndss.2017.23119
[LSZ+14]
Hong Li, Limin Sun, Haojin Zhu, Xiang Lu, and Xiuzhen Cheng. Achieving Privacy Preservation in WiFi Fingerprint-Based Localization. In IEEE Conference on Computer Communications (INFOCOM), pages 2337-2345. 2014. DOI: 10.1109/INFOCOM.2014.6848178
[LZ23]
Jing Liu and Liang Feng Zhang. Privacy-Preserving and Publicly Verifiable Matrix Multiplication. IEEE Transactions on Services Computing, 16(3):2059-2071, 2023. DOI: 10.1109/TSC.2022.3215499
[MMJG24]
Xirong Ma, Chuan Ma, Yali Jiang, and Chunpeng Ge. Improved Privacy-Preserving PCA using Optimized Homomorphic Matrix Multiplication. Computers & Security, 138:103658, 2024. DOI: https://doi.org/10.1016/j.cose.2023.103658
[MOV18]
Alfred J. Menezes, Paul C. Van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press 2018. DOI: 10.1201/9780429466335
[MSH+19]
Tilen Marc, Miha Stopar, Jan Hartman, Manca Bizjak, and Jolanda Modic. Privacy-Enhanced Machine Learning with Functional Encryption. In European Symposium on Research in Computer Security, pages 3-21. 2019. DOI: 10.1007/978-3-030-29959-0_1
[MYJK24]
Jungho Moon, Dongwoo Yoo, Xiaoqian Jiang, and Miran Kim. THOR: Secure Transformer Inference with Homomorphic Encryption. Cryptology ePrint Archive, Paper 2024/1881. 2024.
[Nik14]
Christophoros Nikou. Digital Image Processing: Filtering in the Frequency Domain (Circulant Matrices and Convolution). 2014.
[PAH+17]
Le Trieu Phong, Yoshinori Aono, Takuya Hayashi, Lihua Wang, and Shiho Moriai. Privacy-Preserving Deep Learning via Additively Homomorphic Encryption. IEEE Transactions on Information Forensics and Security, 13(5):1333-1345, 2017. DOI: 10.1109/tifs.2017.2787987
[Pai99]
Pascal Paillier. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), pages 223-238. 1999. DOI: 10.1007/3-540-48910-x_16
[Par25]
Jai Hyun Park. Ciphertext-Ciphertext Matrix Multiplication: Fast for Large Matrices. Cryptology ePrint Archive, Paper 2025/448. 2025.
[PZM+24]
Qi Pang, Jinhao Zhu, Helen Möllering, Wenting Zheng, and Thomas Schneider. Bolt: Privacy-Preserving, Accurate and Efficient Inference for Transformers. In IEEE Symposium on Security and Privacy (SP), pages 4753-4771. 2024. DOI: 10.1109/SP54263.2024.00130
[Ras17]
Bahram Rashidi. A Survey on Hardware Implementations of Elliptic Curve Cryptosystems. arXiv preprint arXiv:1710.08336. 2017.
[RPB+19]
Théo Ryffel, David Pointcheval, Francis Bach, Edouard Dufour-Sans, and Romain Gay. Partially Encrypted Deep Learning using Functional Encryption. In Advances in Neural Information Processing Systems (NeurIPS), pages 4517-4528. 2019.
[RPCS22]
H. Manohar Reddy, Sajimon P. C., and Sriram Sankaran. On the Feasibility of Homomorphic Encryption for Internet of Things. In IEEE World Forum on Internet of Things (WF-IoT), pages 1-6. 2022. DOI: 10.1109/WF-IoT54382.2022.10152214
[RSA78]
Ronald L. Rivest, Adi Shamir, and Leonard Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21(2):120-126, 1978. DOI: 10.1145/359340.359342
[RT22]
Panagiotis Rizomiliotis and Aikaterini Triakosia. On Matrix Multiplication with Homomorphic Encryption. In Cloud Computing Security Workshop (CCSW), pages 53-61. 2022. DOI: 10.1145/3560810.3564267
[Sal22]
Ali Salehi. Convolution as Matrix Multiplication. 2022.
[Sco20]
Michael Scott. On the Deployment of Curve Based Cryptography for the Internet of Things. Cryptology ePrint Archive, Paper 2020/514. 2020.
[Str69]
Volker Strassen. Gaussian Elimination is Not Optimal. Numerische Mathematik, 13(4):354-356, 1969. DOI: 10.1007/BF02165411
[WH19]
Shufang Wang and Hai Huang. Secure Outsourced Computation of Multiple Matrix Multiplication Based on Fully Homomorphic Encryption. KSII Transactions on Internet and Information Systems, 13(11):5616-5630, 2019. DOI: 10.3837/tiis.2019.11.019
[YJ18]
Zheng Yang and Kimmo Jarvinen. The Death and Rebirth of Privacy-Preserving WiFi Fingerprint Localization with Paillier Encryption. In IEEE Conference on Computer Communications (INFOCOM), pages 1223-1231. 2018. DOI: 10.1109/INFOCOM.2018.8486221
[ZHCJ23]
Lin Zhu, Qiang-sheng Hua, Yi Chen, and Hai Jin. Secure Outsourced Matrix Multiplication with Fully Homomorphic Encryption. In European Symposium on Research in Computer Security (ESORICS), pages 249-269. 2023. DOI: 10.1007/978-3-031-50594-2_13
[ZLW25]
Xiaopeng Zheng, Hongbo Li, and Dingkang Wang. A New Framework for Fast Homomorphic Matrix Multiplication. Designs, Codes and Cryptography, 2025. DOI: 10.1007/s10623-025-01614-y
[ZYH+25]
Jiawen Zhang, Xinpeng Yang, Lipeng He, Kejia Chen, Wen-jie Lu, Yinghao Wang, Xiaoyang Hou, Jian Liu, Kui Ren, and Xiaohu Yang. Secure Transformer Inference Made Non-Interactive. In Network and Distributed System Security Symposium (NDSS). 2025. DOI: 10.14722/ndss.2025.230868
PDF
History
Submitted: 2025-01-14
Accepted: 2025-03-11
Published: 2025-04-08
Accepted: 2025-03-11
Published: 2025-04-08
How to cite
Krishna Sai Tarun Ramapragada and Utsav Banerjee, Fast Plaintext-Ciphertext Matrix Multiplication from Additively Homomorphic Encryption. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/abhey76bm.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.