Secure and efficient publicly verifiable outsourcing of matrix multiplication in online mode

Abstract

With the emergence of cloud computing paradigm in many scientific applications, outsourcing of computation has attracted a great amount of attention from the research community. Outsourcing of heavy computations such as multiplication of two large matrices has raised some security concerns. Data and the result of computation should be protected not only from attackers, but also from the cloud servers. Moreover, data owner should be able to verify the correctness of computation with complexity less than the original computation. The previous schemes either have expensive offline phase or do not support public verifiability. In this paper, first we find a security vulnerability in the Zhang-Lei’s scheme for outsourcing of matrix multiplication where the cloud server can forge the result and pass the verification phase. Then, we present a secure and efficient publicly verifiable outsourcing of matrix multiplication scheme which achieves privacy protection of outsourced data and result, unforgeability of result, public verifiability and high efficiency. Our analyses show that compared with the related work, the proposed scheme is superior in terms of functionality, computation, communication and storage overhead, especially in verification computation overhead.

1 Introduction

With the explosive growth of data volume and computing scales in recent years, now many users and corporations are unable to afford their heavy storage and computing equipment with the same rate. Fortunately, cloud technology with its extensive storage and processing capacity offers an attractive solution.

Based on a pay-per-use model, a client with limited computational power can easily outsource large-scale computational tasks to a cloud server [31]. However, when the data to be outsourced is valuable and private, this solution is not so straightforward. The untrusted cloud may misuse or sell the data. Not only must the outsourced data be kept secret from the cloud but the result of computation over this private data also must be blind to the cloud. Therefore, the data owner (or client) and the cloud server need a security protocol that (1) protects the data not only against outsider eavesdroppers but also against the cloud, (2) allows the cloud to perform computation over this blinded data without finding the final result of its computation, (3) allows the data owner to efficiently discover the final result from the blinded result the cloud has computed, and (4) makes the data owner sure about the correctness of the final result. The latter requirement is known as verifiability. Verification of the result may be performed by the data owner itself or by any public verifier. The public verifier must not learn neither the original data nor the final result. In this paper, we focus on the secure outsourcing of multiplication of two large matrices of private entries. Our proposed protocol provides public verifiability.

1.1 Motivation

Matrix multiplication is a basic computational operation in many scientific and engineering fields and has numerous applications including computer graphics, image compression, image transformation and so on [15, 17]. A client with limited computational resources might be unable to tolerate huge overhead of multiplying large matrices. Therefore, it prefers to outsource matrix multiplication and verification of the results. On the other hand, the client wants to protect privacy of its sensitive data. In many cases, the client is unwilling to share the data with others, including the cloud server [31]. Also, we require that the total running time for the client, including blinding (or encrypting) the matrices, unblinding (or decrypting) the blinded result and verifying the correctness of the result, must be less than the time of the original computation. If not, the client would perform the computation on its own rather than outsource the computation [22].

The existing work mainly suffer from the massive overheads [3, 8, 10, 24]. In many previous schemes the client has to declare the matrices that he may require their multiplication in the future. In these schemes, the client declares two groups $M_A$ and $M_B$ of matrices, each identified with a unique ID, to the cloud server in the offline phase. Later, in the online phase, he is only allowed to request for the multiplication of a matrix from $M_A$ by a matrix from $M_B$. Only a few schemes such as [19] allow the client to request for the multiplication of two fresh (not previously announced to the cloud server) matrices. As an instance of this, in Lei’s scheme [19] the client can directly outsource its two matrices to the cloud server and request for the multiplication of these two fresh matrices. However, this scheme does not consider public verifiability. Moreover, some of them cannot protect the privacy of outsourced data and results [8, 10]. Therefore, we are motivated to design a secure and efficient protocol for outsourcing of multiplication of two freshly generated large matrices with public verifiability.

1.2 Challenges

Although it is quite promising, outsourcing computational problems to the commercial public clouds inevitably brings in new security concerns and challenges [19]. The first challenge is privacy of outsourced data and result. Generally speaking, the issue of security and privacy has become a major concern when the sensitive data is not processed in a fully trusted cloud environment [31]. Recently, a number of publications have been proposed to design specific secure schemes for outsourcing computation operations. In most of them data owner, i.e. a person who has sensitive data, tolerates massive overheads. But the privacy of sensitive data is not protected completely. In our scheme we consider that a client can outsource multiplication of two large matrices to a cloud server and even the verification of the result to a third party as a verifier.

The second challenge is verifying the result returned by the server. A cloud server might not always provide the correct result of a given computational task [19]. It might be lazy in order to save its resources and return random result to the data owner. In some cases, servers are not willing to report their failures and may return accidental results in order to keep their clients. Hence, the cloud servers need to prove their honesty by sending an unforgeable proof.

The third challenge is efficiency. On one hand, a key requirement is that the amount of local work performed by the client must be substantially cheaper than performing the original computational problem on its own. Otherwise, it does not make sense for the client to resort to the cloud. On the other hand, it is also desirable to maintain the amount of work performed by the cloud as close as possible to that needed to compute the original problem by the client itself. Conversely, the cloud may be unable to complete the task in a reasonable amount of time, or the cost of the cloud may become prohibitive [19]. In addition, most of the clients have no powerful resources to verify the result. Thus, a public verifiable outsourcing protocol with low computation overhead is needed.

1.3 Contribution

The contributions of this paper are summarized as below:

• 1. We present a forgery attack by the malicious cloud server against the Zhang-Lei’s scheme for outsourcing matrix multiplication.

• 2. We propose a cryptographic protocol for secure outsourcing of multiplication of two arbitrary large matrices.

• 3. In our proposed scheme, the problem of high computation overhead in both client and verifier side is well addressed.

• 4. We show that the proposed protocol is efficient in terms of computation, communication and storage overhead.

1.4 Organization

The rest of the paper is organized as follows. Section 2 reviews related work on outsourcing of matrix multiplication to the cloud server. Section 3 describes the preliminaries including system model, threat model and design goals. In Sect. 4, we briefly review the Zhang-Lei’s scheme and present a security attack against this scheme. Section 5 presents our proposed scheme. Section 6 discusses correctness and security analysis of our scheme. In this section, we evaluate performance of our scheme and compare it with related work. Finally, Sect. 7 concludes the paper.

2 Related work

As previously stated, the problem of outsourcing computation has attracted extreme attention in academia. Recently, various papers has discussed secure outsourcing of heavy operations such as modular exponentiation [13, 22, 23, 28], bilinear pairing [5], Fourier transformation [26], matrix inversion [4, 14, 18], determinant computation [20] and matrix multiplication [16, 33]. In this paper, we focus on secure outsourcing of matrix multiplication. The schemes proposed for matrix multiplication in the literature can be classified into two categories as reviewed below.

Multiplication of two arbitrary matrices In some schemes [9, 15, 24, 30] two matrices involved in the protocol are variable. In fact, the client has two arbitrary matrices A and B and wants to outsource the computation of $A\times B$ . These schemes are more flexible inasmuch as both input matrices involved in the protocol are of arbitrary, yet compatible, dimensions.

For the first time, in 2002, Atallah et al. investigated the problem of outsourced scientific computations like matrix multiplications and introduced an outsourcing computation framework. This schemes suffers from information leakage [1]. After that, in 2008, Benjamin et al. presented a private and cheating-free protocol for outsourcing algebraic computations where the data owner outsources its computations to two remote servers. One disadvantage of this technique is that the two servers have to be non-colluding. Moreover, the above protocol requires heavy computations that degrades the efficiency of the outsourcing process [3]. In 2010, Gennaro et al. proposed a scheme by combining fully homomorphic encryption (FHE) [12] and Yao’s Garbled Circuits [27]. This scheme provides the formalized definition of non-interactive verifiable outsourcing computation using the pseudo-random functions (PRF) [11]. In addition, Atallah proposed protocols for secure outsourcing of matrix multiplication based on Shamir’s secret sharing scheme. In this scheme the client outsources its data to at least two servers [2]. In 2011, Mohassel proposed a secure protocol for outsourcing linear algebra computation with verifiable results based on homomorphic encryption scheme that has high costs and overhead [24]. Zhang et al. presented a protocol for secure outsourcing of matrix multiplications. This approach has significant computation overhead in verification phase [32]. In 2017, a secure and efficient protocol is proposed for outsourcing large matrix multiplication in online mode. This scheme protects privacy of outsourced data and result. But it does not support public verification [9]. Recently, Zhang et al. designed a protocol for outsourcing matrix multiplication. This scheme has a massive offline phase [33]. Kong et al. presented a protocol of matrix multiplication based on similarity transformation. This scheme does not support public verification [17].

multiplication of an arbitrary matrix by a fixed matrix In some protocols [8, 10, 21, 29, 33], one of the two matrices must be constant. As a matter of fact, the client sends a constant matrix to the cloud server in offline phase, before starting an online phase. These schemes are not suitable for many real applications due to the massive communication overhead and runtime. In 2012, Fiore et al. presented a publicly verifiable protocol for outsourcing matrix multiplication based on bilinear pairing and algebraic PRFs. Based on [15], this approach not only fails to achieve high efficiency, but also fails to achieve data privacy [10]. In 2015, Jia et al. proposed a protocol for outsourcing matrix multiplication under amortized model. This scheme does not protect privacy of multiplication result and has a heavy preprocessing phase. Moreover, it does not provide public verification [15]. In 2016, Elkhiyaoui et al. proposed a protocol for outsourcing matrix multiplication. In this scheme, one of the matrices must be constant and the client tolerates massive computation [8].

3 Preliminaries

As mentioned above, our scheme is designed for publicly verifiable outsourcing of multiplication of two matrices with arbitrary sizes which is just executed in online mode. In Sect. 3.1, we present notation used in this paper and also the required mathematical background. In the next sub-sections, the system model, threat model and design goals of our scheme are clarified.

3.1 Notation and mathematical background

We denote notations used in this paper in Table 1. Based on [21, 32] we define the notion of bilinear pairing utilized in Zhang-Lei’s scheme [30] which is explained in Sect. 4.

Definition 1

(Bilinear Pairing) Let $G_1$, $G_2$ and $G_T$ be three multiplicative cyclic groups of the same prime order q, and $g_1$ and $g_2$ be a generators of group $G_1$ and $G_2$, respectively. The map $e: G_1\times G_2 \rightarrow G_T$ is called a bilinear pairing if it satisfies the following properties.

• Bilinearity: for any $a,b\in Z_q$, any $g\in G_1$ and any $h\in G_2$ the equation $e(g^a,h^b )=e(g,h)^{ab}$ holds.

• Non-degeneracy: for any $g\in G_1$, if for all $h\in G_2$ equation $e(g,h)=1$ is true then $g=0$. Moreover, for any $h\in G_2$, there exists some $g\in G_1$ such that $e(g,h) \ne 1$.

• Efficiency: there exists an efficient algorithm for computing e.

  Table 1 Notations

3.2 System model

As shown in Fig. 1 our proposed scheme has three entities: a computationally weak client, a powerful cloud server and a verifier.

Client: the client wants to outsource matrix multiplication of two large matrices with compatible sizes to a powerful cloud server for decreasing its computational overhead. In order to protect the privacy of data, the client encrypts and sends data to the cloud server. The client performs computations on encrypted matrices to obtain the encrypted result. After receiving encrypted result that is verified by the verifier, the client accepts and decrypts it. On the whole, in our scheme the client can choose some verifiers to verify the correctness of the result. Particularly, public verifiability means that everyone can verify the correctness of the result. It helps the client to be sure about the correctness of the result.

Fig. 1

System Model

Cloud server: The computational resource-limited client outsources its heavy computations to the cloud server with unlimited computing resources. In our scheme, the cloud server computes multiplication result in encrypted form and a non-interactive proof. Then, it sends the non-interactive proof to the verifier. It is worthwhile to know that one of the reasons that the client outsources its matrices and verify the result by utilizing public verifiability is that some servers may be reluctant to report their failures in order to increase client retention for their own services.

Verifier: the verifier is the third party who can check validity of the result. It receives the encrypted result and the proof from the cloud server and verifies them by using the public keys. If the results are true, the verifier sends them to the client. Now the client is sure about validity of the result.

3.3 Threat model

Generally, there are two types of threat models in outsourcing: semi-honest cloud and malicious cloud. The semi-honest cloud follows the protocol correctly, but it tries to learn additional information about input and output data. While, the malicious cloud can arbitrarily deviate from protocol specification [19]. The malicious cloud server may send random result to the client for saving its resources. In this paper, we assume the cloud server treats as a semi-honest cloud server.

3.4 Design goals

In this part, we define our goals as follows.

Privacy protection of outsourced data: the privacy of outsourced matrices must be protected. In this scheme, we use secret keys to protect privacy of matrices.

Privacy protection of multiplication result: our proposed scheme provides protection of multiplication result by secret matrices.

Unforgeability of proof: We have to guarantee that the cloud server cannot forge the proof.

Arbitrary large matrix: Most of existing works are not flexible enough since one of matrices involved in the multiplication should be fixed. The proposed scheme enables a flexible way to outsource multiplication of any two arbitrary matrices.

Efficiency: In this paper, the proposed scheme will be executed in online mode and does not need any offline preprocessing phase. Therefore, the client tolerates less overhead in total.

Public verifiability: Any verifier can check validity of the result by checking the correctness of the proof. Therefore the client can outsource even the verification of the result.

4 Review of the Zhang-Lei’s scheme

In this section, we first describe Zhang-Lei’s scheme [30] which contains five phases namely, Encryption, Requesting, Computing, Verification and Decryption phases. In this scheme, the matrices are categorized into two groups as ${\mathcal{M}}_{A_{n_1 \times n_2}}$ and ${\mathcal{M}}_{B_{n_2 \times n_3}}$ beforehand, where each matrix has a unique identifier.

Encryption phase In this phase, the client encrypts matrices $A \in {\mathcal{M}}_A$ as ${\tilde{A}}=A+\alpha _A \beta _A^T$ and $B \in {\mathcal{M}}_B$ as ${\tilde{B}}=B+\alpha _B \beta _B^T$ , where $\alpha _A \in Z_q^{n_1}, \,\beta _A \in Z_q^{n_1}, \, \alpha _B \in Z_q^{n_2}$ and $\beta _B \in Z_q^{n_2}$ are columnar vectors. It computes $W_{n_1 \times n_2}$, where $W_{i,j}=g_1^{r_i {\tilde{a}}_{i,j}}$ and $pk2_i=g_2^{c_i}$ , where $r_i=H(ID_A \Vert i\Vert SK)$ and $c_j=H(ID_B \Vert j\Vert SK)$ and sends them to the cloud server.

Requesting phase In this phase, the client computes $pkt_{i,j}=g_T^{r_ic_j}$, where $g_T=e(g_1,g_2)$ and sends it with identifiers of matrices to the cloud server.

Computing phase The cloud server computes ${\widetilde{Res}}={\tilde{A}} \times {\tilde{B}}$ and a non-interactive proof $\pi _{n_1 \times n_3}$ , where its (i, j)-th element is computed as $\pi _{i,j}=\prod _{k=1}^{n_2} W_{i,k}^{{\tilde{b}}_{k,j}}$ . Then it sends the (encrypted result, proof) pair $({\widetilde{Res}}, \pi )$ to the verifier.

Verification phase The verifier judges the correctness of equation for each element of ${\widetilde{Res}}$ as $e(\pi _{i,j},pk2_j)=(pkt_{i,j})^{{\widetilde{Res}}_{i,j}}$. If all the conditions are true, it sends the encrypted result ${\widetilde{Res}}$ to the client.

Decryption phase After that, the client computes $R=(A \alpha _B)\beta _B^T+\alpha _A(\beta _A^TB)+\alpha _A(\beta _A^T \alpha _B)\beta _B^T$ and obtains the final result as $Res={\widetilde{Res}}-R$.

4.1 Forgery attack against Zhang-Lei’s scheme

In this section, we find a security vulnerability in Zhang-Lei’s scheme and in the next section, we present a new secure and efficient publicly verifiable scheme for outsourcing multiplication of large matrices which fixes this vulnerability. If the cloud server behaves dishonestly, it can pass the verification equation $e(\pi _{i,j} , pk2_j)=(pkt_{i,j})^{{\widetilde{Res}}_{i,j}}$. More precisely, the attack procedure is as follows.

• 1. The client and the cloud server proceed the Zhang-Lei’s protocol until the cloud server computes the true values for the encrypted result and the proof as $({\widetilde{Res}}, \pi )$.

• 2. Then it chooses an arbitrary scalar $x \in {\mathbb{Z}}_q^*.$

• 3. It computes $x. {\widetilde{Res}}$ as the manipulated encrypted result and tunes the corresponding proof as $\pi ^x.$

• 4. Finally, it sends $({\widetilde{Res}}', \pi ')= (x. {\widetilde{Res}}, \pi ^x)$ as a new (encrypted result and proof) to the verifier. Now we show that this incorrect pair of $(x. {\widetilde{Res}} , \pi ^x)$ passes the verification equation $e(\pi '_{i,j}, pk2_j)= (pkt_{i,j})^{{\widetilde{Res}}'_{i,j}}$.

Since ${{\pi }_{i,j}}=\mathop{\prod}\nolimits_{k=1}^{{{{n}_{2}}}} W_{i,k}^{{{{{\tilde{b}}}}_{k,j}}},~{{W}_{i,k}}=g_{1}^{{{r}_{i}}{{{{\tilde{a}}}}_{i,k}}}$, $pkt_{i,j}=g^{r_i c_j}_T$ and $pk2_j=g_2^{c_j}$ we have that

$$\begin{aligned} e\left( {{{{\pi }'}}_{i,j}},pk{{2}_{j}} \right)&=e\left( \pi _{i,j}^{x},pk{{2}_{j}} \right) \\&=e\left( {{\left( \underset{k=1}{\overset{{{n}_{2}}}{\mathop \prod }}\,W_{i,k}^{{{{{\tilde{b}}}}_{k,j}}}\right) ^x}},pk{{2}_{j}} \right) \\&= e\bigg (\bigg( \prod _{k=1}^{n_2} (g_1^{r_i {\tilde{a}}_{i,k}})^{{\tilde{b}}_{k,j}}\bigg)^x , g_2^{c_j} \bigg )\\&= e\big (\big( g_1^{\sum _{k=1}^{n_2} r_i {\tilde{a}}_{i,k}.{\tilde{b}}_{k,j}})^x, g_2^{c_j} \big )\\&=e{{\left( {{g}_{1}},{{g}_{2}} \right) }^{{{r}_{i}}.{{c}_{j}}.x\underset{k=1}{\overset{{{n}_{2}}}{\mathop \sum }}\,{{{{\tilde{a}}}}_{i,k}}.{{{{\tilde{b}}}}_{k,j}}}}\\&={{\left( {{g}_{T}} \right) }^{{{r}_{i}}.{{c}_{j}}.x\underset{k=1}{\overset{{{n}_{2}}}{\mathop \sum }}\,{{{{\tilde{a}}}}_{i,k}}.{{{{\tilde{b}}}}_{k,j}}}}\\&={{\left( pk{{t}_{i,j}} \right) }^{x\underset{k=1}{\overset{{{n}_{2}}}{\mathop \sum }}\,{{{{\tilde{a}}}}_{i,k}}.{{{{\tilde{b}}}}_{k,j}}}}\\&={{\left( pk{{t}_{i,j}} \right) }^{x.{\widetilde{Res}}}}={{\left( pk{{t}_{i,j}} \right) }^{{{{\widetilde{Res}}}^{'}}}} \end{aligned}$$

The last equation is true because $\sum _{k=1}^{n_2} {\tilde{a}}_{i,k}. {\tilde{b}}_{k,j}$ is the (i, j)-th element of ${\widetilde{Res}}={\tilde{A}} \times {\tilde{B}}$. Thus, the verifier accepts ${\widetilde{Res}}'$ as the correct encrypted result and sends it to the client. Then the client decrypts ${\widetilde{Res}}'$ as $Res'= {\widetilde{Res}}'-R$ which is not equal to $A \times B$. But the client accepts it as the result $A \times B$. Therefore, this is a successful forgery attack.

Besides, this security vulnerability, the Zhang-Lei’s scheme has a preprocessing phase in offline mode. So the client tolerates heavy computational overhead. Also the verifier has to compute $n^2$ pairings in the verification phase. Therefore this protocol requires heavy computations that may degrade the efficiency of the outsourcing process. Moreover, their scheme is not flexible in the sense that the client is only allowed to request of the multiplication of matrices who has already committed to beforehand. In other words, the client cannot outsource the multiplication of two freshly generated matrices. So we are motivated to enhance Zhang -Lei’s scheme in order to make it work for freshly generated matrices, fix the mentioned security vulnerability and finally increase efficiency and computing speed. Specifically, we remove the offline phase and matrix identifiers. In addition, the computational overhead of the verifier side would be reduced into $2n^2$ exponentiations.

5 The proposed scheme

We assume a client outsources two encrypted matrices to the cloud server. The cloud server computes matrix multiplication and also provides a proof $\pi$ to the verifier. The verifier checks the proof. If the correctness of the result is proved, then the verifier computes MAC of the result. Then it sends ${\widetilde{Res}}$ and MAC to the client. Finally, the client checks the validity of MAC. IfMAC is validated, then he accepts the result and decrypts it. It is important to say that the client and the verifier have a common key to compute MAC.

In this section, we explain the proposed scheme which consists of five phases: the first phase is Setup. The second phase is Encryption phase that is executed by the client. Then the Computing phase is done by the server. The Verification phase is executed by the verifier and finally the client executes the Decryption phase.

Setup phase The client chooses two large primes p and q such that $q|p-1$. Then it generates a subgroup G of ${\mathbb{Z}}_p^*$ with the generator g of order q. Then it chooses a private key $sk \in G$ and a hash function $H:[n_1] \times G \rightarrow {\mathbb{Z}}_q^*$ . After that, the client publishes parameters as $param=(q,g,h)$ which is used by the whole outsourcing system.

Encryption phase in this phase, the client processes matrices before sending them to the cloud server. First the client chooses vectors $\alpha _A \in Z_q^{n_1}, \, \beta _A \in Z_q^{n_2}, \, \alpha _B \in Z_q^{n_2}$ and $\beta _B \in Z_q^{n_3}$ Then it encrypts matrices A and B into ${\tilde{A}}=A+\alpha _A \beta _A^T$ and ${\tilde{B}}=B+\alpha _B \beta _B^T$ , respectively. After that it sends ${\tilde{A}}$ and ${\tilde{B}}$ to the cloud server. Also the client computes matrix $W_{n_1 \times n_2}$ , where $W_{i,j}=g^{r_i {\tilde{a}}_{i,j}}$ and $r_i=H(i ||sk)$ and sk denotes the client’s secret key. Then it computes the public key as $PK_{n_1 \times n_2}=(pk_{i,j})=(g^{r_i})$ and sends it to the verifier. The details are shown in Algorithm 1.

Computing phase the cloud server receives matrices ${\tilde{A}}$ and ${\tilde{B}}$ and computes matrix multiplication result as ${\widetilde{Res}}={\tilde{A}} \times {\tilde{B}}$ and a non-interactive proof as $\pi =(\pi _{i,j})=(\prod _{k=1}^{n_2}W_{i,k}^{{\tilde{b}}_{k,j}})$ where $1 \le i \le n_1, \, 1 \le j \le n_3.$ Then it sends $( {\widetilde{Res}}, \pi )$ to the verifier. The details are shown in Algorithm 2.

Verification phase according to the Algorithm 3, this phase is executed by the verifier. After receiving ${\widetilde{Res}}$ and $\pi$, the verifier checks if $\pi _{i,j}=(pk_{i,j})^{{\widetilde{res}}_{i,j}}$ and $\pi _{i,j}=\prod _{k=1}^{n_2} W_{i,k}^{{\tilde{b}}_{k,j}}$.

If these equations hold, it generates MAC of $({\widetilde{Res}} ,\pi )$ as $MAC_{K_{cv}}(PK,{\widetilde{Res}})$ by the common key ${K_{cv}}$ previously shared between the client and the verifier. The verifier sends the MAC with ${\widetilde{Res}}$ to the client.

Decryption phase as shown in Algorithm 4 to ensure the integrity of the received messages , the client checks the MAC. If the MAC is confirmed , it computes matrix R as $R=(A \alpha _B)\beta _B^T+\alpha _A(\beta _A^T B)+\alpha _A(\beta _A^T \alpha _B) \beta _B^T$ and decrypts ${\widetilde{Res}}$ as $Res={\widetilde{Res}}-R$ . Otherwise the client rejects it and sends $\perp$.

6 Security and performance evaluation

In this section first, we prove the correctness of verification and decryption phases. Second, we evaluate the performance of our scheme and compare it with the related work in terms of functionality as well as computation, communication and storage.

6.1 Correctness and security analysis

We prove the correctness of verification and decryption phases and guarantee the security of our scheme as follows.

Correctness guarantee in this scheme, the verifier checks the equations $\pi _{i,j}=(pk_{i,j})^{{\widetilde{res}}_{i,j}}$ and

$\pi _{i,j}=\prod _{k=1}^{n_2} W_{i,k}^{{\tilde{b}}_{k,j}}$ . If the computation is performed correctly, the above equations hold. First according to the equation $W_{i,j}=g^{r_i {\tilde{a}}_{i,j}}$, we replace $W_{i,j}$ by $g^{r_i{\tilde{a}}_{i,j}}$.

$$\begin{aligned} \pi _{i,j}&= \prod _{k=1}^{n_2} (W_{i,k})^{{\tilde{b}}_{k,j}}\\&= \prod _{k=1}^{n_2} (g^{r_i{\tilde{a}}_{i,k}})^{{\tilde{b}}_{k,j}}\\&= \prod _{k=1}^{n_2} (g)^{r_i{\tilde{a}}_{i,k}{\tilde{b}}_{k,j}}\\ \end{aligned}$$

Now according to the equation $\sum _{k=1}^{n_2} {\tilde{a}}_{i,k} {\tilde{b}}_{k,j}={\widetilde{Res}}_{i,j}$, we have

$$\begin{aligned} \pi _{i,j}&= g^{r_i \sum _{k=1}^{n_2}{\tilde{a}}_{i,k}{\tilde{b}}_{k,j}}\\&= (g^{r_i})^{{\widetilde{Res}}_{i,j}} \end{aligned}$$

Finally, according to the equation $W_{i,k}=g^{r_i {\tilde{a}}_{i,k}}$ , the above equation is written as:

$$\begin{aligned} \pi _{i,j}&= \prod _{k=1}^{n_2} (g^{r_i{\tilde{a}}_{i,k}})^{{\tilde{b}}_{k,j}}\\&= \prod _{k=1}^{n_2} (W_{i,k})^{{\tilde{b}}_{k,j}}\\ \end{aligned}$$

Now, we evaluate correctness of decryption phase as stated below

$$\begin{aligned}{\widetilde{Res}} -R&={\tilde{A}} \times {\tilde{B}} -R= (A+ \alpha _A \beta _A^T )( B+ \alpha _B \beta _B^T)-R\\&=AB+\underbrace{ A \alpha _B \beta _B^T +\alpha _A\beta _A^T B+ \alpha _A\beta _A^T \alpha _B\beta _B^T}_\text{{ R}}-R\\&=AB \end{aligned}$$

Security guarantee as mentioned before, the client outsources multiplication of two arbitrary matrices A and B to the cloud server. Actually, it has to send its sensitive data to the untrusted entity. The semi-honest cloud server may send incorrect results to the client. To ensure that the protocol is secure, we analyze security properties of our scheme. The security properties that we focus on are described as follows.

Privacy Protection of Outsourced Data: We demonstrate that our scheme achieves the privacy protection of outsourced data. We assume a semi-honest cloud server tries to learn more information about matrices. To protect of revealing outsourced data, the matrices are encrypted. In this way, the client encrypts matrices A and B as ${\tilde{A}}=A+\alpha _A \beta _A^T$ and ${\tilde{B}}=B+\alpha _B \beta _B^T$ , respectively. To achieve matrices A and B, the cloud server has to know vectors $\alpha _A,\beta _A^T,\alpha _B$ and $\beta _B^T$ . These vectors are randomly chosen and kept secret from the cloud server. Therefore, the private information about outsourced matrices could not be obtained by the cloud server and our scheme achieves privacy protection of outsourced matrices.

Privacy protection of result One of the most important properties of outsourced computing is the privacy protection of the result. The cloud server needs matrix R to achieve the decrypted result Res. But matrix R is private and created by the client and the cloud server cannot learn any more information about the original result Res. So the privacy protection of result is achieved.

Unforgeability of result When the verifier sends the result to the client, the attacker can manipulate the result ${\widetilde{Res}}$ and sends it to the client. To prevent this attack, the verifier computes MAC of public key and result as $MAC_{K_{cv} } (PK,{\widetilde{Res}} )\Vert {\widetilde{Res}}$ that receives from the cloud server. The verifier sends MAC to the client and the client checks the validity of the MAC.

Unforgeability of proof Based on the threat model of this scheme, the cloud server may send incorrect results to the client. So the client has to check the correctness of result. It delegates verifying phase to the verifier. The cloud server sends the encrypted result ${\widetilde{Res}}$ and the proof $\pi$ to the verifier. The cloud server needs $r_i=H(i \Vert sk)$ to forge the proof and pass the verifier filter. But, based on hardness of the discrete logarithm problem (DLP), the cloud server cannot achieve $r_i$ in the equation $PK=(pk_{i,j})=(g^{r_i } ).$ Also it cannot achieve $r_i$ by using equation $W=(W_{i,j})=(g^{r_i {\tilde{a}}_{i,j}} )$ and having encrypted matrix ${\tilde{A}}$ . On the other hand, due to the one-way hash function H, the cloud server also cannot achieve any information about $r_i=H(i \Vert sk)$ and private key sk. If the cloud server sends ${\widetilde{Res}}$ and $\pi$ randomly, it can pass the first equation. To prevent this attack, the verifier has to check the second equation $\pi _{i,j}=\prod _{k=1}^{n_2} W_{i,k}^{{\tilde{b}}_{k,j} }$ . If the cloud server forges the proof $\pi$, it cannot pass the second equation. As a result, our proposed scheme will provide the property of unforgeability of proof.

6.2 Performance evaluation

Now, we evaluate the performance of our scheme and compare it with the related work in terms of functionalities as well as computation, communication and storage. Table 2 presents some notations used in this section.

Table 2 Notation for performance evaluation

Table 3 Comparison of functionality

Functionality we compare functionalities among [9, 10, 15, 21, 30, 33] and our scheme. All schemes except [30] are protected against the forgery attack. Also all schemes except [9, 15] have public verifiability. Protocols [10, 15] do not provide privacy protection of multiplication result. Moreover, protocols [10, 21] do not provide privacy protection of outsourced data and one of the matrices involved in the computing has to be fixed, which makes the scheme unsuitable for many applications. In [15, 30, 33] the client chooses matrices among two categories as ${ M_A}$ and ${M_B}$ which are created in the preprocessing phase. While in our scheme and [9] the matrices are selected arbitrarily whenever the client wants, and the protocol can just be executed in the online mode. The details are shown in Table 3.

Computation overhead as shown in previous section, [9] does not have public verifiability. So in this section, we compare our protocol with [10, 21, 30, 33] in term of computation overhead. First the computation overhead in the offline phase and second the computation overhead in the online phase will be compared. As shown in Table 4 our scheme does not have any offline phase. While [10, 21, 30, 33] have heavy preprocessing phases. As mentioned in Table 3, N is the number of matrices in categories ${M_A}$ and ${M_B}$. Based on [33] we consider $N=10^4$. In this section we also compare computation overhead of the verifier. The verifier in the verification phase of [10, 21, 30] has to compute $n^2$ pairings and $n^2$ exponentiations and in [33] $2n^2$ pairings and $2n^2$ exponentiations. While the proposed scheme has to compute only $2n^2$ exponentiations. So, not only our scheme fixes the mentioned security vulnerability of [30], but also its computation overhead in client side and verifier side are n exponentiations and $n^2$ pairings less than [30], respectively. As a result, our scheme is more efficient than related work in term of computation overhead.

To support this inference in reality, we estimate the running time of our protocol on a system with core i5 processor 2.7 GHz and 4.0 GB RAM and compare it with [10, 21, 30, 33]. Our estimation is based on the run times of the cryptographic operations reported in [6, 7, 25]. Let all the matrices be square, where $n_1=n_2=n_3=10^3$.

To clarify, as mentioned before, we specify time of multiplication, exponentiation, pairing and hash function computation in Table 5 based on [6, 7, 25]. In addition, we estimate the run time of protocols presented in [10, 21, 30, 33] and compare them with our scheme in terms of client side and verifier side which is shown in Tables 6 and 7, respectively. It is necessary to mention that all the values reported in these tables are in terms of seconds. Further, the dimensions of matrices are supposed to be 1000 to 6000. As can be seen in Table 7, our scheme is at least 15 times faster than the related work in verification side when dimensions increase.

Table 4 Comparison of computation overhead

Table 5 Running time of operations

Table 6 Comparison of client runtime

Table 7 Comparison of verifier runtime

As shown in Figs. 2 and 3, the running time of our scheme are obviously less than those of previous schemes. Therefore, our scheme is more efficient than others in the client and verifier sides. The most striking feature observed from tables and figures is that our proposed scheme has overwhelmingly decreased verifier’s computation overhead which demonstrates a major achievement of our proposed scheme clearly.

Communication overhead In this part, we compare communication overhead of related work with our scheme. Our scheme does not have any offline mode. But [10, 21, 30, 33] have an offline phase where the client tolerates massive communication overheads. As a matter of fact, the communication overhead is measured in terms of the number of elements exchanged between the client and the server. This comparison is shown in Table 8.

Fig. 2

Comparison of client side overhead

Fig. 3

Comparison of verifier side overhead

Table 8 Comparison of communication overhead

Storage overhead in this section, we analyze the storage overhead of the client side. In [30] the client has to save secret key, secret parameters and public keys.

Remarkably, in [10, 33] the client has to keep encryption parameters. Whilst, in our scheme the client only saves the secret key and the secret parameters. In fact, the storage overhead is measured in terms of the number of elements stored in the client side. Overall consideration, the storage overhead of our scheme is acceptable. The details are shown in Table 9.

Table 9 Comparison of storage overhead

7 Conclusion

In this paper, we presented a secure and efficient protocol for publicly verifiable outsourcing of large matrix multiplication. Our proposed scheme provides a more secure and efficient way for the client to compute multiplication of any two arbitrary matrices in an online mode with public verifiability. More particularly, security analysis demonstrates that our scheme achieves privacy protection of outsourced data, privacy protection of multiplication result, unforgeability of proof and public verification of the result in online mode. We compared our scheme with related work in terms of functionality, computation, communication and storage overhead. In consequence, the runtime of our protocol has dramatically plummeted due to declining computation overhead of verification side and eliminating offline phase in the client side. Hence, this scheme has a lighter computation, communication and storage overhead than previous works.