# Verifiable and Private Oblivious Polynomial Evaluation

Manik Lal Das, Hardik Gajera, David Gerault, Matthieu Giraud, Pascal Lafourcade

► To cite this version:

Manik Lal Das, Hardik Gajera, David Gerault, Matthieu Giraud, Pascal Lafourcade. Verifiable and Private Oblivious Polynomial Evaluation. 13th IFIP International Conference on Information Security Theory and Practice (WISTP), Dec 2019, Paris, France. pp.49-65, 10.1007/978-3-030-41702-4_4 . hal-02412789

HAL Id: hal-02412789

https://hal.science/hal-02412789

Submitted on 13 Mar 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Verifiable and Private Oblivious Polynomial
Evaluation

Manik Lal Das and Hardik Gajera and David Gérault and Matthieu Giraud
and Pascal Lafourcade

**Abstract.** It is a challenging problem to delegate the computation of a polynomial on encrypted data to a server in an oblivious and verifiable way. In this paper, we formally define *Verifiable and Private Oblivious Polynomial Evaluation* (VPOPE) scheme. We design a scheme called Verifiable IND-CFA Paillier based Private Oblivious Polynomial Evaluation (VIP-POPE). Using security properties of Private Polynomial Evaluation (PPE) schemes and Oblivious Polynomial Evaluation (OPE) schemes, we prove that our scheme is *proof unforgeability, indistinguishability against chosen function attack, and client privacy-secure* under the Decisional Composite Residuosity assumption in the random oracle model.

**Keywords:** Delegation of computation · Verifiable computation · Oblivious evaluation · Privacy.

# 1 Introduction

From harmless smart gardening [19] to critical applications such as forest fire
detection [17], data monitoring through sensors is becoming pervasive. In par-
ticular, sensors for monitoring health-related data are more and more widely
adopted, be it through smartwatches that track the heart rate, or sensors imple-
mented in the patient's body [2]. This medical data can sometimes be used to
assess the health status of an individual, by applying a single variable polynomial
prediction function on it [7]. However, when it comes to medical data, extreme
care must be taken in order to avoid any leakage. Recently, the leak of medical
data of 1.5 million SingHealth users in Singapore strongly incentivized to im-
prove the security and privacy surrounding medical data [1]. In this context, we
consider the following problem:

*How can a company use medical data recorded by clients to give them predictions about their health status in a private way?*

For instance, this company may collect Fitbit data from its customers, and
use it to predict things such as a risk factor for certain diseases. For economic
reasons, this company keeps the polynomial secret: it invested time to build it,
and required to collect lots of data. Its economic model is based on the secrecy of
the polynomial: the clients pay the company to obtain the polynomial's output on
their medical data. If the polynomial was public, then the clients would directly
compute it, and the company would cease to exist. However, as the company grows, it becomes difficult to treat all the computation requests, so that the company needs to delegate this computation to a cloud service. The company trusts the cloud service provider and gives the secret polynomial; however, the clients may not trust the server to produce correct results, so that the company would like the server to be able to prove the correctness of each prediction to the client, i.e., prove that its output is correct with regards to the secret prediction function.

<figure><img src="image_2.png" /><figcaption>Fig. 1: Illustration of a PPE scheme.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 2: Illustration of a VPOPE scheme.</figcaption></figure>

In this scenario, the problem is how to delegate computations on a secret polynomial function to an external server in a verifiable way. This problem is solved by *Private Polynomial Evaluation (PPE)* schemes [1, 11, 3, 24] illustrated in Fig. 1. In a PPE scheme, the company outsources the secret polynomial function $f(\cdot)$ to an external server. Moreover, the company provides some public information vk called *verification key*. This verification key is used with the proof $\pi$ generated by the server during the delegated computation of $f(x)$ to allow clients to verify the correctness of the result returned by the server.

However, PPE schemes do not protect the privacy of the clients: their data is handled in clear by the server. After the SingHealth hack, the company wants to be sure that even if an intruder hacks the server, he will not be able to steal the medical data of its clients. To solve this problem, we propose a new primitive called *Verifiable and Private Oblivious Polynomial Evaluation (VPOPE)*. A VPOPE scheme is a private polynomial evaluation scheme, in which the data of the client cannot be read by the cloud server. More precisely, the client sends his encrypted data to the server, and the server never learns anything about $x$. We illustrate this new primitive in Fig. 2.

## 1.1 Related Works

VPOPE schemes are related to several research domains. The first one is the *Verifiable Computation* (VC) introduced by Gennaro et al. [13]. The aim of VC is to delegate a costly computation to an untrusted third party. This third party returns the result of the computation and a proof of correctness, which is easier
to verify. Primitives where everyone can check the correctness of the computation
are said to be *publicly verifiable* [23]. VC has given rise to a bunch of protocols [5,
9, 6, 22, 21]. Although VC is related to our paper; the difference is that in these
works, the polynomial used by the server is not secret.

Another similar primitive is *Oblivious Polynomial Evaluation* (OPE) intro-
duced by Naor and Pinkas [18]. OPE protocols are constituted of two parties.
The first party, *A*, knows a secret function *f*(*x*) and the other one, *B*, has a secret
element *x*. The aim of OPE is that *B* receives *f*(*x*) in such a way *A* learns noth-
ing about the value *x* sent by *B*, and that *B* learns nothing about the function
*f*(*x*). OPE are used to solve different cryptographic problems as set membership,
oblivious keyword search, and set intersection [16, 11, 10]. Although OPE and
VPOPE are very similar; their difference lies in the fact that OPE do not con-
sider the verifiability of the computation of *f*(*x*), whereas it is a crucial point in
VPOPE since the client does not trust the server.

Finally, the nature of VPOPE is very close to those of *Private Polynomial Evaluation* (PPE). To the best of our knowledge, only five papers [15, 14, 12, 4, 25] propose to hide a polynomial used by the server and allow a client to verify the returned results. Kate *et al.* [15] formally define a primitive called *commitments to polynomials* that can be used as a PPE scheme and propose the *PolyCommit*<sub>Ped</sub> scheme. In this primitive, the committer publishes some points (*x*, *y*) of the secret polynomial together with a proof that *y* = *f*(*x*). Then, she can open the commitment *a* *posteriori* to reveal the secret polynomial. This is primitive is close to PPE and VPOPE schemes since the verification key used in PPE and VPOPE can be viewed as a commitment. However, this verification key is computed by a trusted party (the company) and computations are performed by an untrusted party (the server). Although the verification cost is in constant-time, it uses three pairing computations, and we show that, in practice, the verification cost of our VPOPE scheme is more efficient (see Section 5.2).

Independently of Kate et al. [15], Guo et al. [14] propose a scheme with
similar security properties to delegate the computation of a secret health-related
function on the users’ health record. The polynomials are explicitly assumed to
have low coefficients and degree, which significantly reduces their randomness.
However, the authors give neither security models nor proofs. Later, Gajera
et al. [12] show that any user can guess the polynomial using the Lagrange’s
interpolation on several points. They propose a scheme where the degree *k* is
hidden and claim that it does not suffer from this kind of attack.

Following this work, Bultel et al. [4] show that hiding the degree *k* is useless
and that no scheme can be secure when user query more than *k* points to the
server. Moreover, they give a cryptanalysis of Guo et al. [14] PPE scheme and
of Gajera et al. [12] PPE scheme which requires only one query to the server
and present the first security model for PPE schemes. A PPE scheme must
satisfy the following properties: (i) proof unforgeability (UNF) requires that the
server cannot provide a valid proof to the client for a point that is not a point
of the secret polynomial; (ii) indistinguishability against chosen function attack
(IND-CFA) requires that the client cannot distinguish which of two polynomials of
her choice has been evaluated by the server. Bultel et al. show that PolyCommit$_{Ped}$ scheme from Kate et al. [15] satisfies these security properties. Moreover, Bultel et al. design a PPE scheme called PIPE that is IND-CFA secure and solves an open problem described by Kate et al. concerning the design of a scheme with a weaker assumption than t-SDH. Despite having the additional property that it protects the privacy of the client, we show that the verification of our VPOPE scheme is more efficient than for PIPE.

More recently, Xia et al. [25] proposed a new efficient PPE scheme. As PIPE, their scheme satisfies the required security properties defined in [4]. Their scheme is based on the Pedersen's Verifiable Secret Sharing [24] and does not depend on NIZKP to allow the client to verify the correctness of the result contrary to Bultel et al. [4]. In addition to have computational advantages over previous PPE schemes, Xia et al.'s scheme relies only on the Discrete Logarithm assumption. However, the verification cost of Xia et al.'s scheme also requires $k$ exponentiations where $k$ is the degree of the secret polynomial, which makes it costlier than our scheme that needs only three exponentiations, one Paillier decryption, and $k$ multiplications.

## 1.2 Contributions

The contributions of this paper are summarized as follows:

- We formally define the VPOPE schemes and give security framework based on those of PPE and *Oblivious Polynomial Evaluation (OPE)* schemes.

- We design VIP-POPE (for *Verifiable IND-CFA Paillier based Private Oblivious Polynomial Evaluation*), an efficient and secure VPOPE scheme. This scheme uses homomorphic properties of Paillier's encryption scheme [20] in order to achieve encrypted polynomial evaluation.

- We also formally prove its security in the random oracle model and compare its efficiency for the verification cost with the existing PPE schemes. We show that VIP-POPE is more efficient for the verification part than PPE schemes presented in [15, 4, 25].

## 1.3 Outline

In the next section, we recall the cryptographic notions used in this paper. In Section 3, we give the PPE and OPE security model for VPOPE schemes. Then, we present in Section 4, our VPOPE scheme called VIP-POPE. Before to conclude, we prove in Section 5 that VIP-POPE satisfies the security properties for VPOPE schemes and compare its verification cost with other PPE schemes of the literature.

# 2 Preliminaries

We start by recalling the definition of the cryptographic tools used in this paper. In the rest of the paper, we denote by $POLY(\eta)$ the set of probabilistic polynomial time algorithms with respect to the security parameter $\eta$.
## 2.1 Paillier Cryptosystem

We now recall the generation, the encryption and decryption algorithms of the Paillier's public key encryption scheme [20] used in our scheme.

**Key Generation.** We denote by $Z_n$, the ring of integers modulo $n$ and by $Z_n^*$ the set of invertible elements of $Z_n$. The public key pk of Paillier's encryption scheme is $(n, g)$, where $g \in Z_{n^2}$ and $n = pq$ is the product of two prime numbers.

The corresponding secret key sk is $(\lambda, \mu)$, where $\lambda$ is the least common multiple of $p-1$ and $q-1$ and $\mu = (L(g^{\lambda} \bmod n^2))^{-1} \bmod n$, where $L(x) = \frac{x-1}{n}$.

**Encryption Algorithm.** Let $m$ be a message such that $m \in Z_n$. Let $r$ be a random element of $Z_n^*$. We denote by $\mathcal{E}_{pk}$ the encryption algorithm that produces the ciphertext $c$ from a given plaintext $m$ with the public key pk = $(n, g)$ as follows: $c = \mathcal{E}_{pk}(m) = g^m r^n \bmod n^2$.

**Decryption Algorithm.** Let $c$ be the ciphertext such that $c \in Z_{n^2}$. We denote by $\mathcal{D}_{sk}$ the decryption function of the plaintext $c$ with the secret key sk = $(\lambda, \mu)$ defined as follows: $m = \mathcal{D}_{sk}(c) = L(c^{\lambda} \bmod n^2) \cdot \mu \bmod n$.

Paillier's cryptosystem is a partial homomorphic encryption scheme. Let $m_1$ and $m_2$ be two plaintexts in $Z_n$. The product of the two associated ciphertexts with the public key pk = $(n, g)$, denoted $c_1 = \mathcal{E}_{pk}(m_1) = g^{m_1} r_1^n \bmod n^2$ and $c_2 = \mathcal{E}_{pk}(m_2) = g^{m_2} r_2^n \bmod n^2$, is the encryption of the sum of $m_1$ and $m_2$. We also remark that: $\mathcal{E}_{pk}(m_1) \cdot \mathcal{E}_{pk}(m_2)^{-1} = \mathcal{E}_{pk}(m_1 - m_2)$ and $\mathcal{E}_{pk}(m_1)^{m_2} = \mathcal{E}_{pk}(m_1 m_2)$.

**Theorem 1.** Paillier's cryptosystem is IND-CPA-secure if and only if the Decisional Composite Residuosity Assumption holds [20].

To present our scheme, we first claim the following property on Paillier ciphertexts.

*Property 1.* Let $n$ be the product of two prime numbers, $x \in Z_n$, and $g \in Z_{n^2}^*$. We set $\mathbf{pk} = (n, g)$ a Paillier public key. Let $\{t_i\}_{i=1}^k$ such that for all $i \in \{1, \dots, k\}$, we have $t_i = t_{i-1}^x \cdot r_i^n$ with $t_0 = g$, and $r_i \in Z_{n^2}^*$. Then for all $i \in \{1, \dots, k\}$, $t_i = \mathcal{E}_{pk}(x^i)$.

## 2.2 Zero-Knowledge Proof

We use the ZKP given by Baudron et al. [3] to prove the plaintexts equality of $k \in \mathbb{N}$ Paillier ciphertexts. Let $Z_{n^2}^*$ be a multiplicative group where $n$ is the product of two prime numbers $p$ and $q$. The language is the set of all statements $(t_1, \dots, t_k) \in (Z_{n^2}^*)^k$ for $k \in \mathbb{Z}_{\ge 2}$ such that for all $i \in \{1, \dots, k\}$, $t_i = t_{i-1}^x \cdot r_i^n \bmod n^2$ where $t_0 \in Z_{n^2}^*$ and $r_i \in Z_{n^2}^*$.

Since the ZKP given by Baudron et al. [3] is a sigma protocol, we can use the *Fiat-Shamir Transformation* [8] to obtain a NIZKP. We formally define this NIZKP called *DecPaillierEq*.

**Definition 1 (DecPaillierEq [3]).** Let $n$ be the product of two prime numbers $p$ and $q$ and $H$ be a hash function, $\mathcal{L}$ be the set of all $(t_1, \dots, t_k) \in (Z_{n^2}^*)^k$ such that for all $i \in \{1, \dots, k\}$, $t_i = t_{i-1}^x \cdot r_i^n \bmod n^2$ where $t_0 \in Z_{n^2}^*$ and $r_i \in Z_{n^2}^*$. We define the NIZKP DecPaillierEq = (Prove, Verify) for $\mathcal{L}$ as follows:
- Prove((t₁, ..., tₖ), ω): Using the witness ω = (x, t₀, {rᵢ}ᵢ=₁)ₖ, it picks ρ ← [0, 2^log(n)] and sᵢ ∈ Zₙ* for 1 ≤ i ≤ k, and computes uᵢ = tᵢ' sᵢ^n mod n² for 1 ≤ i ≤ k. Moreover, it computes w = ρ + x · H(t) and sets vᵢ = sᵢ · rᵢ^H(t) mod n for 1 ≤ i ≤ k. Finally, it outputs πₜ = (w, {uᵢ}ᵢ=₁, {vᵢ}ᵢ=₁).
- Verify((t₁, ..., tₖ), πₜ): Using πₜ = (w, {uᵢ}ᵢ=₁, {vᵢ}ᵢ=₁), it verifies if w ∈ [0, 2^log(n)], and if tᵢ' sᵢ^n = uᵢ · rᵢ^H(t) mod n² for 1 ≤ i ≤ k. Then it outputs 1, else 0.

- Verify((t₁, ..., tₖ), πₜ): Using πₜ = (w, {uᵢ}ᵢ=₁, {vᵢ}ᵢ=₁), it verifies if w ∈ [0, 2^log(n)], and if tᵢ' sᵢ^n = uᵢ · rᵢ^H(t) mod n² for 1 ≤ i ≤ k. Then it outputs 1, else 0.

Moreover, Baudron et al. [3] prove the following theorem.

**Theorem 2.** *DecPaillierEq is unconditionally complete, sound and zero-knowledge in the random oracle model.*

3 Definition and Security Model

Before we present our security model, we first formally define a Private Oblivious
Polynomial Evaluation scheme.

**Definition 2.** A Verifiable and Private Oblivious Polynomial Evaluation (VPOPE) scheme is composed of eight algorithms (**setup**, **init**, **keyGen**, **queryGen**, **queryDec**, **compute**, **decrypt**, **verif**) defined as follows:

- setup(η) : Using the security parameter η, this algorithm generates a ring F,
  public parameters **pub** and secret parameters **sec**. It returns (**pub**, **F**, **sec**).

- init(F, f, sec) : Using F, the secret polynomial f, and parameters sec, this algorithm returns a verification key vk and a server key skf associated to the secret polynomial f.

- keyGen(η, pub, k) : Using the security parameter η and public parameters pub, this algorithm generates and returns a client's key pair (pkc, skc).

- queryGen(pkc, x) : Using a public key pkc and an input x, this algorithm generates an encrypted query t associated to x, a proof πt proving that t is a valid encrypted query, and returns (t, πt).

- queryDec(sk_c, t) : Using a secret key sk_c and an encrypted request t, this algorithm outputs x if t is a valid request of x, ⊥ otherwise.

- compute(t, π_t, f, sk_f, F) : Using t, π_t, f, sk_f, and F, this algorithm returns an encrypted value d along with a proof π_d proving that d is an encryption of f(x) if the proof π_t is "accepted". Else it returns ⊥.

- decrypt(sk_c, d) : Using a secret key sk_c and the encrypted value d, this algorithm returns y, the decryption of d.

- verif(x, sk_c, pub, y, π_d, vk) : This algorithm returns 1 if the proof π_d is "accepted", 0 otherwise.

3.1 Security Models

We use security notions of PPE schemes formalized by Bultel et al. [4], namely Unforgeability (UNF), and Indistinguishability against Chosen Function Attack (IND-CFA), and adapt them to VPOPE

**Exp<sup>CPI</sup><sub>Π,A</sub>(η):**

b ← {0, 1};
    (pub, F, sec) ← setup(η);

f ← F[X]<sup>k</sup>;
    (vk, sk<sub>f</sub>) ← init(F, f, sec);
    (pk<sub>c</sub>, sk<sub>c</sub>) ← keyGen(η, pub, k);
    (x<sub>0</sub>, x<sub>1</sub>, st) ← A<sub>1</sub>(pk<sub>c</sub>, pub, F);
    (t, π<sub>t</sub>) ← queryGen(pk<sub>c</sub>, x<sub>b</sub>);

b* ← A<sup>CO<sub>CPI</sub>(·)</sup><sub>2</sub>(t, f, sk<sub>f</sub>, F, st);
return (b = b*).

**CO<sub>CPI</sub>(x):**

(t, π<sub>t</sub>) ← queryGen(pk<sub>c</sub>, x);
return t.

<caption>Fig. 3: CPI experiment.</caption>
schemes. The security model IND-CFA ensure secrecy of the polynomial, the security model UNF ensures validity of the verification process. Since VPOPE schemes consider encrypted data on client side, we recall the Client's Privacy - Indistinguishability (CPI) security property defined by Naor and Pinkas [18] to include the privacy on data client. Moreover, we define the Query Soundness (QS) notion in order to prove that a client cannot have other information than points that she queried. In all the security models, we denote by $F[x]^k$, the set of all polynomials of degree $k$ over a finite field $F$.

## Client's Privacy - Indistinguishability

We first recall the Client's Privacy - Indistinguishability (CPI) security for VPOPE schemes introduced by Naor and Pinkas [18]. In this model the adversary chooses two queries $(x_0, x_1)$ and tries to guess the evaluation $x_b$ asked by the client. The adversary has access to the ciphertext oracle $CO_{CPI}(\cdot)$ taking $x$ as input and returns the encrypted query $t$. A VPOPE scheme is CPI-secure if no adversary can output the query chosen by the client with a better probability than by guessing.

**Definition 3 (Client's privacy - indistinguishability).** Let $\Pi$ be a VPOPE, $\mathcal{A} = (\mathcal{A}_1, \mathcal{A}_2) \in \text{POLY}(\eta)^2$ be a two-party adversary. The client's privacy - indistinguishability (CPI) experiment for $\mathcal{A}$ against $\Pi$ is defined in Fig. 3, where $\mathcal{A}$ has access to the oracle $CO_{CPI}(\cdot)$. The advantage of the adversary $\mathcal{A}$ against the CPI experiment is given by:

$$ \text{Adv}_{\Pi, \mathcal{A}}^{CPI}(\eta) = \left| \frac{1}{2} - \text{Pr} \left[ 1 \leftarrow \text{Exp}_{\Pi, \mathcal{A}}^{CPI}(\eta) \right] \right| $$

A scheme $\Pi$ is CPI-secure if this advantage is negligible for any $\mathcal{A} \in \text{POLY}(\eta)^2$.

## Chosen Function Attack

We recall the model for k-Indistinguishability against Chosen Function Attack (k-IND-CFA). In this model, the adversary chooses two polynomials $(f_0, f_1)$ and tries to guess the polynomial $f_b$ used by the server, where $b \in \{0, 1\}$. The adversary has access to a server oracle $CO_{CFA}(\cdot)$ and sends to her an

$\text{Exp}_{\Pi, \mathcal{A}}^{k-\text{IND-CFA}}(\eta)$:

b $\stackrel{\sim}{\leftarrow}$ $\{0, 1\}$;

(pub, F, sec) $\leftarrow$ setup($\eta$);

(pk$_c$, sk$_c$) $\leftarrow$ keyGen($\eta$, pub, k);

(f$_0$, f$_1$, st$_2$) $\leftarrow$ $\mathcal{A}_1(\text{pk}_c, \text{pub}, F, k)$;

c $\leftarrow$ 0;

(vk, sk$_f$) $\leftarrow$ init(F, f$_b$, sec);

b$_*$ $\leftarrow$ $\mathcal{A}_2^{\text{CO}_{\text{CFA}}(\cdot)}(\text{pk}_c, \text{pub}, F, \text{vk}, k, \text{st})$;

if $f_0 \notin F[X]^k$ or $f_1 \notin F[X]^k$:

then return $\perp$;

else return $(b = b_*)$.

$\text{CO}_{\text{CFA}}(t, \pi_t)$:

(d, $\pi_d$) $\leftarrow$ compute($t, \pi_t, f_b, \text{sk}_f, F$);

if $x \leftarrow \text{queryDec}(t, \text{sk}_c)$ and $x \neq \perp$ and $f_0(x) = f_1(x)$:

then return $(d, \pi_d)$;

else return $\perp$.

<caption>Fig. 4: IND-CFA experiment.</caption>
encrypted query $t$ associated to her data $x$ along with a proof $\pi_t$. The oracle decrypts the query $t$ and obtains $x$ if $t$ is valid. If $f_0(x) = f_1(x)$, the oracle returns $d$ i.e. the encrypted value of $f_b(x)$, along with a proof $\pi_d$. If $f_0(x) \neq f_1(x)$, then the server returns nothing. In practice, an adversary chooses $(f_0, f_1)$ such that $f_0 \neq f_1$, but with $k$ points $(x_i, y_i)$ such that $f_0(x_i) = f_1(x_i)$. It allows the adversary to maximize his oracle calls in order to increase his chances of success.

**Definition 4.** (k-IND-CFA). Let $\Pi$ be a VPOPE, $\mathcal{A} = (\mathcal{A}_1, \mathcal{A}_2) \in \text{POLY}(\eta)$ be a two-party adversary and $k$ be an integer. The k-IND-CFA experiment for $\mathcal{A}$ against $\Pi$ is defined in Fig. 4, where $\mathcal{A}$ has access to the server oracle $\text{CO}_{\text{CFA}}(\cdot)$. The advantage of the adversary $\mathcal{A}$ against the k-IND-CFA experiment is given by:

$$ \text{Adv}_{\Pi, \mathcal{A}}^{k\text{-IND-CFA}}(\eta) = \left| \frac{1}{2} - \text{Pr} \left[ 1 \leftarrow \text{Exp}_{\Pi, \mathcal{A}}^{k\text{-IND-CFA}}(\eta) \right] \right| . $$

A scheme $\Pi$ is k-IND-CFA-secure if this advantage is negligible for any $\mathcal{A} \in \text{POLY}(\eta)^2$.

## Query Soundness

We now define a model for Query Soundness (QS). In this model, the adversary tries to learn other information than points of the secret polynomial that she queried by sending a particular query $t$ along with a proof $\pi_t$ to the server.

Exp$^{QS}_{\Pi, \mathcal{A}}(\eta)$:
$(\text{pub}, F, \text{sec}) \leftarrow \text{setup}(\eta)$;
$f \stackrel{\$}{\leftarrow} F[X]^k$;
$(\text{vk}, \text{sk}_f) \leftarrow \text{init}(F, f, \text{sec})$;
$(\text{pk}_c, \text{sk}_c) \leftarrow \text{keyGen}(\eta, \text{pub}, k)$;
$(t, \pi_t) \leftarrow \mathcal{A}((\text{pk}_c, \text{sk}_c), \text{pub}, F)$;
if $\text{queryDec}(t) \neq \perp$ and $\text{compute}(t, \pi_t, f, \text{sk}_f, F) \neq \perp$ and $f(\text{queryDec}(\text{sk}_c, t)) \neq \text{decrypt}(\text{sk}_c, d)$ such that $(d, \pi_d) \leftarrow \text{compute}(t, \pi_t, f, \text{sk}_f, F)$:
then return 1;
else return 0.

<caption>Fig. 5: QS experiment.</caption>

**Definition 5 (Query Soundness).** Let $\Pi$ be a VPOPE, and $\mathcal{A} \in \text{POLY}(\eta)$ be an adversary. The Query Soundness (QS) experiment for $\mathcal{A}$ against $\Pi$ is defined in Fig. 5. The advantage of the adversary $\mathcal{A}$ against the QS experiment is given by:

$$ \text{Adv}_{\Pi, \mathcal{A}}^{\text{QS}}(\eta) = \text{Pr} \left[ 1 \leftarrow \text{Exp}_{\Pi, \mathcal{A}}^{\text{QS}}(\eta) \right] . $$

A scheme $\Pi$ is QS-secure if this advantage is negligible for any $\mathcal{A} \in \text{POLY}(\eta)$.

## Unforgeability
Exp<sub>Π,A</sub>(η):
/pub, F, sec) ← setup(η);
(f, st) ← A<sub>1</sub>(sec);
(vk, sk<sub>f</sub>) ← init(F, f, sec);
(pk<sub>c</sub>, sk<sub>c</sub>) ← keyGen(η, pub, k);
(x*, y*, π*) ← A<sub>2</sub>(pub, sk<sub>f</sub>, vk, F, f, st);
if f(x*) ≠ y* and verif(x*, sk<sub>c</sub>, pub, y*, π*, vk) = 1:
  then return 1;
else return 0.

Finally, we recall the unforgeability property. A VPOPE is un- forgeable when a dishonest server cannot produce a valid proof for a point (x, y) such that y ≠ f(x). In this model, the secret polynomial f is chosen by the server.

<caption>Fig. 6: UNF experiment.</caption>

**Definition 6 (Unforgeability).** Let $\Pi$ be a VPOPE, $\mathcal{A} = (\mathcal{A}_1, \mathcal{A}_2) \in \text{POLY}(\eta)$ be a two-party adversary. The unforgeability (UNF) experiment for $\mathcal{A}$ against $\Pi$ is defined in Fig. 6. We define the advantage of the adversary $\mathcal{A}$ against the UNF experiment by:

$$ \text{Adv}_{\Pi, \mathcal{A}}^{\text{UNF}}(\eta) = \Pr \left[ 1 \leftarrow \text{Exp}_{\Pi, \mathcal{A}}^{\text{UNF}}(\eta) \right]. $$

A scheme $\Pi$ is UNF-secure if this advantage is negligible for any $\mathcal{A} \in \text{POLY}(\eta)^2$.

## 3.2 Security Against Collusion Attacks

There are two possible collusion scenarios: collusion of a client and the server, and collusion of two or more clients.

**Scenario 1:** In collusion of a client and the server, the server can provide the secret polynomial to the client. This is inherent problem and cannot be prevented. The client can share public parameters and verification keys with the server but these parameters are already public and known to the server. The collusion does not give any advantage to the server to forge fake proof of computation.

**Scenario 2:** In collusion of two or more clients, sharing Paillier secret key with each other does not provide any information about the secret polynomial. All the verification keys and public parameters are same for each client. The inherent limitation is that the collusion of clients can share their evaluated points with each other and if the total number of points is more than $k$, where $k$ is the degree of the secret polynomial, then clients can derive the polynomial. This problem exists in any polynomial computation and cannot be prevented.

# 4 VIP-POPE Description

In our scheme, we assume that the server is not trusted with the computation result and clients are curious to learn about the secret polynomial. A client may forge an encrypted query to gain more information about the secret polynomial. We first give the intuition of our scheme VIP-POPE and then give its formal definition.
We use homomorphic properties of Paillier's cryptosystem to design our scheme called VIP-POPE. The key idea is to use the fact that a client can generate an encrypted query $t = \{t_i\}_{i=1}^k$ where $t_i = \mathcal{E}_{pk}(x^i)$ and $k$ is the degree of the secret polynomial $f(\cdot)$ to allow the server to compute $\mathcal{E}_{pk}(f(x))$. Since the server knows coefficients $\{a_i\}_{i=0}^k$ of $f(\cdot)$, it computes $\mathcal{E}_{pk}(f(x))$ as follows:

$$ \mathcal{E}_{pk}(a_0) \cdot \prod_{i=1}^{i=k} \mathcal{E}_{pk}(x^i) a_i = \prod_{i=0}^{i=k} \mathcal{E}_{pk}(a_i x^i) = \mathcal{E}_{pk} \left( \sum_{i=0}^{i=k} a_i x^i \right) = \mathcal{E}_{pk}(f(x)). $$

The client may forges an untrustworthy encrypted query to learn more than a point on the polynomial. To avoid this kind of attack, the client must provide a proof of validity $\pi_t$ for each query $t = \{t_i\}_{i=1}^k$ that she sends to the server, i.e., a proof that $t_i = \mathcal{E}_{pk}(x^i)$ for all $i \in \{1, \dots, k\}$. Based on Property 1, such a proof can be built using the NIZKP DecPaillierEq presented in Definition 1.

## 4.1 Formal Definition of VIP-POPE

We now give the formal definition of our scheme VIP-POPE. The algorithms setup and init are run by the company, the algorithm compute is run by the server and the algorithms keyGen, queryGen, decrypt and verif are run by a client.

**Definition 7.** Let VIP-POPE = (setup, init, keyGen, queryGen, queryDec, compute, decrypt, verif) be a scheme defined by:

- setup($\eta$) : Using the security parameter $\eta$, this algorithm first generates a prime number $q$. It selects a multiplicative group $G$ of order $q$ and generated by $h$. It picks $(s_1, s_2) \leftarrow (\mathbb{Z}_q^*)^2$ and sets $\text{pub} = (h^{s_1}, h^{s_2}, h, q)$, $\text{sec} = (s_1, s_2)$, and $F = \mathbb{Z}_q$. Finally, it outputs $\text{pub}, F$, and $\text{sec}$.

- init($F, f, \text{sec}$) : We set $f(x) = \sum_{i=0}^{i=k} a_i \cdot x^i$ where $a_i \in \mathbb{Z}_q$. For all $i \in \{0, \dots, k\}$, it picks $r_i \in \mathbb{Z}_q^*$ and computes $\alpha_i = (a_i+r_i) \cdot s_1$ and $\gamma_i = s_1 \cdot s_2^{-1} \cdot r_i$. Finally, it sets $\text{vk} = \{\gamma_i\}_{i=0}^k$, $\text{sk}_f = \{\alpha_i\}_{i=0}^k$, and returns $(\text{vk}, \text{sk}_f)$.

- keyGen($\eta$, pub, $k$) : For a client $c$, it picks two primes $p_c$ and $q_c$ such that $(k+1)q^2 < p_c q_c$ and $p_c \approx q_c$. It sets $n_c = p_c q_c$. According to $n_c$, it generates a Paillier key pair such that $\text{pk}_c = (n_c, g_c)$ and $\text{sk}_c = (\lambda_c, \mu_c)$ as described in Section 2. It outputs $(\text{pk}_c, \text{sk}_c)$.

- queryGen($\text{pk}_c, x$) : Using $x$ and the Paillier public key $\text{pk}_c$, this algorithm computes, for all $i \in \{1, \dots, k\}$, $t_i = \mathcal{E}_{pk}(x^i)$ and returns the encrypted query $t = (\text{pk}_c, \{t_i\}_{i=1}^k)$ along with a proof $\pi_t$ of equality of plaintexts using proof PaillierEq.

- queryDec($\text{sk}_c, t$) : First this algorithm parses $t$ as $(\text{pk}_c, \{t_i\}_{i=1}^k)$. Using the Paillier secret key $\text{sk}_c$, this algorithm sets $x = \mathcal{D}_{\text{sk}_c}(t_1)$. If $\mathcal{D}_{\text{sk}_c}(t_i) = x^i$ for $2 \le i \le k$, it outputs $x$, $\perp$ otherwise.

- compute($t, \pi_t, f, \text{sk}_f, F$) : If $\pi_t$ is accepted by verify PaillierEq, this algorithm uses $\{t_i\}_{i=1}^k$ from $t$, coefficients $\{a_i\}_{i=0}^k$ of the polynomial function $f(\cdot)$, and $\{\alpha_i\}_{i=0}^k$ from the server secret key $\text{sk}_f$ to compute:

$$ d = \mathcal{E}_{\text{pk}_c}(a_0) \cdot \prod_{i=1}^{i=k} t_i^{a_i} \quad \text{and} \quad \pi_d = \mathcal{E}_{\text{pk}_c}(\alpha_0) \cdot \prod_{i=1}^{i=k} t_i^{\alpha_i}, $$

and returns $(d, \pi_d)$, else it returns $\perp$.
- decrypt(sk_c, d) : Using the Paillier secret key sk_c which is equal to (λ_c, μ_c), this algorithm returns y = D_{sk_c}(d) mod q.

- verif(x, sk_c, pub, y, π_d, vk) : Using x, sk_c, vk, and the proof π_d, this algorithm computes:

$$y' = D_{sk_c}(\pi_d) \mod q \quad \text{and} \quad z = \sum_{i=0}^{i=k} \gamma_i \cdot x^i.$$

If $(h^{s_1})^y \cdot (h^{s_2})^z = h^{y'}$, then the algorithm returns 1, else it returns 0.

**Parameter Selection.** First, consider the additive group $F = \mathbb{Z}_q$ of order $q$. The size of the prime $q$ must be at least 1024 bits to make the discrete logarithm problem hard in the group $G$. We recall that the polynomial $f(\cdot)$ is equal to $\sum_{i=0}^{i=k} a_i \cdot x^i$ where $a_i \in \mathbb{Z}_q$ for all $i \in \{0, \dots, k\}$. Hence, all evaluations are in $\mathbb{Z}_q$; thus we assume that for all $i \in \{0, \dots, k\}$, we have $0 \le x^i < q$, and that $0 \le f(x) < q$. Moreover, the client encrypts for all $i \in \{1, \dots, k\}$ the value $x^i$. The evaluation performed by the server is done over encrypted values, i.e., $\mathcal{E}_{pk_c}(a_0) \cdot \prod_{i=1}^{i=k} \mathcal{E}_{pk_c}(x^i)^{a_i} = \mathcal{E}_{pk_c}(a_0 + a_1 \cdot x + \dots + a_k \cdot x^k)$; then, we need to have $\sum_{i=0}^{i=k} a_i \cdot x^i < n_c = p_c \cdot q_c$ for successful decryption due to Paillier cryptosystem properties, where $\mathbb{Z}_{n_c}$ is the plaintext space of Paillier cryptosystem, $p_c$ and $q_c$ are two prime numbers. Since $0 \le a_i < q$ and $0 \le x^i < q$, we have $a_i \cdot x^i < q^2$ for each $i \in \{0, \dots, k\}$ that gives us $a_0 + a_1 \cdot x + \dots + a_k \cdot x^k < (k+1) \cdot q^2$. Hence, we need to have $(k+1) \cdot q^2 < n_c$ to always have successful decryption. Moreover, we recommend the size of each prime $p_c$ and $q_c$ to be at least 1024 bits to make the factorization of $n_c$ hard.

# 5 Security and Performance Analysis

We first give a theorem on the security of VIP-POPE. Then we provide some comparisons with PPE schemes of the literature [15, 4, 25].

## 5.1 Security proofs

We present the security proofs of VIP-POPE in our security model.

**Theorem 3.** VIP-POPE is a CPI-secure scheme under the DCR assumption.

*Proof.* We assume there exists $\mathcal{A} \in \text{POLY}(\eta)^2$ such that $\text{Adv}_{\text{VIP-POPE},\mathcal{A}}^{\text{CPI}}$ is non-negligible and we show there exists an algorithm $\mathcal{B} \in \text{POLY}(\eta)$ such that $\text{Adv}_{\text{Paillier},\mathcal{B}}^{\text{IND-CPA}}(\eta)$ is non-negligible. We build $\mathcal{B}$ as follows:

- $\mathcal{B}$ receives $\mathbb{Z}_q$, sec from setup($\eta$) and pk_c from keyGen($\eta$, pub, k).

- $\mathcal{B}$ runs $(x_0, x_1, \text{st}) \leftarrow \mathcal{A}_1(\text{pk}_c)$.

- $\mathcal{B}$ picks $f \stackrel{\$}{\leftarrow} \mathbb{Z}_q[X]^k$ and runs init($\mathbb{Z}_q, f, \text{sec}$) to obtain vk and sk_f.

- $\mathcal{B}$ runs the oracle $\mathcal{E}_{pk}(\text{LR}_b(\cdot, \cdot))$ on $(x_0^i, x_1^i)$ for $i \in \{1, \dots, k\}$ and obtains $t = \{t_i\}_{i=1}^k$, Paillier ciphertexts of $x_b^i$.

- $\mathcal{B}$ runs $b_* \leftarrow \mathcal{A}_2(t, f, \text{sk}_f, \mathbb{Z}_q, \text{st})$. To simulate the oracle $\text{CO}_{\text{CPI}}(\cdot)$ on $x$ to $\mathcal{A}$, $\mathcal{B}$ computes $t = \{\mathcal{E}_{pk_c}(x^i)\}_{i=1}^k$.

- Finally, $\mathcal{B}$ outputs $b_*$.

We remark that:
1. The experiment CPI is perfectly simulated for $\mathcal{A}$.

2. $\mathcal{B}$ wins the IND-CPA experiment if and only if $\mathcal{A}$ wins the CPI experiment.

Since $\text{Adv}_{\text{VIP-POPE},\mathcal{A}}^{\text{CPI}}(\eta)$ is non-negligible, then $\text{Adv}_{\text{Paillier},\mathcal{B}}^{\text{IND-CPA}}(\eta)$ is non-negligible. However, Paillier cryptosystem is IND-CPA under the DCR assumption, then $\mathcal{B}$ can be used to break the DCR assumption, which contradicts our hypothesis and concludes the proof. $\square$

**Theorem 4.** For any $k \in \mathbb{N}$, VIP-POPE is a k-IND-CFA-secure scheme.

*Proof.* Let $\mathcal{A} \in \text{POLY}(\eta)$ be an algorithm. We show that there exists an algorithm $\mathcal{B} \in \text{POLY}(\eta)$ simulating the experiment $\text{Exp}_{\text{VIP-POPE},\mathcal{A}}^{k-\text{IND-CFA}}(\eta)$ to $\mathcal{A}$. We build $\mathcal{B}$ as follows:

- $\mathcal{B}$ picks $b \stackrel{\$}{\leftarrow} \{0, 1\}$.

- $\mathcal{B}$ generates $(\text{pub}, \mathbb{Z}_q, \text{sec}) \leftarrow \text{setup}(\eta)$, where $\text{pub} = (h^{s_1}, h^{s_2}, h)$, and $\text{sec} = (s_1, s_2) \in \mathbb{Z}_q^*$.

- $\mathcal{B}$ runs $(f_0, f_1, \text{st}) \leftarrow \mathcal{A}_1(\mathbb{Z}_q, k)$, and it sets $f_0(x) = \sum_{i=0}^{i=k} a_{0,i} \cdot x^i$ and $f_1(x) = \sum_{i=0}^{i=k} a_{1,i} \cdot x^i$.

- $\mathcal{B}$ picks $r \stackrel{\$}{\leftarrow} \mathbb{Z}_q^*$. For all $i \in \{0, \dots, k\}$, it picks $r_i \stackrel{\$}{\leftarrow} \mathbb{Z}_q^*$, and sets $\alpha_i = (a_{b,i} + r_i) \cdot s_1$, and $\gamma_i = s_1 \cdot s_2^{-1} \cdot r_i$. Finally, it sets $f'(x) = \sum_{i=0}^{i=k} \alpha_i \cdot x^i$, and returns $\text{vk} = \{\gamma_i\}_{i=0}^k$.

- $\mathcal{B}$ generates $(\text{pk}_c, sk_c) \leftarrow \text{keyGen}(\eta, \text{pub}, k)$.

- $\mathcal{B}$ runs $b_* \leftarrow \mathcal{A}_2((\text{pk}_c, sk_c), \text{pub}, \mathbb{Z}_q^*, \text{vk}, k, \text{st})$. To simulate the oracle $\text{CO}_{\text{CFA}}(\cdot)$ to $\mathcal{A}$ on $t = \{\mathcal{E}_{\text{pk}}(x^i)\}_{i=1}^k$, $\mathcal{B}$ first verifies if $f_0(\mathcal{D}_{\text{sk}_c}(\mathcal{E}_{\text{pk}_c}(x))) = f_1(\mathcal{D}_{\text{sk}_c}(\mathcal{E}_{\text{pk}_c}(x)))$ then computes:

$$d = \mathcal{E}_{\text{pk}_c}(a_{b,0}) \cdot \prod_{i=1}^{i=k} \mathcal{E}_{\text{pk}}(x_j^i)^{a_{b,i}}, \quad \pi_d = \mathcal{E}_{\text{pk}_c}(\alpha_0) \cdot \prod_{i=1}^{i=k} \mathcal{E}_{\text{pk}}(x_j^i)^{\alpha_i},$$

and returns $(d, \pi_d)$. Else, it returns $\perp$.

- Finally, $\mathcal{B}$ outputs $b_*$.

We remark that $r$ and $r_i$ (for $0 \le i \le k$) are chosen in the uniform distribution of $\mathbb{Z}_q^*$, then each element of $\text{vk}$ comes from the uniform distribution on $\mathbb{Z}_q^*$. Finally, we have:

$$ \begin{align*} (h^{s_1})^{f(x)} \cdot (h^{s_2})^{Z(x)} &= h^{s_1 \cdot \sum_{i=0}^{i=k} a_i \cdot x^i + s_2 \cdot \sum_{i=0}^{i=k} \gamma_i \cdot x^i} \\ &= h^{s_1 \cdot \sum_{i=0}^{i=k} a_i \cdot x^i + s_2 \cdot \sum_{i=0}^{i=k} s_1 \cdot s_2^{-1} \cdot r_i \cdot x^i} \\ &= h^{\sum_{i=0}^{i=k} (a_i + r_i) \cdot s_1 \cdot x^i} = h^{\sum_{i=0}^{i=k} \alpha_i \cdot x^i} = h^{f'(x)}. \end{align*} $$

We deduce that the experiment k-IND-CFA is perfectly simulated for $\mathcal{A}$. Then $\mathcal{A}$ cannot do better than the random to guess the value of the chosen $b$. Hence, we have:

$$\Pr[1 \leftarrow \text{Exp}_{\text{VIP-POPE},\mathcal{A}}^{k-\text{IND-CFA}}(\eta)] = 1/2,$$

and so $\text{Adv}_{\text{VIP-POPE},\mathcal{A}}^{k-\text{IND-CFA}}(\eta)$ is negligible which concludes the proof. $\square$
**Theorem 5.** For any $k \in \mathbb{N}$, VIP-POPE is QS-secure in the random oracle model.

*Proof.* The proof $\pi_t$ is computed as in DecPaillierEq (Definition 1). This NIZKP is unconditionally sound, then there exists no probabilistic polynomial time algorithm that forges a valid proof on a false statement with non-negligible probability, i.e., a statement $(t_1, \dots, t_k)$ where there exists $1 \le i \le k$ such that $t_i \ne t_{i-1}^x \cdot r_i^n$ where $n = p \cdot q$ and $p, q$ are two prime numbers, $t_0 \in \mathbb{Z}_{n^2}^*$, $r_i \in \mathbb{Z}_{n^2}^*$, and $x \in \mathbb{Z}_{n^2}^*$.

We show that if there exists $\mathcal{A} \in \text{POLY}(\eta)^2$ such that $\text{Adv}_{\text{VIP-POPE},\mathcal{A}}^{\text{QS}}(\eta)$ is non-negligible, then there exists $\mathcal{B} \in \text{POLY}(\eta)$ that forges a valid proof of an instance where $t_i \ne t_{i-1}^x \cdot r_i^n$. It contradicts the soundness of DecPaillierEq which concludes the proof. $\mathcal{B}$ works as follows:

- $\mathcal{B}$ runs $(\text{pub}, F, \text{sec}) \leftarrow \text{setup}(\eta)$, $(\text{pk}_c, \text{sk}_c) \leftarrow \text{keyGen}(\eta, \text{pub}, k)$, $(f, \text{st}) \leftarrow \mathcal{A}_1(\text{pk}_c, \text{pub}, F)$, $(\text{vk}, \text{sk}_f) \leftarrow \text{init}(F, f, \text{sec})$, and $(t, \pi_t) \leftarrow \mathcal{A}_2(\text{pk}_c, \text{pub}, F, \text{vk})$ where $\pi_t = (w, \{u_i\}_{i=1}^k, \{v_i\}_{i=1}^k)$.

- $\mathcal{B}$ returns $t$ as a statement together with the proof $\pi_t$.

We observe that since $\text{Adv}_{\text{VIP-POPE},\mathcal{A}}^{\text{QS}}(\eta)$ is non-negligible, then the probability that $f(\text{queryDec}(\text{sk}_c, t)) \ne \text{decrypt}(\text{sk}_c, d)$ and $\text{compute}(t, \pi_t, f, \text{sk}_f, F) \ne \bot$ is non-negligible. Moreover:

- $f(\text{queryDec}(\text{sk}_c, t)) \ne \text{decrypt}(\text{sk}_c, d) \Rightarrow f(x) \ne y$, that means there exists $1 \le i_0 \le k$ such that $\mathcal{D}_{\text{sk}_c}(t_i) \ne x^i$.

- $\text{compute}(t, \pi_t, f, \text{sk}_f, F) \ne \bot \Rightarrow t_{i-1}^w \cdot v_i^n = u_i \cdot t_i^{H(t)} \mod n^2$ for $1 \le i \le k$. Then $\pi_t$ is a valid proof.

$\mathcal{B}$ returns a valid proof of a false instance with non-negligible probability. $\square$

**Theorem 6.** For any $k \in \mathbb{N}$, VIP-POPE is UNF-secure under the DL assumption.

*Proof.* We assume there exists $\mathcal{A} \in \text{POLY}(\eta)^2$ such that $\text{Adv}_{\text{VIP-POPE},\mathcal{A}}^{\text{UNF}}(\eta)$ is non-negligible. We show that $\mathcal{A}$ can be used to construct an algorithm $\mathcal{B}$ that computes $\log_h(h^{s_1})$.

First, we note that if $y_* \ne f(x_*)$, then we also have $y'_* \ne y'$ where we denote $y'_* = \mathcal{D}_{\text{sk}_c}(\pi_*)$ and $y' = \sum_{i=0}^{i=k} \alpha_i \cdot x_i^*$. It is easy to check this condition. Therefore, we must have both inequalities $y_* \ne f(x_*)$ and $y'_* \ne y'$ hold. We show that there exists an algorithm $\mathcal{B} \in \text{POLY}(\eta)$ that breaks the DL assumption by computing $\log_h(h^{s_1})$ using $\mathcal{A}$. $\mathcal{B}$ works as follows:

- $\mathcal{B}$ obtains $(\text{pub}, F, \text{sec}) \leftarrow \text{setup}(\eta)$ and $(\text{pk}_c, \text{sk}_c) \leftarrow \text{keyGen}(\eta, \text{pub}, k)$.

- $\mathcal{B}$ receives $(f, \text{st}) \leftarrow \mathcal{A}_1(\text{pk}_c, \text{pub}, F)$.

- $\mathcal{B}$ runs $(\text{vk}, \text{sk}_f) \leftarrow \text{init}(F, f, \text{sec})$ where $\text{sk}_f = \{\alpha_i\}_{i=0}^k$, then obtains $(x_*, y_*, \pi_*) \leftarrow \mathcal{A}_2(\text{pub}_c, \text{sk}_f, \text{vk}, F, f, \text{st})$.

- $\mathcal{B}$ computes:

$$ \log_h(h^{s_1}) = \frac{\mathcal{D}_{\text{sk}_c}(\pi_*) - \sum_{i=0}^{i=k} \alpha_i \cdot x_i^*}{y_* - f(x_*)} . $$
Since we have proved that $y_* \neq f(x_*)$, the discrete logarithm $\log_h(h^{s_1})$ can be computed with the same probability as $\mathcal{A}$ wins the UNF experiment. Therefore, based on the DL assumption, there cannot exist an adversary $\mathcal{A}$ such that $\mathrm{Adv}_{\mathrm{VIP-POPE}, \mathcal{A}}(\eta)$ is non-negligible. □

## 5.2 Comparison with other PPE schemes

In Table 1, we provide comparison of our scheme with $\mathrm{PolyCommit}_{\mathrm{Ped}}$ [15], PIPE [4] and Xia et al.'s scheme [25]. We observe that the verification key size and verification cost are constant in $\mathrm{PolyCommit}_{\mathrm{Ped}}$ while in all other schemes it depends on the degree $k$. The verification equation in $\mathrm{PolyCommit}_{\mathrm{Ped}}$ involves several bilinear pairing which is costly compared to other operations. The verification key size and verification cost are not constant in our scheme but our scheme is pairing free and efficient as compared to other pairing free schemes. Moreover, our scheme VIP-POPE provides client's data privacy while other three schemes do not provide any privacy. To support our claim about efficiency, we implement all these schemes for different values of degrees with realistic parameters.

In our scheme, the verification of the result obtained from the server is done by a client. In such a case, the verification cost becomes important aspect of the scheme. We claim that our scheme is most efficient so far in terms of verification cost. We implement VIP-POPE, PIPE and Xia's scheme in SageMath [8, 1]. Table 1: Comparison of VIP-POPE with other PPE schemes. We denote by $D$ the constant cost of one Paillier decryption.

<table><thead><tr><th>Schemes</th><th>Setup size</th><th>Key size</th><th>Verif. cost</th><th>Pairing</th><th>Assumption</th><th>Model</th><th>Privacy</th></tr></thead><tbody><tr><td>PolyCommit<sub>Ped</sub> [15]</td><td>O(k)</td><td>O(1)</td><td>O(1)</td><td>Yes</td><td>t-SDH</td><td>Standard</td><td>No</td></tr><tr><td>PIPE [4]</td><td>O(1)</td><td>O(k)</td><td>O(k · log(q))</td><td>No</td><td>DDH</td><td>ROM</td><td>No</td></tr><tr><td>Xia et al.'s [25]</td><td>O(1)</td><td>O(k)</td><td>O(k · log(q))</td><td>No</td><td>DL</td><td>Standard</td><td>No</td></tr><tr><td>VIP-POPE</td><td>O(1)</td><td>O(k)</td><td>O(3 · log(q) + k) + D</td><td>No</td><td>DL/DCR</td><td>ROM</td><td>Yes</td></tr></tbody></table>

on 64-bit PC with Intel Core i5-6500 CPU @ 3.2 GHz and 4 GiB RAM. The new scheme, VIP-POPE, provides privacy of client's data while the other two schemes, PIPE and Xia's scheme, do not provide privacy of client's data. To keep the comparison as fair as possible, we implement all three schemes with the same realistic parameters. For our scheme, we choose a 1024 bit prime $q$ and 160 bit prime $q_1$ such that $q' = 2q_1q + 1$ is a prime. We choose another 1024 bit prime $p$ and set $n = pq'$. The coefficients of the polynomial $f(x)$, the secret values $(s_1, s_2)$ and $\{r_i\}_{i=0}^k$ are all selected uniformly at random from $\mathbb{Z}_q^*$. For Xia's scheme and PIPE, we keep the value of $q$, the polynomial $f(x)$ and $\{r_i\}_{i=0}^k$ same as in VIP-POPE. We compare the cost of only verification equation in all the three schemes.

<figure><img src="image_4.png" /><figcaption>Fig. 7: Verification cost comparison.</figcaption></figure>

For different values of the degree of the polynomial $f(x)$, we ran each scheme for 100 new instances and each instance for 10 times. We then averaged out the total time for the verification equation
in each scheme. In Fig. 7, we observe that VIP-POPE takes almost constant time while the cost of verification equation in PIPE and Xia's scheme increases linearly with respect to the degree $k$. Moreover, our scheme takes only around 5–6 milliseconds for verification equation even for $k = 100$ which makes it practically feasible for real applications.

## 6 Conclusion

In this paper, we gave a formal definition of new primitive called VPOPE (for Verifiable and Private Oblivious Polynomial Evaluation). This primitive allows a company to delegate the computation of a secret polynomial $f(\cdot)$ to an external server on client's encrypted data in a verifiable way. In other terms, a client sends an encrypted query to a server associated to her secret data $x$ using her own public key $pk$. Then, the client receives $d$ with a proof that $d = E_{pk}(f(x))$. We design the first VPOPE scheme called VIP-POPE (for Verifiable IND-CFA Paillier based Private Oblivious IND-CFA Polynomial Evaluation) and prove that it satisfies the required security properties, i.e., VIP-POPE is CPI-, IND-CFA-, QS-, UNF-secure in the random oracle model. Moreover, we compare our scheme to other existing PPE schemes of the literature and show that its computational verification cost is less as compared others.

## References

1. Personal info of 1.5m SingHealth patients, including PM Lee, stolen in Singapore's worst cyber attack. https://www.straitstimes.com/singapore/personal-info-of-15m-singhealth-patients-including-pm-lee-stolen-in-singapores-most, accessed: 2019-08-20

2. Amin, R., Islam, S.H., Biswas, G., Khan, M.K., Kumar, N.: A robust and anonymous patient monitoring system using wireless medical sensor networks. Future Generation Computer Systems 80, 483–495 (2018)

3. Baudron, O., Fouque, P., Pointcheval, D., Stern, J., Poupard, G.: Practical multicandidate election system. In: Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing, PODC 2001, Newport, Rhode Island, USA. pp. 274–283 (2001)

4. Bultel, X., Das, M.L., Gajera, H., Gérault, D., Giraud, M., Lafourcade, P.: Verifiable Private Polynomial Evaluation. In: Proceedings of Provable Security - 11th International Conference, ProvSec 2017, Xi'an, China. pp. 487–506 (2017)

5. Canetti, R., Riva, B., Rothblum, G.N.: Two Protocols for Delegation of Computation. In: Proceedings of Information Theoretic Security - 6th International Conference, ICITS, Montreal, QC, Canada. pp. 37–61 (2012)

6. Choi, S.G., Katz, J., Kumaresan, R., Cid, C.: Multi-Client Non-interactive Verifiable Computation. In: Proceedings of Theory of Cryptography - 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan. pp. 499–518 (2013)

7. De Muth, J.E.: Basic statistics and pharmaceutical statistical applications. Chapman and Hall/CRC (2014)
8. Fiat, A., Shamir, A.: How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In: Proceedings of Advances in Cryptology - CRYPTO '86, Santa Barbara, California, USA. pp. 186-194 (1986)

9. Fiore, D., Gennaro, R.: Publicly verifiable delegation of large polynomials and matrix computations, with applications. In: Proceedings of the ACM Conference on Computer and Communications Security, CCS'12, Raleigh, NC, USA. pp. 501-512 (2012)

10. Freedman, M.J., Ishai, Y., Pinkas, B., Reingold, O.: Keyword Search and Oblivious Pseudorandom Functions. In: Proceedings of Theory of Cryptography, Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA. pp. 303-324 (2005)

11. Freedman, M.J., Nissim, K., Pinkas, B.: Efficient Private Matching and Set Intersection. In: Proceedings of Advances in Cryptology - EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland. pp. 1-19 (2004)

12. Gajera, H., Naik, S., Das, M.L.: On the Security of "Verifiable Privacy-Preserving Monitoring for Cloud-Assisted mHealth Systems". In: Proceedings of Information Systems Security - 12th International Conference, ICISS, Jaipur, India. pp. 324-335 (2016)

13. Gennaro, R., Gentry, C., Parno, B.: Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers. In: Proceedings of Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA. pp. 465-482 (2010)

14. Guo, L., Fang, Y., Li, M., Li, P.: Verifiable privacy-preserving monitoring for cloud-assisted mHealth systems. In: Proceedings of IEEE Conference on Computer Communications, INFOCOM, Kowloon, Hong Kong. pp. 1026-1034 (2015)

15. Kate, A., Zaverucha, G.M., Goldberg, I.: Constant-Size Commitments to Polynomials and Their Applications. In: Proceedings of Advances in Cryptology - ASIACRYPT 2010 - 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore. pp. 177-194 (2010)

16. Lindell, Y., Pinkas, B.: Privacy Preserving Data Mining. Journal of Cryptology 15(3), 177-206 (2002)

17. Lloret, J., Garcia, M., Bri, D., Sendra, S.: A wireless sensor network deployment for rural and forest fire detection and verification. Sensors 9(11), 8722-8747 (2009)

18. Naor, M., Pinkas, B.: Oblivious Transfer and Polynomial Evaluation. In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, Atlanta, Georgia, USA. pp. 245-254 (1999)

19. Okayama, T.: Future gardening system—smart garden. Journal of Developments in Sustainable Agriculture 9(1), 47-50 (2014)

20. Paillier, P.: Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In: Proceedings of Advances in Cryptology - EUROCRYPT '99, International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic. pp. 223-238 (1999)

21. Papamanthou, C., Shi, E., Tamassia, R.: Signatures of Correct Computation. In: Proceedings of Theory of Cryptography - 10th Theory of Cryptography Conference, TCC, Tokyo, Japan. pp. 222-242 (2013)

22. Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: Nearly Practical Verifiable Computation. In: Proceedings of IEEE Symposium on Security and Privacy, SP 2013, Berkeley, CA, USA. pp. 238-252 (2013)
23. Parno, B., Raykova, M., Vaikuntanathan, V.: How to delegate and verify in public: Verifiable computation from attribute-based encryption. In: Proceedings of Theory of Cryptography - 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy. pp. 422–439 (2012)

24. Pedersen, T.P.: Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. In: Proceedings of Advances in Cryptology - CRYPTO '91, 11th Annual International Cryptology Conference, Santa Barbara, California, USA. pp. 129–140 (1991)

25. Xia, Z., Yang, B., Zhang, M., Mu, Y.: An Efficient and Provably Secure Private Polynomial Evaluation Scheme. In: Proceedings of 14th International Conference on Information Security Practice and Experience, ISPEC, Tokyo, Japan. pp. 595–609 (2018)