DEIM Forum 2019 I5-5

Function Evaluation with Fully Homomorphic Encryption using
Table Lookup
Ruixiao LI †, Yu ISHIMAKI ‡, Hayato YAMANA*†School of Fundamental Science and Engineering, Waseda University 3-4-1 Okubo, Shinjuku-ku, Tokyo,169-8555, Japan.
‡Graduate School of Fundamental Science and Engineering, Waseda University 3-4-1 Okubo, Shinjukuku, Tokyo, 169-8555 Japan*Faculty of Science and Engineering, Waseda University 3-4-1 Okubo, Shinjuku-ku, Tokyo, 169-8555
Japan
Email: {liruixiao, yuishi, yamana}@yama.info.waseda.ac.jp
Abstract: Fully homomorphic encryption (FHE) allows a third party to evaluate arithmetic circuits over encrypted
data without decryption. However, FHE typically only supports addition and multiplication over encrypted data.
Thus, functions that cannot be directly represented using additions or multiplications (such as reciprocals andlogarithms) are not compatible with FHE. To overcome this limitation, Crawford et al. (WAHC 2018) proposeda method of evaluating such functions using a lookup table (LUT). While this approach provides the ability toevaluate any functions using FHE, two problems arise. First, it uses bitwise encoding, i.e., an integer isdecomposed into a set of bits, and then each bit is encrypted individually, which typically results in a large
overhead in terms of both computational and storage costs. Second, the size of the LUT can be huge, dependingon the function to be evaluated, as all possible pairs of input and output values of the function must be included.
This necessitates an expensive computation for LUT evaluation with FHE. In this study, we propose a more
efficient function evaluation protocol with FHE than the method of Crawford et al. Our protocol allows the useof integer encoding, i.e., a single integer is encrypted as a single ciphertext, rather than using bitwise encoding.
In addition, our protocol guarantees that no information on the underlying plaintext between two parties can beleaked, via a combination of permutation operations and private information retrieval. Our experimental results
in a multi-threaded environment show that the runtime of our protocol is approximately 51 s when the size of the
LUT is 448,000. Thus, we surmise that our protocol is more practical.
Keyword: Function Evaluation, Lookup Table, Fully Homomorphic Encryption, Cloud Computing, Private
Information Retrieval

1.INTRODUCTION
Nowadays, cloud computing services and big datatechniques are proliferating rapidly. With the widespread
adoption of big data technology, data security issues havereceived increasing attention. The existence of
information uploaded by large numbers of users, stored incloud servers, increases data security risks [1][2]. Several
mature traditional encryption schemes are available, suchas AES and DES. However, once data has been encrypted,
operations cannot be performed on it without decryption.
In 2009, a fully homomorphic encryption (FHE) scheme
was introduced by Gentry [3], which allows a third party
to perform function evaluations over encrypted data
without decryption. However, the limitations of FHE,
such as 1) only allowing the evaluation of functions
composed of additions and multiplications and 2) its large
computational cost and memory usage, make it difficult toadapt to big data.
The previous study [4] by Crawford et al. replaces
function evaluation with a lookup table (LUT) protocol for
FHE. This enables the evaluation of some complex
functions using FHE, such as reciprocals and logarithms.
However, two problems remain in their approach: 1) they
employ bitwise encoding, which is not scalable; and 2) the
LUT must include all possible input values, meaning thatit can be huge, increasing the evaluation time. In this study,
our protocol adopts integer encoding rather than bitwise
encoding. We generate two LUT matrices, where eachrow in an LUT matrix includes only some of values, tospeed up the evaluation. This approach is implemented

with a two-party protocol, consisting of a server and adecryptor, where the latter owns a decryption key toevaluate complex functions such as reciprocals andlogarithms. Although decryption is required on theencrypted data, our protocol guarantees that no
information on the underlying plaintext can be leaked, by
combining permutation operations with private
information retrieval (PIR) [5]. The query generation
method is based on our previous work [6]. In addition, asimilar procedure is performed in every row in an LUT
matrix, so that multi-thread operations can be adopted for
all rows to further reduce the evaluation time.
This remainder of this paper is organized as follows. In
Section 2, we describe FHE, BGV cryptosystems, single
instruction multiple data (SIMD)-style operations, andPIR from a single database. In Section 3, related work is
discussed. In Section 4, our proposed model and overall
protocol for two parties is described. In Sections 5 and 6,
a security analysis, experimental results, and an evaluation
are presented. Finally, in Section 7 we conclude the paper.

2. PRELIMINARIES
2.1 FULLY HOMOMORPHIC ENCRYPTIONFHE is an encryption scheme that allows a third party toevaluate arbitrary functions using modular arithmetic(mod 𝑝) over encrypted data without decryption.
When 𝑝 = 2, a number is encoded into a binary string.
This is introduced in, e.g., the GSW scheme (Gentry et al.
[7]), which can encrypt each bit as ciphertext. Using logiccircuit AND and XOR operations, any function can be

1DEIM Forum 2019 I5-5

evaluated. However, this approach involves a large
ciphertext:plaintext ratio.
When 𝑝 > 2, a number is encoded into an integer. ThisFHE operation is introduced in, e.g., the BGV scheme(Brakerski et al. [8]), which can encrypt a large integer asa single ciphertext. Thus, the integer circuit has a better
ciphertext:plaintext ratio, which means that more data canbe processed with one operation. Using polynomial
approximations, a function consisting only of additions
and multiplications can be evaluated. However, thisapproach has some restrictions in terms of functionality,
in that functions that cannot be directly represented using
additions and multiplications (such as reciprocals andlogarithms) are not compatible with FHE. Thus, it is ideal
to apply an integer circuit for the evaluation of any
function.
A. BGV CRYPTOSYSTEM
In this section, we describe the following four mainalgorithms in the BGV scheme.
1. Setup: 𝑝𝑎𝑟𝑎𝑚𝑠 ← FHE. Setup (15 ,16 )Input the security parameter 𝜆 and number of levels L,
output a set of parameters 𝑝𝑎𝑟𝑎𝑚𝑠.
2. Key Generation:(𝑝𝑘, 𝑠𝑘) ← FHE. SecretKeyGen(𝑝𝑎𝑟𝑎𝑚𝑠)
Input the set of parameters, generate a pair of keys: public
key 𝑝𝑘 and secret key 𝑠𝑘.
3. Encryption: 𝑐 ← FHE. Enc(𝑝𝑘, 𝑚)
Input the public key, encrypt a message 𝑚 as a ciphertext𝑐.
4. Decryption: 𝑚 ← FHE. Dec(𝑠𝑘, 𝑐)
Input the secret key, decrypt a ciphertext 𝑐 as a message𝑚.
B. SIMD-STYLE OPERATIONSIn [9], Smart and Vercauteren introduced a type of
ciphertext packing technique based on the Chinese
reminder theorem (CRT), which can support SIMD-styleoperations. In their work [9], a CRT-represented
ciphertext generated from 𝑙 plaintexts can be considered
as a vector consisting of 𝑙 slots, each of which contains
one plaintext. The SIMD-style operations over the CRTrepresented ciphertext are performed slot-wise in parallel.
For example, we denote two vectors of length 𝑙 by 𝒙 =[𝑥G , … , 𝑥I ] and 𝒚 = [𝑦G , … , 𝑦I ]. Using the packing method[9], we can pack all the elements of a vector into a single
ciphertext. Then, the slot-wise addition and multiplication
operations over a packed ciphertext can be respectively
expressed as follows:
𝐷𝑒𝑐(𝐸𝑛𝑐(𝒙) ⊞ 𝐸𝑛𝑐(𝒚)) = [(𝑥G + 𝑦G ), … , (𝑥I + 𝑦I )]𝐷𝑒𝑐(𝐸𝑛𝑐(𝒙) ⊡ 𝐸𝑛𝑐(𝒚)) = [(𝑥G × 𝑦G ), … , (𝑥I × 𝑦I )]2.3 SINGLE DATABASE PIR FROM FHE
The PIR protocol [5] allows a user to retrieve a record
from a database server without letting the server learn
which element is selected by the user.
Aguilar et al. [10] introduced a PIR scheme with a querycompression technique called XPIR. Here, a PIR query inthis work includes 𝑛 ciphertexts, where 𝑛 is the number of
elements in the database. To reduce the size of a query andincrease the efficiency, Angel et al. [11] proposed SealPIR,
which reduces the number of queries, i.e., ciphertexts, toone, a via new query encoding method.

The basic idea of PIR with homomorphic encryption is
to assume a vector 𝒗 of length 𝑛, where 𝑛 is the numberof elements in the database. A user has the index 𝑡 thatthey would like to access. The user creates a binary vector
𝒒 of length 𝑛 as a query. The element whose index is 𝑡 in
the query is 1, and other elements are 0. Using the packing
method in [9], the user encrypts 𝒒 into a ciphertext andthen sends it to the database. The database responds to theuser with the result 𝐸𝑛𝑐(𝒗𝑹 ) = 𝐸𝑛𝑐(𝒗) ⊡ 𝐸𝑛𝑐(𝒒). The
result 𝒗𝑹 only contains the element with the index 𝑡 in the
database. After decryption, the user can retrieve 𝑣Z fromthe database as desired. (Fig. 2-3)

Fig. 2-3 AN EXAMPLE OF PIR FROM FHE

3. RELATED WORK
It is difficult to evaluate certain functions with FHE, suchas reciprocals and logarithms. Crawford et al. [4] proposedcomputing “complicated functions” using table lookup.
When a function is difficult to evaluate, one can look up atable that includes all possible input values andcorresponding output values, which have already been
calculated. Using this solution, they implemented a lowprecision approximation method for complex functions. A
function 𝑓 to be computed is pre-computed in a table 𝑇] ,such that 𝑇] [𝑥] = 𝑓(𝑥) for every x in some range. Then,
given the encryptions of the bits of x, homomorphic tablelookup is performed to obtain the bits of the value 𝑇] [𝑥].
Two problems remain in this approach. First, bitwise
encoding is employed, which is not scalable. Second, an
LUT must include all possible input values, meaning thatit may be huge, increasing the evaluation time. Fig. 3-1

presents an example of this approach.

Fig. 3-1 EXAMPLE OF BITWISE TABLE LOOKUP

4. FUNCTION EVALUATION WITH FHE USINGTABLE LOOKUP
There are two fundamental factors that appear to limit theapplication of FHE to cloud computing services: 1) FHE
with integer encoding can only evaluate functions
composed of additions and multiplications, and 2) it
requires a large computational cost and memory usage. To
solve the first problem, we adopt LUTs to evaluate
functions such as reciprocals and logarithms. To reducethe computational cost, we construct an LUT matrix thatcan be adopted for multi-thread operations.
4.1 PROPOSED MODEL
Our proposed LUT evaluation method relies on a twoparty protocol, which consists of a computation server (CS)and a decryptor. Here, we suppose that a complex function
𝑓 is evaluated at the CS, based on an encryption of 𝑥
denoted by Enc(𝑥) . Namely, the CS aims to evaluate2

DEIM Forum 2019 I5-5
Enc(𝑓(𝑥)) , which is difficult to evaluate using anarithmetic circuit over FHE. For this propose, thedecryptor is required to transform x into a PIR query. The
input 𝑥 and output 𝑓(𝑥) are private information in thisprotocol, which cannot be known by the CS or decryptor.
In the initialization phase, the decryptor generates a pairof keys: a public key and secret key. The decryptor sends
the public key to the CS, and owns the secret key. Enc(𝑥)is the input of the CS, and Enc(𝑓(𝑥)) is an output that canbe used for other evaluations in the CS. For example, in arecommender system [12] [13], the cosine distance needs
to be computed, which requires a square root operation.
This is difficult to evaluate over FHE, because FHE only
supports addition and multiplication. The input of thesquare root operation is a computational result. Fig. 4-1
presents an example. The function is 𝑓(𝑥) = √𝑥 . The
input of the square root operation is a computational result
𝐸𝑛𝑐(𝑥) = 𝐸𝑛𝑐(𝑥` ) ⊞ … ⊞ 𝐸𝑛𝑐(𝑥a ) ⊞ … ⊞ 𝐸𝑛𝑐(𝑥b ) .
Here, 𝐸𝑛𝑐(𝑥a ) comes from user 𝑖, and 𝐸𝑛𝑐(𝑥) includes
sensitive information for 𝑛 users.

values from the original LUT, where 𝑛 is the number of
elements. The vector 𝒗𝒐𝒖𝒕 ∈ ℤb holds all output values
from the original LUT. The CS constructs two new LUT
matrices 𝑇ab , 𝑇deZ ∈ ℤm×I , where 𝑘 is the number of rows
and 𝑙 is the number of columns (which is the same as thenumber of slots). We define 𝑘 = ⌈𝑛/𝑙⌉ ∈ ℤ , |𝑇ab | =𝑘 × 𝑙 ≥ |𝒗𝒊𝒏 | = 𝑛 and |𝑇deZ | = 𝑘 × 𝑙 ≥ |𝒗𝒐𝒖𝒕 | = 𝑛 . Let𝒗 be a permutation vector that holds various random
values within the integer range [0, 𝑛 − 1].
Fig. 4-3 shows an example of lookup table construction.
The input and output integer values in the original LUT
are stored as two vectors 𝒗𝒊𝒏 , 𝒗𝒐𝒖𝒕 of length 12. The new
LUT matrices are 𝑇ab , 𝑇deZ, with the number of slots 𝑙 = 4
and number of rows 𝑘 = ⌈𝑛/𝑙⌉ = ⌈12/4⌉ = 3 . 𝒗 is apermutation vector, which holds various random values in
the integer range [0,11]. For ease of understanding, we
add a permuted LUT vector in Fig. 4-3, which is divided
into three rows in an LUT matrix.

Fig. 4-3 EXAMPLE OF LOOKUP TABLE CONSTRUCTION

Fig. 4-1 AN EXAMPLE OF the PROPOSED MODEL
4.2 PROPOSED PROTOCOLThe overview of our protocol is as follows. 1) Construct
lookup table: The CS generates two new permuted LUT
matrices, based on a permutation vector generated by the
CS. This is performed for each encrypted input in our
protocol, and the two LUT matrices 𝑇ab , 𝑇deZ are known
and kept by the CS. The LUT matrix 𝑇ab holds all the input
values of the function 𝑓, and its output is in LUT matrix
𝑇deZ . 2) Search input value: The CS searches the input
over the LUT matrix 𝑇ab . The result after this step also
consists of ciphertext, which cannot be known by the CS.
To determine the index of the input in 𝑇ab and generate the
PIR query, the CS sends the result to the decryptor. 3)
Generate PIR query: Using one decryption, the decryptor
can obtain the index of the input in 𝑇ab , which is the sameas the output index in 𝑇deZ. Then, the decryptor generates
the encrypted PIR query and sends it to the CS. 4) Selectoutput value: The CS selects the output from 𝑇deZ with the
PIR query. Fig. 4-2 illustrates the overall protocol.
A. Construct Lookup Table
The LUT must include all input values of the function 𝑓and the corresponding output values. The original LUT
can be known by the CS and the decryptor. We denote theinput and output integer values in original LUT,
respectively, by two vectors 𝒗𝒊𝒏 , 𝒗𝒐𝒖𝒕 ∈ ℤb of length 𝑛.
The CS creates two new permuted LUT matrices 𝑇ab , 𝑇deZ
based on a permutation vector 𝒗 generated by the CS.
FHE allows us to encrypt a vector of integers of length 𝑙
as a single ciphertext. The vector 𝒗𝒊𝒏 ∈ ℤb holds all input

We represent how to construct the LUT matrices
𝑇ab , 𝑇deZ from the original LUT vectors 𝒗𝒊𝒏 , 𝒗𝒐𝒖𝒕 in
Algorithm 1.
Algorithm 1: Construct lookup table
Input. vectors 𝒗𝒊𝒏 , 𝒗𝒐𝒖𝒕 ∈ ℤb ; a permutation vector 𝒗 ∈ℤb .
Output. LUT matrices 𝑇ab , 𝑇deZ ∈ ℤm×I .
1: function LUTConstruction (𝒗𝒊𝒏 , 𝒗𝒐𝒖𝒕 , 𝒗)
2: 𝑠 ← 0
3: Fill all the elements in 𝑇ab and 𝑇deZ by zeros
4: for 𝑖 = 0 to 𝑘 − 1 do
5: for 𝑗 = 0 to 𝑙 − 1 do
6: 𝑖𝑛𝑑𝑒𝑥 ← 𝒗[𝑠]7: 𝑇ab [𝑖][𝑗] ← 𝒗𝒊𝒏 [𝑖𝑛𝑑𝑒𝑥]
8: 𝑇deZ [𝑖][𝑗] ← 𝒗𝒐𝒖𝒕 [𝑖𝑛𝑑𝑒𝑥]
9: 𝑠 ← 𝑠 + 1
10: end for
11: end for
12: return 𝑇ab , 𝑇deZ
13: end function
B. Search Input Value
The CS owns the LUT matrices 𝑇ab , 𝑇deZ. We denote theciphertext of a vector with elements 𝑥 as 𝑐. In addition, we
denote slot-wise addition and multiplication over FHE by⊞ and ⊡, respectively. For the 𝑖-th row in the matrix 𝑇ab ,by executing the operation 𝑐 ⊞ (−𝑇ab [𝑖]) we obtain the
result as a ciphertext 𝒗𝒄 [𝑖]. If the input value 𝑥 matches
the value at the index (𝑡zd{ , 𝑡|dI ) in 𝑇ab , the 𝒗𝒄 [𝑡zd{ ]encrypts a vector whose element at 𝑡|dI is zero. Because
the result 𝒗𝒄 , which will be sent to decryptor, is multipliedby the vector 𝒓𝒊 that contains all uniformly random
numbers in ℤ~ \{0} of length 𝑙, we can hide the true input

3

DEIM Forum 2019 I5-5

in the LUT matrix from the decryptor. We represent how
to search the input over 𝑇ab in Algorithm 2.
Algorithm 2: Search input value
Input. LUT matrix 𝑇ab ∈ ℤm×I ; input ciphertext 𝑐
Output. a vector of ciphertexts 𝒗𝒄 of length 𝑘
1: function InputSearch (𝑇ab , 𝑐)
2: for 𝑖 = 0 𝐭𝐨 𝑘 − 1 do
3: Sample a vector 𝒓𝒊 of uniformly random numbers
4: 𝒗𝒄 [𝑖] ← 𝑐 ⊞ (−𝑇ab [𝑖]) w𝑇ab [𝑖]: 𝑖-th row in 𝑇ab
5: 𝒗𝒄 [𝑖] ← 𝑣| [𝑖] ⊡ 𝒓𝒊 w𝒓𝒊 : a random numbers vector
6: end for7: return 𝒗𝒄
8: end function
C. Generate PIR Query
The decryptor receives the result, which is a vector of
ciphertexts 𝒗𝒄 of length 𝑘. First, the decryptor decrypts 𝒗𝒄
as a matrix 𝑉z…† . Then, the decryptor finds the index ofzero in 𝑉z…† . Because this protocol accepts a single input
value, which only matches one element of the LUT matrix
𝑇ab . Thus, after decryption there is also only one zero in𝑉z…† . We denote the index of the zero by (𝑡zd{ , 𝑡|dI ). We
know that the index (𝑡zd{ , 𝑡|dI ) represents the input andoutput index in the permuted LUT matrices 𝑇ab , 𝑇deZ. Here,we hide the index 𝑡|dI from the CS using a PIR query. To
hide the index 𝑡zd{ from the CS, we employ the query
generation method described in [6], which can reduce thenumber of PIR queries. The number of PIR queries is thesame as the number of dimensions 𝑑 = ⌈log I (𝑙 × 𝑘)⌉ in ad-dimensional hypercube representation. In this study, we
implemented both two-dimensional and two-dimensional
cases, which means that we can support 𝑛 up to 𝑙Š .
In the two-dimensional case, we generate two (to matchthe number of dimensions) queries 𝒒𝟎 and 𝒒𝟏 . The PIR
query 𝒒𝟎 is a vector whose 𝑡|dI -th element is 1, with otherelements 0. The query 𝒒𝟏 is a permuted vector that leftrotates 𝑡G = 𝑡zd{ elements from 𝒒𝟎 . For example, if
𝒒𝟎 = {0,0,1,0} and 𝑡G = 2 , then after left-rotating twoelements from 𝒒𝟎, we have that 𝒒𝟏 ={1,0,0,0}. If 𝑡G = 3,
then after left-rotating three elements from 𝒒𝟎 we havethat 𝒒𝟏 = {0,0,0,1}. In the three-dimensional case, we
generate three queries 𝒒𝟎 , 𝒒𝟏, and 𝒒𝟐. The PIR query 𝒒𝟎
is a vector whose 𝑡|dI -th element is 1, with other elements
0. The index 𝑡G = 𝑡zd{ 𝑚𝑜𝑑 𝑙, and 𝑡• = ⌊𝑡zd{ /𝑙• ⌋ 𝑚𝑜𝑑 𝑙.
The query 𝒒𝟏 is a permuted vector that left-rotates 𝑡G
elements from 𝒒𝟎. The query 𝒒𝟐 is a permuted vector thatleft-rotates 𝑡• elements from 𝒒𝟏.
The decryptor encrypts the queries, and then sends themto the CS. We represent how to generate PIR queries forthe two- and three-dimensional cases in Algorithm 3 andAlgorithm 4, respectively.
Algorithm 3: Generate PIR query for two-dimensional
case
Input. a vector of ciphertexts 𝒗𝒄 of length 𝑘
Output. two PIR queries 𝐸𝑛𝑐(𝒒𝟎 ) and 𝐸𝑛𝑐(𝒒𝟏 )1: function QueryGeneration (𝒗𝒄 )2: for 𝑖 = 0 to 𝑘 − 1 do
3: 𝑉z…† [𝑖] ← 𝐷𝑒𝑐(𝒗𝒄 [𝑖])wa matrix 𝑉z…†
4: end for
5: Fill all the element in 𝒒𝟎 by zeros
6: for 𝑖 = 0 to 𝑘 − 1 do
7: for 𝑗 = 0 to 𝑙 − 1 do
8: if 𝑉z…† [𝑖][𝑗] == 0 then
9: 𝑖𝑛𝑑 ← 𝑖
10: 𝒒𝟎 [𝑗] ← 1

11: end if
12: end for
13: end for
14: 𝑡G = 𝑖𝑛𝑑
15: 𝒒𝟏 = 𝒒𝟎 ≪ 𝑡G
wleft-rotate by 𝑡G -elements
16: return 𝐸𝑛𝑐(𝒒𝟎 ), 𝐸𝑛𝑐(𝒒𝟏 )17: end function
Algorithm 4: Generate PIR query for three-dimensional
case
Input. a vector of ciphertexts 𝒗𝒄 of length 𝑘
Output. three PIR queries 𝐸𝑛𝑐(𝒒𝟎 ), 𝐸𝑛𝑐(𝒒𝟏 ), 𝐸𝑛𝑐(𝒒𝟐 ).
1: function QueryGeneration (𝒗𝒄 )2: for 𝑖 = 0 to 𝑘 − 1 do
3: 𝑉z…† [𝑖] ← 𝐷𝑒𝑐(𝒗𝒄 [𝑖])wa matrix 𝑉z…†
4: end for
5: Fill all the element in 𝒒𝟎 by zeros
6: for 𝑖 = 0 to 𝑘 − 1 do
7: for 𝑗 = 0 to 𝑙 − 1 do
8: if 𝑉z…† [𝑖][𝑗] == 0 then
9: 𝑖𝑛𝑑 ← 𝑖
10: 𝒒𝟎 [𝑗] ← 1
11: end if
12: end for
13: end for
14: 𝑡G ← ⌊𝑖𝑛𝑑/𝑙⌋ 𝑚𝑜𝑑 𝑙
15: 𝑡• ← ⌊𝑖𝑛𝑑/𝑙• ⌋ 𝑚𝑜𝑑 𝑙
16: 𝒒𝟏 = 𝒒𝟎 ≪ 𝑡G
wleft-rotate by 𝑡G -elements
17: 𝒒𝟐 = 𝒒𝟏 ≪ 𝑡•wleft-rotate by 𝑡• -elements
18: return 𝐸𝑛𝑐(𝒒𝟎 ), 𝐸𝑛𝑐(𝒒𝟏 ), 𝐸𝑛𝑐(𝒒𝟐 )19: end function
D. Select Output Value
The CS receives encrypted PIR queries from thedecryptor, and then selects the output using the queries.
We define a function 𝑃𝑒𝑟𝑚(𝐶𝑡𝑥𝑡, 𝑛𝑢𝑚), where 𝐶𝑡𝑥𝑡 is aciphertext of a vector 𝑡𝑥𝑡 of length 𝑙 , and 𝑛𝑢𝑚 is an
integer𝑛𝑢𝑚 ∈ [0, 𝑙 − 1].
Thefunction𝑃𝑒𝑟𝑚(𝐶𝑡𝑥𝑡, 𝑛𝑢𝑚) right-rotates 𝑛𝑢𝑚 elements from theencrypted vector 𝑡𝑥𝑡. For example, 𝐷𝑒𝑐(𝐶𝑡𝑥𝑡) ={0,1,2}
and 𝐷𝑒𝑐–𝑃𝑒𝑟𝑚(𝐶𝑡𝑥𝑡, 2)— ={1,2,0}.
In the two-dimensional case, we first permute the query
𝐸𝑛𝑐(𝒒𝟏 ) by the function 𝑃𝑒𝑟𝑚. Second, for the 𝑖-th row
of LUT 𝑇deZ , we construct 𝒒′ for the output selection
using the operation 𝐸𝑛𝑐(𝒒𝟎 ) ⊡ 𝑃𝑒𝑟𝑚(𝐸𝑛𝑐(𝒒𝟏 ), 𝑖). Then,
we denote the result of 𝑞′ ⊡ 𝑇deZ [𝑖] as a vector 𝑣d of
ciphertext of length 𝑘. By summing all ciphertexts in 𝑣d,we obtain a ciphertext 𝑐 š , where only one slot contains theoutput 𝑓(𝑥), and remainder of the slots are 0.
In the three-dimensional case, for each 𝑗 ∈ [0, 𝑙 − 1] ∩ ℤ
we first reconstruct a vector of ciphertext 𝒗𝒒 of length 𝑙using the operation 𝐸𝑛𝑐(𝒒𝟏 ) ⊡ 𝑃𝑒𝑟𝑚(𝐸𝑛𝑐(𝒒𝟐 ), 𝑗) .
Second, for the 𝑖-th row of the LUT 𝑇deZ, we construct 𝑞′
for the output selection using the operation 𝐸𝑛𝑐(𝒒𝟎 ) ⊡𝑃𝑒𝑟𝑚(𝒗𝒒 [𝑥], 𝑦) . Then, we denote the result of 𝑞′ ⊡𝑇deZ [𝑖] as a vector 𝒗𝒐 of ciphertext of length 𝑘 . By
summing all ciphertexts in 𝒗𝒐 , we obtain a ciphertext 𝑐 š ,where only one slot contains the desired output 𝑓(𝑥), andthe remainder of the slots are 0.
We represent how to select the output value over 𝑇deZœeZ
in Algorithm 5 and Algorithm 6.
Algorithm 5: Output value selection for two-dimensional
case
Input. LUT matrix 𝑇deZ ∈ ℤm×I ; two PIR queries
𝐸𝑛𝑐(𝒒𝟎 ) and 𝐸𝑛𝑐(𝒒𝟏 )4

DEIM Forum 2019 I5-5
Output. a ciphertext 𝑐′
1: function OutputSelection (𝑇deZ , 𝐸𝑛𝑐(𝒒𝟎 ), 𝐸𝑛𝑐(𝒒𝟏 ))2: 𝑐′ ← 𝐸𝑛𝑐(𝒗𝒛 )wan all-zero vector 𝒗𝒛
2: for 𝑖 = 0 to 𝑘 − 1 do
3: 𝑞′ ← 𝐸𝑛𝑐(𝒒𝟎 ) ⊡ 𝑃𝑒𝑟𝑚(𝐸𝑛𝑐(𝒒𝟏 ), 𝑖)
4: 𝒗𝒐 [𝑖] ← 𝑞′ ⊡ (𝑇deZ [𝑖])wa ciphertext 𝑞′
5: 𝑐 š ← 𝑐 š ⊞ 𝒗𝒐 [𝑖] wa vector of ciphertext 𝒗𝒐
8: end for
9: return 𝑐′
10: end function
Algorithm 6: Output value selection for threedimensional case
Input. LUT matrix 𝑇deZ ∈ ℤm×I ; three PIR query
𝐸𝑛𝑐(𝒒𝟎 ), 𝐸𝑛𝑐(𝒒𝟏 ), 𝐸𝑛𝑐(𝒒𝟐 )Output. a ciphertext 𝑐′
1: function OutputSelection (𝑇deZ , 𝐸𝑛𝑐(𝒒𝟎 ), 𝐸𝑛𝑐(𝒒𝟏 ),𝐸𝑛𝑐(𝒒𝟐))
2: 𝑐′ ← 𝐸𝑛𝑐(𝒗𝒛 )wan all-zero vector 𝒗𝒛
3: for 𝑗 = 0 to 𝑙 − 1 do
4: 𝒗𝒒 [𝑗] ← 𝐸𝑛𝑐(𝑞G ) ⊡ 𝑃𝑒𝑟𝑚(𝐸𝑛𝑐(𝑞• ), 𝑗)
5: end for
6: for 𝑖 = 0 to 𝑘 − 1 do
7: 𝑥 = 𝑖/𝑙
8: 𝑦 = 𝑖%𝑙
9: 𝑞′ ← 𝐸𝑛𝑐(𝒒𝟎 ) ⊡ 𝑃𝑒𝑟𝑚(𝒗𝒒 [𝑥], 𝑦)10: 𝒗𝒐 [𝑖] ← 𝒒′ ⊡ (𝑇deZ [𝑖])wa ciphertext 𝑞′
11: 𝑐 š ← 𝑐 š ⊞ 𝒗𝒐 [𝑖] wa vector of ciphertext 𝒗𝒐
12: end for
13: return 𝑐′
14: end function
Input: vectors 𝒗𝒊𝒏 , 𝒗𝒐𝒖𝒕 ∈ ℤb ; ciphertext 𝑐 of input 𝑥.
Output: ciphertext 𝑐′ of output 𝑓(𝑥)1. Decryptor Setup[Create FHE parameters] The decryptor generates apair of keys: a public key 𝑝𝑘 and a secret key 𝑠𝑘.
Decryptor: 𝑝𝑎𝑟𝑎𝑚𝑠 ← 𝐹𝐻𝐸. 𝑆𝑒𝑡𝑢𝑝 (15 ,16 ,𝑏);(𝑝𝑘, 𝑠𝑘) ← 𝐹𝐻𝐸. 𝑆𝑒𝑐𝑟𝑒𝑡𝐾𝑒𝑦𝐺𝑒𝑛(𝑝𝑎𝑟𝑎𝑚𝑠)[Send the public key] The decryptor sends the public
key to CS.
𝐷𝑒𝑐𝑟𝑦𝑝𝑡𝑜𝑟 → 𝐶𝑆: 𝑝𝑘
2. Construct Lookup Table[Generate a permutation vector] CS generates a
permutation vector 𝒗 ∈ ℤb
[Construct LUT matrices] CS constructs LUT matrices
𝑇ab , 𝑇deZ ∈ ℤm×I
𝑇ab , 𝑇deZ ← 𝐿𝑈𝑇𝐶𝑜𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 (𝒗𝒊𝒏 , 𝒗𝒐𝒖𝒕 , 𝒗)
(Algorithm 1)
3. CS Searches Input Value over LUT matrix[Search input value over the LUT matrix] CS searches
the input ciphertext 𝑐 over the LUT matrix 𝑇ab and get
the result 𝒗𝒄
𝒗𝒄 ← 𝐼𝑛𝑝𝑢𝑡𝑆𝑒𝑎𝑟𝑐ℎ (𝑇ab , 𝑐)
(Algorithm 2)[Send result to the decryptor] CS sends the result to thedecryptor
4. The Decryptor Generate PIR Query[Decrypt the result from the CS] The decryptor
decrypts the result 𝒗𝒄 to a matrix 𝑉z…†
[Generate PIR queries] The decryptor performs two
PIR queries in the two-dimensional case; three PIR
queries in the three-dimensional case.
[Encrypt the PIR queries] The decryptor decrypts the
PIR queries.

𝐸𝑛𝑐(𝒒𝟎 ), 𝐸𝑛𝑐(𝒒𝟏 ) ← QueryGeneration (𝑣| )(2-dimensional case Algorithm 3)
𝐸𝑛𝑐(𝒒𝟎 ), 𝐸𝑛𝑐(𝒒𝟏 ), 𝐸𝑛𝑐(𝒒𝟐 ) ← QueryGeneration (𝑣| )(3-dimensional case Algorithm 4)[Send the PIR queries to the CS] Send the PIR queries
to the CS
5. The CS Selects Output Value from LUT matrix[Select output value from the LUT matrix] CS selects
the output ciphertext 𝑐′ from the LUT matrix 𝑇deZ by the
PIR queries from decryptor.
𝑐′ ← 𝑂𝑢𝑡𝑝𝑢𝑡𝑆𝑒𝑙𝑒𝑐𝑡𝑖𝑜𝑛 (𝑇deZ , 𝐸𝑛𝑐(𝒒𝟎 ), 𝐸𝑛𝑐(𝒒𝟏 ))(two-dimensional case Algorithm 5)𝑐′← 𝑂𝑢𝑡𝑝𝑢𝑡𝑆𝑒𝑙𝑒𝑐𝑡𝑖𝑜𝑛 (𝑇deZ , 𝐸𝑛𝑐(𝒒𝟎 ), 𝐸𝑛𝑐(𝒒𝟏 ), 𝐸𝑛𝑐(𝒒𝟐 ))(three-dimensional case Algorithm 6)
Fig. 4-2 FUNCTION EVALUATION WITH FHE USING LUT
PROTOCOL

5. SECURITY ANALYSIS
Our protocol is implemented using a two-party protocol,
consisting of a CS and decryptor. Below, we demonstrate
how the input value 𝑥 and output value 𝑓(𝑥) are notrevealed to the CS and decryptor. The decryptor is a semihonest party, which owns the secret key but must follow
the exact prespecified protocol, and cannot change its
inputs or outputs.
We guarantee that no information on the underlying
plaintext can leak to anyone in the four main algorithms in
our protocol: construct LUT matrix, search input value,
generate PIR query, and select output value. The original
LUT can be known and uploaded by anyone, which meansthat the original LUT is public.
In the algorithm construct LUT matrix, the CS uses theoriginal LUT to construct two permuted LUT matrices 𝑇ab ,𝑇deZ, and saves these in the CS. In the algorithm search
input value, the input 𝑐 and output 𝑣| of the algorithm areboth ciphertext. Thus, 𝑥 and 𝑓(𝑥) cannot be known by the
CS. In the algorithm generate PIR query, the decryptor
receives the result 𝑣| from the CS, and decrypts it to 𝑉z…† .
The decryptor knows the index (𝑡zd{ , 𝑡|dI ) , i.e.,
𝑉z…† [𝑡zd{ ][𝑡|dI ] = 0, which is also the index of the value
in 𝑇deZ that we want to extract. Then, the decryptor
generates the PIR queries. Because 1) the original LUT ispermuted by a random permutation and the permuted LUT
matrices 𝑇ab , 𝑇deZ are not sent to decryptor, and 2) all theelements in 𝑉z…† contain uniformly random values, thedecryptor cannot know 𝑥 and 𝑓(𝑥). In the algorithm selectoutput value, the input PIR queries and output 𝑐 š are bothciphertexts. Thus, 𝑥 and 𝑓(𝑥) cannot be known by the CS.
Therefore, neither CS nor the decryptor can know the
input value 𝑥 and output value 𝑓(𝑥).

6. EXPERIMENTAL EVALUATIONIn this section, we evaluate the proposed protocol toconfirm its efficiency, by implementing it with HElib*,which is based on the BGV scheme. The implemented
protocol considers the two-dimensional and twodimensional cases, which means that the protocol supports
up to 𝑙Š elements in the LUT matrix, whose number ofcolumns is 𝑙 (the number of slots). In the evaluation, one
machine was prepared to operate as both the CS anddecryptor, i.e., both modules run on the same machine.
The communication between the CS and decryptor, suchas ciphertext results and encrypted PIR queries, washandled by writing to files.
HElib*: https://github.com/shaih/HElib

5

DEIM Forum 2019 I5-5

The experimental evaluation consists of two evaluations:
Experiment-1 and Experiment-2. Experiment-1 confirms
the effectiveness of our proposed protocol in comparison
with the method of Crawford et al.. Experiment-2
evaluates the feasibility of our proposed protocol, by
measuring both the runtime and communication cost.
Experiment-1
Experiment-1 compares the proposed method with therelated method of Crawford et al. [4]. The utilized FHE
parameters are shown in Table 6-1, which are as consistent
as possible with those of [4]. We set the plaintext space as
2G¬ = 32,768, which means that in our protocol the input
and output integers of the function are in a 15-bit range
size. The number of elements in this experiment is 27,000(𝑘 = 15). We employed the environment detailed in Table
6-2 for Experiment-1. We set a larger plaintext space andtable size on the machine, whose CPU and memory are
weaker to those used in [4], to perform the experiment. To
implement a multi-thread environment, we utilize
NTL/BasicThreadPool.h from the NTL* library, and wetest the runtime for different numbers of threads.
Experiment-2
The purpose of this experiment is to measure the runtime
and communication cost for our proposed protocol. We
perform this experiment with different numbers ofelements in the LUT matrix. Using the same FHE
parameters as shown in Table 6-1, we vary the number of
elements by varying the number of rows 𝑘 in the LUT
matrix. When 𝑘 ≤ 224, the number of dimensions is two,
and when 224 < 𝑘 ≤ 224• the number of dimensions isthree. We employed the environment detailed in Table 62. To implement a multi-thread environment, we employ
NTL/BasicThreadPool.h from the NTL library, and set the
number of threads to 36, which means that we utilize twoCPUs (each with 18 cores) in this experiment.
6.1 RUNTIME RESULTS
We show the runtimes for the search input value,
generate PIR query, and select output value algorithms inExperiment-1, along with the total time as the averageover five trials, in Table 6-3. The runtime forExperiment-2 is shown in Table 6-4.
Crawford et al. employed an Intel Xeon E5-2698 v3(which is a Haswell processor), with two sockets and 16
cores per socket, at 2.30 GHz. The main memory size was
250 GB. They set 𝑚 = 2G¬ − 1 = 32767 , with theExperiment
1
2
Experiment1
2

𝒎
32,767
11,441

plaintext space 2GG = 2048 , so that 1800 slots wereavailable. Each plaintext slot held a degree-15 extension(𝐿 = 15).
The result from Experiment-1 shows that we can look up
27,000 15-bit integers the LUT matrix in approximately
23 s, excluding the communication time. By using eight
threads, the runtime can be reduced to 6 s excluding thecommunication time. The evaluation time is independentof the function. Our result shows that our proposed
protocol using integer encoding is more practical than themethod in [4].
The result from Experimente-2 shows that we can lookup 448,000 19-bit integers in the LUT in approximately
20 min for one thread, excluding the communication time.
By using 36 threads, the runtime can be reduced toapproximately 51 s excluding the communication time.
Our results show that the construction of the LUT matrices
supports multi-thread execution in every row, whichmakes it possible to further reduce the runtime.
6.2 COMMUNICATION COSTIn our protocol, the CS communicates with the decryptor.
We measured the transferred data size for each input inour protocol, and calculated the transmission time. The
communication cost in Experiment-1 is shown in Table
6-5, and that in Experiment-2 is shown in Table 6-6.
The result for Experiment-1 (Table 6-5) shows that when
the transmission speed is 100 Mbps, we can look up
27,000 15-bit integers the LUT matrix in approximately
30 s using one thread, including approximately 7 s ofcommunication time. Even our protocol involves
communication between the CS and decryptor, the overallruntime of our protocol is approximately 120 times fasterthan that of Crawford et al. [4] running on one thread, andapproximately 74 times faster running on eight threads.
The result from Experiment-2 (Table 6-6) shows that in
our protocol, the communication cost is 𝑂(𝑘 ∙ 𝑠) for the
CS to send the result to the decryptor, and 𝑂(𝑑 ∙ 𝑠) for thedecryptor to send the PIR query to the CS, where 𝑠 is thesize of a single ciphertext, 𝑘 is the number of rows in the
LUT matrix, and 𝑑 is the number of dimensions. As thenumber of elements in the LUT matrix increases, thetransferred data size from the CS to the decryptor
increases linearly, and the transferred data size from thedecryptor to the CS increases in stages.
NTL*: https://www.shoup.net/ntl/

Table 6-1 FHE PARAMETERS OF HELIB IN THE EXPERIMENT
Security
Plaintext space
𝒍
1,800
300
32,768 (2^15)
224
142
524,288 (2^19)

Table 6-2 EXPERIMENTAL ENVIRONMENT IN THE EXPERIMENTOS
CPU
MemoryIntel(R) Core (TM)Ubuntu 18.04.1
15.4 GB
i7-8700 @3.2 GHzIntel Xeon CPU E78880 v3 @ 2.3 GHz
CentOS 7.3.1611
3 TB(Turbo Boost: 3.1
GHz)

𝑳
15
10
# of CPUs (sockets)
one (each with six
cores)
four (each with 18
cores)

6

DEIM Forum 2019 I5-5

Table 6-3 RUNTIME IN EXPERIMENT-1
Our protocol
1
2
4
8
0.63
0.37
0.21
0.17
14.90
8.33
4.28
3.32
7.72
4.71
2.65
2.20
23.25
13.42
7.14
5.69

# of threads(a) Search Input Value [s](b) Generate PIR Query [s](c) Select Output Value [s](a)+(b)+(c) Total [s]# of elements# of dimensions# of threads(a) Search Input Value [s](b) Generate PIR Query[s](c) Select Output Value[s](a)+(b)+(c) Total [s]Data
CS to Decryptor
Decryptor to CS

Data

CS to
Decryptor

Decryptor toCS

Crawford et al. [4]
2
4

1
60
min

35
min

20
min

8
16
min

1
4.73

Table 6-4 RUNTIME IN EXPERIMENT-2
44,800
2
4
12
36
1
1.50
0.61
0.44
47.30

4
13.78

12
4.98

36
2.28

53.55

15.02

5.44

2.47

534.18149.98

51.57

17.98

55.01

16.56

6.52

5.03

598.09179.22

69.86

30.80

113.29

33.08

12.57

5.90

1179.58

342.97126.5551.07

448,000
3

Table 6-5 COMMUNICATION COST IN EXPERIMENT-1
Calculated transmission time [ms]Measured transferred data size
# of elements[MB]
100 Mbps
1 Gbps
10 Gbps
826406.25640.6
64.06
27,00011859.38
85.93
8.60
# of
elements
11,20022,40033,60044,800112,000
224,000
336,000
448,000
11,20022,40033,60044,80050,17650,177
112,000
224,000
336,000
448,000

Table 6-6 COMMUNICATION COST IN EXPERIMENT-2
Calculated transmission time# ofMeasured transferreddimensions
data size [MB]100 Mbps
1 Gbps
10 Gbps66
5.16 s0.52 s0.05 s132
10.31 s1.03 s0.10 s2
197
15.39 s1.54 s0.15 s263
20.55 s2.06 s0.21 s656
51.25 s5.13 s0.51 s1,331
103.98 s
10.40 s1.04 s3
2,048
160.00 s
16.00 s1.60 s2,662
207.97 s
20.80 s2.08 s22.7

210.9 ms

21.10 ms

2.11 ms3

4.0

312.50 ms

31.25 ms

3.13 ms

7. CONCLUSION
In this paper, we proposed an LUT protocol forevaluating any single-integer input functions. We
proposed a new protocol to resolve the problems with theexisting method in [4], i.e., 1) bitwise encoding is
employed, which is not scalable, and 2) the LUT must
include all possible input values, meaning that it may behuge, increasing the evaluation time.
Our protocol adopts integer encoding, which is more
efficient than bitwise encoding. The experimental results
show that we can look up 27,000 15-bit integers in the
LUT matrix in approximately 30 s using one thread,including approximately 7 s of communication time. The
evaluation time is independent of the function.
The construction of the LUT matrices supports multithread execution in every row, which makes it possible tofurther reduce the runtime. We can look up 448,000 19-bit

integers in the LUT in approximately 51 s excluding thecommunication time using 36 threads.
Using the query generation method based on ourprevious work [6], we can reduce the communication cost.
The communication cost is 𝑂(𝑘 ∙ 𝑠) for the CS to send theresult to the decryptor, and 𝑂(𝑑 ∙ 𝑠) for the decryptor tosend the PIR query to the CS, where 𝑠 is the size of asingle ciphertext, 𝑘 is the number of rows in the LUT
matrix, and 𝑑 is the number of dimensions. As the numberof elements in the LUT matrix increases, the transferreddata size from the CS to the decryptor increases linearly,
and the transferred data size from the decryptor to the CS
increases in stages.
Our experimental result shows that we can achieve a
shorter runtime using a weaker machine than in [4] to lookup more integers, which demonstrates that our protocol ismore practical than that in [4].

7DEIM Forum 2019 I5-5

Currently, our proposed protocol can evaluate any
functions with one input value. Our future work will
include extending our protocol to handle multi-input
values.

ACKNOWLEDGEMENT
This work was supported by JST CREST Grant Number
JPMJCR1503, Japan and Japan-US Network Opportunity
2 by the Commissioned Research of National Institute ofInformation and Communications Technology (NICT),JAPAN.

REFERENCES
[1]

[2]

[3]
[4]

[5]

M. D. Ryan.: Cloud computing security: The
scientific challenge, and a survey of solutions. In
Journal of Systems and Software, vol 86, issue 9,
pp.2263-2268. (2013)
S. M. Shariati, Abouzarjomehri and M. H.
Ahmadzadegan.: Challenges and security issues incloud computing from two perspectives: Data
security and privacy protection. In Proc. of KBEI
2015, pp.1078-1082. (2015)
C. Gentry.: Fully Homomorphic Encryption Using
Ideal Lattices. In Proc. of STOC 2009, pp.169-178.
(2009)J. L. H. Crawford, C. Gentry, S. Halevi, D. Platt andV. Shoup: Doing Real Work with FHE: The Case ofLogistic Regression. In Proc. of WAHC 2018, pp. 112. (2018)
B. Chor, O. Goldreich, E. Kushilevitz, and M.
Sudan.: Private information retrieval. In Journal of
the ACM, vol 45, issue 6, pp. 965-981. (1998)[6]

Y. Ishimaki, H. Imabayashi and H.Yamana.: Private
Substring Search on Homomorphically Encrypted
Data. In Proc. of SMARTCOMP 2017, pp.1-6.
(2017)[7] Z. Brakerski and V. Vaikuntanathan.: Lattice-based
FHE as secure as PKE. In Proc. of ITCS 2014, pp. 112. (2014)[8] Z. Brakerski, C. Gentry and V. Vaikuntanathan:(Leveled) Fully Homomorphic Encryption without
Bootstrapping. In Proc. of ITCS 2012, pp.309-325.
(2012)[9] N. P. Smart and F. Vercauteren.: Fully homomorphic
SIMD operations. In Journal of Designs, Codes andCryptography, vol 71, issue 1, pp. 57-81. (2014)[10] C. Aguilar-Melchor, J. Barrier, L. Fousse, and M.
Killijian.: XPIR: Private information retrieval foreveryone. In Journal of Proceedings on Privacy
Enhancing Technologies, vol 2016, issue 2, pp. 155174. (2015)[11] S. Angel, H. Chen, K. Laine, S. Setty.: PIR with
Compressed Queries and Amortized Query
Processing. In Proc. of S&P 2018, pp.962-979.
(2017)[12] S. Badsha, X. Yi, I. Khalil and E. Bertino.: Privacy
Preserving User-based Recommender System. In
Proc. of ICDCS 2017, pp. 1074-1083. (2017)[13] Q. Tang and H. Wang.: Privacy-preserving Hybrid
Recommender System. In Proc. of CSS 2017, pp.
59-66. (2017)8