| Approximate Homomorphic Encryption(AHE)becomes a research hot spot in homomorphic cryptography in recent years as it is widely used in neural network,deep learning and other fields.Since matrix multiplication is a common operation and performance bottleneck in these applications,it attracts the attention of many researchers.CKKS scheme which supporting kinds of approximate evaluations of the vector is critically important in approximate homomorphic evaluation.Hence it is a good choice to design matrix approximate encryption scheme under CKKS scheme.There are many achievements in this field.In this thesis,matrix is regarded as an ordered set of vectors and the matrix encryption scheme is designed by encrypting each row vector of it under CKKS scheme.The matrix multiplication method introduced by S.Halevi and V.Shoup is used to design the homomorphic encryption scheme of numeric matrix.With slightly adjustment,the multiplication between matrices with vector elements and the Hadamard product between the matrices with submatrice elements are also homomorphically implemented.Both the ciphertexts and the keys(public key and private key)of these schemes are in small size.In this thesis,the quick matrix multiplication is introduced into homomorphic evaluation by simulating Strassen’s algorithm under cipher state in a purpose of reducing the time complexity of the matrix multiplication.Concretely,the half-cut transformation is simulated on each row of the encrypted matrix firstly.Then they are all put into the cipher matrices in same columns with original matrices.That is,M1,M2,M3,M4 in Strassen algorithm are combined to a matrix in same rows with original matrices,M5,M6 in Strassen algorithm are combined to a matrix in half rows of original matrix as well as M7 is combined with a transformation of itself to a matrix in 1/2 rows of original matrix.Thirdly,simulate the Strassen’s algorithm by replacing normal matrix multiplication into homomorphic matrix multiplication.Finally,combining each submatrices of these ciphertexts in special way in order to achieve the ciphertext of the product of the matrices.The algorithm reduces the complexity of the matrix homomorphic multiplication from O(N3)to O(Nlog(3+(?))).Additionally,the homormphic matrix evaluation is combined with g base decomposition technique to a new matrix evaluation scheme in the purpose of reducing the nosie’s incresement in this thesis.The upper bound of the final noise is related only with the norm of the matrix A(the left operator which is refresh ciphertext before evaluation)and the basis g.Hence it increases more slowly than normal homomorphic matrix multiplication.The impact of the g-base decomposition technique on both the common matrix homomorphic multiplication and quick matrix homomorphic multiplication is analysed in this thesis.Finally,the homomorphic implementation of Gaussian elimination is proposed in this thesis and the algorithm for the determinant of the square matrix is proposed based on it.Concretely,the polynomial approximation of the sign function is used to determine whether a given row is k-valid,that is,the first k elements are not all zero,and a suitable permutation matrix is generated according on it in order to decide whether the given row will be moved below another row.By combining the row permutation method and elimination method,the matrix is finally converted to a upper triangle matrix,which the product of the elements on the main diagonal is the determinant of the given matrix.The upper bound of the noise caused by these algorithms are also estimated. |
