Efficient Noninteractive Outsourcing of Large-Scale QR and LU Factorizations

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.'e 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. 'e 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. 'e 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.


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. is 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. erefore, a potential way to deal with the dilemma is to seek help from advanced computing facilities with great computational power. is 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. Lowerupper (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 of O(m 2 n) 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. e 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 from O(m 2 n) to O(max m 2 , 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) e 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) e 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) e 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. e structure of this paper is arranged as follows. Section 3presents 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.

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. ese 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 O(m 2 ) computational complexity to generate a random orthogonal matrix and takes O(m 3 ) 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 O(m 2 n) 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.

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

Householder-Based QR Factorization.
e well-known QR factorization of a matrix will decompose matrix A 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 where Q is the (m × n) orthogonal (Q T Q � 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 where P i is an orthogonal and symmetric matrix called the Householder transformation matrix, and it is obtained by the following formula: where v is a column vector and I is the identity matrix of order size (v i ), note that v 1 is the first column vector of original matrix A, we can get P 1 by substituting v 1 into equation (3), and then multiply P 1 by A, and v 2 is the second column vector of new matrix P 1 A, we can get P 2 by substituting v 2 into equation (3), v 2 is the third column vector of new matrix P 2 P 1 A, following the same process, v i is the ith column vector of the corresponding matrix, P i can be obtained by substituting v i into equation (3), and continue this process until it reaches P m . And the matrix Qis not given explicitly as Since P i is an orthogonal matrix, we can derive Q as

Gauss Elimination-Based LU Factorization.
e wellknown LU factorization refers to decompose a matrix Binto 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 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]:

Security and Communication Networks
where M i is obtained by the following formula: Note that is the ith element of the first column of matrix B, and I is the identity matrix of order size (Π i e i ); let e 1 � (1, 0, . . . , 0), and we can get M 1 by substituting Π 1 and e 1 into equation (8). After getting a new matrix by multiplying M 1 by B, then we use ith element of the second column of matrix M 1 B to calculate Π 2 � (0, 0, π 2 3 , . . . , π 2 m ) T ; let e 2 � (0, 1, · · · , 0), and M 2 can be obtained by substituting Π 2 and e 2 into equation (8). Following the same process, once the last Gauss transformations M m−1 are reached. Finally, we can get Ufrom equation (7) and the matrix Lis computed by where

System
Model. e architecture of our proposed efficient and noninteractive outsourcing of the large-scale QR and LU factorization algorithm is illustrated in Figure 1, 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. e 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. ere is no extra interaction between two entities in our proposed algorithm. e implementation of our proposed algorithm consists of five subalgorithms. e 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) ClientEnc(A, K) ⟶ A′: with the input of an original matrix A ∈ R m×n , this algorithm is executed by the client to output the encrypted matrix A ′ ∈ R m×n , and the data are encrypted by the secret key K.
receiving the computation task Fand the corresponding matrix A ′ , this algorithm is executed by the cloud to complete the task F and output the result Q ′ ∈ R m×m and R ′ ∈ R m×n , which are two factor matrices of A ′ .
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 ⊥.
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.

reat 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.

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,

Encryption
Secret key Secret key The cloud server 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 adversary A, there exists a negligible function nelg(λ), and the A's advantage in winning the experiment is where λ is an initial parameter, Adv Exp A � |Pr(x � x ′ ) − 1/2|, and the experiment we will proceed further which is explained in Algorithm 1.

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 key Kwhich 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.

Efficient Noninteractive Outsourcing of Large-Scale QR Factorizations. Given a valid large-scale input matrix
A ∈ R m×n , the client wants to accomplish the QR factorizations with the assistance of the cloud server, and QR factorization will decompose matrix A ∈ R m×n into a product of an orthogonal matrix Q ∈ R m×m and an upper triangular matrix R ∈ R m×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 key Kand generate an orthogonal matrix O ∈ R m×m and an upper triangular matrix S ∈ R n×n .
Specifically, for perturbing all elements in original matrix A ∈ R m×n in an effective way, we take the novel transform based on Givens matrix [23], and the orthogonal matrix O ∈ R m×m is composed of kGivens matrices as where G i 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), and (j, j) positions of the identity matrix I ∈ R m×m with some certain random parameters cos θ, − sin θ, sin θ, and cos θ respectively. And the structure of G i can be expressed as e detailed generation of O is presented in Algorithm 2 as follows: Since every G i 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 matrix S ∈ R n×n . e 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 Security and Communication Networks 5 Concretely, the structure of C i is as follows: where C i is an elementary matrix, and the detailed generation of S is shown in Algorithm 3; we can see that the all nondiagonal elements of C i are zero except c i , and the row index of the element c i is bigger than the column index of c i ; note that the element c i is randomly picked within the interval (−2 q , 2 q ). erefore, c i is a random variable with its probability density function defined as In conclusion, the ClientEnc 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.

Clou dC om.
Once the client gets the ciphertext matrix A ′ ∈ R m×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 ′ ∈ R m×m and R ′ ∈ R m×n , i.e., and then the cloud returns Q ′ , R ′ to the client.

ClientVer.
is algorithm is always utilized to verify whether the cloud server follows the specification and executes the computation faithfully. After receiving the results including Q ′ , 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 ⊥.
(1) A client C generates a random matrix A 0 and a key K with the security parameter λ (2) An adversary A output (i, j) and two different values a 0 , a 1 (3) C picks x← 0, 1 { } randomly, replaces the (i, j) element of A 0 with a x to get A, and calculates the masked task ClientEnc(A, K) (4) A predicts x′←A ClientEnc(A,·) (a 0 , a 1 , i, j, A′) with the access to the oracle ClientEnc(A, ·) (5) Return 1 if x′ � 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. With a certain constant l, for i � 1 to l, the client generates two column vectors r i ∈ 0, 1 { } n randomly and r i ′ ∈ 0, 1 { } m and then computes e i � Q ′ × (R ′ × r i ) − A ′ × r i and e i ′ � (Q ′ ) T × (Q ′ × r i ′ ) − I × r i ′ , 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 e i and e i ′ both equal to 0, it means that the result is correct, and the algorithm outputs Q ′ , R ′ . Else, the algorithm returns ⊥.

ClientDecrpyt.
Once the client affirms that the encrypted QR decomposition result has passed the verification, it will commence this algorithm to decrypt the Q ′ , 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: e inversion of Ocan be computed easily due to the properties of orthogonal matrix, and it means O − 1 � O T . When it comes to the matrix S − 1 , we can express as S − 1 � C −1 n · · · C −1 2 C −1 1 , and these sparse matrices all are elementary matrix, so the inversion of these matrices is very convenient to get, as C −1 i �

Efficient Noninteractive Outsourcing of Large-Scale LU
Factorizations. Similarly, as for the outsourcing algorithm designed for LU factorization, the encryption method for matrix B ∈ R m×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.

KeyGen.
is algorithm is executed by the client to generate two permutation matrices K ∈ R m×m and V ∈ R n×n . e lower triangular matrix K ∈ R m×m can be formed of a series of random elementary matrices as where the structure of K i is as follows: We can know that every K i 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 k i is randomly selected from the interval (−2 q , 2 q ), and therefore, k i is also a random variable Input: size n Output: S (1) Set S to be an identity matrix (2) for i � 1: n do (3) set C i to be an identity matrix (4) set c i to be a random real number within (−2 q , 2 q ) 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 α i th and the β i th column in matrix C i to be c i (8) set S � S × C i (9) end for ALGORITHM 3: Generation of elementary perturbation matrix S. Input: size m Output: K (1) Set K to be an identity matrix (2) for i � 1: m do (3) set K i to be an identity matrix (4) set k i to be a random real number within (−2 q , 2 q ) 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 α i th and the β i th column in matrix K i to be k i (8) set K � K × K i (9) end for ALGORITHM 4: Generation of elementary perturbation matrix K.
Security and Communication Networks and the probability density function of k i satisfies the following equation: Similarly, we can generate an upper triangular matrix V ∈ R n×n as where every V i 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. e client permutates the original matrices through multiplying the secret matrices K ∈ R m×m and V ∈ R n×n , and then the client can obtain ciphertext matrix B ′ ∈ R m×n after the conversion as

CloudCom.
Once the client completes the encryption algorithm and gets matrix B ′ ∈ R m×n , the client will turn to the cloud. en, 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 ′ ∈ R m×m and U ′ ∈ R m×n , i.e., and then the cloud returns L ′ , U ′ to the client.

ClientVer.
After getting the L ′ , 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 ⊥. en, input a certain constant l, and for i � 1 to l, the client generates a random column vector r i ∈ 0, 1 { } n and then computes e i � L ′ × (U ′ × r i ) − B ′ × r i ; in detail, this equal is used to determine whether L ′ × U ′ is equal to B ′ . If the result of e i equals to 0, it means that the result is correct, and the algorithm outputs L ′ , U ′ . Else, the algorithm returns ⊥.

ClientDecrpyt.
Once the client ensures that the encrypted LU decomposition result is correct, it will conduct this algorithm to decrypt the L ′ , 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:

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

Theorem 1. For any valid large-scale input matrix
A ∈ R m×n , B ∈ R m×n , our proposed outsourcing algorithms are correct exactly.
Proof. If the cloud server performs the task correctly, we can get Q ′ and R ′ which satisfy 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 matrix Afrom A ′ is negli- 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 � G 1 G 2 G 3 · · · G k and S � C 1 C 2 C 3 · · · C n ; we can know each G i processes two rows of Aand each S i processes one column of A. We assume that e elements in ith row and the kth row of matrix A 0 can be described as follows, which is concealed by arbitrary parameters cos θ, sin θ, where θ ∈ (0, π), a 0 ij � cos θa ij − sin θa kj , a 0 kj � sin θa ij + cos θa kj .
By the next encryption step, the elements of A ′ are easy to deduce that As we mentioned before, these parameters cos θ, sin θ, c i are chosen by the client randomly and all are blind to adversary A, in order to recover a ij , the adversary needs to access cos θ, sin θ, c i and a kj 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 a ij from a ij ′ , in terms of the ClientDecrpyt algorithm, the client generates encryption matrices by O � G 1 G 2 G 3 · · · G k and S � C 1 C 2 C 3 · · · C n , due to all θ in G i , i ∈ [1, k] satisfy the uniform distribution of (0, π), the random parameter c i in Sis selected from the interval (−2 q , 2 q ) randomly, the total probability that an adversary can recover a ij form a ij ′ is the product of the probability of recovering θ and c i and also need to get the position of another element a kj , so the success probability of an adversary is 1/(∞ × ∞)by launching a brute-force attack to obtain the two sets θ 1 , θ 2 , . . . , θ k and c 1 , c 2 , . . . , c n , and it is small enough that an adversary can recover a ij is definitely impossible. Now, we consider the input privacy of B ′ ; 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 � K 1 K 2 K 3 · · · K m and V � V 1 V 2 V 3 · · · V n ; we can know that each K i processes one row of Band each V i 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 e elements in ith row and the jth row of matrix B 0 can be described as follows, which is concealed by arbitrary parameters k i , where By the next encryption step, the elements of B ′ are easy to deduce that Because these parameters k i , v i are chosen by the client randomly and all are blind to adversary A, and the random parameters k i , v i in K and V are selected from the interval (−2 q , 2 q )randomly, the total probability that an adversary can recover b ij form b ij ′ is the product of the probability of recovering k i and v i and also need to get the position of another element b i′j , so the success probability of an adversary is 1/(∞ × ∞)by launching a brute-force attack to obtain the two sets k 1 , k 2 , . . . , k m and v 1 , v 2 , . . . , v n , and it is small enough that an adversary can recover b ij is definitely impossible.
If there is no oracle ClientEnc, 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 a 0 , a 1 , and x ← 0, 1 { }is 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 the Kto answer at least one of A's queries. Because Kwill be randomly chosen for each query, the probability is Pr[case 1] ≤ negl(λ).
us, adversary A can tell and get x ′ � xcorrectly. Case2: the oracle never chooses the K 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(λ). e probability of successful prediction can be deduced as follows: 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 matrix A, B from A ′ , B ′ . us, we can draw the conclusion that the input privacy is well protected. □ 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.

Theorem 4. For any valid large-scale matrix A ∈ R m×n , our proposed algorithm is verifiable exactly with a probability of approximated to 1.
Proof.
e vectors e i , e i ′ are generated in our concrete method of verification. However, e i ′ is used to analyse whether Q is an orthogonal matrix as we need. So, we simply consider the scenario where the equality 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 e i ≠ 0, it means that there will be at least one nonzero element in e (i) 1 , e (i) 2 , . . . , e (i) n T , and we assume that the nonzero element locates in kth row, 1 ≤ k ≤ n, i.e., e (i) k � 0. We can obtain Because the above process will be conducted ltimes independently, so e same procedure may be easily adapted to obtain 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. 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 O(2m 2 n + m 3 ). Now, we analyse the time cost in our outsourcing algorithms executed by the client thoroughly.
In the KeyGen 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 O(m + n).
In the ClientEnc subalgorithm, client performs the lowcomplexity matrix transformation to encrypt e matrix multiplication between two dense matrices can be avoided due to O and Sare two sparse matrices. e complexity of ClientEnc(A, K) ⟶ A ′ is no more than O(mn).
In the CloudCom subalgorithm, the cloud completes QR factorization on ciphertext matrix A ′ which takes computations with O(2m 2 n + m 3 )complexity.
In the ClientVer subalgorithm, client needs to calculate vector-matrix multiplication instead of calculate matrixmatrix 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 O(m 2 + mn).
In the ClientDecrpyt 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 O(m 2 + mn).
e 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 of O(max m 2 , mn ), which is less than the computational complexity of O(m 2 n) of conducting QR or LU factorization, so it is fully in line with the design goals of efficiency.

Efficiency Comparisons.
In this section, we further compare our scheme with those of the most related schemes mentioned in Section 2. We demonstrate the concrete analysis in Tables 1 and 2. ese 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.
When 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 the ClientVer 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 O(m 2 n) to O(max m 2 , 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.

Experimental Evaluation
In this section, we provide a concrete experimental analysis on the performance of the proposed algorithms in a realworld 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. Tables 3 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.
To 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. T original denotes the execution time for the client locally employing QR and LU factorizations without the assistant of the cloud. T client 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. T cloud 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 T original /T client ; 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 Figure 2. Table 4 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 Figure 3.
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, T original /T client 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 time T client with respect to dimension of input matrix in Tables 5 and 6.
As 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 T client is the longest among all the works. We can see that T client 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. e data in Tables 5 and 6 validate our previous analysis. e execution time T client 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., T original /T client , 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.

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. e evaluation results show that regarding computational complexity and communication overhead, our proposed scheme has considerably better performance than the existing research studies.

Data Availability
No data were used to support the findings of this study.

Conflicts of Interest
e authors declare that there are no conflicts of interest regarding the publication of this paper.