Fully Homomorphic Encryption forClassification in Machine Learning
Seiko Arita

Shota Nakasato

Graduate School of Information Security
Institute of Information Security, Japan
Email: arita@iisec.ac.jp

Graduate School of Information Security
Institute of Information Security, Japan
Email: snakasato@snakasato.com

Abstract—Using fully homomorphic encryption scheme, weconstruct fully homomorphic encryption scheme FHE4GT that
can homomorphically compute an encryption of the greaterthan bit that indicates 𝑥 > 𝑥′ or not, given two ciphertexts
𝑐 and 𝑐′ of 𝑥 and 𝑥′ , respectively, without knowing the secretkey. Then, we construct homomorphic classifier homClassify that
can homomorphically classify a given encrypted data without
decrypting it, using machine learned parameters.

I. I NTRODUCTION
Fully Homomorphic Encryption (FHE) scheme enables
us to homomorphically compute an encrypted XORed bit
Enc(𝑏1 XOR 𝑏2 ) and encrypted AND bit Enc(𝑏1 AND 𝑏2 ) ofgiven encrypted bits Enc(𝑏1 ) and Enc(𝑏2 ) without knowing thesecret key [7]. Since any function can be written using XOR
and AND gates, this means that one can homomorphicallycompute any function of encrypted bits without knowing thesecret key.
Practically, computation over bitwise encryptions is not efficient. It is a kind of “1-bit” processor. In schemes such as [3],[4], one can encrypt congruent integers (i.e., 𝑥 mod 𝑛) and canhomomorphically compute addition Enc(𝑥1 + 𝑥2 mod 𝑛) andmultiplication Enc(𝑥1 × 𝑥2 mod 𝑛) of encrypted congruent
integers Enc(𝑥1 ) and Enc(𝑥2 ) without knowing the secret key.
Using the FHE schemes, many researchers consider about
the privacy-preserving data mining for outsourced data suchas encrypted genomic, medical, financial data and so on [10],[14], [5], [15], [13], [12].
In this paper, we propose a homomorphic classifier using
machine learned parameters. Suppose some machine learned
parameters are stored in some cloud servers, and clients want
the cloud server to classify their own data using the machinelearned parameters stored in the cloud. Here, if clients send
their data to the server without encryption, they must worry
about their data privacy. However, if clients encrypts their data,then the cloud server cannot do the classifying task against
such encrypted data.
Our solution to the dilemma is to encrypt client’s data using
FHE schemes. Clients encrypt their own data using some FHE
scheme and send the encrypted data to the cloud server. The
cloud server can perform its classifying task homomorphically(i.e., without decryption of encrypted client’s data) thanks to
the homomorphic property of FHE, where the server can only
know its encrypted classified result. The encrypted result will978-1-5090-6517-2/17/$31.00 ©2017 IEEE

send back to the client, and only the client can decrypt theclassifying result. By using such homomorphic classifier, we
can utilize machine learned parameters in the cloud, keeping
the privacy of client’s data.
However, here is an important technical problem. Classifying algorithms require to compute greater-than relation of
given data items. However, conventional FHEs are not able
to compute greater-than relation of encrypted data homomorphically. Actually, conventional methods compute greater-thanrelation after decrypting [10] or by using the greater-thanprotocol [1].
Therefore, we construct fully homomorphic encryption
scheme FHE4GT that can homomorphically compute an encryption of the greater-than bit that indicates 𝑥 > 𝑥′ or not,given two ciphertexts 𝑐 and 𝑐′ of 𝑥 and 𝑥′ , respectively, without
knowing the secret key.

A. Our Contribution
1) FHE scheme FHE4GT for Greater-Than relation: At
the first, we construct the FHE scheme FHE4GT that canhomomorphically compute an encryption of greater-than bitthat indicates 𝑥 > 𝑥′ or not, given two ciphertexts 𝑐 and 𝑐′ of𝑥 and 𝑥′ , respectively, without knowing the secret key.
2) Homomorphic Classifier homClassify: By using the
FHE4GT, we construct homomorphic classifier homClassify
that can homomorphically classify a given encrypted data
without decrypting it, using machine learned parameters.
Implementation and benchmark: We implemented ourscheme using homomorphic encryption library HElib byHalevi and Shoup [11], which is based on the BGV scheme[3].
Organization: Section II recalls FHE scheme and its basic properties. Then, we treat the problem of homomorphic
computation for greater-than relation in Section II-B. We
construct the FHE4GT scheme of greater-than relation in
Section III. And then, we construct the homomorphic classifier
homClassify for binary classification (i.e. a machine learningalgorithm like SVM[16]) in Section IV. Finally, we show ourbenchmark results in Section V.

II. P RELIMINARIES
A. Homomorphic Encryption
A homomorphic encryption scheme is a quadruple HE =(Keygen, Enc, Dec, Eval) of probabilistic polynomial time algorithms. Keygen generates a public key pk, a secret key
sk and an evaluation key evk: (pk, sk, evk) ← Keygen(1𝜆 ).
Enc encrypts a plaintext 𝑥 ∈ ℤ𝑛 to a ciphertext 𝑐 under apublic key pk: 𝑐 ← Enc(pk, 𝑥). Dec decrypts a ciphertext 𝑐
to a plaintext 𝑥 by the secret key sk: 𝑥 ← Dec(sk, 𝑐). Eval
applies a function 𝑓 : ℤ𝑙𝑛 → ℤ𝑛 to given ciphertexts 𝑐1 , . . . , 𝑐𝑙and outputs a ciphertext 𝑐𝑓 using the evaluation key evk :𝑐𝑓 ← Eval(evk, 𝑓, 𝑐1 , . . . , 𝑐𝑙 ).
A homomorphic encryption scheme HE is called 𝐿homomorphic for 𝐿 = 𝐿(𝑛) if for any function 𝑓 : ℤ𝑙𝑛 → ℤ𝑛given as a circuit of depth 𝐿 and for any 𝑙 bits 𝑥1 , . . . , 𝑥𝑙 , itholds that Decsk (Evalevk (𝑓, 𝑐1 , . . . , 𝑐𝑙 )) = 𝑓 (𝑥1 , . . . , 𝑥𝑙 ) for𝑐𝑖 ← Encpk (𝑥𝑖 ) (𝑖 = 1, . . . , 𝑙) except with a negligible probability. A homomorphic encryption scheme is called fully homomorphic encryption (FHE) scheme if it is 𝐿-homomorphic
for any polynomial function 𝐿 = 𝑝𝑜𝑙𝑦(𝑛).
B. Greater-than relation
We consider the problem of comparison of magnitude of two
encrypted numbers. Suppose we have two encrypted numbers
Enc(𝑥) and Enc(𝑥′ ). Define a bit 𝑏 to be 1 if 𝑥 > 𝑥′ and 0
otherwise. We want to compute an encryption Enc(𝑏) of the bit𝑏 given only ciphertexts Enc(𝑥) and Enc(𝑥′ ) without knowing
the secret key. In the literature [13], [12] such problem istackled by Greater-Than protocol based on (such as) the one
given by Golle [9]. Their protocol is based on the fact that if𝑥 > 𝑥′ , there exists a positive integer 𝑖 such that 𝑥 = 𝑥′ + 𝑖.

Digits-Extraction (𝑐, 𝑟) :𝑤0,0 ← 𝑐
For 𝑖 ∈ [0..𝑟 − 1]:𝑦←𝑐
For 𝑗 ∈ [0..𝑖]:𝑤𝑗,𝑖+1 ← 𝑤𝑗,𝑖 2𝑦 ← (𝑦 − 𝑤𝑗,𝑖+1 )/2
𝑤𝑖+1,𝑖+1 ← 𝑦return 𝑤𝑟,𝑟Fig. 1. The Digits-Extraction algorithm

Keygen () : return (sk, pk) ← FHE.Keygen()Enc (pk, 𝑥 ∈ 𝑅2𝑡 ) : return𝑐 ← FHE.Enc(pk,𝑥)[]
Dec (sk, 𝑐) : return FHE.Dec(sk, 𝑐) 2𝑡
Add (𝑐, 𝑐′ ) : return FHE.Add(𝑐, 𝑐′ )Mult (𝑐, 𝑐′ ) : return FHE.Mult(𝑐, 𝑐′ )homBitDecomp (𝑐, 𝑟) :𝑤0 ← 𝑐
For 𝑖 ∈ [0..𝑟 − 1]:𝑦←𝑐
For 𝑗 ∈ [0..𝑖 − 1]:
𝑤𝑗 ← Mult(𝑤𝑗 , 𝑤𝑗 )𝑦 ← Add(𝑦, −𝑤𝑗 )/2
𝑤𝑖 ← 𝑦return (𝑤0 , 𝑤1 , ..., 𝑤𝑟−1 )GT (𝑐, 𝑐′ ) :(𝛾0 , ..., 𝛾𝑟−1 ) ← homBitDecomp(Add(𝑐′ , −𝑐), 𝑟)
return 𝛾𝑟−1
Fig. 2. The FHE4GT scheme

III. T HE P ROPOSED S CHEME FHE4GT
In this section we construct an FHE scheme that canhomomorphically compute the greater-than bit, using FHE
schemes based on RLWE problem such as [2], [3], [6] asbuilding blocks.
Parameters: The FHE4GT scheme is parameterized bythree parameters 𝑞, 𝑟 and 𝑡. The parameter 𝑞 denotes ciphertext
modulus. The parameter 2𝑟 denotes plaintext modulus of
FHE and the parameter 𝑡 denotes bit-length of plaintext. Let𝑟 = 𝑡 + 1. For 𝑧 ∈ ℤ, [𝑧]𝑞 denotes the unique integer in[−𝑞/2, 𝑞/2) with [𝑧]𝑞 ≡ 𝑧 mod 𝑞.
SchemeDescription:
Let
FHE
=
(Keygen, Enc, Dec, Add, Mult)beconventional
FHE such as [2]. The FHE4GT scheme consistsof the algorithms in Figure 2. Note that key
generation/encryption/decryption/addition/multiplication
algorithms are the same as corresponding algorithms of FHE
scheme. Additional points are homomorphic bit decompositionand homomorphic computation of greater-than bit. First, we
describe procedure homBitDecomp(𝑐, 𝑟), that computes an
encryption of the bit decomposition of 𝑥 ∈ 𝑅𝑡 , given an
FHE ciphertext 𝑐 of some plaintext 𝑥. It homomorphicallyextracts the bit decomposition of (𝑏0 , 𝑏1 , ..., 𝑏𝑟−1 ) of 𝑥 using
Digits-Extraction algorithm in [8]. The Digits-Extraction

algorithm in the base-2 case forthe ciphertext of∑ extracting
𝑖
𝑥
2
is
shown
in the Fig.
𝑟th digit of the integer 𝑥 =𝑖𝑖
1. Note that, the homomorphic division by 2 is possible bymultiplying the ciphertext by the constant 2−1 mod 𝑞.
Based on Digits-Extraction algorithm, for ciphertext 𝑐 of
𝑥 of 𝑟 bits, we construct homBitDecomp algorithm. Outputs(𝑤0 , 𝑤1 , ..., 𝑤𝑟−1 ) of homBitDecomp satisfies that𝑥 = (Dec(𝑤𝑟−1 ) ∥ Dec(𝑤𝑟−2 ) ∥ ⋅ ⋅ ⋅ ∥ Dec(𝑤0 ))2 .
Using the homBitDecomp algorithm, only given two ciphertexts 𝑐 and 𝑐′ of 𝑥 and 𝑥′ , we can compute an encryptionof greater-than bit homomorphically. In the GT algorithm,
it simply computes homBitDecomp(𝑐′ − 𝑐), then outputs
encryption of the most significant bit because the sign bit of
the value 𝑐′ − 𝑐 becomes a bit representing the greater-thanrelation.
Using such GT algorithm, we can compute the greater-thanbit encryption Enc(𝑏) given only Enc(𝑥) and Enc(𝑥′ ), neither
knowing the secret key nor interaction with secret key holder.
The FHE4GT scheme is semantically secure and fully
homomorphic with suitable choice of parameters that makes
the underlying FHE scheme so.

Efficiency: We estimate efficiency of homomorphic operations of FHE4GT scheme of parameter 𝑞, 𝑟, 𝑡. Addition
Add(𝑐, 𝑐′ ) and multiplication Mult(𝑐, 𝑐′ ) are done by one addition/multiplication of FHE of parameter 𝑞, 𝑟. Homomorphic
computation of greater-than relation GT depends on the number of multiplications of ciphertexts and the circuit of depth
𝐿 because it is dominated by homomorphic bit decomposition
homBitDecomp. In the homBitDecomp, it recursively needs
to repeat squaring. Therefore, for bit length 𝑡 of plaintext,
since we use the plaintext modulus 2𝑟 = 2𝑡+1 , homomorphic
computation of greater-than relation needs the circuit of depth
corresponding to 𝐿
depthGT = 𝑂(𝑟2 ).
IV. C LASSIFICATIONIn this section, we propose the homomorphic classifier homClassify based on the FHE4GT scheme. Let us consider thecase of binary classification (i.e. a machine learning algorithm
like SVM[16]).
𝑔(x) = w ⋅ x + 𝑏 =𝑑∑𝑤𝑖 𝑥𝑖 + 𝑏.

𝑖=1Here, w is the weight vector and 𝑏 is the bias. A hyperplane
is a generalization of a straight line to > 2 dimensions. We
consider a linear discriminant function. A hyperplane contains
all the points in a 𝑑 dimensional space satisfying the following
equation.
𝑤1 𝑥1 + 𝑤2 𝑥2 + ... + 𝑤𝑑 𝑥𝑑 + 𝑏 = 0.
By identifying the components of w with the coefficients 𝑤𝑖 ,we can see the weight vector and the bias define a linear
decision surface in 𝑑 dimensions. It is common to simplify
notation by including the bias in the weight vector, i.e. 𝑏 =𝑤0 , 𝑥0 = 1.
𝑑∑𝑔(x) = w ⋅ x =𝑤𝑖 𝑥 𝑖 .
𝑖=0

We consider a linear classifier of the following form.
{
1 if 𝑔(x) > 0𝑓 (x; w) =0 otherwise.
In our proposed homomorphic classification (Fig. 3), we
treat given test data x and output of classifier 𝑓 as ciphertexts(i.e. only given Enc(𝑥𝑖 ), it outputs Enc(𝑓 (x; w)).
Therefore, we consider the testing stage where the client’s
data is encrypted with its own public key.
Efficiency: In the case of homomorphic classification, it
needs the circuit of depth depthhomClassify = depthGT + 1.
V. B ENCHMARK R ESULTS
We implemented the FHE4GT scheme described in Section
III using homomorphic encryption library HElib [11].
In this section, we show experimental results of FHE4GT
and homClassify. We implemented our proposed scheme
using homomorphic encryption library HElib by Halevi andShoup [11], which is based on the BGV scheme [3].

homClassify (c, w) :𝑔 ← Enc(0)For 𝑖 ∈ [0..𝑑]:𝑔 ← Add(𝑔, 𝑤𝑖 𝑐𝑖 )𝑦 ← GT(𝑔, Enc(0))
return 𝑦
Fig. 3. The homClassify algorithm

All timings were obtained running on an Intel Core i7 at
2.4 GHz with 16GB of memory. Timings are given in seconds.
These results are the averages of 100 times trials.
Choise of Parameters: We implemented three cases where
the size of plaintext 𝑡 is 2bits, 4bits and 8bits (did not use
slots). Each parameter sets are shown in the Table I. For
these experiments, we fix the security parameter 𝜆 = 80,
the standard deviation of Gaussian distribution (i.e. a noise
parameter) 𝜎 = 3.2, and the secret key is chosen uniformly
random among ternary vector (i.e. {−1, 0, 1}) of Hamming
weight 64. In theory, the level 𝐿 of ciphertext is roughly𝑂(𝑟2 ), but in fact the smaller value shown in the Table I issufficient.
Timings for FHE4GT and homClassify: Table II shows
timing s for the FHE4GT operations: encryption, decryption,
addition, and multiplication. Table III shows timings for the
GT and homClassify. For the homClassify, we experimented
in three cases of dimensions 𝑑 = 10, 20, 30 for each parameterset.
The time spent on homomorphic computation of greaterthan relation is about 0.02 seconds for parameter set 𝑃1 , 0.3
seconds for 𝑃2 and 3.2 seconds for 𝑃3 . In addition, the timespent on homomorphic classification for dimension 𝑑 = 10 isabout 0.03 seconds for 𝑃1 , 0.3 seconds for 𝑃2 and 3.3 seconds
for 𝑃3 . As the circuit of depth 𝐿 increases, the ciphertext
modulus 𝑞 also increases, which affects the calculation speed.
VI. C ONCLUSION
In order to protect a private data from leakage whenclassifying in machine learning, we should encrypt the data.
In this paper, using fully homomorphic encryption
scheme, we constructed fully homomorphic encryption scheme
FHE4GT that can homomorphically compute an encryptionof the greater-than bit that indicates 𝑥 > 𝑥′ or not, given
two ciphertexts 𝑐 and 𝑐′ of 𝑥 and 𝑥′ , respectively, without
knowing the secret key. Then, we proposed homomorphic
classifier homClassify that can homomorphically classify agiven encrypted data without decrypting it, using machinelearned parameters. By using homomorphic classifier, we areable to deal more safely with classification using the learning
results.
ACKNOWLEDGMENT
This work was supported by JST CREST Grant Number
JPMJCR1503, Japan.

TABLE I
PARAMETER SETS FOR FHE4GT.

𝑃1
𝑃2
𝑃3

Parameters𝑚 = 4051, 𝑝 = 2, 𝑟 = 3, 𝑡 = 2, 𝐿 = 3, 𝜎 = 3.2, 𝜆 = 80𝑚 = 7781, 𝑝 = 2, 𝑟 = 5, 𝑡 = 4, 𝐿 = 7, 𝜎 = 3.2, 𝜆 = 80𝑚 = 14351, 𝑝 = 2, 𝑟 = 9, 𝑡 = 8, 𝐿 = 17, 𝜎 = 3.2, 𝜆 = 80

TABLE IIT IMING FOR FHE4GT OPERATIONS ( SEC ): ENCRYPTION , DECRYPTION , ADDITION , AND MULTIPLICATION .

Parameter set
𝑃1
𝑃2
𝑃3

FHE4GT.Enc
0.00440.01490.057

FHE4GT.Dec
0.00160.00620.0227FHE4GT.Add
3.654E-5
1.514E-4
6.127E-4

FHE4GT.Mult
0.00960.04490.1706TABLE IIIT IMING FOR GT AND HOM C LASSIFY ( SEC ).

GT
𝑃1
𝑃2
𝑃3

0.02240.25593.235

𝑑 = 100.03170.25933.3302R EFERENCES[1] Raphaël. Bost, Raluca Ada Popa, Stephen Tu and Shafi Goldwasser,
Machine learning classification over encrypted data. IACR Cryptology
ePrint Archive, (2014/331).
[2] Zvika Brakerski, Fully homomorphic encryption without modulus switching from classical GapSVP. Crypto 2012, LNCS 7417, pages 868-886.
Springer, 2012.
[3] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan, (Leveled) fully
homomorphic encryption without bootstrapping. In Shafi Goldwasser,
editor, ITCS, pages 309-325. ACM, 2012.
[4] Jung Hee Cheon, Jean-Sébastien Coron, Jinsu Kim, Moon Sung Lee,
Tancrède Lepoint, Mehdi Tibouchi, and Aaram Yun, Batch fully homomorphic encryption over the integers. In Thomas Johansson and Phong
Q. Nguyen, editors, EUROCRYPT 2013, LNCS 7881, pages 315-335.
Springer, 2013.
[5] Jung Hee Cheon, Miran Kim, Kristin Lauter, Homomorphic Computationof Edit Distance. Financial Cryptography and Data Security 2015, LNCS
8976, pp 194-212, 2015.
[6] Junfeng Fan and Frederik Vercauteren, Somewhat practical fully homomorphic encryption. IACR Cryptology ePrint Archive, (2012/144).
[7] Craig Gentry, Fully homomorphic encryption using ideal lattices. In
Michael Mitzenmacher, editor, STOC, pages 169-178. ACM, 2009.
[8] C. Gentry, S. Halevi, and N. P. Smart, Better bootstrapping in fully
homomorphic encryption. In Public Key Cryptography, pages 1-16. 2012.
[9] Philippe Golle, A private stable matching algorithm. In Financial Cryptography and Data Security, pages 65-80. Springer, 2006.
[10] Thore Graepel, Kristin Lauter, Michael Naehrig, ML Confidential: Machine Learning on Encrypted Data. ICISC 2012, LNCS 7839, SpringerVerlag (2013), pp 1-21.
[11] Shai Halevi, Victor Shoup, Algorithms in HElib. CRYPTO2014, LNCS
8616, pp 554-571.
[12] Yu Ishimaki, Kana Shimizu, Koji Nuida, Hayato Yamana, Faster privacypreserving search for genome sequences using fully homomorphic encryption, SCIS’16, 2016, Japan.
[13] Wen-jie Lu, Shohei Kawasaki, Jun Sakuma, Cryptographically-secure
Outsourcing of statistical Data Analysis I: Descriptive Statistics. CSS’15,
2015, Japan.
[14] K. Lauter, A. López-Alt, M. Naehrig, Private Computation on Encrypted
Genomic Data. LATINCRYPT 2014, LNCS 8895, Springer-Verlag, pp 327.

homClassify
𝑑 = 200.03040.29063.3754𝑑 = 300.03120.29323.4104[15] Junqiang Liu, Jiuyong Li, Shijian Xu, and Benjamin C.M. Fung, Secure
Outsourced Frequent Pattern Mining by Fully Homomorphic Encryption.
S. Madria and T. Hara (Eds.): DaWaK 2015, LNCS 9263, pp. 70-81,
2015.
[16] V. Vapnik, and A. Lerner, Pattern recognition using generalized portrait
method. Automation and Remote Control, 24, pp. 774-780, 1963.