# Efficient Noninteractive Outsourcing of Large-Scale QR and LU Factorizations

Authors: Lingzan Yu; Yanli Ren; Guorui Feng; Xinpeng Zhang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

QR and LU factorizations are two basic mathematical methods for decomposition and dimensionality reduction of large-scale matrices. However, they are too complicated to be executed for a limited client because of big data. Outsourcing computation allows a client to delegate the tasks to a cloud server with powerful resources and therefore greatly reduces the client’s computation cost. However, the previous methods of QR and LU outsourcing factorizations need multiple interactions between the client and cloud server or have low accuracy and efficiency in large-scale matrix applications. In this paper, we propose a noninteractive and efficient outsourcing algorithm of large-scale QR and LU factorizations. The proposed scheme is based on the specific perturbation method including a series of consecutive and sparse matrices, which can be used to protect the original matrix and obtain the results of factorizations. The generation and inversion of sparse matrix has small workloads on the client’s side, and the communication cost is also small since the client does not need to interact with the cloud server in the outsourcing algorithms. Moreover, the client can verify the outsourcing result with a probability of approximated to 1. The experimental results manifest that as for the client, the proposed algorithms reduce the computational overhead of direct computation successfully, and it is most efficient compare with the previous ones.


---

## Body

## 1. Introduction

At the era of big data, the exponential growth of data volume has attracted more and more attention. It is predicted that by 2021, every person will average generate about 1.7 MB of data per second. This presents an inevitable challenge, because the owners of data and analysts need to find a way to store and analyse enormous data properly and effectively.During the processing of large-scale data, the storage capacity and computing power are closely related to the computer system hardware and available memory. Due to the limitations of the local computation resources, the client can neither be able to employ large-scale data tasks nor meet the requirements for calculation time. Therefore, a potential way to deal with the dilemma is to seek help from advanced computing facilities with great computational power. This promotes the motivation to develop outsourced computing server, also known as cloud server. In an outsourcing computation scheme, the clients only need to upload data and computation tasks to the cloud server, and the server provides on-demand resources. Outsourcing computation allows source-constrained client to the abundant computing resources and save abundant local memory space or computation overhead.Matrix factorization is a data analysis technique and has been increasing prevalent several fields, such as regression analysis [1] and dimension reduction [2]. QR factorization [3] is one of the basic methods for matrix factorization, and it implements a way of decomposing an original matrix into the product of two specific matrices which satisfy the orthogonality and upper triangular properties, respectively, so that some useful properties of the original matrix can be extracted further. It is common to utilize QR factorization to analyse real-world data analysis problems; for instance, it is always used to employ singular value decomposition [4] and utilized to solve least squares problems [5] as well. Lower-upper (LU) factorization is a means of taking the matrix as the product of the lower triangular matrix and the upper triangular matrix, it is used wildly in numerical analysis and linear algebra fields, computers usually use LU factorization to solve the square system of linear equations, and it is also an essential step when calculating the inversion of a matrix and the determinant of a matrix.Notice that QR and LU factorizations have been widely used in many fields, the requirement of conducting QR and LU factorizations on large-scale matrix becomes increasingly common, however, it will cost computational complexity ofOm2n when conducting QR or LU factorizations of a m×n matrix, as the dimension increases, the computation overhead expands sharply, and for resource-constrained clients such as individuals or small companies, the enormous computation and storage overheads are beyond their computing capabilities when dealing with a large-scale matrix. To address this problem, our goal is to design an efficient outsourcing algorithm of large-scale QR and LU factorizations while preserving noninteractive performance, which will help the clients take use of notable advantages of the cloud server to complete complicated task.In order to achieve our design goals, we need to pay attention to potential menace and several challenges. More precisely, the first is the security issue [6], and the data outsourced to the cloud may be private and sensitive, which means the clients are undesirable to leak their data; our proposed algorithms will take actions based on matrix permutation techniques to transform the original data, to prevent the semi-trustful or even malicious cloud server from deducing the client’s data and inferring the behaviour information; besides, our proposed algorithms are designed under one cloud server and avoid the strict security precondition of all the cloud servers must be noncolluding. Another challenge is the correctness of calculations, and the client should check the correctness of results of outsourcing computation, so in our proposed algorithms, we have designed a subalgorithm to determine whether the calculation tasks outsourced to the cloud server are performed correctly or return invalid results simply. In addition, efficiency is also a vital challenge, it is required that the computational overheads locally should be remarkably less than the computational expenses without outsourcing, we utilize a special matrix generation technique with little cost, and only sparse matrix multiplication is required in encryption and decryption algorithms; vector-matrix multiplication is required in the verification algorithm, which lessens the computational burden on the client side successfully. Moreover, the client employs our algorithms without interaction between the client and the cloud server, thereby reducing clients’ communication overhead and minimizing the risks of destroying data security and privacy during the interaction process.In this paper, we put forward a secure and noninteractive outsourcing algorithm of large-scale QR and LU factorizations. Concretely, our algorithm utilizes special sparse matrices to encrypt the original matrix. The client first generates transform matrices for outsourcing QR and LU factorizations at the low computational cost and then encrypts the original matrix to hide the original data through matrix multiplication. After that, the cloud conducts the QR factorization and LU factorization on the transformed matrix without interaction between the clients and sends the computation results back to the client. Once getting the results, the decomposition results will be verified through the Freivalds algorithm by the client. If the results are proved to be correct, the client recovers the desired factor matrices in the way of computing the product of returned results and the inverse of the permutation matrix.We have summarized all the contributions of our work as follows:(1)
We propose an efficient and noninteractive outsourcing algorithm for large-scale QR and LU factorizations. In terms of complexity, our proposed algorithms realize the reduction of the computational overhead fromOm2n to Omaxm2,mn on the client side, where m,ndenote the dimension of the matrix. Compared with the previous ones, it is the most efficient outsourcing scheme for the client.(2)
The proposed QR and LU factorization algorithms are also noninteractive which achieves small communication overheads, where several interactions between the client and the cloud server are required in the previous algorithms.(3)
The proposed algorithms use a matrix transform method based on a series of particular and sparse matrices in both encryption and decryption stage, and we prove our method can satisfy the demand of the privacy security for outsourcing.(4)
The verifiability of the results is realized in our proposed scheme, which allows the client to judge whether the results of the outsourcing computation are correct with a probability of close to 1.The structure of this paper is arranged as follows. Section3presents the preliminaries including concrete QR and LU algorithms and system architecture. In Section 4, we will introduce the proposed algorithm for secure and noninteractive outsourcing of large-scale QR and LU factorizations in detail. A comprehensive theoretical analysis will be shown in Section 5. We provide the experimental data including the performance of our algorithms and the comparison in Section 6and summarize the algorithms in our paper in Section 7.


## 2. Related Work

In recent years, driven by the widespread application of the large-scale matrix [7], there exists some outsourcing algorithms for the matrix operations at present, which are designed for complicated matrix computations such as multiplication, matrix inversion, matrix eigenvalue evaluation, and matrix decomposition. These algorithms can be divided into two categories: algorithms based on cryptographic technology and those based on linear transformation. For the former, many scholars propose to use traditional encryption techniques such as homomorphic encryption [8] to protect the client’s data privacy. For the latter, scholars proposed data transformation techniques to transform the original data. When it comes to the outsourcing of matrix multiplication calculation, as discussed by Atallah [9], they commenced the research on outsourcing algorithms through mapping the random permutation matrix to transform the original matrix. Benjamin and Atallah [10] proposed a secure outsourcing scheme of matrix multiplication through employing homomorphic encryption to the original matrix. As for matrix inversion, Mohassel [11] proposed a secure outsourcing algorithm firstly, and due to the constraints of efficiency, their algorithm failed to be practical in applications. A scheme for outsourcing matrix inversion computation based on the novel transformation method is introduced in Lei [12]. Chen et al. [13] further put forward a matrix inversion outsourcing scheme without the precondition that the original matrix must be invertible.In recent years, the research on matrix factorization outsourcing has attracted considerable attention. An outsourcing protocol for matrix factorization based on the fully and partially homomorphic encryptions is presented in Kim [14]. Duan et al. [15] proposed an outsourcing scheme of computation-intensive nonnegative matrix, which uses multiplication of permuted matrices. As discussed by Fu [16], they used two cloud servers which are noncollusion to outsource nonnegative matrix factorization and take effective encryption measures based on Paillier homomorphism to protect data privacy. Zhou et al. [17] proposed an outsourcing scheme for matrix eigenvalue decomposition and matrix singular value decomposition, which achieved the verifiability of the results. Luo et al. [18] proposed a secure large-scale QR and LU decomposition outsourcing algorithm and protected the original matrix by utilizing specific matrix transformations, which greatly reduces the client’s local computing overhead. However, their algorithm requires additional interaction between the client and cloud, which results in high communication overhead. Zhang et al. [19] presented the implementation of QR decomposition based on a ring-LWE homomorphic encryption and reduced the number of interactions between the client and cloud. As we know, the plaintexts to be encrypted can only be integers and the data should round to the nearest integers, and so the accuracy of the scheme cannot be guaranteed. Moreover, the experimental stage of the scheme does not include the performance when the scheme is applied to large-scale matrices. Simultaneously, neither of the above two schemes can provide verification of the outsourced results.In previous related research, Luo et al. [18] transform the original matrix by multiplying it with two random and dense matrices, one of them is an orthogonal matrix, and when it comes to the orthogonal matrix, it takes Om2 computational complexity to generate a random orthogonal matrix and takes Om3 computational complexity to get the inversion of this orthogonal matrix, so their scheme chooses to outsource this progress. As for transforming the original matrix, includes dense matrix multiplication, this takes Om2n complexity [20]. Because dense matrix multiplication and matrix inversion computation require huge resources, they also need to outsource. In a word, they choose to outsource these computations in an interactive way, and every matrix for interaction still needs to be encrypted for enhanced privacy protection, which results in a lot of communication overhead on the client.


## 3. Backgrounds

In this section, we will provide the details concerning QR and LU factorizations and describe the system model and the threat model.


### 3.1. Householder-Based QR Factorization

The well-known QR factorization of a matrix will decompose matrixA into the form of the product of an orthogonal matrix and an upper triangular matrix, let A be a real m×nmatrix (m≥n), and A may be decomposed into the product on the form(1)A=Q×R,where Q is the (m×n) orthogonal (QTQ=I), and R is the (n×n) upper triangular; they are obtained by the use of a sequence of Householder transformations, and this type of transformation conducts the QR decomposition using elementary orthogonal Householder matrices, such as(2)Pm−1⋯P2P1A=R,where Pi is an orthogonal and symmetric matrix called the Householder transformation matrix, and it is obtained by the following formula:(3)Pi=I−2viviTviTvi,where v is a column vector and I is the identity matrix of order size vi, note that v1 is the first column vector of original matrix A, we can get P1 by substituting v1 into equation (3), and then multiply P1 by A, and v2 is the second column vector of new matrix P1A, we can get P2 by substituting v2 into equation (3), v2 is the third column vector of new matrix P2P1A, following the same process, viis the ith column vector of the corresponding matrix, Pi can be obtained by substituting vi into equation (3), and continue this process until it reaches Pm.And the matrixQis not given explicitly as(4)QT=Pm−1⋯P2P1.SincePi is an orthogonal matrix, we can derive Q as(5)Q=P1−1P2−1⋯Pm−1−1.


### 3.2. Gauss Elimination-Based LU Factorization

The well-known LU factorization refers to decompose a matrixBinto two factors, a lower triangular matrix Land an upper triangular matrix U. Assume Bis a real m×n matrix (m≥n), and it may be decomposed into the product on the form(6)B=L×U,where L is the (m×n) lower triangular and U is the (n×n) upper triangular which means all the elements below the diagonal are zero, and U is obtained with the use of a sequence of Gauss transformations [20]:(7)Mm−1⋯M2M1B=U,where Mi is obtained by the following formula:(8)Mi=I−Πiei.Note thatΠ1=0,π21,π31,…,πm1T, where πi1=bi1/b11, bi1 is the ith element of the first column of matrix B, and I is the identity matrix of order size Πiei; let e1=1,0,…,0, and we can get M1 by substituting Π1and e1 into equation (8). After getting a new matrix by multiplying M1 by B, then we use ith element of the second column of matrix M1B to calculate Π2=0,0,π32,…,πm2T; let e2=0,1,⋯,0, and M2can be obtained by substituting Π2and e2into equation (8). Following the same process, once the last Gauss transformations Mm−1 are reached. Finally, we can get Ufrom equation (7) and the matrix Lis computed by(9)L=M1−1M2−1⋯Mm−1−1,where Mi−1=I+Πiei.


### 3.3. Security Requirements

#### 3.3.1. System Model

The architecture of our proposed efficient and noninteractive outsourcing of the large-scale QR and LU factorization algorithm is illustrated in Figure1, involves two main different entities: the client and the cloud server with excellent computational ability and significant storage capacity. Due to the inability to carry out the matrix factorizations when the size of this matrix is too large, the client would like to outsource this task to the cloud server. The client only needs to complete these processes locally include key generation, encryption, decryption, and verification. As for the cloud server, it will conduct QR and LU factorizations on the encrypted matrix. There is no extra interaction between two entities in our proposed algorithm.Figure 1
The model of our proposed outsourcing algorithm.The implementation of our proposed algorithm consists of five subalgorithms. The concrete definitions of these algorithms are shown as follows:(1)
KeyGenλ⟶K: with the input of a security parameter λ, this algorithm will generate a secret key K which will be further used for matrix encryption and matrix decryption, and the secret key K is stored by the client.(2)
ClientEncA,K⟶A′: with the input of an original matrix A∈Rm×n, this algorithm is executed by the client to output the encrypted matrix A′∈Rm×n, and the data are encrypted by the secret key K.(3)
CloudComF,A′⟶Q′,R′: receiving the computation task ℱand the corresponding matrix A′, this algorithm is executed by the cloud to complete the task ℱ and output the result Q′∈Rm×mand R′∈Rm×n, which are two factor matrices of A′.(4)
ClientVerA′,l,Q′,R′⟶Q′,R′∪⊥: receiving the result Q′and R′ from the cloud, this algorithm is executed by the client to verify the correctness of the answer and detect the incorrect answer. If the result passes the verification algorithm, the client accepts the returned results (Q′,R′). Otherwise, the algorithm returns ⊥.(5)
ClientDecrpytK,Q′,R′⟶Q,R: after verifying the result Q′ and R′, this algorithm is executed by the client, and the client utilizes the secret key K to decrypt the returned result, to recover and output two factor matrices Qand Rfor the original matrix A.


#### 3.3.2. Threat Model

As we know, the client can benefit from outsourcing computation, but it still causes challenges and threats during data treatments. We think about the security challenges and threats from two kinds of servers in generic outsourcing frameworks, one is from external attackers, it means the cloud server and the stored data might suffer from external attacks, and this situation is not considered in this paper; in addition, another security threat is from internal participants, it means that the threats to information confidentiality exactly come from the cloud server, and we consider two kinds of threat models which are classified depending on the cloud’s behaviour: one is named the “honest-but-curious” [21], the cloud server may be curious and take action to infer confidential information from the original data or the intermediate results, although the cloud server follows the protocol specification and execute the computation faithfully, the second is “malicious” model, and this cloud server may deceive the client and return the client with incorrect answers on purpose in order to save computational resources. And we assume that the cloud is malicious in our proposed scheme.


#### 3.3.3. Design Goals

In this section, we formulate these design goals of our proposed outsourcing algorithm as follows:(A)
Correctness: assume that the client and the cloud server execute the outsourcing scheme faithfully, and the client can recover the result of the computation and then get the correct result.(B)
Input and output privacy: it is required that the adversary cannot get any knowledge from client’s data during the process of carrying out the scheme. In our paper, for making sure the security of outsourcing algorithm, we introduce the formal security definitions of indistinguishability in value under a chosen-plaintext attack (CPA) [22].All personal information will be considered confidential if for any probabilistic polynomial time adversaryA, there exists a negligible function nelgλ, and the A’s advantage in winning the experiment is(10)AdvAExp≤nelgλ,whereλ is an initial parameter, AdvAExp=Prx=x′−1/2, and the experiment we will proceed further which is explained in Algorithm 1.Algorithm 1: A CPA indistinguishability experiment in value.
(1)
A client C generates a random matrixA0 and a key K with the security parameter λ(2)
An adversaryA output i,j and two different values a0,a1(3)
C picksx←0,1 randomly, replaces the i,j element of A0 with ax to get A, and calculates the masked task ClientEncA,K(4)
A predicts x′←AClientEncA,⋅a0,a1,i,j,A′ with the access to the oracle ClientEncA,⋅(5)
Return 1 ifx′=x and 0 otherwise(C)
Efficiency: it actually means that the overhead involved in using outsourcing scheme by the client should be substantially less than the overhead required for executing the computational task computation on its own.(D)
Verifiability: it is commonly required that the proposed algorithm can verify correctness of the returned result, the correct results can pass the verification algorithm successfully, and the probability of incorrect results sent back from a malicious cloud server can pass the verification is negligible.


## 3.1. Householder-Based QR Factorization

The well-known QR factorization of a matrix will decompose matrixA into the form of the product of an orthogonal matrix and an upper triangular matrix, let A be a real m×nmatrix (m≥n), and A may be decomposed into the product on the form(1)A=Q×R,where Q is the (m×n) orthogonal (QTQ=I), and R is the (n×n) upper triangular; they are obtained by the use of a sequence of Householder transformations, and this type of transformation conducts the QR decomposition using elementary orthogonal Householder matrices, such as(2)Pm−1⋯P2P1A=R,where Pi is an orthogonal and symmetric matrix called the Householder transformation matrix, and it is obtained by the following formula:(3)Pi=I−2viviTviTvi,where v is a column vector and I is the identity matrix of order size vi, note that v1 is the first column vector of original matrix A, we can get P1 by substituting v1 into equation (3), and then multiply P1 by A, and v2 is the second column vector of new matrix P1A, we can get P2 by substituting v2 into equation (3), v2 is the third column vector of new matrix P2P1A, following the same process, viis the ith column vector of the corresponding matrix, Pi can be obtained by substituting vi into equation (3), and continue this process until it reaches Pm.And the matrixQis not given explicitly as(4)QT=Pm−1⋯P2P1.SincePi is an orthogonal matrix, we can derive Q as(5)Q=P1−1P2−1⋯Pm−1−1.


## 3.2. Gauss Elimination-Based LU Factorization

The well-known LU factorization refers to decompose a matrixBinto two factors, a lower triangular matrix Land an upper triangular matrix U. Assume Bis a real m×n matrix (m≥n), and it may be decomposed into the product on the form(6)B=L×U,where L is the (m×n) lower triangular and U is the (n×n) upper triangular which means all the elements below the diagonal are zero, and U is obtained with the use of a sequence of Gauss transformations [20]:(7)Mm−1⋯M2M1B=U,where Mi is obtained by the following formula:(8)Mi=I−Πiei.Note thatΠ1=0,π21,π31,…,πm1T, where πi1=bi1/b11, bi1 is the ith element of the first column of matrix B, and I is the identity matrix of order size Πiei; let e1=1,0,…,0, and we can get M1 by substituting Π1and e1 into equation (8). After getting a new matrix by multiplying M1 by B, then we use ith element of the second column of matrix M1B to calculate Π2=0,0,π32,…,πm2T; let e2=0,1,⋯,0, and M2can be obtained by substituting Π2and e2into equation (8). Following the same process, once the last Gauss transformations Mm−1 are reached. Finally, we can get Ufrom equation (7) and the matrix Lis computed by(9)L=M1−1M2−1⋯Mm−1−1,where Mi−1=I+Πiei.


## 3.3. Security Requirements

### 3.3.1. System Model

The architecture of our proposed efficient and noninteractive outsourcing of the large-scale QR and LU factorization algorithm is illustrated in Figure1, involves two main different entities: the client and the cloud server with excellent computational ability and significant storage capacity. Due to the inability to carry out the matrix factorizations when the size of this matrix is too large, the client would like to outsource this task to the cloud server. The client only needs to complete these processes locally include key generation, encryption, decryption, and verification. As for the cloud server, it will conduct QR and LU factorizations on the encrypted matrix. There is no extra interaction between two entities in our proposed algorithm.Figure 1
The model of our proposed outsourcing algorithm.The implementation of our proposed algorithm consists of five subalgorithms. The concrete definitions of these algorithms are shown as follows:(1)
KeyGenλ⟶K: with the input of a security parameter λ, this algorithm will generate a secret key K which will be further used for matrix encryption and matrix decryption, and the secret key K is stored by the client.(2)
ClientEncA,K⟶A′: with the input of an original matrix A∈Rm×n, this algorithm is executed by the client to output the encrypted matrix A′∈Rm×n, and the data are encrypted by the secret key K.(3)
CloudComF,A′⟶Q′,R′: receiving the computation task ℱand the corresponding matrix A′, this algorithm is executed by the cloud to complete the task ℱ and output the result Q′∈Rm×mand R′∈Rm×n, which are two factor matrices of A′.(4)
ClientVerA′,l,Q′,R′⟶Q′,R′∪⊥: receiving the result Q′and R′ from the cloud, this algorithm is executed by the client to verify the correctness of the answer and detect the incorrect answer. If the result passes the verification algorithm, the client accepts the returned results (Q′,R′). Otherwise, the algorithm returns ⊥.(5)
ClientDecrpytK,Q′,R′⟶Q,R: after verifying the result Q′ and R′, this algorithm is executed by the client, and the client utilizes the secret key K to decrypt the returned result, to recover and output two factor matrices Qand Rfor the original matrix A.


### 3.3.2. Threat Model

As we know, the client can benefit from outsourcing computation, but it still causes challenges and threats during data treatments. We think about the security challenges and threats from two kinds of servers in generic outsourcing frameworks, one is from external attackers, it means the cloud server and the stored data might suffer from external attacks, and this situation is not considered in this paper; in addition, another security threat is from internal participants, it means that the threats to information confidentiality exactly come from the cloud server, and we consider two kinds of threat models which are classified depending on the cloud’s behaviour: one is named the “honest-but-curious” [21], the cloud server may be curious and take action to infer confidential information from the original data or the intermediate results, although the cloud server follows the protocol specification and execute the computation faithfully, the second is “malicious” model, and this cloud server may deceive the client and return the client with incorrect answers on purpose in order to save computational resources. And we assume that the cloud is malicious in our proposed scheme.


### 3.3.3. Design Goals

In this section, we formulate these design goals of our proposed outsourcing algorithm as follows:(A)
Correctness: assume that the client and the cloud server execute the outsourcing scheme faithfully, and the client can recover the result of the computation and then get the correct result.(B)
Input and output privacy: it is required that the adversary cannot get any knowledge from client’s data during the process of carrying out the scheme. In our paper, for making sure the security of outsourcing algorithm, we introduce the formal security definitions of indistinguishability in value under a chosen-plaintext attack (CPA) [22].All personal information will be considered confidential if for any probabilistic polynomial time adversaryA, there exists a negligible function nelgλ, and the A’s advantage in winning the experiment is(10)AdvAExp≤nelgλ,whereλ is an initial parameter, AdvAExp=Prx=x′−1/2, and the experiment we will proceed further which is explained in Algorithm 1.Algorithm 1: A CPA indistinguishability experiment in value.
(1)
A client C generates a random matrixA0 and a key K with the security parameter λ(2)
An adversaryA output i,j and two different values a0,a1(3)
C picksx←0,1 randomly, replaces the i,j element of A0 with ax to get A, and calculates the masked task ClientEncA,K(4)
A predicts x′←AClientEncA,⋅a0,a1,i,j,A′ with the access to the oracle ClientEncA,⋅(5)
Return 1 ifx′=x and 0 otherwise(C)
Efficiency: it actually means that the overhead involved in using outsourcing scheme by the client should be substantially less than the overhead required for executing the computational task computation on its own.(D)
Verifiability: it is commonly required that the proposed algorithm can verify correctness of the returned result, the correct results can pass the verification algorithm successfully, and the probability of incorrect results sent back from a malicious cloud server can pass the verification is negligible.


## 3.3.1. System Model

The architecture of our proposed efficient and noninteractive outsourcing of the large-scale QR and LU factorization algorithm is illustrated in Figure1, involves two main different entities: the client and the cloud server with excellent computational ability and significant storage capacity. Due to the inability to carry out the matrix factorizations when the size of this matrix is too large, the client would like to outsource this task to the cloud server. The client only needs to complete these processes locally include key generation, encryption, decryption, and verification. As for the cloud server, it will conduct QR and LU factorizations on the encrypted matrix. There is no extra interaction between two entities in our proposed algorithm.Figure 1
The model of our proposed outsourcing algorithm.The implementation of our proposed algorithm consists of five subalgorithms. The concrete definitions of these algorithms are shown as follows:(1)
KeyGenλ⟶K: with the input of a security parameter λ, this algorithm will generate a secret key K which will be further used for matrix encryption and matrix decryption, and the secret key K is stored by the client.(2)
ClientEncA,K⟶A′: with the input of an original matrix A∈Rm×n, this algorithm is executed by the client to output the encrypted matrix A′∈Rm×n, and the data are encrypted by the secret key K.(3)
CloudComF,A′⟶Q′,R′: receiving the computation task ℱand the corresponding matrix A′, this algorithm is executed by the cloud to complete the task ℱ and output the result Q′∈Rm×mand R′∈Rm×n, which are two factor matrices of A′.(4)
ClientVerA′,l,Q′,R′⟶Q′,R′∪⊥: receiving the result Q′and R′ from the cloud, this algorithm is executed by the client to verify the correctness of the answer and detect the incorrect answer. If the result passes the verification algorithm, the client accepts the returned results (Q′,R′). Otherwise, the algorithm returns ⊥.(5)
ClientDecrpytK,Q′,R′⟶Q,R: after verifying the result Q′ and R′, this algorithm is executed by the client, and the client utilizes the secret key K to decrypt the returned result, to recover and output two factor matrices Qand Rfor the original matrix A.


## 3.3.2. Threat Model

As we know, the client can benefit from outsourcing computation, but it still causes challenges and threats during data treatments. We think about the security challenges and threats from two kinds of servers in generic outsourcing frameworks, one is from external attackers, it means the cloud server and the stored data might suffer from external attacks, and this situation is not considered in this paper; in addition, another security threat is from internal participants, it means that the threats to information confidentiality exactly come from the cloud server, and we consider two kinds of threat models which are classified depending on the cloud’s behaviour: one is named the “honest-but-curious” [21], the cloud server may be curious and take action to infer confidential information from the original data or the intermediate results, although the cloud server follows the protocol specification and execute the computation faithfully, the second is “malicious” model, and this cloud server may deceive the client and return the client with incorrect answers on purpose in order to save computational resources. And we assume that the cloud is malicious in our proposed scheme.


## 3.3.3. Design Goals

In this section, we formulate these design goals of our proposed outsourcing algorithm as follows:(A)
Correctness: assume that the client and the cloud server execute the outsourcing scheme faithfully, and the client can recover the result of the computation and then get the correct result.(B)
Input and output privacy: it is required that the adversary cannot get any knowledge from client’s data during the process of carrying out the scheme. In our paper, for making sure the security of outsourcing algorithm, we introduce the formal security definitions of indistinguishability in value under a chosen-plaintext attack (CPA) [22].All personal information will be considered confidential if for any probabilistic polynomial time adversaryA, there exists a negligible function nelgλ, and the A’s advantage in winning the experiment is(10)AdvAExp≤nelgλ,whereλ is an initial parameter, AdvAExp=Prx=x′−1/2, and the experiment we will proceed further which is explained in Algorithm 1.Algorithm 1: A CPA indistinguishability experiment in value.
(1)
A client C generates a random matrixA0 and a key K with the security parameter λ(2)
An adversaryA output i,j and two different values a0,a1(3)
C picksx←0,1 randomly, replaces the i,j element of A0 with ax to get A, and calculates the masked task ClientEncA,K(4)
A predicts x′←AClientEncA,⋅a0,a1,i,j,A′ with the access to the oracle ClientEncA,⋅(5)
Return 1 ifx′=x and 0 otherwise(C)
Efficiency: it actually means that the overhead involved in using outsourcing scheme by the client should be substantially less than the overhead required for executing the computational task computation on its own.(D)
Verifiability: it is commonly required that the proposed algorithm can verify correctness of the returned result, the correct results can pass the verification algorithm successfully, and the probability of incorrect results sent back from a malicious cloud server can pass the verification is negligible.


## 4. Efficient Noninteractive Outsourcing of QR and LU Factorizations

As described before, it will waste too much resources in computation and communication aspects in work [18, 19], we should make progress that the client completes the operation for the original matrix with the least computational complexity. Based on these considerations, we decide to use the sparse matrices to execute matrix multiplication operation. It is necessary to protect the confidentiality of the input/output data simultaneously, we take an efficient encryption method on the original data, the client transforms the original matrix by multiplying a series of particular matrices, these appropriate matrices all are sparse enough to ensure efficiency, and ensure data security at the same time; in this way, the client only needs to turn to the cloud one time and receive results, and the interactions are no longer needed. We use these particular matrices due to the specific forms of the factor matrices after decomposing. Because Rand Lare both upper triangular matrices, either QR or LU outsourcing factorizations will use a random upper triangular matrix to encrypt data, and the generation of encryption matrix in KeyGenwill be similar partly. Another encryption matrix will be related to outsourcing algorithms, they are the orthogonal matrix and the lower triangular matrix, respectively.In this section, we describe noninteractive and efficient outsourcing of large-scale QR and LU factorizations, including the following steps: the client generates a secret keyKwhich comprises stochastic parameters with input security parameter, then the client employs some encryption steps to transform original matrix, the client sends the encrypted matrix which is exactly blind to the cloud server to the cloud, next, the complicated decomposing computation on the encrypted matrix will be completed by the cloud, and the client utilizes the key Kwhich is saved on his own to recover the results if the results after decomposing pass the verification. We will illustrate every step concretely as follows.


### 4.1. Efficient Noninteractive Outsourcing of Large-Scale QR Factorizations

Given a valid large-scale input matrixA∈Rm×n, the client wants to accomplish the QR factorizations with the assistance of the cloud server, and QR factorization will decompose matrix A∈Rm×n into a product of an orthogonal matrix Q∈Rm×m and an upper triangular matrix R∈Rm×n, i.e., A=Q×R.


#### 4.1.1.KeyGen

As mentioned before, this algorithm is conducted on the client side, which can produce a secret keyKand generate an orthogonal matrix O∈Rm×m and an upper triangular matrix S∈Rn×n.Specifically, for perturbing all elements in original matrixA∈Rm×n in an effective way, we take the novel transform based on Givens matrix [23], and the orthogonal matrix O∈Rm×m is composed of kGivens matrices as(11)O=G1G2G3⋯Gk,where Gi is a Givens matrix (i=1,2,…,k), and the detailed generation of Ois shown in Algorithm 2; the client can construct an orthogonal sparse matrix by substituting certain elements located in i,i,i,j,j,i, andj,j positions of the identity matrix I∈Rm×m with some certain random parameters cosθ,−sinθ,sinθ,andcosθ respectively. And the structure of Gi can be expressed as(12)G=1⋱cosθ−sinθ1⋱1sinθcosθ⋱1.Algorithm 2: Generation of orthogonal perturbation matrix O.
Input: size mOutput: O(1)
SetO to be an identity matrix(2)
SetL=1,2,3,…,m(3)
fork=1:m/2do(4)
seti,j are random integers chosen randomly in L, and remove i,j from L(5)
setθ to be a random real number within 0,2π(6)
setOii=Ojj=cosθ, Oij=−sinθ, Oji=sinθ(7)
end for(8)
take the remaining elementl in L(9)
setOll=1The detailed generation ofO is presented in Algorithm 2 as follows:Concretely, we haveG×GT=I,G−1=GT. Since every Gi is an orthogonal and sparse matrix, we can draw the conclusion that the permutation matrix O is an orthogonal matrix certainly, and it is easy to get the inversion of O on the client side, instead of the outsourcing algorithm for matrix inverse in [18].Next, let us focus on the generation of the upper triangular matrixS∈Rn×n. The client can construct a sparse and upper triangular matrix by multiplying a series of random, consecutive upper triangular matrix. S is composed of n elementary matrices as(13)S=C1C2C3⋯Cn.Concretely, the structure ofCi is as follows:(14)Ci=11⋯ci⋱⋮11,i=1,2,…,n,where Ci is an elementary matrix, and the detailed generation of S is shown in Algorithm 3; we can see that the all nondiagonal elements of Ciare zero except ci, and the row index of the element ci is bigger than the column index of ci; note that the element ci is randomly picked within the interval −2q,2q. Therefore, ci is a random variable with its probability density function defined as(15)fCici=12q+1,−2q<ci<2q,0,and the matrices O and S are kept by the client secretly.Algorithm 3: Generation of elementary perturbation matrix S.
Input: size nOutput: S(1)
SetS to be an identity matrix(2)
fori=1:ndo(3)
setCi to be an identity matrix(4)
setci to be a random real number within −2q,2q except 0, and q>0(5)
setαi=i(6)
setβi is a random integer chosen randomly within αi,n(7)
add the element of theαith and the βith column in matrix Ci to be ci(8)
setS=S×Ci(9)
end for


#### 4.1.2.ClientEnc

Considering the existence of malicious servers, it is necessary to ensure the confidentiality of the original matrix and the output matrices as well, and we propose to execute a secure and efficient matrix transforming method. A concise way to encryptAis multiplying Aby O and S on both the left and right sides simultaneously. Then, the client can obtain the final ciphertext matrix A′∈Rm×n as(16)A′=O×A×S.In conclusion, theClientEnc algorithm is completed by multiplying a series of consecutive matrices. In virtue of the property of these sparse matrices, the computation overhead required in this algorithm is affordable.


#### 4.1.3.CloudCom

Once the client gets the ciphertext matrixA′∈Rm×n, the client will send it to the cloud. Afterwards, the cloud server computes the QR factorization which is based on Householder reflection; after the computation, the original matrix A′ can be decomposed into the product of Q′∈Rm×m and R′∈Rm×n, i.e.,(17)A′=Q′×R′,and then the cloud returns Q′,R′ to the client.


#### 4.1.4.ClientVer

This algorithm is always utilized to verify whether the cloud server follows the specification and executes the computation faithfully. After receiving the results includingQ′,R′, the client needs to determine whether R′ is an upper triangular matrix; if Q′,R′ do not satisfy the correctness of the structure, the algorithm returns ⊥.With a certain constantl, fori=1tol, the client generates two column vectors ri∈0,1n randomly and ri′∈0,1m and then computes ei=Q′×R′×ri−A′×ri and ei′=Q′T×Q′×ri′−I×ri′, in detail; these equals are used to judge whether Q′ is an orthogonal matrix and whether Q′×R′ is equal to A′. If two column vectors ei and ei′ both equal to 0, it means that the result is correct, and the algorithm outputs Q′,R′. Else, the algorithm returns ⊥.


#### 4.1.5.ClientDecrpyt

Once the client affirms that the encrypted QR decomposition result has passed the verification, it will commence this algorithm to decrypt theQ′,R′ and obtain the results Q,R. Intuitively, the recover algorithm can be accomplished by multiplying the result with the inverse of the corresponding permutation matrix:(18)Q=O−1Q′,R=R′S−1.The inversion ofOcan be computed easily due to the properties of orthogonal matrix, and it means O−1=OT. When it comes to the matrix S−1, we can express as S−1=Cn−1⋯C2−1C1−1, and these sparse matrices all are elementary matrix, so the inversion of these matrices is very convenient to get, as Ci−1=11⋯−ci⋱⋮11.


### 4.2. Efficient Noninteractive Outsourcing of Large-Scale LU Factorizations

Similarly, as for the outsourcing algorithm designed for LU factorization, the encryption method for matrixB∈Rm×n is similar to the previous one, through multiplying it with two random matrices which have a specific form on both the left and right sides simultaneously, and we will explain each subalgorithm in the following part.


#### 4.2.1.KeyGen

This algorithm is executed by the client to generate two permutation matricesK∈Rm×m and V∈Rn×n. The lower triangular matrix K∈Rm×m can be formed of a series of random elementary matrices as(19)K=K1K2K3⋯Km,where the structure of Kiis as follows:(20)Ki=Ci=11⋮⋱ki⋯11,i=1,2,…,m.We can know that everyKi is not only a random elementary matrix, but also a lower triangular matrix, the detailed generation of K is demonstrated in Algorithm 4, note that the element ki is randomly selected from the interval −2q,2q, and therefore, ki is also a random variable and the probability density function of ki satisfies the following equation:(21)fKiki=12q+1,−2q<ci<2q.0,Algorithm 4: Generation of elementary perturbation matrix K.
Input: size mOutput: K(1)
SetK to be an identity matrix(2)
fori=1:mdo(3)
setKi to be an identity matrix(4)
setki to be a random real number within −2q,2q except 0, and q>0(5)
setαi=i(6)
setβi is a random integer chosen randomly within 1,αi(7)
add the element of theαith and the βith column in matrix Ki to be ki(8)
setK=K×Ki(9)
end forSimilarly, we can generate an upper triangular matrixV∈Rn×n as(22)V=V1V2V3⋯Vn,where every Vi is not only a random elementary matrix which is an upper triangular matrix as well, and the detailed generation of V is demonstrated in Algorithm 3.


#### 4.2.2.ClientEnc

The client permutates the original matrices through multiplying the secret matricesK∈Rm×m and V∈Rn×n, and then the client can obtain ciphertext matrix B′∈Rm×n after the conversion as(23)B′=K×B×V.


#### 4.2.3.CloudCom

Once the client completes the encryption algorithm and gets matrixB′∈Rm×n, the client will turn to the cloud. Then, the cloud server will use its powerful resources to accomplish the LU factorization, after the computation, the original matrix B′ can transfer into the product of L′∈Rm×m and U′∈Rm×n, i.e.,(24)B′=L′×U′,and then the cloud returns L′,U′to the client.


#### 4.2.4.ClientVer

After getting theL′,U′ returned from the cloud, determining whether L′ is a lower triangular matrix and whether U′ is an upper triangular matrix will be the first step; if L′,U′do not satisfy the correctness of the structure, the algorithm returns ⊥.Then, input a certain constantl, and fori=1tol, the client generates a random column vector ri∈0,1n and then computes ei=L′×U′×ri−B′×ri; in detail, this equal is used to determine whether L′×U′ is equal to B′. If the result of ei equals to 0, it means that the result is correct, and the algorithm outputs L′,U′. Else, the algorithm returns ⊥.


#### 4.2.5.ClientDecrpyt

Once the client ensures that the encrypted LU decomposition result is correct, it will conduct this algorithm to decrypt theL′,U′ and obtain the final results L,U. Intuitively, the decryption algorithm can be accomplished by multiplying the result L′,U′with the inverse of the corresponding permutation matrix:(25)L=K−1L′,U=U′V−1.


## 4.1. Efficient Noninteractive Outsourcing of Large-Scale QR Factorizations

Given a valid large-scale input matrixA∈Rm×n, the client wants to accomplish the QR factorizations with the assistance of the cloud server, and QR factorization will decompose matrix A∈Rm×n into a product of an orthogonal matrix Q∈Rm×m and an upper triangular matrix R∈Rm×n, i.e., A=Q×R.


### 4.1.1.KeyGen

As mentioned before, this algorithm is conducted on the client side, which can produce a secret keyKand generate an orthogonal matrix O∈Rm×m and an upper triangular matrix S∈Rn×n.Specifically, for perturbing all elements in original matrixA∈Rm×n in an effective way, we take the novel transform based on Givens matrix [23], and the orthogonal matrix O∈Rm×m is composed of kGivens matrices as(11)O=G1G2G3⋯Gk,where Gi is a Givens matrix (i=1,2,…,k), and the detailed generation of Ois shown in Algorithm 2; the client can construct an orthogonal sparse matrix by substituting certain elements located in i,i,i,j,j,i, andj,j positions of the identity matrix I∈Rm×m with some certain random parameters cosθ,−sinθ,sinθ,andcosθ respectively. And the structure of Gi can be expressed as(12)G=1⋱cosθ−sinθ1⋱1sinθcosθ⋱1.Algorithm 2: Generation of orthogonal perturbation matrix O.
Input: size mOutput: O(1)
SetO to be an identity matrix(2)
SetL=1,2,3,…,m(3)
fork=1:m/2do(4)
seti,j are random integers chosen randomly in L, and remove i,j from L(5)
setθ to be a random real number within 0,2π(6)
setOii=Ojj=cosθ, Oij=−sinθ, Oji=sinθ(7)
end for(8)
take the remaining elementl in L(9)
setOll=1The detailed generation ofO is presented in Algorithm 2 as follows:Concretely, we haveG×GT=I,G−1=GT. Since every Gi is an orthogonal and sparse matrix, we can draw the conclusion that the permutation matrix O is an orthogonal matrix certainly, and it is easy to get the inversion of O on the client side, instead of the outsourcing algorithm for matrix inverse in [18].Next, let us focus on the generation of the upper triangular matrixS∈Rn×n. The client can construct a sparse and upper triangular matrix by multiplying a series of random, consecutive upper triangular matrix. S is composed of n elementary matrices as(13)S=C1C2C3⋯Cn.Concretely, the structure ofCi is as follows:(14)Ci=11⋯ci⋱⋮11,i=1,2,…,n,where Ci is an elementary matrix, and the detailed generation of S is shown in Algorithm 3; we can see that the all nondiagonal elements of Ciare zero except ci, and the row index of the element ci is bigger than the column index of ci; note that the element ci is randomly picked within the interval −2q,2q. Therefore, ci is a random variable with its probability density function defined as(15)fCici=12q+1,−2q<ci<2q,0,and the matrices O and S are kept by the client secretly.Algorithm 3: Generation of elementary perturbation matrix S.
Input: size nOutput: S(1)
SetS to be an identity matrix(2)
fori=1:ndo(3)
setCi to be an identity matrix(4)
setci to be a random real number within −2q,2q except 0, and q>0(5)
setαi=i(6)
setβi is a random integer chosen randomly within αi,n(7)
add the element of theαith and the βith column in matrix Ci to be ci(8)
setS=S×Ci(9)
end for


### 4.1.2.ClientEnc

Considering the existence of malicious servers, it is necessary to ensure the confidentiality of the original matrix and the output matrices as well, and we propose to execute a secure and efficient matrix transforming method. A concise way to encryptAis multiplying Aby O and S on both the left and right sides simultaneously. Then, the client can obtain the final ciphertext matrix A′∈Rm×n as(16)A′=O×A×S.In conclusion, theClientEnc algorithm is completed by multiplying a series of consecutive matrices. In virtue of the property of these sparse matrices, the computation overhead required in this algorithm is affordable.


### 4.1.3.CloudCom

Once the client gets the ciphertext matrixA′∈Rm×n, the client will send it to the cloud. Afterwards, the cloud server computes the QR factorization which is based on Householder reflection; after the computation, the original matrix A′ can be decomposed into the product of Q′∈Rm×m and R′∈Rm×n, i.e.,(17)A′=Q′×R′,and then the cloud returns Q′,R′ to the client.


### 4.1.4.ClientVer

This algorithm is always utilized to verify whether the cloud server follows the specification and executes the computation faithfully. After receiving the results includingQ′,R′, the client needs to determine whether R′ is an upper triangular matrix; if Q′,R′ do not satisfy the correctness of the structure, the algorithm returns ⊥.With a certain constantl, fori=1tol, the client generates two column vectors ri∈0,1n randomly and ri′∈0,1m and then computes ei=Q′×R′×ri−A′×ri and ei′=Q′T×Q′×ri′−I×ri′, in detail; these equals are used to judge whether Q′ is an orthogonal matrix and whether Q′×R′ is equal to A′. If two column vectors ei and ei′ both equal to 0, it means that the result is correct, and the algorithm outputs Q′,R′. Else, the algorithm returns ⊥.


### 4.1.5.ClientDecrpyt

Once the client affirms that the encrypted QR decomposition result has passed the verification, it will commence this algorithm to decrypt theQ′,R′ and obtain the results Q,R. Intuitively, the recover algorithm can be accomplished by multiplying the result with the inverse of the corresponding permutation matrix:(18)Q=O−1Q′,R=R′S−1.The inversion ofOcan be computed easily due to the properties of orthogonal matrix, and it means O−1=OT. When it comes to the matrix S−1, we can express as S−1=Cn−1⋯C2−1C1−1, and these sparse matrices all are elementary matrix, so the inversion of these matrices is very convenient to get, as Ci−1=11⋯−ci⋱⋮11.


## 4.1.1.KeyGen

As mentioned before, this algorithm is conducted on the client side, which can produce a secret keyKand generate an orthogonal matrix O∈Rm×m and an upper triangular matrix S∈Rn×n.Specifically, for perturbing all elements in original matrixA∈Rm×n in an effective way, we take the novel transform based on Givens matrix [23], and the orthogonal matrix O∈Rm×m is composed of kGivens matrices as(11)O=G1G2G3⋯Gk,where Gi is a Givens matrix (i=1,2,…,k), and the detailed generation of Ois shown in Algorithm 2; the client can construct an orthogonal sparse matrix by substituting certain elements located in i,i,i,j,j,i, andj,j positions of the identity matrix I∈Rm×m with some certain random parameters cosθ,−sinθ,sinθ,andcosθ respectively. And the structure of Gi can be expressed as(12)G=1⋱cosθ−sinθ1⋱1sinθcosθ⋱1.Algorithm 2: Generation of orthogonal perturbation matrix O.
Input: size mOutput: O(1)
SetO to be an identity matrix(2)
SetL=1,2,3,…,m(3)
fork=1:m/2do(4)
seti,j are random integers chosen randomly in L, and remove i,j from L(5)
setθ to be a random real number within 0,2π(6)
setOii=Ojj=cosθ, Oij=−sinθ, Oji=sinθ(7)
end for(8)
take the remaining elementl in L(9)
setOll=1The detailed generation ofO is presented in Algorithm 2 as follows:Concretely, we haveG×GT=I,G−1=GT. Since every Gi is an orthogonal and sparse matrix, we can draw the conclusion that the permutation matrix O is an orthogonal matrix certainly, and it is easy to get the inversion of O on the client side, instead of the outsourcing algorithm for matrix inverse in [18].Next, let us focus on the generation of the upper triangular matrixS∈Rn×n. The client can construct a sparse and upper triangular matrix by multiplying a series of random, consecutive upper triangular matrix. S is composed of n elementary matrices as(13)S=C1C2C3⋯Cn.Concretely, the structure ofCi is as follows:(14)Ci=11⋯ci⋱⋮11,i=1,2,…,n,where Ci is an elementary matrix, and the detailed generation of S is shown in Algorithm 3; we can see that the all nondiagonal elements of Ciare zero except ci, and the row index of the element ci is bigger than the column index of ci; note that the element ci is randomly picked within the interval −2q,2q. Therefore, ci is a random variable with its probability density function defined as(15)fCici=12q+1,−2q<ci<2q,0,and the matrices O and S are kept by the client secretly.Algorithm 3: Generation of elementary perturbation matrix S.
Input: size nOutput: S(1)
SetS to be an identity matrix(2)
fori=1:ndo(3)
setCi to be an identity matrix(4)
setci to be a random real number within −2q,2q except 0, and q>0(5)
setαi=i(6)
setβi is a random integer chosen randomly within αi,n(7)
add the element of theαith and the βith column in matrix Ci to be ci(8)
setS=S×Ci(9)
end for


## 4.1.2.ClientEnc

Considering the existence of malicious servers, it is necessary to ensure the confidentiality of the original matrix and the output matrices as well, and we propose to execute a secure and efficient matrix transforming method. A concise way to encryptAis multiplying Aby O and S on both the left and right sides simultaneously. Then, the client can obtain the final ciphertext matrix A′∈Rm×n as(16)A′=O×A×S.In conclusion, theClientEnc algorithm is completed by multiplying a series of consecutive matrices. In virtue of the property of these sparse matrices, the computation overhead required in this algorithm is affordable.


## 4.1.3.CloudCom

Once the client gets the ciphertext matrixA′∈Rm×n, the client will send it to the cloud. Afterwards, the cloud server computes the QR factorization which is based on Householder reflection; after the computation, the original matrix A′ can be decomposed into the product of Q′∈Rm×m and R′∈Rm×n, i.e.,(17)A′=Q′×R′,and then the cloud returns Q′,R′ to the client.


## 4.1.4.ClientVer

This algorithm is always utilized to verify whether the cloud server follows the specification and executes the computation faithfully. After receiving the results includingQ′,R′, the client needs to determine whether R′ is an upper triangular matrix; if Q′,R′ do not satisfy the correctness of the structure, the algorithm returns ⊥.With a certain constantl, fori=1tol, the client generates two column vectors ri∈0,1n randomly and ri′∈0,1m and then computes ei=Q′×R′×ri−A′×ri and ei′=Q′T×Q′×ri′−I×ri′, in detail; these equals are used to judge whether Q′ is an orthogonal matrix and whether Q′×R′ is equal to A′. If two column vectors ei and ei′ both equal to 0, it means that the result is correct, and the algorithm outputs Q′,R′. Else, the algorithm returns ⊥.


## 4.1.5.ClientDecrpyt

Once the client affirms that the encrypted QR decomposition result has passed the verification, it will commence this algorithm to decrypt theQ′,R′ and obtain the results Q,R. Intuitively, the recover algorithm can be accomplished by multiplying the result with the inverse of the corresponding permutation matrix:(18)Q=O−1Q′,R=R′S−1.The inversion ofOcan be computed easily due to the properties of orthogonal matrix, and it means O−1=OT. When it comes to the matrix S−1, we can express as S−1=Cn−1⋯C2−1C1−1, and these sparse matrices all are elementary matrix, so the inversion of these matrices is very convenient to get, as Ci−1=11⋯−ci⋱⋮11.


## 4.2. Efficient Noninteractive Outsourcing of Large-Scale LU Factorizations

Similarly, as for the outsourcing algorithm designed for LU factorization, the encryption method for matrixB∈Rm×n is similar to the previous one, through multiplying it with two random matrices which have a specific form on both the left and right sides simultaneously, and we will explain each subalgorithm in the following part.


### 4.2.1.KeyGen

This algorithm is executed by the client to generate two permutation matricesK∈Rm×m and V∈Rn×n. The lower triangular matrix K∈Rm×m can be formed of a series of random elementary matrices as(19)K=K1K2K3⋯Km,where the structure of Kiis as follows:(20)Ki=Ci=11⋮⋱ki⋯11,i=1,2,…,m.We can know that everyKi is not only a random elementary matrix, but also a lower triangular matrix, the detailed generation of K is demonstrated in Algorithm 4, note that the element ki is randomly selected from the interval −2q,2q, and therefore, ki is also a random variable and the probability density function of ki satisfies the following equation:(21)fKiki=12q+1,−2q<ci<2q.0,Algorithm 4: Generation of elementary perturbation matrix K.
Input: size mOutput: K(1)
SetK to be an identity matrix(2)
fori=1:mdo(3)
setKi to be an identity matrix(4)
setki to be a random real number within −2q,2q except 0, and q>0(5)
setαi=i(6)
setβi is a random integer chosen randomly within 1,αi(7)
add the element of theαith and the βith column in matrix Ki to be ki(8)
setK=K×Ki(9)
end forSimilarly, we can generate an upper triangular matrixV∈Rn×n as(22)V=V1V2V3⋯Vn,where every Vi is not only a random elementary matrix which is an upper triangular matrix as well, and the detailed generation of V is demonstrated in Algorithm 3.


### 4.2.2.ClientEnc

The client permutates the original matrices through multiplying the secret matricesK∈Rm×m and V∈Rn×n, and then the client can obtain ciphertext matrix B′∈Rm×n after the conversion as(23)B′=K×B×V.


### 4.2.3.CloudCom

Once the client completes the encryption algorithm and gets matrixB′∈Rm×n, the client will turn to the cloud. Then, the cloud server will use its powerful resources to accomplish the LU factorization, after the computation, the original matrix B′ can transfer into the product of L′∈Rm×m and U′∈Rm×n, i.e.,(24)B′=L′×U′,and then the cloud returns L′,U′to the client.


### 4.2.4.ClientVer

After getting theL′,U′ returned from the cloud, determining whether L′ is a lower triangular matrix and whether U′ is an upper triangular matrix will be the first step; if L′,U′do not satisfy the correctness of the structure, the algorithm returns ⊥.Then, input a certain constantl, and fori=1tol, the client generates a random column vector ri∈0,1n and then computes ei=L′×U′×ri−B′×ri; in detail, this equal is used to determine whether L′×U′ is equal to B′. If the result of ei equals to 0, it means that the result is correct, and the algorithm outputs L′,U′. Else, the algorithm returns ⊥.


### 4.2.5.ClientDecrpyt

Once the client ensures that the encrypted LU decomposition result is correct, it will conduct this algorithm to decrypt theL′,U′ and obtain the final results L,U. Intuitively, the decryption algorithm can be accomplished by multiplying the result L′,U′with the inverse of the corresponding permutation matrix:(25)L=K−1L′,U=U′V−1.


## 4.2.1.KeyGen

This algorithm is executed by the client to generate two permutation matricesK∈Rm×m and V∈Rn×n. The lower triangular matrix K∈Rm×m can be formed of a series of random elementary matrices as(19)K=K1K2K3⋯Km,where the structure of Kiis as follows:(20)Ki=Ci=11⋮⋱ki⋯11,i=1,2,…,m.We can know that everyKi is not only a random elementary matrix, but also a lower triangular matrix, the detailed generation of K is demonstrated in Algorithm 4, note that the element ki is randomly selected from the interval −2q,2q, and therefore, ki is also a random variable and the probability density function of ki satisfies the following equation:(21)fKiki=12q+1,−2q<ci<2q.0,Algorithm 4: Generation of elementary perturbation matrix K.
Input: size mOutput: K(1)
SetK to be an identity matrix(2)
fori=1:mdo(3)
setKi to be an identity matrix(4)
setki to be a random real number within −2q,2q except 0, and q>0(5)
setαi=i(6)
setβi is a random integer chosen randomly within 1,αi(7)
add the element of theαith and the βith column in matrix Ki to be ki(8)
setK=K×Ki(9)
end forSimilarly, we can generate an upper triangular matrixV∈Rn×n as(22)V=V1V2V3⋯Vn,where every Vi is not only a random elementary matrix which is an upper triangular matrix as well, and the detailed generation of V is demonstrated in Algorithm 3.


## 4.2.2.ClientEnc

The client permutates the original matrices through multiplying the secret matricesK∈Rm×m and V∈Rn×n, and then the client can obtain ciphertext matrix B′∈Rm×n after the conversion as(23)B′=K×B×V.


## 4.2.3.CloudCom

Once the client completes the encryption algorithm and gets matrixB′∈Rm×n, the client will turn to the cloud. Then, the cloud server will use its powerful resources to accomplish the LU factorization, after the computation, the original matrix B′ can transfer into the product of L′∈Rm×m and U′∈Rm×n, i.e.,(24)B′=L′×U′,and then the cloud returns L′,U′to the client.


## 4.2.4.ClientVer

After getting theL′,U′ returned from the cloud, determining whether L′ is a lower triangular matrix and whether U′ is an upper triangular matrix will be the first step; if L′,U′do not satisfy the correctness of the structure, the algorithm returns ⊥.Then, input a certain constantl, and fori=1tol, the client generates a random column vector ri∈0,1n and then computes ei=L′×U′×ri−B′×ri; in detail, this equal is used to determine whether L′×U′ is equal to B′. If the result of ei equals to 0, it means that the result is correct, and the algorithm outputs L′,U′. Else, the algorithm returns ⊥.


## 4.2.5.ClientDecrpyt

Once the client ensures that the encrypted LU decomposition result is correct, it will conduct this algorithm to decrypt theL′,U′ and obtain the final results L,U. Intuitively, the decryption algorithm can be accomplished by multiplying the result L′,U′with the inverse of the corresponding permutation matrix:(25)L=K−1L′,U=U′V−1.


## 5. Theoretical Evaluations

In this section, the elaborate theoretical analysis of our proposed algorithm and efficiency comparisons will be shown.


### 5.1. Security Analysis

#### 5.1.1. Correctness

Theorem 1.
For any valid large-scale input matrixA∈Rm×n,B∈Rm×n, our proposed outsourcing algorithms are correct exactly.Proof.
If the cloud server performs the task correctly, we can getQ′andR′ which satisfy A′=Q′×R′, OAS=Q′×R′, because cloud performs the QR factorization by Householder reflection, and we can know that the result of QR factorization is unique. So, we can get Q′=O×Q and R′=R×S, when we use equation (18) to decrypt Q′ and R′, and the results of ClientDecrpyt are correct exactly. As for LU outsourcing factorization, we can get L′ and U′when the cloud server performs the task correctly, which satisfy B′=L′×U′ and KBV=L′×U′, because cloud performs the LU factorization by Gauss elimination, and we can know that the result of LU factorization is unique. So, we can obtain L′=K×L and U′=U×V through equation (25). Above all, we can say our proposed outsourcing algorithms are correct exactly.


#### 5.1.2. Privacy Security

Theorem 2.
For any valid large-scale input matrixA,B∈Rm×n, the encrypted matrices A′=O×A×S and B′=K×B×Vare computationally indistinguishable under chosen-plaintext attack, and A′or B′ is computationally indistinguishable from a random matrix, respectively, which means that our proposed algorithm satisfies the security definition of data privacy.Proof.
We consider the input privacy firstly, and in other words, it means the probability that an adversary can infer the information of the original matrixAfrom A′ is negligible, where A′=O×A×S. In the ClientDecrpyt algorithm, O and Sare permutation matrices, O is an orthogonal matrix based on Givens matrix, and S is an upper triangular matrix specially, where O=G1G2G3⋯Gk and S=C1C2C3⋯Cn; we can know each Gi processes two rows of Aand each Si processes one column of A. We assume that A′=O×A×S=O×A×S=A0×S. The elements in ith row and the kth row of matrix A0can be described as follows, which is concealed by arbitrary parameters cosθ,sinθ, where θ∈0,π,(26)aij0=cosθaij−sinθakj,akj0=sinθaij+cosθakj.
By the next encryption step, the elements ofA′ are easy to deduce that(27)aij′=aij0+ciaij′0.
As we mentioned before, these parameterscosθ,sinθ,ci are chosen by the client randomly and all are blind to adversary A, in order to recover aij, the adversary needs to access cosθ,sinθ,ci and akj even if the adversary knows the encryption algorithm ClientDecrpyt, however, the number of unknown variables is more than the number of equations, so it is actually impossible to recover aij from aij′, in terms of the ClientDecrpyt algorithm, the client generates encryption matrices by O=G1G2G3⋯Gk and S=C1C2C3⋯Cn, due to all θ in Gi,i∈1,k satisfy the uniform distribution of 0,π, the random parameterciin Sis selected from the interval −2q,2q randomly, the total probability that an adversary can recover aijform aij′is the product of the probability of recovering θ and ciand also need to get the position of another element akj, so the success probability of an adversary is 1/∞×∞by launching a brute-force attack to obtain the two sets θ1,θ2,…,θk and c1,c2,…,cn, and it is small enough that an adversary can recover aij is definitely impossible.
Now, we consider the input privacy ofB′; in other words, we need to prove that the probability that an adversary can infer the information of the original matrix B from B′is negligible, where B′=K×B×V. In the ClientDecrpyt algorithm, Kand Vare elementary permutation matrices, where K=K1K2K3⋯Km and V=V1V2V3⋯Vn; we can know that each Ki processes one row of Band each Vi processes one column of B, so we can say that the elementary permutation matrices will process mrows and ncolumns of the original matrix in total. We assume that B′=K×B×V=K×B×V=B0×V. The elements in ith row and the jth row of matrix B0 can be described as follows, which is concealed by arbitrary parameterski, where ki∈−2q,2q:(28)bij0=kibi′j+bij.
By the next encryption step, the elements ofB′are easy to deduce that(29)bij′=bij0+vibij′0.
Because these parameterski,vi are chosen by the client randomly and all are blind to adversary A, and the random parameters ki,vi in K andV are selected from the interval −2q,2qrandomly, the total probability that an adversary can recover bij form bij′is the product of the probability of recovering ki and vi and also need to get the position of another element bi′j, so the success probability of an adversary is 1/∞×∞by launching a brute-force attack to obtain the two sets k1,k2,…,km and v1,v2,…,vn, and it is small enough that an adversary can recover bij is definitely impossible.
If there is no oracleClientEnc, we can say that the advantage of adversary A can be neglected actually. As for a CPA indistinguishability experiment, an adversary A outputs two different integers a0,a1, and x←0,1is picked randomly, and ClientEnc is calculated and given to adversary A; A predicts x′ with the access to the oracle ClientEncand eventually outputs x′, if x′=x, it means adversary A succeeds, and the successful prediction mainly relies on the following cases:Case1: the oracle chooses theKto answer at least one of A’s queries. Because Kwill be randomly chosen for each query, the probability is Prcase1≤neglλ. Thus, adversary A can tell and get x′=xcorrectly.Case2: the oracle never chooses theK to answer at least one of A’s queries. As the output after the ClientEnc algorithm is random, A obtains nothing about which of its values was transformed, and it leads to the probability that x′=x is no more than 1/2+neglλ.
The probability of successful prediction can be deduced as follows:(30)PrExp=1=PrExp=1|case1Prcase1+PrExp=1|case2Prcase2≤Prcase1+PrExp=1|case2≤neglλ+12.
As discussed before, the advantage can be neglected actually, it means that this encrypted matrix is computationally indistinguishable from the matrix generated stochastically and the cloud server cannot get any individual private knowledge contained in the original matrixA,B from A′,B′. Thus, we can draw the conclusion that the input privacy is well protected.Theorem 3.
For any encrypted matrixA′=O×A×S and B′=K×B×V, after the cloud server conducts the QR and LU factorization and gets the factor matrices Q′,R′ and L′,U′, the adversary cannot obtain any private information from original matrices Q,R and L,U.Proof.
Based on the previous analysis, matrices O and S are generated and kept by the client secretly, so the adversary cannot obtain matrices O and S; it is undoubted that O-1 and S-1 cannot be obtained, so we can say the adversary is unable to recover the factor matrices according to equation (18) without matrices O-1 and S-1. As for LU outsourcing factorization, since the adversary cannot obtain the encrypted matrices K and V and cannot obtain K-1 and V-1 as well, so it is obvious that the adversary is unable to recover L and U according to equation (25) without K−1 and V−1 can the adversary recover the result according to equation (25). All these lead up to that our proposed algorithm satisfies the security definition of data privacy including input privacy and output privacy.


#### 5.1.3. Verifiability

Theorem 4.
For any valid large-scale matrixA∈Rm×n, our proposed algorithm is verifiable exactly with a probability of approximated to 1.Proof.
The vectorsei,ei′ are generated in our concrete method of verification. However, ei′ is used to analyse whether Q is an orthogonal matrix as we need. So, we simply consider the scenario where the equality ei=Q′×R′×ri−A′×ri=e1i,e2i,…,eniT∈0,1n, where ri=r1i,r2i,…,rniT∈0,1n. n is the number of columns in the matrix A′. Assume that the answer from the server is wrong, we can get the inequality Q′×R′−A′≠0, which further results in ei≠0, it means that there will be at least one nonzero element in e1i,e2i,…,eniT, and we assume that the nonzero element locates in kth row, 1≤k≤n, i.e., eki=0. We can obtain(31)Prei=0,0,…,0T≤Preki=0≤12.
Because the above process will be conductedltimes independently, so(32)PrClientVerA′,l,Q′,R′⟶true|result is incorrect≤Prei=0,0,…,0Tl≤12l.
The same procedure may be easily adapted to obtain(33)PrClientVerB′,l,L′,U′⟶true|result is incorrect≤12l.
We can draw the conclusion that the incorrect result is impossible to pass the verification, and our proposed algorithm is verifiable exactly with a probability of approximated to 1.


#### 5.1.4. Efficiency

For any valid large-scale input matrixA∈Rm×n, client performs QR and LU factorizations on its own requires O2m2n+m3 and O1/3m2n computational complexity by employing Householder reflection and Gauss elimination methods, respectively. Considering enormous data in practice, the values of m and n will be large extremely, which leads to the high computational complexity which is unacceptable for the client. In our proposed algorithms, the total complexity of the client is much less than O2m2n+m3. Now, we analyse the time cost in our outsourcing algorithms executed by the client thoroughly.In theKeyGen subalgorithm, O and S are permutation matrices generated by client, O is an orthogonal matrix, and S is an upper triangular matrix specially, the detailed generative process is shown in Algorithm 2 and Algorithm 3, and the total cost is Om+n.In theClientEnc subalgorithm, client performs the low-complexity matrix transformation to encrypt A with A′=O×A×S whereO∈Rm×n,S∈Rn×n. The matrix multiplication between two dense matrices can be avoided due to O and Sare two sparse matrices. The complexity of ClientEncA,K⟶A′ is no more than Omn.In theCloudCom subalgorithm, the cloud completes QR factorization on ciphertext matrix A′ which takes computations with O2m2n+m3complexity.In theClientVer subalgorithm, client needs to calculate vector-matrix multiplication instead of calculate matrix-matrix multiplication, and the verification process needs to be performed at most ltimes. Due to the ClientVer subalgorithm only includes vector-matrix multiplication and l≪n, the overall complexity of ClientVer on the client side is Om2+mn.In theClientDecrpyt subalgorithm, we only need the inversion of Oand Sto decrypt the results which are received from cloud when the results have passed the ClientVer process. And as we talked in Section 4, the inversion matrices of O and Sare both convenient to generate. Hence, the ClientDecrpyt only contains the sparse matrix-matrix multiplication, and we can know that the complexity of decryption is Om2+mn.The efficiency analysis of LU factorization is similar, and we list the concrete computational complexity of each subalgorithm in the next section. To sum up, our proposed scheme requires computational complexity ofOmaxm2,mn, which is less than the computational complexity of Om2n of conducting QR or LU factorization, so it is fully in line with the design goals of efficiency.


### 5.2. Efficiency Comparisons

In this section, we further compare our scheme with those of the most related schemes mentioned in Section2. We demonstrate the concrete analysis in Tables 1 and 2. These tables show the comparison regarding the computation complexity at each step and the whole communication overhead of the proposed outsourcing algorithm for QR and LU factorization, respectively, and other properties as well.Table 1
Comparisons of the outsourcing scheme of QR factorization.
KeyGenClient encryptClient verifyClient decryptNoninteractiveCommunication overheadWork [18]Om2+m+nO3m2+6mn—O9m2+4mnNo (4 interaction)C5m2+8mn+n2Work [19]ON2Omn×N2—Om2+mn×N2YesC2m2+mnOur schemeOm+nOm2+mnOm2+mnOm2+mnYesC2m2+mnTable 2
Comparisons of the outsourcing scheme of LU factorization.
KeyGenClient encryptClient verifyClient decryptNoninteractiveCommunication overheadWork [18]Om2O2m2+2n2+6mn—O6m2+2n2+4mnNo (4 interaction)C4m2+8mn+n2Our schemeOm+nOm2+mnOmnOm2+mnYesC2m2+mnWhen calculating the complexity of the QR decomposition outsourcing scheme in work [19], which is using homomorphic encryption (HE), the parameter N denotes the polynomial modulus and is always a power of two, such as 1024, 2048, and 4096. And we assume that the computational complexity of modular multiplication is equal to multiplication, but in real scenario, the time complexity of modular multiplication operations is greater than that of multiplication operation.As we discussed before, we demonstrate the computation complexity in each stage. And we can observe that the computational complexity in each stage in our scheme is smaller than other works, the computational complexity in theClientVer subalgorithm is affordable as for the client, and the total communication overhead in our scheme only includes the overhead of sending the encryption matrix A′ to the cloud server and receiving the results from the cloud. Our proposed scheme realizes the reduction of the computational overhead from Om2n to Omaxm2,mn on the client side.Specifically speaking, compared with the scheme in [18], the client needs to outsource large-scale matrix multiplication and large-scale matrix inversion, more than outsourcing QR and LU factorizations, which inevitably lead to an increase in computation and communication overhead for the client. Meanwhile, their scheme requires many interactions with the cloud, and every matrix for interaction still needs to be encrypted for enhanced privacy protection, which cause the high communication overhead on the client. However, our proposed scheme is noninteractive, so the client only needs to send matrix and receive results, the interactions are no longer needed, and the client can complete outsourcing process locally with little cost by employing our scheme, which not only guarantees the privacy security but also reduces the client’s computation and communication overhead.In [19], they presented the implementation of QR factorizations through a homomorphic encryption method based on ring learning with errors, note that the plaintexts to be encrypted should only be integers, if the inputs are decimals or floating numbers, they first need be enlarged by a scaling factor, rounded to the nearest integers, only in this way, the inputs can accomplish the homomorphic processing, and their algorithm is subject to low efficiency. Furthermore, the experiment in their scheme has not applied to large-scale matrices and fails to be practical in applications, so we cannot evaluate the performance of their scheme. Compared with the existing scheme [19], our scheme does not require additional data operations, and our scheme has more accuracy and efficiency and fulfills extra verification function as well.To sum up, as for the client, the client has already outsourced the most complex matrix operation to the cloud and enjoys significant cost savings by deploying our proposal, and the detailed experimental results will be presented in the next section. One can see that regarding computational complexity and communication overhead, the proposed scheme reduces the computational overhead of direct computation successfully, and it has considerably better performance than the existing research.


## 5.1. Security Analysis

### 5.1.1. Correctness

Theorem 1.
For any valid large-scale input matrixA∈Rm×n,B∈Rm×n, our proposed outsourcing algorithms are correct exactly.Proof.
If the cloud server performs the task correctly, we can getQ′andR′ which satisfy A′=Q′×R′, OAS=Q′×R′, because cloud performs the QR factorization by Householder reflection, and we can know that the result of QR factorization is unique. So, we can get Q′=O×Q and R′=R×S, when we use equation (18) to decrypt Q′ and R′, and the results of ClientDecrpyt are correct exactly. As for LU outsourcing factorization, we can get L′ and U′when the cloud server performs the task correctly, which satisfy B′=L′×U′ and KBV=L′×U′, because cloud performs the LU factorization by Gauss elimination, and we can know that the result of LU factorization is unique. So, we can obtain L′=K×L and U′=U×V through equation (25). Above all, we can say our proposed outsourcing algorithms are correct exactly.


### 5.1.2. Privacy Security

Theorem 2.
For any valid large-scale input matrixA,B∈Rm×n, the encrypted matrices A′=O×A×S and B′=K×B×Vare computationally indistinguishable under chosen-plaintext attack, and A′or B′ is computationally indistinguishable from a random matrix, respectively, which means that our proposed algorithm satisfies the security definition of data privacy.Proof.
We consider the input privacy firstly, and in other words, it means the probability that an adversary can infer the information of the original matrixAfrom A′ is negligible, where A′=O×A×S. In the ClientDecrpyt algorithm, O and Sare permutation matrices, O is an orthogonal matrix based on Givens matrix, and S is an upper triangular matrix specially, where O=G1G2G3⋯Gk and S=C1C2C3⋯Cn; we can know each Gi processes two rows of Aand each Si processes one column of A. We assume that A′=O×A×S=O×A×S=A0×S. The elements in ith row and the kth row of matrix A0can be described as follows, which is concealed by arbitrary parameters cosθ,sinθ, where θ∈0,π,(26)aij0=cosθaij−sinθakj,akj0=sinθaij+cosθakj.
By the next encryption step, the elements ofA′ are easy to deduce that(27)aij′=aij0+ciaij′0.
As we mentioned before, these parameterscosθ,sinθ,ci are chosen by the client randomly and all are blind to adversary A, in order to recover aij, the adversary needs to access cosθ,sinθ,ci and akj even if the adversary knows the encryption algorithm ClientDecrpyt, however, the number of unknown variables is more than the number of equations, so it is actually impossible to recover aij from aij′, in terms of the ClientDecrpyt algorithm, the client generates encryption matrices by O=G1G2G3⋯Gk and S=C1C2C3⋯Cn, due to all θ in Gi,i∈1,k satisfy the uniform distribution of 0,π, the random parameterciin Sis selected from the interval −2q,2q randomly, the total probability that an adversary can recover aijform aij′is the product of the probability of recovering θ and ciand also need to get the position of another element akj, so the success probability of an adversary is 1/∞×∞by launching a brute-force attack to obtain the two sets θ1,θ2,…,θk and c1,c2,…,cn, and it is small enough that an adversary can recover aij is definitely impossible.
Now, we consider the input privacy ofB′; in other words, we need to prove that the probability that an adversary can infer the information of the original matrix B from B′is negligible, where B′=K×B×V. In the ClientDecrpyt algorithm, Kand Vare elementary permutation matrices, where K=K1K2K3⋯Km and V=V1V2V3⋯Vn; we can know that each Ki processes one row of Band each Vi processes one column of B, so we can say that the elementary permutation matrices will process mrows and ncolumns of the original matrix in total. We assume that B′=K×B×V=K×B×V=B0×V. The elements in ith row and the jth row of matrix B0 can be described as follows, which is concealed by arbitrary parameterski, where ki∈−2q,2q:(28)bij0=kibi′j+bij.
By the next encryption step, the elements ofB′are easy to deduce that(29)bij′=bij0+vibij′0.
Because these parameterski,vi are chosen by the client randomly and all are blind to adversary A, and the random parameters ki,vi in K andV are selected from the interval −2q,2qrandomly, the total probability that an adversary can recover bij form bij′is the product of the probability of recovering ki and vi and also need to get the position of another element bi′j, so the success probability of an adversary is 1/∞×∞by launching a brute-force attack to obtain the two sets k1,k2,…,km and v1,v2,…,vn, and it is small enough that an adversary can recover bij is definitely impossible.
If there is no oracleClientEnc, we can say that the advantage of adversary A can be neglected actually. As for a CPA indistinguishability experiment, an adversary A outputs two different integers a0,a1, and x←0,1is picked randomly, and ClientEnc is calculated and given to adversary A; A predicts x′ with the access to the oracle ClientEncand eventually outputs x′, if x′=x, it means adversary A succeeds, and the successful prediction mainly relies on the following cases:Case1: the oracle chooses theKto answer at least one of A’s queries. Because Kwill be randomly chosen for each query, the probability is Prcase1≤neglλ. Thus, adversary A can tell and get x′=xcorrectly.Case2: the oracle never chooses theK to answer at least one of A’s queries. As the output after the ClientEnc algorithm is random, A obtains nothing about which of its values was transformed, and it leads to the probability that x′=x is no more than 1/2+neglλ.
The probability of successful prediction can be deduced as follows:(30)PrExp=1=PrExp=1|case1Prcase1+PrExp=1|case2Prcase2≤Prcase1+PrExp=1|case2≤neglλ+12.
As discussed before, the advantage can be neglected actually, it means that this encrypted matrix is computationally indistinguishable from the matrix generated stochastically and the cloud server cannot get any individual private knowledge contained in the original matrixA,B from A′,B′. Thus, we can draw the conclusion that the input privacy is well protected.Theorem 3.
For any encrypted matrixA′=O×A×S and B′=K×B×V, after the cloud server conducts the QR and LU factorization and gets the factor matrices Q′,R′ and L′,U′, the adversary cannot obtain any private information from original matrices Q,R and L,U.Proof.
Based on the previous analysis, matrices O and S are generated and kept by the client secretly, so the adversary cannot obtain matrices O and S; it is undoubted that O-1 and S-1 cannot be obtained, so we can say the adversary is unable to recover the factor matrices according to equation (18) without matrices O-1 and S-1. As for LU outsourcing factorization, since the adversary cannot obtain the encrypted matrices K and V and cannot obtain K-1 and V-1 as well, so it is obvious that the adversary is unable to recover L and U according to equation (25) without K−1 and V−1 can the adversary recover the result according to equation (25). All these lead up to that our proposed algorithm satisfies the security definition of data privacy including input privacy and output privacy.


### 5.1.3. Verifiability

Theorem 4.
For any valid large-scale matrixA∈Rm×n, our proposed algorithm is verifiable exactly with a probability of approximated to 1.Proof.
The vectorsei,ei′ are generated in our concrete method of verification. However, ei′ is used to analyse whether Q is an orthogonal matrix as we need. So, we simply consider the scenario where the equality ei=Q′×R′×ri−A′×ri=e1i,e2i,…,eniT∈0,1n, where ri=r1i,r2i,…,rniT∈0,1n. n is the number of columns in the matrix A′. Assume that the answer from the server is wrong, we can get the inequality Q′×R′−A′≠0, which further results in ei≠0, it means that there will be at least one nonzero element in e1i,e2i,…,eniT, and we assume that the nonzero element locates in kth row, 1≤k≤n, i.e., eki=0. We can obtain(31)Prei=0,0,…,0T≤Preki=0≤12.
Because the above process will be conductedltimes independently, so(32)PrClientVerA′,l,Q′,R′⟶true|result is incorrect≤Prei=0,0,…,0Tl≤12l.
The same procedure may be easily adapted to obtain(33)PrClientVerB′,l,L′,U′⟶true|result is incorrect≤12l.
We can draw the conclusion that the incorrect result is impossible to pass the verification, and our proposed algorithm is verifiable exactly with a probability of approximated to 1.


### 5.1.4. Efficiency

For any valid large-scale input matrixA∈Rm×n, client performs QR and LU factorizations on its own requires O2m2n+m3 and O1/3m2n computational complexity by employing Householder reflection and Gauss elimination methods, respectively. Considering enormous data in practice, the values of m and n will be large extremely, which leads to the high computational complexity which is unacceptable for the client. In our proposed algorithms, the total complexity of the client is much less than O2m2n+m3. Now, we analyse the time cost in our outsourcing algorithms executed by the client thoroughly.In theKeyGen subalgorithm, O and S are permutation matrices generated by client, O is an orthogonal matrix, and S is an upper triangular matrix specially, the detailed generative process is shown in Algorithm 2 and Algorithm 3, and the total cost is Om+n.In theClientEnc subalgorithm, client performs the low-complexity matrix transformation to encrypt A with A′=O×A×S whereO∈Rm×n,S∈Rn×n. The matrix multiplication between two dense matrices can be avoided due to O and Sare two sparse matrices. The complexity of ClientEncA,K⟶A′ is no more than Omn.In theCloudCom subalgorithm, the cloud completes QR factorization on ciphertext matrix A′ which takes computations with O2m2n+m3complexity.In theClientVer subalgorithm, client needs to calculate vector-matrix multiplication instead of calculate matrix-matrix multiplication, and the verification process needs to be performed at most ltimes. Due to the ClientVer subalgorithm only includes vector-matrix multiplication and l≪n, the overall complexity of ClientVer on the client side is Om2+mn.In theClientDecrpyt subalgorithm, we only need the inversion of Oand Sto decrypt the results which are received from cloud when the results have passed the ClientVer process. And as we talked in Section 4, the inversion matrices of O and Sare both convenient to generate. Hence, the ClientDecrpyt only contains the sparse matrix-matrix multiplication, and we can know that the complexity of decryption is Om2+mn.The efficiency analysis of LU factorization is similar, and we list the concrete computational complexity of each subalgorithm in the next section. To sum up, our proposed scheme requires computational complexity ofOmaxm2,mn, which is less than the computational complexity of Om2n of conducting QR or LU factorization, so it is fully in line with the design goals of efficiency.


## 5.1.1. Correctness

Theorem 1.
For any valid large-scale input matrixA∈Rm×n,B∈Rm×n, our proposed outsourcing algorithms are correct exactly.Proof.
If the cloud server performs the task correctly, we can getQ′andR′ which satisfy A′=Q′×R′, OAS=Q′×R′, because cloud performs the QR factorization by Householder reflection, and we can know that the result of QR factorization is unique. So, we can get Q′=O×Q and R′=R×S, when we use equation (18) to decrypt Q′ and R′, and the results of ClientDecrpyt are correct exactly. As for LU outsourcing factorization, we can get L′ and U′when the cloud server performs the task correctly, which satisfy B′=L′×U′ and KBV=L′×U′, because cloud performs the LU factorization by Gauss elimination, and we can know that the result of LU factorization is unique. So, we can obtain L′=K×L and U′=U×V through equation (25). Above all, we can say our proposed outsourcing algorithms are correct exactly.


## 5.1.2. Privacy Security

Theorem 2.
For any valid large-scale input matrixA,B∈Rm×n, the encrypted matrices A′=O×A×S and B′=K×B×Vare computationally indistinguishable under chosen-plaintext attack, and A′or B′ is computationally indistinguishable from a random matrix, respectively, which means that our proposed algorithm satisfies the security definition of data privacy.Proof.
We consider the input privacy firstly, and in other words, it means the probability that an adversary can infer the information of the original matrixAfrom A′ is negligible, where A′=O×A×S. In the ClientDecrpyt algorithm, O and Sare permutation matrices, O is an orthogonal matrix based on Givens matrix, and S is an upper triangular matrix specially, where O=G1G2G3⋯Gk and S=C1C2C3⋯Cn; we can know each Gi processes two rows of Aand each Si processes one column of A. We assume that A′=O×A×S=O×A×S=A0×S. The elements in ith row and the kth row of matrix A0can be described as follows, which is concealed by arbitrary parameters cosθ,sinθ, where θ∈0,π,(26)aij0=cosθaij−sinθakj,akj0=sinθaij+cosθakj.
By the next encryption step, the elements ofA′ are easy to deduce that(27)aij′=aij0+ciaij′0.
As we mentioned before, these parameterscosθ,sinθ,ci are chosen by the client randomly and all are blind to adversary A, in order to recover aij, the adversary needs to access cosθ,sinθ,ci and akj even if the adversary knows the encryption algorithm ClientDecrpyt, however, the number of unknown variables is more than the number of equations, so it is actually impossible to recover aij from aij′, in terms of the ClientDecrpyt algorithm, the client generates encryption matrices by O=G1G2G3⋯Gk and S=C1C2C3⋯Cn, due to all θ in Gi,i∈1,k satisfy the uniform distribution of 0,π, the random parameterciin Sis selected from the interval −2q,2q randomly, the total probability that an adversary can recover aijform aij′is the product of the probability of recovering θ and ciand also need to get the position of another element akj, so the success probability of an adversary is 1/∞×∞by launching a brute-force attack to obtain the two sets θ1,θ2,…,θk and c1,c2,…,cn, and it is small enough that an adversary can recover aij is definitely impossible.
Now, we consider the input privacy ofB′; in other words, we need to prove that the probability that an adversary can infer the information of the original matrix B from B′is negligible, where B′=K×B×V. In the ClientDecrpyt algorithm, Kand Vare elementary permutation matrices, where K=K1K2K3⋯Km and V=V1V2V3⋯Vn; we can know that each Ki processes one row of Band each Vi processes one column of B, so we can say that the elementary permutation matrices will process mrows and ncolumns of the original matrix in total. We assume that B′=K×B×V=K×B×V=B0×V. The elements in ith row and the jth row of matrix B0 can be described as follows, which is concealed by arbitrary parameterski, where ki∈−2q,2q:(28)bij0=kibi′j+bij.
By the next encryption step, the elements ofB′are easy to deduce that(29)bij′=bij0+vibij′0.
Because these parameterski,vi are chosen by the client randomly and all are blind to adversary A, and the random parameters ki,vi in K andV are selected from the interval −2q,2qrandomly, the total probability that an adversary can recover bij form bij′is the product of the probability of recovering ki and vi and also need to get the position of another element bi′j, so the success probability of an adversary is 1/∞×∞by launching a brute-force attack to obtain the two sets k1,k2,…,km and v1,v2,…,vn, and it is small enough that an adversary can recover bij is definitely impossible.
If there is no oracleClientEnc, we can say that the advantage of adversary A can be neglected actually. As for a CPA indistinguishability experiment, an adversary A outputs two different integers a0,a1, and x←0,1is picked randomly, and ClientEnc is calculated and given to adversary A; A predicts x′ with the access to the oracle ClientEncand eventually outputs x′, if x′=x, it means adversary A succeeds, and the successful prediction mainly relies on the following cases:Case1: the oracle chooses theKto answer at least one of A’s queries. Because Kwill be randomly chosen for each query, the probability is Prcase1≤neglλ. Thus, adversary A can tell and get x′=xcorrectly.Case2: the oracle never chooses theK to answer at least one of A’s queries. As the output after the ClientEnc algorithm is random, A obtains nothing about which of its values was transformed, and it leads to the probability that x′=x is no more than 1/2+neglλ.
The probability of successful prediction can be deduced as follows:(30)PrExp=1=PrExp=1|case1Prcase1+PrExp=1|case2Prcase2≤Prcase1+PrExp=1|case2≤neglλ+12.
As discussed before, the advantage can be neglected actually, it means that this encrypted matrix is computationally indistinguishable from the matrix generated stochastically and the cloud server cannot get any individual private knowledge contained in the original matrixA,B from A′,B′. Thus, we can draw the conclusion that the input privacy is well protected.Theorem 3.
For any encrypted matrixA′=O×A×S and B′=K×B×V, after the cloud server conducts the QR and LU factorization and gets the factor matrices Q′,R′ and L′,U′, the adversary cannot obtain any private information from original matrices Q,R and L,U.Proof.
Based on the previous analysis, matrices O and S are generated and kept by the client secretly, so the adversary cannot obtain matrices O and S; it is undoubted that O-1 and S-1 cannot be obtained, so we can say the adversary is unable to recover the factor matrices according to equation (18) without matrices O-1 and S-1. As for LU outsourcing factorization, since the adversary cannot obtain the encrypted matrices K and V and cannot obtain K-1 and V-1 as well, so it is obvious that the adversary is unable to recover L and U according to equation (25) without K−1 and V−1 can the adversary recover the result according to equation (25). All these lead up to that our proposed algorithm satisfies the security definition of data privacy including input privacy and output privacy.


## 5.1.3. Verifiability

Theorem 4.
For any valid large-scale matrixA∈Rm×n, our proposed algorithm is verifiable exactly with a probability of approximated to 1.Proof.
The vectorsei,ei′ are generated in our concrete method of verification. However, ei′ is used to analyse whether Q is an orthogonal matrix as we need. So, we simply consider the scenario where the equality ei=Q′×R′×ri−A′×ri=e1i,e2i,…,eniT∈0,1n, where ri=r1i,r2i,…,rniT∈0,1n. n is the number of columns in the matrix A′. Assume that the answer from the server is wrong, we can get the inequality Q′×R′−A′≠0, which further results in ei≠0, it means that there will be at least one nonzero element in e1i,e2i,…,eniT, and we assume that the nonzero element locates in kth row, 1≤k≤n, i.e., eki=0. We can obtain(31)Prei=0,0,…,0T≤Preki=0≤12.
Because the above process will be conductedltimes independently, so(32)PrClientVerA′,l,Q′,R′⟶true|result is incorrect≤Prei=0,0,…,0Tl≤12l.
The same procedure may be easily adapted to obtain(33)PrClientVerB′,l,L′,U′⟶true|result is incorrect≤12l.
We can draw the conclusion that the incorrect result is impossible to pass the verification, and our proposed algorithm is verifiable exactly with a probability of approximated to 1.


## 5.1.4. Efficiency

For any valid large-scale input matrixA∈Rm×n, client performs QR and LU factorizations on its own requires O2m2n+m3 and O1/3m2n computational complexity by employing Householder reflection and Gauss elimination methods, respectively. Considering enormous data in practice, the values of m and n will be large extremely, which leads to the high computational complexity which is unacceptable for the client. In our proposed algorithms, the total complexity of the client is much less than O2m2n+m3. Now, we analyse the time cost in our outsourcing algorithms executed by the client thoroughly.In theKeyGen subalgorithm, O and S are permutation matrices generated by client, O is an orthogonal matrix, and S is an upper triangular matrix specially, the detailed generative process is shown in Algorithm 2 and Algorithm 3, and the total cost is Om+n.In theClientEnc subalgorithm, client performs the low-complexity matrix transformation to encrypt A with A′=O×A×S whereO∈Rm×n,S∈Rn×n. The matrix multiplication between two dense matrices can be avoided due to O and Sare two sparse matrices. The complexity of ClientEncA,K⟶A′ is no more than Omn.In theCloudCom subalgorithm, the cloud completes QR factorization on ciphertext matrix A′ which takes computations with O2m2n+m3complexity.In theClientVer subalgorithm, client needs to calculate vector-matrix multiplication instead of calculate matrix-matrix multiplication, and the verification process needs to be performed at most ltimes. Due to the ClientVer subalgorithm only includes vector-matrix multiplication and l≪n, the overall complexity of ClientVer on the client side is Om2+mn.In theClientDecrpyt subalgorithm, we only need the inversion of Oand Sto decrypt the results which are received from cloud when the results have passed the ClientVer process. And as we talked in Section 4, the inversion matrices of O and Sare both convenient to generate. Hence, the ClientDecrpyt only contains the sparse matrix-matrix multiplication, and we can know that the complexity of decryption is Om2+mn.The efficiency analysis of LU factorization is similar, and we list the concrete computational complexity of each subalgorithm in the next section. To sum up, our proposed scheme requires computational complexity ofOmaxm2,mn, which is less than the computational complexity of Om2n of conducting QR or LU factorization, so it is fully in line with the design goals of efficiency.


## 5.2. Efficiency Comparisons

In this section, we further compare our scheme with those of the most related schemes mentioned in Section2. We demonstrate the concrete analysis in Tables 1 and 2. These tables show the comparison regarding the computation complexity at each step and the whole communication overhead of the proposed outsourcing algorithm for QR and LU factorization, respectively, and other properties as well.Table 1
Comparisons of the outsourcing scheme of QR factorization.
KeyGenClient encryptClient verifyClient decryptNoninteractiveCommunication overheadWork [18]Om2+m+nO3m2+6mn—O9m2+4mnNo (4 interaction)C5m2+8mn+n2Work [19]ON2Omn×N2—Om2+mn×N2YesC2m2+mnOur schemeOm+nOm2+mnOm2+mnOm2+mnYesC2m2+mnTable 2
Comparisons of the outsourcing scheme of LU factorization.
KeyGenClient encryptClient verifyClient decryptNoninteractiveCommunication overheadWork [18]Om2O2m2+2n2+6mn—O6m2+2n2+4mnNo (4 interaction)C4m2+8mn+n2Our schemeOm+nOm2+mnOmnOm2+mnYesC2m2+mnWhen calculating the complexity of the QR decomposition outsourcing scheme in work [19], which is using homomorphic encryption (HE), the parameter N denotes the polynomial modulus and is always a power of two, such as 1024, 2048, and 4096. And we assume that the computational complexity of modular multiplication is equal to multiplication, but in real scenario, the time complexity of modular multiplication operations is greater than that of multiplication operation.As we discussed before, we demonstrate the computation complexity in each stage. And we can observe that the computational complexity in each stage in our scheme is smaller than other works, the computational complexity in theClientVer subalgorithm is affordable as for the client, and the total communication overhead in our scheme only includes the overhead of sending the encryption matrix A′ to the cloud server and receiving the results from the cloud. Our proposed scheme realizes the reduction of the computational overhead from Om2n to Omaxm2,mn on the client side.Specifically speaking, compared with the scheme in [18], the client needs to outsource large-scale matrix multiplication and large-scale matrix inversion, more than outsourcing QR and LU factorizations, which inevitably lead to an increase in computation and communication overhead for the client. Meanwhile, their scheme requires many interactions with the cloud, and every matrix for interaction still needs to be encrypted for enhanced privacy protection, which cause the high communication overhead on the client. However, our proposed scheme is noninteractive, so the client only needs to send matrix and receive results, the interactions are no longer needed, and the client can complete outsourcing process locally with little cost by employing our scheme, which not only guarantees the privacy security but also reduces the client’s computation and communication overhead.In [19], they presented the implementation of QR factorizations through a homomorphic encryption method based on ring learning with errors, note that the plaintexts to be encrypted should only be integers, if the inputs are decimals or floating numbers, they first need be enlarged by a scaling factor, rounded to the nearest integers, only in this way, the inputs can accomplish the homomorphic processing, and their algorithm is subject to low efficiency. Furthermore, the experiment in their scheme has not applied to large-scale matrices and fails to be practical in applications, so we cannot evaluate the performance of their scheme. Compared with the existing scheme [19], our scheme does not require additional data operations, and our scheme has more accuracy and efficiency and fulfills extra verification function as well.To sum up, as for the client, the client has already outsourced the most complex matrix operation to the cloud and enjoys significant cost savings by deploying our proposal, and the detailed experimental results will be presented in the next section. One can see that regarding computational complexity and communication overhead, the proposed scheme reduces the computational overhead of direct computation successfully, and it has considerably better performance than the existing research.


## 6. Experimental Evaluation

In this section, we provide a concrete experimental analysis on the performance of the proposed algorithms in a real-world scenario. Our experiments are carried out on the computer with 2.7 GHz Intel Core i5-6400 and the memory of 8 GB to simulate the client side, and another computer with an Intel i7-10700 processor running at 2.8 GHz and 16 GB memory is utilized to simulate the cloud server. We implement the proposed algorithms in Matlab.We implement our proposed algorithms on different data scale by experiment to evaluate the running time for QR and LU factorizations, respectively, and we record and provide the running time in each different situation. Besides, we assume that the time spent for interaction between the client and the cloud can be proximately neglected. Tables3 and 4 present the processing time overhead for performing QR and LU factorizations, respectively, and we set the size of the original matrix we construct randomly varies from 500 ∗ 300 to 7500 ∗ 5000, and we simulate l=20in the subalgorithm ClientVerto make a tradeoff between the efficiency and security.Table 3
Time and performance comparisons of QR outsourcing factorization.
Dimensionm×nToriginal(s)Tclient(s)Tcloud(s)Toriginal/Tclient1000∗ 100044.090.2524.10176.751500∗ 1000109.390.4068.80273.122000∗ 1000191.930.51139.63373.252000∗ 2000519.761.04324.08498.333000∗ 20001404.681.78901.72788.294000∗ 25003455.023.702531.44934.965000∗ 30009070.547.085794.171281.787500∗ 500046171.2125.4132394.061816.67Table 4
Time and performance comparisons of LU outsourcing factorization.
Dimensionm×nToriginal(s)Tclient(s)Tcloud(s)Toriginal/Tclient1500∗ 100011.770.387.2131.271500∗ 150028.020.5517.9450.892000∗ 150052.380.8533.4562.002000∗ 200083.381.0354.4580.842500∗ 2500176.101.82118.0796.853000∗ 3000308.612.79218.82110.474000∗ 4000675.526.04491.67111.915000∗ 50001495.3312.011005.73124.48To make our experiment result more concise and intuitive, we pay more attention to the whole treatment time on the client side and the execution time on the cloud server, so we use these parameters.Toriginal denotes the execution time for the client locally employing QR and LU factorizations without the assistant of the cloud. Tclient is represent for the execution time for the client to apply our proposed algorithms, including the client’s time cost of accomplishing the subalgorithms KeyGen,ClientEnc,ClientVer,ClientDecrpyt on its own. Tcloud denotes the execution time for the cloud to accomplish QR and LU factorizations. We will take the execution time as the performance metric, and we can describe the performance gain by Toriginal/Tclient; this value is utilized to measure the resources saved for the client when employing the outsourcing algorithm; generally, the larger the value is, the more computing resources can be saved. In the experiment result shown in the tables, we will focus on this performance metric.And the computation time of matrix of different dimension is demonstrated in Figure2.Figure 2
Time comparisons of QR outsourcing factorizations in the proposed algorithm.Table4 presents the processing time (in seconds) and performance gain for solving LU factorizations of different scale.And the processing time of matrix of different dimension is demonstrated in Figure3.Figure 3
Time comparisons of LU outsourcing factorizations in the proposed algorithm.We can see that the client enjoys significant cost savings by deploying our proposed scheme, and the required time of the proposed outsourcing scheme increases as the size of the input matrices increase. As can be seen from two tables above,Toriginal/Tclient which is represented for the resource advantage of the client is up to 1816.67, and it can be considered as our outsourcing scheme has significant computing savings compared to the situation performing QR and LU factorizations on its own.To validate the efficiency of our scheme sufficiently, we simulate the outsourcing schemes in prior work on our computer and compare the execution timeTclient with respect to dimension of input matrix in Tables 5 and 6.Table 5
The comparisons ofTclientin different QR outsourcing schemes.
Dimensionm×nOur scheme (s)Work [18] (s)Work [19] (s)1000∗ 10000.251.242.061500∗ 10000.402.013.932000∗ 10000.513.826.372000∗ 20001.044.298.443000∗ 20001.7812.6820.164000∗ 25003.7026.7640.585000∗ 30007.0850.1172.027500∗ 500025.41155.72210.68Table 6
The comparisons ofTclientin different LU outsourcing schemes.
Dimensionm×n(s)Our scheme (s)Work [18]1500∗ 10000.381.291500∗ 15000.551.972000∗ 15000.843.072000∗ 20001.034.382500∗ 25001.827.543000∗ 30002.7912.124000∗ 40006.0427.845000∗ 500012.0156.86As for the outsourcing of QR factorizations, the scheme in work [18] requires interactions with the cloud, and every matrix for interaction still need to be encrypted for enhanced privacy protection; it causes a lot of computational overheads on the client side undoubtedly, and the operations for the elements of matrix in work [19] are so complicated that the execution time Tclient is the longest among all the works. We can see that Tclient of our scheme is significantly less than others even though our scheme requires additional overhead of verification, compared to work [18] and work [19], and we can say that our scheme is highly efficient.The data in Tables5 and 6 validate our previous analysis. The execution time Tclient in our scheme is significantly less than others. To sum up, our scheme is the most efficient among the prior work.According to the tables and figures above, we can conclude that our proposed scheme achieves considerable savings in terms of computation and communication overhead on the client side, and the client resource advantage, i.e.,Toriginal/Tclient, improves generally related to the increasing size of the matrix as illustrated in tables and figures above, which fulfills totally the design goals for outsourcing large-scale matrix. More importantly, the experiment shows that the proposed scheme needs fewer computing resources than the prior works, and the client employs our algorithm without interaction, thereby reducing clients’ communication overhead and minimizing the risks of destroying data security and privacy during the interaction process. In summary, the experiment validates the efficiency of proposed outsourcing scheme by numerical experiments.


## 7. Conclusions

As the emergence of the big data and cloud computing era, secure outsourcing services are inevitably becoming prevalent, which allows a resource-constrained client moves the heavy computation to the cloud server which has outstanding performance. Considering that QR and LU factorizations have made noticeable contributions in many fields, but they take too much burden and overhead for the client when the dimension of the input matrix is large extremely. To this end, we propose an efficient and noninteractive outsourcing scheme of large-scale QR and LU factorizations. Specially, we take an efficient encryption method on the original data that the client transforms the original matrix by multiplying a series of particular matrices, these matrices all are sparse enough to ensure efficiency and ensure data security at the same time, this techniques can not only lessen the computational overhead of encryption and decryption stage but also deal with serious potential security menace, then the cloud performs matrix factorizations on the transformed matrix, the client just needs to send matrix and receive results, and the interactions are no longer needed, which brings benefit of reducing communication overhead. Our proposed scheme can fulfill the design goals of correctness, privacy preserving, efficiency, and verifiability, and we provide a concrete experimental result on the performance on large-scale matrices. The evaluation results show that regarding computational complexity and communication overhead, our proposed scheme has considerably better performance than the existing research studies.



---

*Source: 6184920-2021-06-18.xml*