# Publicly Verifiable Outsourcing Computation for QR Decomposition Based on Blockchain

Authors: Huimin Wang; Dong Zheng; Qinglan Zhao
Journal: Security and Communication Networks
 (2021)

---

## Abstract

In the Big Data Era, outsourcing computation has become increasingly significant as it supplies computation resources for clients with limited resources. However, there are still many security challenges such as payment fairness, privacy protection, and verification. In this paper, we propose a secure publicly verifiable outsourcing computation scheme for the large-scale matrix QR decomposition. In the proposed scheme, client can pay for outsourcing services through blockchain-based payment system which achieves the payment fairness. Moreover, to protect privacy, both permutation matrix and block diagonal matrix are applied in encryption process. Meanwhile, to achieve the public verification, the computational complexity is reduced by using the matrix digest technology. It is worth mentioning that our scheme is provable and secure under the co-CDH assumption.


---

## Body

## 1. Introduction

Cloud computing, a new computing technology and service concept, has appeared in the public’s vision and serves customers in a pay-per-use manner [1–3]. It has promoted the development of the emerging fields such as smart medical systems in recent years.Outsourcing computation, as one of the basic applications of cloud computing, can reduce significantly the clients’ computational burden [4]. There are two parts, including payment and computation, in outsourcing scheme. For payment part, it often requires online payment and relies on trusted third party such as bank. To realize secure and fair payment of outsourcing services without relying on any third party, fair payment framework based on blockchain has been used for outsourcing services in cloud computing [5]. For computation part, service requester submits the data-to-service provider, which might get service requester’s privacy from the data. Therefore, there exist many security challenges during the outsourcing process.About the protection of client privacy, computing tasks authorized to cloud server involve some important sensitive information frequently, such as core technology of a company and patient health records. So, it is important for users to conceal their data information before uploaded to the cloud server. The previous works have attempted to protect the confidentiality of the data. For example, full homomorphic encryption [6], a cryptographic technique, can allow service provider to perform valid and meaningful operations on ciphertext. However, the existing schemes based on FHE suffer from high computation complexity.Moreover, the result verification is vital as well. Since the process of cloud computing is not transparent to the public who will upload their data, the public should detect in time whether there are any errors in outsourcing result. There may be many reasons to produce an invalid and wrong result, such as hardware malfunction, software bugs, or malicious hackers. Furthermore, a semihonest cloud server [7] might work dishonestly or even cut down calculation steps due to huge benefits.Considering financial expenses, an outsourcing computating scheme should be highly efficient. That is, the user’s computation in the outsourced process is far less than the computation of their task directly. Otherwise, the outsourcing will get meaningless for the client.Matrix computation has many applications in scientific and engineering fields. The outsourcing matrix computation also involves the above security challenges. We research on secure outsourcing matrix QR decomposition computation and propose a publicly verifiable scheme based on blockchain. The system consists of two parts: blockchain-based payment and publicly verifiable computation. In this paper, we focus on designing publicly verifiable computation scheme and we refer the reader to reference [5] to know more about blockchain-based payment.


### 1.1. Contributions

The contribution of this paper can be described from the following three points:(i)
We multiply a sparse block diagonal matrix with the original matrix to protect the client’s privacy. The computational complexity isOn2 in the encryption process.(ii)
The scheme provides public verification. To reduce the workload of the verifier, we use matrix digest technique which transforms any matrix into a specific vector with chosen parameter in the verification of QR decomposition.(iii)
We show the soundness of the scheme through detailed theoretical analysis, including correctness, security, and efficiency. It is proved that the scheme achieves secure underco-CDH difficulty assumption.


### 1.2. Related Work

Looking back on the development of outsourcing computation in the past decades, many schemes have been designed for different scientific computations. Atallah et al. [8] proposed the concept of the scientific computing outsourcing firstly. To protect privacy of clients, researchers have devoted to design the secure outsourcing schemes [9–14]. Salinas et al. [9] mentioned a privacy-preserving transformation method by adding random matrix to original matrix. For the verifiability of the outsourcing results, Golle and Mironov [15] firstly realized this goal in their scheme. Then, a verifiable scheme about any random function was designed by Gentry [6] which provided the formal concept of verifiable computing. Banabbas et al. [16] put forward to a verifiable scheme for high-degree polynomial functions.Nevertheless, in many applications, verification needs to be public. In other words, any customer can verify it. Recently, some experts turned their attention to public verifiable computation. Fioreand Gennaro [17] allowed service requester to verify the result with a noninteractive evidence. Meanwhile, Parno et al. [18] gave the concept of the correctness and security which had established a connection between public verification computation and attribute-based encryption ABE. In addition, Fiore and Gennaro [17] also designed the matrix multiplication outsourcing scheme according to Yao’s Garbled Circuits [19]. Different from traditional scheme [11], the scheme [20] has achieved that all clients can share a common matrix M to perform matrix multiplication, which did not protect the security of the original matrix.Jia et al. [12] took the privacy protection into account, where the matrix can be arbitrary. Li et al. [21] improved its efficiency compared to previous work and achieved the public verification. Zhang et al. [13] reduced the computing overhead in the verification process hugely. The scheme in [22] not only achieved the public verification but also protected privacy information of original data, where matrix digest was utilized to reduce the overhead of key generation and cloud computing.The above results [12, 17, 20–22] are about publicly verifiable solutions for matrix multiplication. However, there is no publicly verifiable solution about matrix decomposition. Matrix decomposition, as one of the basic matrix operations, has many application scenarios [23–26]. Luo et al. [27] had designed a secure algorithm for QR decompositions without the public verification achieved. We propose a scheme which achieves the promising public verification under the amortized model for QR decomposition of large-scale matrices. To protect privacy, sparse matrices which cut down the computational complexity from On3 to On2 are applied during encryption.


### 1.3. Organization

In Section2, it introduces related definitions of verifiable computing and significant mathematical knowledge. Section 3 details the proposed scheme for the publicly verifiable computation of the QR decomposition. The correctness, security, and efficiency analysis are shown in Section 4. At last, it ends up with our conclusion in Section 5.


## 1.1. Contributions

The contribution of this paper can be described from the following three points:(i)
We multiply a sparse block diagonal matrix with the original matrix to protect the client’s privacy. The computational complexity isOn2 in the encryption process.(ii)
The scheme provides public verification. To reduce the workload of the verifier, we use matrix digest technique which transforms any matrix into a specific vector with chosen parameter in the verification of QR decomposition.(iii)
We show the soundness of the scheme through detailed theoretical analysis, including correctness, security, and efficiency. It is proved that the scheme achieves secure underco-CDH difficulty assumption.


## 1.2. Related Work

Looking back on the development of outsourcing computation in the past decades, many schemes have been designed for different scientific computations. Atallah et al. [8] proposed the concept of the scientific computing outsourcing firstly. To protect privacy of clients, researchers have devoted to design the secure outsourcing schemes [9–14]. Salinas et al. [9] mentioned a privacy-preserving transformation method by adding random matrix to original matrix. For the verifiability of the outsourcing results, Golle and Mironov [15] firstly realized this goal in their scheme. Then, a verifiable scheme about any random function was designed by Gentry [6] which provided the formal concept of verifiable computing. Banabbas et al. [16] put forward to a verifiable scheme for high-degree polynomial functions.Nevertheless, in many applications, verification needs to be public. In other words, any customer can verify it. Recently, some experts turned their attention to public verifiable computation. Fioreand Gennaro [17] allowed service requester to verify the result with a noninteractive evidence. Meanwhile, Parno et al. [18] gave the concept of the correctness and security which had established a connection between public verification computation and attribute-based encryption ABE. In addition, Fiore and Gennaro [17] also designed the matrix multiplication outsourcing scheme according to Yao’s Garbled Circuits [19]. Different from traditional scheme [11], the scheme [20] has achieved that all clients can share a common matrix M to perform matrix multiplication, which did not protect the security of the original matrix.Jia et al. [12] took the privacy protection into account, where the matrix can be arbitrary. Li et al. [21] improved its efficiency compared to previous work and achieved the public verification. Zhang et al. [13] reduced the computing overhead in the verification process hugely. The scheme in [22] not only achieved the public verification but also protected privacy information of original data, where matrix digest was utilized to reduce the overhead of key generation and cloud computing.The above results [12, 17, 20–22] are about publicly verifiable solutions for matrix multiplication. However, there is no publicly verifiable solution about matrix decomposition. Matrix decomposition, as one of the basic matrix operations, has many application scenarios [23–26]. Luo et al. [27] had designed a secure algorithm for QR decompositions without the public verification achieved. We propose a scheme which achieves the promising public verification under the amortized model for QR decomposition of large-scale matrices. To protect privacy, sparse matrices which cut down the computational complexity from On3 to On2 are applied during encryption.


## 1.3. Organization

In Section2, it introduces related definitions of verifiable computing and significant mathematical knowledge. Section 3 details the proposed scheme for the publicly verifiable computation of the QR decomposition. The correctness, security, and efficiency analysis are shown in Section 4. At last, it ends up with our conclusion in Section 5.


## 2. Preliminaries

In this part, we introduce some related definitions, mathematical knowledge, and important techniques.


### 2.1. Publicly Verifiable Computation

As mentioned by Gennaro [28], a public verifiable computation scheme VC not only allows a client to outsource his computating task but also states that the outsourcing result is correct and verifiable. The formal definitions of these properties for public verifiable computation are presented in [22, 28]. For the sake of integrity, we give some related definitions before introducing our scheme.Definition 1.
A outsourcing schemeVC consists of the following five subalgorithms:(i)
KeyGen1λ,ℱ⟶ (SK, PK):Given the random selected parameterλ, a public key PK is produced to protect the function ℱ. Simultaneously, a private key SK saved by the service requester secretly is generated by this algorithm.(ii)
ProbGenSKx⟶τx,σx:The client performs the encryption together with theSK and gets a decoding value τx stored confidentially, where the input x of function is encoded into a encrypted result σx.(iii)
ComputePKσx⟶σy:According to thePK and the encrypted σx, the outsourcing server provider produces a blinded output σy.(iv)
VerifySKτx,σy⟶y∪⊥:Based onσy and τx, if σy of function ℱ is correct, it outputs y. Otherwise, it outputs the symbol ⊥.(v)
SolveSKτx,σy⟶y:The algorithm decodesσy to generate the final result y=ℱx with SK and τx.
Next, we focus on these properties in publicly verifiable computation schemeVC, including correctness, security, privacy, and efficiency.Definition 2.
(correctness). For a functionℱ, we say the verifiable outsourcing scheme VC is correct if the key generation algorithm generates keys PK,SK←KeyGenℱ,1λ and satisfies the following condition: ∀x∈Domainℱ, y=ℱx←VerifySKτx,σy if σx,τx←ProbGenSKx and σy←ComputePK.The formalized definition of security of a verifiable computation outsourcing schemeVC is introduced, where a malicious server cannot persuade the verifier to output a invalid result y^ according to the function ℱ and input x, e.g., ℱx≠y^.Now, we abstract this objective fact with an experiment which is expressed as below.ExperienceExpAVerifyVC,ℱ,λ;Fori=1,…,l=polyλ;PK,SK←RKeyGenℱ,λ;xi←APK,x1,δ1,…,xi−1,δi−1;δi,τi←ProbGenSKxii,δ^y←APK,x1,δ1,…,xl,δly^←VerifySKτi,δ^y;Ify^=⊥ and y^≠ℱxi,output1,else0.Here,poly⋅ is defined as a polynomial.Given an oracle access, the adversary can produce the encryption of multiple problems. Considering a known input, the adversary can persuade the verifier to work smoothly, where any error is unable to be detected in the output.Definition 3.
(security). For a verifiable computation outsourcing schemeVC, the capability of an adversary A in the above experiment is defined as follows:(1)AdvAVerifyVC,ℱ,λ=PrExpAVerifyVC,ℱ,λ=1.
For a functionℱ, the scheme VC is secure if, for any adversary A running in probabilistic polynomial time (PPT),(2)AdvAVerifyVC,ℱ,λ≤negliλ,where negli⋅ is a negligible function of its input.If the outputs of the ProbGen algorithm over two different inputs are indistinguishable, we think aVC scheme is private. To define privacy of a verifiable computation scheme, we need an experiment. Given the public key PK for the scheme, the adversary A treats x0 and x1 as two inputs randomly. Then, he is given the encoded version of one of x0 and x1 and must guess which one was encoded. In the process, the oracle PubProbGenSKx calls ProbGenSKx to obtain (δx, τx) and returns only the public part δx. Now, the experiment is described below.ExperienceExpAPrivVC,ℱ,λ;PK,SK←RKeyGenℱ,λ;x0,x1←APubProbGenSK×PKδ0,τ0←ProbGenSKx0δ1,τ1←ProbGenSKx1y←R0,1;y^←APubProbGenSK×PK,x0,x1,δyIfy=y^, output1,else0.Definition 4.
(privacy). According to the above experiment, the ability of an adversaryA is defined as(3)AdvAPrivVC,ℱ,λ=PrExpAPrivVC,ℱ,λ=1−12.
A verifiable computation scheme is private if, for a functionℱ any adversary A running in PPT,(4)AdvAPrivVC,ℱ,λ≤negliλ,where negli⋅ is a negligible function of its input.Definition 5.
(efficiency). A verifiable schemeVC must be highly efficiency for the client. That is, the time for encryption and verification in the scheme should be shorter than the time to accomplish the computing task directly by itself.


### 2.2. Bilinear Pairings

The knowledge about bilinear pairings, in a verifiable computating schemeVC, will be introduced as follows.LetG1, G2, and GT be three multiplicative cyclic groups with the same large prime order p and g1 and g2 be generators of G1 and G2, respectively. A bilinear pairing is a map e:G1×G2⟶GT, which has the following three characteristics:(i)
Bilinearity: for anyα,β∈Zp and gα∈G1,hβ∈G2, the equation egα,hβ=eg,hαβ holds(ii)
Computability: there exist a valid algorithm for solvingeg,h for any g,h∈G1×G2(iii)
Nondegeneracy: for anyg∈G1, if, for all h∈G2, equation eg,h=1 is true, g=1, where g and h can be interchangedAccording to the above, the related definitions about computational assumptions can be described as follows.Definition 6 (co-CDH problem).
Giveng,gα∈G1, h,hβ∈G2, and α,β∈RFp∗, compute gαβ.Definition 7 (co-CDH assumption).
Giveng,gα∈G1 and h,hβ∈G2, for randomly selecting α,β∈RFp∗, if the probability to compute gαβ is negligible in any PPT, the co-computational Diffie–Hellman assumption holds in G1.


### 2.3. Matrix Digest Technique

As an one-way irreversible mapping process, matrix digest [22, 29] refers to transform an any matrix into a specific vector with a chosen parameter, which makes computational complexity reduce from On3 to On2. In fact, a matrix consists of some column vectors, in which a vector is also a special matrix. For example, a square matrix A^ can be denoted as A^=a⟶1,…,a⟶i,…,a⟶n, where a⟶i∈Zn×1 is a column vector. By this novel technique, we can transform the matrix A^ into the vector b⟶ by a row vector s⟶∈Z∗, where the vector b⟶=s⟶A^ is a matrix digest of A^.There are three properties of matrix digest:(i)
Deterministic: the matrix digest of a matrix will be determined uniquely by the known parameter vector,i.e., if s⟶ is chosen as the parameter, b⟶ must be unique for A^.(ii)
Computable: the result of matrix digest essentially is a vector and retains the computing ability of the initial matrix.(iii)
Irreversible: given a matrix digest, it is difficult for anyone to detect initial matrix and selected parameter. Furthermore, if the matrix digest and the parameter are known at the same time, the initial matrix cannot be obtained as well.


## 2.1. Publicly Verifiable Computation

As mentioned by Gennaro [28], a public verifiable computation scheme VC not only allows a client to outsource his computating task but also states that the outsourcing result is correct and verifiable. The formal definitions of these properties for public verifiable computation are presented in [22, 28]. For the sake of integrity, we give some related definitions before introducing our scheme.Definition 1.
A outsourcing schemeVC consists of the following five subalgorithms:(i)
KeyGen1λ,ℱ⟶ (SK, PK):Given the random selected parameterλ, a public key PK is produced to protect the function ℱ. Simultaneously, a private key SK saved by the service requester secretly is generated by this algorithm.(ii)
ProbGenSKx⟶τx,σx:The client performs the encryption together with theSK and gets a decoding value τx stored confidentially, where the input x of function is encoded into a encrypted result σx.(iii)
ComputePKσx⟶σy:According to thePK and the encrypted σx, the outsourcing server provider produces a blinded output σy.(iv)
VerifySKτx,σy⟶y∪⊥:Based onσy and τx, if σy of function ℱ is correct, it outputs y. Otherwise, it outputs the symbol ⊥.(v)
SolveSKτx,σy⟶y:The algorithm decodesσy to generate the final result y=ℱx with SK and τx.
Next, we focus on these properties in publicly verifiable computation schemeVC, including correctness, security, privacy, and efficiency.Definition 2.
(correctness). For a functionℱ, we say the verifiable outsourcing scheme VC is correct if the key generation algorithm generates keys PK,SK←KeyGenℱ,1λ and satisfies the following condition: ∀x∈Domainℱ, y=ℱx←VerifySKτx,σy if σx,τx←ProbGenSKx and σy←ComputePK.The formalized definition of security of a verifiable computation outsourcing schemeVC is introduced, where a malicious server cannot persuade the verifier to output a invalid result y^ according to the function ℱ and input x, e.g., ℱx≠y^.Now, we abstract this objective fact with an experiment which is expressed as below.ExperienceExpAVerifyVC,ℱ,λ;Fori=1,…,l=polyλ;PK,SK←RKeyGenℱ,λ;xi←APK,x1,δ1,…,xi−1,δi−1;δi,τi←ProbGenSKxii,δ^y←APK,x1,δ1,…,xl,δly^←VerifySKτi,δ^y;Ify^=⊥ and y^≠ℱxi,output1,else0.Here,poly⋅ is defined as a polynomial.Given an oracle access, the adversary can produce the encryption of multiple problems. Considering a known input, the adversary can persuade the verifier to work smoothly, where any error is unable to be detected in the output.Definition 3.
(security). For a verifiable computation outsourcing schemeVC, the capability of an adversary A in the above experiment is defined as follows:(1)AdvAVerifyVC,ℱ,λ=PrExpAVerifyVC,ℱ,λ=1.
For a functionℱ, the scheme VC is secure if, for any adversary A running in probabilistic polynomial time (PPT),(2)AdvAVerifyVC,ℱ,λ≤negliλ,where negli⋅ is a negligible function of its input.If the outputs of the ProbGen algorithm over two different inputs are indistinguishable, we think aVC scheme is private. To define privacy of a verifiable computation scheme, we need an experiment. Given the public key PK for the scheme, the adversary A treats x0 and x1 as two inputs randomly. Then, he is given the encoded version of one of x0 and x1 and must guess which one was encoded. In the process, the oracle PubProbGenSKx calls ProbGenSKx to obtain (δx, τx) and returns only the public part δx. Now, the experiment is described below.ExperienceExpAPrivVC,ℱ,λ;PK,SK←RKeyGenℱ,λ;x0,x1←APubProbGenSK×PKδ0,τ0←ProbGenSKx0δ1,τ1←ProbGenSKx1y←R0,1;y^←APubProbGenSK×PK,x0,x1,δyIfy=y^, output1,else0.Definition 4.
(privacy). According to the above experiment, the ability of an adversaryA is defined as(3)AdvAPrivVC,ℱ,λ=PrExpAPrivVC,ℱ,λ=1−12.
A verifiable computation scheme is private if, for a functionℱ any adversary A running in PPT,(4)AdvAPrivVC,ℱ,λ≤negliλ,where negli⋅ is a negligible function of its input.Definition 5.
(efficiency). A verifiable schemeVC must be highly efficiency for the client. That is, the time for encryption and verification in the scheme should be shorter than the time to accomplish the computing task directly by itself.


## 2.2. Bilinear Pairings

The knowledge about bilinear pairings, in a verifiable computating schemeVC, will be introduced as follows.LetG1, G2, and GT be three multiplicative cyclic groups with the same large prime order p and g1 and g2 be generators of G1 and G2, respectively. A bilinear pairing is a map e:G1×G2⟶GT, which has the following three characteristics:(i)
Bilinearity: for anyα,β∈Zp and gα∈G1,hβ∈G2, the equation egα,hβ=eg,hαβ holds(ii)
Computability: there exist a valid algorithm for solvingeg,h for any g,h∈G1×G2(iii)
Nondegeneracy: for anyg∈G1, if, for all h∈G2, equation eg,h=1 is true, g=1, where g and h can be interchangedAccording to the above, the related definitions about computational assumptions can be described as follows.Definition 6 (co-CDH problem).
Giveng,gα∈G1, h,hβ∈G2, and α,β∈RFp∗, compute gαβ.Definition 7 (co-CDH assumption).
Giveng,gα∈G1 and h,hβ∈G2, for randomly selecting α,β∈RFp∗, if the probability to compute gαβ is negligible in any PPT, the co-computational Diffie–Hellman assumption holds in G1.


## 2.3. Matrix Digest Technique

As an one-way irreversible mapping process, matrix digest [22, 29] refers to transform an any matrix into a specific vector with a chosen parameter, which makes computational complexity reduce from On3 to On2. In fact, a matrix consists of some column vectors, in which a vector is also a special matrix. For example, a square matrix A^ can be denoted as A^=a⟶1,…,a⟶i,…,a⟶n, where a⟶i∈Zn×1 is a column vector. By this novel technique, we can transform the matrix A^ into the vector b⟶ by a row vector s⟶∈Z∗, where the vector b⟶=s⟶A^ is a matrix digest of A^.There are three properties of matrix digest:(i)
Deterministic: the matrix digest of a matrix will be determined uniquely by the known parameter vector,i.e., if s⟶ is chosen as the parameter, b⟶ must be unique for A^.(ii)
Computable: the result of matrix digest essentially is a vector and retains the computing ability of the initial matrix.(iii)
Irreversible: given a matrix digest, it is difficult for anyone to detect initial matrix and selected parameter. Furthermore, if the matrix digest and the parameter are known at the same time, the initial matrix cannot be obtained as well.


## 3. The Proposed Scheme

### 3.1. Treat Model

The semihonest model introduced in [7] is an honest but curious one with an untrustworthy cloud server as the main adversary. It was also mentioned in [30], where participants in the outsourcing are required to honestly execute the designed scheme. With returning a correct result, semihonest cloud will try to recover sensitive information of the data. Our scheme is based on a semihonest cloud server and introduces an independent data center which is trustworthy.


### 3.2. System Model

Considering the public verification, we give a system model about outsourcing computation with the following five entities introduced, as shown in Figure1.(i)
Data centerDC: some keys are produced by DC. After initializing parameters, it generates the private keys and some public keys. Next, it takes advantage of the private key to generate the evaluation key for CS. Finally, it sends the private key to C and V over the secure channel.(ii)
ClientC: first of all, C should deposit enough money into ℬP for the cost of outsourcing services. Meanwhile, a request is sent to CS about solving a QR decomposition of the large-scale matrix. To protect privacy, C needs to encode the original matrix before the private matrix is uploaded to CS. Then, a verification key should be generated for V.(iii)
Cloud serverCS: like C, CS also needs to provide deposits to ℬP. As service provider, CS needs to perform QR decomposition of the encryption matrix and earn fees from C. Moreover, a proof sent to V together with computating results is generated by using the evaluation key. Finally, the result matrices will be transmitted to C. If C has no objection to the outsourcing result within a specified time, CS will provide a proof OSend to ℬP and get the corresponding fees. Otherwise, CS provides compensation to C.(iv)
VerifierV: any verifier can be regarded as V. Utilizing the verification key and the proof, V will examine the correctness of the outsourcing results.(v)
Blockchain paymentℬP: we take advantage of the payment system based on blockchain ℬP. After receiving deposit from C and CS, ℬP provides a proof OSstart for CS to confirm to start the outsourcing service.Figure 1
System model.


### 3.3. Process Description

The system model consists of two parts: blockchain-based payment system and publicly verifiable outsourcing computing system. In blockchain-based payment system,C needs to provide the corresponding deposits in ℬP as the cost of service before requesting CS to perform QR decomposition of large-scale matrix A^. Meanwhile, CS also deposits the compensation in ℬP as a guarantee for honest computing. If outsourcing result is correct, CS can obtain the corresponding service fees from ℬP. Otherwise, C informs ℬP to terminate the payment process, and CS will accept punishment and provide compensation to C. In this paper, we focus on designing publicly verifiable outsourcing computation for QR decomposition scheme called PVCMD-QR.PVCMD-QR can be divided into five phases including initialization phase, encryption phase, computation phase, verification phase, and decryption phase. To better understand this process, a flowchart is shown in Figure 2. Now, the specific process of the scheme is described below.Figure 2
A plan flowchart of the proposed scheme.In the initialization phase,DC runs the KeyGen algorithm. Here, it randomly generates three n-dimensional key vectors s⟶, l⟶, and k⟶ as the private key SK to produce the public key PK=PK1,PK2,PK3 and the evaluation key EK. s⟶ and l⟶ are delivered to C and V through the secure channel, respectively. In the encryption phase, ProbGen algorithm is executed. C encrypts a full rank privacy matrix A into A^=PAN, A∈Zpn×n, where block-diagonal upper triangular matrix N is constructed by C. Meanwhile, the verification key VK is generated by PK2, s⟶, and A^. Here, we make full use of the technique called matrix digest during the process of generating the VK in our scheme. By multiplying s⟶ and the encryption matrix A^ to obtain the vector b⟶, V uses PK2 and b⟶ to create VK. Then, A^ is uploaded to CS, and VK is provided to any V simultaneously. Then, the compute algorithm is implemented in the computation phase. CS receives A^ to perform QR decomposition. Using EK from DC, it generates a value v for V. After getting the orthogonal matrix Q^ and the upper triangular matrix R^, V begins to execute the verify algorithm by using both the key VK and the proof v in the verification phase. If the verification is true, VYES is sent to C at once and V informs C to accept the decomposition results. By the matrix digest, the verifier uses the vector l⟶ and the decomposition results to produce the vector y⟶=y1,…,yj,…,yn. It is this technology that prevents V from having to traverse each element of the result matrices. Eventually, in the decryption phase, utilizing the unit permutation matrix PT and the inverse matrix N−1 of the matrix N, C runs the solve algorithm and decrypts the result matrices to get the orthogonal matrix Q and the upper triangular matrix R of A.


### 3.4. Specific Algorithms ofPVCMD-QR

ThePVCMD-QR scheme consists of five subalgorithms, including KeyGen, ProbGen, Compute, Verify, and Solve.Algorithm1 (KeyGen) is executed by DC.Algorithm 1:KeyGen algorithm.
Input:ℱ, λ;Output:para and SK, PK, EK;(1)
Step 1: initialization(2)
computepara=p,G1,G2,GT,g,h,g˜,h˜.(3)
Step 2: generating keys(4)
generateSK and EK.(5)
computePK(6)
Step 3: return (para, SK, PK, EK)There exist two cyclic groupsG1 and G2 with the order p, where g is generator of G1 and h is generator of G2. So, a bilinear pairings can be described as G1×G2⟶GT. For any δ∈Fp∗, it calculates h˜=hδ and g˜=gδ. Afterwards, it publishes the parameter para=p,G1,G2,GT,g,h,g˜,h˜.(a)
It generates three vectorss⟶, l⟶, and k⟶ randomly, si,li,ki∈Fp∗1≤i≤n. Then, we regard these three vectors as the secret key SK. The algorithm uses the vectors l⟶ and k⟶ to determine the evaluation key EK=z⟶=l⟶+k⟶.(b)
By usingSK=s⟶,l⟶,k⟶, it produces the public key PK=PK1,PK2,PK3, which is defined as follows:(5)PK1=PK11,PK12,…,PK1n,PK2=PK21,PK22,…,PK2n,PK3=PK31,PK32,…,PK3n,where PK1i=gsi, PK2i=egki,h˜, and PK3i=g˜si for i=1 to n.Algorithm2 (ProbGen)is expressed and is executed by C to encrypt a privacy matrix A.(a)
C needs to perform A^=PAN, where N∈Zpn×n. In particular, the matrix P is an n-order unit permutation matrix, and the matrix N is a sparse block diagonal square matrix, whose main diagonal is composed of several matrices Ni and the remaining positions are all 0 elements:(6)N=N10⋯00N2⋯0⋮⋮⋱⋮00⋯Ntn×n,where the submatrixNii=1,2,…,t is lower-order upper triangular invertible matrix, where Ni∈Zp∗ is saved secretly.(b)
It uses the encryption matrixA^ to obtain the verification key VK as below:(i)
The client usess⟶ to produce the auxiliary vector b⟶, where b⟶=s⟶⋅A^.(ii)
PK2 and b⟶ are used to generate VK, namely,(7)VK=∏i=1nPK2ibi.Algorithm 2:ProbGen algorithm.
Input:s⟶, PK2, and A;Output:A^ and VK(1)
Step 1: transforming matrixA(2)
Produce the matricesP and N.(3)
EncodeA into A^.(4)
Step 2: obtainingVK(5)
Computeb⟶.(6)
ObtainVK by equation (7).(7)
Step 3: return (A^, VK)In Algorithm3 (Compute), CS conducts QR decomposition of A^. The process of algorithm is shown in Algorithm 3.(a)
BreakingA^ into A^=Q^R^, CS performs operation of QR decomposition.(b)
It should calculate a proofv to prove the correctness of the decomposition results.(i)
Ann-dimensional auxiliary vector m⟶ is generated, where mi=∏j=1nPK3jA^ji1≤i≤n.(ii)
It uses the vectorm⟶ and EK to generate the value v=∏i=1nmizi.Algorithm 3:Compute algorithm.
Input:A^, PK3 and EK;Output:Q^, R^ and v(1)
Step 1: QR decomposition ofA^(2)
DecomposeA^ into Q^ and R^.(3)
Step 2: obtainingv(4)
Generatem⟶.(5)
Computev with (EK, m⟶).(6)
Step 3: returnQ^, R^, and vAlgorithm4 (Verify) is conducted after V receives the information from other participants. The specific process is explained in Algorithm 4.(a)
V should inspect the orthogonality of Q^.(i)
V uses l⟶ and R^ to generate a intermediate vector y⟶1. By multiplying Q^ by the column vector y⟶1, it can generate a result vector y⟶, which is carried out in field of real number, namely,(8)y⟶1=R^l⟶,y⟶=Q^y⟶1.(ii)
It multiplies the vectory⟶ by Q^T to obtain a new vector denoted by y⟶2, where Q^T is transpose of matrix Q^. Due to property of orthogonal matrix, if y⟶2=Q^Ty⟶=Q^TQ^y⟶1=y⟶1 is true, next step (b) is executed.(b)
If the following equation holds in the finite field,V outputs VYES. Otherwise, it outputs VNO:(9)ev,h=e∏j=1nPK1jyj,h˜⋅VK.Algorithm 4:Verify algorithm.
Input:(Q^,R^), v, l⟶, PK1 and VK;Output:VYES or VNO(1)
Step 1: checking the orthogonality ofQ^(2)
Gety⟶1 with (R^,l⟶).(3)
Producey⟶ with (Q^,y⟶1).(4)
Computey⟶2 with (Q^T,y⟶).(5)
y⟶2−y⟶1=?0.(6)
Step 2: checking the correctness ofQ^ and R^(7)
Computeev,h.(8)
Computee∏j=1nPK1jyj,h˜⋅VK.(9)
ev,h=e∏j=1nPK1jyj,h˜⋅VK⟶VYES(10)
ev,h≠e∏j=1nPK1jyj,h˜⋅VK⟶VNO(11)
Step 3: returnVYES or VNOSuppose that the nonsingular matrixA can be decomposed into A=QR. Algorithm 5 (Solve) is executed by C to obtain both Q and R.(a)
C gets the transposed matrix PT and the inverse matrix N−1 of N which needs to solve the inverse of the upper triangular submatrix Ni for i=1 to t.(b)
MultiplyingPT by the left of Q^ and N−1 by the right of R^, the QR decomposition of matrix A can be obtained:(10)Q=PT⋅Q^,R=R^⋅N−1.Algorithm 5:Solve algorithm.
Input:Q^ and R^;Output:Q and R(1)
SolvePT and N−1.(2)
ObtainQ and R by equation (10).(3)
ReturnQ and R.


## 3.1. Treat Model

The semihonest model introduced in [7] is an honest but curious one with an untrustworthy cloud server as the main adversary. It was also mentioned in [30], where participants in the outsourcing are required to honestly execute the designed scheme. With returning a correct result, semihonest cloud will try to recover sensitive information of the data. Our scheme is based on a semihonest cloud server and introduces an independent data center which is trustworthy.


## 3.2. System Model

Considering the public verification, we give a system model about outsourcing computation with the following five entities introduced, as shown in Figure1.(i)
Data centerDC: some keys are produced by DC. After initializing parameters, it generates the private keys and some public keys. Next, it takes advantage of the private key to generate the evaluation key for CS. Finally, it sends the private key to C and V over the secure channel.(ii)
ClientC: first of all, C should deposit enough money into ℬP for the cost of outsourcing services. Meanwhile, a request is sent to CS about solving a QR decomposition of the large-scale matrix. To protect privacy, C needs to encode the original matrix before the private matrix is uploaded to CS. Then, a verification key should be generated for V.(iii)
Cloud serverCS: like C, CS also needs to provide deposits to ℬP. As service provider, CS needs to perform QR decomposition of the encryption matrix and earn fees from C. Moreover, a proof sent to V together with computating results is generated by using the evaluation key. Finally, the result matrices will be transmitted to C. If C has no objection to the outsourcing result within a specified time, CS will provide a proof OSend to ℬP and get the corresponding fees. Otherwise, CS provides compensation to C.(iv)
VerifierV: any verifier can be regarded as V. Utilizing the verification key and the proof, V will examine the correctness of the outsourcing results.(v)
Blockchain paymentℬP: we take advantage of the payment system based on blockchain ℬP. After receiving deposit from C and CS, ℬP provides a proof OSstart for CS to confirm to start the outsourcing service.Figure 1
System model.


## 3.3. Process Description

The system model consists of two parts: blockchain-based payment system and publicly verifiable outsourcing computing system. In blockchain-based payment system,C needs to provide the corresponding deposits in ℬP as the cost of service before requesting CS to perform QR decomposition of large-scale matrix A^. Meanwhile, CS also deposits the compensation in ℬP as a guarantee for honest computing. If outsourcing result is correct, CS can obtain the corresponding service fees from ℬP. Otherwise, C informs ℬP to terminate the payment process, and CS will accept punishment and provide compensation to C. In this paper, we focus on designing publicly verifiable outsourcing computation for QR decomposition scheme called PVCMD-QR.PVCMD-QR can be divided into five phases including initialization phase, encryption phase, computation phase, verification phase, and decryption phase. To better understand this process, a flowchart is shown in Figure 2. Now, the specific process of the scheme is described below.Figure 2
A plan flowchart of the proposed scheme.In the initialization phase,DC runs the KeyGen algorithm. Here, it randomly generates three n-dimensional key vectors s⟶, l⟶, and k⟶ as the private key SK to produce the public key PK=PK1,PK2,PK3 and the evaluation key EK. s⟶ and l⟶ are delivered to C and V through the secure channel, respectively. In the encryption phase, ProbGen algorithm is executed. C encrypts a full rank privacy matrix A into A^=PAN, A∈Zpn×n, where block-diagonal upper triangular matrix N is constructed by C. Meanwhile, the verification key VK is generated by PK2, s⟶, and A^. Here, we make full use of the technique called matrix digest during the process of generating the VK in our scheme. By multiplying s⟶ and the encryption matrix A^ to obtain the vector b⟶, V uses PK2 and b⟶ to create VK. Then, A^ is uploaded to CS, and VK is provided to any V simultaneously. Then, the compute algorithm is implemented in the computation phase. CS receives A^ to perform QR decomposition. Using EK from DC, it generates a value v for V. After getting the orthogonal matrix Q^ and the upper triangular matrix R^, V begins to execute the verify algorithm by using both the key VK and the proof v in the verification phase. If the verification is true, VYES is sent to C at once and V informs C to accept the decomposition results. By the matrix digest, the verifier uses the vector l⟶ and the decomposition results to produce the vector y⟶=y1,…,yj,…,yn. It is this technology that prevents V from having to traverse each element of the result matrices. Eventually, in the decryption phase, utilizing the unit permutation matrix PT and the inverse matrix N−1 of the matrix N, C runs the solve algorithm and decrypts the result matrices to get the orthogonal matrix Q and the upper triangular matrix R of A.


## 3.4. Specific Algorithms ofPVCMD-QR

ThePVCMD-QR scheme consists of five subalgorithms, including KeyGen, ProbGen, Compute, Verify, and Solve.Algorithm1 (KeyGen) is executed by DC.Algorithm 1:KeyGen algorithm.
Input:ℱ, λ;Output:para and SK, PK, EK;(1)
Step 1: initialization(2)
computepara=p,G1,G2,GT,g,h,g˜,h˜.(3)
Step 2: generating keys(4)
generateSK and EK.(5)
computePK(6)
Step 3: return (para, SK, PK, EK)There exist two cyclic groupsG1 and G2 with the order p, where g is generator of G1 and h is generator of G2. So, a bilinear pairings can be described as G1×G2⟶GT. For any δ∈Fp∗, it calculates h˜=hδ and g˜=gδ. Afterwards, it publishes the parameter para=p,G1,G2,GT,g,h,g˜,h˜.(a)
It generates three vectorss⟶, l⟶, and k⟶ randomly, si,li,ki∈Fp∗1≤i≤n. Then, we regard these three vectors as the secret key SK. The algorithm uses the vectors l⟶ and k⟶ to determine the evaluation key EK=z⟶=l⟶+k⟶.(b)
By usingSK=s⟶,l⟶,k⟶, it produces the public key PK=PK1,PK2,PK3, which is defined as follows:(5)PK1=PK11,PK12,…,PK1n,PK2=PK21,PK22,…,PK2n,PK3=PK31,PK32,…,PK3n,where PK1i=gsi, PK2i=egki,h˜, and PK3i=g˜si for i=1 to n.Algorithm2 (ProbGen)is expressed and is executed by C to encrypt a privacy matrix A.(a)
C needs to perform A^=PAN, where N∈Zpn×n. In particular, the matrix P is an n-order unit permutation matrix, and the matrix N is a sparse block diagonal square matrix, whose main diagonal is composed of several matrices Ni and the remaining positions are all 0 elements:(6)N=N10⋯00N2⋯0⋮⋮⋱⋮00⋯Ntn×n,where the submatrixNii=1,2,…,t is lower-order upper triangular invertible matrix, where Ni∈Zp∗ is saved secretly.(b)
It uses the encryption matrixA^ to obtain the verification key VK as below:(i)
The client usess⟶ to produce the auxiliary vector b⟶, where b⟶=s⟶⋅A^.(ii)
PK2 and b⟶ are used to generate VK, namely,(7)VK=∏i=1nPK2ibi.Algorithm 2:ProbGen algorithm.
Input:s⟶, PK2, and A;Output:A^ and VK(1)
Step 1: transforming matrixA(2)
Produce the matricesP and N.(3)
EncodeA into A^.(4)
Step 2: obtainingVK(5)
Computeb⟶.(6)
ObtainVK by equation (7).(7)
Step 3: return (A^, VK)In Algorithm3 (Compute), CS conducts QR decomposition of A^. The process of algorithm is shown in Algorithm 3.(a)
BreakingA^ into A^=Q^R^, CS performs operation of QR decomposition.(b)
It should calculate a proofv to prove the correctness of the decomposition results.(i)
Ann-dimensional auxiliary vector m⟶ is generated, where mi=∏j=1nPK3jA^ji1≤i≤n.(ii)
It uses the vectorm⟶ and EK to generate the value v=∏i=1nmizi.Algorithm 3:Compute algorithm.
Input:A^, PK3 and EK;Output:Q^, R^ and v(1)
Step 1: QR decomposition ofA^(2)
DecomposeA^ into Q^ and R^.(3)
Step 2: obtainingv(4)
Generatem⟶.(5)
Computev with (EK, m⟶).(6)
Step 3: returnQ^, R^, and vAlgorithm4 (Verify) is conducted after V receives the information from other participants. The specific process is explained in Algorithm 4.(a)
V should inspect the orthogonality of Q^.(i)
V uses l⟶ and R^ to generate a intermediate vector y⟶1. By multiplying Q^ by the column vector y⟶1, it can generate a result vector y⟶, which is carried out in field of real number, namely,(8)y⟶1=R^l⟶,y⟶=Q^y⟶1.(ii)
It multiplies the vectory⟶ by Q^T to obtain a new vector denoted by y⟶2, where Q^T is transpose of matrix Q^. Due to property of orthogonal matrix, if y⟶2=Q^Ty⟶=Q^TQ^y⟶1=y⟶1 is true, next step (b) is executed.(b)
If the following equation holds in the finite field,V outputs VYES. Otherwise, it outputs VNO:(9)ev,h=e∏j=1nPK1jyj,h˜⋅VK.Algorithm 4:Verify algorithm.
Input:(Q^,R^), v, l⟶, PK1 and VK;Output:VYES or VNO(1)
Step 1: checking the orthogonality ofQ^(2)
Gety⟶1 with (R^,l⟶).(3)
Producey⟶ with (Q^,y⟶1).(4)
Computey⟶2 with (Q^T,y⟶).(5)
y⟶2−y⟶1=?0.(6)
Step 2: checking the correctness ofQ^ and R^(7)
Computeev,h.(8)
Computee∏j=1nPK1jyj,h˜⋅VK.(9)
ev,h=e∏j=1nPK1jyj,h˜⋅VK⟶VYES(10)
ev,h≠e∏j=1nPK1jyj,h˜⋅VK⟶VNO(11)
Step 3: returnVYES or VNOSuppose that the nonsingular matrixA can be decomposed into A=QR. Algorithm 5 (Solve) is executed by C to obtain both Q and R.(a)
C gets the transposed matrix PT and the inverse matrix N−1 of N which needs to solve the inverse of the upper triangular submatrix Ni for i=1 to t.(b)
MultiplyingPT by the left of Q^ and N−1 by the right of R^, the QR decomposition of matrix A can be obtained:(10)Q=PT⋅Q^,R=R^⋅N−1.Algorithm 5:Solve algorithm.
Input:Q^ and R^;Output:Q and R(1)
SolvePT and N−1.(2)
ObtainQ and R by equation (10).(3)
ReturnQ and R.


## 4. Protocol Analysis

In this section,PVCMD-QR is analyzed from the perspectives of correctness, security, and efficiency.


### 4.1. Correctness Analysis

#### 4.1.1. ProbGen Algorithm

Since the result of QR decomposition is unique when the main diagonal elements are positive in the upper triangular matrix, not all matrices can be decomposed and the square matrix to be decomposed must be invertible and nonsingular. Therefore, conditions of decomposition of the input matrixA^ should satisfy A^≠0.In fact, after the matrix A is encrypted, this condition is still satisfied. FromA^=PAN, we get the equation A^=P⋅A⋅N. Specifically, since both P and N are invertible matrices, P≠0 and N≠0. In addition, the privacy matrix A is a full rank matrix, A≠0.


#### 4.1.2. Verify Algorithm

Considering the property of the orthogonal matrix, there isQTQ=I, where I represents the identity matrix. If the vectors y⟶2 and y⟶1 are identical, Q^ must be an orthogonal matrix. However, the matrix R^ can be observed directly. The results are correct if the parties involved in the scheme execute the agreement honestly.Before verification, it is necessary forV to compute the result vector y⟶, which can be obtained by y⟶=Q^R^l⟶.Because of equations (11) and (12), equation (13) holds(11)b⟶⋅l⟶=s⟶A^l⟶=s⟶Q^R^l⟶=s⟶⋅y⟶,(12)bi=∑j=1nsjA^ji,1≤i≤n,(13)∑i=1nbili=∑i=1n∑i=1nsjA^jili=∑i=1nsj∑i=1nQ^ji∑i=1nR^iklk=∑i=1nsjyj.According to equation (13), we have(14)ev,h=e∏i=1nmizi,h=e∏i=1n∏j=1nPK3jA^jizi,h=e∏i=1n∏j=1ng˜sjA^jizi,h=e∏i=1ngδ∑j=1nsjA^jizi,h=e∏i=1ngδbizi,h=e∏i=1ngbili,h˜e∏i=1ngbiki,h˜=eg∑j=1nsjyj,h˜∏i=1negki,h˜bi=e∏j=1nPK1jyj,h˜⋅VK.In short, equation (9) is established and the verification is successful and sound.


### 4.2. Security Analysis

Theorem 1.
The publicly verifiable computation schemePVCMD-QR is secure under the co-CDH in group G1.Proof.
We follow Definition3 to illustrate the theoretical analysis for security of our proposed scheme.
To prove this theorem, there are two adversariesA and ℬ. Suppose that the adversary A has a very strong ability to destroy the soundness of PVCMD-QR with a probability ε so that it can obtain important information of the scheme. However, the challenger ℬ with these information from adversary A tries the best to address the co-CDH problem with a nonnegligible probability ε′, and ε≈ε′.
To break this assumption, challengerℬ accesses the random oracle Oco−CDH which generates g,g′=gα∈G1 and h,h′=hβ∈G2 as the result of output in return and selects α,β∈FP∗.
Then, the challengerℬ simulates adversary A to carry out this soundness experiment:
Adversaryℬ denotes g′˜=g′δ and h′˜=h′δ by selecting δ∈Fp∗ randomly as well as generates the parameter para′, namely, para′=p,G1,G2,GT,e,g,g′˜,h,h′˜. It uses parameters para′ to generate PK1′ and PK3′ respectively, which are shown as follows:(15)PK1′=PK11′,PK12′,…,PK1n′,where PK1i′=g′si,1≤i≤n.(16)PK3′=PK31′,PK32′,…,PK3n′,where PK3i′=g′si,1≤i≤n.
Then, it generates an auxiliary vectorm′∈G1n×1, where mi′=∏j=1nPK3j′A^ji for i to n.
According tom′ and PK1′, it computes the public key PK2′ which is a vector. In other words, the expression of PK2′ is determined directly:(17)PK2′=PK21′,PK22′,…,PK2n′.
We take each element ofPK2′ as the following:(18)PK2i′=emi′zi,hePK1i′yi,h′˜1/bi=e∏j=1nPK3j′A^jizi,hePK1i′yi,h′˜1/bi.
There is an important condition for the above expression to be correct, namely,bi≠0. Since the matrix A^ is full rank and s⟶∈Fp∗, the vector b⟶=s⟶⋅A^ is a nonzero vector. In addition, it defines evaluation key EK′=z1,…,zi,…,zn.
Therefore, the challengerℬ can obtain some corresponding information eventually to complete this experiment such as PK2′, para′, and EK′.
Secondly, different from the real output of theKeyGen algorithm, the distribution of the output of the random oracle OkeyGen is independent and indistinguishable. So, we have reason to believe these two facts:(a)
According to the vectorsb⟶ and y⟶=Q^R^l⟶, the following formula must be correct:(19)e∏i=1nmi′zi,h=e∏j=1nPK1j′yj,h′˜⋅∏i=1nPK2i′bi.(b)
The vectorm⟶ and the key PK=PK1,PK2,PK3 are identical to the statistically distribution of m′⟶ and PK′=PK1′,PK2′,PK3′ severally.
Then, adversaryA takes advantage of A^ and PK2′ to access the random oracle OProbGen. The attacker ℬ imitates OProbGen and takes the matrix A^ and VK′ as output, where we denote VK′=∏i=1nPK2i′bi.
Finally, adversaryA will return a value v and fake results (Q^∗,  R^∗) with Q^∗R^∗≠A^. Then, challenger ℬ will calculate the result vector y⟶∗=Q^∗R^∗l⟶ and verify whether y⟶∗=y⟶ is true. If the invalid result y⟶∗ passes this verification, it means that challenger ℬ has failed and does not break the assumption. Otherwise, it returns the following expression of gαβ and declares that the difficult assumption co-CDH is broken, while it is impractical:(20)gαβ=v∏i=1nmi′ziδ∑j=1nsjyj∗−yj−1=v∏i=1n∏j=1nPK3j′A^jiziδ∑j=1nsjyj∗−yj−1.
Now, we are going to provide the specific process of the above solvinggαβ.
If the wrong vectory⟶∗ passes the verification, the following equation (21) must be true:(21)ev,h=e∏j=1nPK1j′yj∗,h′⋅VK′.
Considering equation (18), it is achieved that(22)e∏i=1nmi′zi,h=e∏j=1nPK1j′yj,h˜′⋅VK′.
To divide equations (21) with (22), we obtain(23)ev∏i=1nmi′zi,h=e∏j=1nPK1j′yj∗−yj,h′˜=e∏j=1ng′sjyj∗−yj,h′˜.
Asg′=gα,h′˜=hδβ, and mi′=∏j=1nPK3j′A^ji, it is concluded that(24)ev∏i=1nmi′zi,h=e∏j=1ngαsjyj∗−yj,h′˜=egαβ∑j=1nδsjyj∗−yj,h.
Hence, ifyj∗−yj≠0 and δsj≠0, there is(25)gαβ∑j=1nδsjyj∗−yj=v∏i=1nmi′zi,namely,(26)gαβ=v∏i=1n∏j=1nPK3j′A^jiziδ∑j=1nsjyj∗−yj−1.
Hence, if this scheme is destroyed by adversaryA with a certain probability ε, challenger ℬ is able to break the co-CDH with a nonnegligible advantage ε′. In summary, PVCMD-QR is secure under the co-CDH in group G1.


### 4.3. Efficiency Analysis

In this section, we intend to give a detailed analysis of the computational overhead ofPVCMD-QR.The matrixN, where the order of each submatrix Ni for i=1 to t is chosen randomly from 2 to ww≪n, is produced by C, so there will be many combinations in reality. However, since the matrix N is sparse with the computational complexity On2 for solving N−1, the computational overhead is not taken into consideration about generation of N and N−1.To simplify the analysis, suppose that each submatrixNi is a w-order upper triangular matrix in the main diagonal of N. However, the inverse matrix of the w-order upper triangular matrix is obtained easily, so it is convenient to obtain the inverse matrix N−1 of N, where the inverse Ni−1 of submatrix Ni1≤i≤t is placed in the corresponding position, like this (27)N−1=N1−10⋯00N2−1⋯0⋮⋮⋱⋮00⋯Nt−1n×n.Therefore, we suppose that the ordern of the original matrix A should meet this condition, namely, n=wt.InKeyGen algorithm, three vectors s⟶, l⟶, and k⟶ which are generated randomly require 3n random numbers in the group operation. Next, it needs to calculate PK1, PK2, PK3, and EK separately. The public key PK1 is an n-dimensional vector where there is PK1i=gsi, so DC will execute n exponential operations to obtain PK1. Since the public key PK2, an n-dimensional vector, is obtained by n exponential operations and n pairing operations similarly, where PK2i=egki,h˜, additionally, n exponential operations needs to be performed to get the public key PK3. As the evaluation key EK is also an n-dimensional vector, DC should perform n additions.To performProbGen algorithm where we have A^=PAN, C needs to use a sparse block diagonal upper triangular matrix N and a unit permutation matrix P. Therefore, there are n2+1/2w+1n2 multiplications and 1/2w−1n2 additions in encryption operation. On the contrary, C also computes a verification key VK=∏i=1nPK2ibi with the vector b⟶. To get the vector, it is going to perform n2 multiplications. Therefore, both n exponentials and n−1 multiplications should be required in the process of generating VK.CS executes the QR decomposition of the matrix A^ according to Compute algorithm. It is necessary to produce the value v, where this process involves n exponentiation operations and n−1 multiplications. However, before generating the value v, it should utilize the public key PK3 to get an n-dimensional auxiliary vector m⟶, which requires n2 exponential and nn−1 multiplications operations.InVerify algorithm, V must generate an n-dimensional result vector y⟶, firstly, where 1/2nn+1+n2 multiplications and 1/2n−1n+nn−1 additions should be performed. When checking the orthogonal property of the matrix Q^, V is asked to compute n2 multiplications. Then, it takes advantage of v, y⟶, and VK to verify whether ev,h=e∏j=1nPK1jyj,h˜⋅VK holds, which needs n exponentiation operations, n−1+1 multiplications, and two pairing operations in this phases.We also should take the computation cost ofSolve algorithm. C has to decrypt the matrices Q^ and R^ to obtain the result of QR decomposition of original matrix A. Therefore, n2 multiplication operations are carried out for solving Q=PTQ^. In order to compute R=R^N−1, it will deal with 1/4w+1n2+1/4w+1/3−1/12w2n multiplications and 1/4w−1n2+1/4w+1/3−1/12w2n additions.Here, we denote an exponentiation operation withEx, a multiplication operation with Mu, an addition operation with Ad, a pairing operation with Pa, a matrix decomposition with De, and a random number generation operation with Ge. T1 and T2 are described as follows:(28)T1=14w+13−112w2,T2=14w−16−112w2,where w≪n.In summary, the computation cost of each algorithm is shown in Table1.Table 1
Computation cost of each phase inPVCMD-QR.
AlgorithmComputation costKeyGen3nEx+nPa+nAd+3nGeProbGen1/2w+5n2+n−1Mu+nEx+1/2w−1n2AdComputeDe+n2−1Mu+n2+nExVerify1/25n2+3nMu+nEx+3/2n2−nAd+2PaSolve1/4w+5n2+T1nMu+1/4w−1n2+T2nAdAccording to the above analysis, the computational complexity of the client isOn2 and is lower than to accomplish QR decomposition directly.


### 4.4. Experiment Analysis

Here, we evaluate the proposed scheme with experiments. Using C language, we emulate the data centerDC, the client C, the cloud server CS, and the verifier V on a laptop with Intel Core(TM) i5-8265U CPU processor, 8 GB RAM memory.To better describe the computational efficiency of the proposedPVCMD-QR scheme, we simulate all these algorithms in our scheme (i.e., KeyGen, ProbGen, Compute, Verify, and Solve). First, we assume that the order of each submatrix of the block diagonal matrix N is identical, w=25. The computation costs with different scales of the problem are listed in Table 2, and the specific trend is shown in Figure 3. The experiment shows that the overhead of the client side is smaller than the CS, as listed in Table 3.Table 2
Computation cost ofPVCMD-QR scheme for different problem sizes.
DimensionKeyGen (ms)ProbGen (ms)Compute (ms)Verify (ms)Solve (ms)n = 40033.91000013512.718000167927.37200088.41280011574.687000n = 50043.03700028093.517000264634.147000139.74900022764.303000n = 60052.61900055298.470000377979.489000203.31000039072.307000n = 70062.41000097193.756000513340.065000278.00400061935.196000n = 80070.836000159190.287000670820.937000365.88200092610.783000Figure 3
Computational time cost for each algorithm.Table 3
Comparison of computation cost between the client and cloud side.
DimensionClient cost inPVCMD-QR (ms)Cloud server cost inPVCMD-QR (ms)n = 40025175.817800167927.372000n = 50050997.569000264634.147000n = 60094574.087000377979.489000n = 700159406.956000513340.065000n = 800252166.952000670820.937000Then, we illustrate the superiority of the outsourcing computation in Figure4, in which we mainly consider the time cost of C. In Figure 4, the symbol T(EncAndDec) represents the time cost of C in encryption and decryption phases of outsourcing process, and the symbol T(QR) means the time cost is required for the C to compute QR decomposition of matrix A directly. Compared to directly computing QR decomposition on the original matrix A, the PVCMD-QR scheme is more efficient obviously as the dimension of matrix increases.Figure 4
Efficiency comparison between T(EncAndDec) and T(QR).


## 4.1. Correctness Analysis

### 4.1.1. ProbGen Algorithm

Since the result of QR decomposition is unique when the main diagonal elements are positive in the upper triangular matrix, not all matrices can be decomposed and the square matrix to be decomposed must be invertible and nonsingular. Therefore, conditions of decomposition of the input matrixA^ should satisfy A^≠0.In fact, after the matrix A is encrypted, this condition is still satisfied. FromA^=PAN, we get the equation A^=P⋅A⋅N. Specifically, since both P and N are invertible matrices, P≠0 and N≠0. In addition, the privacy matrix A is a full rank matrix, A≠0.


### 4.1.2. Verify Algorithm

Considering the property of the orthogonal matrix, there isQTQ=I, where I represents the identity matrix. If the vectors y⟶2 and y⟶1 are identical, Q^ must be an orthogonal matrix. However, the matrix R^ can be observed directly. The results are correct if the parties involved in the scheme execute the agreement honestly.Before verification, it is necessary forV to compute the result vector y⟶, which can be obtained by y⟶=Q^R^l⟶.Because of equations (11) and (12), equation (13) holds(11)b⟶⋅l⟶=s⟶A^l⟶=s⟶Q^R^l⟶=s⟶⋅y⟶,(12)bi=∑j=1nsjA^ji,1≤i≤n,(13)∑i=1nbili=∑i=1n∑i=1nsjA^jili=∑i=1nsj∑i=1nQ^ji∑i=1nR^iklk=∑i=1nsjyj.According to equation (13), we have(14)ev,h=e∏i=1nmizi,h=e∏i=1n∏j=1nPK3jA^jizi,h=e∏i=1n∏j=1ng˜sjA^jizi,h=e∏i=1ngδ∑j=1nsjA^jizi,h=e∏i=1ngδbizi,h=e∏i=1ngbili,h˜e∏i=1ngbiki,h˜=eg∑j=1nsjyj,h˜∏i=1negki,h˜bi=e∏j=1nPK1jyj,h˜⋅VK.In short, equation (9) is established and the verification is successful and sound.


## 4.1.1. ProbGen Algorithm

Since the result of QR decomposition is unique when the main diagonal elements are positive in the upper triangular matrix, not all matrices can be decomposed and the square matrix to be decomposed must be invertible and nonsingular. Therefore, conditions of decomposition of the input matrixA^ should satisfy A^≠0.In fact, after the matrix A is encrypted, this condition is still satisfied. FromA^=PAN, we get the equation A^=P⋅A⋅N. Specifically, since both P and N are invertible matrices, P≠0 and N≠0. In addition, the privacy matrix A is a full rank matrix, A≠0.


## 4.1.2. Verify Algorithm

Considering the property of the orthogonal matrix, there isQTQ=I, where I represents the identity matrix. If the vectors y⟶2 and y⟶1 are identical, Q^ must be an orthogonal matrix. However, the matrix R^ can be observed directly. The results are correct if the parties involved in the scheme execute the agreement honestly.Before verification, it is necessary forV to compute the result vector y⟶, which can be obtained by y⟶=Q^R^l⟶.Because of equations (11) and (12), equation (13) holds(11)b⟶⋅l⟶=s⟶A^l⟶=s⟶Q^R^l⟶=s⟶⋅y⟶,(12)bi=∑j=1nsjA^ji,1≤i≤n,(13)∑i=1nbili=∑i=1n∑i=1nsjA^jili=∑i=1nsj∑i=1nQ^ji∑i=1nR^iklk=∑i=1nsjyj.According to equation (13), we have(14)ev,h=e∏i=1nmizi,h=e∏i=1n∏j=1nPK3jA^jizi,h=e∏i=1n∏j=1ng˜sjA^jizi,h=e∏i=1ngδ∑j=1nsjA^jizi,h=e∏i=1ngδbizi,h=e∏i=1ngbili,h˜e∏i=1ngbiki,h˜=eg∑j=1nsjyj,h˜∏i=1negki,h˜bi=e∏j=1nPK1jyj,h˜⋅VK.In short, equation (9) is established and the verification is successful and sound.


## 4.2. Security Analysis

Theorem 1.
The publicly verifiable computation schemePVCMD-QR is secure under the co-CDH in group G1.Proof.
We follow Definition3 to illustrate the theoretical analysis for security of our proposed scheme.
To prove this theorem, there are two adversariesA and ℬ. Suppose that the adversary A has a very strong ability to destroy the soundness of PVCMD-QR with a probability ε so that it can obtain important information of the scheme. However, the challenger ℬ with these information from adversary A tries the best to address the co-CDH problem with a nonnegligible probability ε′, and ε≈ε′.
To break this assumption, challengerℬ accesses the random oracle Oco−CDH which generates g,g′=gα∈G1 and h,h′=hβ∈G2 as the result of output in return and selects α,β∈FP∗.
Then, the challengerℬ simulates adversary A to carry out this soundness experiment:
Adversaryℬ denotes g′˜=g′δ and h′˜=h′δ by selecting δ∈Fp∗ randomly as well as generates the parameter para′, namely, para′=p,G1,G2,GT,e,g,g′˜,h,h′˜. It uses parameters para′ to generate PK1′ and PK3′ respectively, which are shown as follows:(15)PK1′=PK11′,PK12′,…,PK1n′,where PK1i′=g′si,1≤i≤n.(16)PK3′=PK31′,PK32′,…,PK3n′,where PK3i′=g′si,1≤i≤n.
Then, it generates an auxiliary vectorm′∈G1n×1, where mi′=∏j=1nPK3j′A^ji for i to n.
According tom′ and PK1′, it computes the public key PK2′ which is a vector. In other words, the expression of PK2′ is determined directly:(17)PK2′=PK21′,PK22′,…,PK2n′.
We take each element ofPK2′ as the following:(18)PK2i′=emi′zi,hePK1i′yi,h′˜1/bi=e∏j=1nPK3j′A^jizi,hePK1i′yi,h′˜1/bi.
There is an important condition for the above expression to be correct, namely,bi≠0. Since the matrix A^ is full rank and s⟶∈Fp∗, the vector b⟶=s⟶⋅A^ is a nonzero vector. In addition, it defines evaluation key EK′=z1,…,zi,…,zn.
Therefore, the challengerℬ can obtain some corresponding information eventually to complete this experiment such as PK2′, para′, and EK′.
Secondly, different from the real output of theKeyGen algorithm, the distribution of the output of the random oracle OkeyGen is independent and indistinguishable. So, we have reason to believe these two facts:(a)
According to the vectorsb⟶ and y⟶=Q^R^l⟶, the following formula must be correct:(19)e∏i=1nmi′zi,h=e∏j=1nPK1j′yj,h′˜⋅∏i=1nPK2i′bi.(b)
The vectorm⟶ and the key PK=PK1,PK2,PK3 are identical to the statistically distribution of m′⟶ and PK′=PK1′,PK2′,PK3′ severally.
Then, adversaryA takes advantage of A^ and PK2′ to access the random oracle OProbGen. The attacker ℬ imitates OProbGen and takes the matrix A^ and VK′ as output, where we denote VK′=∏i=1nPK2i′bi.
Finally, adversaryA will return a value v and fake results (Q^∗,  R^∗) with Q^∗R^∗≠A^. Then, challenger ℬ will calculate the result vector y⟶∗=Q^∗R^∗l⟶ and verify whether y⟶∗=y⟶ is true. If the invalid result y⟶∗ passes this verification, it means that challenger ℬ has failed and does not break the assumption. Otherwise, it returns the following expression of gαβ and declares that the difficult assumption co-CDH is broken, while it is impractical:(20)gαβ=v∏i=1nmi′ziδ∑j=1nsjyj∗−yj−1=v∏i=1n∏j=1nPK3j′A^jiziδ∑j=1nsjyj∗−yj−1.
Now, we are going to provide the specific process of the above solvinggαβ.
If the wrong vectory⟶∗ passes the verification, the following equation (21) must be true:(21)ev,h=e∏j=1nPK1j′yj∗,h′⋅VK′.
Considering equation (18), it is achieved that(22)e∏i=1nmi′zi,h=e∏j=1nPK1j′yj,h˜′⋅VK′.
To divide equations (21) with (22), we obtain(23)ev∏i=1nmi′zi,h=e∏j=1nPK1j′yj∗−yj,h′˜=e∏j=1ng′sjyj∗−yj,h′˜.
Asg′=gα,h′˜=hδβ, and mi′=∏j=1nPK3j′A^ji, it is concluded that(24)ev∏i=1nmi′zi,h=e∏j=1ngαsjyj∗−yj,h′˜=egαβ∑j=1nδsjyj∗−yj,h.
Hence, ifyj∗−yj≠0 and δsj≠0, there is(25)gαβ∑j=1nδsjyj∗−yj=v∏i=1nmi′zi,namely,(26)gαβ=v∏i=1n∏j=1nPK3j′A^jiziδ∑j=1nsjyj∗−yj−1.
Hence, if this scheme is destroyed by adversaryA with a certain probability ε, challenger ℬ is able to break the co-CDH with a nonnegligible advantage ε′. In summary, PVCMD-QR is secure under the co-CDH in group G1.


## 4.3. Efficiency Analysis

In this section, we intend to give a detailed analysis of the computational overhead ofPVCMD-QR.The matrixN, where the order of each submatrix Ni for i=1 to t is chosen randomly from 2 to ww≪n, is produced by C, so there will be many combinations in reality. However, since the matrix N is sparse with the computational complexity On2 for solving N−1, the computational overhead is not taken into consideration about generation of N and N−1.To simplify the analysis, suppose that each submatrixNi is a w-order upper triangular matrix in the main diagonal of N. However, the inverse matrix of the w-order upper triangular matrix is obtained easily, so it is convenient to obtain the inverse matrix N−1 of N, where the inverse Ni−1 of submatrix Ni1≤i≤t is placed in the corresponding position, like this (27)N−1=N1−10⋯00N2−1⋯0⋮⋮⋱⋮00⋯Nt−1n×n.Therefore, we suppose that the ordern of the original matrix A should meet this condition, namely, n=wt.InKeyGen algorithm, three vectors s⟶, l⟶, and k⟶ which are generated randomly require 3n random numbers in the group operation. Next, it needs to calculate PK1, PK2, PK3, and EK separately. The public key PK1 is an n-dimensional vector where there is PK1i=gsi, so DC will execute n exponential operations to obtain PK1. Since the public key PK2, an n-dimensional vector, is obtained by n exponential operations and n pairing operations similarly, where PK2i=egki,h˜, additionally, n exponential operations needs to be performed to get the public key PK3. As the evaluation key EK is also an n-dimensional vector, DC should perform n additions.To performProbGen algorithm where we have A^=PAN, C needs to use a sparse block diagonal upper triangular matrix N and a unit permutation matrix P. Therefore, there are n2+1/2w+1n2 multiplications and 1/2w−1n2 additions in encryption operation. On the contrary, C also computes a verification key VK=∏i=1nPK2ibi with the vector b⟶. To get the vector, it is going to perform n2 multiplications. Therefore, both n exponentials and n−1 multiplications should be required in the process of generating VK.CS executes the QR decomposition of the matrix A^ according to Compute algorithm. It is necessary to produce the value v, where this process involves n exponentiation operations and n−1 multiplications. However, before generating the value v, it should utilize the public key PK3 to get an n-dimensional auxiliary vector m⟶, which requires n2 exponential and nn−1 multiplications operations.InVerify algorithm, V must generate an n-dimensional result vector y⟶, firstly, where 1/2nn+1+n2 multiplications and 1/2n−1n+nn−1 additions should be performed. When checking the orthogonal property of the matrix Q^, V is asked to compute n2 multiplications. Then, it takes advantage of v, y⟶, and VK to verify whether ev,h=e∏j=1nPK1jyj,h˜⋅VK holds, which needs n exponentiation operations, n−1+1 multiplications, and two pairing operations in this phases.We also should take the computation cost ofSolve algorithm. C has to decrypt the matrices Q^ and R^ to obtain the result of QR decomposition of original matrix A. Therefore, n2 multiplication operations are carried out for solving Q=PTQ^. In order to compute R=R^N−1, it will deal with 1/4w+1n2+1/4w+1/3−1/12w2n multiplications and 1/4w−1n2+1/4w+1/3−1/12w2n additions.Here, we denote an exponentiation operation withEx, a multiplication operation with Mu, an addition operation with Ad, a pairing operation with Pa, a matrix decomposition with De, and a random number generation operation with Ge. T1 and T2 are described as follows:(28)T1=14w+13−112w2,T2=14w−16−112w2,where w≪n.In summary, the computation cost of each algorithm is shown in Table1.Table 1
Computation cost of each phase inPVCMD-QR.
AlgorithmComputation costKeyGen3nEx+nPa+nAd+3nGeProbGen1/2w+5n2+n−1Mu+nEx+1/2w−1n2AdComputeDe+n2−1Mu+n2+nExVerify1/25n2+3nMu+nEx+3/2n2−nAd+2PaSolve1/4w+5n2+T1nMu+1/4w−1n2+T2nAdAccording to the above analysis, the computational complexity of the client isOn2 and is lower than to accomplish QR decomposition directly.


## 4.4. Experiment Analysis

Here, we evaluate the proposed scheme with experiments. Using C language, we emulate the data centerDC, the client C, the cloud server CS, and the verifier V on a laptop with Intel Core(TM) i5-8265U CPU processor, 8 GB RAM memory.To better describe the computational efficiency of the proposedPVCMD-QR scheme, we simulate all these algorithms in our scheme (i.e., KeyGen, ProbGen, Compute, Verify, and Solve). First, we assume that the order of each submatrix of the block diagonal matrix N is identical, w=25. The computation costs with different scales of the problem are listed in Table 2, and the specific trend is shown in Figure 3. The experiment shows that the overhead of the client side is smaller than the CS, as listed in Table 3.Table 2
Computation cost ofPVCMD-QR scheme for different problem sizes.
DimensionKeyGen (ms)ProbGen (ms)Compute (ms)Verify (ms)Solve (ms)n = 40033.91000013512.718000167927.37200088.41280011574.687000n = 50043.03700028093.517000264634.147000139.74900022764.303000n = 60052.61900055298.470000377979.489000203.31000039072.307000n = 70062.41000097193.756000513340.065000278.00400061935.196000n = 80070.836000159190.287000670820.937000365.88200092610.783000Figure 3
Computational time cost for each algorithm.Table 3
Comparison of computation cost between the client and cloud side.
DimensionClient cost inPVCMD-QR (ms)Cloud server cost inPVCMD-QR (ms)n = 40025175.817800167927.372000n = 50050997.569000264634.147000n = 60094574.087000377979.489000n = 700159406.956000513340.065000n = 800252166.952000670820.937000Then, we illustrate the superiority of the outsourcing computation in Figure4, in which we mainly consider the time cost of C. In Figure 4, the symbol T(EncAndDec) represents the time cost of C in encryption and decryption phases of outsourcing process, and the symbol T(QR) means the time cost is required for the C to compute QR decomposition of matrix A directly. Compared to directly computing QR decomposition on the original matrix A, the PVCMD-QR scheme is more efficient obviously as the dimension of matrix increases.Figure 4
Efficiency comparison between T(EncAndDec) and T(QR).


## 5. Conclusion

Aiming at the public verification outsourcing computation, this paper proposes a new publicly verifiable scheme with blockchain payment under the amortized model for QR decomposition of large-scale matrix. The sensitive data information is protected by using the sparse matrix. Therefore, client can upload his/her privacy matrix to the outsourcing service provider to perform QR decomposition. Simultaneously, the matrix digest technique is applied to the verification operation of outsourcing computation, which cuts down the workload of verifier dramatically. Afterwards, we also provide the specific theoretical proof of the correctness, safety, and efficiency of thePVCMD-QR scheme, and the result proves that the scheme is secure under the co-CDH assumption.



---

*Source: 6632518-2021-03-24.xml*