Linear System Solving Scheme Based on Homomorphic Encryption

Abstract

In the fields of scientific computing,statistical analysis and machine learning,many practical problems can be reduced to solving linear system Ax=b,such as least square estimation and regression analysis in machine learning.In practice,the data used for calculation often belong to different users,containing their sensitive information.When different data owners want to collaboratively solve a model,homomorphic encryption can be one of the methods to deal with the privacy leakage in computing.In a scenario with only two parties,based on the HEAAN scheme proposed by Cheon et al,we propose a new scheme involving two-party to securely solve the linear system through Gram-Schmidt orthogonalization,and design an interactive secure multiplicative inverse protocol to solve a problem that they cannot do efficient division.We analyze the security,communication cost and computational complexity,and also implement our scheme based on HEAAN library using C++ language.Through a large number of experiments,it shows that our scheme can solve a linear system with dimension up to 17 safely and efficiently.Compared with the results on unencrypted data,the relative error is no more than 0.000 1.By the proposed parallel encoding method,our scheme can process multiple linear systems simultaneously in SIMD mode,which expands the availability of the scheme.Our scheme can be practically applied in some specific scenarios,and can be further used for the design of privacy-preserving data mining algorithms.

Keywords

• linear system|gram-schmidt orthogonalization|privacy preserving|homomorphic encryption|heaan