# Efficient and Privacy-Preserving Outsourcing of 2D-DCT and 2D-IDCT

Authors: Dezhi An; Shengcai Zhang; Jun Lu; Yan Li
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

As a subset of discrete Fourier transform (DFT), discrete cosine transform (DCT), especially two-dimensional discrete cosine transform (2D-DCT), is an important mathematical tool for digital signal processing. However, the computational complexity of 2D-DCT is quite high, which makes it impossible to meet the requirements in some signal processing fields with large signal sizes. In addition, to optimize the 2D-DCT algorithm itself, seeking help from a cloud platform is considered to be an excellent alternative to dramatically speeding up 2D-DCT operations. Still, there are three key challenges in cloud computing outsourcing that need to be addressed, including protecting the privacy of input and output data, ensuring the correctness of the returned results, and ensuring adequate local cost savings. In this paper, we explore the design of a practical outsourcing protocol for 2D-DCT and 2D-IDCT, which well solves the above three challenges. Both theoretical analysis and simulation experiment results not only confirm the feasibility of the proposed protocol but also show its outstanding performance in efficiency.


---

## Body

## 1. Introduction

DFT is a common tool for frequency domain analysis of discrete signals and systems, but it is inconvenient to process image and voice data due to the need for complex domain operations. To solve this problem, a real domain transform, called DCT, is constructed based on DFT by preserving only the cosine term in the Fourier series. In addition to the general orthogonal transform properties of DCT, the basis vector of its transform matrix can well describe the relevant features of image signals and human voice signals. Therefore, DCT is considered to be a quasioptimal tool for transforming image and voice signals and is widely used in various fields such as media compression [1]–[3], digital watermarking [4]–[6], and wireless communication [7, 8]. 2D-DCT can directly transform two-dimensional data, so it is quite suitable for the analysis and processing of two-dimensional signals, such as static images. For example, 8×8 2D-DFT is adopted as a standard by the JPEG still image compression algorithm [9].The computational complexity of 2D-DCT and 2D-IDCT is dominated by computing the product of three matrices. Such high-computational overhead makes it impossible to perform high-efficiency processing on signals when the local computing equipment is insufficient or the signals are large in size. Wireless camera sensor networks, for example, are widely used in habitat monitoring, target detection, and espionage [10, 11], where nodes typically use processors with low cost, micro power consumption, and poor performance. In contrast, these nodes are often burdened with complex image processing tasks, a considerable portion of which require the participation of 2D-DCT or 2D-IDCT.In order to improve the efficiency of the transformation, the usual method is to divide the signal into blocks, then perform 2D-DCT or 2D-IDCT operations in each block, and finally merge the blocks. Nevertheless, the method of using blocks is not a once and for all solution, because smaller blocks are necessary for greater efficiency, but too small blocks will lead to serious block effects. In addition, various fast 2D-DCT and 2D-IDCT algorithms have been proposed [12]–[14], which can reduce the computational complexity by more than half on the basis of using a block method.We emphasize that in addition to efficiency optimization from an algorithmic perspective, requesting computing assistance from the cloud platform is also an excellent alternative. For example, the image processing tasks of nodes in a wireless sensor network can be delegated to a public cloud server. The cloud platform has a large amount of hardware and software resources, and the temporary use rights of partial computing resources it owns are transferred to clients by way of fee lease. The process by which clients rent cloud resources to help them complete their own computing is called cloud outsourcing. On the one hand, the client can achieve significant computing overhead savings and efficiency improvement through computing outsourcing, so as to quickly complete high-complexity computing tasks. On the other hand, the client can significantly reduce costs by eliminating the expense of purchasing and maintaining large amounts of computing equipment. At the same time, cloud platforms can also reap considerable economic benefits from resource rentals. Therefore, computing outsourcing is considered a win-win move for both the client and the cloud.However, computing outsourcing between the client and the cloud faces three key challenges. First, we must protect the client’s privacy from being stolen. The client’s input and output data contains private information, which may be personally identifiable information, trade secrets, or core technical parameters. Since the cloud is untrusted, we must protect the plaintext of the input and output data from being obtained by the cloud. Meanwhile, the high concentration of information makes the cloud platform vulnerable, which is also a possible way to leak private information. Second, we must verify the results returned by the cloud. The cloud platform is run for profit, and a malicious cloud will deliberately return random error results to the client to extract cost savings. Even if the cloud is honest, calculation errors may occur due to software bugs or hardware errors. Therefore, it is necessary to design an efficient verification algorithm to strictly control the correctness of the returned results. Third, we must ensure that the client can realize significant savings from computing outsourcing. In other words, the total complexity of decryption, encryption, and result verification algorithms must be far less than that of solving the original problem directly; otherwise, there is no need for the client to outsource the computing task. In general, a qualified computing outsourcing protocol must be secure, verifiable, and efficient.In this paper, a protocol capable of solving the above three challenges is designed for the outsourcing of 2D-DCT and 2D-IDCT. Before giving the protocol, we discuss two possible designs in an exploratory way. Multiround communication and block encryption severely damage the efficiency of both designs. In response to the problems in these two designs, we propose the formal outsourcing protocol, which greatly reduces the client’s communication overhead and key management overhead. In the proposed protocol, the original two-dimensional signal matrix is integrally encrypted without affecting the block flexibility of the cloud, i.e., the cloud can still perform 2D-DCT or 2D-IDCT of any block size according to the client’s will. This is an important point that affects the versatility of the protocol, because different application scenarios may require the operation of 2D-DCT or 2D-IDCT with different block sizes. Subsequently, we carried out theoretical analysis to confirm that the proposed protocol meets the requirements of security, verifiability, and efficiency. Finally, the simulation results show that the proposed protocol is not only better than block 2D-DCT and 2D-IDCT in efficiency but also faster than the corresponding fast 2D-DCT and 2D-IDCT algorithms.To summarize, our main contributions include the following:(i)
To the best of our knowledge, we are the first to propose such an outsourcing protocol for 2D-DCT and 2D-IDCT, and we are also the first to accelerate the operational efficiency of 2D-DCT and 2D-IDCT from the perspective of cloud computing outsourcing(ii)
Through carrying out theoretical analysis and simulation experiments, it is shown that the proposed protocol handles the three challenges faced in computing outsourcing well(iii)
In the proposed protocol, only a single round of communication is required and the key management work is simple, which is suitable for the outsourcing of 2D-DCT and 2D-IDCT with arbitrary block sizeThe rest of this paper is organized as follows. Section2 describes the related work, and Section 3 gives the problem statement. 2D-DCT and 2D-IDCT are briefly introduced in Section 4. Section 5 presents the possible designs and the formal outsourcing protocol. Section 6 provides theoretical analysis, followed by experiments in Section 7. Finally, Section 8 concludes this paper.


## 2. Related Work

There are two ways to implement outsourcing for complexity calculations. On the one hand, the theoretical cryptography community considers designing a universal design that covers all problems, i.e., any outsourcing of computing can be realized through this design. The basic approach to achieve this goal is to use some sophisticated basic cryptographic tools, such as Yao’s garbled circuits [15] and Gentry’s fully homomorphic encryption (FHE) schemes [16]. In these designs [17]–[20], the original problem is converted into a Boolean circuit over {0, 1}, and then, the client encrypts the converted problem using a FHE algorithm and sends the encrypted problem to the cloud, who solves the problem homomorphically and returns the result. Finally, the client decrypts the result and checks its correctness. However, such designs are far from practical applications because of the extremely high complexity of FHE operations and the pessimistic circuit sizes.On the other hand, the security engineering community focuses on designing different outsourcing protocols to deal with different practical problems. Under this idea, the encryption of the original problem is generally achieved through some ingenious data conversion. Meanwhile, in order to face practical applications, the efficiency of the protocol is given special consideration to ensure that the client can acquire considerable cost savings from outsourcing. According to this trend, a large number of practical outsourcing protocols have been proposed. Among these protocols, there are outsourcing of basic mathematical calculations. Lei et al. proposed an outsourcing protocol for matrix inversion [21], Chen et al. proposed an outsourcing protocol for linear regression [22], and Li et al. proposed an outsourcing protocol for ID3 decision tree [23]. Several different outsourcing protocols for linear equations were presented in [24]–26]. In addition, some outsourcing protocols are directly oriented to practical engineering application scenarios. An outsourcing protocol for Markowitz portfolio was proposed by Zhang et al. in [27], an outsourcing protocol for data classification was proposed by Li et al. in [28], an outsourcing protocol for the storage and statistics of smart meter data was proposed by Zhang et al. in [29], and an outsourcing protocol for biometric identification was proposed by Zhu et al. in [30]. Moreover, Li et al. proposed an optimal GPU-accelerated multimedia processing service pricing strategy in [31].By using a homomorphic cryptography algorithm, some digital signal processing operations are transferred to the ciphertext domain to protect the privacy of the signal. Bianchi et al. implemented ciphertext domain operations on DFT and DCT in [32, 33], respectively. Zheng and Huang proposed a method for implementing discrete wavelet transform (DWT) and multiresolution analysis (MRA) in the homomorphic ciphertext domain [34]. Pedrouzo-Ulloa et al. realized secure number theoretic transform (NTT) in a distrustful environment [35]. Recently, Han et al. improved the homomorphic DFT with batch homomorphic encryption [36]. However, because of the high complexity of homomorphic operations, outsourcing with these solutions cannot meet the requirements of efficiency, i.e., the client fails to acquire the required savings. By contrast, data processing tools can also be efficiently outsourced, mainly to speed up signal processing. For example, Xiao et al. realized efficient and secure outsourcing of DFT, IDFT, and circular convolution [37], and Zhang et al. designed two outsourcing protocols for compressed sensing and sparse robustness decoding service in [38, 39], respectively. Nevertheless, the efficient outsourcing of 2D-DCT and 2D-IDCT has not been designed by predecessors.


## 3. Problem Statement

### 3.1. System Model

As illustrated in Figure1, the system consists of two entities: the client and the cloud. Their roles are elaborated as follows.(1)
Client, The client has a complex problem Φ that needs to be solved. In this paper, the problem Φ is considered to be the 2D-DCT or 2D-IDCT operation. In order to acquire computing overhead savings, the client plans to outsource the solution of Φ to the cloud platform. To achieve the purpose of privacy protection, the client firstly uses the locally generated private key KG to encrypt the original problem Φ and generate the encrypted problem ΦKG. Subsequently, the user sends ΦKG to the cloud, who solves ΦKG to obtain the result ΛKG and a proof Γ used for verification and returns ΛKG and Γ to the client. After the client receives ΛKG, the private key KG is used to decrypt ΛKG to obtain the result Λ of problem Φ. Finally, the client uses Γ to verify the correctness of Λ. If the verification passes, the client accepts Λ; otherwise, the client rejects Λ.(2)
Cloud. The cloud has a large number of hardware and software resources used for computing. It charges the rental fee of the client and provides computing support services for the client with part of its own resources. After receiving the encrypted problem ΦKG, the cloud solves it and returns ΛKG and Γ.Figure 1
System model.


### 3.2. Threat Model and Design Goals

The threat mainly comes from the cloud’s noncredibility, and here, we assume that the cloud is malicious. On the one hand, the cloud tries to obtain plaintext about problemΦ and result Λ. On the other hand, the cloud tries to save resources by returning a random erroneous result in the expectation that it will not be discovered by the client. In this case, we summarize the design goals of an efficient and privacy-preserving outsourcing protocol as follows.(1)
Correctness. The client must be able to acquire the correct answer if both the client and the cloud follow the protocol carefully.(2)
Privacy. The cloud cannot steal any private information of the client from the input and output data.(3)
Soundness. The client must be able to verify the correctness of the returned results.(4)
Efficiency. The client must be able to realize significant savings from computing outsourcing.


### 3.3. Framework

Syntactically, an outsourcing protocol includes the following five algorithms.(1)
KeyGen (1λ). On input of a security parameter λ, the client uses this algorithm to generate a private key KG.(2)
ProbEnc (Φ;KG). On input of the original problem Φ and the key KG, the client uses this algorithm to encrypt Φ to generate the encrypted problem ΦKG and then sends ΦKG to the cloud.(3)
ProbSolve (ΦKG). On input of the encrypted problem ΦKG, the cloud uses this algorithm to solve ΦKG. Then, the cloud returns the result ΛKG back, together with a proof Γ.(4)
ResultDec (ΛKG;KG). On input of the result ΛKG of ΦKG and the key KG, the client uses the algorithm to decrypt ΛKG to obtain the result Λ of the original problem Φ.(5)
ResultVerify (Λ;Γ). On input of the result Λ of Φ and the proof Γ, the client uses the algorithm to verify the correctness of Λ.


## 3.1. System Model

As illustrated in Figure1, the system consists of two entities: the client and the cloud. Their roles are elaborated as follows.(1)
Client, The client has a complex problem Φ that needs to be solved. In this paper, the problem Φ is considered to be the 2D-DCT or 2D-IDCT operation. In order to acquire computing overhead savings, the client plans to outsource the solution of Φ to the cloud platform. To achieve the purpose of privacy protection, the client firstly uses the locally generated private key KG to encrypt the original problem Φ and generate the encrypted problem ΦKG. Subsequently, the user sends ΦKG to the cloud, who solves ΦKG to obtain the result ΛKG and a proof Γ used for verification and returns ΛKG and Γ to the client. After the client receives ΛKG, the private key KG is used to decrypt ΛKG to obtain the result Λ of problem Φ. Finally, the client uses Γ to verify the correctness of Λ. If the verification passes, the client accepts Λ; otherwise, the client rejects Λ.(2)
Cloud. The cloud has a large number of hardware and software resources used for computing. It charges the rental fee of the client and provides computing support services for the client with part of its own resources. After receiving the encrypted problem ΦKG, the cloud solves it and returns ΛKG and Γ.Figure 1
System model.


## 3.2. Threat Model and Design Goals

The threat mainly comes from the cloud’s noncredibility, and here, we assume that the cloud is malicious. On the one hand, the cloud tries to obtain plaintext about problemΦ and result Λ. On the other hand, the cloud tries to save resources by returning a random erroneous result in the expectation that it will not be discovered by the client. In this case, we summarize the design goals of an efficient and privacy-preserving outsourcing protocol as follows.(1)
Correctness. The client must be able to acquire the correct answer if both the client and the cloud follow the protocol carefully.(2)
Privacy. The cloud cannot steal any private information of the client from the input and output data.(3)
Soundness. The client must be able to verify the correctness of the returned results.(4)
Efficiency. The client must be able to realize significant savings from computing outsourcing.


## 3.3. Framework

Syntactically, an outsourcing protocol includes the following five algorithms.(1)
KeyGen (1λ). On input of a security parameter λ, the client uses this algorithm to generate a private key KG.(2)
ProbEnc (Φ;KG). On input of the original problem Φ and the key KG, the client uses this algorithm to encrypt Φ to generate the encrypted problem ΦKG and then sends ΦKG to the cloud.(3)
ProbSolve (ΦKG). On input of the encrypted problem ΦKG, the cloud uses this algorithm to solve ΦKG. Then, the cloud returns the result ΛKG back, together with a proof Γ.(4)
ResultDec (ΛKG;KG). On input of the result ΛKG of ΦKG and the key KG, the client uses the algorithm to decrypt ΛKG to obtain the result Λ of the original problem Φ.(5)
ResultVerify (Λ;Γ). On input of the result Λ of Φ and the proof Γ, the client uses the algorithm to verify the correctness of Λ.


## 4. 2D-DCT and 2D-IDCT

### 4.1. 2D-DCT

Suppose that the original two-dimensional signal can be represented by a matrixf∈RN×N. In practice, if the original signal is not square, the transformation is usually done after the complement, and the original signal is subsequently obtained by removing the complement after the reconstruction. We consider performing block 2D-DCT of K×K on the matrixf, whereN is divisible by K.First, the matrixf needs to be partitioned as(1)f=f1,1f1,2f2,1f2,2⋯f1,N⋯f2,N⋯⋯fN,1fN,2⋯⋯⋯fN,N=f1,1f1,2f2,1f2,2⋯f1,N/K⋯f2,N/K⋯⋯fN/K,1fN/K,2⋯⋯⋯fN/K,N/K,where fi,j,i,j∈1,N and fi,j∈RK×K,i,j∈1,N/K are the elements and the blocks of f, respectively, and the relation between them is(2)fi,j=fKi−K+1,Kj−K+1⋯fKi−K+1,Kj⋯⋯⋯fKi,Kj−K+1⋯fKi,Kj.Subsequently, an orthogonal matrixA∈RK×K is calculated by(3)Ai,j=cicosj+0.5πNi,where ci is defined by(4)ci=1N,i=0,2N,i≠0.Finally, the operation resultF∈RN×N of K×K 2D-DCT on f can be expressed as(5)F=A·f1,1·ATA·f1,2·ATA·f2,1·ATA·f2,2·AT⋯A·f1,N/K·AT⋯A·f2,N/K·ATA·⋯⋯fN/K,1·ATA·fN/K,2·AT⋯⋯⋯A·fN/K,N/K·AT.


### 4.2. 2D-IDCT

2D-IDCT is the inverse process of 2D-DCT. Thus, similarly, the 2D-IDCT operation is represented as(6)f=AT·F1,1·AAT·F1,2·AAT·F2,1·AAT·F2,2·A⋯AT·F1,N/K·A⋯AT·F2,N/K·AAT·⋯⋯FN/K,1·AAT·FN/K,2·A⋯⋯⋯AT·FN/K,N/K·A.


## 4.1. 2D-DCT

Suppose that the original two-dimensional signal can be represented by a matrixf∈RN×N. In practice, if the original signal is not square, the transformation is usually done after the complement, and the original signal is subsequently obtained by removing the complement after the reconstruction. We consider performing block 2D-DCT of K×K on the matrixf, whereN is divisible by K.First, the matrixf needs to be partitioned as(1)f=f1,1f1,2f2,1f2,2⋯f1,N⋯f2,N⋯⋯fN,1fN,2⋯⋯⋯fN,N=f1,1f1,2f2,1f2,2⋯f1,N/K⋯f2,N/K⋯⋯fN/K,1fN/K,2⋯⋯⋯fN/K,N/K,where fi,j,i,j∈1,N and fi,j∈RK×K,i,j∈1,N/K are the elements and the blocks of f, respectively, and the relation between them is(2)fi,j=fKi−K+1,Kj−K+1⋯fKi−K+1,Kj⋯⋯⋯fKi,Kj−K+1⋯fKi,Kj.Subsequently, an orthogonal matrixA∈RK×K is calculated by(3)Ai,j=cicosj+0.5πNi,where ci is defined by(4)ci=1N,i=0,2N,i≠0.Finally, the operation resultF∈RN×N of K×K 2D-DCT on f can be expressed as(5)F=A·f1,1·ATA·f1,2·ATA·f2,1·ATA·f2,2·AT⋯A·f1,N/K·AT⋯A·f2,N/K·ATA·⋯⋯fN/K,1·ATA·fN/K,2·AT⋯⋯⋯A·fN/K,N/K·AT.


## 4.2. 2D-IDCT

2D-IDCT is the inverse process of 2D-DCT. Thus, similarly, the 2D-IDCT operation is represented as(6)f=AT·F1,1·AAT·F1,2·AAT·F2,1·AAT·F2,2·A⋯AT·F1,N/K·A⋯AT·F2,N/K·AAT·⋯⋯FN/K,1·AAT·FN/K,2·A⋯⋯⋯AT·FN/K,N/K·A.


## 5. Protocol Construction

### 5.1. Attempt One

Since the efficiency of 2D-DCT is mainly limited by the calculation of three matrix multiplication, we naturally think that the key of design is to realize the outsourcing ofA·fi,j·AT, where i,j∈1,N/K. Several different outsourcing protocols for the multiplication of two matrices have been proposed [40]–[42]. Therefore, a direct assumption is to first use these protocols to outsource A·fi,j to obtain the product S and then outsource S·AT, thereby acquiring calculation result of A·fi,j·AT.Apart from other flaws of the protocol, the most obvious drawback of the protocol is the need for two rounds of communication between the cloud and the client. This will bring not only multiplied communication overhead to the client but also multiplied computing overhead for the client, because the client needs to perform independent encryption, decryption, and result verification operations for each round of outsourcing. As a result, the existence of two-round communication will make it difficult for the outsourcing protocol to meet the requirements of high efficiency.


### 5.2. Attempt Two

We attempt to implement an efficient outsourcing protocol that required only one round of communication by using the privacy-preserving matrix multiplication as adopted in [40, 43, 44]. First, to protect the privacy of input and output data, the private key matrices P1,P2,⋯,P4N2/K2∈RK×K are locally generated by the client as follows:(7)Pni,j=piδπni,j,n∈1,4N2K2,where pi is a random number and πn· is a permutation function that maps an original index i to its permuted index. Besides, δi,j is the Kronecker delta function given by(8)δi,j=1,i=j,0,i≠j.We emphasize that the inverse ofPn can be accessed simply by(9)Pn−1i,j=1Piδπn−1i,j.Afterwards, for any blockA·fi,j·AT of the matrix F in (5), the client encrypts the matrices A, fi,j, and AT as(10)EA=P4N/Ki−1+4j−3·A·P4N/Ki−1+4j−2−1,Efi,j=P4N/Ki−1+4j−2·fi,j·P4N/Ki−1+4j−1,EAT=P4N/Ki−1+4j−1−1·AT·P4N/Ki−1+4j.The encrypted matricesEA, Efi,j, and EAT are then sent to the cloud, who perform(11)EFi,j=EA·Efi,j·EAT=P4N/Ki−1+4j−3·Fi,j·P4N/Ki−1+4j.Finally, to decrypt the returnedEFi,j, the client only needs to calculate(12)Fi,j=P4N/Ki−1+4j−3−1·EFi,j·P4N/Ki−1+4j−1.This design avoids the trouble of multiround communication existing in Attempt One and seems to be feasible. However, this is not the case, because the complex key management severely slows down the efficiency of the protocol. In Attempt Two, for an original data matrix with dimensionN×N, the client needs to generate 4N2/K2 mutually independent key matrices with size K×K for encryption. Meanwhile, 2N2/K2 key matrices in them need to be saved in order to be invoked during decryption. Besides, we emphasize that in 2D-DCT and 2D-IDCT operations, only f and F are private in the input and output data, while A and AT are public and can be generated independently by anyone. Therefore, an efficient protocol should manage to encrypt only f or F on input.


### 5.3. Formal Protocol

#### 5.3.1. Outsourcing Protocol for 2D-DCT

We now present the formal protocol, which solves the flaws of Attempt One and Attempt Two well, i.e., not only requires only one round of communication but also greatly simplifies the key management workload.First, in terms of privacy protection, we adopted the privacy-preserving matrix addition as discussed in [26, 41, 45]. The client generates two random vectors u and v with size N×1 as the private key. To protect the privacy information in the original two-dimensional signal, the client encrypts the matrix f as follows:(13)Ef=f+u·vT.After the encryption of (13), any block fi,j in the matrix f satisfies(14)Efi,j=fi,j+ui·vjT,where vector ui∈RK×1 is a vector consisting of the Ki−K+1th to Kith elements of vector u and vector vjT∈R1×K is a vector consisting of the Kj−K+1th to Kjth elements of vector vT.Afterwards, the encrypted matrixEf is sent to the cloud who perform K×K 2D-DCT as(15)EFi,j=A·Efi,j·AT=A·fi,j+ui·vjT·AT=A·fi,j·AT+A·ui·vjT·AT=Fi,j+A·ui·vjT·AT.We emphasize that matricesA and AT are not private and can be generated independently by the cloud itself by (3). The calculated results EFi,j∀i,j∈1,N/K are then combined into matrix EF and returned to the client, who uses the private key vectors u and v to decrypt EF efficiently through(16)Fi,j=EFi,j−A·ui·vjT·AT.Finally, the client quickly verifies the correctness ofFi,j by the inference of Parseval’s theorem, i.e.,(17)∑m=1K∑n=1Kfi,j2m,n=∑m=1K∑n=1KFi,j2m,n.If (17) holds within the allowable error range, block Fi,j passes the verification. As long as all the blocks in the matrix Fpass the verification, the client accepts the calculation result F; otherwise, the client rejects F.We summarize the outsourcing protocol for 2D-DCT as follows.(1)
KeyGen (1λ). On input of a security parameter λ, the client generates the private key KG=u,v.(2)
ProbEnc (Φ;KG). On input of the original problem Φ=f and the key KG, the client performs (13) to encrypt Φ to generate the encrypted problem ΦKG=Ef and then sends ΦKG to the cloud.(3)
ProbSolve (ΦKG). On input of the encrypted problem ΦKG, the cloud solves ΦKG by (15). Then, the cloud returns the result ΛKG=EF back, together with an empty proof Γ.(4)
ResultDec (ΛKG;KG). On input of the result ΛKG of ΦKG and the key KG, the client performs (16) to decrypt ΛKG to obtain the result Λ=F of the original problem Φ.(5)
ResultVerify (Λ;Γ). On input of the result Λ of Φ and the proof Γ, the client verifies the correctness of Λ by (17).Compared with Attempt One and Attempt Two, on the one hand, the formal protocol requires only one round of communication. On the other hand, the difficulty of key management is greatly reduced because the key is just two vectors of lengthN. Meanwhile, only the private matrix f is encrypted on input, eliminating the encryption and transmission of A and AT, which further improves the efficiency of outsourcing. Besides, the original signal matrix f is encrypted in its entirety, making the encryption process more efficient and concise compared with block encryption. However, the integral encryption operation does not affect the block flexibility of the cloud, i.e., the cloud can still perform 2D-DCT of any block size based on negotiation with the client.


#### 5.3.2. Outsourcing Protocol for 2D-IDCT

The outsourcing protocol of 2D-IDCT is similar to that of 2D-DCT. First, the client also generates vectorsuand v locally as the private key. To protect the privacy of the input privacy matrix F, the client performs(18)EF=F+u·vT.Afterwards, the encrypted matrixEF is sent to the cloud who perform K×K 2D-IDCT as(19)Efi,j=AT·EFi,j·A.The calculated resultEf is then returned to the client who uses the private key to decrypt Ef efficiently through(20)fi,j=Efi,j−AT·ui·vjT·A.Finally, the correctness of resultingf is also verified by equation (17). We summarize the outsourcing protocol for 2D-IDCT as follows.(1)
KeyGen (1λ). On input of a security parameter λ, the client generates the private key KG=u,v.(2)
ProbEnc (Φ;KG). On input of the original problem Φ=F and the key KG, the client performs (18) to encrypt Φ to generate the encrypted problem ΦKG=EF and then sends ΦKG to the cloud.(3)
ProbSolve (ΦKG). On input of the encrypted problem ΦKG, the cloud solves ΦKG by (19). Then, the cloud returns the result ΛKG=Ef back, together with an empty proof Γ.(4)
ResultDec (ΛKG;KG). On input of the result ΛKG of ΦKG and the key KG, the client performs (20) to decrypt ΛKG to obtain the result Λ=f of the original problem Φ.(5)
ResultVerify (Λ;Γ). On input of the result Λ of Φ and the proof Γ, the client verifies the correctness of Λ by (17).


## 5.1. Attempt One

Since the efficiency of 2D-DCT is mainly limited by the calculation of three matrix multiplication, we naturally think that the key of design is to realize the outsourcing ofA·fi,j·AT, where i,j∈1,N/K. Several different outsourcing protocols for the multiplication of two matrices have been proposed [40]–[42]. Therefore, a direct assumption is to first use these protocols to outsource A·fi,j to obtain the product S and then outsource S·AT, thereby acquiring calculation result of A·fi,j·AT.Apart from other flaws of the protocol, the most obvious drawback of the protocol is the need for two rounds of communication between the cloud and the client. This will bring not only multiplied communication overhead to the client but also multiplied computing overhead for the client, because the client needs to perform independent encryption, decryption, and result verification operations for each round of outsourcing. As a result, the existence of two-round communication will make it difficult for the outsourcing protocol to meet the requirements of high efficiency.


## 5.2. Attempt Two

We attempt to implement an efficient outsourcing protocol that required only one round of communication by using the privacy-preserving matrix multiplication as adopted in [40, 43, 44]. First, to protect the privacy of input and output data, the private key matrices P1,P2,⋯,P4N2/K2∈RK×K are locally generated by the client as follows:(7)Pni,j=piδπni,j,n∈1,4N2K2,where pi is a random number and πn· is a permutation function that maps an original index i to its permuted index. Besides, δi,j is the Kronecker delta function given by(8)δi,j=1,i=j,0,i≠j.We emphasize that the inverse ofPn can be accessed simply by(9)Pn−1i,j=1Piδπn−1i,j.Afterwards, for any blockA·fi,j·AT of the matrix F in (5), the client encrypts the matrices A, fi,j, and AT as(10)EA=P4N/Ki−1+4j−3·A·P4N/Ki−1+4j−2−1,Efi,j=P4N/Ki−1+4j−2·fi,j·P4N/Ki−1+4j−1,EAT=P4N/Ki−1+4j−1−1·AT·P4N/Ki−1+4j.The encrypted matricesEA, Efi,j, and EAT are then sent to the cloud, who perform(11)EFi,j=EA·Efi,j·EAT=P4N/Ki−1+4j−3·Fi,j·P4N/Ki−1+4j.Finally, to decrypt the returnedEFi,j, the client only needs to calculate(12)Fi,j=P4N/Ki−1+4j−3−1·EFi,j·P4N/Ki−1+4j−1.This design avoids the trouble of multiround communication existing in Attempt One and seems to be feasible. However, this is not the case, because the complex key management severely slows down the efficiency of the protocol. In Attempt Two, for an original data matrix with dimensionN×N, the client needs to generate 4N2/K2 mutually independent key matrices with size K×K for encryption. Meanwhile, 2N2/K2 key matrices in them need to be saved in order to be invoked during decryption. Besides, we emphasize that in 2D-DCT and 2D-IDCT operations, only f and F are private in the input and output data, while A and AT are public and can be generated independently by anyone. Therefore, an efficient protocol should manage to encrypt only f or F on input.


## 5.3. Formal Protocol

### 5.3.1. Outsourcing Protocol for 2D-DCT

We now present the formal protocol, which solves the flaws of Attempt One and Attempt Two well, i.e., not only requires only one round of communication but also greatly simplifies the key management workload.First, in terms of privacy protection, we adopted the privacy-preserving matrix addition as discussed in [26, 41, 45]. The client generates two random vectors u and v with size N×1 as the private key. To protect the privacy information in the original two-dimensional signal, the client encrypts the matrix f as follows:(13)Ef=f+u·vT.After the encryption of (13), any block fi,j in the matrix f satisfies(14)Efi,j=fi,j+ui·vjT,where vector ui∈RK×1 is a vector consisting of the Ki−K+1th to Kith elements of vector u and vector vjT∈R1×K is a vector consisting of the Kj−K+1th to Kjth elements of vector vT.Afterwards, the encrypted matrixEf is sent to the cloud who perform K×K 2D-DCT as(15)EFi,j=A·Efi,j·AT=A·fi,j+ui·vjT·AT=A·fi,j·AT+A·ui·vjT·AT=Fi,j+A·ui·vjT·AT.We emphasize that matricesA and AT are not private and can be generated independently by the cloud itself by (3). The calculated results EFi,j∀i,j∈1,N/K are then combined into matrix EF and returned to the client, who uses the private key vectors u and v to decrypt EF efficiently through(16)Fi,j=EFi,j−A·ui·vjT·AT.Finally, the client quickly verifies the correctness ofFi,j by the inference of Parseval’s theorem, i.e.,(17)∑m=1K∑n=1Kfi,j2m,n=∑m=1K∑n=1KFi,j2m,n.If (17) holds within the allowable error range, block Fi,j passes the verification. As long as all the blocks in the matrix Fpass the verification, the client accepts the calculation result F; otherwise, the client rejects F.We summarize the outsourcing protocol for 2D-DCT as follows.(1)
KeyGen (1λ). On input of a security parameter λ, the client generates the private key KG=u,v.(2)
ProbEnc (Φ;KG). On input of the original problem Φ=f and the key KG, the client performs (13) to encrypt Φ to generate the encrypted problem ΦKG=Ef and then sends ΦKG to the cloud.(3)
ProbSolve (ΦKG). On input of the encrypted problem ΦKG, the cloud solves ΦKG by (15). Then, the cloud returns the result ΛKG=EF back, together with an empty proof Γ.(4)
ResultDec (ΛKG;KG). On input of the result ΛKG of ΦKG and the key KG, the client performs (16) to decrypt ΛKG to obtain the result Λ=F of the original problem Φ.(5)
ResultVerify (Λ;Γ). On input of the result Λ of Φ and the proof Γ, the client verifies the correctness of Λ by (17).Compared with Attempt One and Attempt Two, on the one hand, the formal protocol requires only one round of communication. On the other hand, the difficulty of key management is greatly reduced because the key is just two vectors of lengthN. Meanwhile, only the private matrix f is encrypted on input, eliminating the encryption and transmission of A and AT, which further improves the efficiency of outsourcing. Besides, the original signal matrix f is encrypted in its entirety, making the encryption process more efficient and concise compared with block encryption. However, the integral encryption operation does not affect the block flexibility of the cloud, i.e., the cloud can still perform 2D-DCT of any block size based on negotiation with the client.


### 5.3.2. Outsourcing Protocol for 2D-IDCT

The outsourcing protocol of 2D-IDCT is similar to that of 2D-DCT. First, the client also generates vectorsuand v locally as the private key. To protect the privacy of the input privacy matrix F, the client performs(18)EF=F+u·vT.Afterwards, the encrypted matrixEF is sent to the cloud who perform K×K 2D-IDCT as(19)Efi,j=AT·EFi,j·A.The calculated resultEf is then returned to the client who uses the private key to decrypt Ef efficiently through(20)fi,j=Efi,j−AT·ui·vjT·A.Finally, the correctness of resultingf is also verified by equation (17). We summarize the outsourcing protocol for 2D-IDCT as follows.(1)
KeyGen (1λ). On input of a security parameter λ, the client generates the private key KG=u,v.(2)
ProbEnc (Φ;KG). On input of the original problem Φ=F and the key KG, the client performs (18) to encrypt Φ to generate the encrypted problem ΦKG=EF and then sends ΦKG to the cloud.(3)
ProbSolve (ΦKG). On input of the encrypted problem ΦKG, the cloud solves ΦKG by (19). Then, the cloud returns the result ΛKG=Ef back, together with an empty proof Γ.(4)
ResultDec (ΛKG;KG). On input of the result ΛKG of ΦKG and the key KG, the client performs (20) to decrypt ΛKG to obtain the result Λ=f of the original problem Φ.(5)
ResultVerify (Λ;Γ). On input of the result Λ of Φ and the proof Γ, the client verifies the correctness of Λ by (17).


## 5.3.1. Outsourcing Protocol for 2D-DCT

We now present the formal protocol, which solves the flaws of Attempt One and Attempt Two well, i.e., not only requires only one round of communication but also greatly simplifies the key management workload.First, in terms of privacy protection, we adopted the privacy-preserving matrix addition as discussed in [26, 41, 45]. The client generates two random vectors u and v with size N×1 as the private key. To protect the privacy information in the original two-dimensional signal, the client encrypts the matrix f as follows:(13)Ef=f+u·vT.After the encryption of (13), any block fi,j in the matrix f satisfies(14)Efi,j=fi,j+ui·vjT,where vector ui∈RK×1 is a vector consisting of the Ki−K+1th to Kith elements of vector u and vector vjT∈R1×K is a vector consisting of the Kj−K+1th to Kjth elements of vector vT.Afterwards, the encrypted matrixEf is sent to the cloud who perform K×K 2D-DCT as(15)EFi,j=A·Efi,j·AT=A·fi,j+ui·vjT·AT=A·fi,j·AT+A·ui·vjT·AT=Fi,j+A·ui·vjT·AT.We emphasize that matricesA and AT are not private and can be generated independently by the cloud itself by (3). The calculated results EFi,j∀i,j∈1,N/K are then combined into matrix EF and returned to the client, who uses the private key vectors u and v to decrypt EF efficiently through(16)Fi,j=EFi,j−A·ui·vjT·AT.Finally, the client quickly verifies the correctness ofFi,j by the inference of Parseval’s theorem, i.e.,(17)∑m=1K∑n=1Kfi,j2m,n=∑m=1K∑n=1KFi,j2m,n.If (17) holds within the allowable error range, block Fi,j passes the verification. As long as all the blocks in the matrix Fpass the verification, the client accepts the calculation result F; otherwise, the client rejects F.We summarize the outsourcing protocol for 2D-DCT as follows.(1)
KeyGen (1λ). On input of a security parameter λ, the client generates the private key KG=u,v.(2)
ProbEnc (Φ;KG). On input of the original problem Φ=f and the key KG, the client performs (13) to encrypt Φ to generate the encrypted problem ΦKG=Ef and then sends ΦKG to the cloud.(3)
ProbSolve (ΦKG). On input of the encrypted problem ΦKG, the cloud solves ΦKG by (15). Then, the cloud returns the result ΛKG=EF back, together with an empty proof Γ.(4)
ResultDec (ΛKG;KG). On input of the result ΛKG of ΦKG and the key KG, the client performs (16) to decrypt ΛKG to obtain the result Λ=F of the original problem Φ.(5)
ResultVerify (Λ;Γ). On input of the result Λ of Φ and the proof Γ, the client verifies the correctness of Λ by (17).Compared with Attempt One and Attempt Two, on the one hand, the formal protocol requires only one round of communication. On the other hand, the difficulty of key management is greatly reduced because the key is just two vectors of lengthN. Meanwhile, only the private matrix f is encrypted on input, eliminating the encryption and transmission of A and AT, which further improves the efficiency of outsourcing. Besides, the original signal matrix f is encrypted in its entirety, making the encryption process more efficient and concise compared with block encryption. However, the integral encryption operation does not affect the block flexibility of the cloud, i.e., the cloud can still perform 2D-DCT of any block size based on negotiation with the client.


## 5.3.2. Outsourcing Protocol for 2D-IDCT

The outsourcing protocol of 2D-IDCT is similar to that of 2D-DCT. First, the client also generates vectorsuand v locally as the private key. To protect the privacy of the input privacy matrix F, the client performs(18)EF=F+u·vT.Afterwards, the encrypted matrixEF is sent to the cloud who perform K×K 2D-IDCT as(19)Efi,j=AT·EFi,j·A.The calculated resultEf is then returned to the client who uses the private key to decrypt Ef efficiently through(20)fi,j=Efi,j−AT·ui·vjT·A.Finally, the correctness of resultingf is also verified by equation (17). We summarize the outsourcing protocol for 2D-IDCT as follows.(1)
KeyGen (1λ). On input of a security parameter λ, the client generates the private key KG=u,v.(2)
ProbEnc (Φ;KG). On input of the original problem Φ=F and the key KG, the client performs (18) to encrypt Φ to generate the encrypted problem ΦKG=EF and then sends ΦKG to the cloud.(3)
ProbSolve (ΦKG). On input of the encrypted problem ΦKG, the cloud solves ΦKG by (19). Then, the cloud returns the result ΛKG=Ef back, together with an empty proof Γ.(4)
ResultDec (ΛKG;KG). On input of the result ΛKG of ΦKG and the key KG, the client performs (20) to decrypt ΛKG to obtain the result Λ=f of the original problem Φ.(5)
ResultVerify (Λ;Γ). On input of the result Λ of Φ and the proof Γ, the client verifies the correctness of Λ by (17).


## 6. Protocol Construction

### 6.1. Privacy Analysis

For the outsourcing of 2D-DCT, the input privacy matrix isf and the output privacy matrix is F. In the proposed protocol, f is encrypted with two key vectors uand v by the privacy-preserving matrix addition. According to the theoretical proof in [26], the resulting matrix Ef is computationally indistinguishable in value from a random matrix R. That is, any probabilistic polynomial time distinguisher cannot distinguish the element Efi,j of Ef from the element Ri,j of R for any ∀i,j∈1,N, except with negligible success probability. The success probability of the distinguisher decreases linearly with the expansion of the value range of the key vector. Therefore, the cloud cannot access any private plaintext contained in f from Ef, thereby successfully protecting input privacy. Subsequently, the cloud performs block 2D-DCT of K×K on the encrypted matrix Ef, resulting in EF. F is the result of performing K×K 2D-DCT operation on f. Since the polynomial adversary cannot find any valuable association between Ef and f in terms of value, the association between EF and F is believed to be untraceable, i.e., the output privacy is also successfully protected.For the outsourcing of 2D-IDCT, the input privacy matrix isF and the output privacy matrix is f. Based on the consistency of the implementation approach between 2D-IDCT outsourcing and 2D-DCT outsourcing, we conclude that the privacy of input and output is also well protected in the outsourcing of 2D-IDCT.


### 6.2. Verification Analysis

In terms of result verification, two effects should be achieved. On the one hand, the correct results returned from the cloud should be accepted by the client with a probability close to 1. On the other hand, the erroneous results returned from the cloud should be rejected by the client with a probability close to 1.In the proposed outsourcing protocol for 2D-DCT and 2D-IDCT, the returned results are all verified by the inference of Parseval’s theorem as shown in (17). On the one hand, any correct 2D-DCT or 2D-IDCT transformation result obviously satisfies the inference of Parseval’s theorem, thus reaching the first required effect. On the other hand, we emphasize that the cloud is unable to intentionally generate an erroneous result satisfying (17), because the cloud cannot even obtain the plaintext of the input privacy matrix and therefore cannot know the correct sum of squares of elements. In addition, we discuss the situation where the cloud returns an erroneous result at random, but it just meets (17). In this case, the sum of squares of the elements in the erroneous result matrix happens to be correct. For a grayscale block image with K×K pixels, since the grayscale value of each pixel is taken from the interval [0, 255], the possible values of the sum of squares of elements are in the interval [0,K2·2552]. As long as K is not too small, the probability that the sum of squares of the elements in a randomly selected result matrix happens to be equal to the correct value is minimal. Moreover, the cloud will not try to avoid verification at any cost, because the motivation for the cloud to return erroneous results is considered to be cost-saving. Therefore, we believe that the proposed protocol also conforms to the second required effect.


### 6.3. Efficiency Analysis

In this section, we conduct a theoretical evaluation for the efficiency performance of the protocol. The evaluation is carried out from three parts: client-side overhead, cloud-side overhead, and communication overhead. Since the efficiency of 2D-DCT outsourcing is consistent with that of 2D-IDCT outsourcing, we take the outsourcing of 2D-DCT as an example for evaluation.


#### 6.3.1. Client-Side Overhead

First, the client takes timeO2N on generating the private key vectors u and v and ON on encrypting the two-dimensional signal matrix f. Then, the client performs (16) to decrypt the result EF returned by the cloud, which takes time O2+1/KN2. Finally, the client verifies the decrypted result by (17), which takes time O2N2. In general, the client needs to spend a total of O4+1/KN2+3N time on the outsourcing of 2D-DCT.


#### 6.3.2. Cloud-Side Overhead

The only operation required in the cloud is to perform block 2D-DCT operation ofK×K on the encrypted matrix Ef, which takes time O2KN2.


#### 6.3.3. Communication Overhead

During the outsourcing process, only the matrixf and matrix F need to be transmitted between the client and the cloud; thus, the communication overhead is quite small.Note that the computation overhead in the cloud is the same as it would be for the client to perform the 2D-DCT locally. Based on the above analysis, we conclude that as long asK≥3, the client can get computing savings from outsourcing. Moreover, the larger the value of K, the more cost savings the client can achieve. For the most common case of K=8, the client can reduce the computing overhead to about one quarter by outsourcing.


## 6.1. Privacy Analysis

For the outsourcing of 2D-DCT, the input privacy matrix isf and the output privacy matrix is F. In the proposed protocol, f is encrypted with two key vectors uand v by the privacy-preserving matrix addition. According to the theoretical proof in [26], the resulting matrix Ef is computationally indistinguishable in value from a random matrix R. That is, any probabilistic polynomial time distinguisher cannot distinguish the element Efi,j of Ef from the element Ri,j of R for any ∀i,j∈1,N, except with negligible success probability. The success probability of the distinguisher decreases linearly with the expansion of the value range of the key vector. Therefore, the cloud cannot access any private plaintext contained in f from Ef, thereby successfully protecting input privacy. Subsequently, the cloud performs block 2D-DCT of K×K on the encrypted matrix Ef, resulting in EF. F is the result of performing K×K 2D-DCT operation on f. Since the polynomial adversary cannot find any valuable association between Ef and f in terms of value, the association between EF and F is believed to be untraceable, i.e., the output privacy is also successfully protected.For the outsourcing of 2D-IDCT, the input privacy matrix isF and the output privacy matrix is f. Based on the consistency of the implementation approach between 2D-IDCT outsourcing and 2D-DCT outsourcing, we conclude that the privacy of input and output is also well protected in the outsourcing of 2D-IDCT.


## 6.2. Verification Analysis

In terms of result verification, two effects should be achieved. On the one hand, the correct results returned from the cloud should be accepted by the client with a probability close to 1. On the other hand, the erroneous results returned from the cloud should be rejected by the client with a probability close to 1.In the proposed outsourcing protocol for 2D-DCT and 2D-IDCT, the returned results are all verified by the inference of Parseval’s theorem as shown in (17). On the one hand, any correct 2D-DCT or 2D-IDCT transformation result obviously satisfies the inference of Parseval’s theorem, thus reaching the first required effect. On the other hand, we emphasize that the cloud is unable to intentionally generate an erroneous result satisfying (17), because the cloud cannot even obtain the plaintext of the input privacy matrix and therefore cannot know the correct sum of squares of elements. In addition, we discuss the situation where the cloud returns an erroneous result at random, but it just meets (17). In this case, the sum of squares of the elements in the erroneous result matrix happens to be correct. For a grayscale block image with K×K pixels, since the grayscale value of each pixel is taken from the interval [0, 255], the possible values of the sum of squares of elements are in the interval [0,K2·2552]. As long as K is not too small, the probability that the sum of squares of the elements in a randomly selected result matrix happens to be equal to the correct value is minimal. Moreover, the cloud will not try to avoid verification at any cost, because the motivation for the cloud to return erroneous results is considered to be cost-saving. Therefore, we believe that the proposed protocol also conforms to the second required effect.


## 6.3. Efficiency Analysis

In this section, we conduct a theoretical evaluation for the efficiency performance of the protocol. The evaluation is carried out from three parts: client-side overhead, cloud-side overhead, and communication overhead. Since the efficiency of 2D-DCT outsourcing is consistent with that of 2D-IDCT outsourcing, we take the outsourcing of 2D-DCT as an example for evaluation.


### 6.3.1. Client-Side Overhead

First, the client takes timeO2N on generating the private key vectors u and v and ON on encrypting the two-dimensional signal matrix f. Then, the client performs (16) to decrypt the result EF returned by the cloud, which takes time O2+1/KN2. Finally, the client verifies the decrypted result by (17), which takes time O2N2. In general, the client needs to spend a total of O4+1/KN2+3N time on the outsourcing of 2D-DCT.


### 6.3.2. Cloud-Side Overhead

The only operation required in the cloud is to perform block 2D-DCT operation ofK×K on the encrypted matrix Ef, which takes time O2KN2.


### 6.3.3. Communication Overhead

During the outsourcing process, only the matrixf and matrix F need to be transmitted between the client and the cloud; thus, the communication overhead is quite small.Note that the computation overhead in the cloud is the same as it would be for the client to perform the 2D-DCT locally. Based on the above analysis, we conclude that as long asK≥3, the client can get computing savings from outsourcing. Moreover, the larger the value of K, the more cost savings the client can achieve. For the most common case of K=8, the client can reduce the computing overhead to about one quarter by outsourcing.


## 6.3.1. Client-Side Overhead

First, the client takes timeO2N on generating the private key vectors u and v and ON on encrypting the two-dimensional signal matrix f. Then, the client performs (16) to decrypt the result EF returned by the cloud, which takes time O2+1/KN2. Finally, the client verifies the decrypted result by (17), which takes time O2N2. In general, the client needs to spend a total of O4+1/KN2+3N time on the outsourcing of 2D-DCT.


## 6.3.2. Cloud-Side Overhead

The only operation required in the cloud is to perform block 2D-DCT operation ofK×K on the encrypted matrix Ef, which takes time O2KN2.


## 6.3.3. Communication Overhead

During the outsourcing process, only the matrixf and matrix F need to be transmitted between the client and the cloud; thus, the communication overhead is quite small.Note that the computation overhead in the cloud is the same as it would be for the client to perform the 2D-DCT locally. Based on the above analysis, we conclude that as long asK≥3, the client can get computing savings from outsourcing. Moreover, the larger the value of K, the more cost savings the client can achieve. For the most common case of K=8, the client can reduce the computing overhead to about one quarter by outsourcing.


## 7. Simulation Experiment

In this section, we carry out a simulation experiment to further confirm the efficiency of the proposed protocol. The experiment was performed using MATLAB 2016b on a laptop with an Intel Core i5 processor and 8 GB RAM simulating a client. We simulate the situations of users performing8×8 2D-DCT, fast 8×8 2D-DCT, and computing outsourcing, respectively. The fast 2D-DCT algorithm used for comparison here is proposed by Cho and Lee in [13]. We, respectively, calculated the time required for the client to perform 2D-DCT operation on a two-dimensional signal of different sizes in the three cases. We also assume that the communication between the client and the cloud can be achieved in a negligible time, so the experiment does not count the time spent on communication. The experimental results are shown in Table 1, which is the average value of 10 repeated experiments. The meaning of the parameters in Table 1 is as follows.(i)
t2D−DCT represents the time taken by the client to perform block 2D-DCT of 8×8 using the definition method(ii)
tfast2D−DCT represents the time taken by the client to perform block 2D-DCT of 8×8 using the fast algorithm method(iii)
toutsourcing represents the time taken by the client to perform block 2D-DCT of 8×8 using the outsourcing method(iv)
t2D−DCT/tfast2D−DCT represents the performance gain to the client using the fast algorithm method compared to the definition method(v)
t2D−DCT/toutsourcing represents the performance gain to the client using the outsourcing method compared to the definition method(vi)
tfast2D−DCT/toutsourcing represents the performance gain to the client using the outsourcing method compared to the fast algorithm methodTable 1
Experimental results.
SizeNt2D−DCT (sec)tfast2D−DCT (sec)toutsourcing (sec)t2D−DCTtfast2D−DCTt2D−DCTtoutsourcingtfast2D−DCTtoutsourcing2560.55300.20700.11102.67154.98201.86495121.90760.79790.43012.39084.43521.855110248.78052.87351.70913.05575.13751.6813204833.057711.93146.95592.77064.75251.71534096127.890947.528828.09072.69084.55281.6920As can be seen from Table1, on the one hand, compared with the definition method, regardless of the value of size N, the outsourcing protocol can bring the client a performance gain of more than 4.43 times, which is consistent with the result of previous theoretical analysis. On the other hand, even compared with the fast 2D-DCT algorithm, outsourcing can still bring more than 1.68 times of performance gain to the client, which further demonstrates the outstanding efficiency of the outsourcing method.


## 8. Conclusions

In this paper, we speed up 2D-DCT and 2D-IDCT from the point of view of computing outsourcing rather than algorithm optimization. Based on the privacy-preserving matrix addition, we realize the privacy protection of input and output data. Meanwhile, the inference of Parseval’s theorem is used to verify the returned results. Furthermore, compared with the two possible solutions Attempt One and Attempt Two, the proposed formal protocol’s features of one-round communication and simple key management guarantee the protocol’s efficiency performance. The proposed outsourcing protocol is confirmed by theoretical analysis to solve three key challenges in computing outsourcing. Experimental results show that outsourcing is even more efficient than the fast 2D-DCT and 2D-IDCT algorithms. Thus, the adoption of the proposed outsourcing protocol could indeed be an excellent alternative for speeding up 2D-DCT and 2D-IDCT operations. In the future, we will strive to achieve efficient and secure outsourcing of other signal processing tools, such as DWT and NTT.



---

*Source: 8892838-2020-07-27.xml*