Cheap and Fast Iterative Matrix Inverse in Encrypted Domain

Homomorphic encryption (HE) is a promising technique for preserving the privacy of sensitive data by enabling computations to be performed on encrypted data. However, due to the limitations of arithmetic HE schemes, which typically only support addition and multiplication, many nonlinear operations must be approximated using these basic operations. As a result, some nonlinear operations cannot be executed in the same manner as they would be in the plain domain. For instance, the matrix inverse can be calculated using the Gaussian elimination method in the plain domain, which is not possible using only the usual arithmetic. Therefore, much literature has turned to iterative matrix inverse algorithms such as the Newton method, which can be implemented using only additions and multiplications. In this paper, we propose a new matrix inversion method with better performance and prove that the new method outperforms the existing method; the number of depths of the new method is fewer than that of the existing method. Thus, we can evaluate more operations and design the algorithm efficiently since the number of operations is limited in HE. We experiment on ML algorithms such as linear regression and LDA to show that our matrix inverse operation is more efficient than Newton’s in HE. Our approach exhibits approximately twice the performance improvement compared to the Newton’s method.