On Matrix Multiplication with Homomorphic Encryption
Panagiotis Rizomiliotis, Aikaterini Triakosia
Abstract
Homomorphic Encryption (HE) is one of the main cryptographic tools used to enable secure computation outsourcing. Data is outsourced encrypted to an untrusted service provider and remain encrypted during processing. In the last decade, the performance of HE schemes has impressively improved up to several orders of magnitude thanks to advances in the theory and to more efficient implementations. However, it is still significantly slower than plaintext computations, while realizing HE-based computations is complex for the non-expert. Matrix multiplication is a fundamental computation for a variety of applications that are offered as a service, like machine learning model inference. The matrices are HE encrypted and they are outsourced to an untrusted computation environment. In order to improve the performance of HE schemes, several matrices are encoded in a single ciphertext, known also as message packing. However, a single ciphertext usually has several thousands of slots, and, it is common many of these slots to remain empty due to lack of data. In this work, we introduce a secure matrix multiplication outsourcing method that takes advantage of the message packing, when the available matrix entries are very few, i.e. when several ciphertext slots remain empty. We evaluate the complexity of our proposal in terms of basic homomorphic encryption operations and we compute the multiplicative depth of the corresponding arithmetic circuit. Finally, we implement our multiplication algorithm using the CKKS HE scheme, as it is supported in the MS SEAL library.