DEIM Forum 2019 I6-1

A Privacy-preserving Query System Model using Fully Homomorphic
Encryption
medicine side eﬀect query system as an example
Yusheng JIANG† , Tamotsu NOGUCHI†† , Nobuyuki KANNO††† , and Hayato YAMANA††††† Department of Computer Science and Communication Engineering, Graduate School of Fundamental
Science and Engineering, Waseda University
11F-06, Building 51, 3-4-1 Okubo, Shinjuku-ku, 169-8555 Tokyo, Japan†† Bioinformatics Laboratory, Department of Mathematical Sciences, Pharmacology Education ResearchCenter, Meiji Pharmaceutical University
2-522-1 Noshio, Kiyose-shi, 204-8588 Tokyo, Japan††† Regional Medicine Laboratory, Department of Clinical Pharmacy, Pharmacology Education ResearchCenter, Meiji Pharmaceutical University
2-522-1 Noshio, Kiyose-shi, 204-8588 Tokyo, Japan†††† Department of Computer Science and Communication Engineering, School of Fundamental Science andEngineering, Faculty of Science and Engineering, Waseda University
11F-05, Building 51, 3-4-1 Okubo, Shinjuku-ku, 169-8555 Tokyo, Japan
E-mail: †{amadeus,yamana}@yama.info.waseda.ac.jp, ††{noguchit,nkanno}@my-pharm.ac.jp
Abstract Privacy preservation during a search has become a serious problem in recent years. There is a needto make sure that user queries that contain sensitive private information are not abused or misused by a third
party, including the search provider. One way to conduct a privacy-preserving search is to encrypt the user queries.
However, traditional encryption methods are only capable of protecting user privacy during a data transfer because
the query itself is decrypted at the query server. A query server is usually provided by an untrustworthy cloudprovider, and the exposure of data may therefore lead to the risk of a data breach. Fully homomorphic encryption(FHE), being capable of conducting addition and multiplication over a ciphertext, naturally provides a solution
to this problem. Using FHE, the privacy of both the user queries and the database of the search provider canbe protected. In this paper, we propose a privacy-preserving query system model. We implemented the proposedmodel on a real-world medicine side-eﬀect query system. We applied a filtering prior to the query to reduce thesize of the database and used multi-threading to accelerate the search. The system was tested 10,000 times with arandom query over a database of 40,000 records of simulation data and completed 99.71% of the queries within 60s, proving the real-world application of our system.
Key words privacy-preserving query, fully homomorphic encryption, secured query system

1 Introduction
As a quick and easy way to extract certain informationcompanies including Facebook [3] and Google [4] are raisingawareness regarding the importance of personal information
security.

from the Internet, a search process is an important Internet

Because users want to hide their query content from leak-service. As improvements to search algorithms [1] and an up-

ing to a third party or prevent misuse, they prefer to conduct

scaling of hardware features reach a turning point [2], searcha “search in local ,” namely, they would like to access an en-service providers are now turning their attention to improv-

tire database of a search provider, and choose the information

ing the search experience of users. One important aspect of

they need. However, search providers hold their databases asuser satisfaction regarding a search is whether the private

important assets, and do not want users to have full access.

information of the users is carefully protected and only used

Instead, they only want to show users a small portion [5].

for query-related purposes. Security issues in many global

A dilemma occurs between protecting the privacy of usersand “database’s privacy.” Thus, as a compromise, searcha ciphertext in FHE.

providers allow users to encrypt their query contents. How-

The idea of homomorphic encryption (HE) was first in-ever, this can only protect user data from leakage during a

troduced in 1978 by Rivest el al. [8]. In 2009, Gentry intro-

transfer. Search providers, however, hold a secret key that

duced a practical scheme for FHE implementation on arbi-

still can decrypt the contents of a user query. The contents

trary functions and a number of operations using an idealof user queries remain under the threat of leakage or mis-lattice [9]. In 2012, Brakerski, Gentry, and Vaikuntanathan

use. A third party having access to the database of a search

introduced the BGV scheme using ring-learning with errors

provider, e.g., a cloud server provider, can access the contents(RLWE) [10]. In 2010, Smart and Vercauteren introducedof a user query in decrypted form. In addition, untrustwor-

there SV packing technique to FHE and enabled a single

thy search providers may use such contents in ways other

instruction/multiple data (SIMD) style operation to real-

than the intended query, e.g., selling the query history of theize a speed-up and compression [11]. IBM Research released

users to a third party.

an open-source library of HElib based on the BGV scheme,

In Japan, which is a quickly aging society [6], medical carewhich is one of the most popular FHE libraries available [12].

is an important topic. According to oﬃcial data [7], over

Herein, we briefly introduce the FHE scheme and SV pack-3.5 million elderly people over 65 years in age receive out-ing.

patient treatment each year, and more than 0.9 million re-

2. 2 FHE scheme

ceived hospitalization treatment in 2014. When patients suf-

In the FHE scheme, the following algorithms are included

fer from side eﬀects from a particular medicine, they usually[10]:

ask pharmacists for help. Although referring to the attached•documentation of a medicine is a way to find the potential
ingredient causing a side eﬀect, situations exist in which theattached documentation is insuﬃciently comprehensive. Asa supplementary empirical method, pharmacists may referto the medicinal history of other patients and find similar
situations, i.e., patients with the same gender, a similar age,
and who are taking at least one similar medicine and are

put a set of parameters for encryption, params.
•

F HE.KeyGen(params):

Generate a public/secret

key pair, pk/sk, and evaluation key, ek.
•

F HE.Enc(pk, m): Given a public key pk and plain-text message m, output the corresponding ciphertext, c.
•

F HE.Dec(sk, c): Given a secret key sk and ciphertext

c, output the corresponding plaintext message, m.
•

suﬀering from at least one similar symptom.

F HE.SetU p(1λ ): Given a security parameter λ, out-

F HE.Eval(ek, f, (c1 , ..., ct )):Given evaluation key

It is the responsibility of pharmacies to protect the medici-ek, an arithmetic circuit f that accepts t parameters, andnal history of their customers from a third party because sucht ciphertext c1 to ct , output a ciphertext as an encrypted

information is private and sensitive. Our goal is to develop

calculation result, cf .

a scheme to ensure that the queried data and full medicinal

2. 3 SV packing and SIMD-style calculation

history of the patient remain safe during the entire queryIn [13], Smart and Vercauteren introduced a packing

process. In this paper, we first introduce basic knowledge

method that allows encrypting a vector of plaintext into a

related with fully homomorphic encryption (FHE), followed

single ciphertext. These multiple plaintexts are stored sepa-

by a brief review of related studies. We then describe ourrately in spaces called slots. The authors introduced a SIMD-

system using detailed algorithms, and show the experimentstyle operation on the packed ciphertext. In a SIMD-style

results.

FHE calculation on ciphertexts, operations such as additions
and multiplications are conducted in a slot-wise manner. In

2 Preliminaries

our system, all operations over a ciphertext are applied in a

2. 1 Fully homomorphic encryption (FHE)SIMD manner.

Under traditional encryption methods, decryption must be
performed prior to the calculations. Direct calculations over

3 Related works

a ciphertext are not supported. However, fully homomorphic

A private information retrieval (PIR) scheme was first in-encryption (FHE) supports an arbitrary number of additions

troduced by Chor et al. in 1995 [14]. Kushilevitz and Ostro-and multiplications directly over a ciphertext.

vsky constructed the first single-database PIR in 1997 [15].

F HE.Dec(F HE.Enc(a) ⊕ F HE.Enc(b)) = a + b
F HE.Dec(F HE.Enc(a) ⊗ F HE.Enc(b)) = a × b

Since then, PIR has become one of the most important cryp(1)tography schemes available [16].
The original work by Kushilevitz and Ostrovsky [15] has

In (1), a, b ∈ Z, F HE.Dec and F HE.Enc are methods usedalready resulted in the introduction of a PIR protocol uponin FHE, and ⊕ and ⊗ are additions and multiplications overhomomorphic encryption. Based on Gentry’s improvement

of homomorphic encryption [9], the implementation of PIR
based on the HE scheme has become a reality [17], [18]. A
set of implementations of PIR using the HE scheme proved
its usefulness in various fields including cloud computing [19],chemical compound management [5], data aggregation [20],and e-voting [21]. However, the schemes applied in thesestudies are not suitable for use in our system. [20] and [5]use additional homomorphic encryption (AHE), whereas [19]uses BGN homomorphic encryption and [21] uses ElGamal
homomorphic encryption, which diﬀer from FHE. Thesemethods are eﬀective for specific types of arithmetic circuits,
but they are not suitable for our situation, in which a cipherFigure 1 Relation between participants

text and plaintext are contained inside query content at thesame time. Based on [18], because FHE is theoretically suitable for any arbitrary arithmetic circuit, we consider it to bea more suitable way to solve our problem. In [22], Dong etal. introduced a general PIR scheme using FHE, although
there is still space for optimization for our specific problem.

4. 2. 2 Privacy
With our system, we plan to use PIR on FHE over thefull medicinal history database of patients. A key pair waspreviously generated and distributed to each participant, asshown in Figure 1. The key pair pk/sk is used for a cer-

4 Proposed method
4. 1 GoalOur goal is to provide a privacy-preserving scheme to extract information that can support pharmacists in finding thereason for the occurrence of side eﬀects based on the medicinal history of the patient. To be specific, we need recordsof patients with the following conditions for a comparison of
the query content:•

Gender: same•

Age: R years younger – R years older, R ∈ Z•

Medicine: At least one the same•

Side Eﬀect: At least one the same

Sensitive information includes the gender and age information of the patients, as well as other private information.
Such information must be kept encrypted during the entire
query process.
4. 2 System
4. 2. 1 Overview
For a simple description, we assume that we have only
three participants in our model: the cloud, server, and terminal device. Here, the cloud is an untrustworthy cloud server
conducting FHE calculations, provided by third-party cloudservice providers, which holds the medicinal history databaseof encrypted users; the server represents the branch servers
stored in each branch of a pharmacy, which are considered
to be trustworthy; and the terminal device represents untrustworthy user devices that send a query, i.e., tablet PCs,
which are assumed to be used by pharmacists when they interact with patients. Relations between these participants
are shown in Figure 1.

tain time period (e.g., a month) and renewed periodically. If
there are multiple users, they will share the same sk.
Each party only has access to certain content. With oursystem, the server has access to the key pair pk/sk and evaluation key ek; the terminal device has access to plaintext
query content m, a public key pk, and an evaluation key ek;
and cloud has access to the ciphertext database Enc(db),public key pk, and evaluation key ek.
Plaintext content m only exists inside the terminal device,
and db is not accessible to any party, ensuring the privacy of
the user’s query and database.
4. 2. 3 Procedure
Before a query, the following preparation steps are conducted. In step 1, the parameters for the encryption environment are prepared using the server.

In step 2, thedatabase holder prepares a fully encrypted database Enc(db)and sends it to the cloud.
（ 1 ） step 1: server generate a public/secret key pair

pk/sk, and evaluation key ek, and share pk and ek withthe cloud and terminal device sides.
（ 2 ） step 2: cloud receive the entire encrypted database

Enc(db) oﬀered by the database holder using pk for encryption.
During the search process, the following steps are conducted. In step 1, terminal device prepares the encrypted
query content, which is also shown in Algorithm 1. In step 2,
a comparison of m and db is conducted using SIMD subtraction, and slots with zero as the subtraction result points tothe query result. To make sure the contents of the non-zeroslots are not recovered, the subtraction result is multipliedwith a non-zero random integer r. This is described in Algo-rithm 4. In steps 3 to 5, the server decrypts the result, finds

from the server prepared using Algorithm 1. Herein, we use

the zeros, and reports their index to the cloud, whereas them′ as the grouped parameters from gender and age, combin-

cloud extracts these records accordingly, as shown in Algo-ing the FHE-related parameters into only a single parameter.

rithm 5.

This grouping is supported according to [25], provided that

（ 1 ） step 1: terminal device encrypt the query content

each possible pair of (age, gender) for humans will map to am using pk, and send the encrypted query content Enc(m)unique m′ within [0, 255], when the upper limit of the age dif-to the server side. Then, server send this information to theference is R ⩽ 5. Males are mapped to [0, 127], and females

cloud side.

are mapped to [128, 255].

（ 2 ） step 2: cloud perform a SIMD-style subtraction be-

tween Enc(m) and Enc(db), and then multiply the subtrac-

Algorithm 1 QueryGen
Input age, (M ed1 , ..., M edn ), (Side1 , ..., Sidem )tion result with a non-zero random integer r. Then, cloud
send the resulting ciphertext (Enc(m) ⊖ Enc(db)) ⊗ r toserver.

Output query
1: if gender is male then2:（ 3 ） step 3: server use sk to decrypt the resulting cipher-m′ ← age + R

3: elsem′ ← age + 128 + R

text (Enc(m)⊖Enc(db))⊗r to gain the plaintext (m−db)×r.

4:

server then search for slots with zeros, and gather the index

5: end ifof these slots. server then share the index with the cloud

6: c ← F HE.Enc(pk, m′ )side.

7: query ← c, (M ed1 , ..., M edn ), (Side1 , ..., Sidem )（ 4 ） step 4: cloud refer to Enc(db) according to indexes,

access these parts and pack them as Enc(db′ ), then, send

After receiving the query contents c, (M ed1 , ..., M edn ),them to the server side.

(Side1 , ..., Sidem ) from the server, cloud is initiated to apply（ 5 ） step 5: server use sk to decrypt Enc(db′ ) to gain

filtering with an inverted index of the medicine InvM ed and′plaintext db , and share them with the terminal device side.

side eﬀect InvSide, and a smaller part is extracted from db
for the FHE calculation. The classical pyramidal merge al-

4. 3 Optimization

gorithm used in mergesort [26] will be operated over inverted

Query content m contains the following four types of data:indexes, making a smaller encrypted database Enc(db′ ) ofage, gender, list of medicines, and list of side eﬀects. Here,

size s for the FHE calculation. The filtering is shown in Al-

we encrypt only age and gender to avoid a privacy leakage.

gorithm 2. With this algorithm, Intersect(List) takes the

The lists of medicines and side eﬀects are handled in plain-intersection of several sets, and U nion(List) takes the union

text format. Note that all data, mainly, the encrypted age,of several sets.

encrypted gender, and the other two plaintexts, are transferred over encrypted channels, such as AES, to keep them

Algorithm 2 Filter
Input (M ed1 , ..., M edn ), (Side1 , ..., Sidem )secured during their transfer. We separate m into two parts:•

FHE-encrypted part: age and gender•

non FHE-encrypted part: lists of medicines and side

eﬀectsBecause the lists of medicines and side eﬀects are not en-

Output Enc(db′ )1: M ergeListM ed ← []2: for i ← 1 to n do
3:

calculation, reducing the size of the database for calculation
purposes. We apply the inverted index method commonlyused in search engines to conduct the filtering step [23], as

5: ResM ed ← Intersect(M ergeListM ed)
6: M ergeListSide ← []7: for i ← 1 to m do
8:

we use an NTL threading pool [24] in the cloud side when
conducting the FHE calculations. In addition, as shown in
Algorithm 3, SV packing is used.
4. 4 Algorithm
The implementation of the cloud side contains the mainpart of our scheme. The cloud will receive query content

M ergeListSide.Append(InvSide[Sidei ])9: end forshown in Algorithm 2.
Because the cloud is equipped with multiple CPU cores,▷ M ergeListM ed stores inverted indeces for

inputted medicines

crypted by the FHE, the cloud contains them in plaintext.
Thus, we can apply a filtering at the cloud before the FHE

M ergeListM ed.Append(InvM ed[M edi ])4: end for▷ M ergeListM ed stores inverted indeces for

inputted side eﬀects
10: ResSide ← Intersect(M ergeListSide)
11: Res ← U nion([ResM ed, ResSide])IDs
12: Enc(db′ ) ← []13: for i in Res do
14:

Enc(db′ ).Append(Enc(db)[i])15: end for▷ Res is a list of record

Because we use the SIMD method for calculation, we use

Algorithm 5 Decrypta HElib EncrypedArray class to pack a vector of ciphertext

Input Enc(res)Enc(db′ ) into a single ciphertext P ackDB. This is shown in

Output query result

Algorithm 3.

1: res ← F HE.Dec(pk, Enc(res))

Algorithm 3 SVPack

3:

Input Enc(db′ )4:

2: for item in res do

Output P ackDB

decrypt the responded additional information and send5:

it to the terminal device

2: for i ← 1 to s do4:

request additional information related with the index
of item from cloud

1: P ackDB ← Enc(pk, 0)

3:

if item is 0 thenend ifl ← all-zero integer list of size s6:l[i] ← 1 ▷ l act as a position indicator showing which slot

7: end forto insert
5:

P ackDB ← P ackDB ⊕ l ⊗ Enc(db′ )[i]6: end for

The cloud was equipped with 28 virtual CPUs and 256 GBof memory. To make full use of the system, the maximum
thread for the NTL threading pool was set as 28. In addi-

We can then conduct a calculation using FHE. The matching result should have the same gender as m and at an age

tion, R was set as 5. The FHE parameters used in HElib
were set as shown in Table 1.

diﬀerence within R with the age information of m; hence,
Table 1 HElib parameters

the target value should be in [m − R, m + R] inside the orig-minal partial database db′ . After the SIMD subtraction of

p

r

L

12,097 257 1 11

P ackDB and c, we need to add it with [−R, +R] and obtain
2R + 1 ciphertexts M etaRes. We can SIMD multiply these2R + 1 ciphertexts into one ciphertext Enc(res) and send it

5. 2 Simulation dataset

back to the server for decryption, as shown in Algorithm 4.

We prepared the simulation dataset based on statisticaldata.

We referred to oﬃcial data oﬀered by the Japan

Algorithm 4 FHECalculate

Ministry of Health, Labor, and Welfare [7], and by Statis-

Input P ackDB, c, R

tics Japan [25]. From the statistical data, we gained the

Output Enc(res)patient distribution over the diﬀerent age periods and gen-

1: M etaRes ← []ders. In addition, we assumed 2,000 types of medicines and

2: for i ← −R to + R do
3:

M etaRes.Append(P ackDB ⊖ c ⊕ i)

4: end for▷ M etaRes stores 2R + 1 ciphertexts

100 types of side eﬀects, distributed according to a Pareto
distribution [27]. We arbitrarily assumed that each patient

5: while len(M etaRes) > 1 dotakes fewer than 20 diﬀerent medicines and suﬀers from fewer

6:

i ← 1, j ← len(M etaRes)

than five side eﬀects. According to these rules, we created a7:

while i < j dodataset with a size of 40,000.

8:

M etaRes[i] ← M etaRes[i] ⊗ M etaRes[j]9:M etaRes.Remove(M etaRes[j])10:i+ = 1, j− = 1

11:

We conducted 10,000 uniformly random queries based ona random age, gender, list of medicines, and list of side ef-

end while

12: end while

5. 3 Result▷ Calculate product of sequences

13: Enc(res) ← M etaRes[1] ⊗ random()

fects between the server and cloud. The relation between
the filtered data size and the query processing time is shownin Figures 2 and 3. The distribution of the filtering percent-

After receiving ciphertext Enc(res), the server will apply
a decryption and request additional information, e.g., pharmacy instructions, as shown by Algorithm 5.

5 Experiment and result
5. 1 Experiment
We implemented the scheme in C++ using HElib. We set
up our server on a desktop PC and the cloud on a cloudcomputing platform provided by Nifty Cloud. The server
was equipped with an 8-core CPU and 16 GB of memory.

age, i.e., the percentage of filtered database size based on theoriginal database size is shown in Table 2.
From Figure 2 and Table 2, we can see that filtering is eﬀective in scaling down the database size. In 98.36% of all cases,
the database was scaled down to less than 400 items, which
is only 1% of the original database size. Using filtering, FHE
calculations over the full database are not required, whichsaves time and memory. From Figure 3, we can observe an
improvement through multithreading. We set 100 as the slot
number in a single ciphertext in our experiment. Thus, inmodel is capable of conducting a search for the side eﬀects
of a medicine.
A filtering application using an inverted index and multithreading was successful in decreasing the time and memoryuse. From the results of Table 2, we can see that, in mostcases, only less than 1% of the database needed to be usedin the calculation. If such filtering is not applied, a FHE
calculation must be performed over a full database, resulting in a waste of both time and memory. From Figure 3,
we can see that the server calculations require the greatest
amount of time for a filtered database size s of less than500. At greater than 500, the communication time, however,
Figure 2 Relation between time consumption and filtereddatabase size in 10,000 experiments

becomes the most time-consuming part. We introduced an
NTL threading pool in the server calculations. When s isless than 100, the process is the same as with a single thread,and the server calculation time rapidly increases. When s isgreater than 100, multithreading is applied, and the increasein the calculation time becomes much slower.

7 Conclusion
We proposed a scheme for a privacy-preserving query system, and implemented it into a real-world case. We proved
the usefulness of the scheme through experiments conducted
on real datasets. For future optimization, we can see that thecommunication time contributes significantly to the overallsession time when the filtered database size is large. This isunderstandable because the size of Enc(res) is proportional
Figure 3 A closer view when filtered down to a dataset of 2.00%

to filtered database size s. To reduce this heavy time con-Table 2 Distribution of Filter Percentage

sumption, we can consider packing more slots into a single

Filter Percentage Percentage for a Total of 10,000 Attempts

ciphertext. However, this requires that we adjust the param-

0%60.52%

0%-1%

37.84%

1%-2%

0.57%

2%-5%

0.56%

5%-10%

0.22%

10%-20%0.16%

20%-50%

0.10%

>50%

0.03%

Figure 3, the server calculation time, which was originallyconsidered the most time-consuming, increases much more
slowly after the filtered database size s reaches 100. As ageneral result, 99.71% of all queries completed the entire process, i.e., from the completed collection of m at the terminal
device to the complete output, within 60 s.
The maximum memory usage is approximately 2.48 GB.

6 Discussion
The results of our experiment conducted on a simulation dataset show that our privacy-preserving query system

eters to obtain a larger packing capacity.

Acknowledgment
This work was supported by JST CREST, Grant Number
JPMJCR1503, Japan.

References[1] Lars Kotthoﬀ. Algorithm selection for combinatorial search
problems: A survey. In Data Mining and Constraint Programming, pages 149–190. Springer, 2016.
[2] Hassan N Khan, David A Hounshell, and Erica RH Fuchs.
Science and research policy at the end of moore s law. Nature Electronics, 1(1):14, 2018.
[3] Phee Waterfield and Timothy Revell. Huge new facebook
data leak exposed intimate details of 3m users. New Scientist, URL: https://www.newscientist.com/article/mg238317
82-100-huge-new-facebook-data-leak-exposed-intimate-detailsof-3m-users, May 2018. Accessed: 2019-01-05.
[4] Julia Carrie Wong and Olivia Solon. Google to shut
down google+ after failing to disclose user data leak. The
Guardian, URL: https://www.theguardian.com/technology/
2018/oct/08/google-plus-security-breach-wall-street-journal,
Oct 2018. Accessed: 2019-01-05.
[5] Kana Shimizu, Koji Nuida, Hiromi Arai, Shigeo Mitsunari,

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

Nuttapong Attrapadung, Michiaki Hamada, Koji Tsuda,
Takatsugu Hirokawa, Jun Sakuma, Goichiro Hanaoka,
et al. Privacy-preserving search for chemical compound
databases. BMC bioinformatics, 16(18):S6, 2015.
Naoko Muramatsu and Hiroko Akiyama. Japan: superaging society preparing for the future. The Gerontologist,
51(4):425–432, 2011.
大 臣 官 房 統 計 情 報 部. 平 成 26 年 (2014) 患 者 調 査 の 概 況.
https://www.mhlw.go.jp/toukei/saikin/hw/kanja/14/, Dec
2015.
Ronald L Rivest, Len Adleman, and Michael L Dertouzos.
On data banks and privacy homomorphisms. Foundationsof secure computation, 4(11):169–180, 1978.
Craig Gentry. Fully homomorphic encryption using ideal
lattices. In Proceedings of the 41st annual ACM symposium
on Symposium on theory of computing-STOC\’09, pages
169–169. ACM Press, 2009.
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan.
(leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory (TOCT),
6(3):13, 2014.
Nigel P Smart and Frederik Vercauteren. Fully homomorphic encryption with relatively small key and ciphertext
sizes. In International Workshop on Public Key Cryptography, pages 420–443. Springer, 2010.
Shai Halevi and Victor Shoup. Algorithms in helib. In 34rd
Annual International Cryptology Conference, CRYPTO
2014. Springer Verlag, 2014.
Nigel P Smart and Frederik Vercauteren. Fully homomorphic simd operations. Designs, codes and cryptography,
71(1):57–81, 2014.
Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu
Sudan. Private information retrieval. In Foundations ofComputer Science, 1995. Proceedings., 36th Annual Symposium on, pages 41–50. IEEE, 1995.
Eyal Kushilevitz and Rafail Ostrovsky. Replication is notneeded: Single database, computationally-private information retrieval. In Foundations of Computer Science, 1997.
Proceedings., 38th Annual Symposium on, pages 364–373.
IEEE, 1997.
Rafail Ostrovsky and William E Skeith. A survey of singledatabase private information retrieval: Techniques and applications. In International Workshop on Public Key Cryptography, pages 393–411. Springer, 2007.
Vinod Vaikuntanathan. Computing blindfolded: New developments in fully homomorphic encryption. In Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, pages 5–16. IEEE, 2011.
Xun Yi, Mohammed Golam Kaosar, Russell Paulet, andElisa Bertino. Single-database private information retrieval
from fully homomorphic encryption. IEEE Transactions on
Knowledge and Data Engineering, 25(5):1125–1134, 2013.
Yang HaiBin and Zhang Ling. A secure private information retrieval in cloud environment. In Intelligent Networking and Collaborative Systems (INCoS), 2016 International
Conference on, pages 388–391. IEEE, 2016.
Tsotsope Daniel Ramotsoela et al. Data aggregation usinghomomorphic encryption in wireless sensor networks. PhD
thesis, University of Pretoria, 2015.
Shubhangi S Shinde, Sonali Shukla, and DK Chitre. Secure e-voting using homomorphic technology. International
Journal of Emerging Technology and Advanced Engineering, 3(8):203–206, 2013.
Changyu Dong and Liqun Chen. A fast single server private information retrieval protocol with low communication
cost. In European Symposium on Research in Computer
Security, pages 380–399. Springer, 2014.
Justin Zobel, Alistair Moﬀat, and Kotagiri Ramamoha-

[24]
[25]
[26]
[27]

narao. Inverted files versus signature files for text indexing. ACM Transactions on Database Systems (TODS),
23(4):453–490, 1998.
Victor Shoup. Ntl: A library for doing number theory.
http://www.shoup.net/ntl/, 2001.
総務省. 日本の統計: 2018. 日本統計協会, 2018.
Richard Cole. Parallel merge sort. SIAM Journal on Computing, 17(4):770–785, 1988.
Tudor I Oprea. Property distribution of drug-related chemical databases. Journal of computer-aided molecular design,
14(3):251–264, 2000.