# Confidentiality-Preserving Publicly Verifiable Computation Schemes for Polynomial Evaluation and Matrix-Vector Multiplication

Authors: Jiameng Sun; Binrui Zhu; Jing Qin; Jiankun Hu; Jixin Ma
Journal: Security and Communication Networks
 (2018)

---

## Abstract

With the development of cloud services, outsourcing computation tasks to a commercial cloud server has drawn attention of various communities, especially in the Big Data era. Public verifiability offers a flexible functionality in real circumstance where the cloud service provider (CSP) may be untrusted or some malicious users may slander the CSP on purpose. However, sometimes the computational result is sensitive and is supposed to remain undisclosed in the public verification phase, while existing works on publicly verifiable computation (PVC) fail to achieve this requirement. In this paper, we highlight the property of result confidentiality in publicly verifiable computation and present confidentiality-preserving public verifiable computation (CP-PVC) schemes for multivariate polynomial evaluation and matrix-vector multiplication, respectively. The proposed schemes work efficiently under the amortized model and, compared with previous PVC schemes for these computations, achieve confidentiality of computational results, while maintaining the property of public verifiability. The proposed schemes proved to be secure, efficient, and result-confidential. In addition, we provide the algorithms and experimental simulation to show the performance of the proposed schemes, which indicates that our proposal is also acceptable in practice.


---

## Body

## 1. Introduction

Outsourcing computation has been served as a significant service with the rapid development of Cloud Computing Technology. It provides the service purchaser (whom we call user) with constraint computational power to delegate the complicated computational tasks to the service provider (which we call cloud server) and enjoy its unlimited computational resources in a pay-per-use manner. This brings a huge convenience for resource-constraint devices to reduce their computational overhead and thus has attracted significant interests in both industrial and academic communities. A number of large enterprise groups, such as Amazon, Google, and Alibaba, have launched their Cloud Computing to provide computation outsourcing services. What is more, in Big Data era, the ability to deal with the massive data has become core competitiveness while outsourcing computation just fits this demand.While outsourcing computation paradigm enjoys numerous benefits, it also suffers from rigorous challenges [1]. To begin with, since the cloud server is commercialized, sometimes it may not perform the computation honestly but output a computationally indistinguishable result in order to save its cost for more interests. Therefore, a basic requirement of outsourcing computation is to assure the correctness of the computational result. In other words, the user should have a way to verify the correctness of the output from the cloud server with an overwhelming probability. Despite the untrustworthy of cloud server, misbehavior may also happen from the user side. For example, a malicious user may deliberately claim the output from the cloud server incorrect and slander the cloud service provider by this even if the cloud server has performed the computation honestly. This is due to the fact that verification is done in a private manner. Therefore, it is preferable that the verification can be done publicly. That is to say, anyone except the user himself is able to verify the output from the cloud server. With public verification, not only cannot the cloud server cheat with an incorrect output, but also the user cannot claim the output from the cloud server incorrect for no reason, because now the output is witnessed and verified by everyone. Secondly, since sometimes the computational result is something sensitive, it needs to be kept secret to any party except the user himself. Thus another challenge of outsourcing computation is to assure confidentiality of the computational result, especially when the output from the cloud server can be verified publicly. Last but not least, the whole workload of the user in certain computation outsourcing procedure must be much less than accomplishing this computation task all by the user himself. We call this the requirement of efficiency. This is essential because if not, the outsourcing will be meaningless.The evaluation of multivariate polynomialsp
(
x
) is one of the most fundamental computational tasks in scientific communities. In practice, there are so many problems that can be reduced to a model of evaluating certain polynomial with multivariate input value, for example, to evaluate an employee’s performance in a company and to evaluate a person’s health condition. Matrix-vector multiplication is another fundamental computational task that is widely applied, for example the Discrete Fourier Transform (DFT) and the Singular Value Decomposition (SVD). And in Big Data era, with the data we need to deal with getting more and more enormous, it is very likely that the storage requirement when evaluating multivariate polynomials or matrix-vector multiplication exceeds the available memory of the user’s computational devices, like cell phones or portable laptop. Thus we need to find another way to fulfill the computational tasks securely and efficiently. Plenty of works have been done to seek secure and efficient schemes of outsourcing computation for polynomials and matrix-vector multiplication. Fiore and Gennaro [2] proposed schemes to securely outsource evaluation of multivariate polynomials and matrix-vector multiplication and verify the corresponding result in a public manner. Unfortunately, one disadvantage of their proposal is the leakage of final result. Anyone is able to verify the correctness of the output from the cloud server and then obtain the result of the target evaluation. This brings a drawback in practice when the result is something sensitive, for example, the year-end bonus of an employee and the health condition of a person.


### 1.1. Related Works

#### 1.1.1. Verifiable Computation

Verifiable computation (VC) was first proposed by Gennaro et al. [3]. In VC, only two parties are involved, the client that processes the input data and the server that evaluates the target function with the value client sends. The output of the server can be verified by the client only. Both the input and output value of the function are private in the whole procedure. Gennaro et al. proposed a concrete VC scheme for arbitrary circuit using Yao’s [4] two-party computation scheme and Gentry’s [5] fully homomorphic encryption (FHE) scheme. After that, different VC schemes using FHE were proposed [6–8]. They made use of various techniques to achieve verifiability. However, applying FHE in practice brings expensive overhead.To avoid applying FHE and promote efficiency, a lot of papers [9–15] focused on VC schemes for various kinds of computation and had achieved outstanding results.


#### 1.1.2. Publicly Verifiable Computation

Different from VC where the verification is done privately, publicly verifiable computation (PVC) allows anyone to verify the result output by the server. PVC brings more flexible application in the untrusted cloud environment than VC, mainly in two-fold. One is to release the workloads of verification for the client. Another is the supervision of users. This is because if the verification is only done privately, once an incorrect result is claimed, it is hard to tell whether the server misbehaved or the user is intentionally slandering. However if the result can be verified publicly, the user’s slandering is easy to detect. PVC was first proposed by Parno et al. [16]. They constructed a PVC scheme for Boolean functions using KP-ABE schemes. After that, many PVC schemes were proposed [2, 17–19]. In 2012, Fiore et al. [2] proposed a PVC scheme for multivariate polynomial evaluation and matrix multiplication. They took inspiration from Benabbas et al.’s [9] VC scheme to use pseudorandom function that enjoys closed form efficiency to generate the verification key efficiently, and they generalized the function to multivariate case. Moreover, by leveraging the technique of bilinear map, they have improved the verification procedure from private to public manner. With the similar technique, Sun et al. [17] constructed batch verifiable computation schemes with public verification for polynomial and matrix that achieve simultaneously evaluation of multiple functions in one outsourcing phase. In 2016, Elkhiyaoui et al. proposed another solution for univariate polynomial evaluation and matrix multiplication. They leverage the idea of Euclidean division of polynomials to construct the structure of the verifiable computation. And the bilinear map technique is utilized to make the verification able to be public. However, this idea is only suitable for univariate polynomial scenario. What is more, all the schemes mentioned above share the same disadvantage that anyone except for the user that verifies the result will surely obtain its concrete value. This is insecure in practice when the result of certain computation is usually something sensitive and the verification process is supposed to output a judgement to the correctness of the result rather than disclosing the value itself. To overcome this, Alderman et al. [20] improved Parno et al.’s [16] scheme with a secret substitution bit and presented a PVC with key distribution center (KDC) for Boolean functions. They also achieved other properties like revocation based on this PVC with KDC [21, 22], but this way of using secret substitution bit cannot fit other functions that have large range.


### 1.2. Our Contributions

In this paper, we present a modified PVC model that is considered to be more practical. It captures the confidentiality of the computational result, which we believe is an important property when utilizing in practice.We present outsourcing schemes for securely and efficiently evaluating high degree multivariate polynomials and matrix-vector multiplication. Compared with existing outsourcing schemes for polynomials [2, 23] and matrix multiplication, our proposal simultaneously captures properties of both public verifiability and result confidentiality. This offers a more flexible application in practice.We also provide the algorithm for our outsourcing scheme and run some simulated experiments to show the efficiency of the proposed schemes.This paper is an extension of its corresponding conference version [24]. In the revised version, we extends the CP-PVC scheme to the matrix-vector multiplication case. The resulting scheme proved to achieve not only the properties of polynomial case (i.e., security, public verifiability, and result confidentiality) but also the input privacy. We run corresponding simulated experiments and the result is also acceptable for practice.


### 1.3. Paper Organization

The remaining parts of the paper are organized as follows. Some necessary preliminaries are provided for the proposed schemes in Section2. The framework of the proposed CP-PVC protocol is defined in Section 3. The concrete constructions of the CP-PVC schemes for polynomial evaluation and matrix-vector multiplication are presented, analyzed, and simultaneously experimented separately in Sections 4 and 5. The conclusion of the paper is in Section 6.


## 1.1. Related Works

### 1.1.1. Verifiable Computation

Verifiable computation (VC) was first proposed by Gennaro et al. [3]. In VC, only two parties are involved, the client that processes the input data and the server that evaluates the target function with the value client sends. The output of the server can be verified by the client only. Both the input and output value of the function are private in the whole procedure. Gennaro et al. proposed a concrete VC scheme for arbitrary circuit using Yao’s [4] two-party computation scheme and Gentry’s [5] fully homomorphic encryption (FHE) scheme. After that, different VC schemes using FHE were proposed [6–8]. They made use of various techniques to achieve verifiability. However, applying FHE in practice brings expensive overhead.To avoid applying FHE and promote efficiency, a lot of papers [9–15] focused on VC schemes for various kinds of computation and had achieved outstanding results.


### 1.1.2. Publicly Verifiable Computation

Different from VC where the verification is done privately, publicly verifiable computation (PVC) allows anyone to verify the result output by the server. PVC brings more flexible application in the untrusted cloud environment than VC, mainly in two-fold. One is to release the workloads of verification for the client. Another is the supervision of users. This is because if the verification is only done privately, once an incorrect result is claimed, it is hard to tell whether the server misbehaved or the user is intentionally slandering. However if the result can be verified publicly, the user’s slandering is easy to detect. PVC was first proposed by Parno et al. [16]. They constructed a PVC scheme for Boolean functions using KP-ABE schemes. After that, many PVC schemes were proposed [2, 17–19]. In 2012, Fiore et al. [2] proposed a PVC scheme for multivariate polynomial evaluation and matrix multiplication. They took inspiration from Benabbas et al.’s [9] VC scheme to use pseudorandom function that enjoys closed form efficiency to generate the verification key efficiently, and they generalized the function to multivariate case. Moreover, by leveraging the technique of bilinear map, they have improved the verification procedure from private to public manner. With the similar technique, Sun et al. [17] constructed batch verifiable computation schemes with public verification for polynomial and matrix that achieve simultaneously evaluation of multiple functions in one outsourcing phase. In 2016, Elkhiyaoui et al. proposed another solution for univariate polynomial evaluation and matrix multiplication. They leverage the idea of Euclidean division of polynomials to construct the structure of the verifiable computation. And the bilinear map technique is utilized to make the verification able to be public. However, this idea is only suitable for univariate polynomial scenario. What is more, all the schemes mentioned above share the same disadvantage that anyone except for the user that verifies the result will surely obtain its concrete value. This is insecure in practice when the result of certain computation is usually something sensitive and the verification process is supposed to output a judgement to the correctness of the result rather than disclosing the value itself. To overcome this, Alderman et al. [20] improved Parno et al.’s [16] scheme with a secret substitution bit and presented a PVC with key distribution center (KDC) for Boolean functions. They also achieved other properties like revocation based on this PVC with KDC [21, 22], but this way of using secret substitution bit cannot fit other functions that have large range.


## 1.1.1. Verifiable Computation

Verifiable computation (VC) was first proposed by Gennaro et al. [3]. In VC, only two parties are involved, the client that processes the input data and the server that evaluates the target function with the value client sends. The output of the server can be verified by the client only. Both the input and output value of the function are private in the whole procedure. Gennaro et al. proposed a concrete VC scheme for arbitrary circuit using Yao’s [4] two-party computation scheme and Gentry’s [5] fully homomorphic encryption (FHE) scheme. After that, different VC schemes using FHE were proposed [6–8]. They made use of various techniques to achieve verifiability. However, applying FHE in practice brings expensive overhead.To avoid applying FHE and promote efficiency, a lot of papers [9–15] focused on VC schemes for various kinds of computation and had achieved outstanding results.


## 1.1.2. Publicly Verifiable Computation

Different from VC where the verification is done privately, publicly verifiable computation (PVC) allows anyone to verify the result output by the server. PVC brings more flexible application in the untrusted cloud environment than VC, mainly in two-fold. One is to release the workloads of verification for the client. Another is the supervision of users. This is because if the verification is only done privately, once an incorrect result is claimed, it is hard to tell whether the server misbehaved or the user is intentionally slandering. However if the result can be verified publicly, the user’s slandering is easy to detect. PVC was first proposed by Parno et al. [16]. They constructed a PVC scheme for Boolean functions using KP-ABE schemes. After that, many PVC schemes were proposed [2, 17–19]. In 2012, Fiore et al. [2] proposed a PVC scheme for multivariate polynomial evaluation and matrix multiplication. They took inspiration from Benabbas et al.’s [9] VC scheme to use pseudorandom function that enjoys closed form efficiency to generate the verification key efficiently, and they generalized the function to multivariate case. Moreover, by leveraging the technique of bilinear map, they have improved the verification procedure from private to public manner. With the similar technique, Sun et al. [17] constructed batch verifiable computation schemes with public verification for polynomial and matrix that achieve simultaneously evaluation of multiple functions in one outsourcing phase. In 2016, Elkhiyaoui et al. proposed another solution for univariate polynomial evaluation and matrix multiplication. They leverage the idea of Euclidean division of polynomials to construct the structure of the verifiable computation. And the bilinear map technique is utilized to make the verification able to be public. However, this idea is only suitable for univariate polynomial scenario. What is more, all the schemes mentioned above share the same disadvantage that anyone except for the user that verifies the result will surely obtain its concrete value. This is insecure in practice when the result of certain computation is usually something sensitive and the verification process is supposed to output a judgement to the correctness of the result rather than disclosing the value itself. To overcome this, Alderman et al. [20] improved Parno et al.’s [16] scheme with a secret substitution bit and presented a PVC with key distribution center (KDC) for Boolean functions. They also achieved other properties like revocation based on this PVC with KDC [21, 22], but this way of using secret substitution bit cannot fit other functions that have large range.


## 1.2. Our Contributions

In this paper, we present a modified PVC model that is considered to be more practical. It captures the confidentiality of the computational result, which we believe is an important property when utilizing in practice.We present outsourcing schemes for securely and efficiently evaluating high degree multivariate polynomials and matrix-vector multiplication. Compared with existing outsourcing schemes for polynomials [2, 23] and matrix multiplication, our proposal simultaneously captures properties of both public verifiability and result confidentiality. This offers a more flexible application in practice.We also provide the algorithm for our outsourcing scheme and run some simulated experiments to show the efficiency of the proposed schemes.This paper is an extension of its corresponding conference version [24]. In the revised version, we extends the CP-PVC scheme to the matrix-vector multiplication case. The resulting scheme proved to achieve not only the properties of polynomial case (i.e., security, public verifiability, and result confidentiality) but also the input privacy. We run corresponding simulated experiments and the result is also acceptable for practice.


## 1.3. Paper Organization

The remaining parts of the paper are organized as follows. Some necessary preliminaries are provided for the proposed schemes in Section2. The framework of the proposed CP-PVC protocol is defined in Section 3. The concrete constructions of the CP-PVC schemes for polynomial evaluation and matrix-vector multiplication are presented, analyzed, and simultaneously experimented separately in Sections 4 and 5. The conclusion of the paper is in Section 6.


## 2. Preliminaries

In this section, we provide some definitions about algebraic pseudorandom function (PRF) with closed form efficiency, bilinear Map, and some related notions. We also provide the computational assumptions that are used for the construction of our schemes.


### 2.1. Algebraic PRF with Closed Form Efficiency

One of our main techniques is the PRF with closed form efficiency. PRF is a function (denoted byR) that is generated from a secret seed K. It owns the properties of both randomness and computational efficiency. A closed form efficient PRF consists of algorithms (KG, R) that are defined as follows:(i)
KG
(
1
λ
)
→
(
K
,
p
p
): The randomized key generation algorithm takes as input the security parameter 1
λ and outputs a tuple of parameters (
K
,
p
p
), where K denotes the secret seed and p
p denotes the public parameters that specifies the domain X and range Y of the function, respectively.
(ii)
R
(
K
,
x
)
→
y: The deterministic functional computation algorithm takes as input the secret seed K and the value x
∈
X and computes a value y
∈
Y. We usually denote it by R
K
(
·
).An algebraic PRF with closed form efficiency must satisfies the following properties:(
1
)
(Algebraic) A PRF (
K
G
,
R
) is algebraic if the range Y of R
K
(
·
) forms an abelian group. We use multiplication notation for group operation.
(
2
)
(Pseudorandom) A PRF (
K
G
,
R
) is pseudorandom if for every PPT adversary A, there holds(1)
P
r
A
R
K
·
1
λ
,
p
p
=
1
-
P
r
A
r
·
1
λ
,
p
p
=
1
≤
ϵ
where(
K
,
p
p
)
←
$
K
G
(
1
λ
) and r
:
X
→
Y is a random function.
(
3
)
(Closed form efficiency) LetComp represent arbitrary computation that takes as input l random values r
1
,
…
,
r
l
∈
Y and a vector of m arbitrary values x
=
(
x
1
,
…
,
x
m
). Assume that the fastest algorithm to computeComp
(
r
1
,
…
,
r
l
,
x
1
,
…
,
x
m
) takes time t
0. Let z
=
(
z
1
,
…
,
z
l
) be a tuple of arbitrary values taken from X. Then a PRF (
K
G
,
R
) is closed form efficient for (Comp, z) if there exists an algorithm C
F
E
v
a
l
C
o
m
p
,
z such that(2)
C
F
E
v
a
l
C
o
m
p
,
z
K
,
x
=
C
o
m
p
R
K
z
1
,
…
,
R
K
z
l
,
x
1
,
…
,
x
m
and its running time iso
(
t
0
). When z
=
(
1
,
…
,
l
), we usually omit it from the subscript and write C
F
E
v
a
l
C
o
m
p
(
K
,
x
) instead.Here we only show the definition of PRF with closed form efficiency. We will give a concrete algorithm of PRF with closed form efficiency for multivariate polynomials in Section3.


### 2.2. Bilinear Map

Our constructions also use bilinear maps. Bilinear pairing is a powerful tool in noninteractive authentication and has been widely applied in both encryption and signature schemes [9, 25]. To be specific, let G
1
,
G
2, and G
T be finite cyclic multiplicative groups of order p, and let g
,
h be generators of G
1 and G
2. A map e
^
:
G
1
×
G
2
→
G
T is called a bilinear map if it satisfies the following properties:(
1
)
Bilinearity: it holds that(3)
e
^
g
α
,
h
β
=
e
^
g
,
h
α
β
for allα
,
β
∈
Z
N.
(
2
)
Nondegeneracy: there existg
1
∈
G
1
,
h
1
∈
G
2 such that e
^
(
g
1
,
h
1
)
≠
1.
(
3
)
Computability: there exists an efficient algorithm to computee
^
(
g
1
,
h
1
) for any g
1
∈
G
1
,
h
1
∈
G
2.


### 2.3. Computational Assumptions

The computational assumption that is used for the construction of the PRF with closed form efficiency is decision linear (DL) assumption. We present the definition below.Definition 1 (decision linear assumption).
LetG be a group of prime order p. Given g
0
,
g
1
,
g
2
∈
G and r
0
,
r
1
,
r
2
∈
Z
p, one defines the advantage of an algorithm A in deciding the decision linear problem in G as(4)
A
d
v
A
d
l
=
P
r
A
p
,
g
0
,
g
1
,
g
2
,
g
1
r
1
,
g
2
r
2
,
g
0
r
1
+
r
2
=
1
-
P
r
A
p
,
g
0
,
g
1
,
g
2
,
g
1
r
1
,
g
2
r
2
,
g
0
r
0
=
1
.One says that the decision linear assumption (
t
,
ϵ
) holds in G if for every t-time algorithm A one has A
d
v
A
d
l
≤
ϵ.Note that the decision linear assumption holds in generic bilinear groups. Relative proof can be found in [26].Next we present the definition of co-CDH, which is the base for the security of our proposed schemes. The co-CDH assumption was first introduced in BLS signature scheme presented by Boneh et al. [27], as a natural extension of standard CDH problem in asymmetric bilinear pairing. It is defined as follows.Definition 2 (co-CDH assumption).
Let(
p
,
g
,
h
,
G
1
,
G
2
,
G
T
,
e
^
) be as above in Section 2.2. Given random a
,
b
∈
Z
p, one defines the advantage of an algorithm A in solving the co-CDH problem in G
1
,
G
2 as(5)
A
d
v
A
c
o
-
c
d
h
=
P
r
A
p
,
g
,
h
,
g
a
,
h
b
=
g
a
band one says that the co-CDH assumption (
t
,
ϵ
) holds in G
1
,
G
2 if for every t-time algorithm A one has A
d
v
A
c
o
-
c
d
h
≤
ϵ.Note that whenG
1
=
G
2, the co-CDH problem reduces to standard CDH.


## 2.1. Algebraic PRF with Closed Form Efficiency

One of our main techniques is the PRF with closed form efficiency. PRF is a function (denoted byR) that is generated from a secret seed K. It owns the properties of both randomness and computational efficiency. A closed form efficient PRF consists of algorithms (KG, R) that are defined as follows:(i)
KG
(
1
λ
)
→
(
K
,
p
p
): The randomized key generation algorithm takes as input the security parameter 1
λ and outputs a tuple of parameters (
K
,
p
p
), where K denotes the secret seed and p
p denotes the public parameters that specifies the domain X and range Y of the function, respectively.
(ii)
R
(
K
,
x
)
→
y: The deterministic functional computation algorithm takes as input the secret seed K and the value x
∈
X and computes a value y
∈
Y. We usually denote it by R
K
(
·
).An algebraic PRF with closed form efficiency must satisfies the following properties:(
1
)
(Algebraic) A PRF (
K
G
,
R
) is algebraic if the range Y of R
K
(
·
) forms an abelian group. We use multiplication notation for group operation.
(
2
)
(Pseudorandom) A PRF (
K
G
,
R
) is pseudorandom if for every PPT adversary A, there holds(1)
P
r
A
R
K
·
1
λ
,
p
p
=
1
-
P
r
A
r
·
1
λ
,
p
p
=
1
≤
ϵ
where(
K
,
p
p
)
←
$
K
G
(
1
λ
) and r
:
X
→
Y is a random function.
(
3
)
(Closed form efficiency) LetComp represent arbitrary computation that takes as input l random values r
1
,
…
,
r
l
∈
Y and a vector of m arbitrary values x
=
(
x
1
,
…
,
x
m
). Assume that the fastest algorithm to computeComp
(
r
1
,
…
,
r
l
,
x
1
,
…
,
x
m
) takes time t
0. Let z
=
(
z
1
,
…
,
z
l
) be a tuple of arbitrary values taken from X. Then a PRF (
K
G
,
R
) is closed form efficient for (Comp, z) if there exists an algorithm C
F
E
v
a
l
C
o
m
p
,
z such that(2)
C
F
E
v
a
l
C
o
m
p
,
z
K
,
x
=
C
o
m
p
R
K
z
1
,
…
,
R
K
z
l
,
x
1
,
…
,
x
m
and its running time iso
(
t
0
). When z
=
(
1
,
…
,
l
), we usually omit it from the subscript and write C
F
E
v
a
l
C
o
m
p
(
K
,
x
) instead.Here we only show the definition of PRF with closed form efficiency. We will give a concrete algorithm of PRF with closed form efficiency for multivariate polynomials in Section3.


## 2.2. Bilinear Map

Our constructions also use bilinear maps. Bilinear pairing is a powerful tool in noninteractive authentication and has been widely applied in both encryption and signature schemes [9, 25]. To be specific, let G
1
,
G
2, and G
T be finite cyclic multiplicative groups of order p, and let g
,
h be generators of G
1 and G
2. A map e
^
:
G
1
×
G
2
→
G
T is called a bilinear map if it satisfies the following properties:(
1
)
Bilinearity: it holds that(3)
e
^
g
α
,
h
β
=
e
^
g
,
h
α
β
for allα
,
β
∈
Z
N.
(
2
)
Nondegeneracy: there existg
1
∈
G
1
,
h
1
∈
G
2 such that e
^
(
g
1
,
h
1
)
≠
1.
(
3
)
Computability: there exists an efficient algorithm to computee
^
(
g
1
,
h
1
) for any g
1
∈
G
1
,
h
1
∈
G
2.


## 2.3. Computational Assumptions

The computational assumption that is used for the construction of the PRF with closed form efficiency is decision linear (DL) assumption. We present the definition below.Definition 1 (decision linear assumption).
LetG be a group of prime order p. Given g
0
,
g
1
,
g
2
∈
G and r
0
,
r
1
,
r
2
∈
Z
p, one defines the advantage of an algorithm A in deciding the decision linear problem in G as(4)
A
d
v
A
d
l
=
P
r
A
p
,
g
0
,
g
1
,
g
2
,
g
1
r
1
,
g
2
r
2
,
g
0
r
1
+
r
2
=
1
-
P
r
A
p
,
g
0
,
g
1
,
g
2
,
g
1
r
1
,
g
2
r
2
,
g
0
r
0
=
1
.One says that the decision linear assumption (
t
,
ϵ
) holds in G if for every t-time algorithm A one has A
d
v
A
d
l
≤
ϵ.Note that the decision linear assumption holds in generic bilinear groups. Relative proof can be found in [26].Next we present the definition of co-CDH, which is the base for the security of our proposed schemes. The co-CDH assumption was first introduced in BLS signature scheme presented by Boneh et al. [27], as a natural extension of standard CDH problem in asymmetric bilinear pairing. It is defined as follows.Definition 2 (co-CDH assumption).
Let(
p
,
g
,
h
,
G
1
,
G
2
,
G
T
,
e
^
) be as above in Section 2.2. Given random a
,
b
∈
Z
p, one defines the advantage of an algorithm A in solving the co-CDH problem in G
1
,
G
2 as(5)
A
d
v
A
c
o
-
c
d
h
=
P
r
A
p
,
g
,
h
,
g
a
,
h
b
=
g
a
band one says that the co-CDH assumption (
t
,
ϵ
) holds in G
1
,
G
2 if for every t-time algorithm A one has A
d
v
A
c
o
-
c
d
h
≤
ϵ.Note that whenG
1
=
G
2, the co-CDH problem reduces to standard CDH.


## 3. Modelling CP-PVC

We use an amortized model [16] to construct our CP-PVC scheme. That is, the user (denoted by SU) shall invest a larger amount of computational work in a preprocessing phase in order to obtain efficiency during the computation outsourcing phase. The adversaries in a PVC protocol are two types, the cloud server (denoted by C
S) and some “curious” verifiers (denoted by C
V). The former is in lazy-but-honest model [28] and the latter is in honest-but-curious model. This is reasonable since, in practice, a rational commercial cloud service will try to minimize the computation it needs to do to pass the verification algorithm. And passing the verification algorithm is its priority because only in this way can it get the payback. Also since the verification is public, there will be some curious verifiers that perform the public verification algorithm and try to discover some secret information about the final result value.A difference between the framework of PVC proposed by Parno et al. [16] and ours is that we address the confidentiality of the computational result. In the public verification phase, a bit is output instead of the result value. And the result value is obtained in the later phase called private retrieval. To realize confidentiality, the user needs to operate the target function in the preprocessing phase and obtain a secret key for retrieval and keep it secret.LetF be a class of functions and F
∈
F. We define a confidentiality-preserving publicly verifiable computation (CP-PVC) protocol π via the following five algorithms:(i)
KeyGen
(
1
λ
,
F
)
→
(
S
K
F
,
E
K
F
,
P
P
): The randomized key generation algorithm takes as input a security parameter and the function F and as outputs a secret key S
K
F for the input delegation phase, an evaluation key E
K
F for the cloud server to compute the outsourced message, and the public parameter P
P. This is done by the client.
(ii)
ProbGen
(
P
P
,
S
K
F
,
x
)
→
(
σ
x
,
V
K
x
,
R
K
x
): Given the public parameter P
P, the secret key S
K
F, and the input value x
∈
D
o
m
a
i
n
(
F
), the randomized problem generation algorithm outputs a public value σ
x, which is the encoding of x, together with a public verification key V
K
x for nonclient parties to verify the correctness and a private retrieval key R
K
x for the client to retrieve final result F
(
x
). This is done by the client.
(iii)
Compute
(
E
K
F
,
σ
x
)
→
σ
o
u
t: On inputting the evaluation key E
K
F together with the value σ
x, the randomized computation algorithm outputs a value σ
o
u
t. This is done by the worker (cloud server).
(iv)
PubVer
(
P
P
,
V
K
x
,
σ
o
u
t
)
→
{
a
c
c
e
p
t
,
r
e
j
e
c
t
}: The deterministic public verification algorithm uses the public parameter P
P and public verification key V
K
x to check whether the final result is correct and returns a
c
c
e
p
t or r
e
j
e
c
t accordingly. This is done by the nonclient verifiers.
(v)
PrivRet
(
P
P
,
V
K
x
,
R
K
x
,
σ
o
u
t
)
→
y: The deterministic private retrieval algorithm is run on input P
P, V
K
x,R
K
x, and σ
o
u
t to compute a string y
∈
0,1
∗
∪
{
⊥
}. Here, the special symbol ⊥ indicates that the public verification algorithm rejects the worker’s answer σ
o
u
t. This is done by the client.A verifiable computation scheme should be both correct and secure. We give the definition of correctness and security in the following.Definition 3 (correctness).
A confidentiality-preserving publicly verifiable computation protocolπ is correct for a class of functions F if, for any F from F, any tuple (
S
K
F
,
E
K
F
,
P
P
) output byKeyGen
(
1
λ
,
F
), any x chosen fromDomain
(
F
), any tuple (
σ
x
,
V
K
x
,
R
K
x
) output byProbGen
(
P
P
,
S
K
F
,
x
), and any σ
o
u
t output byCompute
(
E
K
F
,
σ
x
), thePubVer algorithm on input (P
P
,
V
K
x
,
σ
o
u
t) outputs a
c
c
e
p
t, and thePrivRet algorithm on input P
P
,
V
K
x
,
R
K
x, and σ
o
u
t outputs y
=
F
(
x
).The security of a verifiable computation requires that the worker is not able to output an incorrect value that passes thePubVer or thePrivRet algorithm. We give the formal definition via the following experiment.Definition 4 (security).
Letπ be a confidentiality-preserving publicly verifiable computation scheme for a class of functions F, and assume that A is PPT adversaries. Consider Experiment E
X
P
A
[
π
,
F
,
λ
] for any F
∈
F below:E
x
p
e
r
i
m
e
n
t
E
X
P
A
[
π
,
F
,
λ
]
K
e
y
G
e
n
(
1
λ
,
F
)
→
$
(
S
K
F
,
E
K
F
,
P
P
);
F
o
r
i
=
1 to q,
A
(
P
P
,
E
K
F
,
σ
x
,
1
,
V
K
x
,
1
,
…
,
σ
x
,
i
-
1
,
V
K
x
,
i
-
1
)
→
x
i;
P
r
o
b
G
e
n
(
P
P
,
S
K
F
,
x
i
)
→
$
(
σ
x
i
,
V
K
x
i
,
R
K
x
i
);
A
(
P
P
,
E
K
F
,
σ
x
,
1
,
V
K
x
,
1
,
…
,
σ
x
,
q
,
V
K
x
,
q
)
→
x
∗;
P
r
o
b
G
e
n
(
P
P
,
S
K
F
,
x
∗
)
→
$
(
σ
x
∗
,
V
K
x
∗
,
R
K
x
∗
);
A
(
σ
x
∗
,
V
K
x
∗
)
→
(
σ
o
u
t
∗
);
P
u
b
V
e
r
V
K
x
∗
,
σ
o
u
t
∗
→
k;
P
r
i
v
R
e
t
(
σ
o
u
t
∗
,
V
K
x
∗
,
R
K
x
∗
)
→
y
∗;
I
f
k
=
a
c
c
e
p
t
a
n
d
y
∗
≠
F
(
x
∗
)
,
o
u
t
p
u
t
1
;
e
l
s
e
o
u
t
p
u
t
0
.
A confidentiality-preserving publicly verifiable computation schemeπ is secure for a class of functions F, if, for any F from F and any PPT adversary A, it holds that(6)
P
r
E
X
P
A
π
,
F
,
λ
=
1
≤
n
e
g
l
λ
.Here n
e
g
l represents a negligible function in λ.Next we give the confidentiality definition of CP-PVC which is not defined in existing PVC frameworks [2, 16]. In this paper we focus on the confidentiality for final result, which means that the adversaries cannot learn any information about the value y
=
F
(
x
) from the value σ
o
u
t output byCompute algorithm. Here the adversaries refer to the cloud server and any nonclient verifier. Since the cloud server has extra knowledge of the evaluation key compared with the nonclient verifiers, we only need to define the result confidentiality to cloud server. And the confidentiality to cloud server implicitly implies the confidentiality to nonclient verifiers. Notice that we do not emphasize the input privacy as a necessity in publicly verifiable computation. This is because, in some scenarios, input data is obtained from some public sources that can be accessed by anyone. However, we still present a loose definition on input privacy for multivariate function, which we call (
δ
-
ϵ
)-privacy. Intuitively, it means that, for a function with an input set of multi-independent variables, the probability that the adversary leans the values of a δ fraction of the input sets is ϵ. The definitions are as follows.Definition 5 (result confidentiality).
A confidentiality-preserving publicly verifiable computation protocolπ is result-confidential for a class of functions F if, for any F from F, any tuple (
S
K
F
,
E
K
F
,
P
P
) output byKeyGen
(
1
λ
,
F
), any x chosen fromDomain
(
F
), any tuple (
σ
x
,
V
K
x
,
R
K
x
) output byProbGen
(
P
P
,
S
K
F
,
x
), any σ
o
u
t output byCompute
(
E
K
F
,
σ
x
), and any PPT adversary A, it holds that(7)
P
r
A
P
P
,
E
K
F
,
V
K
x
,
σ
x
,
σ
o
u
t
=
F
x
≤
n
e
g
l
λ
.Definition 6 (δ
-
ϵ input privacy).
A confidentiality-preserving publicly verifiable computation protocolπ for a class of multivariate functions F achieves δ
-
ϵ input privacy if, for any F from F, any tuple (
S
K
F
,
E
K
F
,
P
P
) output byKeyGen
(
1
λ
,
F
), any input set x
=
x
i
1
≤
i
≤
m chosen fromDomain
(
F
), any tuple (
σ
x
,
V
K
x
,
R
K
x
) output byProbGen
(
P
P
,
S
K
F
,
x
), any σ
o
u
t output byCompute
(
E
K
F
,
σ
x
), and any PPT adversary A, it holds that(8)
P
r
A
P
P
,
E
K
F
,
V
K
x
,
σ
x
,
σ
o
u
t
=
x
j
1
≤
j
≤
m
′
∣
x
j
∈
x
,
m
′
>
δ
m
≤
ϵ
+
n
e
g
l
λ
.Finally, we give the definition of efficiency. Informally speaking, efficiency means that the total computational cost on the client side by engaging the CP-PVC scheme is less than that of executing the direct algorithm to compute the target function. In the amortized model, since theKeyGen is done once and amortized by multiple function evaluation with different input value, this part of computational overhead does not need to be counted in.Definition 7 (efficiency).
A confidentiality-preserving publicly verifiable computation protocolπ for a class of multivariate functions F is efficient if, for any F from F and any x chosen fromDomain
(
F
), the total computational cost of algorithmsProbGen andPrivRet is less than that of directly evaluating F on x.


## 4. The CP-PVC Scheme for Polynomial Evaluation

In this section, we first review the construction of PRF in [29], showing that it is closed form efficient for polynomials in m variables and degree at most d in each variable. Then we present the corresponding algorithm for evaluating the PRF and its closed form efficiency. After that, we give the concrete construction of our CP-PVC scheme for polynomial evaluation together with the analysis and experimental simulation.


### 4.1. Algorithm for PRF with Closed Form Efficiency

LetG be a group generator that takes as input a secure parameter λ and outputs a description of group with prime order. Consider any polynomial p
(
x
1
,
…
,
x
m
) that has m variables and degree at most d in each variable. Then the polynomial has totally l
=
(
d
+
1
)
m monomials. Index them with tuple (
i
1
,
…
,
i
m
), 0
≤
i
j
≤
d. We say that the construction of P
R
F
L
W
(
K
G
,
R
K
(
i
1
,
…
,
i
m
)
) admits the closed form efficiency for the following computation:(9)
P
o
l
y
r
i
1
,
…
,
i
m
0
≤
i
1
,
…
,
i
m
≤
d
,
x
1
,
…
,
x
m
=
∏
0
≤
i
1
,
…
,
i
m
≤
d
r
i
1
,
…
,
i
m
x
1
i
1
⋯
x
m
i
m
=
g
p
x
1
,
…
,
x
mwhere p
(
·
) is the polynomial whose coefficients are the discrete logs of the r values. If we set r
(
i
1
,
…
,
i
m
)
=
R
K
(
i
1
,
…
,
i
m
), then there exists an algorithm C
F
E
v
a
l
P
o
l
y
,
z
(
K
,
x
1
,
…
,
x
m
) that can compute(10)
g
p
x
1
,
…
,
x
m
=
∏
0
≤
i
1
,
…
,
i
m
≤
d
R
K
i
1
,
…
,
i
m
x
1
i
1
⋯
x
m
i
min time O
(
m
log
⁡
d
), instead of the regular running time O
(
d
m
·
m
log
⁡
d
).The proof of the above claim can be found in [2]. Here we show the algorithm for evaluating the PRF as well as the polynomial P
(
x
1
,
…
,
x
m
).Lets
=
log
⁡
d
+
1. The construction of PRF is the following algorithm:(i)
KG
(
1
λ
,
m
,
s
): Run G
(
1
λ
) to generate a group description (
p
,
g
,
G
1
). Choose 4
m
s
+
2 random values(11)
y
0
,
z
0
,
y
a
,
b
,
z
a
,
b
,
w
a
,
b
,
v
a
,
b
1
≤
a
≤
m
,
1
≤
b
≤
s
←
$
Z
p
.The algorithm outputs(12)
K
=
y
0
,
z
0
,
y
a
,
b
,
z
a
,
b
,
w
a
,
b
,
v
a
,
b
a
,
b
.The domain of the function is0
,
…
,
d
m, and the range is G
1.(ii)
R
K
(
·
): Let i
=
(
i
1
,
…
,
i
m
) be the input of the PRF. First interpret each i
j
=
(
i
j
,
1
,
…
,
i
j
,
s
) as a binary string of s bits. Then run Algorithm 1.Algorithm 1:PRF.
setR
K
1
(
i
)
=
y
0, R
K
2
(
i
)
=
z
0
for
j
=
1 to m: do
for
k
=
1 to s: do
if
i
j
,
k
=
0
then
R
K
1
(
i
)
=
R
K
1
(
i
), R
K
2
(
i
)
=
R
K
2
(
i
)
else
R
K
1
(
i
)
=
R
K
1
(
i
)
⋅
y
j
,
k
+
R
K
2
(
i
)
⋅
z
j
,
k
R
K
2
(
i
)
=
R
K
1
(
i
)
⋅
w
j
,
k
+
R
K
2
(
i
)
⋅
v
j
,
k
end if
end for
end for
return
g
R
K
1
(
i
)Finally, the value of the PRF isR
K
(
i
)
=
g
R
K
1
(
i
). Let x
=
(
x
1
,
…
,
x
m
) be the input; the polynomial p can be written as(13)
p
x
1
,
…
,
x
m
=
∑
0
≤
i
1
,
…
,
i
m
≤
d
R
K
1
i
1
,
…
,
i
m
x
1
i
1
⋯
x
m
i
m
.Now we present the algorithm for evaluating the computationg
p
(
x
1
,
…
,
x
m
) in Algorithm 2. The derivation and proof can be found in [2].Algorithm 2:
C
F
E
v
a
l
P
o
l
y
(
K
,
x
1
,
…
,
x
m
).
setp
1
(
x
)
=
y
0
,
p
2
(
x
)
=
z
0
for
j
=
1 to m: do
for
k
=
1 to s: do
p
1
(
x
)
=
p
1
(
x
)
+
x
j
2
k
-
1
(
p
1
(
x
)
⋅
y
j
,
k
+
p
2
(
x
)
⋅
z
j
,
k
)
p
2
(
x
)
=
p
2
(
x
)
+
x
j
2
k
-
1
(
p
1
(
x
)
⋅
w
j
,
k
+
p
2
(
x
)
⋅
v
j
,
k
)
end for
end for
return
g
p
1
(
x
)Finally, the value ofg
p
x
1
,
…
,
x
m
=
g
p
1
x. Note that the above algorithm makes totally m
s times recursive operation. Thus its running time is O
(
m
s
)
=
O
(
m
log
⁡
d
), much faster than the regular running time O
(
d
m
·
m
log
⁡
d
).With the use of the above closed form efficient PRF in Algorithm2, we can realize public verifiability by letting the PRF value be a part of the verification key. Then our remaining goal is to make this public verification process “blind”. Intuitively, to make the value F
(
x
) confidential, one way is to encrypt the input value x. This is usually done in verifiable computation schemes. However such operation requires the homomorphic property of the encryption scheme, and encryption schemes with better homomorphic property are usually less efficient. Therefore, here we consider the way to blind the target polynomial F. We use two sparse m-variate polynomials A
(
x
) and B
(
x
) to randomize the target polynomial. Here sparse means that the degree of the polynomial is 1 and there are at most m terms of monomials that are nonzero. Thus the value of F
(
x
) is covered under A
(
x
) and B
(
x
), and the computational overhead of A
(
x
) and B
(
x
) is O
(
m
).


### 4.2. Construction of CP-PVC for Polynomial Case

Now, we present our concrete scheme of CP-PVC for multivariate polynomialsF with m variables and degree at most d
′ of each variable. In the case, F has totally at most w
=
d
′
+
1
m terms of monomial. Assume T
(
x
)
=
A
(
x
)
F
(
x
)
+
B
(
x
). Let the degree of each variable be at most d and the total terms of monomial be l
=
d
+
1
m, and for 1
≤
j
T
≤
l write j
T
=
i
1
T
,
…
,
i
m
T with 0
≤
i
k
T
≤
d; then we can represent T
(
x
) by ∑
j
T
=
1
l
t
^
j
T
·
t
j
T
(
x
), where t
j
T
(
x
) represents each monomial and t
^
j
T represents the coefficient correspondingly. Similarly, represent A
(
x
) and B
(
x
) by ∑
j
A
=
1
2
m
a
^
j
A
·
a
j
A
(
x
) and ∑
j
B
=
1
2
m
b
^
j
B
·
b
j
B
(
x
), respectively. The CP-PVC scheme works as follows:KeyGen: For parameter λ, the client runs a bilinear group generator G
e
(
1
λ
) to generate a bilinear tuple (
p
,
g
,
h
,
G
1
,
G
2
,
G
T
,
e
^
). Choose a tuple a
^
j
A
,
b
^
j
B
1
≤
j
A
,
j
B
≤
2
m
←
$
G
1.
The client runs PRF key generation algorithmKG
(
1
λ
,
⌊
log
⁡
d
⌋
+
1
,
m
) to generate a key K and the range in G
1. Choose a random α
∈
Z
p, and compute(14)
E
j
T
=
g
α
·
t
^
j
T
·
R
K
j
T
,
∀
j
T
=
1
,
…
,
l
.
LetE
=
(
E
1
,
…
,
E
l
)
∈
G
1
l. The algorithm outputs(15)
S
K
F
=
K
,
a
^
j
A
,
b
^
j
B
1
≤
j
A
,
j
B
≤
2
m
,
E
K
F
=
T
,
E
,
P
P
=
e
g
,
h
α
,
e
.
ProbGen: On inputting S
K
F
=
(
K
,
a
^
j
A
,
b
^
j
B
1
≤
j
A
,
j
B
≤
2
m
), P
P
=
(
e
g
,
h
α
,
e
), and owning x, the client computes A
(
x
),B
(
x
) and C
F
E
v
a
l
P
o
l
y
(
K
,
x
1
,
…
,
x
m
)
=
g
R
(
x
). The algorithm outputs(16)
σ
x
=
x
,
V
K
x
=
e
g
R
x
,
h
,
R
K
x
=
A
x
,
B
x
.
Compute: On receiving E
K
F
=
(
T
,
E
) and σ
x
=
x, the cloud server computes y
′
=
T
(
x
)
=
∑
j
T
=
1
l
t
^
j
T
·
t
j
T
(
x
), V
=
∏
j
T
=
1
l
E
j
T
t
j
T
(
x
) and outputs(17)
σ
o
u
t
=
y
′
,
V
.
PubVer: On receiving V
K
x
=
e
(
g
R
(
x
)
,
h
) and σ
o
u
t
=
(
y
′
,
V
), the verifier checks the equation(18)
e
V
,
h
=
e
g
,
h
α
y
′
·
V
K
x
.
The algorithm outputsa
c
c
e
p
t if the above equation holds; otherwise it outputs r
e
j
e
c
t.
PrivRet: On receiving V
K
x
=
e
(
g
R
(
x
)
,
h
), σ
o
u
t
=
(
y
,
V
), and owning R
K
x
=
(
A
(
x
)
,
B
(
x
)
), the algorithm first runs thePubVer algorithm with V
K
x and σ
o
u
t. If thePubVer outputs a
c
c
e
p
t, then compute y
=
(
y
′
-
B
(
x
)
)
/
A
(
x
) and return y as the output.


### 4.3. Security Analysis

Now we analyze the correctness, security, and confidentiality of the proposed CP-PVC scheme.


#### 4.3.1. Correctness

Correctness is easy to prove. Letσ
o
u
t
,
V
K
x
,
R
K
x be as above; then(19)
e
V
,
h
=
e
∏
j
T
=
1
l
E
j
T
t
j
T
x
,
h
=
e
∏
j
T
=
1
l
g
α
·
t
^
j
T
·
R
K
j
T
t
j
T
x
,
h
=
e
g
α
T
x
,
h
·
e
g
R
x
,
h
=
e
g
,
h
α
y
′
·
V
K
x
.The above proves the correctness for evaluatingy
′
=
T
(
x
), and this implies the correctness of y
=
(
y
′
-
B
(
x
)
)
/
A
(
x
)
=
F
(
x
).


#### 4.3.2. Confidentiality

We show that, for an adversarial cloud server with the information of(
P
P
,
E
K
F
,
V
K
x
,
σ
x
,
σ
o
u
t
), the probability that it can extract the value of the result y is negligible; i.e., the result confidentiality holds for cloud server. This implies that the confidentiality also holds for any third party verifier since they have less information (E
K
F) than the cloud server does. To extract y
=
F
(
x
), one way is directly from T
(
x
). However, this requires the knowledge of (
A
(
x
)
,
B
(
x
)
) which are parts of the retrieval key and kept secret. The other way is to discover the coefficients of the function F
(
·
) and evaluate F on x since the input value x is a plain text stored in σ
x. We will show that under this circumstance the adversary cannot discover the coefficients of F with a nonnegligible probability. Let A
,
B
,
F be as follows:(20)
A
x
=
∑
j
A
=
1
2
m
a
^
j
A
·
a
j
A
x
B
x
=
∑
j
B
=
1
2
m
b
^
j
B
·
b
j
B
x
F
x
=
∑
j
F
=
1
d
′
+
1
m
f
^
j
F
·
f
j
F
xand then we have that(21)
T
x
=
A
x
F
x
+
B
x
=
∑
j
T
=
1
2
m
∑
j
T
=
j
A
+
j
F
a
^
j
A
f
^
j
F
+
b
^
j
B
t
j
T
x
+
∑
j
T
=
2
m
+
1
l
∑
j
T
=
j
A
+
j
F
a
^
j
A
f
^
j
F
t
j
T
x
=
∑
j
T
=
1
l
t
^
j
T
t
j
T
x
.Comparing the coefficients and setting2
m
=
s of the above equation, we get a system(22)
∑
j
A
+
j
F
=
1
a
^
j
A
f
^
j
F
+
b
^
1
=
t
^
1
⋮
∑
j
A
+
j
F
=
s
a
^
j
A
f
^
j
F
+
b
^
s
=
t
^
s
∑
j
A
+
j
F
=
s
+
1
a
^
j
A
f
^
j
F
=
t
^
s
+
1
⋮
∑
j
A
+
j
F
=
l
a
^
j
A
f
^
j
F
=
t
^
l
.Note that the above system does not have a unique solution inG
1, and the coefficients of A
(
·
) and B
(
·
) are chosen uniformly at random from G
1. This means that the probability to choose the correct coefficients is negligible, and thus the privacy of coefficients of F
(
·
) is guaranteed, which makes the confidentiality of the final result hold.


#### 4.3.3. Security

The security of the scheme is based on co-CDH assumption and the corresponding proof follows from that in [2]. We take it as an inspiration and define the following four games.Game 0.
It is the same asE
x
p
e
r
i
m
e
n
t
E
X
P
A
[
π
,
F
,
λ
].Game 1.
It is similar to Game 0, with the difference thatE
K
F contains coefficients randomly chosen from G
1 instead of T.Game 2.
It is similar to Game 1, with the difference that theProbGen phase uses an inefficient algorithm ∏
j
T
=
1
l
R
K
(
j
T
)
t
j
T
(
x
) instead of the C
F
E
v
a
l
P
o
l
y
(
K
,
x
1
,
…
,
x
m
) to evaluate V
K
x.Game 3.
It is similar to Game 2, with the difference that each valueR
K
(
j
T
) is replaced by a random element R
j
T
∈
G
1.We use a hybrid way to perform the proof, with the following claims.Corollary 4.
P
r
G
0
A
=
1
=
P
r
G
1
A
=
1.Proof.
This claim holds in an obvious way, since the change of algorithm for evaluatingV
K
X does not change the distribution of its values. Thus the probability that the adversary wins is the same in both Games 0 and 1.Corollary 5.
P
r
G
1
A
=
1
=
P
r
G
2
A
=
1.Proof.
The difference between Games 2 and 1 is the coefficients of the target function. According to the confidentiality proof, these coefficients are indistinguishable sinceA and B are chosen uniformly at random, thus sharing the same distribution in the view of the adversary.Corollary 6.
|
P
r
G
2
A
=
1
=
P
r
G
3
A
=
1
|
≤
ϵ
p
r
f, where ϵ
p
r
f represents the probability in the pseudorandomness definition of PRF.Proof.
The difference between Games 3 and 2 is that the output of PRFR
K
(
x
) is replaced by uniformly random elements in G
1. According to the pseudorandomness property of PRF, the probability that an adversary A distinguishes the two values is no better than ϵ
p
r
f.Corollary 7.
P
r
G
3
A
=
1
≤
ϵ
c
d
h, whereϵ
c
d
hrepresents the probability that an adversary solves co-CDH problem.Proof.
To prove this claim we need to show that if there exists a PPT algorithm that wins in Game 3 with a probability larger thanϵ
c
d
h, then one can build an efficient algorithm B with oracle access to A to solve the co-CDH problem with some nonnegligible probability. Assume that the group in co-CDH problem is described as (
p
,
g
,
h
,
G
1
,
G
2
,
G
T
,
e
^
) and the adversary is given a co-CDH tuple (
g
a
,
h
b
) with the exponents a
,
b chosen randomly from Z
p; the algorithm B works as follows.
First,B needs to simulate public parameter P
P and evaluation key E
K
F. It computes the bilinear map e
(
g
a
,
h
b
) and chooses 2
l random elements t
^
j
T
,
E
j
T
1
≤
j
T
≤
l. The simulated public key P
P
=
(
e
(
g
a
,
h
b
)
,
e
), and the simulated evaluation key E
K
F
=
(
T
,
E
)
=
t
^
j
T
,
W
j
T
1
≤
j
T
≤
l. Since the W generated in Game 3 contains a PRF as a factor and the PRF enjoys pseudorandomness, it is clear that the P
P and E
K
F generated above enjoy a perfect distribution as that in Game 3.
Second,B gives the simulated P
P and E
K
F to A and prepares to simulate the answers to the queries from A. A difference here is that B does not need to generate the retrieval key R
K in querying phase as that in Game 3 because A does not have access to R
K, neither does B need this R
K to solve the co-CDH problem. Let x
i
(
1
≤
i
≤
q
) be the querying value. B first computes U
j
T
=
e
(
E
j
T
,
h
)
/
e
g
a
,
h
b
t
^
j
T and then computes V
K
x
i
=
∏
j
T
=
1
l
U
j
T
t
j
T
(
x
i
). Since in Game 3,(23)
e
E
j
T
,
h
e
g
α
,
h
t
^
j
T
=
R
K
j
T
,combining the bilinear property of map e, it is clear that the simulated V
K
x
i also enjoys a perfect distribution as that in Game 3. A is then given the corresponding verification key V
K
x
i. Let x
∗ be the challenge value chosen by A. The above process is repeated and A obtains V
K
x
∗.
Finally,A will output a tuple σ
^
o
u
t
∗
=
(
y
^
,
V
^
) such that(24)
P
u
b
V
e
r
V
K
x
∗
,
σ
o
u
t
∗
⟶
k
,
P
r
i
v
R
e
t
σ
o
u
t
∗
,
V
K
x
∗
,
R
K
x
∗
⟶
y
∗
,
wherek
=
a
c
c
e
p
t and y
∗
≠
F
(
x
∗
). Due to the correctness property, this y
∗
≠
F
(
x
∗
) also implies that y
^
≠
T
(
x
∗
). By k
=
a
c
c
e
p
t we obtain that(25)
e
V
^
,
h
=
e
g
a
,
h
b
y
^
·
V
K
x
∗
.Let y
=
F
(
x
∗
) be the correct output of the PrivRet algorithm. Then by correctness we know y
′
=
T
(
x
∗
) is also correct. Thus the following equation also holds:(26)
e
V
,
h
=
e
g
a
,
h
b
y
′
·
V
K
x
∗
,where V
=
∏
j
T
=
1
l
E
j
T
t
j
T
(
x
∗
).
Dividing (25) and (26) and combining bilinear property, we can obtain that(27)
e
V
^
V
,
h
=
e
g
a
b
,
h
y
^
-
y
′
.Then B can compute g
a
b
=
(
V
^
/
V
)
1
/
(
y
^
-
y
′
). Thus, if A wins Game 3 with probability ϵ
c
d
h, B solves the co-CDH problem with the same probability. This proves Claim 4.Combining the four claims together, we obtain that(28)
P
r
E
X
P
A
π
,
F
,
λ
=
1
≤
ϵ
p
r
f
+
ϵ
c
d
h
.


### 4.4. Performance Analysis

In this subsection, we analyze the computational complexity of the proposed scheme and compare it with some existing works [2, 19]. Our scheme is efficient in the amortized model. That is, the expensiveKeyGen algorithm is executed once and its computational overhead is amortized by the following evaluation of the polynomial function with different input value. Here the structure of the function cannot be changed unless anotherKeyGen algorithm for a different function is performed. Now we give detailed analysis on the computational costs of each algorithm. Let each letter denote the same item as that in the proposed scheme above. In theKeyGen phase, to compute the term E
j
T, the client needs to execute 2
d
′
+
2
m
+
1 times of exponential modulo and d
′
+
1
m times of multiplication arithmetic in group G
1. To compute the structure of function T
(
·
), 2
d
′
+
1
m times of multiplication and 2
m times of addition arithmetic in N are executed. To generate the public key, one time of pairing arithmetic is executed. In theProbGen phase, no execution needs to be done to generate σ
x since σ
x remains the same as input x. To generate the public verification key V
K
x, algorithm C
F
E
v
a
l
P
o
l
y
(
·
) is executed together with one time pairing arithmetic. And to generate the private retrieval key, the client needs to execute two times of (m-variate, 1-degree) sparse polynomial evaluation arithmetic. In theCompute phase, the cloud server needs to execute one time of (m-variate,d
′
+
1-degree) polynomial evaluation arithmetic to compute y
′ and d
′
+
2
m times of exponential modulo in group G
1 to compute term V. In thePubVer phase, to compute the corresponding terms in the checking equation, the third party verifier needs to execute one time of pairing arithmetic, one time of exponential modulo arithmetic in G
T, and one time of multiplication arithmetic in G
T, respectively. Finally, in thePrivRet phase, the client firstly needs to execute what is done inPubVer phase and then execute, respectively, one time of subtraction and division arithmetic in N to compute the result y.We present a complexity comparison between our scheme and existing works of PVC schemes for polynomial evaluation [2, 19]. After analyzing the specific arithmetic of each algorithm, We would like to use the notation O to compare computational complexity. Since the arithmetic operations in different groups are the same, we use three types of notation, O
I,O
N, and O
E, to classify different types of complexity. O
I denotes the time complexity of operations in ring Z
p including integer addition and multiplication modulo prime p. O
N denotes the time complexity of operations in ring N including addition and multiplication. O
E denotes the time complexity of operations in group G
1, G
2, G
T including multiplication, exponentiation, and bilinear map. The comparison result is shown in Table 1. From the table we can see that, compared with the scheme in [2], ours has a complexity increase of O
N
(
d
′
m
) inKeyGen, O
N
(
m
) inProbGen, and O
N
(
1
) inPrivRet performed by the client. However, since the most expensive arithmetic in each of the three phases is O
E
(
d
′
m
), O
I
(
m
log
⁡
d
′
), and O
E
(
1
), respectively, the impact of the increasing complexity will not be obvious in the real performance. Compared with the scheme in [19], we first notice that the scheme in [19] only works for univariate case, while ours works for multivariate case. If we set “m
=
1”, the complexity of the two schemes is nearly the same, with a small increase of O
N
(
1
) inProbGen andPrivRet, respectively, which is not the most expensive part in the two phases. By doing so, our scheme achieves a security property-result confidentiality that is considered to be important for user privacy.Table 1
Comparison of the three PVC schemes for polynomial evaluation.
FG12 [2]
EOA16 [19]
Ours
Problem size
m-variate, d
′-degree
univariate,d
′-degree
m-variate, d
′-degree
KeyGen
O
E
(
d
′
m
)
O
E
(
d
′
)
+
O
N
(
d
′
)
O
E
(
d
′
m
)
+
O
N
(
d
′
m
)
ProbGen
O
E
(
1
)
+
O
I
(
m
log
⁡
d
′
)
O
E
(
1
)
+
O
I
(
1
)
O
E
(
1
)
+
O
I
(
m
log
⁡
d
′
)
+
O
N
(
m
)
Compute
O
E
(
d
′
m
)
+
O
N
(
d
′
m
)
O
E
(
d
′
)
+
O
N
(
d
′
)
O
E
(
d
′
m
)
+
O
N
(
d
′
m
)
PubVer
O
E
(
1
)
O
E
(
1
)
O
E
(
1
)
PrivRet
⊥
⊥
O
E
(
1
)
+
O
N
(
1
)
Result confidentiality
No
No
YesWe also provide some experimental simulation of CP-PVC for polynomial to show the efficiency. Intuitively, efficiency means that the total computational overhead on the client side by engaging an outsourcing computation protocol is less than that by directly executing the target function algorithm. Since our scheme is constructed in an amortized model, i.e., the computations inKeyGen need to be done only once, we will not count that part of computation in the efficiency performance. Then for the client side, all the computation costs that are counted containProbGen andPrivRet phase. We implement the corresponding algorithms on the client side using MATLAB 2015 on a computer with Intel(R) Core(TM) i7-4790 CPU processor running at 3.60 GHz and 8 GB RAM. We show the time cost for different sizes of problems in Table 2, where m represents variable number and s represents bit length of the highest degree d
′. This part of work is done in the previous conference version of this paper [24].Table 2
Times cost of the client [24].
m
s
=
10
s
=
50
s
=
200
s
=
1000
1000
0.0312s
0.0936s
0.1248s
0.4836s
5000
0.0624s
0.1716s
0.4836s
2.1372s
20000
0.1872s
0.5304s
1.7628s
8.3304s
100000
0.5460s
2.3712s
8.5956s
41.7614sFor comparison of efficiency, we also do some evaluation using the direct algorithmF
(
x
)
=
∑
j
F
=
1
w
f
^
j
F
·
f
j
F
(
x
), where f
j
F
(
x
) represents each monomial for polynomial F and w
=
2
s
+
1
m. The corresponding result is shown in Table 3, which is also done in the previous conference version [24]. We see that the cost time is already infinite when the case goes to s
=
50. This is reasonable because theoretically the complexity of the direct algorithm is O
(
m
·
2
s
). Recalling that the complexity of the way using closed form efficient PRF is O
(
m
s
), thus the scheme achieves a log time efficiency promoted for the evaluation of multivariate polynomials. We show in Figure 1 a time cost comparison between direct algorithm and outsourcing algorithm, in which case s
=
10; i.e., the degree of each variate is 2
10. This is also done in the previous conference version [24].Table 3
Times cost of direct algorithm [24].
m
s
=
10
s
=
50
s
=
200
s
=
1000
1000
3.28s
∞
∞
∞
5000
6.55s
∞
∞
∞
20000
19.65s
∞
∞
∞
100000
59.24s
∞
∞
∞Figure 1
Time cost of different problem sizes [24].


## 4.1. Algorithm for PRF with Closed Form Efficiency

LetG be a group generator that takes as input a secure parameter λ and outputs a description of group with prime order. Consider any polynomial p
(
x
1
,
…
,
x
m
) that has m variables and degree at most d in each variable. Then the polynomial has totally l
=
(
d
+
1
)
m monomials. Index them with tuple (
i
1
,
…
,
i
m
), 0
≤
i
j
≤
d. We say that the construction of P
R
F
L
W
(
K
G
,
R
K
(
i
1
,
…
,
i
m
)
) admits the closed form efficiency for the following computation:(9)
P
o
l
y
r
i
1
,
…
,
i
m
0
≤
i
1
,
…
,
i
m
≤
d
,
x
1
,
…
,
x
m
=
∏
0
≤
i
1
,
…
,
i
m
≤
d
r
i
1
,
…
,
i
m
x
1
i
1
⋯
x
m
i
m
=
g
p
x
1
,
…
,
x
mwhere p
(
·
) is the polynomial whose coefficients are the discrete logs of the r values. If we set r
(
i
1
,
…
,
i
m
)
=
R
K
(
i
1
,
…
,
i
m
), then there exists an algorithm C
F
E
v
a
l
P
o
l
y
,
z
(
K
,
x
1
,
…
,
x
m
) that can compute(10)
g
p
x
1
,
…
,
x
m
=
∏
0
≤
i
1
,
…
,
i
m
≤
d
R
K
i
1
,
…
,
i
m
x
1
i
1
⋯
x
m
i
min time O
(
m
log
⁡
d
), instead of the regular running time O
(
d
m
·
m
log
⁡
d
).The proof of the above claim can be found in [2]. Here we show the algorithm for evaluating the PRF as well as the polynomial P
(
x
1
,
…
,
x
m
).Lets
=
log
⁡
d
+
1. The construction of PRF is the following algorithm:(i)
KG
(
1
λ
,
m
,
s
): Run G
(
1
λ
) to generate a group description (
p
,
g
,
G
1
). Choose 4
m
s
+
2 random values(11)
y
0
,
z
0
,
y
a
,
b
,
z
a
,
b
,
w
a
,
b
,
v
a
,
b
1
≤
a
≤
m
,
1
≤
b
≤
s
←
$
Z
p
.The algorithm outputs(12)
K
=
y
0
,
z
0
,
y
a
,
b
,
z
a
,
b
,
w
a
,
b
,
v
a
,
b
a
,
b
.The domain of the function is0
,
…
,
d
m, and the range is G
1.(ii)
R
K
(
·
): Let i
=
(
i
1
,
…
,
i
m
) be the input of the PRF. First interpret each i
j
=
(
i
j
,
1
,
…
,
i
j
,
s
) as a binary string of s bits. Then run Algorithm 1.Algorithm 1:PRF.
setR
K
1
(
i
)
=
y
0, R
K
2
(
i
)
=
z
0
for
j
=
1 to m: do
for
k
=
1 to s: do
if
i
j
,
k
=
0
then
R
K
1
(
i
)
=
R
K
1
(
i
), R
K
2
(
i
)
=
R
K
2
(
i
)
else
R
K
1
(
i
)
=
R
K
1
(
i
)
⋅
y
j
,
k
+
R
K
2
(
i
)
⋅
z
j
,
k
R
K
2
(
i
)
=
R
K
1
(
i
)
⋅
w
j
,
k
+
R
K
2
(
i
)
⋅
v
j
,
k
end if
end for
end for
return
g
R
K
1
(
i
)Finally, the value of the PRF isR
K
(
i
)
=
g
R
K
1
(
i
). Let x
=
(
x
1
,
…
,
x
m
) be the input; the polynomial p can be written as(13)
p
x
1
,
…
,
x
m
=
∑
0
≤
i
1
,
…
,
i
m
≤
d
R
K
1
i
1
,
…
,
i
m
x
1
i
1
⋯
x
m
i
m
.Now we present the algorithm for evaluating the computationg
p
(
x
1
,
…
,
x
m
) in Algorithm 2. The derivation and proof can be found in [2].Algorithm 2:
C
F
E
v
a
l
P
o
l
y
(
K
,
x
1
,
…
,
x
m
).
setp
1
(
x
)
=
y
0
,
p
2
(
x
)
=
z
0
for
j
=
1 to m: do
for
k
=
1 to s: do
p
1
(
x
)
=
p
1
(
x
)
+
x
j
2
k
-
1
(
p
1
(
x
)
⋅
y
j
,
k
+
p
2
(
x
)
⋅
z
j
,
k
)
p
2
(
x
)
=
p
2
(
x
)
+
x
j
2
k
-
1
(
p
1
(
x
)
⋅
w
j
,
k
+
p
2
(
x
)
⋅
v
j
,
k
)
end for
end for
return
g
p
1
(
x
)Finally, the value ofg
p
x
1
,
…
,
x
m
=
g
p
1
x. Note that the above algorithm makes totally m
s times recursive operation. Thus its running time is O
(
m
s
)
=
O
(
m
log
⁡
d
), much faster than the regular running time O
(
d
m
·
m
log
⁡
d
).With the use of the above closed form efficient PRF in Algorithm2, we can realize public verifiability by letting the PRF value be a part of the verification key. Then our remaining goal is to make this public verification process “blind”. Intuitively, to make the value F
(
x
) confidential, one way is to encrypt the input value x. This is usually done in verifiable computation schemes. However such operation requires the homomorphic property of the encryption scheme, and encryption schemes with better homomorphic property are usually less efficient. Therefore, here we consider the way to blind the target polynomial F. We use two sparse m-variate polynomials A
(
x
) and B
(
x
) to randomize the target polynomial. Here sparse means that the degree of the polynomial is 1 and there are at most m terms of monomials that are nonzero. Thus the value of F
(
x
) is covered under A
(
x
) and B
(
x
), and the computational overhead of A
(
x
) and B
(
x
) is O
(
m
).


## 4.2. Construction of CP-PVC for Polynomial Case

Now, we present our concrete scheme of CP-PVC for multivariate polynomialsF with m variables and degree at most d
′ of each variable. In the case, F has totally at most w
=
d
′
+
1
m terms of monomial. Assume T
(
x
)
=
A
(
x
)
F
(
x
)
+
B
(
x
). Let the degree of each variable be at most d and the total terms of monomial be l
=
d
+
1
m, and for 1
≤
j
T
≤
l write j
T
=
i
1
T
,
…
,
i
m
T with 0
≤
i
k
T
≤
d; then we can represent T
(
x
) by ∑
j
T
=
1
l
t
^
j
T
·
t
j
T
(
x
), where t
j
T
(
x
) represents each monomial and t
^
j
T represents the coefficient correspondingly. Similarly, represent A
(
x
) and B
(
x
) by ∑
j
A
=
1
2
m
a
^
j
A
·
a
j
A
(
x
) and ∑
j
B
=
1
2
m
b
^
j
B
·
b
j
B
(
x
), respectively. The CP-PVC scheme works as follows:KeyGen: For parameter λ, the client runs a bilinear group generator G
e
(
1
λ
) to generate a bilinear tuple (
p
,
g
,
h
,
G
1
,
G
2
,
G
T
,
e
^
). Choose a tuple a
^
j
A
,
b
^
j
B
1
≤
j
A
,
j
B
≤
2
m
←
$
G
1.
The client runs PRF key generation algorithmKG
(
1
λ
,
⌊
log
⁡
d
⌋
+
1
,
m
) to generate a key K and the range in G
1. Choose a random α
∈
Z
p, and compute(14)
E
j
T
=
g
α
·
t
^
j
T
·
R
K
j
T
,
∀
j
T
=
1
,
…
,
l
.
LetE
=
(
E
1
,
…
,
E
l
)
∈
G
1
l. The algorithm outputs(15)
S
K
F
=
K
,
a
^
j
A
,
b
^
j
B
1
≤
j
A
,
j
B
≤
2
m
,
E
K
F
=
T
,
E
,
P
P
=
e
g
,
h
α
,
e
.
ProbGen: On inputting S
K
F
=
(
K
,
a
^
j
A
,
b
^
j
B
1
≤
j
A
,
j
B
≤
2
m
), P
P
=
(
e
g
,
h
α
,
e
), and owning x, the client computes A
(
x
),B
(
x
) and C
F
E
v
a
l
P
o
l
y
(
K
,
x
1
,
…
,
x
m
)
=
g
R
(
x
). The algorithm outputs(16)
σ
x
=
x
,
V
K
x
=
e
g
R
x
,
h
,
R
K
x
=
A
x
,
B
x
.
Compute: On receiving E
K
F
=
(
T
,
E
) and σ
x
=
x, the cloud server computes y
′
=
T
(
x
)
=
∑
j
T
=
1
l
t
^
j
T
·
t
j
T
(
x
), V
=
∏
j
T
=
1
l
E
j
T
t
j
T
(
x
) and outputs(17)
σ
o
u
t
=
y
′
,
V
.
PubVer: On receiving V
K
x
=
e
(
g
R
(
x
)
,
h
) and σ
o
u
t
=
(
y
′
,
V
), the verifier checks the equation(18)
e
V
,
h
=
e
g
,
h
α
y
′
·
V
K
x
.
The algorithm outputsa
c
c
e
p
t if the above equation holds; otherwise it outputs r
e
j
e
c
t.
PrivRet: On receiving V
K
x
=
e
(
g
R
(
x
)
,
h
), σ
o
u
t
=
(
y
,
V
), and owning R
K
x
=
(
A
(
x
)
,
B
(
x
)
), the algorithm first runs thePubVer algorithm with V
K
x and σ
o
u
t. If thePubVer outputs a
c
c
e
p
t, then compute y
=
(
y
′
-
B
(
x
)
)
/
A
(
x
) and return y as the output.


## 4.3. Security Analysis

Now we analyze the correctness, security, and confidentiality of the proposed CP-PVC scheme.


### 4.3.1. Correctness

Correctness is easy to prove. Letσ
o
u
t
,
V
K
x
,
R
K
x be as above; then(19)
e
V
,
h
=
e
∏
j
T
=
1
l
E
j
T
t
j
T
x
,
h
=
e
∏
j
T
=
1
l
g
α
·
t
^
j
T
·
R
K
j
T
t
j
T
x
,
h
=
e
g
α
T
x
,
h
·
e
g
R
x
,
h
=
e
g
,
h
α
y
′
·
V
K
x
.The above proves the correctness for evaluatingy
′
=
T
(
x
), and this implies the correctness of y
=
(
y
′
-
B
(
x
)
)
/
A
(
x
)
=
F
(
x
).


### 4.3.2. Confidentiality

We show that, for an adversarial cloud server with the information of(
P
P
,
E
K
F
,
V
K
x
,
σ
x
,
σ
o
u
t
), the probability that it can extract the value of the result y is negligible; i.e., the result confidentiality holds for cloud server. This implies that the confidentiality also holds for any third party verifier since they have less information (E
K
F) than the cloud server does. To extract y
=
F
(
x
), one way is directly from T
(
x
). However, this requires the knowledge of (
A
(
x
)
,
B
(
x
)
) which are parts of the retrieval key and kept secret. The other way is to discover the coefficients of the function F
(
·
) and evaluate F on x since the input value x is a plain text stored in σ
x. We will show that under this circumstance the adversary cannot discover the coefficients of F with a nonnegligible probability. Let A
,
B
,
F be as follows:(20)
A
x
=
∑
j
A
=
1
2
m
a
^
j
A
·
a
j
A
x
B
x
=
∑
j
B
=
1
2
m
b
^
j
B
·
b
j
B
x
F
x
=
∑
j
F
=
1
d
′
+
1
m
f
^
j
F
·
f
j
F
xand then we have that(21)
T
x
=
A
x
F
x
+
B
x
=
∑
j
T
=
1
2
m
∑
j
T
=
j
A
+
j
F
a
^
j
A
f
^
j
F
+
b
^
j
B
t
j
T
x
+
∑
j
T
=
2
m
+
1
l
∑
j
T
=
j
A
+
j
F
a
^
j
A
f
^
j
F
t
j
T
x
=
∑
j
T
=
1
l
t
^
j
T
t
j
T
x
.Comparing the coefficients and setting2
m
=
s of the above equation, we get a system(22)
∑
j
A
+
j
F
=
1
a
^
j
A
f
^
j
F
+
b
^
1
=
t
^
1
⋮
∑
j
A
+
j
F
=
s
a
^
j
A
f
^
j
F
+
b
^
s
=
t
^
s
∑
j
A
+
j
F
=
s
+
1
a
^
j
A
f
^
j
F
=
t
^
s
+
1
⋮
∑
j
A
+
j
F
=
l
a
^
j
A
f
^
j
F
=
t
^
l
.Note that the above system does not have a unique solution inG
1, and the coefficients of A
(
·
) and B
(
·
) are chosen uniformly at random from G
1. This means that the probability to choose the correct coefficients is negligible, and thus the privacy of coefficients of F
(
·
) is guaranteed, which makes the confidentiality of the final result hold.


### 4.3.3. Security

The security of the scheme is based on co-CDH assumption and the corresponding proof follows from that in [2]. We take it as an inspiration and define the following four games.Game 0.
It is the same asE
x
p
e
r
i
m
e
n
t
E
X
P
A
[
π
,
F
,
λ
].Game 1.
It is similar to Game 0, with the difference thatE
K
F contains coefficients randomly chosen from G
1 instead of T.Game 2.
It is similar to Game 1, with the difference that theProbGen phase uses an inefficient algorithm ∏
j
T
=
1
l
R
K
(
j
T
)
t
j
T
(
x
) instead of the C
F
E
v
a
l
P
o
l
y
(
K
,
x
1
,
…
,
x
m
) to evaluate V
K
x.Game 3.
It is similar to Game 2, with the difference that each valueR
K
(
j
T
) is replaced by a random element R
j
T
∈
G
1.We use a hybrid way to perform the proof, with the following claims.Corollary 4.
P
r
G
0
A
=
1
=
P
r
G
1
A
=
1.Proof.
This claim holds in an obvious way, since the change of algorithm for evaluatingV
K
X does not change the distribution of its values. Thus the probability that the adversary wins is the same in both Games 0 and 1.Corollary 5.
P
r
G
1
A
=
1
=
P
r
G
2
A
=
1.Proof.
The difference between Games 2 and 1 is the coefficients of the target function. According to the confidentiality proof, these coefficients are indistinguishable sinceA and B are chosen uniformly at random, thus sharing the same distribution in the view of the adversary.Corollary 6.
|
P
r
G
2
A
=
1
=
P
r
G
3
A
=
1
|
≤
ϵ
p
r
f, where ϵ
p
r
f represents the probability in the pseudorandomness definition of PRF.Proof.
The difference between Games 3 and 2 is that the output of PRFR
K
(
x
) is replaced by uniformly random elements in G
1. According to the pseudorandomness property of PRF, the probability that an adversary A distinguishes the two values is no better than ϵ
p
r
f.Corollary 7.
P
r
G
3
A
=
1
≤
ϵ
c
d
h, whereϵ
c
d
hrepresents the probability that an adversary solves co-CDH problem.Proof.
To prove this claim we need to show that if there exists a PPT algorithm that wins in Game 3 with a probability larger thanϵ
c
d
h, then one can build an efficient algorithm B with oracle access to A to solve the co-CDH problem with some nonnegligible probability. Assume that the group in co-CDH problem is described as (
p
,
g
,
h
,
G
1
,
G
2
,
G
T
,
e
^
) and the adversary is given a co-CDH tuple (
g
a
,
h
b
) with the exponents a
,
b chosen randomly from Z
p; the algorithm B works as follows.
First,B needs to simulate public parameter P
P and evaluation key E
K
F. It computes the bilinear map e
(
g
a
,
h
b
) and chooses 2
l random elements t
^
j
T
,
E
j
T
1
≤
j
T
≤
l. The simulated public key P
P
=
(
e
(
g
a
,
h
b
)
,
e
), and the simulated evaluation key E
K
F
=
(
T
,
E
)
=
t
^
j
T
,
W
j
T
1
≤
j
T
≤
l. Since the W generated in Game 3 contains a PRF as a factor and the PRF enjoys pseudorandomness, it is clear that the P
P and E
K
F generated above enjoy a perfect distribution as that in Game 3.
Second,B gives the simulated P
P and E
K
F to A and prepares to simulate the answers to the queries from A. A difference here is that B does not need to generate the retrieval key R
K in querying phase as that in Game 3 because A does not have access to R
K, neither does B need this R
K to solve the co-CDH problem. Let x
i
(
1
≤
i
≤
q
) be the querying value. B first computes U
j
T
=
e
(
E
j
T
,
h
)
/
e
g
a
,
h
b
t
^
j
T and then computes V
K
x
i
=
∏
j
T
=
1
l
U
j
T
t
j
T
(
x
i
). Since in Game 3,(23)
e
E
j
T
,
h
e
g
α
,
h
t
^
j
T
=
R
K
j
T
,combining the bilinear property of map e, it is clear that the simulated V
K
x
i also enjoys a perfect distribution as that in Game 3. A is then given the corresponding verification key V
K
x
i. Let x
∗ be the challenge value chosen by A. The above process is repeated and A obtains V
K
x
∗.
Finally,A will output a tuple σ
^
o
u
t
∗
=
(
y
^
,
V
^
) such that(24)
P
u
b
V
e
r
V
K
x
∗
,
σ
o
u
t
∗
⟶
k
,
P
r
i
v
R
e
t
σ
o
u
t
∗
,
V
K
x
∗
,
R
K
x
∗
⟶
y
∗
,
wherek
=
a
c
c
e
p
t and y
∗
≠
F
(
x
∗
). Due to the correctness property, this y
∗
≠
F
(
x
∗
) also implies that y
^
≠
T
(
x
∗
). By k
=
a
c
c
e
p
t we obtain that(25)
e
V
^
,
h
=
e
g
a
,
h
b
y
^
·
V
K
x
∗
.Let y
=
F
(
x
∗
) be the correct output of the PrivRet algorithm. Then by correctness we know y
′
=
T
(
x
∗
) is also correct. Thus the following equation also holds:(26)
e
V
,
h
=
e
g
a
,
h
b
y
′
·
V
K
x
∗
,where V
=
∏
j
T
=
1
l
E
j
T
t
j
T
(
x
∗
).
Dividing (25) and (26) and combining bilinear property, we can obtain that(27)
e
V
^
V
,
h
=
e
g
a
b
,
h
y
^
-
y
′
.Then B can compute g
a
b
=
(
V
^
/
V
)
1
/
(
y
^
-
y
′
). Thus, if A wins Game 3 with probability ϵ
c
d
h, B solves the co-CDH problem with the same probability. This proves Claim 4.Combining the four claims together, we obtain that(28)
P
r
E
X
P
A
π
,
F
,
λ
=
1
≤
ϵ
p
r
f
+
ϵ
c
d
h
.


## 4.3.1. Correctness

Correctness is easy to prove. Letσ
o
u
t
,
V
K
x
,
R
K
x be as above; then(19)
e
V
,
h
=
e
∏
j
T
=
1
l
E
j
T
t
j
T
x
,
h
=
e
∏
j
T
=
1
l
g
α
·
t
^
j
T
·
R
K
j
T
t
j
T
x
,
h
=
e
g
α
T
x
,
h
·
e
g
R
x
,
h
=
e
g
,
h
α
y
′
·
V
K
x
.The above proves the correctness for evaluatingy
′
=
T
(
x
), and this implies the correctness of y
=
(
y
′
-
B
(
x
)
)
/
A
(
x
)
=
F
(
x
).


## 4.3.2. Confidentiality

We show that, for an adversarial cloud server with the information of(
P
P
,
E
K
F
,
V
K
x
,
σ
x
,
σ
o
u
t
), the probability that it can extract the value of the result y is negligible; i.e., the result confidentiality holds for cloud server. This implies that the confidentiality also holds for any third party verifier since they have less information (E
K
F) than the cloud server does. To extract y
=
F
(
x
), one way is directly from T
(
x
). However, this requires the knowledge of (
A
(
x
)
,
B
(
x
)
) which are parts of the retrieval key and kept secret. The other way is to discover the coefficients of the function F
(
·
) and evaluate F on x since the input value x is a plain text stored in σ
x. We will show that under this circumstance the adversary cannot discover the coefficients of F with a nonnegligible probability. Let A
,
B
,
F be as follows:(20)
A
x
=
∑
j
A
=
1
2
m
a
^
j
A
·
a
j
A
x
B
x
=
∑
j
B
=
1
2
m
b
^
j
B
·
b
j
B
x
F
x
=
∑
j
F
=
1
d
′
+
1
m
f
^
j
F
·
f
j
F
xand then we have that(21)
T
x
=
A
x
F
x
+
B
x
=
∑
j
T
=
1
2
m
∑
j
T
=
j
A
+
j
F
a
^
j
A
f
^
j
F
+
b
^
j
B
t
j
T
x
+
∑
j
T
=
2
m
+
1
l
∑
j
T
=
j
A
+
j
F
a
^
j
A
f
^
j
F
t
j
T
x
=
∑
j
T
=
1
l
t
^
j
T
t
j
T
x
.Comparing the coefficients and setting2
m
=
s of the above equation, we get a system(22)
∑
j
A
+
j
F
=
1
a
^
j
A
f
^
j
F
+
b
^
1
=
t
^
1
⋮
∑
j
A
+
j
F
=
s
a
^
j
A
f
^
j
F
+
b
^
s
=
t
^
s
∑
j
A
+
j
F
=
s
+
1
a
^
j
A
f
^
j
F
=
t
^
s
+
1
⋮
∑
j
A
+
j
F
=
l
a
^
j
A
f
^
j
F
=
t
^
l
.Note that the above system does not have a unique solution inG
1, and the coefficients of A
(
·
) and B
(
·
) are chosen uniformly at random from G
1. This means that the probability to choose the correct coefficients is negligible, and thus the privacy of coefficients of F
(
·
) is guaranteed, which makes the confidentiality of the final result hold.


## 4.3.3. Security

The security of the scheme is based on co-CDH assumption and the corresponding proof follows from that in [2]. We take it as an inspiration and define the following four games.Game 0.
It is the same asE
x
p
e
r
i
m
e
n
t
E
X
P
A
[
π
,
F
,
λ
].Game 1.
It is similar to Game 0, with the difference thatE
K
F contains coefficients randomly chosen from G
1 instead of T.Game 2.
It is similar to Game 1, with the difference that theProbGen phase uses an inefficient algorithm ∏
j
T
=
1
l
R
K
(
j
T
)
t
j
T
(
x
) instead of the C
F
E
v
a
l
P
o
l
y
(
K
,
x
1
,
…
,
x
m
) to evaluate V
K
x.Game 3.
It is similar to Game 2, with the difference that each valueR
K
(
j
T
) is replaced by a random element R
j
T
∈
G
1.We use a hybrid way to perform the proof, with the following claims.Corollary 4.
P
r
G
0
A
=
1
=
P
r
G
1
A
=
1.Proof.
This claim holds in an obvious way, since the change of algorithm for evaluatingV
K
X does not change the distribution of its values. Thus the probability that the adversary wins is the same in both Games 0 and 1.Corollary 5.
P
r
G
1
A
=
1
=
P
r
G
2
A
=
1.Proof.
The difference between Games 2 and 1 is the coefficients of the target function. According to the confidentiality proof, these coefficients are indistinguishable sinceA and B are chosen uniformly at random, thus sharing the same distribution in the view of the adversary.Corollary 6.
|
P
r
G
2
A
=
1
=
P
r
G
3
A
=
1
|
≤
ϵ
p
r
f, where ϵ
p
r
f represents the probability in the pseudorandomness definition of PRF.Proof.
The difference between Games 3 and 2 is that the output of PRFR
K
(
x
) is replaced by uniformly random elements in G
1. According to the pseudorandomness property of PRF, the probability that an adversary A distinguishes the two values is no better than ϵ
p
r
f.Corollary 7.
P
r
G
3
A
=
1
≤
ϵ
c
d
h, whereϵ
c
d
hrepresents the probability that an adversary solves co-CDH problem.Proof.
To prove this claim we need to show that if there exists a PPT algorithm that wins in Game 3 with a probability larger thanϵ
c
d
h, then one can build an efficient algorithm B with oracle access to A to solve the co-CDH problem with some nonnegligible probability. Assume that the group in co-CDH problem is described as (
p
,
g
,
h
,
G
1
,
G
2
,
G
T
,
e
^
) and the adversary is given a co-CDH tuple (
g
a
,
h
b
) with the exponents a
,
b chosen randomly from Z
p; the algorithm B works as follows.
First,B needs to simulate public parameter P
P and evaluation key E
K
F. It computes the bilinear map e
(
g
a
,
h
b
) and chooses 2
l random elements t
^
j
T
,
E
j
T
1
≤
j
T
≤
l. The simulated public key P
P
=
(
e
(
g
a
,
h
b
)
,
e
), and the simulated evaluation key E
K
F
=
(
T
,
E
)
=
t
^
j
T
,
W
j
T
1
≤
j
T
≤
l. Since the W generated in Game 3 contains a PRF as a factor and the PRF enjoys pseudorandomness, it is clear that the P
P and E
K
F generated above enjoy a perfect distribution as that in Game 3.
Second,B gives the simulated P
P and E
K
F to A and prepares to simulate the answers to the queries from A. A difference here is that B does not need to generate the retrieval key R
K in querying phase as that in Game 3 because A does not have access to R
K, neither does B need this R
K to solve the co-CDH problem. Let x
i
(
1
≤
i
≤
q
) be the querying value. B first computes U
j
T
=
e
(
E
j
T
,
h
)
/
e
g
a
,
h
b
t
^
j
T and then computes V
K
x
i
=
∏
j
T
=
1
l
U
j
T
t
j
T
(
x
i
). Since in Game 3,(23)
e
E
j
T
,
h
e
g
α
,
h
t
^
j
T
=
R
K
j
T
,combining the bilinear property of map e, it is clear that the simulated V
K
x
i also enjoys a perfect distribution as that in Game 3. A is then given the corresponding verification key V
K
x
i. Let x
∗ be the challenge value chosen by A. The above process is repeated and A obtains V
K
x
∗.
Finally,A will output a tuple σ
^
o
u
t
∗
=
(
y
^
,
V
^
) such that(24)
P
u
b
V
e
r
V
K
x
∗
,
σ
o
u
t
∗
⟶
k
,
P
r
i
v
R
e
t
σ
o
u
t
∗
,
V
K
x
∗
,
R
K
x
∗
⟶
y
∗
,
wherek
=
a
c
c
e
p
t and y
∗
≠
F
(
x
∗
). Due to the correctness property, this y
∗
≠
F
(
x
∗
) also implies that y
^
≠
T
(
x
∗
). By k
=
a
c
c
e
p
t we obtain that(25)
e
V
^
,
h
=
e
g
a
,
h
b
y
^
·
V
K
x
∗
.Let y
=
F
(
x
∗
) be the correct output of the PrivRet algorithm. Then by correctness we know y
′
=
T
(
x
∗
) is also correct. Thus the following equation also holds:(26)
e
V
,
h
=
e
g
a
,
h
b
y
′
·
V
K
x
∗
,where V
=
∏
j
T
=
1
l
E
j
T
t
j
T
(
x
∗
).
Dividing (25) and (26) and combining bilinear property, we can obtain that(27)
e
V
^
V
,
h
=
e
g
a
b
,
h
y
^
-
y
′
.Then B can compute g
a
b
=
(
V
^
/
V
)
1
/
(
y
^
-
y
′
). Thus, if A wins Game 3 with probability ϵ
c
d
h, B solves the co-CDH problem with the same probability. This proves Claim 4.Combining the four claims together, we obtain that(28)
P
r
E
X
P
A
π
,
F
,
λ
=
1
≤
ϵ
p
r
f
+
ϵ
c
d
h
.


## 4.4. Performance Analysis

In this subsection, we analyze the computational complexity of the proposed scheme and compare it with some existing works [2, 19]. Our scheme is efficient in the amortized model. That is, the expensiveKeyGen algorithm is executed once and its computational overhead is amortized by the following evaluation of the polynomial function with different input value. Here the structure of the function cannot be changed unless anotherKeyGen algorithm for a different function is performed. Now we give detailed analysis on the computational costs of each algorithm. Let each letter denote the same item as that in the proposed scheme above. In theKeyGen phase, to compute the term E
j
T, the client needs to execute 2
d
′
+
2
m
+
1 times of exponential modulo and d
′
+
1
m times of multiplication arithmetic in group G
1. To compute the structure of function T
(
·
), 2
d
′
+
1
m times of multiplication and 2
m times of addition arithmetic in N are executed. To generate the public key, one time of pairing arithmetic is executed. In theProbGen phase, no execution needs to be done to generate σ
x since σ
x remains the same as input x. To generate the public verification key V
K
x, algorithm C
F
E
v
a
l
P
o
l
y
(
·
) is executed together with one time pairing arithmetic. And to generate the private retrieval key, the client needs to execute two times of (m-variate, 1-degree) sparse polynomial evaluation arithmetic. In theCompute phase, the cloud server needs to execute one time of (m-variate,d
′
+
1-degree) polynomial evaluation arithmetic to compute y
′ and d
′
+
2
m times of exponential modulo in group G
1 to compute term V. In thePubVer phase, to compute the corresponding terms in the checking equation, the third party verifier needs to execute one time of pairing arithmetic, one time of exponential modulo arithmetic in G
T, and one time of multiplication arithmetic in G
T, respectively. Finally, in thePrivRet phase, the client firstly needs to execute what is done inPubVer phase and then execute, respectively, one time of subtraction and division arithmetic in N to compute the result y.We present a complexity comparison between our scheme and existing works of PVC schemes for polynomial evaluation [2, 19]. After analyzing the specific arithmetic of each algorithm, We would like to use the notation O to compare computational complexity. Since the arithmetic operations in different groups are the same, we use three types of notation, O
I,O
N, and O
E, to classify different types of complexity. O
I denotes the time complexity of operations in ring Z
p including integer addition and multiplication modulo prime p. O
N denotes the time complexity of operations in ring N including addition and multiplication. O
E denotes the time complexity of operations in group G
1, G
2, G
T including multiplication, exponentiation, and bilinear map. The comparison result is shown in Table 1. From the table we can see that, compared with the scheme in [2], ours has a complexity increase of O
N
(
d
′
m
) inKeyGen, O
N
(
m
) inProbGen, and O
N
(
1
) inPrivRet performed by the client. However, since the most expensive arithmetic in each of the three phases is O
E
(
d
′
m
), O
I
(
m
log
⁡
d
′
), and O
E
(
1
), respectively, the impact of the increasing complexity will not be obvious in the real performance. Compared with the scheme in [19], we first notice that the scheme in [19] only works for univariate case, while ours works for multivariate case. If we set “m
=
1”, the complexity of the two schemes is nearly the same, with a small increase of O
N
(
1
) inProbGen andPrivRet, respectively, which is not the most expensive part in the two phases. By doing so, our scheme achieves a security property-result confidentiality that is considered to be important for user privacy.Table 1
Comparison of the three PVC schemes for polynomial evaluation.
FG12 [2]
EOA16 [19]
Ours
Problem size
m-variate, d
′-degree
univariate,d
′-degree
m-variate, d
′-degree
KeyGen
O
E
(
d
′
m
)
O
E
(
d
′
)
+
O
N
(
d
′
)
O
E
(
d
′
m
)
+
O
N
(
d
′
m
)
ProbGen
O
E
(
1
)
+
O
I
(
m
log
⁡
d
′
)
O
E
(
1
)
+
O
I
(
1
)
O
E
(
1
)
+
O
I
(
m
log
⁡
d
′
)
+
O
N
(
m
)
Compute
O
E
(
d
′
m
)
+
O
N
(
d
′
m
)
O
E
(
d
′
)
+
O
N
(
d
′
)
O
E
(
d
′
m
)
+
O
N
(
d
′
m
)
PubVer
O
E
(
1
)
O
E
(
1
)
O
E
(
1
)
PrivRet
⊥
⊥
O
E
(
1
)
+
O
N
(
1
)
Result confidentiality
No
No
YesWe also provide some experimental simulation of CP-PVC for polynomial to show the efficiency. Intuitively, efficiency means that the total computational overhead on the client side by engaging an outsourcing computation protocol is less than that by directly executing the target function algorithm. Since our scheme is constructed in an amortized model, i.e., the computations inKeyGen need to be done only once, we will not count that part of computation in the efficiency performance. Then for the client side, all the computation costs that are counted containProbGen andPrivRet phase. We implement the corresponding algorithms on the client side using MATLAB 2015 on a computer with Intel(R) Core(TM) i7-4790 CPU processor running at 3.60 GHz and 8 GB RAM. We show the time cost for different sizes of problems in Table 2, where m represents variable number and s represents bit length of the highest degree d
′. This part of work is done in the previous conference version of this paper [24].Table 2
Times cost of the client [24].
m
s
=
10
s
=
50
s
=
200
s
=
1000
1000
0.0312s
0.0936s
0.1248s
0.4836s
5000
0.0624s
0.1716s
0.4836s
2.1372s
20000
0.1872s
0.5304s
1.7628s
8.3304s
100000
0.5460s
2.3712s
8.5956s
41.7614sFor comparison of efficiency, we also do some evaluation using the direct algorithmF
(
x
)
=
∑
j
F
=
1
w
f
^
j
F
·
f
j
F
(
x
), where f
j
F
(
x
) represents each monomial for polynomial F and w
=
2
s
+
1
m. The corresponding result is shown in Table 3, which is also done in the previous conference version [24]. We see that the cost time is already infinite when the case goes to s
=
50. This is reasonable because theoretically the complexity of the direct algorithm is O
(
m
·
2
s
). Recalling that the complexity of the way using closed form efficient PRF is O
(
m
s
), thus the scheme achieves a log time efficiency promoted for the evaluation of multivariate polynomials. We show in Figure 1 a time cost comparison between direct algorithm and outsourcing algorithm, in which case s
=
10; i.e., the degree of each variate is 2
10. This is also done in the previous conference version [24].Table 3
Times cost of direct algorithm [24].
m
s
=
10
s
=
50
s
=
200
s
=
1000
1000
3.28s
∞
∞
∞
5000
6.55s
∞
∞
∞
20000
19.65s
∞
∞
∞
100000
59.24s
∞
∞
∞Figure 1
Time cost of different problem sizes [24].


## 5. The CP-PVC Scheme for Matrix-Vector Multiplication

In this section, we first review theP
R
F that is used for matrix-vector case and give the algorithm for its closed form efficiency. Then we give the concrete construction of our CP-PVC scheme for matrix-vector multiplication together with the analysis and experimental simulation.


### 5.1. Algorithm for PRF with Closed Form Efficiency

TheP
R
F is defined in another domain, namely, the set [
1
,
…
,
m
]
×
[
1
,
…
,
n
].LetG be a group generator that takes as input a secure parameter λ and outputs a description of group with prime order. The PRF is defined as follows:(i)
KG
(
1
λ
,
m
,
n
): Run G
(
1
λ
) to generate a group description (
p
,
g
,
G
1
). Choose 2
(
n
+
m
) random values(29)
A
i
,
B
i
1
≤
i
≤
m
←
$
G
1
,
α
j
,
β
j
1
≤
j
≤
n
←
$
Z
p
.
The algorithm outputs(30)
K
=
A
i
,
B
i
,
α
j
,
β
j
i
,
j
.
(ii)
R
K
(
·
): Let (
i
,
j
) be the input of the PRF. The algorithm outputs(31)
R
K
i
,
j
=
A
j
α
i
B
j
β
i
.The pseudorandomness holds under Decisional Linear assumption, and the corresponding proof is shown in [29]. We omit it here.Now we consider then-dimensional vector t
→
=
(
t
1
,
…
,
t
n
)
∈
G, where t
i
=
∏
j
r
i
,
j
x
j and (r
i
,
j) forms an n
×
m matrix. We show that the construction of P
R
F
M
(
K
G
,
R
K
(
i
,
j
)
) admits the closed form efficiency for the computation of vector t
→. If we set r
i
,
j
=
R
K
(
i
,
j
), then there exists an algorithm C
F
E
v
a
l
M
a
t
r
i
x
(
K
,
x
1
,
…
,
x
m
) that can compute t
→
=
(
t
1
,
…
,
t
m
) in time O
(
m
+
n
), instead of the regular running time O
(
n
m
). The corresponding algorithm is shown in Algorithm 3.Algorithm 3:
C
F
E
v
a
l
M
a
t
x
(
K
,
x
1
,
…
,
x
m
).
sett
→
=
Φ
A
=
∏
j
=
1
m
‍
A
j
x
j
B
=
∏
j
=
1
m
‍
B
j
x
j
for
i
=
1 to n: do
t
i
=
A
α
i
B
β
i
end for
return
t
→
=
(
t
1
,
…
,
t
n
)With the use of the above closed form efficient PRF in Algorithm3, we can realize public verifiability by letting the PRF value be a part of the verification key. Then our remaining goal is to make this public verification process “blind”. Inspired by the blinding technique in Chen et al.’s work [15], we can use a vector r
→ to blind the real input r
→ and a matrix N
∈
Z
p
n
×
m to blind the target matrix M and ask the cloud server to compute (
M
+
N
)
(
x
→
+
r
→
). Thus the result is confidential and the public verification phase can be processed as usual. However, to retrieve the real result M
x
→, the user needs to compute the value M
r
→
N
x
→ and N
r
→. This will cost three times the original computational task M
x
→ does (O
(
n
m
)). To reduce the overhead of this computation, we can make the blinding vector and matrix sparse. The sparse matrix is like that in [15]. To make the result confidentiality solid, we usually set at least one nonzero element in each row of matrix N. For the sparse vector, we set randomly ⌈
(
1
-
δ
)
m
⌉ (0
<
δ
<
1) positions 0. Then the computational overhead of M
r
→, N
x
→, and N
r
→ is reduced to O
(
δ
n
m
), O
(
n
), and O
(
δ
n
). What is more, the blinding vector also preserves the privacy of input data to some extent.


### 5.2. Construction of CP-PVC for Matrix-Vector Case

Now, we present our concrete scheme of CP-PVC for matrix multiplication. Letp be a prime. Recall that our goal is to compute the n-dimensional vector y
→
=
M
x
→, where M is an n
×
m matrix denoted by (
M
i
,
j
) with entries from Z
p. Such matrix-vector multiplication can be naturally extended to matrix-matrix multiplication by regarding the latter matrix as a row vector of column vectors and repeating the above matrix-vector multiplication several times. For matrix-vector multiplication M
x
→, the CP-PVC scheme works as follows:(i)
KeyGen: Let M
=
(
M
i
,
j
). For parameter λ, the client runs a bilinear group generator G
e
(
1
λ
) to generate a bilinear tuple (
p
,
g
,
h
,
G
1
,
G
2
,
G
T
,
e
^
). Choose a random sparse matrix N
∈
Z
p
n
×
m and set M
′
=
M
+
N. The client then runs PRF key generation algorithmKG
(
1
λ
,
m
,
n
) to generate a key K and the range in G
1. Choose a random α
∈
Z
p, and compute(32)
E
i
,
j
=
g
α
·
M
i
,
j
′
·
R
K
i
,
j
,
∀
i
=
1
,
…
,
n
;
j
=
1
,
…
,
m
.
LetE
=
(
E
i
,
j
)
∈
G
1
n
×
m. The algorithm outputs(33)
S
K
F
=
K
,
N
,
E
K
F
=
E
,
M
′
,
P
P
=
e
^
,
e
^
g
,
h
α
.
(ii)
ProbGen: On inputting S
K
F
=
(
K
,
N
), P
P
=
(
e
^
,
e
^
(
g
,
h
)
α
), and owning x
→
=
(
x
1
,
…
,
x
m
)
∈
Z
p
m, the client randomly chooses a δ
∈
(
0,1
) and a sparse m-dimensional vector r
→
=
(
r
1
,
…
,
r
m
)
∈
Z
p
m, where ⌈
(
1
-
δ
)
m
⌉ coordinates of r
→ are 0. Let x
→
′
=
x
→
+
r
→. Compute M
r
→, N
x
→, N
r
→in O
(
δ
n
m
), O
(
n
), O
(
δ
n
) time, respectively, and compute t
i
=
C
F
E
v
a
l
M
a
t
x
(
K
,
x
1
′
,
…
,
x
m
′
) in O
(
n
+
m
) time using the closed form efficiency. Define v
i
=
e
^
(
t
i
,
h
) for i
=
1
,
…
,
n.
The algorithm outputs(34)
σ
x
=
x
→
′
,
V
K
x
=
v
i
,
…
,
v
n
,
R
K
x
=
M
r
→
,
N
x
→
,
N
r
→
.
(iii)
Compute: On receiving E
K
F
=
(
E
,
M
′
) and σ
x
=
x
→
′, the cloud server computes y
→
′
=
M
′
x
→
′, w
i
=
∏
j
=
1
m
E
i
,
j
x
j
′ (for i
=
1
,
…
,
n) and outputs(35)
σ
o
u
t
=
y
→
′
,
W
=
y
1
′
,
…
,
y
n
′
,
w
i
,
…
,
w
n
.
(iv)
PubVer: On receiving V
K
x
=
(
v
i
,
…
,
v
n
) and σ
o
u
t
=
(
y
→
′
,
W
), the verifier checks the following equation:(36)
e
^
w
i
,
h
=
e
^
g
,
h
α
y
i
′
·
v
i
,
∀
i
=
1
,
…
,
n
.
The algorithm outputsa
c
c
e
p
t if the above equation holds; otherwise, it outputs r
e
j
e
c
t.
(v)
PrivRet: On receiving V
K
x
=
(
v
i
,
…
,
v
n
), σ
o
u
t
=
(
y
→
′
,
W
), and owning R
K
x
=
(
M
r
→
,
N
x
→
,
N
r
→
), the client first runs thePubVer algorithm with V
K
x and σ
o
u
t. If thePubVer outputs a
c
c
e
p
t, then compute y
→
=
y
→
′
-
M
r
→
-
N
x
→
-
N
r
→ and return y
→ as the output.Remark 8.
In order to be uniform, we assume that each entry of the matrixM and vector x
→ is from ring Z
p. However, when performing the arithmetic computation between matrix-matrix, vector-vector, and matrix-vector, the execution is actually done in the ring N. That is, the results are not in the form modulo prime p. This is to keep correctness of the computational result.


### 5.3. Security Analysis

Now we analyze the correctness, security, and privacy and confidentiality of the proposed CP-PVC scheme.


#### 5.3.1. Correctness

Correctness is easy to prove. Letσ
o
u
t
,
V
K
x
,
R
K
x be as above. For i
=
1
,
…
,
n,(37)
e
^
w
i
,
h
=
e
^
∏
j
=
1
m
E
i
,
j
x
j
′
,
h
=
e
^
∏
j
=
1
m
g
α
·
M
i
,
j
′
·
R
K
i
,
j
x
j
′
,
h
=
e
^
∏
j
=
1
m
g
α
M
i
,
j
′
x
j
′
,
h
·
e
^
∏
j
=
1
m
R
K
i
,
j
x
j
′
,
h
=
e
^
g
α
y
i
′
,
h
·
e
^
t
i
,
h
=
e
^
g
,
h
α
y
i
′
·
v
i
.The above proves the correctness for evaluatingy
→
′
=
M
x
→
′, and this implies the correctness of y
→
=
y
→
′
-
M
r
→
-
N
x
→
-
N
r
→.


#### 5.3.2. Result Confidentiality and Input Privacy

The result confidentiality is similar to the polynomial case. We prove that, given the tuple(
P
P
,
E
K
F
,
V
K
,
σ
x
,
σ
o
u
t
), the adversary cannot extract the result vector y
=
M
x.LetM
,
N
,
x
→
,
r
→
,
y
→
,
y
→
′ be as above; then we have that(38)
y
i
=
∑
j
=
1
m
M
i
,
j
·
x
jand(39)
y
i
′
=
∑
j
=
1
m
M
i
,
j
+
N
i
,
j
·
x
j
+
r
j
=
∑
j
=
1
m
M
i
,
j
·
r
j
+
∑
j
=
1
m
N
i
,
j
·
x
j
+
∑
j
=
1
m
N
i
,
j
·
r
j
+
∑
j
=
1
m
M
i
,
j
·
x
j
.Notice that the blinding matrix has at least one nonzero element in each row, and the nonzero elements are all chosen uniformly at random. Thus they
i are all blinded by a random nonzero element, which makes the confidentiality of y
→ hold.As an additional bonus, the random sparse vectorr
→ that is added to the input x
→ provides some preservation to the privacy of input value. Since the vector is sparse, with 1
-
δ
m coordinates being 0, such blinding operation may preserve the input privacy at a degree of 1
-
δ; namely, the adversary may successfully guess one entry of the input vector with this probability. However since the position of 0 elements is chosen at random, the probability of the adversary to recover 1
-
δ fraction of the input data is 1
/
m
δ
m.


#### 5.3.3. Security

The proof of the security follows that in [2]. We take it as an inspiration and define the following four games.Game 0.
It is the same asE
x
p
e
r
i
m
e
n
t
E
X
P
A
[
π
,
F
,
λ
].Game 1.
It is similar to Game 0, with the difference thatE
K
F contains an n
×
m random matrix from Z
p
n
×
m instead of N.Game 2.
It is similar to Game 1, with the difference that theProbGen phase uses an inefficient algorithm ∏
j
=
1
m
R
K
i
,
j
x
j instead of the C
F
E
v
a
l
P
o
l
y
(
K
,
x
1
,
…
,
x
m
) to evaluate V
K
x.Game 3.
It is similar to Game 2, with the difference that each valueR
K
(
i
,
j
) is replaced by a random element R
i
,
j
∈
G
1.We use a hybrid way to perform the proof, with the following claims.Corollary 4.
P
r
[
G
0
(
A
)
=
1
]
=
P
r
G
1
A
=
1.Proof.
This claim holds in an obvious way, since the change of algorithm for evaluatingV
K
Xdoes not change the distribution of its values. Thus the probability that the adversary wins is the same in both Games 0 and 1.Corollary 5.
P
r
G
1
A
=
1
=
P
r
G
2
A
=
1.Proof.
The difference between Games 2 and 1 is the coefficients of the target matrix. According to the confidentiality proof, these coefficients are indistinguishable since eachN
i
,
j is chosen uniformly at random, thus sharing the same distribution in the view of the adversary.Corollary 6.
P
r
G
2
A
=
1
=
P
r
G
3
A
=
1
≤
ϵ
p
r
f, whereϵ
p
r
frepresents the probability in the pseudorandomness definition of PRF.Proof.
The difference between Games 3 and 2 is that the output of PRFR
K
(
x
) is replaced by uniformly random elements in G
1. According to the pseudorandomness property of PRF, the probability that an adversary A distinguishes the two values is no better than ϵ
p
r
f.Corollary 7.
P
r
G
3
A
=
1
≤
ϵ
c
d
h, where ϵ
c
d
h represents the probability that an adversary solves co-CDH problem.The proof of this corollary is the same as that in [2]; we omit it here.Combining the four claims together, we obtain that(40)
P
r
E
X
P
A
π
,
F
,
λ
=
1
≤
ϵ
p
r
f
+
ϵ
c
d
h
.


### 5.4. Performance Analysis

We also analyze the computational complexity of the proposed CP-PVC scheme for matrix-vector multiplication and compare it with existing works [2, 19]. Analogous to polynomial case, we first give detailed analysis on the computational costs of each algorithm in matrix-vector multiplication case. Let each letter denote the same item as that in the proposed scheme above. In theKeyGen phase, to compute the term E
j
T, the client needs to execute 3
n
m
+
1 times of exponential modulo and 2
n
m times of multiplication arithmetic in group G
1. To compute the matrix M
′, since N is sparse, only n times of addition arithmetic in N are executed. To generate the public key, one time of pairing arithmetic is executed. In theProbGen phase, the client first needs to execute δ
m times of addition arithmetic in N to get σ
x. To generate the public verification key V
K
x, algorithm C
F
E
v
a
l
M
a
t
x
(
·
) is executed together with n times of pairing arithmetic. And to generate the private retrieval key, the client needs to execute three times of matrix-vector multiplication arithmetic with computation complexity being O
(
δ
n
m
), O
(
n
), and O
(
δ
n
), respectively. In theCompute phase, the cloud server needs to execute one time of dense matrix-vector multiplication arithmetic to compute y
′ and n
m times of exponential modulo and n
(
m
-
1
) times of multiplication in group G
1 to compute term W. In thePubVer phase, to compute the corresponding terms in the checking equation, the third party verifier needs to execute n times of pairing arithmetic, n times of exponential modulo arithmetic in G
T, and n times of multiplication arithmetic in G
T, respectively. Finally, in thePrivRet phase, the client firstly needs to execute what is done inPubVer phase and then execute, respectively, three times of vector subtraction arithmetic in N to compute the result y.Next we present a complexity comparison between our scheme and existing works of PVC schemes for matrix-vector multiplication [2, 19]. Similar to the polynomial case, We also use the notation O to compare computational complexity. According to the specific analysis of each algorithm, the arithmetic computations take place in ring N and group G
1, G
2, G
T. Thus we only use two types of notation, O
N and O
E, where O
N denotes the time complexity of operations in ring N including addition and multiplication and O
E denotes the time complexity of operations in group G
1, G
2, G
T including multiplication, exponentiation, and bilinear map. Let n
×
m be the problem size; then the comparison result is shown in Table 4. From the table we can see that, compared with the scheme in [2], ours has a complexity increase of O
N
(
δ
n
m
) inProbGen and O
N
(
n
) inPrivRet performed by the client. However, when the value of δ is small, the part O
N
(
δ
n
m
) will be much less expensive than O
E
(
n
+
m
). And O
N
(
n
) is surely less expensive than O
E
(
n
). Therefore, by choosing a proper δ, the impact of the increasing complexity will not be obvious in the real performance. Compared with the scheme in [19], ours has a complexity increase of O
E
(
n
)
+
O
N
(
δ
n
m
) inProbGen and O
N
(
n
) inPrivRet performed by the client. If n
≤
m, or the difference between n and m is small, the complexity of O
E
(
m
) and O
E
(
n
+
m
) is nearly the same. Under this circumstance, our scheme can achieve a comparative performance with a small δ chosen. What is more, our scheme achieves result confidentiality and partial input privacy that are considered to be important for user privacy.Table 4
Comparison of the three PVC schemes for matrix vector multiplication.
FG12 [2]
EOA16 [19]
Ours
KeyGen
O
E
(
n
m
)
O
E
(
n
m
)
+
O
N
(
n
m
)
O
E
(
n
m
)
+
O
N
(
n
)
ProbGen
O
E
(
n
+
m
)
O
E
(
m
)
O
E
(
n
+
m
)
+
O
N
(
δ
n
m
)
Compute
O
E
(
n
m
)
+
O
N
(
n
m
)
O
E
(
n
m
)
+
O
N
(
n
m
)
O
E
(
n
m
)
+
O
N
(
n
m
)
PubVer
O
E
(
n
)
O
E
(
n
)
O
E
(
n
)
PrivRet
⊥
⊥
O
E
(
n
)
+
O
N
(
n
)
Result confidentiality
No
No
Yes
Input Privacy
No
No
PartialWe also provide an experimental evaluation on the client side to show the efficiency compared with direct algorithm for matrix-vector multiplication. Different from that in polynomial case, we have a sparse coefficientδ in matrix-vector case. We choose different δ values and show the time cost for different sizes of problems in Table 5, which is done in the previous conference version of this paper [24]. Note that in theProbGen phase, the time cost of V
K generation is related only to n
,
m but not to δ. However, the time cost of R
K generation is related to not only n
,
m but also δ. With a smaller δ, one can get a more efficient CP-PVC scheme, but this inevitably brings more risks to input privacy. This seems inherently a trade-off. Also, note that the computations in thePubVer andPrivRet phase are n times of bilinear map operation and three times of vector subtraction, respectively. This part of cost is too small to be counted in, so we omit it from the table.Table 5
Time cost under differentδ values [24].
n
×
m
Original cost
VK_Gen
RK_Gen (δ
=
0.5)
RK_Gen (δ
=
0.2)
1000
×
50000
1.4508s
0.0077s
0.6864s
0.2652s
1000
×
100000
3.3228s
0.0156s
1.2728s
0.5460s
1000
×
200000
7.9092s
0.0312s
2.9484s
1.0764s
1000
×
400000
14.1683s
0.0624s
6.4428s
2.1840sFrom the table we can see that, no matter what the choice ofδ is, the total cost of V
K generation and R
K generation is much less than the original cost of matrix multiplication. Things can be more visualized in the column diagram of Figures 2 and 3 [24], where the volume of V
K generation (blue) and R
K generation (green) together is less than that of the original cost (red). Even when counting in the omitted time cost ofPubVer andPrivRet phase, the CP-PVC scheme achieves an acceptable efficiency performance in practice.Figure 2
Time cost of different problem sizes (×
1000) when δ
=
0.5 [24].Figure 3
Time cost of different problem sizes (×
1000) when δ
=
0.2 [24].


## 5.1. Algorithm for PRF with Closed Form Efficiency

TheP
R
F is defined in another domain, namely, the set [
1
,
…
,
m
]
×
[
1
,
…
,
n
].LetG be a group generator that takes as input a secure parameter λ and outputs a description of group with prime order. The PRF is defined as follows:(i)
KG
(
1
λ
,
m
,
n
): Run G
(
1
λ
) to generate a group description (
p
,
g
,
G
1
). Choose 2
(
n
+
m
) random values(29)
A
i
,
B
i
1
≤
i
≤
m
←
$
G
1
,
α
j
,
β
j
1
≤
j
≤
n
←
$
Z
p
.
The algorithm outputs(30)
K
=
A
i
,
B
i
,
α
j
,
β
j
i
,
j
.
(ii)
R
K
(
·
): Let (
i
,
j
) be the input of the PRF. The algorithm outputs(31)
R
K
i
,
j
=
A
j
α
i
B
j
β
i
.The pseudorandomness holds under Decisional Linear assumption, and the corresponding proof is shown in [29]. We omit it here.Now we consider then-dimensional vector t
→
=
(
t
1
,
…
,
t
n
)
∈
G, where t
i
=
∏
j
r
i
,
j
x
j and (r
i
,
j) forms an n
×
m matrix. We show that the construction of P
R
F
M
(
K
G
,
R
K
(
i
,
j
)
) admits the closed form efficiency for the computation of vector t
→. If we set r
i
,
j
=
R
K
(
i
,
j
), then there exists an algorithm C
F
E
v
a
l
M
a
t
r
i
x
(
K
,
x
1
,
…
,
x
m
) that can compute t
→
=
(
t
1
,
…
,
t
m
) in time O
(
m
+
n
), instead of the regular running time O
(
n
m
). The corresponding algorithm is shown in Algorithm 3.Algorithm 3:
C
F
E
v
a
l
M
a
t
x
(
K
,
x
1
,
…
,
x
m
).
sett
→
=
Φ
A
=
∏
j
=
1
m
‍
A
j
x
j
B
=
∏
j
=
1
m
‍
B
j
x
j
for
i
=
1 to n: do
t
i
=
A
α
i
B
β
i
end for
return
t
→
=
(
t
1
,
…
,
t
n
)With the use of the above closed form efficient PRF in Algorithm3, we can realize public verifiability by letting the PRF value be a part of the verification key. Then our remaining goal is to make this public verification process “blind”. Inspired by the blinding technique in Chen et al.’s work [15], we can use a vector r
→ to blind the real input r
→ and a matrix N
∈
Z
p
n
×
m to blind the target matrix M and ask the cloud server to compute (
M
+
N
)
(
x
→
+
r
→
). Thus the result is confidential and the public verification phase can be processed as usual. However, to retrieve the real result M
x
→, the user needs to compute the value M
r
→
N
x
→ and N
r
→. This will cost three times the original computational task M
x
→ does (O
(
n
m
)). To reduce the overhead of this computation, we can make the blinding vector and matrix sparse. The sparse matrix is like that in [15]. To make the result confidentiality solid, we usually set at least one nonzero element in each row of matrix N. For the sparse vector, we set randomly ⌈
(
1
-
δ
)
m
⌉ (0
<
δ
<
1) positions 0. Then the computational overhead of M
r
→, N
x
→, and N
r
→ is reduced to O
(
δ
n
m
), O
(
n
), and O
(
δ
n
). What is more, the blinding vector also preserves the privacy of input data to some extent.


## 5.2. Construction of CP-PVC for Matrix-Vector Case

Now, we present our concrete scheme of CP-PVC for matrix multiplication. Letp be a prime. Recall that our goal is to compute the n-dimensional vector y
→
=
M
x
→, where M is an n
×
m matrix denoted by (
M
i
,
j
) with entries from Z
p. Such matrix-vector multiplication can be naturally extended to matrix-matrix multiplication by regarding the latter matrix as a row vector of column vectors and repeating the above matrix-vector multiplication several times. For matrix-vector multiplication M
x
→, the CP-PVC scheme works as follows:(i)
KeyGen: Let M
=
(
M
i
,
j
). For parameter λ, the client runs a bilinear group generator G
e
(
1
λ
) to generate a bilinear tuple (
p
,
g
,
h
,
G
1
,
G
2
,
G
T
,
e
^
). Choose a random sparse matrix N
∈
Z
p
n
×
m and set M
′
=
M
+
N. The client then runs PRF key generation algorithmKG
(
1
λ
,
m
,
n
) to generate a key K and the range in G
1. Choose a random α
∈
Z
p, and compute(32)
E
i
,
j
=
g
α
·
M
i
,
j
′
·
R
K
i
,
j
,
∀
i
=
1
,
…
,
n
;
j
=
1
,
…
,
m
.
LetE
=
(
E
i
,
j
)
∈
G
1
n
×
m. The algorithm outputs(33)
S
K
F
=
K
,
N
,
E
K
F
=
E
,
M
′
,
P
P
=
e
^
,
e
^
g
,
h
α
.
(ii)
ProbGen: On inputting S
K
F
=
(
K
,
N
), P
P
=
(
e
^
,
e
^
(
g
,
h
)
α
), and owning x
→
=
(
x
1
,
…
,
x
m
)
∈
Z
p
m, the client randomly chooses a δ
∈
(
0,1
) and a sparse m-dimensional vector r
→
=
(
r
1
,
…
,
r
m
)
∈
Z
p
m, where ⌈
(
1
-
δ
)
m
⌉ coordinates of r
→ are 0. Let x
→
′
=
x
→
+
r
→. Compute M
r
→, N
x
→, N
r
→in O
(
δ
n
m
), O
(
n
), O
(
δ
n
) time, respectively, and compute t
i
=
C
F
E
v
a
l
M
a
t
x
(
K
,
x
1
′
,
…
,
x
m
′
) in O
(
n
+
m
) time using the closed form efficiency. Define v
i
=
e
^
(
t
i
,
h
) for i
=
1
,
…
,
n.
The algorithm outputs(34)
σ
x
=
x
→
′
,
V
K
x
=
v
i
,
…
,
v
n
,
R
K
x
=
M
r
→
,
N
x
→
,
N
r
→
.
(iii)
Compute: On receiving E
K
F
=
(
E
,
M
′
) and σ
x
=
x
→
′, the cloud server computes y
→
′
=
M
′
x
→
′, w
i
=
∏
j
=
1
m
E
i
,
j
x
j
′ (for i
=
1
,
…
,
n) and outputs(35)
σ
o
u
t
=
y
→
′
,
W
=
y
1
′
,
…
,
y
n
′
,
w
i
,
…
,
w
n
.
(iv)
PubVer: On receiving V
K
x
=
(
v
i
,
…
,
v
n
) and σ
o
u
t
=
(
y
→
′
,
W
), the verifier checks the following equation:(36)
e
^
w
i
,
h
=
e
^
g
,
h
α
y
i
′
·
v
i
,
∀
i
=
1
,
…
,
n
.
The algorithm outputsa
c
c
e
p
t if the above equation holds; otherwise, it outputs r
e
j
e
c
t.
(v)
PrivRet: On receiving V
K
x
=
(
v
i
,
…
,
v
n
), σ
o
u
t
=
(
y
→
′
,
W
), and owning R
K
x
=
(
M
r
→
,
N
x
→
,
N
r
→
), the client first runs thePubVer algorithm with V
K
x and σ
o
u
t. If thePubVer outputs a
c
c
e
p
t, then compute y
→
=
y
→
′
-
M
r
→
-
N
x
→
-
N
r
→ and return y
→ as the output.Remark 8.
In order to be uniform, we assume that each entry of the matrixM and vector x
→ is from ring Z
p. However, when performing the arithmetic computation between matrix-matrix, vector-vector, and matrix-vector, the execution is actually done in the ring N. That is, the results are not in the form modulo prime p. This is to keep correctness of the computational result.


## 5.3. Security Analysis

Now we analyze the correctness, security, and privacy and confidentiality of the proposed CP-PVC scheme.


### 5.3.1. Correctness

Correctness is easy to prove. Letσ
o
u
t
,
V
K
x
,
R
K
x be as above. For i
=
1
,
…
,
n,(37)
e
^
w
i
,
h
=
e
^
∏
j
=
1
m
E
i
,
j
x
j
′
,
h
=
e
^
∏
j
=
1
m
g
α
·
M
i
,
j
′
·
R
K
i
,
j
x
j
′
,
h
=
e
^
∏
j
=
1
m
g
α
M
i
,
j
′
x
j
′
,
h
·
e
^
∏
j
=
1
m
R
K
i
,
j
x
j
′
,
h
=
e
^
g
α
y
i
′
,
h
·
e
^
t
i
,
h
=
e
^
g
,
h
α
y
i
′
·
v
i
.The above proves the correctness for evaluatingy
→
′
=
M
x
→
′, and this implies the correctness of y
→
=
y
→
′
-
M
r
→
-
N
x
→
-
N
r
→.


### 5.3.2. Result Confidentiality and Input Privacy

The result confidentiality is similar to the polynomial case. We prove that, given the tuple(
P
P
,
E
K
F
,
V
K
,
σ
x
,
σ
o
u
t
), the adversary cannot extract the result vector y
=
M
x.LetM
,
N
,
x
→
,
r
→
,
y
→
,
y
→
′ be as above; then we have that(38)
y
i
=
∑
j
=
1
m
M
i
,
j
·
x
jand(39)
y
i
′
=
∑
j
=
1
m
M
i
,
j
+
N
i
,
j
·
x
j
+
r
j
=
∑
j
=
1
m
M
i
,
j
·
r
j
+
∑
j
=
1
m
N
i
,
j
·
x
j
+
∑
j
=
1
m
N
i
,
j
·
r
j
+
∑
j
=
1
m
M
i
,
j
·
x
j
.Notice that the blinding matrix has at least one nonzero element in each row, and the nonzero elements are all chosen uniformly at random. Thus they
i are all blinded by a random nonzero element, which makes the confidentiality of y
→ hold.As an additional bonus, the random sparse vectorr
→ that is added to the input x
→ provides some preservation to the privacy of input value. Since the vector is sparse, with 1
-
δ
m coordinates being 0, such blinding operation may preserve the input privacy at a degree of 1
-
δ; namely, the adversary may successfully guess one entry of the input vector with this probability. However since the position of 0 elements is chosen at random, the probability of the adversary to recover 1
-
δ fraction of the input data is 1
/
m
δ
m.


### 5.3.3. Security

The proof of the security follows that in [2]. We take it as an inspiration and define the following four games.Game 0.
It is the same asE
x
p
e
r
i
m
e
n
t
E
X
P
A
[
π
,
F
,
λ
].Game 1.
It is similar to Game 0, with the difference thatE
K
F contains an n
×
m random matrix from Z
p
n
×
m instead of N.Game 2.
It is similar to Game 1, with the difference that theProbGen phase uses an inefficient algorithm ∏
j
=
1
m
R
K
i
,
j
x
j instead of the C
F
E
v
a
l
P
o
l
y
(
K
,
x
1
,
…
,
x
m
) to evaluate V
K
x.Game 3.
It is similar to Game 2, with the difference that each valueR
K
(
i
,
j
) is replaced by a random element R
i
,
j
∈
G
1.We use a hybrid way to perform the proof, with the following claims.Corollary 4.
P
r
[
G
0
(
A
)
=
1
]
=
P
r
G
1
A
=
1.Proof.
This claim holds in an obvious way, since the change of algorithm for evaluatingV
K
Xdoes not change the distribution of its values. Thus the probability that the adversary wins is the same in both Games 0 and 1.Corollary 5.
P
r
G
1
A
=
1
=
P
r
G
2
A
=
1.Proof.
The difference between Games 2 and 1 is the coefficients of the target matrix. According to the confidentiality proof, these coefficients are indistinguishable since eachN
i
,
j is chosen uniformly at random, thus sharing the same distribution in the view of the adversary.Corollary 6.
P
r
G
2
A
=
1
=
P
r
G
3
A
=
1
≤
ϵ
p
r
f, whereϵ
p
r
frepresents the probability in the pseudorandomness definition of PRF.Proof.
The difference between Games 3 and 2 is that the output of PRFR
K
(
x
) is replaced by uniformly random elements in G
1. According to the pseudorandomness property of PRF, the probability that an adversary A distinguishes the two values is no better than ϵ
p
r
f.Corollary 7.
P
r
G
3
A
=
1
≤
ϵ
c
d
h, where ϵ
c
d
h represents the probability that an adversary solves co-CDH problem.The proof of this corollary is the same as that in [2]; we omit it here.Combining the four claims together, we obtain that(40)
P
r
E
X
P
A
π
,
F
,
λ
=
1
≤
ϵ
p
r
f
+
ϵ
c
d
h
.


## 5.3.1. Correctness

Correctness is easy to prove. Letσ
o
u
t
,
V
K
x
,
R
K
x be as above. For i
=
1
,
…
,
n,(37)
e
^
w
i
,
h
=
e
^
∏
j
=
1
m
E
i
,
j
x
j
′
,
h
=
e
^
∏
j
=
1
m
g
α
·
M
i
,
j
′
·
R
K
i
,
j
x
j
′
,
h
=
e
^
∏
j
=
1
m
g
α
M
i
,
j
′
x
j
′
,
h
·
e
^
∏
j
=
1
m
R
K
i
,
j
x
j
′
,
h
=
e
^
g
α
y
i
′
,
h
·
e
^
t
i
,
h
=
e
^
g
,
h
α
y
i
′
·
v
i
.The above proves the correctness for evaluatingy
→
′
=
M
x
→
′, and this implies the correctness of y
→
=
y
→
′
-
M
r
→
-
N
x
→
-
N
r
→.


## 5.3.2. Result Confidentiality and Input Privacy

The result confidentiality is similar to the polynomial case. We prove that, given the tuple(
P
P
,
E
K
F
,
V
K
,
σ
x
,
σ
o
u
t
), the adversary cannot extract the result vector y
=
M
x.LetM
,
N
,
x
→
,
r
→
,
y
→
,
y
→
′ be as above; then we have that(38)
y
i
=
∑
j
=
1
m
M
i
,
j
·
x
jand(39)
y
i
′
=
∑
j
=
1
m
M
i
,
j
+
N
i
,
j
·
x
j
+
r
j
=
∑
j
=
1
m
M
i
,
j
·
r
j
+
∑
j
=
1
m
N
i
,
j
·
x
j
+
∑
j
=
1
m
N
i
,
j
·
r
j
+
∑
j
=
1
m
M
i
,
j
·
x
j
.Notice that the blinding matrix has at least one nonzero element in each row, and the nonzero elements are all chosen uniformly at random. Thus they
i are all blinded by a random nonzero element, which makes the confidentiality of y
→ hold.As an additional bonus, the random sparse vectorr
→ that is added to the input x
→ provides some preservation to the privacy of input value. Since the vector is sparse, with 1
-
δ
m coordinates being 0, such blinding operation may preserve the input privacy at a degree of 1
-
δ; namely, the adversary may successfully guess one entry of the input vector with this probability. However since the position of 0 elements is chosen at random, the probability of the adversary to recover 1
-
δ fraction of the input data is 1
/
m
δ
m.


## 5.3.3. Security

The proof of the security follows that in [2]. We take it as an inspiration and define the following four games.Game 0.
It is the same asE
x
p
e
r
i
m
e
n
t
E
X
P
A
[
π
,
F
,
λ
].Game 1.
It is similar to Game 0, with the difference thatE
K
F contains an n
×
m random matrix from Z
p
n
×
m instead of N.Game 2.
It is similar to Game 1, with the difference that theProbGen phase uses an inefficient algorithm ∏
j
=
1
m
R
K
i
,
j
x
j instead of the C
F
E
v
a
l
P
o
l
y
(
K
,
x
1
,
…
,
x
m
) to evaluate V
K
x.Game 3.
It is similar to Game 2, with the difference that each valueR
K
(
i
,
j
) is replaced by a random element R
i
,
j
∈
G
1.We use a hybrid way to perform the proof, with the following claims.Corollary 4.
P
r
[
G
0
(
A
)
=
1
]
=
P
r
G
1
A
=
1.Proof.
This claim holds in an obvious way, since the change of algorithm for evaluatingV
K
Xdoes not change the distribution of its values. Thus the probability that the adversary wins is the same in both Games 0 and 1.Corollary 5.
P
r
G
1
A
=
1
=
P
r
G
2
A
=
1.Proof.
The difference between Games 2 and 1 is the coefficients of the target matrix. According to the confidentiality proof, these coefficients are indistinguishable since eachN
i
,
j is chosen uniformly at random, thus sharing the same distribution in the view of the adversary.Corollary 6.
P
r
G
2
A
=
1
=
P
r
G
3
A
=
1
≤
ϵ
p
r
f, whereϵ
p
r
frepresents the probability in the pseudorandomness definition of PRF.Proof.
The difference between Games 3 and 2 is that the output of PRFR
K
(
x
) is replaced by uniformly random elements in G
1. According to the pseudorandomness property of PRF, the probability that an adversary A distinguishes the two values is no better than ϵ
p
r
f.Corollary 7.
P
r
G
3
A
=
1
≤
ϵ
c
d
h, where ϵ
c
d
h represents the probability that an adversary solves co-CDH problem.The proof of this corollary is the same as that in [2]; we omit it here.Combining the four claims together, we obtain that(40)
P
r
E
X
P
A
π
,
F
,
λ
=
1
≤
ϵ
p
r
f
+
ϵ
c
d
h
.


## 5.4. Performance Analysis

We also analyze the computational complexity of the proposed CP-PVC scheme for matrix-vector multiplication and compare it with existing works [2, 19]. Analogous to polynomial case, we first give detailed analysis on the computational costs of each algorithm in matrix-vector multiplication case. Let each letter denote the same item as that in the proposed scheme above. In theKeyGen phase, to compute the term E
j
T, the client needs to execute 3
n
m
+
1 times of exponential modulo and 2
n
m times of multiplication arithmetic in group G
1. To compute the matrix M
′, since N is sparse, only n times of addition arithmetic in N are executed. To generate the public key, one time of pairing arithmetic is executed. In theProbGen phase, the client first needs to execute δ
m times of addition arithmetic in N to get σ
x. To generate the public verification key V
K
x, algorithm C
F
E
v
a
l
M
a
t
x
(
·
) is executed together with n times of pairing arithmetic. And to generate the private retrieval key, the client needs to execute three times of matrix-vector multiplication arithmetic with computation complexity being O
(
δ
n
m
), O
(
n
), and O
(
δ
n
), respectively. In theCompute phase, the cloud server needs to execute one time of dense matrix-vector multiplication arithmetic to compute y
′ and n
m times of exponential modulo and n
(
m
-
1
) times of multiplication in group G
1 to compute term W. In thePubVer phase, to compute the corresponding terms in the checking equation, the third party verifier needs to execute n times of pairing arithmetic, n times of exponential modulo arithmetic in G
T, and n times of multiplication arithmetic in G
T, respectively. Finally, in thePrivRet phase, the client firstly needs to execute what is done inPubVer phase and then execute, respectively, three times of vector subtraction arithmetic in N to compute the result y.Next we present a complexity comparison between our scheme and existing works of PVC schemes for matrix-vector multiplication [2, 19]. Similar to the polynomial case, We also use the notation O to compare computational complexity. According to the specific analysis of each algorithm, the arithmetic computations take place in ring N and group G
1, G
2, G
T. Thus we only use two types of notation, O
N and O
E, where O
N denotes the time complexity of operations in ring N including addition and multiplication and O
E denotes the time complexity of operations in group G
1, G
2, G
T including multiplication, exponentiation, and bilinear map. Let n
×
m be the problem size; then the comparison result is shown in Table 4. From the table we can see that, compared with the scheme in [2], ours has a complexity increase of O
N
(
δ
n
m
) inProbGen and O
N
(
n
) inPrivRet performed by the client. However, when the value of δ is small, the part O
N
(
δ
n
m
) will be much less expensive than O
E
(
n
+
m
). And O
N
(
n
) is surely less expensive than O
E
(
n
). Therefore, by choosing a proper δ, the impact of the increasing complexity will not be obvious in the real performance. Compared with the scheme in [19], ours has a complexity increase of O
E
(
n
)
+
O
N
(
δ
n
m
) inProbGen and O
N
(
n
) inPrivRet performed by the client. If n
≤
m, or the difference between n and m is small, the complexity of O
E
(
m
) and O
E
(
n
+
m
) is nearly the same. Under this circumstance, our scheme can achieve a comparative performance with a small δ chosen. What is more, our scheme achieves result confidentiality and partial input privacy that are considered to be important for user privacy.Table 4
Comparison of the three PVC schemes for matrix vector multiplication.
FG12 [2]
EOA16 [19]
Ours
KeyGen
O
E
(
n
m
)
O
E
(
n
m
)
+
O
N
(
n
m
)
O
E
(
n
m
)
+
O
N
(
n
)
ProbGen
O
E
(
n
+
m
)
O
E
(
m
)
O
E
(
n
+
m
)
+
O
N
(
δ
n
m
)
Compute
O
E
(
n
m
)
+
O
N
(
n
m
)
O
E
(
n
m
)
+
O
N
(
n
m
)
O
E
(
n
m
)
+
O
N
(
n
m
)
PubVer
O
E
(
n
)
O
E
(
n
)
O
E
(
n
)
PrivRet
⊥
⊥
O
E
(
n
)
+
O
N
(
n
)
Result confidentiality
No
No
Yes
Input Privacy
No
No
PartialWe also provide an experimental evaluation on the client side to show the efficiency compared with direct algorithm for matrix-vector multiplication. Different from that in polynomial case, we have a sparse coefficientδ in matrix-vector case. We choose different δ values and show the time cost for different sizes of problems in Table 5, which is done in the previous conference version of this paper [24]. Note that in theProbGen phase, the time cost of V
K generation is related only to n
,
m but not to δ. However, the time cost of R
K generation is related to not only n
,
m but also δ. With a smaller δ, one can get a more efficient CP-PVC scheme, but this inevitably brings more risks to input privacy. This seems inherently a trade-off. Also, note that the computations in thePubVer andPrivRet phase are n times of bilinear map operation and three times of vector subtraction, respectively. This part of cost is too small to be counted in, so we omit it from the table.Table 5
Time cost under differentδ values [24].
n
×
m
Original cost
VK_Gen
RK_Gen (δ
=
0.5)
RK_Gen (δ
=
0.2)
1000
×
50000
1.4508s
0.0077s
0.6864s
0.2652s
1000
×
100000
3.3228s
0.0156s
1.2728s
0.5460s
1000
×
200000
7.9092s
0.0312s
2.9484s
1.0764s
1000
×
400000
14.1683s
0.0624s
6.4428s
2.1840sFrom the table we can see that, no matter what the choice ofδ is, the total cost of V
K generation and R
K generation is much less than the original cost of matrix multiplication. Things can be more visualized in the column diagram of Figures 2 and 3 [24], where the volume of V
K generation (blue) and R
K generation (green) together is less than that of the original cost (red). Even when counting in the omitted time cost ofPubVer andPrivRet phase, the CP-PVC scheme achieves an acceptable efficiency performance in practice.Figure 2
Time cost of different problem sizes (×
1000) when δ
=
0.5 [24].Figure 3
Time cost of different problem sizes (×
1000) when δ
=
0.2 [24].


## 6. Conclusion

We have proposed confidentiality-preserving publicly verifiable computation schemes for multivariate polynomial evaluation and matrix-vector multiplication. The proposed schemes achieve both public verifiability and result confidentiality, while the latter one also achieves partial input privacy. These security properties are considered to be important in practical application of publicly verifiable computation. With the experimental evaluation we have done, the scheme is also acceptable in practice.



---

*Source: 5275132-2018-06-21.xml*