# Efficient Private Information Retrieval Protocol with Homomorphically Computing Univariate Polynomials

Authors: Wenju Xu; Baocang Wang; Rongxing Lu; Quanbo Qu; Yange Chen; Yupu Hu
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Private information retrieval (PIR) protocol is a powerful cryptographic tool and has received considerable attention in recent years as it can not only help users to retrieve the needed data from database servers but also protect them from being known by the servers. Although many PIR protocols have been proposed, it remains an open problem to design an efficient PIR protocol whose communication overhead is irrelevant to the database sizeN. In this paper, to answer this open problem, we present a new communication-efficient PIR protocol based on our proposed single-ciphertext fully homomorphic encryption (FHE) scheme, which supports unlimited computations with single variable over a single ciphertext even without access to the secret key. Specifically, our proposed PIR protocol is characterized by combining our single-ciphertext FHE with Lagrange interpolating polynomial technique to achieve better communication efficiency. Security analyses show that the proposed PIR protocol can efficiently protect the privacy of the user and the data in the database. In addition, both theoretical analyses and experimental evaluations are conducted, and the results indicate that our proposed PIR protocol is also more efficient and practical than previously reported ones. To the best of our knowledge, our proposed protocol is the first PIR protocol achieving O1 communication efficiency on the user side, irrelevant to the database size N.


---

## Body

## 1. Introduction

Private information retrieval (PIR) protocol [1] is a cryptographic primitive run between database servers and a user. The salient feature of PIR is that it ensures the user can obtain some data from the database servers, while the database servers cannot learn anything about the queries of the user. To obtain the feature, a trivial solution for the user is to download all the data from the database servers and obtain the data he wants to ask at any time. However, this solution wastes plenty of time and storage space for the user since the database servers usually store a huge volume of items. In addition, considering that there are continuous interactions with multiservers at the price of communication costs for the user, many research studies have been focused on the single-server PIR protocol that is composed of only one database server and one query user [1–7].In 1997, the first single-server PIR protocol was proposed by Kushilevitz and Ostrovsky [2]. They constructed a PIR protocol based on group homomorphism and the quadratic residuosity problem and achieved the communication complexity ONεlogN bits (the symbols O·,Ω·,ando· are commonly used asymptotic complexity notations. We denote an asymptotic upper bound, noncompact upper bound, and lower bound with O·,o·, and Ω·, respectively) on the user side for database size N and any constant ε. After that, some single-server PIR protocols were also proposed [3–5]. Kushilevitz and Ostrovsky [3] applied the trapdoor permutation approach to the single-server PIR protocol with communication overhead N−cN/k+Ok2 bits, where c is a constant and k is the security parameter of the one-way trapdoor permutation. Gentry and Ramzan [4] presented a single-server PIR protocol based on a slight variation of the computational difficulty of deciding whether a small prime divides Euler’s totient function of any composite integer. The total communication cost of the protocol is 3 messages, each of the size of Ωlog3−o1N bits. A PIR protocol was proposed based on group homomorphism by Melchor et al. [5] of communication ON bits.In recent years, with the development of fully homomorphic encryption (FHE) [8, 9], many researchers have turned into utilizing the FHE schemes to construct the single-server PIR protocols [6, 7, 10, 11]. Brakerski and Vaikuntanathan [10] proposed a brief PIR protocol based on learning with errors (LWE) by using FHE. The FHE DGHV [12] over the integers was applied to the PIR protocols by Yi et al. [6]. The communication overhead of the PIR protocol is OlogN bits and also relies on the size of ciphertext Oλ5 (the security parameter λ) in DGHV. Li et al. [7] modified Brakerski and Vaikuntanathan’s PIR protocol [10] and united the HAO scheme in [13] to construct a PIR protocol. However, the main idea of the protocol is similar to invoking the decryption circuit homomorphically, which is expensive and of extremely low efficiency. Aiming at single-server PIR protocols, we notice that all the aforementioned PIR protocols depend on the database size N in terms of communication cost. When the size N becomes larger, the communication will not be efficient. Therefore, how to efficiently design a PIR protocol with communication overhead O1, i.e., independent on the database size N, becomes an open problem.In this paper, to address the above open problem, we propose a new FHE scheme with special properties and utilize it to design a new single-server PIR protocol withO1 communication efficiency for any user. To the best of our knowledge, our single-server PIR protocol is the most efficient one in terms of the communication efficiency. In addition, our single-server PIR protocol also allows a user to retrieve positive integer data from the database server, instead of a single bit for every query. Specifically, the main contributions of this paper are threefold:(i)
First, in order to achieveO1 communication efficiency on the user side, we design a new kind of FHE scheme called single-ciphertext FHE, which supports unlimited computations with single variable over a single ciphertext without access to the secret key. Our proposed single-ciphertext FHE scheme is characterized with extremely efficient in terms of both encryption and decryption dependent on the truncated polynomial ring. Detailed security analysis illustrates that the proposed FHE scheme is one-way secure, which is exactly equivalent to the 3rd RSA problem.(ii)
Second, we take the single-ciphertext FHE as a symmetric encryption scheme and the Lagrange interpolating polynomial technique to construct our single-server PIR protocol. Security analyses show that our proposed PIR protocol can efficiently protect the privacy of the user and the data in the database in our defined security model.(iii)
Third, we conduct both theoretical analyses and experimental evaluations to demonstrate that our proposed PIR protocol is indeed efficient in terms of computational complexity and communication overhead. In particular, our proposed protocol is the first PIR protocol, which can achieveO1 communication efficiency, irrelevant to the database size N.The remainder of this paper is organized as follows. We describe some preliminaries in Section2. Then, in Section 3, we formalize our system model, security model, and design goal. In Section 4, we first present a new single-ciphertext FHE scheme, followed by our single-server communication-efficient PIR protocol. After that, the security analyses and the performance evaluation of our single-server PIR protocol are given in Sections 5 and 6, respectively. Some related works are also discussed in Section 7. Finally, we draw our conclusion in Section 8.


## 2. Preliminaries

In this section, we first give some notations that will be used throughout this paper and then describe the definitions of the truncated polynomial rings and our proposed single-ciphertext FHE scheme.


### 2.1. Notations

In this paper, we denote row vectors by bold letters (e.g.,DB and c), and the symbol DBi represents the i-th data in DB. Some other notations that will be used in this work are listed in Table 1.Table 1
Notations.
NotationExplanationaThe binary length of an integeragcda,bThe greatest common divisor of integersa,bφnThe Euler function of integernℤThe integer ringℤn0,1,…,n−1, the ring of integers modulo nℤnx,yThe bivariate polynomial ring onℤn


### 2.2. Truncated Polynomial Rings

The truncated polynomial rings will be used as a building block for constructing a special FHE scheme in this work. Essentially, the concept of truncated polynomials is not quite complicated, e.g., an extension field is constructed fromFx defined over a finite field F modulo a monic irreducible polynomial [14], and the NTRU public key cryptosystem [15] also utilizes a univariate truncated polynomial ring modulo XN−1. Though the above examples only involve univariate polynomials, we can extend the situations to the case of bivariate polynomials.To be specific, we can setn=pq to be a standard RSA modulus, namely, n is the product of two large primes p and q. In order to make our proposal more efficient, we consider the RSA cryptosystem [16] with the encryption public key e=3, from which we define two polynomials fx=x3−umodn and gy=y3−vmodn with u,v∈ℤn. We also define a bivariate polynomial set(1)S=hx,y=∑i=02∑j=02hijxiyj|hij∈ℤnand the additive and multiplicative operations on S. Given two bivariate polynomials h1x,y=∑i=02∑j=02hij1xiyj and h2x,y=∑i=02∑j=02hij2xiyj, the sum of h1x,y and h2x,y is defined as h+x,y=∑i=02∑j=02hij+xiyj, where hij+≡hij1+hij2modn. The multiplication can also be defined as h∗x,y≡h1x,yh2x,ymodn,fx,gy. To perform the multiplication, we first carry out the standard polynomial multiplication h1x,yh2x,y on ℤnx,y. Because the maximum degree with respect to x (y, respectively) is 2 in h1x,y (h2x,y, respectively), the maximum degree of x (y, respectively) in the multiplication h1x,yh2x,y becomes 4. Thus, in the second step, we perform modulo fx=x3−u and gy=y3−v on the multiplication h1x,yh2x,y to truncate it back to the set S as follows: replace x3 (y3, respectively) with u (v, respectively), and replace x4 (y4, respectively) with ux (vy, respectively). From the definition, one can easily verify that ℤnx,ymodfx,gy also forms a ring called truncated polynomial ring, and it is denoted as ℤnx,y/fx,gy.


### 2.3. Single-Ciphertext FHE Scheme

In the following, we will formalize the definition of single-ciphertext FHE, together with its security notion. Before that, we first give some necessary descriptions of the special FHE.The proposed single-ciphertext FHE is a special kind of FHE, which supports unlimited computations with single variable over a single ciphertext without access to the secret key. Different from the general FHE, the evaluation algorithm of our single-ciphertext FHE is subject to performing upon a single ciphertext rather than any multiciphertexts. In other words, our single-ciphertext FHE skips (or aborts) any circuits with multivariables for the general FHE and allows any computations over any circuits with single variable. Compared with the general FHE, our single-ciphertext FHE possesses less functionality due to the single ciphertext, but it still permits any computations on any circuits with single variable. Hence, our single-ciphertext FHE, as a well-suitable cryptographic tool, is enough for the requirements of single-server PIR protocols since the evaluation of the single-server PIR protocols can be regarded as univariate polynomials.Definition 1.
(single-ciphertext FHE scheme). A single-ciphertext FHE scheme consists of four probabilistic polynomial time (PPT) algorithms, namely, key generation, encryption, decryption, and homomorphic evaluation algorithm. The details are as follows:(i)
Key generation (pk,evk,sk← KeyGen(λ)): take the security parameter λ as the input, and output a public key pk, an evaluation key evk, and a secret key sk(ii)
Encryption (c← Enc(m,pk)): using the public key pk, encrypt a message m∈M into a ciphertext c, where M is the message space(iii)
Decryption (m← Dec(c,sk)): using the secret key sk, decrypt a ciphertext c to recover the corresponding message m∈M(iv)
Evaluation (c^← Eval(C,c,evk)): given a circuit with single variable C and a ciphertext c with the underlying plaintext m, i.e., c=Encm,pk, the algorithm utilizes the evaluation key evk to compute a new ciphertext c^=EvalC,c,evk
Note that the correctness of decryption requires that the plaintextm can be correctly decrypted from the ciphertext, i.e., m=DecEncm,pk,sk. The correctness of the homomorphic evaluation requires that the ciphertext c^ can be correctly decrypted into the plaintext Cm, namely, Decc^,sk=Cm.
Actually, our proposal single-ciphertext FHE scheme performs no noises. Every time an evaluation on the ciphertext is performed, there is no noise to obscure the underlying plaintext. In terms of the noiseless FHE schemes, there is a main drawback: none can be strictly proved secure and feasible in the framework of provable security. For more introduction of noiseless FHE, one can refer toSection 7. Hence, we give the following security definition for our noiseless single-ciphertext FHE scheme.Definition 2.
(the one-way security of single-ciphertext FHE). Given the security parameterλ, the public key pk, the evaluation key evk, and a ciphertext c with the underlying plaintext m, it should be difficult for any PPT adversary to find m∈M from the ciphertext c such that c=Encm,pk. Formally, we require that for any PPT adversary A, we have(2)Prm∈M|pk,evk←KeyGenλ,c=Encm,pk≤ελ,where ελ represents a negligible function.
Different from general security notions such as indistinguishability under chosen-plaintext attack (IND-CPA) and indistinguishability under chosen-ciphertext attack (IND-CCA1) of known FHE schemes [8–10, 12, 17–22] (FHE essentially supports malleability on ciphertexts and hence cannot obtain the highest security goal, namely, indistinguishability under adaptive chosen-ciphertext attack (IND-CCA2)), we only consider the one-way security due to the following observations. Firstly, the security notion is tailored for the single-ciphertext FHE scenarios, where no distinguishability games are permitted on distinct plaintexts. Secondly, in the PIR scenario, the single-ciphertext FHE scheme is used as a symmetric encryption algorithm without considering the IND-CPA security in the public key encryption schemes.


## 2.1. Notations

In this paper, we denote row vectors by bold letters (e.g.,DB and c), and the symbol DBi represents the i-th data in DB. Some other notations that will be used in this work are listed in Table 1.Table 1
Notations.
NotationExplanationaThe binary length of an integeragcda,bThe greatest common divisor of integersa,bφnThe Euler function of integernℤThe integer ringℤn0,1,…,n−1, the ring of integers modulo nℤnx,yThe bivariate polynomial ring onℤn


## 2.2. Truncated Polynomial Rings

The truncated polynomial rings will be used as a building block for constructing a special FHE scheme in this work. Essentially, the concept of truncated polynomials is not quite complicated, e.g., an extension field is constructed fromFx defined over a finite field F modulo a monic irreducible polynomial [14], and the NTRU public key cryptosystem [15] also utilizes a univariate truncated polynomial ring modulo XN−1. Though the above examples only involve univariate polynomials, we can extend the situations to the case of bivariate polynomials.To be specific, we can setn=pq to be a standard RSA modulus, namely, n is the product of two large primes p and q. In order to make our proposal more efficient, we consider the RSA cryptosystem [16] with the encryption public key e=3, from which we define two polynomials fx=x3−umodn and gy=y3−vmodn with u,v∈ℤn. We also define a bivariate polynomial set(1)S=hx,y=∑i=02∑j=02hijxiyj|hij∈ℤnand the additive and multiplicative operations on S. Given two bivariate polynomials h1x,y=∑i=02∑j=02hij1xiyj and h2x,y=∑i=02∑j=02hij2xiyj, the sum of h1x,y and h2x,y is defined as h+x,y=∑i=02∑j=02hij+xiyj, where hij+≡hij1+hij2modn. The multiplication can also be defined as h∗x,y≡h1x,yh2x,ymodn,fx,gy. To perform the multiplication, we first carry out the standard polynomial multiplication h1x,yh2x,y on ℤnx,y. Because the maximum degree with respect to x (y, respectively) is 2 in h1x,y (h2x,y, respectively), the maximum degree of x (y, respectively) in the multiplication h1x,yh2x,y becomes 4. Thus, in the second step, we perform modulo fx=x3−u and gy=y3−v on the multiplication h1x,yh2x,y to truncate it back to the set S as follows: replace x3 (y3, respectively) with u (v, respectively), and replace x4 (y4, respectively) with ux (vy, respectively). From the definition, one can easily verify that ℤnx,ymodfx,gy also forms a ring called truncated polynomial ring, and it is denoted as ℤnx,y/fx,gy.


## 2.3. Single-Ciphertext FHE Scheme

In the following, we will formalize the definition of single-ciphertext FHE, together with its security notion. Before that, we first give some necessary descriptions of the special FHE.The proposed single-ciphertext FHE is a special kind of FHE, which supports unlimited computations with single variable over a single ciphertext without access to the secret key. Different from the general FHE, the evaluation algorithm of our single-ciphertext FHE is subject to performing upon a single ciphertext rather than any multiciphertexts. In other words, our single-ciphertext FHE skips (or aborts) any circuits with multivariables for the general FHE and allows any computations over any circuits with single variable. Compared with the general FHE, our single-ciphertext FHE possesses less functionality due to the single ciphertext, but it still permits any computations on any circuits with single variable. Hence, our single-ciphertext FHE, as a well-suitable cryptographic tool, is enough for the requirements of single-server PIR protocols since the evaluation of the single-server PIR protocols can be regarded as univariate polynomials.Definition 1.
(single-ciphertext FHE scheme). A single-ciphertext FHE scheme consists of four probabilistic polynomial time (PPT) algorithms, namely, key generation, encryption, decryption, and homomorphic evaluation algorithm. The details are as follows:(i)
Key generation (pk,evk,sk← KeyGen(λ)): take the security parameter λ as the input, and output a public key pk, an evaluation key evk, and a secret key sk(ii)
Encryption (c← Enc(m,pk)): using the public key pk, encrypt a message m∈M into a ciphertext c, where M is the message space(iii)
Decryption (m← Dec(c,sk)): using the secret key sk, decrypt a ciphertext c to recover the corresponding message m∈M(iv)
Evaluation (c^← Eval(C,c,evk)): given a circuit with single variable C and a ciphertext c with the underlying plaintext m, i.e., c=Encm,pk, the algorithm utilizes the evaluation key evk to compute a new ciphertext c^=EvalC,c,evk
Note that the correctness of decryption requires that the plaintextm can be correctly decrypted from the ciphertext, i.e., m=DecEncm,pk,sk. The correctness of the homomorphic evaluation requires that the ciphertext c^ can be correctly decrypted into the plaintext Cm, namely, Decc^,sk=Cm.
Actually, our proposal single-ciphertext FHE scheme performs no noises. Every time an evaluation on the ciphertext is performed, there is no noise to obscure the underlying plaintext. In terms of the noiseless FHE schemes, there is a main drawback: none can be strictly proved secure and feasible in the framework of provable security. For more introduction of noiseless FHE, one can refer toSection 7. Hence, we give the following security definition for our noiseless single-ciphertext FHE scheme.Definition 2.
(the one-way security of single-ciphertext FHE). Given the security parameterλ, the public key pk, the evaluation key evk, and a ciphertext c with the underlying plaintext m, it should be difficult for any PPT adversary to find m∈M from the ciphertext c such that c=Encm,pk. Formally, we require that for any PPT adversary A, we have(2)Prm∈M|pk,evk←KeyGenλ,c=Encm,pk≤ελ,where ελ represents a negligible function.
Different from general security notions such as indistinguishability under chosen-plaintext attack (IND-CPA) and indistinguishability under chosen-ciphertext attack (IND-CCA1) of known FHE schemes [8–10, 12, 17–22] (FHE essentially supports malleability on ciphertexts and hence cannot obtain the highest security goal, namely, indistinguishability under adaptive chosen-ciphertext attack (IND-CCA2)), we only consider the one-way security due to the following observations. Firstly, the security notion is tailored for the single-ciphertext FHE scenarios, where no distinguishability games are permitted on distinct plaintexts. Secondly, in the PIR scenario, the single-ciphertext FHE scheme is used as a symmetric encryption algorithm without considering the IND-CPA security in the public key encryption schemes.


## 3. System Model, Security Model, and Design Goal

In this section, we formalize our system model and security model and identify our design goal.


### 3.1. System Model

In our system model, we consider a typical single-server PIR protocol, which includes two entities, namely, a user and a database (DB) server, as shown in Figure1.(i)
DB server: the database server is powerful in both storing and computing data. In our system model, the database server stores and processes a databaseDB=i,DBi|0≤i≤N−1 with totally N items. For simplicity of our PIR protocol discussed later, we assume the value of each item DBi is a positive integer, not just one bit. In addition, the server will offer a PIR response to a query user after the latter makes a PIR query with unbounded computations.(ii)
User: in our system model, we consider a query user can directly make a PIR query to the DB server and obtain the desirable result from the DB server. Meanwhile, the user does not want to reveal the queried valuei to the DB server when asking the corresponding data DBi from DB and hopes the communication of PIR should be efficient.Figure 1
System model under consideration.Formally, a single-server PIR protocol in our system model comprises three phases as follows:(i)
Query generation phase (Qi← QG(i)): taking the index i as the input, the user sends a query Qi to the server(ii)
Response generation phase (Ri← RG(Qi,DB)): using the query Qi and the database DB, the server returns a response Ri to the user(iii)
Response retrieval phase (DBi← RR(Ri)): upon receiving a response Ri, the user outputs the data DBi corresponding to the index iA single-server PIR protocol is correct if for any databaseDB with any size N and any index i for 0≤i≤N−1, DBi=RRDB,i,Qi,Ri holds, where Qi=QGi and Ri=RGQi,DB.


### 3.2. Security Model

In our security model, we consider the DB server is honest but curious, and there is no collusion between the DB server and any other third parties. In other words, the DB server will faithfully follow the protocol; however, he is curious about the queried value of the user. Note that, in case the DB server is compromised by some attackers, the compromised DB server may launch other active attacks and return a response with errors to the user who is not able to verify. However, since we focus on the communication-efficient PIR protocol for the user in this paper, those active attacks from the compromised DB server are beyond the major work of this paper, though it is not difficult to apply some verifiable techniques to tackle these attacks. For details, one can refer to Remark3 in Section 5.


### 3.3. Design Goal

Our design goal is to present a communication-efficient PIR protocol on the user side to address the requirements mentioned in the above system model and security model. The communication-efficient PIR protocol is the center of our attention; hence, we assume the power of the server is unlimited, and the computation burden of the server is less important than the one of any user. Specifically, the following two objectives should be included:(i)
The proposed PIR protocol should be privacy preserving: the queried indexi should be private, and no one, except the query user, can determine the value of i. In addition, no one, except the query user, can retrieve the data DBi after receiving the response Ri returned by the DB server.(ii)
The proposed PIR protocol should be communication efficient: in order to achieve the above privacy requirement, additional communication costs will be incurred in the PIR protocols. Therefore, in the proposed PIR protocol, we aim to make the query’s communication efficient, i.e., achieving less communication costs for the user.


## 3.1. System Model

In our system model, we consider a typical single-server PIR protocol, which includes two entities, namely, a user and a database (DB) server, as shown in Figure1.(i)
DB server: the database server is powerful in both storing and computing data. In our system model, the database server stores and processes a databaseDB=i,DBi|0≤i≤N−1 with totally N items. For simplicity of our PIR protocol discussed later, we assume the value of each item DBi is a positive integer, not just one bit. In addition, the server will offer a PIR response to a query user after the latter makes a PIR query with unbounded computations.(ii)
User: in our system model, we consider a query user can directly make a PIR query to the DB server and obtain the desirable result from the DB server. Meanwhile, the user does not want to reveal the queried valuei to the DB server when asking the corresponding data DBi from DB and hopes the communication of PIR should be efficient.Figure 1
System model under consideration.Formally, a single-server PIR protocol in our system model comprises three phases as follows:(i)
Query generation phase (Qi← QG(i)): taking the index i as the input, the user sends a query Qi to the server(ii)
Response generation phase (Ri← RG(Qi,DB)): using the query Qi and the database DB, the server returns a response Ri to the user(iii)
Response retrieval phase (DBi← RR(Ri)): upon receiving a response Ri, the user outputs the data DBi corresponding to the index iA single-server PIR protocol is correct if for any databaseDB with any size N and any index i for 0≤i≤N−1, DBi=RRDB,i,Qi,Ri holds, where Qi=QGi and Ri=RGQi,DB.


## 3.2. Security Model

In our security model, we consider the DB server is honest but curious, and there is no collusion between the DB server and any other third parties. In other words, the DB server will faithfully follow the protocol; however, he is curious about the queried value of the user. Note that, in case the DB server is compromised by some attackers, the compromised DB server may launch other active attacks and return a response with errors to the user who is not able to verify. However, since we focus on the communication-efficient PIR protocol for the user in this paper, those active attacks from the compromised DB server are beyond the major work of this paper, though it is not difficult to apply some verifiable techniques to tackle these attacks. For details, one can refer to Remark3 in Section 5.


## 3.3. Design Goal

Our design goal is to present a communication-efficient PIR protocol on the user side to address the requirements mentioned in the above system model and security model. The communication-efficient PIR protocol is the center of our attention; hence, we assume the power of the server is unlimited, and the computation burden of the server is less important than the one of any user. Specifically, the following two objectives should be included:(i)
The proposed PIR protocol should be privacy preserving: the queried indexi should be private, and no one, except the query user, can determine the value of i. In addition, no one, except the query user, can retrieve the data DBi after receiving the response Ri returned by the DB server.(ii)
The proposed PIR protocol should be communication efficient: in order to achieve the above privacy requirement, additional communication costs will be incurred in the PIR protocols. Therefore, in the proposed PIR protocol, we aim to make the query’s communication efficient, i.e., achieving less communication costs for the user.


## 4. Our Proposed Scheme

In this section, we will describe our communication-efficient PIR protocol. Before delving into the details, we first present our new single-ciphertext FHE scheme based on the aforementioned truncated polynomial rings.


### 4.1. Our New Single-Ciphertext FHE Scheme

Our new single-ciphertext FHE scheme comprises four algorithms, namely, KeyGen, Enc, Dec, and Eval algorithms. The detailed descriptions are as follows:(i)
KeyGen(λ): taking the security parameter λ (even for simplicity) as the input, randomly generate two λ/2-bit large primes p and q satisfying gcd p−1,3=1 and gcd q−1,3=1, and compute n=pq,φn=p−1q−1 and the inverse d of 3 modulo φn, namely, 3d≡1modφn. The modulus n is set as the public key pk=n, the evaluation key is set as evk=n, and the integer d is set as the secret key, i.e., sk=d.(ii)
Enc(m,pk): given a plaintext m∈M=ℤn, randomly choose a,b∈ℤn and compute u≡a3modn and v≡b3modn. Also, randomly choose 9 integers aij∈ℤn for i,j∈0,1,2, and construct a polynomial fx,y=∑i=02∑j=02aijxiyj. Set a polynomial Fx,y≡fx,y−fa,bmodn, and compute cx,y≡Fx,y+mmodn. The ciphertext is c=Encm,n=u,v,cx,y.(iii)
Dec(c,sk): upon the receipt of a ciphertext c=u,v,cx,y, compute a≡udmodn and b≡vdmodn with the secret key d to obtain the two random numbers a,b. The plaintext can be recovered by substituting a,b into cx,y, that is, ca,b≡Fa,b+m≡mmodn due to Fa,b≡fa,b−fa,b≡0modn.(iv)
Eval(f^,c,evk)): given the ciphertext c=Encm,n=u,v,cx,y and a univariate polynomial f^x=∑i=0αβixi∈ℤnx, the evaluation algorithm is described in Algorithm 1. We remind that the involved addition and multiplication operations are performed over the truncated polynomial ring ℤnx,y/x3−u,y3−v. Especially, for each iteration, cf^x,y will be truncated back to the truncated polynomial ring via the reduction operation modulo x3−u and y3−v. Hence, the final result of cf^x,y remains in the truncated polynomial ring ℤnx,y/x3−u,y3−v, i.e., it remains a bivariate polynomial in S.Algorithm 1:Univariate polynomial evaluation algorithm.
Input:f^=∑i=0αβiximodn, c=u,v,cx,y, evk=n.(1)
Setcf^x,y=0.(2)
For eachi=0,…,α, computecf^x,y=cf^x,ycx,y+βα−imodn,x3−u,y3−v.Output:cf^=u,v,cf^x,y.Remark 1.
Note that, in order to ensure the one-way security of our single-ciphertext FHE scheme, the length of the modulusn should be larger than 2048 bits, i.e., λ≥2048.
Correctness: in order to demonstrate the correctness of the homomorphic evaluation algorithm, we need to show thatDeccf^x,y,d=f^m. From Algorithm 1, one can easily verify that(3)cf^x,y≡f^cx,y≡∑i=0αβicx,yimodn,x3−u,y3−v.
Then, there must exist two bivariate polynomialsAx,y,Bx,y∈ℤnx,y such that(4)cf^x,y≡f^cx,y+Ax,yx3−u+Bx,yy3−vmodn.
Sincea3≡umodn and b3≡vmodn, we have(5)Deccf^x,y,d=cf^a,b≡f^ca,b+Aa,ba3−u+Ba,bb3−vmodn.
Recall thatca,b≡mmodn, a3−u≡0modn, and b3−v≡0modn, and we immediately have Deccf^x,y,d=cf^a,b≡f^mmodn as desired.
Security: in the following, we prove our proposed single-ciphertext FHE scheme is one-way secure based on the hardness of the 3rd RSA problem.Definition 3.
(the 3rd RSA problem). Thee-th RSA problem is defined as follows: given the RSA public key n=pq and e, and a ciphertext π, to find the plaintext μ such that π≡μemodn. The 3rd RSA problem is the special case with e=3.Theorem 1.
The one-way security of our proposed single-ciphertext FHE scheme is polynomially equivalent to the 3rd RSA problem.Proof.
Both directions (⇔) need to be proven. The direction from the right to the left (⇐) is trivial. If an adversary can break the 3rd RSA problem, then given a ciphertext c=u,v,cx,y of the single-ciphertext FHE scheme, the adversary can solve two 3rd RSA problems a3≡umodn and b3≡vmodn to derive two integers a,b∈ℤn and finally breaks the one-way security by computing m≡ca,bmodn.
In order to prove the direction from the left to the right (⇒), we assume there is a PPT adversary A which can break the one-way security of our scheme, i.e., m←Ac,n. Then, we can construct another algorithm ℬ which can utilize A to break the 3rd RSA problem, i.e., μ←ℬπ,n, as shown in Algorithm 2.
To prove the correctness of the reduction in Algorithm2, we first note that u≡π≡μ3modn and that m is the plaintext corresponding to c=u,v,cx,y, so there must exist a bivariate polynomial Fx,y∈ℤnx,y/x3−u,y3−v such that cx,y≡Fx,y+mmodn and Fμ,b≡0modn. So, x≡μmodn is a common root for both congruences x3−u≡x3−π≡0modn and cx,b−m≡0modn. Thus, we can efficiently perform the Euclidean algorithm [23] to compute the greatest common divisor x−μ≡gcdx3−umodn,cx,b−mmodn. So, the plaintext μ of the RSA problem is recovered, i.e., we can construct an algorithm ℬ for solving the 3rd RSA problem.
Note that Theorem1 establishes an exact equivalence between the one-wayness of the proposed single-ciphertext FHE scheme and the 3rd RSA problem. One may doubt that choosing the RSA encryption key as 3 will produce serious threats on the security of the single-ciphertext FHE scheme. In fact, in many implementations, choosing a relatively small encryption key such as e=3 or 217+1 is widely suggested to reduce the encryption costs.
Computational complexity: next, we analyze the computational costs of our single-ciphertext FHE scheme.
During the Enc phase, there are 2 modular multiplications to computeu (v, respectively). Computing the polynomial Fx,y needs 18 modular multiplications and some modular additions since there are i+j modular multiplications to compute the monomial aijxiyj for i,j=0,1,2 in Fx,y. Compared with the calculation of the modular multiplication, the time cost of modular addition can be negligible. Hence, there are totally 22 modular multiplications and some negligible modular additions in the Enc phase. Considering the computational complexity of a multiplication modulo n=pq is Oλ2, we conclude that the computational complexity of the Enc phase is Oλ2.
During the Dec phase, the main operations are to outputa,b from u,v by 2 modular exponentiation operations of exponentiation d. Considering that the computational complexity of a modular exponentiation is Oλ3, the total computational complexity of the Dec phase is Oλ3 when ignoring some modular additions.
During the Eval phase, the outputcf^x,y is actually a truncated bivariable polynomial. There are α-iterations, and every iteration performs a modular multiplication besides a negligible modular addition. Hence, there are totally α-modular multiplications and some negligible modular additions. As a result, the computational complexity of the Eval phase is Oαλ2 subject to the value of α in ciphertext evaluations.
In summary, the computational complexity isOλ2 for encryption, Oλ3 for decryption, and Oαλ2 for evaluation, respectively, where λ≥2048 is the length of the RSA modulus n.
Comparisons of several noiseless FHE: comparisons of several noiseless FHE schemes among [24–26] with ours are shown in Table 2. Nuida utilized the commutator and an encoding scheme by a homomorphic mapping φ from noncommutative group G to noncommutative group G^ to construct the noiseless FHE. The ciphertext is composed of two elements from G and Ker φ which is a subset of G. However, the security is based on the open sampling of group G, and the assumption that judging whether an element is in the kernel Ker φ is difficult. Yagisawa [25] is an improved version of [26] with smaller ciphertext size; hence, we only discuss about [25]. The octonion ring over the finite field was used by Yagisawa to achieve 1:8 length ratio of the plaintext and ciphertext. Yagisawa’s noiseless FHE is immune from the Grobner basis attacks, which is weaker than our one-way security. With respect to ciphertext space and length ratio, our noiseless FHE is more efficient than [25] while less than [24]. Totally speaking, our single-ciphertext FHE scheme is more superior to [24–26], especially considering that the security is more important than other factors for noiseless FHE.Algorithm 2: Algorithm ℬ with access to A.
Input: the public modulus n, and the RSA ciphertext π∈ℤn.(1)
Randomly choose an integerb∈ℤn and compute v≡b3modn.(2)
Setu=π and randomly generate a bivariate polynomial cx,y∈ℤnx,y/x3−u,y3−v.(3)
Setc=u,v,cx,y and run m←Ac,n.(4)
Compute the greatest common divisorx+θ≡gcdx3−umodn,cx,b−mmodn.Output:μ≡−θmodn.Table 2
Comparisons of several noiseless FHE schemes.
SchemesAlgebraic structureCiphertext spaceLengthratioaSecurityNuida [24]Noncommutative groupVector of dimension 21:2GbJudgement of the kernel elementYagisawa [25]Octonion ringOctonion ring1:8Immune from the Grobner basis attacksOursTruncated polynomial ringVector of dimension 31:11One-way securityLengthratioa: the length ratio between the plaintext and ciphertext. Gb: the number of elements in group G.


### 4.2. Description of Our Communication-Efficient PIR Protocol

Before delving our communication-efficient PIR protocol, we first give a brief overview of how our single-ciphertext FHE scheme is utilized to construct the single-server PIR protocol.(i)
The single-server PIR protocol aims to help the user to obtain theith data from the server possessing the whole database, without leaking the index i to the server. Obviously, the server performs an evaluation algorithm on a single ciphertext corresponding to the queried index. So, our single-ciphertext FHE scheme is well suitable for the single-server PIR protocol.(ii)
In our protocol, the user can encrypt the indexi with our single-ciphertext FHE scheme and then send the ciphertext to the server. For the consideration of efficiency, we directly encrypt the index with a symmetric encryption scheme. The parameters a,b connect the partial ciphertext cx,y and its corresponding plaintext. In particular, the parameters a,b invoke a polynomial, and the polynomial is used to encrypt the queried index; meanwhile, the polynomial ciphertext cx,y can be directly decrypted with the parameters a,b ignoring the parameters u,v as the auxiliary information. In turn, the server outputs a function about the ith data ai relative to the polynomial ciphertext. Then, the user decrypts the function using the parameters a,b, and he will exactly obtain the ith data ai corresponding to the index i. During the process, the server provides some computation and storage space and is unable to acquire the information of the index i. Consequently, our single-server PIR protocol achieves the goal as desired.(iii)
Moreover, we prefer the communication complexity on the user side rather than on the server side. Hence, inSection 6, the communication complexity on the user side is much more important than the overheads on the server side. In the future, we will delve the communication-efficient single-server PIR protocol which can attain the tradeoff overheads of the communication and the computation between the user and the server.In the following, we employ the single-ciphertext FHE scheme proposed inSection 4.1 and the Lagrange interpolating polynomial to construct our communication-efficient single-server PIR protocol. The detailed three algorithms are described as follows:(i)
Query generation phase: taking the indexi0≤i≤N−1 as the input, the user sends a query Qi to the DB server. The details are described in Algorithm 3.(ii)
Response generation phase: upon receiving the queryQi, the DB server outputs Ri=gx,y to the user in Algorithm 4. Note that even if u,v are obtained in the query Qi=n,u,v,cx,y, the DB server cannot recover the index i due to not knowing the symmetric key a,b.(iii)
Response retrieval phase: refer to Algorithm5. Upon receiving the response Ri=gx,y, the user retrieves the data DBi≡ga,bmodn corresponding to the index i by using the symmetric key a,b.Algorithm 3: The query generation algorithm (user).
Input: the index i0≤i≤N−1.(1)
Randomly generateλ/2-bit-long primes p,q subject to gcd p−1,3=1 and gcd q−1,3=1 and compute n=pq.(2)
Randomly chooseaij∈ℤn for i,j=0,1,2 and set fx,y=∑i=02∑j=02aijxiyj.(3)
Randomly choosea,b∈ℤn and compute u≡a3modn,v≡b3modn.(4)
SetFx,y≡fx,y−fa,bmodn.(5)
Computecx,y≡Fx,y+imodn.//The symmetric keya,bis kept by the user and private for the DB server.Output:Qi=n,u,v,cx,y.Correctness: now, we illustrate the correctness of our proposed single-server PIR protocol, namely,DBi=RRDB,i,Qi,Ri, for any database DB=a0,a1,…,aN−1 with any size N and any index 0≤i≤N−1.During the response generation phase, the responseRi=gx,y is an evaluation of encryption of index i. Meanwhile, the response Ri=gx,y is N numbers of addition operations about the whole data al for 0≤l≤N−1. When decrypting the response Ri correctly, the user will obtain that(6)ga,b≡∑l=0N−1al∏0≤j≤N−1,j≠lca,b−jl−jmodn≡∑l=0N−1al∏0≤j≤N−1,j≠li−jl−jmodn∵ca,b≡imodn≡a0·i−10−1·i−20−2⋯i−N−10−N−1+a1·i−01−0·i−21−2⋯i−N−11−N−1+⋯⋯+aN−1·i−0N−1−0·i−1N−1−1⋯i−N−2N−1−N−2modn.When we assumei=1 for an example, it is obvious that the above items (6) in ga,b all equal 0 since there is an item i−1 in the molecule, while item (6) in ga,b equals a1 since the molecule is equal to the denominator. Therefore, we can conclude that once decrypting the response Ri correctly, the user will obtain that ga,b≡aimodn since ca,b≡imodn. As a result, the correctness of our proposed single-server PIR protocol holds, as desired.Remark 2.
Note that the length of each itemDBi, for any 0≤i≤N−1, in DB should be smaller than λ. Otherwise, what the user would obtain from the above response retrieval algorithm is not the value of DBi as DBi had been damaged by the operation of modulo n.


## 4.1. Our New Single-Ciphertext FHE Scheme

Our new single-ciphertext FHE scheme comprises four algorithms, namely, KeyGen, Enc, Dec, and Eval algorithms. The detailed descriptions are as follows:(i)
KeyGen(λ): taking the security parameter λ (even for simplicity) as the input, randomly generate two λ/2-bit large primes p and q satisfying gcd p−1,3=1 and gcd q−1,3=1, and compute n=pq,φn=p−1q−1 and the inverse d of 3 modulo φn, namely, 3d≡1modφn. The modulus n is set as the public key pk=n, the evaluation key is set as evk=n, and the integer d is set as the secret key, i.e., sk=d.(ii)
Enc(m,pk): given a plaintext m∈M=ℤn, randomly choose a,b∈ℤn and compute u≡a3modn and v≡b3modn. Also, randomly choose 9 integers aij∈ℤn for i,j∈0,1,2, and construct a polynomial fx,y=∑i=02∑j=02aijxiyj. Set a polynomial Fx,y≡fx,y−fa,bmodn, and compute cx,y≡Fx,y+mmodn. The ciphertext is c=Encm,n=u,v,cx,y.(iii)
Dec(c,sk): upon the receipt of a ciphertext c=u,v,cx,y, compute a≡udmodn and b≡vdmodn with the secret key d to obtain the two random numbers a,b. The plaintext can be recovered by substituting a,b into cx,y, that is, ca,b≡Fa,b+m≡mmodn due to Fa,b≡fa,b−fa,b≡0modn.(iv)
Eval(f^,c,evk)): given the ciphertext c=Encm,n=u,v,cx,y and a univariate polynomial f^x=∑i=0αβixi∈ℤnx, the evaluation algorithm is described in Algorithm 1. We remind that the involved addition and multiplication operations are performed over the truncated polynomial ring ℤnx,y/x3−u,y3−v. Especially, for each iteration, cf^x,y will be truncated back to the truncated polynomial ring via the reduction operation modulo x3−u and y3−v. Hence, the final result of cf^x,y remains in the truncated polynomial ring ℤnx,y/x3−u,y3−v, i.e., it remains a bivariate polynomial in S.Algorithm 1:Univariate polynomial evaluation algorithm.
Input:f^=∑i=0αβiximodn, c=u,v,cx,y, evk=n.(1)
Setcf^x,y=0.(2)
For eachi=0,…,α, computecf^x,y=cf^x,ycx,y+βα−imodn,x3−u,y3−v.Output:cf^=u,v,cf^x,y.Remark 1.
Note that, in order to ensure the one-way security of our single-ciphertext FHE scheme, the length of the modulusn should be larger than 2048 bits, i.e., λ≥2048.
Correctness: in order to demonstrate the correctness of the homomorphic evaluation algorithm, we need to show thatDeccf^x,y,d=f^m. From Algorithm 1, one can easily verify that(3)cf^x,y≡f^cx,y≡∑i=0αβicx,yimodn,x3−u,y3−v.
Then, there must exist two bivariate polynomialsAx,y,Bx,y∈ℤnx,y such that(4)cf^x,y≡f^cx,y+Ax,yx3−u+Bx,yy3−vmodn.
Sincea3≡umodn and b3≡vmodn, we have(5)Deccf^x,y,d=cf^a,b≡f^ca,b+Aa,ba3−u+Ba,bb3−vmodn.
Recall thatca,b≡mmodn, a3−u≡0modn, and b3−v≡0modn, and we immediately have Deccf^x,y,d=cf^a,b≡f^mmodn as desired.
Security: in the following, we prove our proposed single-ciphertext FHE scheme is one-way secure based on the hardness of the 3rd RSA problem.Definition 3.
(the 3rd RSA problem). Thee-th RSA problem is defined as follows: given the RSA public key n=pq and e, and a ciphertext π, to find the plaintext μ such that π≡μemodn. The 3rd RSA problem is the special case with e=3.Theorem 1.
The one-way security of our proposed single-ciphertext FHE scheme is polynomially equivalent to the 3rd RSA problem.Proof.
Both directions (⇔) need to be proven. The direction from the right to the left (⇐) is trivial. If an adversary can break the 3rd RSA problem, then given a ciphertext c=u,v,cx,y of the single-ciphertext FHE scheme, the adversary can solve two 3rd RSA problems a3≡umodn and b3≡vmodn to derive two integers a,b∈ℤn and finally breaks the one-way security by computing m≡ca,bmodn.
In order to prove the direction from the left to the right (⇒), we assume there is a PPT adversary A which can break the one-way security of our scheme, i.e., m←Ac,n. Then, we can construct another algorithm ℬ which can utilize A to break the 3rd RSA problem, i.e., μ←ℬπ,n, as shown in Algorithm 2.
To prove the correctness of the reduction in Algorithm2, we first note that u≡π≡μ3modn and that m is the plaintext corresponding to c=u,v,cx,y, so there must exist a bivariate polynomial Fx,y∈ℤnx,y/x3−u,y3−v such that cx,y≡Fx,y+mmodn and Fμ,b≡0modn. So, x≡μmodn is a common root for both congruences x3−u≡x3−π≡0modn and cx,b−m≡0modn. Thus, we can efficiently perform the Euclidean algorithm [23] to compute the greatest common divisor x−μ≡gcdx3−umodn,cx,b−mmodn. So, the plaintext μ of the RSA problem is recovered, i.e., we can construct an algorithm ℬ for solving the 3rd RSA problem.
Note that Theorem1 establishes an exact equivalence between the one-wayness of the proposed single-ciphertext FHE scheme and the 3rd RSA problem. One may doubt that choosing the RSA encryption key as 3 will produce serious threats on the security of the single-ciphertext FHE scheme. In fact, in many implementations, choosing a relatively small encryption key such as e=3 or 217+1 is widely suggested to reduce the encryption costs.
Computational complexity: next, we analyze the computational costs of our single-ciphertext FHE scheme.
During the Enc phase, there are 2 modular multiplications to computeu (v, respectively). Computing the polynomial Fx,y needs 18 modular multiplications and some modular additions since there are i+j modular multiplications to compute the monomial aijxiyj for i,j=0,1,2 in Fx,y. Compared with the calculation of the modular multiplication, the time cost of modular addition can be negligible. Hence, there are totally 22 modular multiplications and some negligible modular additions in the Enc phase. Considering the computational complexity of a multiplication modulo n=pq is Oλ2, we conclude that the computational complexity of the Enc phase is Oλ2.
During the Dec phase, the main operations are to outputa,b from u,v by 2 modular exponentiation operations of exponentiation d. Considering that the computational complexity of a modular exponentiation is Oλ3, the total computational complexity of the Dec phase is Oλ3 when ignoring some modular additions.
During the Eval phase, the outputcf^x,y is actually a truncated bivariable polynomial. There are α-iterations, and every iteration performs a modular multiplication besides a negligible modular addition. Hence, there are totally α-modular multiplications and some negligible modular additions. As a result, the computational complexity of the Eval phase is Oαλ2 subject to the value of α in ciphertext evaluations.
In summary, the computational complexity isOλ2 for encryption, Oλ3 for decryption, and Oαλ2 for evaluation, respectively, where λ≥2048 is the length of the RSA modulus n.
Comparisons of several noiseless FHE: comparisons of several noiseless FHE schemes among [24–26] with ours are shown in Table 2. Nuida utilized the commutator and an encoding scheme by a homomorphic mapping φ from noncommutative group G to noncommutative group G^ to construct the noiseless FHE. The ciphertext is composed of two elements from G and Ker φ which is a subset of G. However, the security is based on the open sampling of group G, and the assumption that judging whether an element is in the kernel Ker φ is difficult. Yagisawa [25] is an improved version of [26] with smaller ciphertext size; hence, we only discuss about [25]. The octonion ring over the finite field was used by Yagisawa to achieve 1:8 length ratio of the plaintext and ciphertext. Yagisawa’s noiseless FHE is immune from the Grobner basis attacks, which is weaker than our one-way security. With respect to ciphertext space and length ratio, our noiseless FHE is more efficient than [25] while less than [24]. Totally speaking, our single-ciphertext FHE scheme is more superior to [24–26], especially considering that the security is more important than other factors for noiseless FHE.Algorithm 2: Algorithm ℬ with access to A.
Input: the public modulus n, and the RSA ciphertext π∈ℤn.(1)
Randomly choose an integerb∈ℤn and compute v≡b3modn.(2)
Setu=π and randomly generate a bivariate polynomial cx,y∈ℤnx,y/x3−u,y3−v.(3)
Setc=u,v,cx,y and run m←Ac,n.(4)
Compute the greatest common divisorx+θ≡gcdx3−umodn,cx,b−mmodn.Output:μ≡−θmodn.Table 2
Comparisons of several noiseless FHE schemes.
SchemesAlgebraic structureCiphertext spaceLengthratioaSecurityNuida [24]Noncommutative groupVector of dimension 21:2GbJudgement of the kernel elementYagisawa [25]Octonion ringOctonion ring1:8Immune from the Grobner basis attacksOursTruncated polynomial ringVector of dimension 31:11One-way securityLengthratioa: the length ratio between the plaintext and ciphertext. Gb: the number of elements in group G.


## 4.2. Description of Our Communication-Efficient PIR Protocol

Before delving our communication-efficient PIR protocol, we first give a brief overview of how our single-ciphertext FHE scheme is utilized to construct the single-server PIR protocol.(i)
The single-server PIR protocol aims to help the user to obtain theith data from the server possessing the whole database, without leaking the index i to the server. Obviously, the server performs an evaluation algorithm on a single ciphertext corresponding to the queried index. So, our single-ciphertext FHE scheme is well suitable for the single-server PIR protocol.(ii)
In our protocol, the user can encrypt the indexi with our single-ciphertext FHE scheme and then send the ciphertext to the server. For the consideration of efficiency, we directly encrypt the index with a symmetric encryption scheme. The parameters a,b connect the partial ciphertext cx,y and its corresponding plaintext. In particular, the parameters a,b invoke a polynomial, and the polynomial is used to encrypt the queried index; meanwhile, the polynomial ciphertext cx,y can be directly decrypted with the parameters a,b ignoring the parameters u,v as the auxiliary information. In turn, the server outputs a function about the ith data ai relative to the polynomial ciphertext. Then, the user decrypts the function using the parameters a,b, and he will exactly obtain the ith data ai corresponding to the index i. During the process, the server provides some computation and storage space and is unable to acquire the information of the index i. Consequently, our single-server PIR protocol achieves the goal as desired.(iii)
Moreover, we prefer the communication complexity on the user side rather than on the server side. Hence, inSection 6, the communication complexity on the user side is much more important than the overheads on the server side. In the future, we will delve the communication-efficient single-server PIR protocol which can attain the tradeoff overheads of the communication and the computation between the user and the server.In the following, we employ the single-ciphertext FHE scheme proposed inSection 4.1 and the Lagrange interpolating polynomial to construct our communication-efficient single-server PIR protocol. The detailed three algorithms are described as follows:(i)
Query generation phase: taking the indexi0≤i≤N−1 as the input, the user sends a query Qi to the DB server. The details are described in Algorithm 3.(ii)
Response generation phase: upon receiving the queryQi, the DB server outputs Ri=gx,y to the user in Algorithm 4. Note that even if u,v are obtained in the query Qi=n,u,v,cx,y, the DB server cannot recover the index i due to not knowing the symmetric key a,b.(iii)
Response retrieval phase: refer to Algorithm5. Upon receiving the response Ri=gx,y, the user retrieves the data DBi≡ga,bmodn corresponding to the index i by using the symmetric key a,b.Algorithm 3: The query generation algorithm (user).
Input: the index i0≤i≤N−1.(1)
Randomly generateλ/2-bit-long primes p,q subject to gcd p−1,3=1 and gcd q−1,3=1 and compute n=pq.(2)
Randomly chooseaij∈ℤn for i,j=0,1,2 and set fx,y=∑i=02∑j=02aijxiyj.(3)
Randomly choosea,b∈ℤn and compute u≡a3modn,v≡b3modn.(4)
SetFx,y≡fx,y−fa,bmodn.(5)
Computecx,y≡Fx,y+imodn.//The symmetric keya,bis kept by the user and private for the DB server.Output:Qi=n,u,v,cx,y.Correctness: now, we illustrate the correctness of our proposed single-server PIR protocol, namely,DBi=RRDB,i,Qi,Ri, for any database DB=a0,a1,…,aN−1 with any size N and any index 0≤i≤N−1.During the response generation phase, the responseRi=gx,y is an evaluation of encryption of index i. Meanwhile, the response Ri=gx,y is N numbers of addition operations about the whole data al for 0≤l≤N−1. When decrypting the response Ri correctly, the user will obtain that(6)ga,b≡∑l=0N−1al∏0≤j≤N−1,j≠lca,b−jl−jmodn≡∑l=0N−1al∏0≤j≤N−1,j≠li−jl−jmodn∵ca,b≡imodn≡a0·i−10−1·i−20−2⋯i−N−10−N−1+a1·i−01−0·i−21−2⋯i−N−11−N−1+⋯⋯+aN−1·i−0N−1−0·i−1N−1−1⋯i−N−2N−1−N−2modn.When we assumei=1 for an example, it is obvious that the above items (6) in ga,b all equal 0 since there is an item i−1 in the molecule, while item (6) in ga,b equals a1 since the molecule is equal to the denominator. Therefore, we can conclude that once decrypting the response Ri correctly, the user will obtain that ga,b≡aimodn since ca,b≡imodn. As a result, the correctness of our proposed single-server PIR protocol holds, as desired.Remark 2.
Note that the length of each itemDBi, for any 0≤i≤N−1, in DB should be smaller than λ. Otherwise, what the user would obtain from the above response retrieval algorithm is not the value of DBi as DBi had been damaged by the operation of modulo n.


## 5. Security Analyses

In this section, we will discuss the security of our single-server PIR protocol. We particularly focus on the privacy properties, i.e., the query index should be privacy preserving, and the response is also privacy preserving in the proposed single-server PIR protocol.(i)
The query index is privacy preserving in the proposed single-server PIR protocol: our design goal is to require that the queried indexi should be private, and no one, except the query user, can determine the value of i. As we know, the query index is encrypted by our single-ciphertext FHE scheme, and only the query user can obtain the index. Because the security of our single-ciphertext FHE scheme can be reduced to the 3rd RSA problem, without knowing the private key, no one can retrieve the query index. As a result, the query index can be hidden, and the privacy-preserving requirement on the query index can be achieved in the proposed single-server PIR protocol.(ii)
The response is also privacy preserving in the proposed single-server PIR protocol: since we consider there is no collusion on the DB server, the server will not forge the data inDB. Instead, the server will follow Algorithm 4 and output correct responses. Moreover, according to the correctness in Section 4.2, it is easy to find that the response Ri is a polynomial about the encryption of DBi. Automatically, the data DBi can be hidden in the response Ri. No one, except the query user, can retrieve DBi by correctly decrypting the response Ri. Therefore, the response is privacy preserving in the proposed single-server PIR protocol (Algorithm 5).Algorithm 4: Response generation algorithm (DB server).
Input: a database B=a0,a1,…,aN−1 of size N and a query Qi=n,u,v,cx,y.(1)
Computegx,y≡∑l=0N−1al∏0≤j≤N−1,j≠lcx,y−j/l−jmodn,x3−u,y3−v.Output:Ri=gx,y.Algorithm 5: The response retrieval algorithm (user).
Input: the response Ri=gx,y and the symmetric key a,b.Output:DBi≡ga,bmodn.Now, we will present the security of our single-server PIR protocol by the simulation-based framework.Theorem 2.
Our single-server PIR protocol is secure against the adversariesA=User,Server.Proof.
We will elaborate that there is a probabilistic polynomial time simulatorSServer playing the role of the DB server such that the real view and the ideal one are computationally indistinguishable for User.The interactions between User andSServer are defined by the following steps:(1)
Following Algorithm3, User sends Qi of the index i to SServer(2)
SServer sends the encryption of ai back to User(3)
Decrypt the result fromSServer with his own secret key, and User will obtain ai as desired
The real view for User isQi,Ri,ai, while the ideal view for User is Qi,Encai,ai. Considering that Ri and Encai are indistinguishable, we can conclude that the ideal view of User is indistinguishable from the real view. Then, we can claim that User can learn nothing about the data from the database server except ai, which implies that the single-server PIR protocol is secure for the DB server.
From the above analyses, we can see our proposed single-server PIR protocol is confidential and can protect the information of the indexi and the corresponding data ai.Remark 3.
In our security model, we consider the DB server is honest but curious. However, we cannot avoid the semimalicious DB servers. To prevent semimalicious servers from forging the data inDB as responses, we can add a verifiable procedure during the response generation phase. The following is a desirable attempt: we will use a hash function h to act on the data because of its one-wayness. During the response generation phase, we require the server should substitute al with al‖hal in Algorithm 4 and send a correct result in the response gx,y to the user, where .‖ represents concatenation. There is no doubt that the length of al‖hal is smaller than n, that is, al+hal<λ. Then, the new response R′i=g′x,y is an encryption of the data DBi‖hDBi. Therefore, the user can verify whether the server forges the data. After decrypting the response Ri to obtain ai and hai, the user can compute the hash value hai due to knowing ai. If it equals the value hai the server sends, the data ai are exactly corresponding to the index i without errors. If not, the server is dishonest. The details are omitted here.


## 6. Performance Evaluation

In this section, we evaluate the performance of our proposed single-server PIR protocol from two perspectives, i.e., the theoretical analyses and experimental evaluation by comparing it with two existing PIR protocols in [6, 7].


### 6.1. Theoretical Analyses of Our PIR Protocol on the User Side

Here, we first illustrate that our single-server PIR protocol is much more efficient and practical than the PIR protocols in [6, 7] in terms of the computational complexity, the extension ratio of the query (similar to the length ratio between the ciphertext and its underlying plaintext, denoted by Ri/DBi), and the communication overhead (denoted by Qi+Ri).Our PIR protocol: in our proposed PIR protocol, since the query generation phase applies our single-ciphertext FHE scheme as the basic symmetric encryption scheme, from the computational complexity analysis inSection 4.1, we can see the computational complexity is Oλ2 for both the query generation and the response retrieval. In addition, we can find that Qi=12λ,Ri=9λ, and DBi=λ. Hence, the extension ratio of the query is Ri/DBi=9 in our single-server PIR protocol. The communication overhead represents the length sum of Qi and Ri, i.e., Qi+Ri. Hence, the communication overhead is 21λ in our single-server PIR protocol.Yi et al.’s PIR protocol [6]: in Yi et al.’s PIR protocol, the computational complexity depends on the modular addition operations, and thus, we consider the computational complexity is O1. Since the data corresponding to the index are one bit and Ri equals the length of the DGHV ciphertext [12], i.e., Ri=Oλ5 and DBi=1, the extension ratio of the query is Ri/DBi=Oλ5. Finally, the communication overhead is OγlogN, where γ is the size of the ciphertext and N is the size of DB. Again, because the DGHV scheme with the ciphertext length Oλ5 is utilized to construct the PIR protocol, the communication overhead is Oλ5logN.Li et al.’s PIR protocol [7]: the computational complexity of Li et al.’s PIR protocol mainly relies on the total λ7log4N modular multiplications of the matrix multiplication in the HAO scheme [13]. From the computational complexity of modular multiplication mentioned in Section 4.1 and the parameters in [7], we can easily see that the valid computational complexity of Li et al.’s PIR protocol is Oλ9log4N. On the contrary, the data underlying the index are one bit, e.g.,DBi=1. The query user needs to send two ciphertexts to the DB server: one is an encryption of the query with communication overhead Oλ2log2N, and the other is an encryption of the key with communication overhead logN+12·λ4=Oλ4log2N, while the DB server needs to send back an encryption of DBi with communication overhead Oλ4log2N to the user, i.e., Qi=Ri=Oλ4log2N. As a result, both the extension ratio of the query and the communication overhead in [7] are Oλ4log2N.Table3 summarizes the differences among the above three PIR protocols, where the second column “Batching” captures whether the PIR protocol can directly encrypt the index from ℤn. If the PIR protocol can, we output “Yes” and “No,” otherwise, and the symbol λ is the security parameter and N is the database size. It is obvious that our proposed single-server PIR protocol, which has access to the database DB composed of items from ℤn, can directly encrypt the index from ℤn and perform the processing batch, while the PIR protocols in [6, 7] cannot. This fact makes our single-server PIR protocol more practical. In addition, from the table, we can see, in terms of the communication overhead, our single-server PIR protocol is far superior to [6, 7] since ours is independent on the database size N.Table 3
The theoretical performance analyses of PIR protocols.
SchemesBatchingCCaERQbCOc/bitsYi et al. [6]NoO1Oλ5Oλ5logNLi et al. [7]NoOλ9log4NOλ4log2NOλ4log2NOursYesOλ2921λCCa: CC represents a valid computational complexity for the user. ERQb: we use ERQ to denote the extension ratio of the query, i.e., Ri/DBi. COc: CO of unit bit represents the communication overhead, i.e., Qi+Ri.When setting the security parameterλ=2048 in our PIR protocol and λ=128 in PIR protocols [6, 7] for achieving certain security level, Figure 2 compares the communication overheads of the three PIR protocols varying with N from 21 to 220. From the figure, we can see that our proposed single-server PIR protocol is much more efficient, especially for a larger N. Furthermore, no one can deny that when N is considered in the range 21,220, the communication overheads of the PIR protocols in Yi et al. [6] and Li et al. [7] are largely subject to the security parameter λ in comparison to the database size N, and the communication overhead Oλ4log2N in Li et al.’s protocol is better than Oλ5logN in Yi et al.’s protocol from Figure 2. To the best of our knowledge, for a fixed security parameter λ, our proposed protocol is the first single-server PIR protocol, which can achieve O1 communication efficiency.Figure 2
Communication cost comparisons varying withN from 21 to 220 when setting the security parameter λ=2048 in our PIR protocol and λ=128 in PIR protocols [6, 7] for achieving certain security level.


### 6.2. Theoretical Analyses of Our PIR Protocol on the Server Side

Although we prefer the communication for the user than the computation complexity on the server to evaluate the efficiency of our single-server PIR protocol, the theoretical analysis on the server side is necessary to be illustrated in this section. In brief, we will present the computation burden on the server compared with the PIR protocols in [6, 7].Our PIR protocol: the server mainly performs operations upon the special bivariate polynomials, i.e., the degree of either variablex (or y) is no more than 2. Specifically, N number of additions upon the bivariate polynomials for the server are enough, where N is the number of databases. Meanwhile, every bivariate polynomial also includes operations of polynomials modulo n,x3−u, and y3−v. And N number of bivariate polynomials can be performed in parallel or in a preprocessing way. Quantitatively speaking, the computational complexity is near to ON·λ2, where λ≥2048 bits.Yi et al.’s PIR protocol [6]: Yi et al. encrypted the index with binary strings of length l=⌊logN⌋+1. Every bit is protected with an FHE scheme called DGHV10 [12]. During the response generation in the PIR protocol, the server mainly computes 2l number of modulus additions and l−1 number of modulus multiplications upon the integers of length Oλ5. In addition, the server also provides l number of ciphertexts. In a nutshell, the computational burden of the server is OlogN·λ10.Li et al.’s PIR protocol [7]: after receiving the ciphertexts of queried index i and the secret key, the server performs a bootstrapping operation, i.e., homomorphically evaluate the decryption circuits, which is a very expensive process and occupies numerous overhead of computations for the server. The best result of bootstrapping at present is not exceeding 10 ms [27] when homomorphically implementing a single gate. It remains to be far from being practical to homomorphically evaluating a computing circuit. We will not describe the computation complexity of the bootstrapping but claim that the decryption circuit is of depth almost Ologλ [20].Totally speaking, the computational burden of our single-server PIR protocol is relatively less than [6, 7]. However, the experimental performance of the server will not be analysed in the following Section 6.3 since we regard the server powerful and can provide unrestricted computations. Furthermore, the computation burden of the server in our single-server PIR can be relaxed in parallel or in a preprocessing way.


### 6.3. Experimental Evaluations of Our PIR Protocol

In this section, we further present some experimental evaluations of our PIR protocol in comparison with the PIR protocols in [6, 7]. It is obvious to see that there are two common factors for the PIR protocols in [6, 7], i.e., the queried index is resolved into its binary presentation and the data in the database DB only consist of one bit 0 or 1, while in our PIR protocol, we can directly encrypt the index, not in its binary representation, and the data in DB belonging to ℤn are more practical. The details of experimental settings are as follows.Our PIR protocol: we implement our proposed protocol on a personal computer by utilizing the NTL [28] and the C++ language. The environment is listed as follows:(i)
CPU: Intel(R) Core(TM) i3-7100 3.90 GHz(ii)
RAM: 4.00 GB(iii)
OS: Windows 10, 64 bitsThe length of the modulus ofn in our experiment includes 2048 bits, 2560 bits, and 3072 bits. The size N of DB varies from 800, 1000, to 1200. Although the number of items in the database N seems a little small, the whole space of the database is not small at all. Considering that the response generation (RG) phase is performed by the DB server and the query generation (QG) phase and response retrieval (RR) phase are run at the user side, we test 100 instances on ℤn for every phase. The average results are given in Tables 4–6.Table 4
The computational costs of our PIR protocol underN=800.
nInstancesQG phaseRR phaseRG phase2048 bits1003.7μs1.36 ms1.65 h2560 bits1004.6μs2.00 ms2.41 h3072 bits1005.2μs2.82 ms3.16 hTable 5
The computational costs of our PIR protocol underN=1000.
nInstancesQG phaseRR phaseRG phase2048 bits1003.7μs1.34 ms2.41 h2560 bits1004.5μs2.01 ms3.89 h3072 bits1005.4μs2.80 ms4.98 hTable 6
The computational costs of our PIR protocol underN=1200.
nInstancesQG phaseRR phaseRG phase2048 bits1003.5μs1.38 ms3.55 h2560 bits1004.5μs2.04 ms5.45 h3072 bits1005.3μs2.80 ms7.09 hThe first column called “n” represents the length of RSA modulus, and the data in DB are from ℤn. The second column means the number of our tested instances. We use the time of the query generation phase, response retrieval phase, and response generation phase to illustrate the performance of our single-server PIR protocol.From Tables4 to 6, it is easy to see that the size N of DB has a little bit effect on the user side in our single-server PIR protocol, which can almost be ignored. We also see that the time in the query generation phase and response retrieval phase increases a little with the modulus growing under the same situations. On the contrary, the time cost on the DB server side largely depends on the size N. When the database size N is fixed, the DB server takes more time with n increasing. Similarly, when the modulus n is fixed, the DB server also takes more time with N increasing. In brief, it shows that our single-server PIR protocol is efficient. For example, even when the modulus is n=3072 bits, the query generation phase only costs 5.4 μs, and the response retrieval phase costs 2.82 ms at most when all data in the database DB are drawn from ℤn.The effects of database sizeN on the user and the DB server are readily comprehensible. Theoretically speaking, there are just modular multiplications and some negligible modular additions for the user, all of which are irrelevant to the size N during the query generation phase, let alone the response retrieval phase. On the contrary, the response generation phase completely relies on all the data in database DB. Hence, the size N is the main factor for the time cost at the DB server side. Nevertheless, the server can perform parallel computations to reduce the computational complexity from ON2log2n to ONlogNlog2n. Furthermore, when a powerful DB server is employed, the time costs at the DB server side should be reduced greatly.Yi et al.’s PIR protocol [6]: Yi et al. [6] experimented on a PBR protocol (an extension of a PIR protocol) with 10,000 blocks instead of a PIR protocol. The query generation phase costs 10 μs when the modulus is of 882 bits. The overhead is obviously larger than our single-server PIR protocol. In addition, Yi et al.’s scheme did not discuss the time cost of the response retrieval phase. On this basis, our single-server PIR protocol has obvious advantages over [6]. Moreover, their PBR protocol cannot encrypt the index from ℤn, let alone within a few milliseconds.Li et al.’s PIR protocol [7]: Li et al. [7] proposed a PIR protocol based on the lattice assumption. However, they did not use simulation to evaluate their PIR protocol. Nevertheless, we can claim that our single-server PIR protocol is more efficient than [7] based on the aforementioned theoretic analyses of computational complexity, the extension ratio of the query, and the communication overhead. In addition, the performance of Li et al.’s PIR protocol [7] relies on the efficiency of the bootstrapping and the size of the secret key. The size of the secret key in [7] is OλlogN, and by now, the best result for bootstrapping does not exceed 10 ms to evaluate a single gate in [27], which is impractical.To sum up, our experimental evaluation further demonstrates that our single-server PIR protocol is more efficient and practical.


## 6.1. Theoretical Analyses of Our PIR Protocol on the User Side

Here, we first illustrate that our single-server PIR protocol is much more efficient and practical than the PIR protocols in [6, 7] in terms of the computational complexity, the extension ratio of the query (similar to the length ratio between the ciphertext and its underlying plaintext, denoted by Ri/DBi), and the communication overhead (denoted by Qi+Ri).Our PIR protocol: in our proposed PIR protocol, since the query generation phase applies our single-ciphertext FHE scheme as the basic symmetric encryption scheme, from the computational complexity analysis inSection 4.1, we can see the computational complexity is Oλ2 for both the query generation and the response retrieval. In addition, we can find that Qi=12λ,Ri=9λ, and DBi=λ. Hence, the extension ratio of the query is Ri/DBi=9 in our single-server PIR protocol. The communication overhead represents the length sum of Qi and Ri, i.e., Qi+Ri. Hence, the communication overhead is 21λ in our single-server PIR protocol.Yi et al.’s PIR protocol [6]: in Yi et al.’s PIR protocol, the computational complexity depends on the modular addition operations, and thus, we consider the computational complexity is O1. Since the data corresponding to the index are one bit and Ri equals the length of the DGHV ciphertext [12], i.e., Ri=Oλ5 and DBi=1, the extension ratio of the query is Ri/DBi=Oλ5. Finally, the communication overhead is OγlogN, where γ is the size of the ciphertext and N is the size of DB. Again, because the DGHV scheme with the ciphertext length Oλ5 is utilized to construct the PIR protocol, the communication overhead is Oλ5logN.Li et al.’s PIR protocol [7]: the computational complexity of Li et al.’s PIR protocol mainly relies on the total λ7log4N modular multiplications of the matrix multiplication in the HAO scheme [13]. From the computational complexity of modular multiplication mentioned in Section 4.1 and the parameters in [7], we can easily see that the valid computational complexity of Li et al.’s PIR protocol is Oλ9log4N. On the contrary, the data underlying the index are one bit, e.g.,DBi=1. The query user needs to send two ciphertexts to the DB server: one is an encryption of the query with communication overhead Oλ2log2N, and the other is an encryption of the key with communication overhead logN+12·λ4=Oλ4log2N, while the DB server needs to send back an encryption of DBi with communication overhead Oλ4log2N to the user, i.e., Qi=Ri=Oλ4log2N. As a result, both the extension ratio of the query and the communication overhead in [7] are Oλ4log2N.Table3 summarizes the differences among the above three PIR protocols, where the second column “Batching” captures whether the PIR protocol can directly encrypt the index from ℤn. If the PIR protocol can, we output “Yes” and “No,” otherwise, and the symbol λ is the security parameter and N is the database size. It is obvious that our proposed single-server PIR protocol, which has access to the database DB composed of items from ℤn, can directly encrypt the index from ℤn and perform the processing batch, while the PIR protocols in [6, 7] cannot. This fact makes our single-server PIR protocol more practical. In addition, from the table, we can see, in terms of the communication overhead, our single-server PIR protocol is far superior to [6, 7] since ours is independent on the database size N.Table 3
The theoretical performance analyses of PIR protocols.
SchemesBatchingCCaERQbCOc/bitsYi et al. [6]NoO1Oλ5Oλ5logNLi et al. [7]NoOλ9log4NOλ4log2NOλ4log2NOursYesOλ2921λCCa: CC represents a valid computational complexity for the user. ERQb: we use ERQ to denote the extension ratio of the query, i.e., Ri/DBi. COc: CO of unit bit represents the communication overhead, i.e., Qi+Ri.When setting the security parameterλ=2048 in our PIR protocol and λ=128 in PIR protocols [6, 7] for achieving certain security level, Figure 2 compares the communication overheads of the three PIR protocols varying with N from 21 to 220. From the figure, we can see that our proposed single-server PIR protocol is much more efficient, especially for a larger N. Furthermore, no one can deny that when N is considered in the range 21,220, the communication overheads of the PIR protocols in Yi et al. [6] and Li et al. [7] are largely subject to the security parameter λ in comparison to the database size N, and the communication overhead Oλ4log2N in Li et al.’s protocol is better than Oλ5logN in Yi et al.’s protocol from Figure 2. To the best of our knowledge, for a fixed security parameter λ, our proposed protocol is the first single-server PIR protocol, which can achieve O1 communication efficiency.Figure 2
Communication cost comparisons varying withN from 21 to 220 when setting the security parameter λ=2048 in our PIR protocol and λ=128 in PIR protocols [6, 7] for achieving certain security level.


## 6.2. Theoretical Analyses of Our PIR Protocol on the Server Side

Although we prefer the communication for the user than the computation complexity on the server to evaluate the efficiency of our single-server PIR protocol, the theoretical analysis on the server side is necessary to be illustrated in this section. In brief, we will present the computation burden on the server compared with the PIR protocols in [6, 7].Our PIR protocol: the server mainly performs operations upon the special bivariate polynomials, i.e., the degree of either variablex (or y) is no more than 2. Specifically, N number of additions upon the bivariate polynomials for the server are enough, where N is the number of databases. Meanwhile, every bivariate polynomial also includes operations of polynomials modulo n,x3−u, and y3−v. And N number of bivariate polynomials can be performed in parallel or in a preprocessing way. Quantitatively speaking, the computational complexity is near to ON·λ2, where λ≥2048 bits.Yi et al.’s PIR protocol [6]: Yi et al. encrypted the index with binary strings of length l=⌊logN⌋+1. Every bit is protected with an FHE scheme called DGHV10 [12]. During the response generation in the PIR protocol, the server mainly computes 2l number of modulus additions and l−1 number of modulus multiplications upon the integers of length Oλ5. In addition, the server also provides l number of ciphertexts. In a nutshell, the computational burden of the server is OlogN·λ10.Li et al.’s PIR protocol [7]: after receiving the ciphertexts of queried index i and the secret key, the server performs a bootstrapping operation, i.e., homomorphically evaluate the decryption circuits, which is a very expensive process and occupies numerous overhead of computations for the server. The best result of bootstrapping at present is not exceeding 10 ms [27] when homomorphically implementing a single gate. It remains to be far from being practical to homomorphically evaluating a computing circuit. We will not describe the computation complexity of the bootstrapping but claim that the decryption circuit is of depth almost Ologλ [20].Totally speaking, the computational burden of our single-server PIR protocol is relatively less than [6, 7]. However, the experimental performance of the server will not be analysed in the following Section 6.3 since we regard the server powerful and can provide unrestricted computations. Furthermore, the computation burden of the server in our single-server PIR can be relaxed in parallel or in a preprocessing way.


## 6.3. Experimental Evaluations of Our PIR Protocol

In this section, we further present some experimental evaluations of our PIR protocol in comparison with the PIR protocols in [6, 7]. It is obvious to see that there are two common factors for the PIR protocols in [6, 7], i.e., the queried index is resolved into its binary presentation and the data in the database DB only consist of one bit 0 or 1, while in our PIR protocol, we can directly encrypt the index, not in its binary representation, and the data in DB belonging to ℤn are more practical. The details of experimental settings are as follows.Our PIR protocol: we implement our proposed protocol on a personal computer by utilizing the NTL [28] and the C++ language. The environment is listed as follows:(i)
CPU: Intel(R) Core(TM) i3-7100 3.90 GHz(ii)
RAM: 4.00 GB(iii)
OS: Windows 10, 64 bitsThe length of the modulus ofn in our experiment includes 2048 bits, 2560 bits, and 3072 bits. The size N of DB varies from 800, 1000, to 1200. Although the number of items in the database N seems a little small, the whole space of the database is not small at all. Considering that the response generation (RG) phase is performed by the DB server and the query generation (QG) phase and response retrieval (RR) phase are run at the user side, we test 100 instances on ℤn for every phase. The average results are given in Tables 4–6.Table 4
The computational costs of our PIR protocol underN=800.
nInstancesQG phaseRR phaseRG phase2048 bits1003.7μs1.36 ms1.65 h2560 bits1004.6μs2.00 ms2.41 h3072 bits1005.2μs2.82 ms3.16 hTable 5
The computational costs of our PIR protocol underN=1000.
nInstancesQG phaseRR phaseRG phase2048 bits1003.7μs1.34 ms2.41 h2560 bits1004.5μs2.01 ms3.89 h3072 bits1005.4μs2.80 ms4.98 hTable 6
The computational costs of our PIR protocol underN=1200.
nInstancesQG phaseRR phaseRG phase2048 bits1003.5μs1.38 ms3.55 h2560 bits1004.5μs2.04 ms5.45 h3072 bits1005.3μs2.80 ms7.09 hThe first column called “n” represents the length of RSA modulus, and the data in DB are from ℤn. The second column means the number of our tested instances. We use the time of the query generation phase, response retrieval phase, and response generation phase to illustrate the performance of our single-server PIR protocol.From Tables4 to 6, it is easy to see that the size N of DB has a little bit effect on the user side in our single-server PIR protocol, which can almost be ignored. We also see that the time in the query generation phase and response retrieval phase increases a little with the modulus growing under the same situations. On the contrary, the time cost on the DB server side largely depends on the size N. When the database size N is fixed, the DB server takes more time with n increasing. Similarly, when the modulus n is fixed, the DB server also takes more time with N increasing. In brief, it shows that our single-server PIR protocol is efficient. For example, even when the modulus is n=3072 bits, the query generation phase only costs 5.4 μs, and the response retrieval phase costs 2.82 ms at most when all data in the database DB are drawn from ℤn.The effects of database sizeN on the user and the DB server are readily comprehensible. Theoretically speaking, there are just modular multiplications and some negligible modular additions for the user, all of which are irrelevant to the size N during the query generation phase, let alone the response retrieval phase. On the contrary, the response generation phase completely relies on all the data in database DB. Hence, the size N is the main factor for the time cost at the DB server side. Nevertheless, the server can perform parallel computations to reduce the computational complexity from ON2log2n to ONlogNlog2n. Furthermore, when a powerful DB server is employed, the time costs at the DB server side should be reduced greatly.Yi et al.’s PIR protocol [6]: Yi et al. [6] experimented on a PBR protocol (an extension of a PIR protocol) with 10,000 blocks instead of a PIR protocol. The query generation phase costs 10 μs when the modulus is of 882 bits. The overhead is obviously larger than our single-server PIR protocol. In addition, Yi et al.’s scheme did not discuss the time cost of the response retrieval phase. On this basis, our single-server PIR protocol has obvious advantages over [6]. Moreover, their PBR protocol cannot encrypt the index from ℤn, let alone within a few milliseconds.Li et al.’s PIR protocol [7]: Li et al. [7] proposed a PIR protocol based on the lattice assumption. However, they did not use simulation to evaluate their PIR protocol. Nevertheless, we can claim that our single-server PIR protocol is more efficient than [7] based on the aforementioned theoretic analyses of computational complexity, the extension ratio of the query, and the communication overhead. In addition, the performance of Li et al.’s PIR protocol [7] relies on the efficiency of the bootstrapping and the size of the secret key. The size of the secret key in [7] is OλlogN, and by now, the best result for bootstrapping does not exceed 10 ms to evaluate a single gate in [27], which is impractical.To sum up, our experimental evaluation further demonstrates that our single-server PIR protocol is more efficient and practical.


## 7. Related Work

In this section, we will briefly review some FHE schemes and some other existing single-server PIR protocols, which are closely related to our proposal.Fully homomorphic encryption: FHE enables meaningful process over encrypted data without access to the original plaintext data. In the past years, many generic FHE constructions have been proposed [10, 12, 13, 18–20]. For example, the first generation is represented by the DGHV FHE scheme [12], which serves as a vital tool in building a PIR protocol in [6]. However, most of them turn out to be impractical. The main reason is that the noises are added to the ciphertexts for the consideration of the security. Later, a new class of FHE schemes without noises have naturally been exploited to avoid complicated noise management [24–26, 29]. For example, Nuida [24] declared a beautiful public key FHE frame without noises, employing a commutator and an encoding scheme over two noncommutative groups. The security is based on an assumption that judging whether an element is in the kernel is difficult, which is not standard. Yagisawa [25, 26] proposed noiseless FHE schemes with the underlying octonion ring over the finite field, which are immune from the Grobner basis attacks. Nevertheless, it remains an open problem to prove strictly secure and feasible in the framework of provable security. In this work, motivated by the noiseless FHE schemes, we define a special kind of algebraic structure called truncated polynomial rings to construct a single-ciphertext FHE scheme. Our proposed scheme is noiseless, and hence, it inherently supports fully homomorphic computations on any univariate polynomials, such as the single-server PIR protocols. In addition, there is a security reduction between the one-wayness of our single-ciphertext FHE scheme and the 3rd RSA problem we define. Compared with the FHE schemes in [6, 7], our single-ciphertext FHE scheme is noiseless and of the smallest ciphertext size, which offer enormous convenience for the single-server PIR protocols.Single-server PIR protocols: a single-server PIR protocol allows a user to retrieve thei-th data from a database server without revealing the index i. The past years have witnessed the development of the single-server PIR protocols, especially in communication cost [30–33]. For example, Cachin et al. [31] proposed a PIR protocol based on the φ-hiding assumption with communication complexity Olog4N. And the Damgard–Jurik scheme [34] was utilized by Lipmaa [32] to construct a PIR protocol, which achieved Olog2N communication complexity. However, most of them are inefficient due to depending on the database size N, especially when N is million or even larger magnitude in real life. Hence, it will be a great work to construct a single-server PIR protocol with communication overhead O1, which is irrelevant to the database size N. In this work, we devote ourselves to designing a single-server PIR protocol with communication efficiency O1. First, on the basis of the single-server PIR protocols in [6, 7], we tend to resort to the FHE schemes since the FHE schemes not only keep privacy preserving but also support direct computations on encrypted data. Second, the Lagrange interpolating polynomial is a suitable tool for the database DB=i,DBi|0≤i≤N−1 owing to its property. Hence, an FHE scheme and the Lagrange interpolating polynomial technique are used to construct our single-server PIR protocol. Meanwhile, theoretical analyses and experimental evaluations are performed to demonstrate that our single-server PIR protocol is efficient, which is the first one of communication overhead O1.


## 8. Conclusions

In this paper, we have proposed a new communication-efficient PIR protocol by using homomorphically computing univariate polynomials. Specifically, we first propose a new cryptographic primitive called single-ciphertext FHE and instantiate the special kind of FHE supporting evaluations of a single ciphertext. Then, we illustrate how the single-ciphertext FHE scheme works in our single-server PIR protocol. Theoretical analyses and experimental evaluations are both conducted to demonstrate that it is more efficient and practical to apply our single-ciphertext FHE scheme to the PIR protocol. To the best of our knowledge, our proposed protocol is the first PIR protocol, which can achieveO1 communication efficiency on the user side, irrelevant to the database size N. In future work, we will study other FHE techniques to exploit more efficient PIR protocols, which can achieve the tradeoff overheads of the communication and the computation between the user and the server.



---

*Source: 5553256-2021-04-28.xml*