Data confidentiality and integrity preserving outsourcing algorithm for matrix chain multiplication over malicious cloud server

Abstract

Cloud computing offers an economical, convenient and elastic pool of computing resources over the internet. It enables computationally weak client to execute large computations by outsourcing their computation load to the cloud servers. However, outsourcing of data and computation to the third-party cloud servers bring multifarious security and privacy challenges that needed to be understood and address before the development of outsourcing algorithm. In this paper, the authors propose solutions for matrix-chain multiplication (MCM) problem. Our goal is to minimize the execution burden on the client without sacrificing the confidentiality and integrity of the input/output. Conventionally, the complexity of matrix-chain multiplication is O (n³). After leveraging the facility of outsourcing, the client-side complexity reduces to O (n²). In the proposed algorithm, the client employs some efficient linear transformation schemes, which preserve the data confidentiality. It also developed a novel result verification scheme, which verifies the result with modest burden and high probability and maintain the integrity of computed result. The analytical analysis of algorithm depicted that the algorithm is simultaneously meeting the design goals of correctness, security, efficiency and verifiability. We conduct many experiments to validate the algorithm and demonstrate its practical usability. The algorithm is implemented on public cloud “Amazon EC2”, and found that the proposed outsource algorithm performs 11.655 times faster computation of matrix-chain multiplication than the direct implementation.

Keywords

Matrix-chain multiplication cloud computing secure outsourcing security verifiability

1 Introduction

The development of high performance hardware such as multicore CPUs, GPUs, large capacity storage systems, high performance caches, network interfaces and high speed internet have been the driving forces towards the development of cloud computing. It aims to provide ubiquitous, convenient, on-demand network access to a shared pool of configurable computing resources [1].

Nowadays, many clients from large enterprises to small business houses are shifting towards cloud computing rather abandoning the traditional in-house IT infrastructure. This shift has happened due to many reasons, such as huge capital saving on procurement and maintenance of IT resources, immediate on-demand availability of resources, scalability and elasticity of resources, high availability of resources and the best facility is the provision of all the services in a pay as you go manner. In fact at many places the cloud has even replaces the requirement of high-cost traditional computing infrastructure [2]. However, the lack of trust between the client and cloud is the main hurdle towards the widespread adoption of cloud computing.

The outsourcing paradigm involves two entities the client and the cloud server. The client wants to execute some complex polynomial time computation, but lacks the necessary computing resources to complete the execution. Therefore, it outsources the large computations to the cloud servers, which have the necessary capability to perform the job. But this type of arrangement is expose to security and privacy concerns. The main security concern of this arrangement arises due to the lack of trust between the client and cloud server. The cloud server might record all the computation and data that came into custody during the execution of the problem and later behave maliciously. Due to the sensitivity of data, it became extremely important to protect the privacy of data before outsourcing to the cloud. Moreover, the client also has no reliance on the computation performed by the cloud server. Eventually, the cloud also has financial advantage of executing a computation extremely fast, behave lazily (lazy computation), terminate a problem arbitrary and produces incorrect results. Consequently, releasing up the valuable computing resources for other computations to increase the financial output. That is why it has become extremely important to implement an efficient verifiable outsource computation, where the client can verify the integrity of result with minimum effort and interaction (non-interactive verifiable computation) [3].

In this paper, we attempt to provide a secure outsourcing solution for matrix-chain multiplication problem. There are two main reasons that motivate us to solve MCM problem. First, MCM is a basic operation that has application in many domains, such as statistics, computer graphics, scientific computations, machine learning, sensor networks, economics, image encryption just list a few. Second, it is a complex problem, takes O (n³) for execution. Further, if MCM work on large data set, it becomes impossible for a resource constrained client to perform execution. Therefore, outsourcing of MCM is worthwhile. Further, the problem of matrix multiplication has been the subject of much attention in [4 –8]. These solutions have considered and solve the matrix multiplication problem, but neither the solution designed to work in a cloud computing environment nor considered the computational asymmetry between the client and cloud. Moreover, in the best of our knowledge, none of the previous work has addressed the MCM for outsourcing to the cloud. Interested with the facts that MCM is an important problem and well rooted in the scientific and engineering field, authors are highly motivated to develop a privacy preserving, efficient and secure outsourcing algorithm in a fully malicious environment.

The main contribution of the article is mentioned in below points:

The goal of MCM algorithm is to securely outsource the matrix-chain and calculate the product efficiently. As the matrix multiplication is associative hence we have no restrictions on which the multiplications performed as long as multiplicative conditions are met. At the very first, by applying the algorithm discussed in [9], we found the optimal order in which the matrices should be multiplied.

The paper discusses several potential design approaches for the formulation of the privacy preserving algorithm. They differ in security and efficiency parameter, the best one is targeted and finally implemented.

A through analytical analysis is presented, which shows that the MCM algorithm is successfully meeting the algorithm design challenges.

The experimental assessment validates the algorithm for practical usability.

The rest of the sections of this paper is organized as follows: Section 2 discusses the existing work. Section 3 presents an outline, framework and design goals of secure outsourcing algorithm. Section 4, formulates the problem. Also, the proposed privacy preserving method for MCM. In Section 5, we analyse the performance of algorithm rationally and illustrate that outsourcing algorithm meeting the design goals. Section 6, presents the implementation results and experimental analysis. Finally, concluding remarks and future direction incorporated in Section 7.

2 Related work

The ease of usability, reliability and economic viability of cloud has attracted many researchers to perform investigations on efficient cloud-based architectures and proposed algorithms for outsourcing of various complex problems. We are listing few problems, which has secure outsourcing solution in cloud environment. The problems such as matrix multiplication [4–6 , 10–18], matrix inversion [19], system of linear equation [20 –22], linear regression analysis [23, 24], modular exponent [25], matrix determinant [26].

In [4], the authors has built a secure outsourcing algorithm on the theory of Shamir’s secret sharing technique. This method suffers from computational overhead since the multiplication overhead expands to polynomial time. Further, Mohassel has proposed a non-interactive and secure protocols for matrix multiplication. They has employed many encryption schemes with limited homomorphic properties and generalized the verification scheme. The efficiency of verification is destructively hampered the overall algorithm. Further, this protocol for matrix multiplication is extended for other linear algebra tasks in [5]. However, the generic protocol involves cryptographic primitive such as a FHE (fully homomorphic encryption) or SHE (somewhat homomorphic encryption) scheme that makes the protocols complicated, inefficient and far from practical usage [27]. In [3] the author has proposed a formal definition for secure outsourcing algorithm. Later they proposed a non-interactive solution for polynomial functions. The function modeled into grabbled circuit and homomorphically encrypted. Further, the server executed the function and returned the result with non-interactive proof of verification that could be verified in O (m) time.

Further, in [10, 19], authors have proposed linear transformation method for secure outsourcing of matrix multiplication and matrix inversion problem. The algorithms efficiently outsources the problems to the cloud server, while maintaining the correctness, privacy of the input-output, and verifies the result efficiently. Further a solution is develop for polynomial evaluation, which later extended to matrix multiplication outsourcing using Diffie-Hellman assumption and bilinear group. The solution preserves the input-output privacy and achieved public delegation. However, suffers from low efficiency due to extensive use cryptographic preambles, which make it impractical to use with large input size [14]. Furthermore a protocol is presented for matrix multiplication outsourcing, which preserve the secrecy by adding the blind divisors to the input, which makes the input matrix indistinguishable. Further, this method is very efficient since does not involved in any heavy cryptography. The authors claim that they achieve concrete level of security efficiency and verifiability [12].

Recently, two algorithms have been proposed in [11]. They proposed privacy preserving secure algorithm based on algebraic property of the matrices. They introduces the orthogonal and diagonal property of the matrices to propose the privacy preserving transformation operation. They also proposes verification algorithm, which detect the server misbehavior with high probability and modest overload. The author claims that the two protocols achieve the security, efficiency and verifiability. They has proved the proposal with the help of analytical and experimental analysis.

3 Problem formulation

In this section, we define the matrix-chain multiplication outsourcing problem. A system model has been proposed for the MCM problem, which gives a modular view of the problem such as privacy preserving transformation operation, computation of the problem on cloud server, verification of the output result and finally the re-transformation of the result. Description of the security challenges (threat model) faced by the proposed system. Further the design goal of the algorithm that is correctness, security, efficiency and verifiability is also discussed in this section. Finally, the framework of the algorithm is also elaborated in detail.

3.1 System model

The system model for matrix-chain multiplication algorithm is presented in Figs. 1 and 2 in two steps. Here, the client wants a solution of multiplication for a chain of matrices. But the client in the system model is resource-constrained and lack the necessary computing resources needed for computation. Therefore, the client decided to outsource the computation to cloud server. In the matrix-chain problem the client first computes the optimal order of computation to minimize the number of scalar multiplication. Later, the client follows the optimal order and outsources the matrices to the cloud server for multiplication. Further, the matrix-chain multiplication problem can be stated as follows: given a chain (M₁, M₂, …, M_n) of n matrices, where for i = 1, 2, …, n, matrix M_i has dimension p_i-1 × p_i, fully parenthesize the product M₁, M₂, …, M_n in a way that minimizes the number of scalar multiplications.

Fig.1

Computation of optimal sequence.

Fig.2

System model for matrix-chain multiplication.

First the client computes the optimal sequence of the matrices with the help of the cloud to execute the MCM in a lowest cost. Then the client applies the linear transformation operation on the first input pair φ (M_i-1, M_i) and produces the transformed problem $φ_{k} (M_{i - 1}^{'}, M_{i}^{'})$ . Then the transformed problem $φ_{k} (M_{i - 1}^{'}, M_{i}^{'})$ is outsourced to the cloud server. The server computes the result and returned the output result. The client first re-transform the result R_i and then verifies it. If it found correct, it again outsources the next pair of input until all the matrices get multiplied. In this way, the client get the result of MCM.

3.2 Algorithm framework

Gennaro et al. [3] has presented a formal definition for secure outsourcing algorithm. The outsourcing algorithm has five steps in the following order: “KeyGen”, “ProbTrans”, “Compute”, “Verify”, and “Retransform”.

KeyGen (1^λ): This algorithm invokes with an input of security parameter λ. Later generates random keys in the form of matrices, which are further used for problem transformation operation.

ProbTrans (φ, k): On the input of security key matrices k. The ProbTrans (φ, k) operation perform the encryption, the original problem φ (M_i-1, M_i, k) with the key k generates the transformed problem $φ_{k} (M_{i - 1}^{'}, M_{i}^{'})$ .

$Compute (φ_{k} (M_{i - 1}^{'}, M_{i}^{'})) :$ The server performs the computation and produces the encrypted result.

$Retransform (R_{i}^{'}, k)$ : Once the cloud server completed the execution of problem, it returns the result to client. The client with the help of keys (k) retransform the result and find R_i = φ (M_i-1, M_i).

Verify (R_i, k): Finally, the client with the help of security keys verifies the correctness of result R_i.

3.3 Threat model

We consider the proposed algorithm for public cloud server, where the algorithm is expose to many vulnerabilities i.e. the cloud server could produce incorrect results either being lazy or intentionally disrupting the algorithm. The threat model considered in this section closely follow the previous work on secure outsourcing in [10 , 22]. The cloud server might be “curious”, “lazy” and dishonest simultaneously. Therefore, the cloud server attempt to record the data and computation also, produce incorrect results. In short, such behavior of cloud server tries to completely sabotage the outsourcing algorithm.

3.4 Design goals

A secure and efficient MCM outsourcing algorithm should satisfy the following four properties such as correctness, privacy, efficiency and verifiability simultaneously. Correctness: The client and the cloud server should follow the outsourcing algorithm instructions correctly. Privacy: The MCM outsourcing algorithm should able to maintain the privacy of input and the output. Efficiency: The computation cost for (transformation, verification and re-transformation) should substantially lesser than executing the MCM problem. Verification: The verification algorithm should detect cheating and server misbehavior of the cloud server. Simultaneously, it should be efficient and not involved any expensive computation.

4 Proposed data confidentiality and integrity preserving outsourcing algorithm

This section presents a discussion on matrix-chain multiplication outsourcing problem. The discussion gives many possible solutions based on efficiency and security parameters, the best will be selected for practical implementation and result analysis.

4.1 Matrix-chain multiplication problem

The matrix-chain multiplication problem can be stated as follows: given a chain <M₁, M₂, … , M_n > of n matrices, where for i = 1, 2, …, n, matrix M_i has the dimension of p_i-1 × p_i. The product M₁, M₂, …, M_n in a way that minimizes the number of scalar multiplications. The matrix-chain is evaluated as $M_{p_{0} \times p_{1}} \times M_{p_{1} \times p_{2}} \times, \dots, \times M_{p_{n - 1 \times n}}$ (1)

The given chain multiplication given in Equation (1) is evaluated by n matrix multiplications. The operation of matrix multiplication (M_p₀×p₁ × M_p₁×p₂) may be considered as elimination of element p₁ from the set of {p₀, p₁, p₂} at the cost of p₀p₁p₂ scalar multiplication and addition, which is also referred as the cost of finding an optimal sequence for the multiplication of matrices. The client in the outsourcing algorithm with the help of cloud server first computes the optimal sequence of multiplication using the algorithm discussed in [9]. Once the client got the optimal sequence of the matrix-chain, the problem can be restated as an equivalent matrix multiplication problem. The client took a pair of matrices from the optimal sequence. And outsources them to the cloud server until all the matrices get multiplied. In this process, the client finally gets resultant matrix of order R_{p₀×p_n} by eliminating all the elements {p₁, p₂… , p_n-1 } from the set of {p₀, p₁, … , p_n }. Before outsourcing the matrices for chain multiplication, the client applies an efficient transformation operation on input data to preserve the privacy of data. The client applied the transformation operation on (M_p₀×p₁ × M_p₁×p₂). Then, the transformed problem $φ_{k} (M_{p_{0} \times p_{1}}^{'} \times M_{p_{1} \times p_{2}}^{'})$ is outsourced to the cloud server. The cloud server could not infer anything meaningful from the input. In this way, the confidentiality of data is maintained. The cloud server performed the matrix-chain multiplication and produces encrypted result $R_{p_{0} \times p_{2}}^{'}$ . The client later decrypted this result and perform verification to verify its integrity. If the result passes the verification test, then only the client accepts the result else rejects.

4.2 Transformation operation

In this section, the authors proposed the privacy preserving linear transformation operation for data confidentiality. The transformation operation transforms the data to provide the input secrecy as well as the output secrecy. For a matrix-chain multiplication problem M_p₀×p₁ × M_p₁×p₂ × , …, × M_{p
_n-1×n}. The client outsources the pair of matrices in the optimal order to the cloud server to calculate the final result. The client performs the transformation for every pair of matrices of the matrix-chain operation. Let the client is preparing the pair of matrices (M_p₀×p₁ × M_p₁×p₂) for matrix multiplication. The client performs an efficient transformation which transform the problem φ (M_p₀×p₁ × M_p₁×p₂) into $φ_{k} (M_{p_{0} \times p_{1}}^{'} \times M_{p_{1} \times p_{2}}^{'})$ .

If two matrices are compatible for multiplication, the matrix multiplication can be performed as $R_{p_{0} \times p_{2}} = M_{p_{0} \times p_{1}} \times M_{p_{1} \times p_{2}}$ (2)

The Equation (2) presents a situation for linear transformation of inputs such as $M_{p_{0} \times p_{1}}^{'} = M_{p_{0} \times p_{1}} \times A$ and $M_{p_{0} \times p_{2}}^{'} = B \times M_{p_{0} \times p_{2}}$ . If the client outsources this transformed problem to the cloud $φ_{k} (M_{p_{0} \times p_{1}}^{'} \times M_{p_{1} \times p_{2}}^{'})$ for matrix multiplication the result $R_{p_{0} \times p_{2}}^{'} = M_{p_{0} \times p_{1}} A \times {BM}_{p_{1} \times p_{2}}$ , upon comparing this result with the result R_p₀×p₂ the key matrices A and B are the additional terms. In order to retrieve the result R_p₀×p₂, a meaningful relation needed to be establish between $R_{p_{0} \times p_{2}}^{'}$ and R_p₀×p₂. If the key matrices A and B are orthogonal to each other, means B = A^T, then the Equation $R_{p_{0} \times p_{2}}^{'} = M_{p_{0} \times p_{1}} A \times {BM}_{p_{1} \times p_{2}}$ (putting the value of B), become $R_{p_{0} \times p_{2}}^{'} = M_{p_{0} \times p_{1}} \times M_{p_{1} \times p_{2}}$ i.e., $R_{p_{0} \times p_{2}}^{'} = R_{p_{0} \times p_{2}}$ . The result of transformed matrix multiplication problem is exactly equal to the original problem. This transformation operation is not fully protected, since it provides partial secrecy, the output is still expose to the cloud server. Hence, output is at risk. The malicious cloud server might copy the output result and use for some personal gain. Thus, we need some other technique, which protect the input as well as output.

(a) In the pursuit of better solution, which efficiently maintain the secrecy of input and output. The authors have reached to a conclusion that if the input matrices are multiplied by key matrices from the left-side and right-side simultaneously the input and output both become protected i.e., $M_{p_{0} \times p_{1}}^{'} = K_{1} \times M_{p_{0} \times p_{1}} \times A$ (3) $M_{p_{1} \times p_{2}}^{'} = A^{T} \times M_{p_{1} \times p_{2}} \times K_{2}$ (4)

Putting the value of $M_{p_{0} \times p_{1}}^{'}$ and $M_{p_{1} \times p_{2}}^{'}$ to Equation 2. It became $R'_{p_{0} \times p_{2}} = K_{1} \times M_{p_{0} \times p_{1}} \times A \times A^{T} \times M'_{p_{0} \times p_{1}} \times K_{2},$ where A × A^T = I, $R_{p_{0} \times p_{2}}^{'} = K_{1} \times M_{p_{0} \times p_{1}} M_{p_{1} \times p_{2}} \times K_{2}$ (5) where K₁ and K₂ are general permutation matrices that means they are readily invertible. The general permutation matrices are efficiently invertible in the order O (n) is the reason to be chosen as key matrices. Further, the client can make a relation between $R_{p_{0} \times p_{2}}^{'}$ and R_p₀×p₂. The client kept the transformation keys secret (K₁, K₂, A). It also generates $K_{1}^{- 1}$ and $K_{2}^{- 1}$ to retransform $R_{p_{0} \times p_{2}}^{'}$ into R_p₀×p₂ i.e. from the Equation (2) Substituting the values to Equation (5),

$\begin{matrix} R'_{p_{0} \times p_{2}} & = & K_{1} \times R_{p_{0} \times p_{2}} \times K_{2} \\ R_{p_{0} \times p_{2}} & = & K_{1}^{- 1} R'_{p_{0} \times p_{2}} K_{2}^{- 1} \end{matrix}$ (6)

This privacy preserving method preserves the secrecy of the input and the output result. Further, the client easily establishes a relationship between the original result and transformed result. We have shown mathematically that the retransformation operation is very efficient and the client easily transforms the transformed result to the original result.

(b) In the search of a better solution than the discussed in section (a), the quest for better solution forward towards a new direction and our research has found that if the input matrices could be transformed as, $M'_{p_{0} \times p_{1}} = D_{1} \times M_{p_{0} \times p_{1}} \times A$ (7) $M'_{p_{1} \times p_{2}} = A^{T} \times M_{p_{1} \times p_{2}} \times D_{2}$ (8)

The client will achieve better performance gain than the previous approach. The key matrices D₁ and D₂ are diagonal matrices (p₀ × p₀, p₂ × p₂), $ℝ^{p_{0}}$ and $ℝ^{p_{2}}$ , while A is an orthogonal matrix of dimension n × n in $ℝ^{n}$ respectively. The secret keys D₁ and D₂ needed only linear time complexity and also linear memory time. However, for the secret keys K₁ and K₂ memory become the bottleneck since it took additional O (n) space to the store random indices values.

Putting the Equations (7) and (8) into Equation (2), $R'_{p_{0} \times p_{2}} = D_{1} \times M_{p_{0} \times p_{1}} \times A \times A^{T} \times M_{p_{1} \times p_{2}} \times D_{2},$ where A × A^T = I, $R'_{p_{0} \times p_{2}} = D_{1} \times M_{p_{0} \times p_{1}} M_{p_{1} \times p_{2}} \times D_{2}$ (9)

It is understood from the Equations (7), (8) and (9) that this method is able to maintain the secrecy of input and the computed result. Further a relationship needed to be established, so that the client could efficiently transform the computed result of transformed input of the final results. The diagonal matrices D₁ and D₂ are invertible matrices and the client can easily compute the $D_{1}^{- 1}$ and $D_{2}^{- 1}$ in linear time.

$\begin{matrix} R'_{p_{0} \times p_{2}} = D_{1} \times R_{p_{0} \times p_{2}} \times D_{2}, \\ R_{p_{0} \times p_{2}} = D_{1}^{- 1} R'_{p_{0} \times p_{2}} D_{2}^{- 1} \end{matrix}$ (10)

It can be drawn from the Equation (10) the client could efficiently transform the result.

(c) Later we see whether we could improve the efficiency of the algorithm. It has found if we restrict the key matrices A, D₁ and D₂ as diagonal matrices the efficiency of the algorithm effectively increases. In order to perform this operation, the orthogonality property of A needed to be relaxed to some extent. The values of elements in matrix A are constrained to r or -r, where $r \in ℝ$ . Therefore, A^TA = r²I. Putting these values for transforming the input, $\begin{matrix} M'_{p_{0} \times p_{1}} & = & D_{1} \times M_{p_{0} \times p_{1}} \times A, \\ M'_{p_{1} \times p_{2}} & = & A^{T} \times M_{p_{1} \times p_{2}} \times D_{2} \\ R'_{p_{0} \times p_{2}} & = & D_{1} \times M_{p_{0} \times p_{1}} \times A \times A^{T} \\ \times M'_{p_{1} \times p_{2}} \times D_{2}, \end{matrix}$ where A × A^T = r²

$\begin{matrix} R'_{p_{0} \times p_{2}} & = & D_{1} \times M_{p_{0} \times p_{1}} \times r^{2} \times M_{p_{1} \times p_{2}} \times D_{2} \\ R'_{p_{0} \times p_{2}} & = & r^{2} (D_{1} \times M_{p_{0} \times p_{1}} M_{p_{1} \times p_{2}} \times D_{2}), \\ R'_{p_{0} \times p_{2}} & = & r^{2} (D_{1} \times R_{p_{0} \times p_{2}} \times D_{2}) \\ R_{p_{0} \times p_{2}} & = & (D_{1}^{- 1} R'_{p_{0} \times p_{2}} D_{2}^{- 1}) / r^{2} \end{matrix}$ (11)

It is understood from the Equation (11) that this method able to secure the input and output security. Moreover, this method is more efficient method than the discussed in section (a) and section (b). Thus, the client can choose a favorable option between (a), (b) and (c) based upon his requirement of security and efficiency. A detail security analysis of the algorithms discussed in (a), (b) and (c) will be discussed in the algorithm analysis section.

5 Analysis of MCM outsourcing algorithm

In this section, we prove that the proposed algorithm is meeting the design goals of correctness, security, efficiency and verifiability simultaneously.

5.1 Correctness analysis

The client will get a correct result of matrix-chain problem only if the client and cloud server follow the algorithm instructions correctly. The client follows an optimal order in which it outsources the matrix-chain to the cloud server and receive the result and once all the matrices in the chain got multiplied the client get the final result.

Theorem 1.If the client and cloud server follows the algorithm instructions then only the algorithm will produce correct resultR_p₀×p₂.

Case 1. The key matrices (A, K₁, K₂), where the key matrix A is orthogonal and K₁ and K₂ are permutation matrix.

From the Equation (6) $R_{p_{0} \times p_{2}}^{'} = K_{1} \times R_{p_{0} \times p_{2}} \times K_{2}$

$R_{p_{0} \times p_{2}} = K_{1}^{- 1} R_{p_{0} \times p_{2}}^{'} K_{2}^{- 1}$ , putting the value of $R_{p_{0} \times p_{2}}^{'}$

$R_{p_{0} \times p_{2}} = K_{1}^{- 1} K_{1} \times M_{p_{0} \times p 1} M_{p 1 \times p_{2}} \times K_{2} K_{2}^{- 1},$ where KK^-1 = I

R_p₀×p₂ = M_p₀×p₁M_p₁×p₂

Case 2. When the key matrix A is orthogonal and D₁, D₂ are diagonal matrices.

The proof of this case is similar to the case 1, since the case 2 is a special case of case 1.

Case 3. The key matrices (A, D₁, D₂), where the key matrix A is also diagonal along with D₁ and D₂.

From the Equation (11),

$R_{p_{0} \times p_{2}} = (D_{1}^{- 1} R_{p_{0} \times p_{2}}^{'} D_{2}^{- 1}) / r^{2}$ , substituting the value of $R_{p_{0} \times p_{2}}^{'},$ where A × A^T = r²

$R_{p_{0} \times p_{2}} = (D_{1}^{- 1} D_{1} \times M_{p_{0} \times p_{1}} \times A \times A^{T} \times M_{p_{0} \times p_{1}}^{'} \times D_{2} D_{2}^{- 1}) / r^{2},$ where A × A^T = r²

$R_{p_{0} \times p_{2}} = (D_{1}^{- 1} D_{1} \times M_{p_{0} \times p_{1}} \times r^{2} \times M_{p_{0} \times p_{1}}^{'} \times D_{2} D_{2}^{- 1}) / r^{2},$ where DD^-1 = I

R_p₀×p₂ = M_p₀×p₂

Here the proof in all the three cases 1, 2 and 3 revels that the proposed outsourcing algorithm is a correct implementation of MCM problem.

5.2 Security analysis

The proposed privacy preserving method is able to secure the privacy of input and the computed result. The cloud server never succeeded to recover the original information. Moreover, to justify the secrecy claim, a security analysis has been presented.

Theorem 2. The proposed matrix-chain multiplication algorithm successfully defends the privacy concerns.

Proof. The client in the matrix-chain multiplication outsources the matrix multiplication problem in optimal order and eventually after the multiplication of the matrices in matrix-chain get the final result. The client encrypts each pair of matrices before outsourcing to the cloud every time.

Case 1. When the secret key matrices (A, K₁ & K₂), where the key matrix A is orthogonal and K₁ & K₂ are monomial matrix.

The secret keys (A, D₁ & D₂) is a special case of (A, K₁ & K₂), which has similar security analysis but the permutation matrix K₁ and K₂ randomize the indices position, which performs row-wise transformation for M_p₀×p₁ and column-wise transformation for M_p₁×p₂. Therefore, adds extra security to the transformed values, and extra complexity to the security analysis with a factor of (p₀) ! and (p₂) !. Details of security analysis is discussed in case 2 and case 3 given below.

Case 2. When the secret key matrices (A . D₁ & D₂), where the key matrix A is orthogonal and D₁ & D₂ are diagonal matrix.

The orthogonal matrix A is square matrix, where its dimension is p₁ × p₁ in $ℝ^{p_{1} * p_{1}}$ , each entry in the matrix is l bit long integer. Therefore, the matrix A has some $\frac{1}{2} (p_{1}^{2} l)$ bit of information, which means there are $2^{(1 / 2 (p_{1}^{2} l))}$ possible choices for A. Similiarly, the other key matrices D₁ and D₂ are diagonal matrices while their dimensions are (p₀ × p₀), (p₂ × p₂) in $ℝ^{p_{o}}$ and $ℝ^{p_{2}}$ . Therefore, they have p₀l and p₂l bit of information. Additionally, these keys were applied simultaneously for the transformation operation that’s why there are $2^{(\frac{1}{2 (p_{1}^{2} l)} + p_{0} l + p_{2} l)}$ potential key combinations, which a very large quantity in terms of exponentials.

Case 3. When the secret key matrices (A, D₁and D₂) are diagonal matrices.

The third case keys were developed keeping in mind to improve the efficiency of the outsourcing algorithm. Therefore, this method has lower key complexity than the previous two methods, but this method is still safe. Further, the analysis of keys presented such as; the orthogonal diagonal matrix A has entries either r or -r, where the r is a random real number of l bits long. Therefore, there are 2^p₁+l possible choices of A. Later, the diagonal matrices D₁ and D₂ have 2^p₀l+p₂l possibilities as discussed in previous cases. Hence, when the keys are applied simultaneously for transformation operation the combined key combination is 2^{p₀l+p₂l+p₁+l}, which is large quantity in terms of (p₀, p₁ and p₂) and if the values problem size is large this case is sufficient to manage possible brute force attacks.

As discussed in the privacy preserving transformation section the proposed transformation methods are capable to preserve the privacy input and output. Therefore, the output produced by the cloud server does not disclose any meaningful information about the result. The security analysis of output matrix is same as the input matrix. Besides, the client generates a pair of new security keys for every new problem submission to the cloud server. Therefore, the solution is resembled to one-time-pad scheme and diminish the chances of plain-text and chosen-plain text attacks.

5.3 Verifiability

In the malicious cloud environment, the cloud may behave arbitrary. It might not follow the actual algorithm instruction, in that situation the cloud will produce wrong results. Sometimes the cloud behaves lazily and produces wrong result. Therefore, to detect any such situation the client must be able to verify the correctness of the result.

Theorem 3. The client in the verification operation detects a wrong/invalid result with an error probability of $\Pr_{k} \leq Pr (d_{i} = 0) \leq 1 / 2^{l} .$

Proof. An incorrect result is produced by the cloud server never passes the verification steps. The verification performed as,

$\begin{matrix} D & = & R_{p_{0} \times p_{2}}^{'} \times x - M_{p_{0} \times p_{1}}^{'} \times M_{p_{1} \times p_{2}}^{'} \times x \\ = & {0, 0, \dots . 0}^{T} \end{matrix}$ (12)

If the cloud produces a correct result this relation must hold true, however if fails $D \neq R_{p_{0} \times p_{2}}^{'} \times x - M_{p_{0} \times p_{1}}^{'} \times M_{p_{1} \times p_{2}}^{'} \times x$ , then their exists at least a row in D which is not equals to zero $Dx = {d_{1}, \dots \dots . ., d_{p}}^{T}$ (13)

Let the row d_i ≠ 0 $d_{i, 1} \times x_{1} + \dots + d_{i, k} \times x_{k} + \dots + d_{i, n} \times x_{n} = 0 .$

Then,

$\begin{matrix} \Rightarrow \sum_{j \neq k}^{n} d_{i, j} \times x_{j} + d_{i, k} \times x_{k} = 0 \\ \Rightarrow d_{i, k} \times x_{k} = - \sum_{j \neq k}^{n} d_{i, j} \times x_{j} \\ \Rightarrow x_{k} = \sum_{j \neq k}^{n} d_{i, j} \times x_{j} / d_{i, k} \end{matrix}$ (14)

The value x_k is chosen where k ≠ j and x_k∈ { 0, 1 }, however there is only one value that satisfies the equation (14). Therefore, one of the value between {0, 1} fails to satisfy the Equation (14). Thus, the verification algorithm verifies the result with an error probability of, ${Pr}_{k} \leq Pr (d_{i} = 0) \leq 1 / 2^{l}$ (15)

The client needed to run the verification process l times to avoid any erroneous result passes the verification test. Therefore, the client adjusts the value of l such that it could detect the wrong result with high probability and yet the verification algorithm is efficient than executing the problem itself.

5.4 Efficiency

For secure outsourcing of matrix-chain multiplication problem the client needed to perform some preprocessing and post-processing. It was considered during the design of the algorithm that the portion executed on client-side is always be lesser than the execution cloud-side. The theoretical complexity of each sub-algorithm is presented in Table 1.

Table 1
Theoretical analysis of complexities

Algorithm Primitives Complexity

KeyGen 0 (m + n + p)

ProbTrans 0 (mn + np)

Verify 0 (mp)

Retransform 0 (mp)

Matrix-Chain Order Ω (n³)

Compute 0 (mnp)

Algorithm Primitives	Complexity
KeyGen	0 (m + n + p)
ProbTrans	0 (mn + np)
Verify	0 (mp)
Retransform	0 (mp)
Matrix-Chain Order	Ω (n³)
Compute	0 (mnp)

Theorem 4.The proposed MCM algorithm is an efficient implementation of matrix-chain problem. It cost onlyO (n²) to the client.

Proof. The complexity of the transformation operation dominates the other sub-algorithms executed on the client-side such as verification and re-transformation. Here, we assume the final pair of matrices in the matrix-chain are of dimension (m × n) and (n × p) just to calculate the complexities of sub-algorithms. For the transformation operation ProbTrans (φ, k), the client performs M′_m×n = D₁ × M_m×n × A and M′_n×p = A^T × M_n×p × D₂ operation on its local system. But due to the special arrangement of key matrices i.e. (A, D₁, D₂) are diagonal, therefore multiplication cost only O (mn + np). Later the re-transformation result needed $R_{m \times p} = D_{1}^{- 1} R_{m \times p}^{'} D_{2}^{- 1} = M_{m \times n} \times M_{n \times p}$ needed O (mp). Finally, the verification operation needed to perform $D = R_{m \times p}^{'} \times x_{p} - M_{m \times n} \times M_{n \times p} \times x_{p}$ , this operation cost only O (mp), while the cloud computes the matrix-chain in O (mnp) and optimal chain computation cost Ω (n³).

5.5 Comparison with closely related work

This section presents a comparison of the proposed work to the closely related work for matrix multiplication since to the best of our knowledge, none of the available solution attempt to solve the matrix-chain outsourcing problem. Moreover, the existing solutions offer data secrecy and verifiability but they fail to adopt the cloud environment. The algorithms were predominantly written for remote servers in a semi-trusted environment. They don’t consider the computational asymmetry of cloud server and client. Moreover, these were developed using complex cryptographic primitives, which makes them unsuitable for computation in the cloud with the dataset. Recently, Lei et al. [7], and Kumar et al. [11] discusses linear transformation method to securely outsource the matrix multiplication to cloud server. These methods are very efficient, secure and they provide verification computation of the output result. The methods differ in their privacy preserving method one uses permutation matrix; however, later uses orthogonal matrices and the combinations of orthogonal diagonal matrices. However, these methods are also don’t discuss the solution for matrix-chain multiplication. Table 2 presents the comparison state-of-the-art methods for matrix multiplication outsourcing algorithm.

Table 2
Comparison of closely related secure outsourcing algorithms

Scheme Properties

Encryption Method Matrix Type Range Data Privacy Verifiable Computation Experimental Evaluation

Benjamin et al. [18] Homomorphic Encryption Square Matrices Infinite Field $ℝ$ ✓ ✓ ⊠

Atallah et al. [4] Shamir Secret Key Square Matrices Finite field $ℤ_{p}$ ✓ ✓ ⊠

Mohassel [5] GHV Encryption Square Matrices Finite field $ℤ_{p}$ ✓ ✓ ⊠

Fiore et al. [6] External Diffie-Hellman Assumption General Matrices Finite field $ℤ_{p}$ ✓ ✓ ⊠

Zhang et al. [8] Cryptographic Primitive General Matrices Finite field $ℤ_{p}$ ✓ ✓ ⊠

Lei et al. [10] Permutation General Matrices Infinite Field $ℝ$ ✓ ✓ ✓

Kumar et al. [11] Linear Transformation General Matrices Infinite Field $ℝ$ ✓ ✓ ✓

This Work Multiple Linear Transformation General Matrices Infinite Field $ℝ$ ✓ ✓ ✓

Scheme	Properties
Benjamin et al. [18]	Homomorphic Encryption	Square Matrices	Infinite Field $ℝ$	✓	✓	⊠
Atallah et al. [4]	Shamir Secret Key	Square Matrices	Finite field $ℤ_{p}$	✓	✓	⊠
Mohassel [5]	GHV Encryption	Square Matrices	Finite field $ℤ_{p}$	✓	✓	⊠
Fiore et al. [6]	External Diffie-Hellman Assumption	General Matrices	Finite field $ℤ_{p}$	✓	✓	⊠
Zhang et al. [8]	Cryptographic Primitive	General Matrices	Finite field $ℤ_{p}$	✓	✓	⊠
Lei et al. [10]	Permutation	General Matrices	Infinite Field $ℝ$	✓	✓	✓
Kumar et al. [11]	Linear Transformation	General Matrices	Infinite Field $ℝ$	✓	✓	✓
This Work	Multiple Linear Transformation	General Matrices	Infinite Field $ℝ$	✓	✓	✓

6 Experimental analysis

In this section, the experimental evaluation of proposed algorithm has been performed, where we outsources the matrix-chain multiplication to the cloud server. The algorithm is implemented into two parts as client-side and cloud server-side system. The client system is implemented on a laptop with AMD Processor dual core 2.2 GHz and 4 GB of RAM, 500 GB Hard disk at 5400 RPM. The server is implemented on Amazon EC2 instance hired from Amazon AWS.

The performance analysis focuses on the execution times of the sub-algorithms, while the communication time could be neglected, due to its negligible value in comparison to the execution time. The matrix-chain multiplication results are computed and the performance analysis of algorithm mainly focuses on the values of client-side computation time and cloud-side computation time while the communication time could be neglected. Further, the performance of the proposed algorithm is evaluated on the basis of three standard parameters, i.e. “performance gain”, “efficiency” and “relative extra cost”, which are used in many state-of-the-art implementations.

The “performance gain” is defined as, $PG = t_{original} / t_{client}$ (16)

Ideally, the value of PG > 1. Further, the efficiency parameter is defined as, $η = t_{original} / t_{cloud}$ (17)

The relative extra cost REC parameter is defined as, $REC = t_{client} + t_{cloud} - t_{original} / t_{original}$ (18)

To perform the experiments many random instances of matrix-chain are generated [28]. They solved directly and their execution times are denoted as t_original in the Tables 3–5. After that, the client with the help of cloud server calculate the optimal sequence of each randomly generated matrix-chains and noted the execution time for optimal sequence as t_os. Further, the client performs the privacy preserving transformation on the pair of matrices and outsources the problem to the cloud server. The cloud server executed the matrix-multiplication and returned the result, the process gets repeated until all the matrices in the matrix-chain got multiplied. Meanwhile, we record the execution time of all the sub-algorithms executed on the client-side (transformation t_enc, re-transformation t_dec and verification t_ver) and cloud-side (optimal sequence t_os, matrix multiplication t_mm). After recording all the parameters, we calculate the averages of values to get a stable system performance. The experiments started with a small problem of five matrices, which extended up to the chain of twenty matrices. The detailed results are summarized in the Tables 3–5 for matrix-chain of five, ten and twenty respectively. It could be observed from the results reported in Tables 3–5 as the size of the problem increases, the proposed algorithm took much lesser execution time than the direct method. For example, the largest problem in the experiment of five matrices takes 35.664 seconds, whereas when the problem outsources to the cloud server. It takes only 4.0146 seconds. Therefore, the client in the algorithm achieves the time saving of 88% for the matrix-chain of five matrices. Similarly, for the chain of ten matrices it achieves 90% time saving, while 91% time saving for matrix-chain of twenty matrices. Next, the performance-gain parameter for the experiments. The tables show that the client got the maximum performance gain of 8.8, 10.2, and 11.65 times, when the client outsources the problem to the cloud server. Figure 3, shows that as the problem size increases the client achieves more performance gain. It is a motivating factor for a resource-constrained client to choose “outsourcing” as their primary way problem execution, since for the larger problem the client got performance gain in double digit. Next the efficiency of the outsourcing algorithm, which could be perceived from the Tables 3–5, which is close to one, which means that the matrix-chain problem even after encryption do not take more time for matrix multiplication than the direct algorithm, which means the proposed encryption method don’t complicate the problem execution. Further, the relative extra cost “the additional burden of outsourcing algorithm over the direct implementation of algorithm”. Figure 4, shows that the REC parameter is monotonically decreasing function as the size of the problem increases. The Tables 3–5 and Fig. 4 shows that the values of REC parameter for the largest problem in the experiment is 0.090177, 0.090677 and 0.072602. The smaller values of REC parameter are a revelation that the extra work done by the client and cloud server by employing the proposed outsourcing algorithm for matrix-chain multiplication is very minimum. Further, we could see in the Figs. 5–7, the work done by the client (pre & post-processing) for outsourcing the matrix-chain problem is very minimum, in comparison to the work done by cloud server.

Table 3

Performance analysis for matrix-chain of five matrices at public cloud

t_org	t_cloud		t_client			PG	η	REC
	t_os	t_mm	t_enc	t_dec	t_ver
0.8868	0.00047	0.8125	0.4536	0.0197	0.0154	1.8146	1.0908	0.4678
2.1482	0.00051	2.0124	0.7615	0.0562	0.0315	2.5296	1.0672	0.3323
8.287	0.00048	8.2719	1.2788	0.4567	0.2242	4.2287	1.0017	0.2347
18.434	0.00052	18.854	1.5233	0.6818	0.564	6.6570	0.9776	0.1730
35.664	0.00049	35.865	2.2986	0.968	0.748	8.8835	0.9943	0.1182

Table 4

Performance analysis for matrix-chain of ten matrices at public cloud

t_org	t_cloud		t_client			PG	η	REC
	t_os	t_mm	t_enc	t_dec	t_ver
1.9229	0.00092	2.0191	0.4511	0.0422	0.0458	3.5668	0.9519	0.3308
5.0136	0.00093	5.1752	0.8719	0.1278	0.0966	4.5732	0.9686	0.2510
14.9725	0.00091	15.2589	1.45488	0.6502	0.5177	5.7086	0.9811	0.1943
29.1166	0.00099	29.2391	1.9047	0.9677	0.8433	7.8361	0.9957	0.1318
51.8253	0.00088	51.4521	2.7785	1.2508	1.0424	10.218	1.0072	0.0906

Table 5

Performance analysis for matrix-chain of twenty matrices at public cloud

t_org	t_cloud		t_client			PG	η	REC
	t_os	t_mm	t_enc	t_dec	t_ver
3.8971	0.0048	3.819	0.8195	0.0639	0.0537	4.158	1.0191	0.2216
7.6782	0.0051	7.5911	0.9736	0.182	0.194	5.6892	1.0107	0.1650
25.693	0.0049	25.578	1.8504	0.9426	0.862	7.0297	1.0043	0.1379
38.338	0.0050	38.362	2.2112	1.0326	0.9071	9.2362	0.9992	0.1090
73.158	0.0047	72.189	3.6311	1.511	1.1345	11.655	1.0133	0.0726

Fig.3

Performance Gain.

Fig.4

Relative Extra Cost for the proposed algorithm.

Fig.5

Comparison of execution time between cloud and client for five matrices.

Fig.6

Comparison of execution time between cloud and client for ten matrices.

Fig.7

Comparison of execution time between cloud and client for twenty matrices.

The client performs approximately 12%, 10%, 9% work for matrix-chain multiplication of five, ten and twenty matrices respectively as compared to cloud server. Further, for a resource-constrained client memory is another bottleneck, but due to the special arrangement of security keys the algorithm required only sub-quadratic time complexity of I/O operations in the size of the input. Therefore, the propose algorithm provide ample opportunity for clients, even with limited computing resources perform large complex computation.

Finally, the values of performance gain, efficiency and REC parameter motivates many clients to outsource their large computations to cloud server and complete their work without the need of much IT resources. Further, it is important to mention that the performance of the algorithm depends on the underlying platform. However, if the client considers the large problem, it always achieves performance gain due the asymptotic time complexity gap between the client-side execution and cloud-side execution.

7 Conclusion

In this paper, we formulated and implemented matrix-chain multiplication outsourcing algorithm. The algorithm has been developed by applying the concepts of linear algebra. The privacy of input and output pair has been preserved by the linear transformation operation. Three different proposals are discussed with various key combinations that provide an opportunity for the client to choose the best combination as per their requirement on the basis of efficiency and security. A theoretical analysis is presented, which shows that the proposed implementation of matrix-chain multiplication took quadratic time to execute on the client-side, while the complex part that takes cubic times executed on the cloud-side. In this way, the client got the performance gain of O (n). A detailed experimental and analytical analysis has presented, where the client got time saving of 88%, 90%, 91% for the outsourcing of matrix-chain multiplication of five, ten and twenty matrices respectively. The client got the maximum performance gain of 11.655 times. Moreover, if someone choose a bigger problem the value of performance gain will further increase. The algorithm is able to meet the design goals of correctness, security, efficiency and verifiability, well demonstrated in the analytical analysis. In future, it would be remarkable to see novel algorithms, which extend the verification to public verifiability where any worker can verify the correctness of the result, which subsequently reduce the verification time and increases the overall algorithm.

References

Mell

and Grance

, The NIST definition of cloud computing recommendations of the national institute of standards and technology, Natl Inst Stand Technol Inf Technol Lab145 (2011), 7.

Shiraz

, Gani

, Khokhar

R. H.

and Buyya

, A review on distributed application processing frameworks in smart mobile devices for mobile cloud computing, IEEE Commun Surv Tutorials15(3) (2013), 1294–1313.

Gennaro

, Gentry

and Parno

, Non-interactive verifiable computing: Outsourcing computation to untrusted workers, Lect Notes Comput Sci (including Subser Lect Notes Artif Intell Lect Notes Bioinformatics) LNCS6223 (2010), 465–482.

Atallah

M.J.

and Frikken

K.B.

, Securely outsourcing linear algebra computations, Proc 5th ACM Symp Information, Comput Commun Secur - ASIACCS10 (2010), 48.

Mohassel

, Efficient and secure delegation of linear algebra, IACR Cryptol ePrint Arch (2011), 1–33.

Fiore

and Gennaro

, Publicly verifiable delegation of large polynomials and matrix computations, with applications, Eprint Iacr Org (2012), 1–25.

Atallah

M.J.

, Frikken

K.B.

and Wang

, Private outsourcing of matrix multiplication over closed semi-rings., in SECRYPT (2012), 136–144.

Zhang

and Blanton

, Efficient secure and verifiable outsourcing of matrix multiplications, Springer International Conference on Information Security (2014), 158–178.

Godbole

S. S.

, On efficient computation of matrix chain products, IEEE Trans ComputC-22(9) (1973), 864–866.

10.

Lei

, Liao

, Huang

and Heriniaina

, Achieving security, robust cheating resistance, and high-efficiency for outsourcing large matrix multiplication computation to a malicious cloud, Inf Sci (Ny)280 (2014), 205–217.

11.

Kumar

, Meena

and Vardhan

, Privacy preserving, verifiable and efficient outsourcing algorithm for matrix multiplication to a malicious cloud server, Cogent Eng4(1) (2017), 1–20.

12.

Zhang

, Li

, Jia

, Dai

and Zhao

, Efficient secure outsourcing computation of matrix multiplication in cloud computing, 2016 IEEE Glob Commun Conf GLOBECOM (2016), pp. 1–6.

13.

Kumar

, Algorithm-based secure outsourcing of matrix computations, Master, Thesis, 2013, Inria, Grenoble, France, 1–43.

14.

Chen

and Zhu

Y.-Q.

, Publicly verifiable delegation of matrix operation, 2015 Int Conf Cloud Comput Big Data (2015), 377–384.

15.

, Zhang

, Luan

T.H.

, Ren

, Dai

and Zhou

, Enabling efficient publicly verifiable outsourcing computation for matrix multiplication, 25th Int Telecommun Networks Appl Conf ITNAC 2015 (2015), 44–50.

16.

Jia

, Li

, Liu

and Yu

, Enabling efficient and secure outsourcing of large matrix multiplications, 2015 IEEE Glob Commun Conf GLOBECOM 2015 (2016), 1–6.

17.

Khan

K. M.

and Shaheen

, Secure cloud services: Matrix multiplication revisited, 2014 Cloud Networking (CloudNet) IEEE 3rd International Conference (2014), 272–274.

18.

Benjamin

and J.

, Atallah, Private and cheating-free outsourcing of algebraic computations, 2008 Sixth Annu Conf Privacy Secur Trust (2008), 240–245.

19.

Lei

, Liao

, Huang

, Li

and Hu

, Outsourcing large matrix inversion computation to a public cloud, IEEE Trans Cloud Comput1(1) (2013), 1–1.

20.

Wang

, Ren

, Wang

and Wang

, Harnessing the cloud for securely outsourcing large-scale systems of linear equations, IEEE Trans Parallel Distrib Syst24(6) (2013), 1172–1181.

21.

Chen

, Xiang

and Yang

, Privacy-preserving and verifiable protocols for scientific computation outsourcing to the cloud, J Parallel Distrib Comput74(3) (2014), 2141–2151.

22.

Chen

, Huang

, Li

, Ma

, Lou

and S.

, Wong, New algorithms for secure outsourcing of large-scale systems of linear equations, IEEE transactions on information forensics and security10(1) (2015), 69–78.

23.

Chen

, Xiang

, Lei

and Chen

, Highly efficient linear regression outsourcing to a cloud, IEEE transactions on cloud computing2(4) (2014), 499–508.

24.

Kumar

, Meena

and Vardhan

, Privacy preserving, verifiable and efficient outsourcing algorithm for regression analysis to a malicious cloud server, J Intell Fuzzy Syst4(1) (2017), 3413–3427.

25.

Chen

, Li

, Ma

, Tang

and Lou

, New algorithms for secure outsourcing of modular exponentiations, Tpds25(9) (2014), 2386–2396.

26.

Lei

, Liao

, Huang

and Li

, Cloud computing service: The case of large matrix determinant computation, IEEE Transactions on Services Computing8(5) (2015), 688–700.

27.

Gentry

, Computing arbitrary functions of encrypted data, Commun ACM53(3) (2010), 97.

28.

Kumar

and Vardhan

, Random instances of matrix chain. https://sites.google.com/site/malaynitr/

Scheme	Properties
	Encryption Method	Matrix Type	Range	Data Privacy	Verifiable Computation	Experimental Evaluation
Benjamin et al. [18]	Homomorphic Encryption	Square Matrices	Infinite Field $ℝ$	✓	✓	⊠
Atallah et al. [4]	Shamir Secret Key	Square Matrices	Finite field $ℤ_{p}$	✓	✓	⊠
Mohassel [5]	GHV Encryption	Square Matrices	Finite field $ℤ_{p}$	✓	✓	⊠
Fiore et al. [6]	External Diffie-Hellman Assumption	General Matrices	Finite field $ℤ_{p}$	✓	✓	⊠
Zhang et al. [8]	Cryptographic Primitive	General Matrices	Finite field $ℤ_{p}$	✓	✓	⊠
Lei et al. [10]	Permutation	General Matrices	Infinite Field $ℝ$	✓	✓	✓
Kumar et al. [11]	Linear Transformation	General Matrices	Infinite Field $ℝ$	✓	✓	✓
This Work	Multiple Linear Transformation	General Matrices	Infinite Field $ℝ$	✓	✓	✓

Data confidentiality and integrity preserving outsourcing algorithm for matrix chain multiplication over malicious cloud server

Abstract

Keywords

1 Introduction

2 Related work

3 Problem formulation

3.1 System model

3.3 Threat model

3.4 Design goals

4 Proposed data confidentiality and integrity preserving outsourcing algorithm

4.1 Matrix-chain multiplication problem

5.1 Correctness analysis

5.2 Security analysis

5.3 Verifiability

Table 1 Theoretical analysis of complexities Algorithm Primitives Complexity KeyGen 0 (m + n + p) ProbTrans 0 (mn + np) Verify 0 (mp) Retransform 0 (mp) Matrix-Chain Order Ω (n3) Compute 0 (mnp)

References

Table 1
Theoretical analysis of complexities

Algorithm Primitives Complexity

KeyGen 0 (m + n + p)

ProbTrans 0 (mn + np)

Verify 0 (mp)

Retransform 0 (mp)

Matrix-Chain Order Ω (n³)

Compute 0 (mnp)