A Framework For The Iterative Solution of Sparse Linear Systems on Hybrid Architectures Using Homomorphic Encryption

This paper considers the solution of sparse linear systems via stationary iterative methods when the application of the preconditioner is implemented via plaintext matrix-ciphertext vector product using the Cheon-Kim-Kim-Song homomorphic encryption scheme. The proposed algorithm targets hybrid cloud architectures where the preconditioner application is performed on a non-secure environment and linear algebraic operations must be performed directly on encrypted data. We discuss several practical and theoretical details, and demonstrate that banded approximate inverses can be exploited to reduce the cost of homomorphic matrix-vector products. Numerical simulations demonstrate that the Richardson stationary iteration can compute an accurate solution even under the presence of homomorphic approximations.