This article has been accepted for publication in a future issue of this journal, but has not been

fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/JBHI.2017.2657458, IEEE Journal of
Biomedical and Health Informatics
1

SecureMed: Secure Medical Computation using

GPU-Accelerated Homomorphic Encryption Scheme
Alhassan Khedr, Member, IEEE, and Glenn Gulak, Senior Member, IEEE

Abstract—Sharing the medical records of individuals among

healthcare providers and researchers around the world can
accelerate advances in medical research. While the idea seems Cloud
increasingly practical due to cloud data services, maintaining Server
Analyst
patient privacy is of paramount importance. Standard encryption
algorithms help protect sensitive data from outside attackers but
Secure
they cannot be used to compute on this sensitive data while Channel
being encrypted. Homomorphic Encryption (HE) presents a very
useful tool that can compute on encrypted data without the need
to decrypt it. In this work, we describe an optimized NTRU-
based implementation of the GSW homomorphic encryption Patient Medical Personnel
scheme. Our results show a factor of 58× improvement in
CPU performance compared to other recent work on encrypted
medical data under the same security settings. Our system is Key Authority
built to be easily portable to GPUs resulting in an additional System
speedup of up to a factor of 104× (and 410×) to offer an overall Fig. 1: High level block diagram for the medical data/key-distribution
speedup of 6085× (and 24011×) using a single GPU (or four system.
GPUs), respectively.
Index Terms—Homomorphic Encryption, FHE, NTRU, Med-
ical Applications, Relational Operations, Implementation, GPU.
wearable and portable medical devices prior to uploading
them to the cloud. This can be very useful to help researchers
and clinicians to conduct research or diagnose using this
I. I NTRODUCTION secure data. These devices can store public encryption keys

T HE privacy of sensitive personal information is an

increasingly important topic as a result of the increased
availability of cloud services. These privacy issues arise
produced by a centralized entity, which is also responsible
for the distribution of secret keys to the hospitals through
secure channels. The challenge here is that these portable
due to the legitimate concern of a) having a security breach devices have modest computing power compared to general
on these cloud servers or b) the leakage of this sensitive purpose processors. Fortunately, these devices only need
information due to an honest but curious individual at the to encrypt the measurement data. Since performance of
cloud service provider. Standard encryption schemes try to the encryption function is not time latency critical, these
address the first concern by devising encryption schemes that embedded processors can encrypt sensor data within seconds
are harder to break, yet they don’t solve the possible misuse instead of milliseconds and still offer acceptable performance
of this sensitive data by the cloud service providers. to real applications.

Homomorphic encryption (HE) presents a tool that can A proposed way to handle medical data measurements,
solve both types of privacy concerns. The clients are given analysis, and key distribution system is demonstrated in
the possibility of encrypting their sensitive information before Figure 1. A central medical authority, such as the Ontario
sending it to the cloud. The cloud will then compute over their Laboratories Information System (OLIS), will be responsible
encrypted data without the need for the decryption key. By for generating secret and public keys. Public keys will then
using HE, servers guarantee to the clients that their valuable be distributed, using the wide-area network, among medical
information is never in the clear. A fully homomorphic laboratories and downloaded to portable and wearable medical
encryption scheme (FHE) is an encryption scheme that allows devices. The medical data generated by the medical personnel
evaluation of arbitrary functions on encrypted data. in laboratories and by patients using their devices will then
be encrypted by the public key and uploaded to the cloud.
In the era of Internet of Things (IoT), homomorphic All patient medical data can be stored on the cloud servers
encryption can be used to encrypt the data measured by safely as the HE scheme is provably secure against attacks.
Alhassan Khedr is with the Department of Electrical and Computer Engi- Analysts, administrators, or clinicians can run experiments on
neering, University of Toronto, Toronto, ON, Canada. the encrypted medical data without having any secret keys. In
E-mail: alhassan@ece.utoronto.ca order to finally decrypt the encrypted experiment results, the
Glenn Gulak is with the Department of Electrical and Computer Engineer-
ing, University of Toronto, Toronto, ON, Canada. researchers will need to gain access to the secret keys from
E-mail: gulak@ece.utoronto.ca the key authority system using a secure channel. This secure

2168-2194 (c) 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/JBHI.2017.2657458, IEEE Journal of
Biomedical and Health Informatics
2

channel can be a virtual private network (VPN), a secure the message out of each polynomial which helps us retrieve
physical flash drive, or any other secure way to gain access ` bits messages. Moreover, in [20], since they use the flatten
to the secret keys. operation and their matrices are broken down into bits, they
execute matrix multiplication using circular convolution rather
The first FHE scheme was proposed by Craig Gentry than using the NTT transform. This is reasonable in the case
[1], [2]. Since then, we have seen rapid development in of bit-wise multiplication, but when they tried to reduce the
the theory and implementation of homomorphic encryption computation and storage costs by grouping bits together, the
schemes. HE schemes can now be based on a variety of circular convolution became much harder without the NTT
cryptographic assumptions – approximate greatest common transform.
divisors [3], [4], learning with errors (LWE) [5], [6], [7], [8],
Ring-LWE (RLWE) [9], [10], [11], [12] and NTRU [13], Based on [5], Halevi and Shoup designed a homomorphic
[14], [15], [16], [17]. Simple computations such as matching encryption library [21], [11], but due to the need of additional
entries in a database and computing on the matched items large data structures and functions, the performance of their
were impossible using standard encryption schemes until the library was diminished. In [10] they implemented a variant of
work done in SHIELD [12] where multiple classification the RLWE FHE scheme. Our results also show considerable
functions were implemented including searching in databases speedups over their implementation. Another homomorphic
and computing on the result using a homomorphic encryption library was developed by Rohloff, Cousins, and Peikert [22].
scheme. In their paper they implement primary building blocks in
hardware to accelerate their system. Presently, there are no
The main contributions of this work is the introduction performance results available with which to compare our
of a NTRU based version of SHIELD [12] to reduce its library. Our work is a NTRU variant of SHIELD [12] which
computational complexity by a factor of 4.15×. Our GPU was based on RLWE. This resulted in a 4× reduction in the
implementation of the HE scheme acheives a ciphertext (Ctxt) ciphertext size and 2× speedup in performance compared
multiplication run time of 0.838 milliseconds, and the CPU to [12]. Other researchers have proposed implementations
implementation requires 87.8 milliseconds (See Table V for but they were either an incomplete implementations of an
the design environment). Our CPU implementation acheives a HE scheme capable of only performing one multiplication
speedup of 58× over work in [18]. Our GPU implementation operation [23], or based on other cryptographic assumptions
gives us a further 104× (and 410×) speedup with overall such as approximate greatest common divisor, ideal lattices,
speedup of 6085× (and 24011×) over [18] using a single etc.
GPU (and four GPUs), respectively.
Some applications analyzed in this paper were primarily
This paper is organized as follows. Section II presents inspired from [24], [18], [25]. The work in [18] exhibits
related work. In Section III we introduce the improved en- slow running time. The work in [24] on the other hand has
cryption scheme. Some examples of secure medical applica- considerably faster running times but at the expense of having
tions are introduced in Section IV. Performance results are an incomplete implementation of the HE scheme that needs
introduced in Section VI. Finally we conclude in Section VII. to provide the client with information about the depth of the
computation made in order to correctly decrypt the result.
The authors in [24] mentioned a slowdown by a factor of
II. R ELATED W ORK
50× when using the complete HE implementation. This may
NTRU is a ring-based encryption scheme first proposed raise security concerns from the server side due to the leakage
in [13]. Previous constructions of ring-based FHE schemes of some of information about the applied function. In [26]
including NTRU are [14], [15], [5], [6], [11]. One of the Fujitsu laboratories used simple polynomial multiplication to
drawbacks of these schemes is the need to maintain a compute correlation between different biometric samples but
so-called “modulus chain” which increases the size of the their performance is not representative since their function
prime number and consequently increases the ring dimension F = C1 × C2 needs only a single ciphertext multiplication.
for the same security level [19]. They also need to perform For a simple and general overview of homomorphic encryption
expensive modulus and key switching operations. In [14], concepts the reader is encouraged to read [27], [28].
[15], their homomorphic evaluations are on plaintexts mod
2 (binary arithmetic). Furthermore, the evaluation keys used
III. T HE E NCRYPTION S YSTEM
in the Ctxt multiplication are in the GByte range which
significantly limits their performance. The work in [20] is the Notation: For an odd prime number q we identify the ring
closest one to our work since they also combined the NTRU Z/qZ (or Zq ) with the interval (−q/2, q/2) ∩ Z. The nota-
scheme with GSW scheme concepts in [7]. Yet, in [20], they tion [x]q denotes reducing x modulo q. Our implementation
still require the flatten operation in the GSW scheme which uses polynomial rings defined by the cyclotomic polynomials
leads to large memory usage and more computation time. R = Z[X]/Φm (X), where Φm (X) = xn +1 is the irreducible
They are also able to decrypt only a single bit from one mth cyclotomic polynomial, in which n is a power of 2 and
polynomial and discard the remaining ` − 1 polynomials. m = 2n. We let Rq = R/qR. Any type of multiplication
Whereas in our implementation, we extract a single bit of including matrix and polynomial multiplication is denoted by

2168-2194 (c) 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/JBHI.2017.2657458, IEEE Journal of
Biomedical and Health Informatics
3

the multiplication operator ’·’. Rounding up to the nearest

0 ···
 
integer is denoted by dae. Matrices of rings are defined as 1 0 0
AM ×N , where Aij ∈ Rq and M, N are the matrix dimensions.  2 0 0 ··· 0 
.. .. .. . . ..
 
I`×` represents the identity matrix of rings. 
 . . . . .


 `−1 
2
 0 0 ··· 0 

 0
 1 0 ··· 0 

 0 2 0 ··· 0 
 .. .. .. . . ..
 

 . . . . . 
A. The Encryption Scheme αy`×y =  (1)
 0
 2`−1 0 ··· 0 

 0
 0 1 ··· 0 

 . .. .. .. ..
 ..

The parameters of the system are n, the degree of the . . . . 
 
number field; q, the modulus; σk and σc , the standard  0 0 0 ··· 1 
 
deviation of the discrete Gaussian error distribution in the  0 0 0 ··· 2 
∆
key space and ciphertext space respectively; ` = dlog qe that
 
 . .. .. . . ..
 ..

governs the number of ring elements in a ciphertext. The . . . . 
setting of these parameters depends on the security level 0 0 0 ··· 2`−1
λ (e.g., λ = 80 or 128 bits) as well as the complexity of In this work, we present a NTRU variant of the encryption
functions we expect to evaluate on ciphertexts. scheme presented in [12] in order to reduce computational
complexity and to speedup our operations, as will be detailed
Bit Decompose Function “BD()”: The bit decompose below. Our encryption system works as follows.
function BD(integer) takes an `-bit input integer, then outputs λ
• Keygen(1 ): Choose two polynomials f1×1 , g1×1 ←
a row vector with size ` containing the bit decomposition DZn ,σk such that (a) f is invertible in the ring Rq ; and
of this integer. Similarly, BD(polynomial) takes an input (b) f ≡ 1 (mod 2). This is done by simply sampling
polynomial of size n, where each coefficient is an `-bit the polynomial f from the distribution DZn ,σk until it
integer, then outputs an `-sized row vector of polynomials satisfies conditions (a) and (b).
(each of size n) containing the bit decomposition of each
coefficient of the input polynomial, yielding a matrix of size The public key pk and the secret key sk can be computed
l × n. Finally, BD(Matrix of polynomials) takes an input from (2).
matrix of polynomials of size x × y (each polynomial is of
size n with integer coefficients), then outputs a matrix of −1
polynomials expanded by a factor ` in the column dimension, pk = h1×1 = g1×1 · f1×1 ∈ Rq sk = f1×1 ∈ Rq (2)
yielding a matrix of size x × y`, where each consecutive ` • Enc(pk, m): The message space of our encryption scheme
elements along the row contain the bit representation of each is Rq . Encrypt the plain text polynomial µ ∈ Rq by
coefficient of each of the input polynomials. For example, calculating
the bit decompose of the input polynomial matrix Bx×y×n
is BD(Bx×y×n ) = βx×y`×n . The reader should note that C`×1 = µ · BDI(I`×` ) + S`×1 · h1×1 + E`×1 (3)
despite the fact that the polynomial coefficients of matrix
βx×y`×n are single bit values, the storage requirement of where S`×1 , E`×1 ← DRq`×1 ,σc are sampled from a
matrix β in CPU or GPU memory is not equal to x × y` × n discrete Gaussian distribution with standard deviation σc .
bits. This is due to the fact that the smallest addressable • Dec(sk, C): Given the ciphertext C, the plaintext
unit of memory is a byte (i.e., Byte Addressable). Hence, µ ∈ Rq is restored by multiplying C by the secret-
β requires x × y` × n bytes of storage. This results in the key f as follows :
further observation that the storage requirement of βx×y`×n
is 8× the storage requirement of Bx×y×n . C`×1 · f1×1 = (µ · BDI(I`×` )
+ S`×1 · h1×1 + E`×1 ) · f1×1
Bit Decompose Inverse Function “BDI()”: As the name
= µ · BDI(I`×` ) · f1×1
reveals, the BDI() function is the inverse of BD(). The
BDI() function groups consecutive ` coefficients along a + S`×1 · h1×1 · f1×1 + E`×1 · f1×1
row (the coefficients don’t need to be binary), and outputs = µ · BDI(I`×` ) · f1×1
the integer corresponding to those ` bits. Mathematically, + S`×1 · g1×1 + E`×1 · f1×1
the BDI() function can be defined as multiplying the
= µ · BDI(I`×` ) · f1×1 + error`×1 .
expanded matrix of polynomials βx×y` from the right by
(4)
the matrix αy`×y defined in (1) (polynomial dimension n
will be omitted from this point forward for clarity). Hence The decrypted Ctxt in (4) can be reformulated as in (5)
Bx×y = BDI(βx×y` ) = βx×y` · αy`×y . and the bit representation of each coefficient µfi of the
µf polynomial can be represented as in (6).

2168-2194 (c) 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/JBHI.2017.2657458, IEEE Journal of
Biomedical and Health Informatics
4

The correctness of the multiplication operation is evident


1
 from the decryption operation in (8). Matrix dimensions are
  2 removed for clarity.
C`×1 · f1×1 = µf ·   + error`×1
 
..
  . BD(C) · D · f = BD(C) · (µ2 · BDI(I) + S2 · h + E2 ) · f
`−1
2 = BD(C) · (µ2 · BDI(I) · f + S2 · g + E2 · f )
  (5)
µf = µ2 · C · f + BD(C) · (S2 · g + E2 · f )
 2µf 
=  .  + error`×1
  = µ2 · (µ1 · BDI(I) · f + S1 · g + E1 · f )
 .. 
+ BD(C) · (S2 · g + E2 · f )
2`−1 µf
= µ2 · µ1 · BDI(I) · f + µ2 · (S1 · g + E1 · f )
  + BD(C) · (S2 · g + E2 · f )
µfi = (µfi )`−1 (µfi )`−2 · · · (µfi )2 (µfi )1 (µfi )0
(6) = µ2 · µ1 · BDI(I) · f + µ2 · error1
The result in (5) consists of an `×1 vector of polynomials + BD(C) · error2
`−1
which are in the form µf, 2µf, · · · , 2 µf in addition = µ2 · µ1 · BDI(I) · f + error.
to the error vector. Ignoring the modular reduction effect (8)
for simplicity, which would effect only the lower bits, the
shifted versions of µf can be visualized as in (7). Note that the last line in (8) is the encryption of µ = µ2 ·µ1 ·f .
Note also that BD(C`×1 ) · BDI(I`×` ) = I`×` · C`×1 = C.
   
µf (µf )`−1 ··· (µf )1 (µf )0
 2µf  (µf )`−2 ··· (µf )0 0  Noise Analysis: Correct decryption depends crucially on the
..  (7) ciphertext noise being bounded. Thus, it is important to
   
 ..   .. .. ..
 . = . . . .  understand how homomorphic operations increase ciphertext
   
`−2
2 µf   (µf )1 (µf )0 ··· 0  noise. Let C be a fresh ciphertext. We make the following
2`−1 µf (µf )0 0 ··· 0 observations, after [8].
Note that the left most column of the result in (7) are the • Homomorphic addition of v ciphertexts increases the
individual bits of the µf polynomial. This is true for each noise by a factor of v, in the worst case. In practice,
coefficient “i” in the polynomial µf . This way we can since the coefficients of the error polynomials √follow a
successfully construct back µf , assuming that the error Gaussian distribution, the factor is closer to O( v).
is less than q/2, which can then be multiplied by f −1 to • Homomorphic multiplication is significantly more inter-
recover µ. esting. Multiplication of two fresh ciphertexts Z1 =
Remark: In addition to the ability to recover the message C1 × C2 where C1 = Enc(µ1 ) and C2 = Enc(µ2 ), with
polynomial µ, the ` ring elements in the ciphertext facilitate the messages µi bounded by κ and error bounded by B,
and manage the noise growth in homomorphic operations (in increases the error (E2 ) to E2 = O(B ·kκk1 +B √ ·n log q)
particular, homomorphic multiplication) as we will describe in the worst case, and E2 = O(B ·kκk1 +B · n log q) in
shortly. practice. Here, kµk1 denotes the `1 norm of the message
1) Homomorphic Operations: For input ciphertexts C`×1 polynomial µ. Multiplying by another fresh Ctxt Z2 =
and D`×1 ∈ Rq`×1 encrypting µ1 and µ2 respectively, homo- Z1 ×C3 increases the error to E3 = E2 ·kκk1 +B·n log q.
morphic operations are defined as follows. Substituting with E2
• ADD(C, D): To add the two ciphertexts C`×1 and D`×1 ,
E3 = (B · kκk1 + B · n log q) · kκk1 + B · n log q
simply output C`×1 + D`×1 , which is an entry-wise
addition. = B · kκk21 + B · kκk1 · n log q + B · n log q (9)
=B· (kκk21 + (kκk1 + 1) · n log q)
• MULT(C, D): To multiply the two ciphertexts C`×1 and
Following this analysis, multiplying L sequential Ctxts
D`×1 , output BD(C`×1 ) · D`×1 .
will increase the error to
Correctness of homomorphic addition is immediate, EL = B · (kκkL−1
1 + (kκkL−2
1 + kκkL−3
1 + · · · + 1) · n log q)
however correctness is not that obvious for homomorphic 1 − kκkL−1
multiplication. It is clear that the multiplication algorithm is = B · (kκkL−1
1 + 1
· n log q)
1 − kκk1
asymmetric in the input ciphertexts C and D. That is, we treat (10)
the components of D as a whole, whereas the components of
C are broken up into their “bit-wise decompositions”. This How to Set Parameters: We base the security of our system
is a “feature” that is inherited from the work of BV [8]. It is relying on the analysis in [17], [19], and [29]. Let f be the
shown below that this multiplication method is correct and function that we are evaluating that computes the multiplica-
gives a slow noise-growth rate. tion of v ciphertexts. Let errorf (B, n, q) denote how much the
error grows when evaluating a function f on ciphertexts in Rq

2168-2194 (c) 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/JBHI.2017.2657458, IEEE Journal of
Biomedical and Health Informatics
5

Table I: Parameter Selection and Keys/Ctxt Sizes.

with an initial error of magnitude B. For correct decryption,
we need
Parameter NTRU (This work)
errorf (B, n, q) < q/2 (11)
λ 173
Since error grows slower in our scheme relative to other FHE n 1024
schemes [18], [24], [25], and since there is no need for a ` 31
σk 25
chain of moduli to control the noise growth, q can be set to be σc 10
correspondingly smaller for the same security level. Following SK size n × ` = 3.968 KBytes
the analysis of Lindner and Peikert [19], for a security level PK size n × ` = 3.968 KBytes
of λ bits, we need Ctxt size ` × n × ` = 123.008 KBytes

n > log(q/σ)(λ + 110)/7.2 (12)

Since our log q is smaller relative to [18], [24], [25], we can Substituting log(n) = 10 in (16) results in min(log(q)) =
set our n to be smaller, for the same security level λ. In 48 bits which offers a safe margin from the log(q) = 31 bits
turn, since we now have a smaller n, our new errorf (B, n, q) used in this work. In addition, we sample the polynomials f
is smaller, leading to an even smaller q, and so on. The and g from a Gaussian distribution with standard deviation
optimal parameters are obtained by solving both the above σk = 25, not from [−1, 0, 1]. This improves our security level
inequalities together. since it is directly proportional to σ, as can be deduced from
(12) and (15).
We are aware that the analysis done in [19] was made by
using the older BKZ not the new, more efficient, BKZ 2.0 IV. C ANDIDATE A PPLICATIONS
algorithm [30]. This is because Lindner-Peikert equations
result in more conservative parameters than the ones from We chose to outline some candidate applications, first
BKZ 2.0, as reported in [31], [32]. outlined in [24], [18], [25], in order to be able to compare
the performance of our method.
To protect our NTRU scheme against Subfield Lattice At-
tacks [29], the “perfect immunity”, as described by the authors, A. Relational Operations
can be achieved when Originally, homomorphic addition and multiplication were
√ p the only available operations that can be applied on encrypted
2 · σk2 · ǹ > ǹq/πe (13) data. Afterwards, [12], [25] implemented a homomorphic
equality operation through comparing individual bits of the
where ǹ = n/2. Fixing q and ǹ, the parameter σk should
encrypted data. Homomorphic relational operations > and
satisfy (14).
< can enable new applications. The idea was originally
presented in [34] where they introduced the idea of conditional
r
q
σk > 4 (14) gates. Later in [25] they applied this idea to homomorphic
2ǹπe
encryption. The relational operations a > b results in one bit
which results in the condition that σk should be larger than only, which is equal to 1 if a > b, and 0, otherwise. Individual
or equal 23. The vulnerability factor1 (15) is a ratio which bits of each input a and b are encrypted and denote them as
represents the extent to which this NTRU scheme is vulnerable ai and bi , respectively. Assume we have k-bit numbers, we
to subfield lattice attacks. The scheme is immune when F < 1. start with the least significant bit and the output is given by
p zk , where
ǹq/πe
F = √ 2 (15)
2σk ǹ
z0 = 0 zi+1 = (1 − (ai − bi )2 )zi + ai (1 − bi ). (17)
We set σk = 25 to achieve vulnerability factor F = 0.79.
Table I summarizes our final parameter selection. if any of the two inputs were not encrypted, the complexity of
(17) can be greatly reduced. For example, if b is not encrypted,
Our encryption scheme is also immune against the recent the resulting equations will be
attack on NTRU in [33]. Using the data in [33] (Table 2, Fig-
ure 1), which use polynomials f and g sampled from [−1, 0, 1],
(
(1 − ai )zi + ai if bi = 0
to extrapolate a generalized equation for the minimum log(q) z0 = 0, zi+1 = (18)
below which the algorithm in [33] fails2 , results in (16). ai zi if bi = 1
Blood Pressure Test: As a proof of concept of the benefits
min(log(q)) = 1.0127e0.3867 log(n) (16)
of the homomorphic relational operations, a secure blood
1 Equation (13) only indicates sufficiency to achieve perfect immunity, but pressure application was built. The application simply accepts
it does not indicate to what extent the encryption scheme is vulnerable against the encrypted systolic and diastolic pressures and returns the
subfield lattice attacks. This is represented by the vulnerability factor F blood pressure classification according to Table II.
in (15).
2 We use the points in Table 2 / Figure 1 in [33] with log(r) = 1 and 2 to To implement this blood pressure example, we compare
get the worst case min(log(q)). the input blood pressure to multiple ranges to decide the

2168-2194 (c) 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/JBHI.2017.2657458, IEEE Journal of
Biomedical and Health Informatics
6

Table II: Blood Pressure Classification

and multiply the results. The only downside to this approach
Category Systolic mm Hg Diastolic mm Hg is that in our encryption scheme, in fact all GSW derived
Hypotension < 90 < 60 schemes in general, the homomorphic multiplication is
Desired 90 − 119 60 − 79 asymmetric preventing the possibility of multiplying two
Prehypertension 120 − 139 80 − 89 non-fresh Ctxts. We mean by non-fresh Ctxts the Ctxts that
Stage 1 hypertension 140–159 90–99
contain results of Ctxt multiplications. In order to overcome
Stage 2 hypertension 160–179 100–109
Hypertensive emergency ≥ 180 ≥ 110 this challenge, we reformulated the equations for a < b < c
such that they always multiply fresh Ctxts by an accumulator.

Function 1: Secure Blood Pressure Classification “a < b < c” Reformulated: As mentioned, to implement
Input: Encrypted Blood Pressure Sys Enc, Dia Enc such a function we could multiply the results of individual
Output: Blood Pressure Classification relational operations. We used this idea to re-format the
equations needed to implement this function. For a k-bit input
Sys Ref = [90, 120, 140, 160, 180] “b” with encrypted bits [b0 , b1 , · · · , bk−1 ] compared against
Dia Ref = [60, 80, 90, 100, 110]
For each number “i” in the reference lists { “a” and “c” (encrypted or unencrypted) we can implement
Res Sys += Check Greater(Sys Enc, Sys Ref[i]); the function a < b < c as follows: First we define for bit “0”
Res Dia += Check Greater(Dia Enc, Dia Ref[i]);
} x0 = b0 (1 − a0 ) y0 = c0 (1 − b0 ) z0 = 0. (19)
Return Res Sys and Res Dia
and then for each bit “i”

xi+1 =(1 − (bi − ai )2 )xi + bi (1 − ai )

blood pressure classification. This can be simply done using
yi+1 =(1 − (ci − bi )2 )yi + ci (1 − bi )
Function 1. The Res Sys and Res Dia parameters in Function
1 will each contain an encrypted number ranging from 0 to zi+1 =(1 − (bi − ai )2 )(1 − (ci − bi )2 )zi
5 indicating the classification of the input encrypted blood + (1 − (bi − ai )2 )ci (1 − bi )xi
pressure measurements compared to the blood pressure range + (1 − (ci − bi )2 )bi (1 − ai )yi (20)
in the systolic Sys Ref and diastolic Dia Ref reference lists,
respectively. where xi , yi , zi are accumulators, bi is encrypted bit i of
input b, and ai , ci are the bits of the lower and upper bounds,
It is worth mentioning that the relational operation respectively. zk will contain the result of the relational
applications are numerous. The blood pressure example is operation. In the case that ai and ci are plaintexts, equations
just an illustrative example of its usefulness and power. (20) can be further simplified as in (18).
For example, calculating the CHADS2 Score for Atrial
Fibrillation Stroke Risk is straightforward [35] in a similar It is worth mentioning that the number of Ctxt multiplica-
manner. tions needed for this circuit, in the case of plaintext a and
c, are 8 multiplications per bit, compared to only 2 Ctxts
Framingham Coronary Heart Disease Risk Score (FCRS): multiplications per bit for other HE schemes that supports
The FCRS is an algorithm used to estimate the 10-year multiplying two non-fresh Ctxts.
cardiovascular risk of a person. For more information about
this algorithm, the reader is referred to [36], [37]. The
B. Encrypted Genomic Data
algorithm is based on several factors, including sex, age,
cigarette smoking, total cholesterol, high-density lipoprotein In [24] the authors described statistical algorithms used
(HDL) cholesterol, and systolic blood pressure. Each variable in genomic association studies. In this paper, we briefly
is compared against a range of numbers and a score is summarize some of their algorithms namely the Pearson
assigned for each range and added to the overall Framingham Goodness-of-Fit test and the Cochran-Armitage test for Trend
score. For example, if a man’s age was ≥50 years, 6 points (CATT). For more information about equation derivations we
are added to the total score. refer the reader to [24].

To implement this algorithm, the relational operations In order to implement the algorithms presented in [24],
described in Section IV-A are not sufficient because it gives genotypes and phenotypes are encoded and encrypted as
a “1” if the input is larger than a certain number and “0” follows:
otherwise. If we have an input “b” compared against “a”
as a lower bound and “c” as an upper bound, we need to Genotype Encoding: As in [24], a table containing genotype
implement a < b < c function which gives only a “1” if “b” information is constructed in which each row corresponds
is within this range and “0” otherwise. to genotype information about a single person. For bi-allelic
genes, each person’s gene is encoded using three ciphertexts
The straight-forward way to implement a < b < c, is to cAA , cAa , caa . These ciphertexts will encrypt a “1” only in the
implement it in two steps, namely a < b and then b < c case that the equality statement in (21) is satisfied, otherwise

2168-2194 (c) 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/JBHI.2017.2657458, IEEE Journal of
Biomedical and Health Informatics
7

they encrypt “0”. For the case that the person’s genotype at
2
X 2
the specified locus is not known, all Ctxts will encrypt “0”.
α=N wi (N0i R1 − N1i R0 ) (26)
i=0
cAA = Enc(gene == AA)
2
cAa = Enc(gene == Aa)
X 
(21)
β = R0 R1 wi2 Ci (N − Ci ) − 2w1 w2 C1 C2 (27)
caa = Enc(gene == aa) i=0

Genotype/Phenotype Correlation Encoding: We modified X

the phenotype encoding compared to [24] in order to reduce (i)
Nxy = zxy , where x ∈ {0, 1}, y ∈ {0, 1, 2} (28)
pre-computation time and to have less noise in the final i
encrypted result. This will allow us to further compute on where wi are predetermined weights ∈ {0, 1, 2} as described
the resulting ciphertext if needed. We generate a correlation in [24], Nij represents the number of individuals who are
matrix between genotypes {AA, Aa, aa} and phenotypes affected/unaffected with a certain disease and have genotype
{affected, unaffected} to generate a 3 × 2 correlation matrix ij as in (28). The parameters Nij , Ri , Ci are described in
with Ctxts encrypting a “1” at a single location corresponding Table IV.
to this person’s genotype/phenotype condition, “0” otherwise,
as shown in Table III. If the genotype or phenotype of this Table IV: Affected/Unaffected Genes Statistics
person is unknown, then all Ctxts will be encrypting a “0”. AA Aa aa Sum
Unaffected N00 N01 N02 R0
Table III: Genotype/Phenotype Correlation Matrix
Affected N10 N11 N12 R1
AA Aa aa Sum C0 C1 C2 N
Unaffected z00 z01 z02
Affected z10 z11 z12

Pearson Goodness-of-Fit Test: This test is used to check if C. Predictive Analysis

a gene is in Hardy-Weinberg Equilibrium (HWE). The HWE Predictive equations can be used to check for different
is responsible for testing if the gene allele frequencies are diseases. In order to compute the predictive equation, pa-
independent. Assume A and a are two alleles in a given gene, tients’ information must be used. To protect such informa-
and that NAA , NAa , and Naa are the corresponding number tion, homomorphic encryption can be used to encrypt these
of genotypes AA, Aa, and aa, respectively, as in (23). Let data and privately compute the regression equations [18]. To
N = NAA + NAa + Naa be the total number of genotypes. demonstrate the logistic regression analysis, in [18] they used
Since homomorphic division is expensive to perform, in [24] a model that predicts the likelihood of having a heart attack
they simplified the computations needed and computed the in an unspecified period. The predictive model is given by the
following parameters homomorphically following logistic regression function
ex
P (x) = (29)
2 2
α = (4NAA Naa − NAa ) β1 = 2(2NAA + NAa )2 ex − 1
β2 = (2NAA + NAa )(2Naa + NAa ) β3 = 2(2Naa + NAa )2 where x is represented as
(22)
where Nij can be computed as x =0.072 · a + 0.013 · sys − 0.029 · dia + 0.008 · chol
− 0.053 · ht + 0.021 · wt (30)
(i) (i)
X X X
NAA = cAA NAa = cAa Naa = c(i)
aa (23) where a is the age, sys is the systolic blood pressure, dia is
i i i the diastolic blood pressure, chol is the cholesterol level, ht
is the height, wt is the weight.
these parameters are then sent to the client to compute the
final deviation test statistic
To implement the exponential expression in (29), a Taylor
series can be used up to an acceptable order to result in a
 
2 α 1 1 1
X = + + (24) sufficient accuracy. In [18] they represented (29) up to degree
2N β1 β2 β3
7
Cochran-Armitage Test for Trend (CATT): This study is
used to determine if an allel is associated to a disease or not. ex 1 1 1 1 5 17 7
The test can be computed as P (x) = = + x− x3 + x − x +O(x9 )
−1ex 2 4 48 480 80640
(31)
α
X2 = (25) Since homomorphic encryption relies on integer arithmetic,
β (30) and (31) can be normalized with appropriate accuracy to
where the following

2168-2194 (c) 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/JBHI.2017.2657458, IEEE Journal of
Biomedical and Health Informatics
8

Table V: Design Environment.

Security Level that we substitute the reported parameters
of each encryption scheme in Equation (12) and get the
Item Specification
resulting λ. The following is a further explanation of why
CPU Intel Core-i7 5930K
# of CPU Cores 4
our parameters are smaller than the others despite the fact
# of Threads 8 that we all derived our parameters from [19]. Our work and
CPU Frequency 3.5 GHz SHIELD [12] have the same n and log q because they are
Cache Size 15 MB both based on [7]. The difference in the Ctxt and key sizes
System Memory 32 GB DDR4 are due to the translation from the RLWE to the NTRU
Operating System Windows 8.1 64-bits schemes. On the other hand, the work in [18] and [24] are
Programming IDE Visual Studio 2012 Ultimate edition
both based on [31]. In [31], log q increases with the circuit
GPU NVIDIA GeForce GTX980
Maxwell Version GM204 depth as well as with the number of least significant bits
# of CUDA Cores 2048 reserved for the plaintext log t (the condition for correctness
GPU Core Frequency 1126 MHz is q > 2 · t · error). In our scheme, log q increases only with
GPU Memory 4 GB the circuit depth, as we encode our plaintext in the most
GPU L2 Cache 2 MB significant bit of each of the log q polynomials (the condition
for correctness is q > 2 · error). Also since we use the
asymmetric property of the Ctxt multiplication in our favor,
our noise growth, as well as our parameters, are smaller for
the same circuit depth. We would like to point out that in
z = 72 · a + 13 · sys − 29 · dia + 8 · chol − 53 · ht + 21 · wt (32) [24], they did not use the 512MB evaluation key as in [18] to
speedup their ctxt operations. This came at the expense that
they generate a different secret decryption key for different
F (z) = 40320 + 20160z − 1680z 3 + 168z 5 − 17z 7 (33) circuits with different circuit depth. Also, the large log q used
Inputs to (32) and (33) are represented as integer numbers in [18], [24] along with the very small distribution used in
and encoded in binary format in adjacent polynomial slots. the key generation, χkey = {−1, 0, 1}, make these schemes
When these binary polynomials are multiplied together, they very vulnerable to the subfield lattice attacks in [29].
result in a correct output as was described in [18]. Multiplica-
Table VII summarizes the performance results of the
tion by constants in (32) were implemented through sequential
homomorphic operations for our library compared to the
additions. To compute the correct output, the result of (32) is
[12], [24], [18]. It can be seen from this table that we have
sent back to the client to be re-encrypted and applied to (33)
a 58× speedup for the multiplication operation of our CPU
to compute the final result. Again, for more details, refer to
implementation compared to work in [18]. By additionally
[18].
exploiting the parallelizable properties that our HE library
has, we get another 104× speedup by distributing the HE
V. S ECURITY AGAINST ATTACKS
computations on the GPU cores. This resulted in an overall
Our homomorphic encryption scheme and algorithms, and 6085× speedup for the multiplication operation compared to
indeed all known FHE schemes, are proven secure in the work in [18] and a 286× compared to [24].
IND-CPA sense (i.e., under a chosen plaintext attack). This
is the standard notion of security for FHE schemes as in [1], Scalability: After exploring the parallelism in our system, we
[2], [6]. The algorithms in Section IV are secure against further explored the ability for its scalability across multiple
external attackers. They are also secure against an honest but GPU instances. Experiments were made using four GPUs
curious server that wants to learn the underlying encrypted cards connected to the same CPU to measure the loss in
data without trying to actively change it. It is trivial that any performance due to cross GPU communication. By partition-
homomorphic encryption scheme can be broken by CCA2 ing large problems into small ones, we managed to schedule
(i.e., if the adversary can make decryption queries after the the work among all four GPUs to get a speedup of 3.946×,
challenge). It can also be broken by CCA1 attacks [38] (i.e., which indicates that we managed to hide almost all the
if the adversary can make decryption queries, but only before communication overhead.
the challenge). The correctness of any FHE algorithm relies
on the honesty of the server that it will execute the exact A. Candidate Applications Performance
algorithm. The performance results of the Pearson Goodness-of-fit test
and the CAAT test described in Section IV-B, the predictive
VI. P ERFORMANCE R ESULTS analysis described in Section IV-C, and the relational opera-
Design Environment: A summary of the specifications of tions and blood pressure application described in Section IV-A
the system used to implement our work for the purpose of are summarized in Table VIII. We would like to point out that
benchmarking is found in Table V. the reported results for the work in [25] corresponds to the
ring Z14 , this is because in our blood pressure example we
Table VI summarizes the sets of parameters used for our need to add more than two numbers to get the final correct
library compared to [12], [24], [18]. We mean by the Effective result.

2168-2194 (c) 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/JBHI.2017.2657458, IEEE Journal of
Biomedical and Health Informatics
9

Table VI: Comparison between the parameters in this work and in [12], [18], [24].

Parameter This Work SHIELD [12] [18] [24]

Base Scheme NTRU RLWE NTRU NTRU
Polynomial Dimension “n” 1024 1024 16384 8192
Modulus Bit Width “log q” 31 31 512 384
Plaintext Modulus 230 230 240 2n+1
Key Standard Deviation “σkey ” 25 10 1 1
Effective Security Level “λ” (12) 173 157 120 44
Vulnerability Factor “F ” (15) 0.79 N/A 3 × 1074 2.3 × 1055
Ctxt Size n · log2 q = 123KB 4 · n · log2 q = 492KB n · log q = 1024KB n · log q = 384KB
Key Size n · log q = 3.9KB 2 · n · log q = 7.9KB n · log q = 1024KB n · log q = 384KB
Evaluation Key N/A N/A n · log2 q = 512MB Required but not used
Need to Disclose Circuit Depth? No No No Yes

Table VII: Performance comparison between this work and the work in [12], [18], [24]. The tuple (n, log q) is written below each scheme.

This Work This Work SHIELD [12] GPU Work in [18] GPU Work in [24] GPU
(1024, 31) (1024, 31) (1024, 31) Speedup (16384, 512) Speedup (8192, 384) Speedup
Operation
(CPU) (GPU) (GPU) over (CPU) over (CPU) over
(msec) (msec) (msec) SHIELD (sec) [18] (sec) [24]
Encrypt 23 0.16 23 143× 0.58 3625× 0.78 4875×
Decrypt 5 1 5 5× 0.55 550× 0.74 740×
Add 0.25 0.07 0.2 2.85× 0.001 14.29× 0.003 42.86×
Multiply 87.8 0.838 3.477 4.15× 5.1 6085.92× 0.24 286.4×

Table VIII: Candidate applications performance in milliseconds. The parameter k in the relational operation application represents the
number of bits used to represent the numbers being compared. The tuple (n, log q) is written below each scheme.

This Work Work in [24] Speedup Work in [18] Speedup Speedup

Application Work in [25]
(1024, 31) (8192, 384) over [24] (16384, 512) over [18] over [25]
Pearson Goodness-of-fit Test 8.452 1360 160.9× NA NA NA NA
CAAT 22.28 3630 162.9× NA NA NA NA
Predictive Analysis (32) 0.77 NA NA 196 254.5× NA NA
Predictive Analysis (33) 13.69 NA NA 80, 000 5834.7× NA NA
Relational Operation t1 = 2.514 × k NA NA NA NA t2 = 30.75 × k 12.2×
Blood Pressure 6 × t1 NA NA NA NA 6 × t2 12.2×

VII. C ONCLUSION questions that helped us tune the parameters of our work to
We formulated, optimized, and implemented an NTRU- protect it against subfield lattice attacks. Financial support by
based variant of the HE scheme of [12], [7], [8] which achieves NSERC is greatly acknowledged.
much slower growth of noise, and thus much better parameters
than previous HE schemes. Compared to the work in [18], our R EFERENCES
GPU implementation (GM204 Maxwell architecture) acheives
[1] C. Gentry, “Fully Homomorphic Encryption Using Ideal Lattices,”
a speedup of 6085× in Ctxt multiplication, which represents in Proceedings of the 41st Annual ACM Symposium on Theory of
the bottleneck for most HE schemes. Representative med- Computing, ser. STOC ’09, New York, NY, USA, 2009, pp. 169–178.
ical applications, namely Pearson Goodness-of-fit test [24], [Online]. Available: doi.acm.org/10.1145/1536414.1536440
[2] ——, “A fully homomorphic encryption scheme,” Ph.D. dissertation,
Cochran-Armitage test for trend (CATT) [24], predictive anal- Stanford University, 2009, crypto.stanford.edu/craig.
ysis [18], and relational operations [25] were implemented [3] J.-S. Coron, A. Mandal, D. Naccache, and M. Tibouchi, “Fully
and scored speedups of 160.9×, 162.9×, 80000×, and 12.2×, Homomorphic Encryption over the Integers with Shorter Public
Keys,” in Advances in Cryptology – CRYPTO 2011, ser. Lecture
respectively. Notes in Computer Science, P. Rogaway, Ed. Springer Berlin
Heidelberg, 2011, vol. 6841, pp. 487–504. [Online]. Available:
ACKNOWLEDGMENT dx.doi.org/10.1007/978-3-642-22792-9 28
[4] M. Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan, “Fully
We would like to thank the authors of [29] Martin Albrecht, Homomorphic Encryption over the Integers,” in Advances in Cryptology
Shi Bai, and Léo Ducasthe for their insightful replies to our – EUROCRYPT 2010, ser. Lecture Notes in Computer Science,

2168-2194 (c) 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/JBHI.2017.2657458, IEEE Journal of
Biomedical and Health Informatics
10

H. Gilbert, Ed. Springer Berlin Heidelberg, 2010, vol. 6110, pp. mance Extreme Computing (HPEC), 2012 IEEE Conference on, 2012,
24–43. [Online]. Available: dx.doi.org/10.1007/978-3-642-13190-5 2 pp. 1–5.
[5] Z. Brakerski, C. Gentry, and V. Vaikuntanathan, “(Leveled) Fully [23] M. Yasuda, T. Shimoyama, J. Kogure, K. Yokoyama, and T. Koshiba,
Homomorphic Encryption Without Bootstrapping,” in Proceedings of “Secure pattern matching using somewhat homomorphic encryption,” in
the 3rd Innovations in Theoretical Computer Science Conference, Proceedings of the 2013 ACM Workshop on Cloud Computing Security
ser. ITCS ’12, New York, NY, USA, 2012, pp. 309–325. [Online]. Workshop, ser. CCSW ’13, New York, NY, USA, 2013, pp. 65–76.
Available: doi.acm.org/10.1145/2090236.2090262 [Online]. Available: http://doi.acm.org/10.1145/2517488.2517497
[6] Z. Brakerski and V. Vaikuntanathan, “Efficient Fully Homomorphic [24] K. Lauter, A. Lopez-Alt, and M. Naehrig, “Private Computation on
Encryption from (Standard) LWE,” in Foundations of Computer Science Encrypted Genomic Data,” Tech. Rep. MSR-TR-2014-93, June 2014,
(FOCS), 2011 IEEE 52nd Annual Symposium on, 2011, pp. 97–106. http://research.microsoft.com/apps/pubs/default.aspx?id=219979.
[7] C. Gentry, A. Sahai, and B. Waters, “Homomorphic Encryption from [25] J. H. Cheon, M. Kim, and M. Kim, “Search-and-compute on encrypted
Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, data,” in Financial Cryptography and Data Security: FC 2015
Attribute-Based,” in Advances in Cryptology – CRYPTO 2013, ser. International Workshops, BITCOIN, WAHC, and Wearable, San Juan,
Lecture Notes in Computer Science, R. Canetti and J. Garay, Eds. Puerto Rico, January 30, 2015, Revised Selected Papers. Berlin,
Springer Berlin Heidelberg, 2013, vol. 8042, pp. 75–92. [Online]. Heidelberg: Springer Berlin Heidelberg, 2015, pp. 142–159. [Online].
Available: dx.doi.org/10.1007/978-3-642-40041-4 5 Available: http://dx.doi.org/10.1007/978-3-662-48051-9 11
[8] Z. Brakerski and V. Vaikuntanathan, “Lattice-based FHE As Secure [26] M. Yasuda, T. Shimoyama, J. Kogure, K. Yokoyama, and T. Koshiba,
As PKE,” in Proceedings of the 5th Conference on Innovations in “Packed Homomorphic Encryption Based on Ideal Lattices and Its
Theoretical Computer Science, ser. ITCS ’14, New York, NY, USA, Application to Biometrics,” in Security Engineering and Intelligence
2014, pp. 1–12. [Online]. Available: doi.acm.org/10.1145/2554797. Informatics, ser. Lecture Notes in Computer Science, A. Cuzzocrea,
2554799 C. Kittl, D. Simos, E. Weippl, and L. Xu, Eds. Springer
[9] ——, “Fully Homomorphic Encryption from Ring-LWE and Security Berlin Heidelberg, 2013, vol. 8128, pp. 55–74. [Online]. Available:
for Key Dependent Messages,” in Advances in Cryptology – CRYPTO http://dx.doi.org/10.1007/978-3-642-40588-4 5
2011, ser. Lecture Notes in Computer Science, P. Rogaway, Ed. [27] C. Aguilar-Melchor, S. Fau, C. Fontaine, G. Gogniat, and R. Sirdey,
Springer Berlin Heidelberg, 2011, vol. 6841, pp. 505–524. [Online]. “Recent Advances in Homomorphic Encryption: A Possible Future
Available: dx.doi.org/10.1007/978-3-642-22792-9 29 for Signal Processing in the Encrypted Domain,” Signal Processing
[10] M. Naehrig, K. Lauter, and V. Vaikuntanathan, “Can Homomorphic Magazine, IEEE, vol. 30, no. 2, pp. 108–117, 2013.
Encryption Be Practical?,” in Proceedings of the 3rd ACM Workshop [28] B. Hayes, “Alice and Bob in Cipherspace,” ser. American Scientist,
on Cloud Computing Security Workshop, ser. CCSW ’11, New York, 2012, vol. 100, no. 5, pp. 362–367.
NY, USA, 2011, pp. 113–124. [Online]. Available: doi.acm.org/10. [29] L. D. Martin Albrecht, Shi Bai, “A subfield lattice attack on over-
1145/2046660.2046682 stretched NTRU assumptions: Cryptanalysis of some FHE and Graded
[11] C. Gentry, S. Halevi, and N. Smart, “Homomorphic Evaluation of the Encoding Schemes,” Cryptology ePrint Archive, Report 2016/127, 2016,
AES Circuit,” in Advances in Cryptology – CRYPTO 2012, ser. Lecture http://eprint.iacr.org/2016/127.
Notes in Computer Science, R. Safavi-Naini and R. Canetti, Eds. [30] Y. Chen and P. Q. Nguyen, BKZ 2.0: Better Lattice Security Estimates.
Springer Berlin Heidelberg, 2012, vol. 7417, pp. 850–867. [Online]. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 1–20.
Available: dx.doi.org/10.1007/978-3-642-32009-5 49 [Online]. Available: http://dx.doi.org/10.1007/978-3-642-25385-0 1
[12] A. Khedr, G. Gulak, and V. Vaikuntanathan, “SHIELD: Scalable Homo- [31] J. W. Bos, K. Lauter, J. Loftus, and M. Naehrig, “Improved Security
morphic Implementation of Encrypted Data-Classifiers,” IEEE Transac- for a Ring-Based Fully Homomorphic Encryption Scheme,” Cryptology
tions on Computers, vol. 65, no. 9, pp. 2848–2858, Sept 2016. ePrint Archive, Report 2013/075, 2013, http://eprint.iacr.org/.
[32] T. Lepoint and M. Naehrig, A Comparison of the Homomorphic
[13] J. Hoffstein, J. Pipher, and J. Silverman, “NTRU: A ring-based
Encryption Schemes FV and YASHE. Springer International Publishing,
public key cryptosystem,” in Algorithmic Number Theory, ser.
2014, pp. 318–335. [Online]. Available: http://dx.doi.org/10.1007/
Lecture Notes in Computer Science, J. Buhler, Ed. Springer Berlin
978-3-319-06734-6 20
Heidelberg, 1998, vol. 1423, pp. 267–288. [Online]. Available:
[33] P. Kirchner and P.-A. Fouque, “Comparison between Subfield and
http://dx.doi.org/10.1007/BFb0054868
Straightforward Attacks on NTRU,” Cryptology ePrint Archive, Report
[14] W. Wang, Y. Hu, L. Chen, X. Huang, and B. Sunar, “Accelerating fully
2016/717, 2016, http://eprint.iacr.org/2016/717.
homomorphic encryption using GPU,” in High Performance Extreme
[34] B. Schoenmakers and P. Tuyls, “Practical Two-Party Computation
Computing (HPEC), 2012 IEEE Conference on, 2012, pp. 1–5.
Based on the Conditional Gate,” in Advances in Cryptology -
[15] Y. Doroz, Y. Hu, and B. Sunar, “Homomorphic AES Evaluation ASIACRYPT 2004, ser. Lecture Notes in Computer Science, P. Lee, Ed.
using NTRU,” Cryptology ePrint Archive, Report 2014/039, 2014, Springer Berlin Heidelberg, 2004, vol. 3329, pp. 119–136. [Online].
http://eprint.iacr.org/. Available: http://dx.doi.org/10.1007/978-3-540-30539-2 10
[16] Y. Doroz, B. Sunar, and G. Hammouri, “Bandwidth Efficient PIR from [35] B. F. Gage, C. van Walraven, L. Pearce, R. G. Hart, P. J. Koudstaal,
NTRU,” in Cryptology ePrint Archive, 2014, pp. 1–12. B. Boode, and P. Petersen, “Selecting Patients With Atrial Fibrillation
[17] A. López-Alt, E. Tromer, and V. Vaikuntanathan, “On-the-fly Multiparty for Anticoagulation: Stroke Risk Stratification in Patients Taking
Computation on the Cloud via Multikey Fully Homomorphic Aspirin,” Circulation, vol. 110, no. 16, pp. 2287–2292, 2004. [Online].
Encryption,” in Proceedings of the Forty-fourth Annual ACM Available: http://circ.ahajournals.org/content/110/16/2287.abstract
Symposium on Theory of Computing, ser. STOC ’12. New [36] P. W. F. Wilson, R. B. D’Agostino, D. Levy, A. M. Belanger,
York, NY, USA: ACM, 2012, pp. 1219–1234. [Online]. Available: H. Silbershatz, and W. B. Kannel, “Prediction of Coronary Heart
http://doi.acm.org/10.1145/2213977.2214086 Disease Using Risk Factor Categories,” Circulation, vol. 97, no. 18,
[18] J. W. Bos, K. Lauter, and M. Naehrig, “Private predictive analysis pp. 1837–1847, 1998. [Online]. Available: http://circ.ahajournals.org/
on encrypted medical data.,” in Journal of biomedical informatics. content/97/18/1837.abstract
Elsevier Inc., 2014, pp. 234–243. [Online]. Available: http://www.ncbi. [37] R. B. D’Agostino, R. S. Vasan, M. J. Pencina, P. A. Wolf, M. Cobain,
nlm.nih.gov/pubmed/24835616 J. M. Massaro, and W. B. Kannel, “General Cardiovascular Risk
[19] R. Lindner and C. Peikert, “Better Key Sizes (and Attacks) for Profile for Use in Primary Care: The Framingham Heart Study,”
LWE-based Encryption,” in Proceedings of the 11th International Circulation, vol. 117, no. 6, pp. 743–753, 2008. [Online]. Available:
Conference on Topics in Cryptology: CT-RSA 2011, ser. CT-RSA’11. http://circ.ahajournals.org/content/117/6/743.abstract
Berlin, Heidelberg: Springer-Verlag, 2011, pp. 319–339. [Online]. [38] M. Chenal and Q. Tang, “On Key Recovery Attacks against
Available: http://dl.acm.org/citation.cfm?id=1964621.1964651 Existing Somewhat Homomorphic Encryption Schemes,” in The third
[20] Y. Doröz and B. Sunar, “Flattening NTRU for Evaluation Key Free Ho- International Conference on Cryptology and Information Security in
momorphic Encryption,” Cryptology ePrint Archive, Report 2016/315, Latin America, Latincrypt 2014, 2014, pp. 1–28. [Online]. Available:
2016, http://eprint.iacr.org/. https://orbilu.uni.lu/handle/10993/18106
[21] S. Halevi and V. Shoup. (2013) Design and Implementation of a
Homomorphic-Encryption Library. researcher.ibm.com/researcher/files/
us-shaih/he-library.pdf.
[22] D. Cousins, K. Rohloff, C. Peikert, and R. Schantz, “An update on
SIPHER (Scalable Implementation of Primitives for Homomorphic
EncRyption) ; FPGA implementation using Simulink,” in High Perfor-

2168-2194 (c) 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/JBHI.2017.2657458, IEEE Journal of
Biomedical and Health Informatics
11

Alhassan Khedr received his M.Sc and B.Sc de-

grees from Electronics and Electrical Communica-
tions Engineering Department, Faculty of Engineer-
ing, Cairo University, Cairo, Egypt in 2008 and 2011
respectively. After graduation, he was appointed as
a Teaching Assistant in Cairo University and Amer-
ican University of Cairo for 3 years. He received
numerous awards for his excellence as a student
and as a teaching assistant. He was among the team
responsible for developing and fabricating CUS-
PARC the first fully developed Egyptian embedded
processor. Alhassan joined Electronics and Computer Engineering Department
at University of Toronto to pursue his PhD degree in 2011. Alhassan main
research interests include algorithm optimization and VLSI implementation of
high performance algorithms. He is also interested in parallel and multi/many
core processor architecture design and computer arithmetic.

Dr. Glenn Gulak is a Professor in the Department

of Electrical and Computer Engineering at the Uni-
versity of Toronto. He is a Senior Member of the
IEEE and a registered Professional Engineer in the
Province of Ontario. His present research interests
are in the areas of algorithms, circuits, and CMOS
implementations of high-performance baseband dig-
ital communication systems. He has authored or
co-authored more than 150 publications in refereed
journals and refereed conference proceedings. In
addition, he has received numerous teaching awards
for undergraduate courses taught in both the Department of Computer Science
and the Department of Electrical and Computer Engineering at the University
of Toronto. From Jan. 1985 to Jan. 1988 he was a Research Associate in
the Information Systems Laboratory and the Computer Systems Laboratory at
Stanford University. He has served on the ISSCC Signal Processing Technical
Subcommittee from 1990 to 1999, ISSCC Technical Vice-Chair in 2000 and
served as the Technical Program Chair for ISSCC 2001. He served on the
Technology Directions Subcommittee for ISSCC from 2005 to 2008. He
currently serves as the Vice-President of the Publications Committee for the
IEEE Solid-State Circuits Society and a member of the IEEE PSPB.

2168-2194 (c) 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.