Towards practical private information retrieval from homomorphic encryption
Private information retrieval (PIR) allows a client to retrieve data from a remote database while hiding the client's access pattern. To be applicable for practical usage, PIR protocol should have low communication and computational costs. In this paper a new generic PIR protocol based on som...
Gespeichert in:
| Datum: | 2015 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2015
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/154248 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Towards practical private information retrieval from homomorphic encryption / D. Zhuravlev // Algebra and Discrete Mathematics. — 2015. — Vol. 19, № 2. — С. 302–312. — Бібліогр.: 11 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-154248 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1542482019-06-16T01:26:33Z Towards practical private information retrieval from homomorphic encryption Zhuravlev, D. Private information retrieval (PIR) allows a client to retrieve data from a remote database while hiding the client's access pattern. To be applicable for practical usage, PIR protocol should have low communication and computational costs. In this paper a new generic PIR protocol based on somewhat homomorphic encryption (SWHE) is proposed. Compared to existing constructions the proposed scheme has reduced multiplicative depth of the homomorphic evaluation circuit which allows to cut down the total overhead in schemes with ciphertext expansion. The construction results in a system with O(logn) communication cost and O(n) computational complexity for a database of size n. 2015 Article Towards practical private information retrieval from homomorphic encryption / D. Zhuravlev // Algebra and Discrete Mathematics. — 2015. — Vol. 19, № 2. — С. 302–312. — Бібліогр.: 11 назв. — англ. 1726-3255 2010 MSC:11T71. http://dspace.nbuv.gov.ua/handle/123456789/154248 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
Private information retrieval (PIR) allows a client to retrieve data from a remote database while hiding the client's access pattern.
To be applicable for practical usage, PIR protocol should have low communication and computational costs.
In this paper a new generic PIR protocol based on somewhat homomorphic encryption (SWHE) is proposed.
Compared to existing constructions the proposed scheme has reduced multiplicative depth of the homomorphic evaluation circuit
which allows to cut down the total overhead in schemes with ciphertext expansion.
The construction results in a system with O(logn) communication cost and O(n) computational complexity for a database of size n. |
| format |
Article |
| author |
Zhuravlev, D. |
| spellingShingle |
Zhuravlev, D. Towards practical private information retrieval from homomorphic encryption Algebra and Discrete Mathematics |
| author_facet |
Zhuravlev, D. |
| author_sort |
Zhuravlev, D. |
| title |
Towards practical private information retrieval from homomorphic encryption |
| title_short |
Towards practical private information retrieval from homomorphic encryption |
| title_full |
Towards practical private information retrieval from homomorphic encryption |
| title_fullStr |
Towards practical private information retrieval from homomorphic encryption |
| title_full_unstemmed |
Towards practical private information retrieval from homomorphic encryption |
| title_sort |
towards practical private information retrieval from homomorphic encryption |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2015 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/154248 |
| citation_txt |
Towards practical private information retrieval from homomorphic encryption / D. Zhuravlev // Algebra and Discrete Mathematics. — 2015. — Vol. 19, № 2. — С. 302–312. — Бібліогр.: 11 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT zhuravlevd towardspracticalprivateinformationretrievalfromhomomorphicencryption |
| first_indexed |
2025-07-14T05:54:26Z |
| last_indexed |
2025-07-14T05:54:26Z |
| _version_ |
1837600570029899776 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 19 (2015). Number 2, pp. 302–312
© Journal “Algebra and Discrete Mathematics”
Towards practical private information retrieval
from homomorphic encryption
Dmitry Zhuravlev∗
Communicated by V. V. Kirichenko
Abstract. Private information retrieval (PIR) allows a client
to retrieve data from a remote database while hiding the client’s
access pattern. To be applicable for practical usage, PIR protocol
should have low communication and computational costs. In this
paper a new generic PIR protocol based on somewhat homomorphic
encryption (SWHE) is proposed. Compared to existing construc-
tions the proposed scheme has reduced multiplicative depth of the
homomorphic evaluation circuit which allows to cut down the total
overhead in schemes with ciphertext expansion. The construction
results in a system with O(log n) communication cost and O(n)
computational complexity for a database of size n.
Introduction
Confidentiality of queries to publicly accessible on-line data sources is
becoming increasingly important for retrieving up-to-date information
in many domains, such as patent and media databases, real-time stock
quotes, Internet domain names, location-based services, on-line behavioral
profiling and advertising, e-commerce and search engines. The private
information retrieval (PIR) technology allows to protect client’s query
∗The author would like to thank Ihor Samoilovych for his helpful discussions in the
process of this work.
2010 MSC: 11T71.
Key words and phrases: protocols, encryption, servers, complexity theory, pri-
vate information retrieval, homomorphic encryption.
D. Zhuravlev 303
in such a way that server (or database administrator) cannot infer the
purpose of the query while still being able to return the desired data
(see Fig. 1).
Figure 1. PIR scheme.
PIR was introduced by Chor et al. [1] in non-colluding multi-server
settings. In [2] it was proposed the first single database PIR protocol
based on hardness computationally assumptions. Namely, the security
of the proposed scheme relies on quadratic residuosity problem. The
communication complexity of the protocol is O(2
√
log n log log N ), where n
is the number of bits in the database and N is a composite modulus.
Recent progress in homomorphic cryptography gives rise for new
approaches to PIR. In [3] Gentry constructed the first fully homomorphic
encryption (FHE) scheme — an encryption scheme that supports arbitrary
number of additions and multiplications over ciphertexts, and therefore
admits to compute arbitrary boolean circuits over encrypted data. In
particular, the selection circuit to access the database can be computed
over ciphertexts. Hence, one can encrypt the index bitwise and then apply
the selection circuit to the encrypted database.
All existing FHE schemes are too expensive to be practical. On the
other hand, there exist [4] more practical somewhat homomorphic encryp-
tion (SWHE) schemes that preserve only limited number of operations.
In [5] Brakerski et al. proposed a generic PIR protocol that utilizes a
SWHE scheme and a symmetric encryption scheme as building blocks. In
their protocol the client uses the symmetric scheme to encrypt the index,
and then the server homomorphically decrypts it during query evaluation.
Thus, the client’s query is short but the server computational cost and
response size can be quite large because of the deep response generation
circuit.
304 Towards practical PIR
In [6] Yi et al. constructed a PIR protocol with communication
complexity O(log n) and computational complexity O(n log n) using the
SWHE scheme from [7]. Similar approach is presented in [8] where the
SWHE scheme from [9] is exploited to privately retrieve the data. In
their protocol a tree-based compression scheme is used to reduce the
communication complexity.
Contribution. The presented approach improves both computational
and communication costs compared to the previous SWHE based PIR
protocols. To adopt PIR for using SWHE, in the proposed protocol the
multiplication depth (the number of nested multiplications) of response
generation circuit was decreased. For example, a SWHE that can evaluate
circuits of depth 5 is sufficient to retrieve the data from a database con-
taining more than 8 billion rows. This multiplication depth is practical for
state-of-the-art SWHE [4]. Moreover, the proposed PIR protocol utilizes
the recursive retrieval algorithm from [10], which allows to reduce compu-
tational complexity from O(n log n) to O(n). The security of proposed
generic protocol is based on the security of the underlying SWHE scheme.
1. Preliminaries
In this section the concepts of PIR protocol and SWHE scheme will
be introduced.
1.1. Notations
Throughout the paper we will use the following notation. In the
sequel, n denotes the database size in bits and l = ⌈log2 n⌉ gives the
bit capacity of database indexes. Vector indexes always start from 0, e.g.
a = (a0, a1, . . . , an−1). For nonnegative l-bit integer i =
∑l−1
k=0 i(k) · 2
k we
denote (k + 1)-th bit of i as i(k) for all k ∈ {0, 1, . . . , l − 1}.
For all a ∈ {0, 1} we use aR to denote corresponding additive iden-
tity 0R and multiplicative identity 1R of unitary ring R, namely
aR def
=
{
0R, if a = 0;
1R, othewise.
For some unitary ring R and all b = (b0, b1, . . . , bl−1) ∈ Rl we define
associated element to (k + 1)-th bit of nonnegative l-bit integer t as
bt
k
def
=
{
bk + 1R, if t(k) = 0;
bk, othewise.
D. Zhuravlev 305
If A is a probabilistic polynomial time (PPT) Turing machine, by
Pr
[
A(x) = y
]
, we denote the probability that y is equal to answer gener-
ated by A on input x. By AB(·), we denote an algorithm that can make
oracle queries to B.
1.2. Definitions
We are now ready to define a single database computational private
information retrieval. PIR protocols consist of two interactive PPT Turing
machines C, S which are called the client and the server, respectively. Each
will take as input the security parameter λ and the size of the database n.
The server will take as input the database d = (d0, d1, . . . , dn−1) ∈ {0, 1}n.
The client will take as input an index i ∈ {0, . . . , n− 1}, and at the end
of the protocol the client will output a bit di. This notion can be formally
described by the following definition:
Definition 1 (PIR Correctness). A PIR protocol (C,S) is correct if for
any λ, n, i and d as specified above, if
(outC , outS)←
〈
C(1λ, n, i),S(1λ, n, d)
〉
then outC = di.
One of the most important properties of the private information
retrieval protocol is the possibility of non-revealing of the index i to the
server. In this paper, we consider a PIR scheme to be secure in the sense
that it is computationally infeasible for an adversary to distinguish two
queries.
Definition 2 (Negligible function). A positive function µ is negligible in
λ, or just negligible, if for every positive polynomial p and any sufficiently
large λ it holds that µ(λ) 6 1/p(λ).
Formally the security of PIR protocol is defined as follows:
Definition 3 (PIR Security). A PIR protocol (C,S) is secure if for all i
and j from {0, 1, . . . , n− 1} and all non-uniform PPT Turing machines
A there exists a negligible function µ such that
∣
∣
∣ Pr
[
(outC , outA)←
〈
C(1λ, n, i),A(state)
〉
: outA = i
]
−
− Pr
[
(outC , outA)←
〈
C(1λ, n, j),A(state)
〉
: outA = i
]
∣
∣
∣ 6 µ(λ) (1)
306 Towards practical PIR
The basis of our PIR protocol is encryption that allows to securely
compute polynomial functions of bounded degree.
Definition 4 (Somewhat homomorphic encryption). A symmetric some-
what homomorphic encryption (SWHE) scheme is a tuple of three PPT
algorithms E = (KeyGen, Enc, Dec) in which its spaces of plaintexts and
ciphertexts are rings and exists a positive number M such that for all
polynomial p with deg (p) 6 M , all plaintexts m0, . . . , mk, and all outputs
sk ← KeyGen (1λ), we have
Dec
(
sk, p(Enc (sk, m0)), . . . , Enc (sk, mk))
)
= p(m0, . . . , mk). (2)
We say that the cryptosystem is secure, if the adversary unable to
distinguish pairs of ciphertexts based on the message is encrypted by
them.
Definition 5 (IND-CPA Security). A symmetric encryption scheme
E = (KeyGen, Enc, Dec) is indistinguishable chosen plaintext attack secure
(IND-CPA) if for any PPT adversary A, there is a negligible function µ
such that
∣
∣
∣ Pr
[
sk ← KeyGen (1λ) : AEnc (sk,Select (·,·,0)) = 1
]
−
− Pr
[
sk ← KeyGen (1λ) : AEnc (sk,Select (·,·,1)) = 1
]
∣
∣
∣ 6 µ(λ), (3)
where Select(m0, m1, b) = mb for b ∈ {0, 1}.
2. From SWHE to PIR
In this section we describe the construction of PIR from [5,6,8] based
on homomorphic cryptography with computational optimization from [10].
2.1. The basic scheme
Let d = (d0, d1, . . . , dn−1) be the client’s database, where di ∈ {0, 1}.
We take a SWHE scheme E = (KeyGen, Enc, Dec) on bits (the message
space is residue ring Z2 = {0, 1}), which is used as a “black-box” module.
The parameters of the scheme are specified to allow below computations.
The idea of retrieving data is based on the observation that one
can algebraically realize the comparison of homomorphically encrypted
indexes. Let i be an index of an element in the database d, 0 6 i < n,
where i(k) ∈ {0, 1} are the bits of i. The client encrypts index i bitwise,
D. Zhuravlev 307
Enc(sk, i) = (c0, . . . , cl−1), ci ← Enc(sk, i(k)), and sends the result to the
server. The server can compare the encrypted address Enc(sk, i) with a
given index j, algebraically:
ej = (c0 + Enc(j(0)) + Enc(1)) · . . . · (cl−1 + Enc(j(l−1)) + Enc(1)),
where Enc (0) and Enc (1) are predetermined encryption of 0 and 1. Since
the ciphertext space R is a ring, 0R and 1R are a valid encryption of 0
and 1.
The homomorphic properties of the scheme E imply that
Dec (sk, ej) =
{
1, if j = i;
0, othewise.
The server computes the auxiliary encrypted choice-bits ek for every
0 6 k < n. Then, in order to access the data with encrypted index End(i),
the server computes the linear combination over all database
r = e0 · Enc (d0) + . . . + en−1 · Enc (dn−1), (4)
where Enc (di) = dR
i is the deterministic bit encryption. The client
decrypts the result and gets the requested value
Dec (r) =
n−1
∑
k=0
Dec (ek) ·Dec (dR
k ) = di.
2.2. Efficiency
Direct computation in formula (4) requires approximately l + n ho-
momorphic additions and l · n multiplications with depth ⌈log2 l⌉ on the
server side per request. In [10] efficient method that combines calculation
of ei and the linear combination (4) was proposed. The main idea of
this method is to consequently reduce the database so that at the end
there is only one element left which is the correct requested element after
decryption. Construct elements
fi = c0 · (d
R
2i + dR
2i+1) + dR
2i, i = 0, 1, . . . , l − 1,
where addition and multiplication are the homomorphic operations from
the encryption scheme. Note that
Dec (sk, fi) =
{
d2i, if Dec (sk, c0) = 0;
d2i+1, if Dec (sk, c0) = 1.
308 Towards practical PIR
Therefore the requested element is the element of the database
(f0, . . . , f2l−1−1) with encrypted index (c1, . . . , cn−1) after decryption. We
can repeat the same construction for the new database and index. After
l steps we obtain only one element, which is di after decryption. The
scheme of the algorithm is shown on Fig. 2.
2
2
0
0 1
2
2 3
4
4
4 5
Figure 2. Retrieving element with index 0102 from database of size 6.
This algorithm reduces the number of operations from O(n log n) to
O(n) while calculating server response. Notice that the multiplicative
depth of polynomial remains ⌈log2 l⌉ as well as in direct computation.
3. Our protocol
In this section, we will show how to decrease the degree of the polyno-
mial in the formula (4) to allow more effective using of server resources.
3.1. PIR with reduced depth
Without loss of generality it is assumed that the database content
is represented as an n-bit string d = (d0, d1, . . . , dn−1) from which the
client wishes to obtain the bit di while keeping the index i private. Let
E = (KeyGen, Enc, Dec) be a symmetric SWHE scheme such that its
plaintexts form the residue ring Z2, its ciphertexts form some unitary
ring (R, +, ·) and this scheme admits correct evaluation of polynomials
of degree l − 1, where l = ⌈log2 n⌉.
The proposed PIR protocol consists of initialization, query, answering
and reconstruction algorithms:
1) Init (λ, n): Given a security parameter λ and the database of size n,
the client invokes KeyGen (1λ) to generate a secret key sk of the
scheme E .
D. Zhuravlev 309
2) QGen (n, i, 1λ): The client encrypts an index i bitwise as ck ←
Enc (sk, i(k)), where i = i(l−1) . . . i(1)i(0) in binary representation.
Let c = (c0, . . . , cl−1).
3) RGen (d, c): The server generates and returns a response consisting
of two parts, i.e (r, s) ∈ R× Z2.
• The server computes r in the ring R:
r =
n−1
∑
t=0
(
dR
t ·
l−1
∏
k=0
ct
k
)
−
n−1
∑
t=0
dR
t ·
l−1
∏
k=0
ck, (5)
where
dR
i
def
=
{
0R, if di = 0
1R, othewise
and ct
k
def
=
{
ck + 1R, if t(k) = 0
ck, othewise
• The server computes the sum s of the database elements as
elements of the ring Z2, i.e. s =
∑n−1
t=0 di.
4) RExt (r, s, i): Given the response (r, s) ∈ R × Z2 and index i, the
client:
• Decrypts r to obtain Dec (sk, r) = r′ ∈ Z2
• Computes the bit di = r′ + s ·
∏l−1
k=0 i(k) ∈ Z2.
Theorem 1 (Correctness). The generic PIR protocol described above is
correct for any SWHE sheme on bits E which can evaluate polynomial of
degree l − 1, any security parameter λ, any database d with any size n
and index 0 6 i < n− 1.
Proof. The degree of polynomial with respect to ciphertext in equation (5)
is l − 1. Thus the homomorphic property of E implies that
Dec (sk, r)+s·
l−1
∏
k=0
i(k) =
n−1
∑
t=0
(
dt·
l−1
∏
k=0
i(k)
t
k
)
−s·
l−1
∏
k=0
i(k)+s·
l−1
∏
k=0
i(k) = di.
3.2. Security proof
Based on the formal definition of security for PIR protocol given in
Section 1, we have
Theorem 2 (Security). If the SWHE scheme E = (KeyGen, Enc, Dec)
is IND-CPA secure, then PIR protocol described above is secure.
310 Towards practical PIR
Proof. We show that if a PPT adversary A against the PIR scheme can
distinguish two queries, than there is an adversary A′ that can distinguish
two ciphertexts.
Assume A distinguishes i0 and i1 with probability ǫ. That is,
∣
∣
∣Pr
[
A(1λ, c0, state) = i1]
− Pr
[
A(1λ, c1, state) = i1]
∣
∣
∣ > ǫ,
where ci = (ci
0, . . . , ci
n−1) such that ck
j ← Enc
(
sk, ik
(j)
)
. This implies,
l−1
∑
k=0
∣
∣
∣ Pr
[
A(Hyb (c0, c1, k)) = Hyb (i0, i1, k − 1)
]
−
− Pr
[
A(Hyb (c0, c1, k − 1)) = Hyb (i0, i1, k − 1)
]
∣
∣
∣ >
>
∣
∣
∣
l−1
∑
k=0
(
Pr
[
A(Hyb (c0, c1, k)) = Hyb (i0, i1, k − 1)
]
−
− Pr
[
A(Hyb (c0, c1, k − 1)) = Hyb (i0, i1, k − 1)
])
∣
∣
∣ > ǫ,
where Hyb (a, b, k)
def
= (a0, . . . , ak−1, bk, . . . , bl−1).
Therefore, there must exist k⋆ such that
∣
∣
∣ Pr
[
A(Hyb (c0, c1, k⋆)) = Hyb (i0, i1, k⋆ − 1)
]
−
− Pr
[
A(Hyb (c0, c1, k⋆ − 1)) = Hyb (i0, i1, k⋆ − 1)
]
∣
∣
∣ >
ǫ
l
.
Consider the algorithm
A′(c⋆)
def
=
{
i0
(k⋆), if A
(
1λ, (c0
0, . . . , c0
k−1, c⋆, c1
k+1, . . . , c1
l−1)
)
= i0;
i1
(k⋆), othewise.
A′ runs in polynomial time since A does. Furthermore, A′ will distin-
guish c⋆ with probability ǫ
l2
.
4. Efficiency analysis
Since the construction described above can potentially be used with
any SWHE scheme, the number of homomorphic operations per request
and the size of ciphertexts were used as an efficiency metric.
The most time consuming step of the response generation is computing
the linear combination (5). An efficient algorithm of encrypted memory
D. Zhuravlev 311
reading proposed in [10] requires approximately O(n) homomorphic addi-
tions and O(n) multiplications on the server side per request.
Current SWHE schemes have a ciphertext expansion property. It
means that the size of server response grows with the multiplicative depth
of the circuit. Unlike previous construction, in the proposed PIR proto-
col the multiplicative depth is ⌈log2 (l − 1)⌉. So overall, the server side
computational complexity and communication overhead in our protocol
is lower.
The current implementation (based on the SWHE scheme from [9]) of
the proposed protocol has the response time 1.88 seconds for a query to
a database with 10-bit indexes and 1-Kb records (the benchmarks were
measured on an i7 @ 2.20 GHz machine).
Conclusion
This research makes another step towards making private information
retrieval applicable for the market use-cases. Nowadays the computation
and communication overhead are the major issues. We have shown how
to improve existing approaches by reducing multiplicative depth of the
response generation circuit and utilization recursive retrieval algorithm.
As the future work, we will test our generic protocol with suitable
SWHE scheme. Recently, Tian et al. [11] showed that the SWHE scheme
from [7] can be effectively realized on GPU. This result gives a way
to significantly improve the performance, because a compute-intensive
retrieval of multi-bit records admits massively parallel computations. Thus,
the speed-up of PIR can be achieved by using parallel computations.
References
[1] B. Chor, E. Kushilevitz, O. Goldreich, M. Sudan, Private Information Retrieval,
ACM, 45, 1998.
[2] E. Kushilevitz, R. Ostrovsky, Replication is not needed: single database,
computationally-private information retrieval, In FOCS, 1997, pp 364.
[3] C. Gentry, A fully homomorphic encryption scheme, PhD thesis, Stanford Univer-
sity, 2009.
[4] K. Lauter, M. Naehrig, V. Vaikuntanathan, Can homomorphic encryption be
practical?, Technical Report MSR-TR-2011-61, Microsoft Research, 2011.
[5] Z. Brakerski, V. Vaikuntanathan, Efficient fully homomorphic encryption from
(standard) LWE, FOCS, 2011, pp. 97-106.
[6] X. Yi, M. Kaosar, R. Paulet, E. Bertino, Single-database private information
retrieval from fully homomorphic encryption, IEEE Trans. Knowl. Data Eng.
25(5), 2013, pp. 1125-1134.
312 Towards practical PIR
[7] M. Dijk, C. Gentry, S. Halevi, V. Vaikuntanathan, Fully Homomorphic Encryption
over the Integers Gilbert, H., ed.: EUROCRYPT. Volume 6110 of Lecture Notes
in Computer Science, Springer, 2010, pp. 24-43.
[8] C. Dong, C. Chen, A Fast Single Server Private Information Retrieval Protocol
with Low Communication Cost, ESORICS, Lecture Notes in Computer Science,
Volume 8712, 2014, pp 380-399.
[9] Z. Brakerski, C. Gentry, V. Vaikuntanathan, (Leveled) fully homomorphic encryp-
tion without bootstrapping, ITCS, 2012, pp. 309-325.
[10] D. Zhuravlev, I. Samoilovych, R. Orlovskyi, I. Bondarenko, Y. Lavrenyuk, En-
crypted Program Execution, TrustCom, 2014.
[11] Y. Tian, M. Al-Rodhaan, B. Song, A. Al-Dhelaan, H. Ma, Somewhat homomorphic
cryptography for matrix multiplication using GPU acceleration, ISBAST, 2014.
Contact information
D. Zhuravlev Department of Mechanics and Mathematics
Kyiv National Taras Shevchenko University
Volodymyrska, 64, Kyiv 01033, Ukraine
E-Mail(s): dzhuravlev@ukr.net
Received by the editors: 11.03.2015
and in final form 16.07.2015.
|