# Secure Testing for Genetic Diseases on Encrypted Genomes with Homomorphic Encryption Scheme

Authors: Tan Ping Zhou; Ning Bo Li; Xiao Yuan Yang; Li Qun Lv; Yi Tao Ding; Xu An Wang
Journal: Security and Communication Networks
 (2018)

---

## Abstract

The decline in genome sequencing costs has widened the population that can afford its cost and has also raised concerns about genetic privacy. Kim et al. present a practical solution to the scenario of secure searching of gene data on a semitrusted business cloud. However, there are three errors in their scheme. We have made three improvements to solve these three errors.(1) They truncate the variation encodings of gene to 21 bits, which causes LPCE error and more than 5% of the entries in the database cannot be queried integrally. We decompose these large encodings by 44 bits and deal with the components, respectively, to avoid LPCE error. (2) We abandon the hash function used in Kim’s scheme, which may cause HCE error with a probability of 2-22 and decompose the position encoding of gene into three parts with the basis 211 to avoid HCE error. (3) We analyze the relationship between the parameters and the CCE error and specify the condition that parameters need to satisfy to avoid the CCE error. Experiments show that our scheme can search all entries, and the probability of searching error is reduced to less than 2-37.4.


---

## Body

## 1. Introduction

Genes are the intrinsic nature of human health. All human life activities and physiological phenomena are directly related to the gene. Genome data can be used for a wide range of applications including healthcare, biomedical research, and forensics [1]. Gene sequencing technology is the core of the human genome project; the genome sequencing technology helps humans to better understand the whole life activities of cells and organisms, and it is also of great significance for the prevention and treatment of some diseases, such as cancer and genetic diseases.Advances in high throughput technologies have made it increasingly affordable to sequence the human genome in various settings, ranging from biomedical research to healthcare [2]. Relevant data show that in 2000 the cost of whole genome sequencing for human is nearly $3 billion, and by 2015, the cost of single genome sequencing is reduced to less than $1,000, and the sequencing costs for certain sites on the genome are lower.The decline in genome sequencing costs has widened the population that can afford the cost of gene sequencing and has also raised concerns about genetic privacy. Genetic data can be widely used in healthcare, biomedical research and identification, and other fields, with a strong personal privacy characteristics. More and more businesses and individuals put the computing processing of genetic data to cloud services, but the current commercial cloud server does not fully guarantee the privacy and security of genetic data. This raises concerns about the privacy of sensitive information since data is stored in external, off-premise data centers. In particular in the health sector, sensitive personal patient records need to be kept confidential [3].There are a number of technical solutions that have been proposed to protect genome privacy, and existing studies can be categorized into two groups [4]: (i) protecting the computation process in genome data analysis [5–7] and (ii) protecting the genome data before computation [8, 9] or research outcomes after computation [10].In order to prevent the user’s genetic data from being compromised by unauthorized users or organizations, protecting genetic privacy is an urgent problem. To mitigate the privacy risks inherent in storing and computing sensitive data, cryptography offers a potential solution in the form of encryption [11]; only the legitimate data owner can access the data by decrypting it using their private decryption key.However, sometimes the calculation and analysis of genetic data need to be implemented in the cloud due to the limitation of personal computing power and genetic diagnosis algorithm patent, the need for cloud server, the user’s genetic data analysis, and analysis to help get the user diagnosis and treatment of the relevant information. Nevertheless, traditional cryptographic schemes limit the computation process on the ciphertext stored on the cloud and also prevent the data center from performing computation on it without the decryption key.Homomorphic encryption can do computation on the encrypted data in the case of unknown secret key, and the decryption results of the ciphertext data are equivalent to the corresponding plaintext for the same processing operations. In 2009, Gentry proposed the first FHE scheme and described the framework blueprint of the FHE [12]. Since then many improvements to FHE have been proposed based on Gentry’s work such as [13–17].Homomorphic encryption-based methods which support secure genome data computation have been studied. Cheon et al. [5] studied how to calculate edit distance of encrypted gene data homomorphically. Yasuda et al. [18] described how to compute multiple Hamming distance values using the LNV scheme [19] on encrypted data. Graepel et al. [20] and Bos et al. [3] applied HE to machine learning and described how to privately conduct predictive analysis based on an encrypted learned model. Lauter et al. [7] gave a solution to privately compute the basic genomic algorithms used in genetic association studies.To achieve safe genetic data analysis, iDASH (integrating Data for Analysis, Anonymization, and SHaring) National Center has released annual security challenges regarding genetic privacy protection since 2014. In 2016, the challenge of testing for genetic diseases on encrypted genomes (secure outsourcing) was published to calculate the probability of genetic diseases through matching a set of biomarkers to encrypted genomes stored in a commercial cloud service. The requirement is that the entire matching process (only consider the exact match for each variation) needs to be carried out using homomorphic encryption so that no trace is left behind during the computation.For the challenge published by iDASH, Kim et al. give a practical solution called [KSC17], which uses the homomorphic encryption technique to encrypt the entire gene database as a polynomial on the ring, thus solving the challenge of testing genetic disease (security outsourcing) to a certain extent [21].The application scenario of this paper is shown in Figure1. There are three parties involved in this scenario: the user (hospital or medical institution that has patient’s gene data), the semitrusted commercial cloud service, and data owner (the research institute that has the genetic variation database). The purpose of this system is to determine if a patient’s gene data is presented in the gene variation database.Figure 1
The application scenario of secure testing for genetic diseases.System Initialization. Data owner encrypts the gene variation database and uploads the ciphertexts to the commercial cloud server. Then, the user interacts with the cloud server to complete the testing process. Step 1: the user encrypts the patient’s gene data and uploads the ciphertexts to the commercial cloud server. Step 2: the cloud homomorphically searches user’s gene data in database and generates a ciphertext of searching result. Step 3: the cloud sends the ciphertexts to the user. Step 4: the user decrypts the ciphertexts and concludes whether the patient’s gene data is presented in the gene variation database. The source code of our implementation is available on github https://github.com/lonyliu/genetest.Our Contributions. The contributions of this paper focus on optimizing the design and improving the correctness of the scheme. Through the analysis of the [21] and its related code, we found three types of query errors in [KSC17], called losing of partial coefficient error (LPCE), hash collision error (HCE), and coefficient combination error (CCE), and made some improvements as follows.(1)
The gene data is encoded by prefix code so as to detect more entries in the gene database with fewer bits than [KSC17].(2)
Correcting the LPCE error: [KSC17] truncates the variation encodings of gene to 21 bits, which causes partial coefficient losing; thus more than 5% of the entries in the database cannot be queried integrally. In this paper, we decompose the encodings of gene variation by 44 bits, then optimize, encrypt, and query the components, respectively. As a result, all the entries can be queried effectively in the database.(3)
Correcting the HCE error: [KSC17] uses the method of hash function unreasonably, which may cause HCE error with a probability of2-22. In this paper, we abandon the hash function by adding half the ciphertext of database, thus avoiding the hash collision.(4)
Correcting the CCE error: [KSC17] cannot distinguish the different groups of gene data, which may return incorrect results with nonnegligible probability. In this paper, we analyze the relationship between the core parameterlsnp (bit size of the encoding for gene variation) and CCE error and specify the condition that parameter lsnp needs to satisfy, so that the probability of CCE errors is negligible.


## 2. Practical Homomorphic Encryptions

This section describes the homomorphic encryption schemes which are used in our genetic privacy protection. First, some symbols and parameters are described below.For the security parameterλ, let integer M=Mλ define the Mth cyclotomic polynomial ΦMx, Throughout this paper, we assume that the integer M is a power of two so that N=M/2 and ΦMx=XN+1. Both of our homomorphic encryption schemes operate in the polynomial ring R=Zx/ΦMx. ·Q denotes the reduction modulo Q into the interval -Q/2,Q/2∩Z of the integer or integer polynomial (coefficient-wise). Set the plaintext space to Rt≔R/tR for some fixed t≥2 and the ciphertext space to RQ≔R/QR for an integer Q=Qλ. Let χ=χλ denote a noise distribution over the ring R. Notation a←D denotes that a is chosen from the distribution D, and a←RD denote that a is randomly chosen from the distribution D.We give the brief introduction of the RLWE scheme [22] and the Ring-GSW scheme [23].


### 2.1. The RLWE Scheme

First basic homomorphic encryption scheme is based on the hardness of Ring Learning with Errors (RLWE) assumption, which is proposed by Lyubashevsky, Peikert, and Regev. The RLWE assumption is divided into decisional RLWE assumption and computational RLWE assumption. The decisional RLWE assumption implies the infeasible solution to distinguish the following two distributions: pairsai,bi where (ai,bi)←RRQ2 and pairs ai,bi=ai,ais+ei where ai←RRQ and s,ei←Rχ. The computational RLWE assumption is that it is hard to find the key s from many samples ai,bi=ai,ais+ei.The RLWE scheme is described as follows:(i)
RLWE.ParamsGen(λ): given the security parameter λ, choose an integer M=M(λ) which is a power of 2, a ciphertext modulus Q=Q(λ), a plaintext modulus t with t∣Q, and discrete Gaussian distribution χerr. Output params ←M,Q,t,χerr.(ii)
RLWE.KeyGen(params): for input parameters M, let N=ϕM and choose a random sparse s←{0,±1}N. Generate an RLWE instance a,b=a,-as+eQ for e←χerr. Set the secret key sk←s and the public key pk←a,b.(iii)
RLWE.Enc(m,pk): for the input plaintext m=∑imiXi∈Rt, choose a small polynomial v∈R and two Gaussian polynomials e0,e1←R, and output the ciphertext ct:(1)ct=c0,c1=Qtm+bv+e0,av+e1∈RQ2.(iv)
RLWE.Dec(ct,sk): given the ciphertext ct=(c0,c1), output the plaintext m:(2)m⟵tQ·c0+s·c1Q.(v)
RLWE.Add(ct1,ct2,ct3,sk): given three ciphertexts ct1, ct2, ct3 with the same secret key sk, output the ciphertext ct=ct1+ct2+ct3∈RQ2.Conversion and Modulus Switching techniques have been introduced in [KSC17]. Conversion technique can change an RLWE ciphertext ofm=∑imiXi∈Rt into an LWE encryption of its constant term m0. Modulus Switching technique reduces the ciphertext modulus Q down to q while preserving the message, thus reducing the size of ciphertext.


### 2.2. The Ring-GSW Scheme

In 2013, Gentry et al. proposed an LWE-based homomorphic encryption scheme [16], which uses the approximate eigenvector method to express ciphertext as a matrix, so that the addition and multiplication of ciphertext no longer cause dimension expansion. In this paper, we use its RLWE version introduced by Ducas and Micciancio [23], and its encryption algorithm is given below:(i)
RGSW.ParamsGen(·): given the same parameters and secret key s as in the RLWE scheme, set the decomposition base Bg and exponent dg satisfying Bgdg>Q. Given a small matrix G=IBgI∥⋯Bgdg-1I∈RQ2dg×2 for 2×2 identity matrix I.(ii)
RGSW.Enc(m,sk): given the plaintext m∈Rt, choose a matrix a←RRQ2dg×1 uniformly, and e←Rχςe∈RQ2dg≃Z2dg•n; output the ciphertext CT:(3)CT=b,a+mG∈RQ2dg×2,b=-a·s+e.And the ciphertextCT satisfies CT·(1,s)=m·(1,s,…,Bgdg-1,Bgdg-1s)+e. Let DecBg(·) denote the decomposition with the base Bg, so m can be regarded as an approximate eigenvalue of DecBg(CT) with the eigenvector (1,s,…,Bgdg-1,Bgdg-1s).Reference [17] defines a hybrid multiplication between an RLWE ciphertext ct∈RQ2 and an RGSW ciphertext CT∈RQ2dg×2.(4)ctH·mult=Hybrid.MultCT,ct=CTT·Decct∈TLWEmCT·mct∈RQ2.Thus the ciphertextctH·mult is a RLWE encryption of mCTmct.


## 2.1. The RLWE Scheme

First basic homomorphic encryption scheme is based on the hardness of Ring Learning with Errors (RLWE) assumption, which is proposed by Lyubashevsky, Peikert, and Regev. The RLWE assumption is divided into decisional RLWE assumption and computational RLWE assumption. The decisional RLWE assumption implies the infeasible solution to distinguish the following two distributions: pairsai,bi where (ai,bi)←RRQ2 and pairs ai,bi=ai,ais+ei where ai←RRQ and s,ei←Rχ. The computational RLWE assumption is that it is hard to find the key s from many samples ai,bi=ai,ais+ei.The RLWE scheme is described as follows:(i)
RLWE.ParamsGen(λ): given the security parameter λ, choose an integer M=M(λ) which is a power of 2, a ciphertext modulus Q=Q(λ), a plaintext modulus t with t∣Q, and discrete Gaussian distribution χerr. Output params ←M,Q,t,χerr.(ii)
RLWE.KeyGen(params): for input parameters M, let N=ϕM and choose a random sparse s←{0,±1}N. Generate an RLWE instance a,b=a,-as+eQ for e←χerr. Set the secret key sk←s and the public key pk←a,b.(iii)
RLWE.Enc(m,pk): for the input plaintext m=∑imiXi∈Rt, choose a small polynomial v∈R and two Gaussian polynomials e0,e1←R, and output the ciphertext ct:(1)ct=c0,c1=Qtm+bv+e0,av+e1∈RQ2.(iv)
RLWE.Dec(ct,sk): given the ciphertext ct=(c0,c1), output the plaintext m:(2)m⟵tQ·c0+s·c1Q.(v)
RLWE.Add(ct1,ct2,ct3,sk): given three ciphertexts ct1, ct2, ct3 with the same secret key sk, output the ciphertext ct=ct1+ct2+ct3∈RQ2.Conversion and Modulus Switching techniques have been introduced in [KSC17]. Conversion technique can change an RLWE ciphertext ofm=∑imiXi∈Rt into an LWE encryption of its constant term m0. Modulus Switching technique reduces the ciphertext modulus Q down to q while preserving the message, thus reducing the size of ciphertext.


## 2.2. The Ring-GSW Scheme

In 2013, Gentry et al. proposed an LWE-based homomorphic encryption scheme [16], which uses the approximate eigenvector method to express ciphertext as a matrix, so that the addition and multiplication of ciphertext no longer cause dimension expansion. In this paper, we use its RLWE version introduced by Ducas and Micciancio [23], and its encryption algorithm is given below:(i)
RGSW.ParamsGen(·): given the same parameters and secret key s as in the RLWE scheme, set the decomposition base Bg and exponent dg satisfying Bgdg>Q. Given a small matrix G=IBgI∥⋯Bgdg-1I∈RQ2dg×2 for 2×2 identity matrix I.(ii)
RGSW.Enc(m,sk): given the plaintext m∈Rt, choose a matrix a←RRQ2dg×1 uniformly, and e←Rχςe∈RQ2dg≃Z2dg•n; output the ciphertext CT:(3)CT=b,a+mG∈RQ2dg×2,b=-a·s+e.And the ciphertextCT satisfies CT·(1,s)=m·(1,s,…,Bgdg-1,Bgdg-1s)+e. Let DecBg(·) denote the decomposition with the base Bg, so m can be regarded as an approximate eigenvalue of DecBg(CT) with the eigenvector (1,s,…,Bgdg-1,Bgdg-1s).Reference [17] defines a hybrid multiplication between an RLWE ciphertext ct∈RQ2 and an RGSW ciphertext CT∈RQ2dg×2.(4)ctH·mult=Hybrid.MultCT,ct=CTT·Decct∈TLWEmCT·mct∈RQ2.Thus the ciphertextctH·mult is a RLWE encryption of mCTmct.


## 3. Encoding and Encryption of Gene Data

Recall the task proposed by iDASH: secure biomarkers matching of encrypted genetic data, and in this section, we describe how to encode and encrypt the genomic data.


### 3.1. Genetic Data

The gene data is stored in a semitrusted business cloud in VCF format. The database VCF file contains multiple genotype information entries, where each of them consists of chrome (chr), position (pos), locus (loc), reference (ref), alternate (alt), type. The example of database is shown in Table1. Chrome represents the chromosome where the gene is located, and it ranges from 1 to 22, X, and Y. Position represents the base position of the gene variation in the chromosome, and locus indicates the location of the gene. Reference, alternate, type display the base transformation information for the variation: reference represents the base information before the mutation occurs; alternate represents the base information after the mutation; type indicates the type of the mutation, including the single base variation (SNP), multibase mutation (SUB), insertion variation (INS), and deletion variation (DEL).Table 1
The format of genome data.
Chr Pos Loc Ref Alt Type 1 160952708 rs2250304 C T SNP 1 160952937 rs71090344  GGAGGTTTCAGTGAGCT INS 1 160953538 rs59471747  T INS 1 160953667 rs2988723 G A SNP 1 160955055 . TG CA SUB 1 160955067 . GCA ACG SUB 1 160955085 . CTA TTG SUB 1 160955294 rs6427571 A G SNP 1 160955725 rs2990700 T C SNP 1 160956178 rs3007155 T C SNP 1 160956420 rs3007156 G A SNP 1 160956744 rs2990701 C T SNP 1 160957493 rs3007157 A G SNP 1 160957862 .  T INS 1 160957885 rs2483148 A C SNP 1 160958160 rs2481072 G A SNP 1 160958212 . C T SNP 1 160959961 rs7530765 C T SNP 1 160961448 rs11300130 AG  DELIn fact, the gene mutation can be located by chr and pos information only, and the information of base change can be obtained by comparing the ref base and the alt base. In order to improve the efficiency of the program, we only match the chr and pos information between the patient and the cloud, and then we get the corresponding ref and alt information of base variation at the same location in the database. Finally the user compares the base change information from the cloud and his base change information to get the final match result.


### 3.2. Encoding and Encryption of Genetic Data

In this section, we describe how to encode the genomic data so that they can be applied to homomorphic encryption scheme. Letdi denote the position information of the ith entry in the gene database, αi the variation information of the ith entry in the gene database, αiref and αialt the integer encodings of reference genome and alternate genome, respectively.For the coding of the gene position information, define a mapping from (chr, pos) todi:(5)θ:Z,Z⟶Z(6)chrom,pos⟶di=chromi+24·posi.In the following we describe how to encode the base variation information in [KSC17]. Firstly, they represent the common SNPs by two binary numbers as(7)A⟶00T⟶01G⟶10C⟶11and encode them according to their order. Then pad with 1 to the left of the bit string so as to distinguish the A-string and empty string. For instance, the base A will be encoded as 1∣00=1002=4, and string CG will be encoded as 1∣11∣10=111102=30. nSNP denotes the maximal number of reference (or alternate) alleles to be compared between the query genome and genomes in the target database; thus the length of the base string is lSNP=2·nSNP+1. And in [KSC17] the encoding of base variation information is expressed as(8)αi=2lnsp·αiref+αialt.Our Contribution. The value of nSNP in [KSC17] is set, respectively, to 2, 5, or 10, but the genovariation that more than 10-base insertion or deletion may occur actually. For example, the second entry in Table 1 for column of “alt” genome is GGAGGTTTCAGT GAGCT. If the patient’s alt genome (query gene information) is GGAGGTTTCA, the server will conclude that the patient is more likely to suffer from a genopathy. At the same time, we found that the numbers of ref bases and alt bases are usually not symmetrical through the statistical analysis of the genetic database, and the number of bases after concatenating the ref and alt genome does not exceed 20 mostly. Therefore, the prefix code is used to encode the genome data:Firstly, the SNPs are encoded as(9)A⟶00,T⟶01,G⟶10,C⟶110.Then, a string “111” is added to concatenate the ref and alt genome; this can help us to separate the encoding of ref and alt genome correctly. Finally, pad with 1 to the left of the bit string so as to distinguish theA-strings. Here is the formula of getting αi:(10)αi=1∣αiref111αialt,αi≤244.Letlsnp denote the bit size of αi, and set lsnp=44 so as to expand the number of gene entries which can be correctly matched. If the length of αi is less than 44 bits, then pad bit 0 at the left of the bit string to ensure that the length of the encoding is 44 bits. For the case of lengthαi>44 bits, αi is divided by 44 bits; the details are in Section 3.3.3.For example, the base variation information of the second entry in the Table1 will be encoded as 00001111101000101001010111000100110001011001. And it can be decoded by the way shown in Figure 2.Figure 2
Coding structure of base variation information.After the process of encoding the genetic data, the database file will be encoded as a set of pairsdi,αi for i=1,2,…,n. The encoding results of Table 1 are shown in Table 2.Table 2
Encoding of genetic data.
Chr Pos d Ref Alt α 1 160952708 3862864993 C T 477 1 160952937 3862870489  GGAGGTTTCAGTGAGCT 1074435738713 1 160953538 3862884913  T 61 1 160953667 3862888009 G A 220 1 160955055 3862921321 TG CA 5880 1 160955067 3862921609 GCA ACG 222106 1 160955085 3862922041 CTA TTG 117206 1 160955294 3862927057 A G 158 1 160955725 3862937401 T C 382 1 160956178 3862948273 T C 382 1 160956420 3862954081 G A 220 1 160956744 3862961857 C T 477 1 160957493 3862979833 A G 158 1 160957862 3862988689  T 61 1 160957885 3862989241 A C 318 1 160958160 3862995841 G A 220 1 160958212 3862997089 C T 477 1 160959961 3863039065 C T 477 1 160961448 3863074753 AG  151The HE scheme in this paper is carried out on a polynomial ring, so it is necessary to express the integer pairs as polynomialDBX=∑i=0NciXi∈R-, where(11)ci=αi,ifi=di,αi⟵Ztelse.Since thedi from VCF files have bits size about 32, set R-≜(Z[X]/[XN-+1]),  N-=233-1. And then the data owner (research institute) encrypts the polynomial DBX with the RLWE public-key encryption scheme as described above.The query genes are also encoded as a pair of integersd,α. However, the hospital or medical institution only needs to encrypt the monomial X-d with the RGSW symmetric encryption scheme.


### 3.3. The Optimization of the Encoded Data

Since thedi from VCF files have bits size of about 32, set R-≜(Z[X]/[XN-+1]), N-=233-1. While taking into account the safety and efficiency of HE schemes, a dimension 211<N<216 is considered appropriate.[KSC17] makes use of SHA-3 to transformdi into a pair of two nonnegative integers di∗ and di†:Hash(di)→(di∗,di†), and both of them have the bit size of 11 bits; then define ring R≜(Z[X]/[XN+1]), N=11, and mapping Φ:R-t→Rtk×2DBX→(DB∗jX,DB†jX)j∈1,…,k, and transform polynomial DBX into k groups of lower-dimension polynomials DB∗jX∈R, DB†jX∈R, where(12)DB∗jX=∑i=0Ncj,di∗∗Xdi∗,DB†jX=∑i=0Ncj,di††Xdi†,and polynomials DB∗j and DB†j satisfy αi=cj,di∗∗+cj,di††, for one j∈1,…,k.A corresponding mappingϕ is defined as the specific mapping from a term in a polynomial R-t to terms in polynomials Rt2.(13)ϕ:R-t⟶Rt2αiXdi⟶cj,di∗∗Xdi∗,cj,di††Xdi†,for  onej∈1,…,k.We found that there are three types of errors in [KSC17], named hash collision error (HCE), coefficient combination error (CCE), and losing of partial coefficient error (LPCE). In the following we will describe these errors and our solutions.


#### 3.3.1. Hash Collision Error

KSC17 made use of SHA-3 to transform 33-bit-sizedi into a pair of two 11-bit-size integers di∗ and di† in order to improve the efficiency of the scheme. The hash function maps 33 bits of information to 22 bits, which may cause the collisions with a probability of 2-22 approximately. This collision will result in a searching error. Take 10,000 entries in the database as an example, and suppose that the user queries the position of d1, where hashd1→d1∗,d1†. The probability of at least one hash collision existing between the query and the database, with the same d1∗ and d1†, is 1-(1-1/222)10000>2-9; that is, the user might get a wrong result with a probability more than 2-9. What is more, this error cannot be avoided by repeating the algorithm.Our Contribution. For the HCE error, we abandon the method of hash function, and decompose the index di with the basis N=211, so that di can be represented as di=N2·di∗+N·di†+di⊥; that is, di=di∗∣di†∣di⊥. Then, we extend the mapping Φ to mapping Ψ(14)Ψ:R-t⟶Rtk×3DBX⟶DB∗jX,DB†jX,DB⊥jXj∈1,…,k,where k is the number of polynomial groups, DB∗jX=∑i=0ncj,di∗∗Xdi∗, DB†jX=∑i=0ncj,di††Xdi†, DB⊥jX=∑i=0ncj,di⊥⊥Xdi⊥, αi=cj,di∗∗+cj,di††+cj,di⊥⊥. And extend the corresponding mapping ϕ to mapping ψ(15)ψ:R-t⟶Rt3αiXdi⟶cj,di∗∗Xdi∗,cj,di††Xdi†,cj,di⊥⊥Xdi⊥,for  onej∈1,…,k.As a result, we can effectively avoid the collision caused by the compression of the indexdi and solve the HCE problem.


#### 3.3.2. Coefficient Combination Error

In this section, we will describe how the CCE error is happening. For∀o,p∈ZN, the CCE error exists because [KSC17] cannot distinguish whether two coefficients cj,o∗ and cj,p†, picked, respectively, from DB∗jX,DB†jXj∈1,…,k, belong to the one mapping ϕ. This error may lead to the mistake that an entry that is not in the database was judged in the database.There is a way to determine whether an integer pair(αi,di) is in the database. Firstly the integer pair (αi,di) is employed to represent the polynomial αiXdi; then transform it into (cdi∗∗Xdi∗,cdi††Xdi†) through mapping ϕ. If there exists a certain group (for one j) (DB∗jX,DB†jX)j∈{1,…,k} whose corresponding entries cj,o∗Xdi∗, cj,p†Xdi† satisfy cj,o∗+cj,p†=αi, then the integer pair (αi,di) is judged in the database; otherwise the integer pair (αi,di) is not judged in the database.We give a brief description in Figure3.Figure 3
A brief description of CCE error.The first line in Figure3 represents the polynomial DB(X) with large dimension, and the second and third lines represent the polynomials DB∗jX and DB†jX with small dimension. All nonzero coefficients in the polynomials are labeled with short lines. If patient want to check whether the query entry (di,αi)=(15,9) exists in the database with hash15→1,5, [KSC17] will give the conclusion that this entry exists in the database, since the coefficients of 5X1 and 4X5 satisfy 5+4=9. This will cause the mistake that the patient was misdiagnosed as sick.Our Contribution. The CCE error means that the query entry (αi,di) does not exist in the database, but the scheme gives the result that the entry is in the database. If the di is decomposed into di∗, di†, and di⊥, this error will happen only if the sum of the coefficients cj,o∗+cj,p†+cj,p⊥ of corresponding term cj,o∗Xdi∗, cj,p†Xdi†, cj,q⊥Xdi⊥ for one j∈1,…,k is exactly equal to αi. Since the sum of coefficients cj,o∗+cj,p†+cj,p⊥∈Zt- is uniformed, the probability of cj,o∗+cj,p†+cj,p⊥=αi for a given αi is 1/t-=1/(2lsnp), for one group j∈{1,…,k}. The mapping Ψ:R-t→Rtk×3 will generate k group polynomials, and the probability of at least one group has a collision with the given query entry (αi,di) is 1-(1-1/2lsnp)k. Through a similar analysis, we find that the probability of CCE error in [KSC17] also satisfies this formula. When [KSC17] gives the parameters nsnp=5, lsnp=11, k=100, this probability will be as high as 1-(1-1/2lsnp)k≈2-4.39>2-5.There are two factors we need to consider for the parameterlsnp. Firstly, the size of coefficients needs to be multiple of 11 bits. Secondly, the size of coefficients needs to be large enough to decrease the probability of CCE error, and the scheme’s efficiency should be taken into account. Consequently we set lsnp=44 to reach the requirement for security and efficiency, and decrease the probability of CCE error to 2-37.4.


#### 3.3.3. Losing of Partial Coefficient Error

In this section, we will describe how the error LPCE is happening. [KSC17] setslsnp=21 bits, while we found that there are some entries in the database whose encodings are more than 21 bits, and the longest one even needs 272 bits to be represented. For those entries whose encodings are more than 21 bits, [KSC17] truncates the encoding bit to the left 21 bits and abandon other bits. The truncation will cause the LPCE problem. In 3.2 we extend lsnp to 44 bits, but also we cannot meet our needs for the correct matching.Our Contribution. In order to solve this problem, we decompose these long encodings by 44 bits, then optimize, encrypt, and query the components, respectively. Suppose that the given entry with large coefficient is (αi,di). First, αi is decomposed by 44 bits; get a set of smaller components (αi,o,…,αi,1), where αi=αi,o∣⋯∣αi,1, αi,j∈Zt. Second, we construct and output multiple new entries with smaller coefficients (αi,o,di),…,(αi,1,di). Finally, these entries are mapped by ψ and optimized separately. As a result, we can represent and query all entries effectively in the database and solve the LPCE problem.


## 3.1. Genetic Data

The gene data is stored in a semitrusted business cloud in VCF format. The database VCF file contains multiple genotype information entries, where each of them consists of chrome (chr), position (pos), locus (loc), reference (ref), alternate (alt), type. The example of database is shown in Table1. Chrome represents the chromosome where the gene is located, and it ranges from 1 to 22, X, and Y. Position represents the base position of the gene variation in the chromosome, and locus indicates the location of the gene. Reference, alternate, type display the base transformation information for the variation: reference represents the base information before the mutation occurs; alternate represents the base information after the mutation; type indicates the type of the mutation, including the single base variation (SNP), multibase mutation (SUB), insertion variation (INS), and deletion variation (DEL).Table 1
The format of genome data.
Chr Pos Loc Ref Alt Type 1 160952708 rs2250304 C T SNP 1 160952937 rs71090344  GGAGGTTTCAGTGAGCT INS 1 160953538 rs59471747  T INS 1 160953667 rs2988723 G A SNP 1 160955055 . TG CA SUB 1 160955067 . GCA ACG SUB 1 160955085 . CTA TTG SUB 1 160955294 rs6427571 A G SNP 1 160955725 rs2990700 T C SNP 1 160956178 rs3007155 T C SNP 1 160956420 rs3007156 G A SNP 1 160956744 rs2990701 C T SNP 1 160957493 rs3007157 A G SNP 1 160957862 .  T INS 1 160957885 rs2483148 A C SNP 1 160958160 rs2481072 G A SNP 1 160958212 . C T SNP 1 160959961 rs7530765 C T SNP 1 160961448 rs11300130 AG  DELIn fact, the gene mutation can be located by chr and pos information only, and the information of base change can be obtained by comparing the ref base and the alt base. In order to improve the efficiency of the program, we only match the chr and pos information between the patient and the cloud, and then we get the corresponding ref and alt information of base variation at the same location in the database. Finally the user compares the base change information from the cloud and his base change information to get the final match result.


## 3.2. Encoding and Encryption of Genetic Data

In this section, we describe how to encode the genomic data so that they can be applied to homomorphic encryption scheme. Letdi denote the position information of the ith entry in the gene database, αi the variation information of the ith entry in the gene database, αiref and αialt the integer encodings of reference genome and alternate genome, respectively.For the coding of the gene position information, define a mapping from (chr, pos) todi:(5)θ:Z,Z⟶Z(6)chrom,pos⟶di=chromi+24·posi.In the following we describe how to encode the base variation information in [KSC17]. Firstly, they represent the common SNPs by two binary numbers as(7)A⟶00T⟶01G⟶10C⟶11and encode them according to their order. Then pad with 1 to the left of the bit string so as to distinguish the A-string and empty string. For instance, the base A will be encoded as 1∣00=1002=4, and string CG will be encoded as 1∣11∣10=111102=30. nSNP denotes the maximal number of reference (or alternate) alleles to be compared between the query genome and genomes in the target database; thus the length of the base string is lSNP=2·nSNP+1. And in [KSC17] the encoding of base variation information is expressed as(8)αi=2lnsp·αiref+αialt.Our Contribution. The value of nSNP in [KSC17] is set, respectively, to 2, 5, or 10, but the genovariation that more than 10-base insertion or deletion may occur actually. For example, the second entry in Table 1 for column of “alt” genome is GGAGGTTTCAGT GAGCT. If the patient’s alt genome (query gene information) is GGAGGTTTCA, the server will conclude that the patient is more likely to suffer from a genopathy. At the same time, we found that the numbers of ref bases and alt bases are usually not symmetrical through the statistical analysis of the genetic database, and the number of bases after concatenating the ref and alt genome does not exceed 20 mostly. Therefore, the prefix code is used to encode the genome data:Firstly, the SNPs are encoded as(9)A⟶00,T⟶01,G⟶10,C⟶110.Then, a string “111” is added to concatenate the ref and alt genome; this can help us to separate the encoding of ref and alt genome correctly. Finally, pad with 1 to the left of the bit string so as to distinguish theA-strings. Here is the formula of getting αi:(10)αi=1∣αiref111αialt,αi≤244.Letlsnp denote the bit size of αi, and set lsnp=44 so as to expand the number of gene entries which can be correctly matched. If the length of αi is less than 44 bits, then pad bit 0 at the left of the bit string to ensure that the length of the encoding is 44 bits. For the case of lengthαi>44 bits, αi is divided by 44 bits; the details are in Section 3.3.3.For example, the base variation information of the second entry in the Table1 will be encoded as 00001111101000101001010111000100110001011001. And it can be decoded by the way shown in Figure 2.Figure 2
Coding structure of base variation information.After the process of encoding the genetic data, the database file will be encoded as a set of pairsdi,αi for i=1,2,…,n. The encoding results of Table 1 are shown in Table 2.Table 2
Encoding of genetic data.
Chr Pos d Ref Alt α 1 160952708 3862864993 C T 477 1 160952937 3862870489  GGAGGTTTCAGTGAGCT 1074435738713 1 160953538 3862884913  T 61 1 160953667 3862888009 G A 220 1 160955055 3862921321 TG CA 5880 1 160955067 3862921609 GCA ACG 222106 1 160955085 3862922041 CTA TTG 117206 1 160955294 3862927057 A G 158 1 160955725 3862937401 T C 382 1 160956178 3862948273 T C 382 1 160956420 3862954081 G A 220 1 160956744 3862961857 C T 477 1 160957493 3862979833 A G 158 1 160957862 3862988689  T 61 1 160957885 3862989241 A C 318 1 160958160 3862995841 G A 220 1 160958212 3862997089 C T 477 1 160959961 3863039065 C T 477 1 160961448 3863074753 AG  151The HE scheme in this paper is carried out on a polynomial ring, so it is necessary to express the integer pairs as polynomialDBX=∑i=0NciXi∈R-, where(11)ci=αi,ifi=di,αi⟵Ztelse.Since thedi from VCF files have bits size about 32, set R-≜(Z[X]/[XN-+1]),  N-=233-1. And then the data owner (research institute) encrypts the polynomial DBX with the RLWE public-key encryption scheme as described above.The query genes are also encoded as a pair of integersd,α. However, the hospital or medical institution only needs to encrypt the monomial X-d with the RGSW symmetric encryption scheme.


## 3.3. The Optimization of the Encoded Data

Since thedi from VCF files have bits size of about 32, set R-≜(Z[X]/[XN-+1]), N-=233-1. While taking into account the safety and efficiency of HE schemes, a dimension 211<N<216 is considered appropriate.[KSC17] makes use of SHA-3 to transformdi into a pair of two nonnegative integers di∗ and di†:Hash(di)→(di∗,di†), and both of them have the bit size of 11 bits; then define ring R≜(Z[X]/[XN+1]), N=11, and mapping Φ:R-t→Rtk×2DBX→(DB∗jX,DB†jX)j∈1,…,k, and transform polynomial DBX into k groups of lower-dimension polynomials DB∗jX∈R, DB†jX∈R, where(12)DB∗jX=∑i=0Ncj,di∗∗Xdi∗,DB†jX=∑i=0Ncj,di††Xdi†,and polynomials DB∗j and DB†j satisfy αi=cj,di∗∗+cj,di††, for one j∈1,…,k.A corresponding mappingϕ is defined as the specific mapping from a term in a polynomial R-t to terms in polynomials Rt2.(13)ϕ:R-t⟶Rt2αiXdi⟶cj,di∗∗Xdi∗,cj,di††Xdi†,for  onej∈1,…,k.We found that there are three types of errors in [KSC17], named hash collision error (HCE), coefficient combination error (CCE), and losing of partial coefficient error (LPCE). In the following we will describe these errors and our solutions.


### 3.3.1. Hash Collision Error

KSC17 made use of SHA-3 to transform 33-bit-sizedi into a pair of two 11-bit-size integers di∗ and di† in order to improve the efficiency of the scheme. The hash function maps 33 bits of information to 22 bits, which may cause the collisions with a probability of 2-22 approximately. This collision will result in a searching error. Take 10,000 entries in the database as an example, and suppose that the user queries the position of d1, where hashd1→d1∗,d1†. The probability of at least one hash collision existing between the query and the database, with the same d1∗ and d1†, is 1-(1-1/222)10000>2-9; that is, the user might get a wrong result with a probability more than 2-9. What is more, this error cannot be avoided by repeating the algorithm.Our Contribution. For the HCE error, we abandon the method of hash function, and decompose the index di with the basis N=211, so that di can be represented as di=N2·di∗+N·di†+di⊥; that is, di=di∗∣di†∣di⊥. Then, we extend the mapping Φ to mapping Ψ(14)Ψ:R-t⟶Rtk×3DBX⟶DB∗jX,DB†jX,DB⊥jXj∈1,…,k,where k is the number of polynomial groups, DB∗jX=∑i=0ncj,di∗∗Xdi∗, DB†jX=∑i=0ncj,di††Xdi†, DB⊥jX=∑i=0ncj,di⊥⊥Xdi⊥, αi=cj,di∗∗+cj,di††+cj,di⊥⊥. And extend the corresponding mapping ϕ to mapping ψ(15)ψ:R-t⟶Rt3αiXdi⟶cj,di∗∗Xdi∗,cj,di††Xdi†,cj,di⊥⊥Xdi⊥,for  onej∈1,…,k.As a result, we can effectively avoid the collision caused by the compression of the indexdi and solve the HCE problem.


### 3.3.2. Coefficient Combination Error

In this section, we will describe how the CCE error is happening. For∀o,p∈ZN, the CCE error exists because [KSC17] cannot distinguish whether two coefficients cj,o∗ and cj,p†, picked, respectively, from DB∗jX,DB†jXj∈1,…,k, belong to the one mapping ϕ. This error may lead to the mistake that an entry that is not in the database was judged in the database.There is a way to determine whether an integer pair(αi,di) is in the database. Firstly the integer pair (αi,di) is employed to represent the polynomial αiXdi; then transform it into (cdi∗∗Xdi∗,cdi††Xdi†) through mapping ϕ. If there exists a certain group (for one j) (DB∗jX,DB†jX)j∈{1,…,k} whose corresponding entries cj,o∗Xdi∗, cj,p†Xdi† satisfy cj,o∗+cj,p†=αi, then the integer pair (αi,di) is judged in the database; otherwise the integer pair (αi,di) is not judged in the database.We give a brief description in Figure3.Figure 3
A brief description of CCE error.The first line in Figure3 represents the polynomial DB(X) with large dimension, and the second and third lines represent the polynomials DB∗jX and DB†jX with small dimension. All nonzero coefficients in the polynomials are labeled with short lines. If patient want to check whether the query entry (di,αi)=(15,9) exists in the database with hash15→1,5, [KSC17] will give the conclusion that this entry exists in the database, since the coefficients of 5X1 and 4X5 satisfy 5+4=9. This will cause the mistake that the patient was misdiagnosed as sick.Our Contribution. The CCE error means that the query entry (αi,di) does not exist in the database, but the scheme gives the result that the entry is in the database. If the di is decomposed into di∗, di†, and di⊥, this error will happen only if the sum of the coefficients cj,o∗+cj,p†+cj,p⊥ of corresponding term cj,o∗Xdi∗, cj,p†Xdi†, cj,q⊥Xdi⊥ for one j∈1,…,k is exactly equal to αi. Since the sum of coefficients cj,o∗+cj,p†+cj,p⊥∈Zt- is uniformed, the probability of cj,o∗+cj,p†+cj,p⊥=αi for a given αi is 1/t-=1/(2lsnp), for one group j∈{1,…,k}. The mapping Ψ:R-t→Rtk×3 will generate k group polynomials, and the probability of at least one group has a collision with the given query entry (αi,di) is 1-(1-1/2lsnp)k. Through a similar analysis, we find that the probability of CCE error in [KSC17] also satisfies this formula. When [KSC17] gives the parameters nsnp=5, lsnp=11, k=100, this probability will be as high as 1-(1-1/2lsnp)k≈2-4.39>2-5.There are two factors we need to consider for the parameterlsnp. Firstly, the size of coefficients needs to be multiple of 11 bits. Secondly, the size of coefficients needs to be large enough to decrease the probability of CCE error, and the scheme’s efficiency should be taken into account. Consequently we set lsnp=44 to reach the requirement for security and efficiency, and decrease the probability of CCE error to 2-37.4.


### 3.3.3. Losing of Partial Coefficient Error

In this section, we will describe how the error LPCE is happening. [KSC17] setslsnp=21 bits, while we found that there are some entries in the database whose encodings are more than 21 bits, and the longest one even needs 272 bits to be represented. For those entries whose encodings are more than 21 bits, [KSC17] truncates the encoding bit to the left 21 bits and abandon other bits. The truncation will cause the LPCE problem. In 3.2 we extend lsnp to 44 bits, but also we cannot meet our needs for the correct matching.Our Contribution. In order to solve this problem, we decompose these long encodings by 44 bits, then optimize, encrypt, and query the components, respectively. Suppose that the given entry with large coefficient is (αi,di). First, αi is decomposed by 44 bits; get a set of smaller components (αi,o,…,αi,1), where αi=αi,o∣⋯∣αi,1, αi,j∈Zt. Second, we construct and output multiple new entries with smaller coefficients (αi,o,di),…,(αi,1,di). Finally, these entries are mapped by ψ and optimized separately. As a result, we can represent and query all entries effectively in the database and solve the LPCE problem.


## 3.3.1. Hash Collision Error

KSC17 made use of SHA-3 to transform 33-bit-sizedi into a pair of two 11-bit-size integers di∗ and di† in order to improve the efficiency of the scheme. The hash function maps 33 bits of information to 22 bits, which may cause the collisions with a probability of 2-22 approximately. This collision will result in a searching error. Take 10,000 entries in the database as an example, and suppose that the user queries the position of d1, where hashd1→d1∗,d1†. The probability of at least one hash collision existing between the query and the database, with the same d1∗ and d1†, is 1-(1-1/222)10000>2-9; that is, the user might get a wrong result with a probability more than 2-9. What is more, this error cannot be avoided by repeating the algorithm.Our Contribution. For the HCE error, we abandon the method of hash function, and decompose the index di with the basis N=211, so that di can be represented as di=N2·di∗+N·di†+di⊥; that is, di=di∗∣di†∣di⊥. Then, we extend the mapping Φ to mapping Ψ(14)Ψ:R-t⟶Rtk×3DBX⟶DB∗jX,DB†jX,DB⊥jXj∈1,…,k,where k is the number of polynomial groups, DB∗jX=∑i=0ncj,di∗∗Xdi∗, DB†jX=∑i=0ncj,di††Xdi†, DB⊥jX=∑i=0ncj,di⊥⊥Xdi⊥, αi=cj,di∗∗+cj,di††+cj,di⊥⊥. And extend the corresponding mapping ϕ to mapping ψ(15)ψ:R-t⟶Rt3αiXdi⟶cj,di∗∗Xdi∗,cj,di††Xdi†,cj,di⊥⊥Xdi⊥,for  onej∈1,…,k.As a result, we can effectively avoid the collision caused by the compression of the indexdi and solve the HCE problem.


## 3.3.2. Coefficient Combination Error

In this section, we will describe how the CCE error is happening. For∀o,p∈ZN, the CCE error exists because [KSC17] cannot distinguish whether two coefficients cj,o∗ and cj,p†, picked, respectively, from DB∗jX,DB†jXj∈1,…,k, belong to the one mapping ϕ. This error may lead to the mistake that an entry that is not in the database was judged in the database.There is a way to determine whether an integer pair(αi,di) is in the database. Firstly the integer pair (αi,di) is employed to represent the polynomial αiXdi; then transform it into (cdi∗∗Xdi∗,cdi††Xdi†) through mapping ϕ. If there exists a certain group (for one j) (DB∗jX,DB†jX)j∈{1,…,k} whose corresponding entries cj,o∗Xdi∗, cj,p†Xdi† satisfy cj,o∗+cj,p†=αi, then the integer pair (αi,di) is judged in the database; otherwise the integer pair (αi,di) is not judged in the database.We give a brief description in Figure3.Figure 3
A brief description of CCE error.The first line in Figure3 represents the polynomial DB(X) with large dimension, and the second and third lines represent the polynomials DB∗jX and DB†jX with small dimension. All nonzero coefficients in the polynomials are labeled with short lines. If patient want to check whether the query entry (di,αi)=(15,9) exists in the database with hash15→1,5, [KSC17] will give the conclusion that this entry exists in the database, since the coefficients of 5X1 and 4X5 satisfy 5+4=9. This will cause the mistake that the patient was misdiagnosed as sick.Our Contribution. The CCE error means that the query entry (αi,di) does not exist in the database, but the scheme gives the result that the entry is in the database. If the di is decomposed into di∗, di†, and di⊥, this error will happen only if the sum of the coefficients cj,o∗+cj,p†+cj,p⊥ of corresponding term cj,o∗Xdi∗, cj,p†Xdi†, cj,q⊥Xdi⊥ for one j∈1,…,k is exactly equal to αi. Since the sum of coefficients cj,o∗+cj,p†+cj,p⊥∈Zt- is uniformed, the probability of cj,o∗+cj,p†+cj,p⊥=αi for a given αi is 1/t-=1/(2lsnp), for one group j∈{1,…,k}. The mapping Ψ:R-t→Rtk×3 will generate k group polynomials, and the probability of at least one group has a collision with the given query entry (αi,di) is 1-(1-1/2lsnp)k. Through a similar analysis, we find that the probability of CCE error in [KSC17] also satisfies this formula. When [KSC17] gives the parameters nsnp=5, lsnp=11, k=100, this probability will be as high as 1-(1-1/2lsnp)k≈2-4.39>2-5.There are two factors we need to consider for the parameterlsnp. Firstly, the size of coefficients needs to be multiple of 11 bits. Secondly, the size of coefficients needs to be large enough to decrease the probability of CCE error, and the scheme’s efficiency should be taken into account. Consequently we set lsnp=44 to reach the requirement for security and efficiency, and decrease the probability of CCE error to 2-37.4.


## 3.3.3. Losing of Partial Coefficient Error

In this section, we will describe how the error LPCE is happening. [KSC17] setslsnp=21 bits, while we found that there are some entries in the database whose encodings are more than 21 bits, and the longest one even needs 272 bits to be represented. For those entries whose encodings are more than 21 bits, [KSC17] truncates the encoding bit to the left 21 bits and abandon other bits. The truncation will cause the LPCE problem. In 3.2 we extend lsnp to 44 bits, but also we cannot meet our needs for the correct matching.Our Contribution. In order to solve this problem, we decompose these long encodings by 44 bits, then optimize, encrypt, and query the components, respectively. Suppose that the given entry with large coefficient is (αi,di). First, αi is decomposed by 44 bits; get a set of smaller components (αi,o,…,αi,1), where αi=αi,o∣⋯∣αi,1, αi,j∈Zt. Second, we construct and output multiple new entries with smaller coefficients (αi,o,di),…,(αi,1,di). Finally, these entries are mapped by ψ and optimized separately. As a result, we can represent and query all entries effectively in the database and solve the LPCE problem.


## 4. Secure Searching of Gene Data

Section4.1 introduces the optimized algorithm for coefficient and dimension of the DBX=∑i=0232-1ciXi. Section 4.2 describes the searching algorithm of gene data. Section 4.3 shows our experimental results.


### 4.1. Optimized Encoding Algorithm of Gene Data

#### 4.1.1. Coefficient Optimization

In order to solve LPCE problem and get an efficient scheme, it is necessary to optimize the coefficients of the polynomialDBX. Set t- as the minimum power of 44 bits, which is larger than the bound of α. We found that the length of the encoding α in the database is no more than 272 bits; thus set t-=2308, which is minimum multiple of 44 bits and larger than 272 bits. We use a general method to decompose αi∈Zt- into (αi,m,αi,m-1,…,αi,1)∈Ztm with the basis t, where αi=tm-1•αi,m+tm-2•αi,m-1+⋯+αi,1, m=t-/t. In this paper, we set t=211, and thus m=28. Algorithm 1 presents the coefficient optimization algorithm.Algorithm 1:Encoding genomic data: coefficient optimization.
Input:(αi,di)∈Zt-×Z233, 1≤i≤n, m=t-/t. ( 1 ) for i∈{1,…,n} do ( 2 )  α i ∈ Z t - → ( α i , m , … , α i , 1 ) ∈ Z t m, where αi=tm-1•αi,m+tm-2•αi,m-1+⋯+αi,1 ( 3 ) set o=0 ( 4 ) for j∈{m/4,…,1} do ( 5 ) if αi,4j=0, αi,4j-1=0, αi,4j-2=0, αi,4j-3=0 ( 6 )  o = o + 1 ( 7 ) else break ( 8 ) output {((αi,m-4o,di),…,(αi,m-4o-3,di))∈(Zt×Z233)4,…,((αi,4,di),…,(αi,1,di))}


#### 4.1.2. Dimension Optimization

Since the encoded integersdi from VCF files have bits size of about 32, while taking into account the safety and efficiency for implementation of HE schemes, a dimension 211<N<216 is considered appropriate. After decomposing the index di into di∗, di†, and di⊥, where di=di∗∣di†∣di⊥, we appoint that if the di∗, di†, and di⊥ have been decomposed for the previous index, then rebuild a set of polynomials and reassign their corresponding coefficients. Here we set the total groups of DB∗jX, DB†jX, DB⊥jX to k which means j∈1,…,k. Dimension optimization of encoding algorithm is shown as Algorithm 2.Algorithm 2:Encoding genomic data: dimension optimization.
Input:(αi,l,di)∈Zt×Z233,1≤i≤n, 1≤l≤4, N=211. ( 1 )  di→(di∗,di†,di⊥)∈Zt3, di=N2•di∗+N1•di†+di⊥ ( 2 )   c 1 , d 1 ∗ ∗ ← R Z t, c1,d1††←RZt, c1,d1⊥⊥←α1,j-c1,d1∗∗-c1,d1††∈Zt ( 3 )  D1∗=, D1†=, D1⊥=; d1∗∈D1∗, d1†∈D1†, d1⊥∈D1⊥ ( 4 ) for i∈2,…,n do ( 5 ) for j∈1,…,k do ( 6 ) if di∗∉Dj∗, di†∉Dj†, di⊥∉Dj⊥ then ( 7 )  c j , d i ∗ ∗ ← R Z t, cj,di††←RZt, cj,di⊥⊥←αi,l-cj,di∗∗-cj,di††∈Zt ( 8 ) else if di∗∈Dj∗, di†∉Dj†, di⊥∉Dj⊥ then ( 9 )  c j , d i † † ← R Z t, cj,di⊥⊥←αi,l-cj,di∗∗-cj,di††∈Zt ( 10 )  ⋯ ( 11 ) else if di∗∈Dj∗, di†∈Dj†, di⊥∉Dj⊥ then ( 12 )  c j , d i ⊥ ⊥ ← α i , l - c j , d i ∗ ∗ - c j , d i † † ∈ Z t ( 13 )  ⋯ ( 14 ) else if di∗∈Dj∗, di†∈Dj†, di⊥∈Dj⊥ then ( 15 ) break ( 16 ) output (cj∗,cj†,cj⊥)∈Rt3, (Dj∗,Dj†,Dj⊥) where j∈1,…,k


### 4.2. Secure Searching Algorithm of Gene Data

This section gives the general framework and complete process of secure searching algorithm, showing the process of our secure testing with details in Figure4.Figure 4
The secure testing process for genetic diseases with details.


#### 4.2.1. Database Encryption

The data owner (research institute) encodes the genomic information asDB∗(X), DB†(X), DB⊥(X) and encrypts the polynomials as (ctDB∗,ctDB†,ctDB⊥). The process is shown in Algorithm 3. Then the research institute submits the ciphertexts to the commercial cloud service (server).Algorithm 3:Database encoding and encryption.
Input:(αi,di)∈Z232×Ztm,  1≤i≤n, k∈Z. ( 1 )  DB′≜((αi,4,di),…,(αi,1,di))1≤i≤n← Algorithm 1  ((αi,di)1≤i≤n) ( 2 )  (DBl,j∗,DBl,j†,DBl,j⊥)l∈1,…,4,j∈1,…,k≜(cl,j∗,cl,j†,cl,j⊥)l∈{1,…,4},j∈{1,…,k}← Algorithm 2  (DB′) ( 3 ) for l∈1,…,4 do ( 4 ) for j∈1,…,k do c t D B l , j ∗ = RLWE.Enc ( D B l , j ∗ ( X ) , p k ); c t D B l , j † = RLWE.Enc ( D B l , j † ( X ) , p k ); c t D B l , j ⊥ = RLWE.Enc ( D B l , j ⊥ ( X ) , p k ). ( 5 ) output (ctDB∗,ctDB†,ctDB⊥)=(ctDBl,j∗,ctDBl,j†,ctDBl,j⊥)l∈1,…,4,j∈1,…,k


#### 4.2.2. Query Encryption

The user (hospital or medical institution) encodes the query(α,d) as X-d∗, X-d†, and X-d⊥, where d=d∗∣d†∣d⊥. Then the user sends the ciphertexts CTQ∗, CTQ†, CTQ⊥ to the server (commercial cloud service):(16)CTQ∗=RGSW.EncX-d∗,pk,CTQ†=RGSW.EncX-d†,pk,CTQ⊥=RGSW.EncX-d⊥,pk.


#### 4.2.3. Evaluation Phase

The server computes the hybrid multiplicationsctmult∗, ctmult†, and ctmult⊥ between the ciphertext of genetic database and the query. Let ct=ctmult∗+ctmult†+ctmult⊥. The server converts it into an LWE ciphertext and performs Modulus Switching operations. Then return the resulting ciphertext ctres to the user.(17)ctmult∗⟵CTQ∗⊡ctDB∗,ctmult†⟵CTQ†⊡ctDB†,ctmult⊥⟵CTQ⊥⊡ctDB⊥∈RQ2,ct=RLWE.AddctDB∗,ctDB†,ctDB⊥∈RQ2,ctconv∈ZQN+1⟵RLWE.Convctmult∈RQ2,ctres∈ZqN+1⟵LWE.ModSwitchctconv∈ZQN+1.


#### 4.2.4. Decryption Phase

The user decrypts the ciphertextctres with the secret key and gets the value α′ corresponding to the target position d in the database.(18)α′⟵LWE.Decctres∈ZqN+1,sk∈-1,0,1N+1.


### 4.3. Implementation of Secure Searching

In fully homomorphic encryption scheme, the homomorphic operations are usually achieved by the polynomial additions and polynomial multiplications as well as bootstrapping processes. As bootstrapping involves costly homomorphic decryption operations, and homomorphic decryption operation requires larger ciphertext modules to prevent decryption errors, this leads to inefficiencies of fully homomorphic encryption. The encryption scheme in this paper is a lattice-based somewhat homomorphic encryption scheme. As few homomorphic operations and no bootstrapping processes are involved in our scheme, a smaller module can ensure the correctness of the scheme. Therefore, the scheme succeeds the efficiency of the [KSC17] scheme. For a 10K database, only hundreds of multiplications and additions of polynomials are needed for the commercial cloud server, so the test results can quickly return. Details are provided in the evaluation phase of Section4.2.According to the application scenario of our scheme, we have implemented a three-party (hospital institution, commercial cloud service, and research institute) interactive experimental platform and done experiments on databases of different sizes (database with 428 entries, 10k entries, 100k entries). We implemented our scheme on a 64-bit single core (i7-6700HQ) at 2.60 GHz, with OS Win 7. The experimental data are listed in Tables3 and 4, and they are shown in Figures 5 and 6. The source code of our implementation is available on github https://github.com/lonyliu/genetest.Table 3
Time of secure searching of biomarkers (ms).
DB size(number of entries) Query-Enc DB-Enc Eval Dec 428 22 25 128 1 10K 21 124 634 1 100K 20 857 3247 1Table 4
Storage of secure searching of biomarkers (MB).
DB size(number of entries) Query DB Result 428 160 KB 4 1 10K 160 KB 23 5.6 100K 160 KB 99 24.7Figure 5
Time of secure searching of biomarkers.Figure 6
Storage of secure searching of biomarkers.Experimental results show that our scheme supports secure searching of gene data for all entries in the genome database (compared to about 5‰ incorrect searching for gene data in [KSC17]). What is more, based on guaranteeing high efficiency for secure searching of gene data, our scheme reduces the probability of searching error to less than 2-37.4.


## 4.1. Optimized Encoding Algorithm of Gene Data

### 4.1.1. Coefficient Optimization

In order to solve LPCE problem and get an efficient scheme, it is necessary to optimize the coefficients of the polynomialDBX. Set t- as the minimum power of 44 bits, which is larger than the bound of α. We found that the length of the encoding α in the database is no more than 272 bits; thus set t-=2308, which is minimum multiple of 44 bits and larger than 272 bits. We use a general method to decompose αi∈Zt- into (αi,m,αi,m-1,…,αi,1)∈Ztm with the basis t, where αi=tm-1•αi,m+tm-2•αi,m-1+⋯+αi,1, m=t-/t. In this paper, we set t=211, and thus m=28. Algorithm 1 presents the coefficient optimization algorithm.Algorithm 1:Encoding genomic data: coefficient optimization.
Input:(αi,di)∈Zt-×Z233, 1≤i≤n, m=t-/t. ( 1 ) for i∈{1,…,n} do ( 2 )  α i ∈ Z t - → ( α i , m , … , α i , 1 ) ∈ Z t m, where αi=tm-1•αi,m+tm-2•αi,m-1+⋯+αi,1 ( 3 ) set o=0 ( 4 ) for j∈{m/4,…,1} do ( 5 ) if αi,4j=0, αi,4j-1=0, αi,4j-2=0, αi,4j-3=0 ( 6 )  o = o + 1 ( 7 ) else break ( 8 ) output {((αi,m-4o,di),…,(αi,m-4o-3,di))∈(Zt×Z233)4,…,((αi,4,di),…,(αi,1,di))}


### 4.1.2. Dimension Optimization

Since the encoded integersdi from VCF files have bits size of about 32, while taking into account the safety and efficiency for implementation of HE schemes, a dimension 211<N<216 is considered appropriate. After decomposing the index di into di∗, di†, and di⊥, where di=di∗∣di†∣di⊥, we appoint that if the di∗, di†, and di⊥ have been decomposed for the previous index, then rebuild a set of polynomials and reassign their corresponding coefficients. Here we set the total groups of DB∗jX, DB†jX, DB⊥jX to k which means j∈1,…,k. Dimension optimization of encoding algorithm is shown as Algorithm 2.Algorithm 2:Encoding genomic data: dimension optimization.
Input:(αi,l,di)∈Zt×Z233,1≤i≤n, 1≤l≤4, N=211. ( 1 )  di→(di∗,di†,di⊥)∈Zt3, di=N2•di∗+N1•di†+di⊥ ( 2 )   c 1 , d 1 ∗ ∗ ← R Z t, c1,d1††←RZt, c1,d1⊥⊥←α1,j-c1,d1∗∗-c1,d1††∈Zt ( 3 )  D1∗=, D1†=, D1⊥=; d1∗∈D1∗, d1†∈D1†, d1⊥∈D1⊥ ( 4 ) for i∈2,…,n do ( 5 ) for j∈1,…,k do ( 6 ) if di∗∉Dj∗, di†∉Dj†, di⊥∉Dj⊥ then ( 7 )  c j , d i ∗ ∗ ← R Z t, cj,di††←RZt, cj,di⊥⊥←αi,l-cj,di∗∗-cj,di††∈Zt ( 8 ) else if di∗∈Dj∗, di†∉Dj†, di⊥∉Dj⊥ then ( 9 )  c j , d i † † ← R Z t, cj,di⊥⊥←αi,l-cj,di∗∗-cj,di††∈Zt ( 10 )  ⋯ ( 11 ) else if di∗∈Dj∗, di†∈Dj†, di⊥∉Dj⊥ then ( 12 )  c j , d i ⊥ ⊥ ← α i , l - c j , d i ∗ ∗ - c j , d i † † ∈ Z t ( 13 )  ⋯ ( 14 ) else if di∗∈Dj∗, di†∈Dj†, di⊥∈Dj⊥ then ( 15 ) break ( 16 ) output (cj∗,cj†,cj⊥)∈Rt3, (Dj∗,Dj†,Dj⊥) where j∈1,…,k


## 4.1.1. Coefficient Optimization

In order to solve LPCE problem and get an efficient scheme, it is necessary to optimize the coefficients of the polynomialDBX. Set t- as the minimum power of 44 bits, which is larger than the bound of α. We found that the length of the encoding α in the database is no more than 272 bits; thus set t-=2308, which is minimum multiple of 44 bits and larger than 272 bits. We use a general method to decompose αi∈Zt- into (αi,m,αi,m-1,…,αi,1)∈Ztm with the basis t, where αi=tm-1•αi,m+tm-2•αi,m-1+⋯+αi,1, m=t-/t. In this paper, we set t=211, and thus m=28. Algorithm 1 presents the coefficient optimization algorithm.Algorithm 1:Encoding genomic data: coefficient optimization.
Input:(αi,di)∈Zt-×Z233, 1≤i≤n, m=t-/t. ( 1 ) for i∈{1,…,n} do ( 2 )  α i ∈ Z t - → ( α i , m , … , α i , 1 ) ∈ Z t m, where αi=tm-1•αi,m+tm-2•αi,m-1+⋯+αi,1 ( 3 ) set o=0 ( 4 ) for j∈{m/4,…,1} do ( 5 ) if αi,4j=0, αi,4j-1=0, αi,4j-2=0, αi,4j-3=0 ( 6 )  o = o + 1 ( 7 ) else break ( 8 ) output {((αi,m-4o,di),…,(αi,m-4o-3,di))∈(Zt×Z233)4,…,((αi,4,di),…,(αi,1,di))}


## 4.1.2. Dimension Optimization

Since the encoded integersdi from VCF files have bits size of about 32, while taking into account the safety and efficiency for implementation of HE schemes, a dimension 211<N<216 is considered appropriate. After decomposing the index di into di∗, di†, and di⊥, where di=di∗∣di†∣di⊥, we appoint that if the di∗, di†, and di⊥ have been decomposed for the previous index, then rebuild a set of polynomials and reassign their corresponding coefficients. Here we set the total groups of DB∗jX, DB†jX, DB⊥jX to k which means j∈1,…,k. Dimension optimization of encoding algorithm is shown as Algorithm 2.Algorithm 2:Encoding genomic data: dimension optimization.
Input:(αi,l,di)∈Zt×Z233,1≤i≤n, 1≤l≤4, N=211. ( 1 )  di→(di∗,di†,di⊥)∈Zt3, di=N2•di∗+N1•di†+di⊥ ( 2 )   c 1 , d 1 ∗ ∗ ← R Z t, c1,d1††←RZt, c1,d1⊥⊥←α1,j-c1,d1∗∗-c1,d1††∈Zt ( 3 )  D1∗=, D1†=, D1⊥=; d1∗∈D1∗, d1†∈D1†, d1⊥∈D1⊥ ( 4 ) for i∈2,…,n do ( 5 ) for j∈1,…,k do ( 6 ) if di∗∉Dj∗, di†∉Dj†, di⊥∉Dj⊥ then ( 7 )  c j , d i ∗ ∗ ← R Z t, cj,di††←RZt, cj,di⊥⊥←αi,l-cj,di∗∗-cj,di††∈Zt ( 8 ) else if di∗∈Dj∗, di†∉Dj†, di⊥∉Dj⊥ then ( 9 )  c j , d i † † ← R Z t, cj,di⊥⊥←αi,l-cj,di∗∗-cj,di††∈Zt ( 10 )  ⋯ ( 11 ) else if di∗∈Dj∗, di†∈Dj†, di⊥∉Dj⊥ then ( 12 )  c j , d i ⊥ ⊥ ← α i , l - c j , d i ∗ ∗ - c j , d i † † ∈ Z t ( 13 )  ⋯ ( 14 ) else if di∗∈Dj∗, di†∈Dj†, di⊥∈Dj⊥ then ( 15 ) break ( 16 ) output (cj∗,cj†,cj⊥)∈Rt3, (Dj∗,Dj†,Dj⊥) where j∈1,…,k


## 4.2. Secure Searching Algorithm of Gene Data

This section gives the general framework and complete process of secure searching algorithm, showing the process of our secure testing with details in Figure4.Figure 4
The secure testing process for genetic diseases with details.


### 4.2.1. Database Encryption

The data owner (research institute) encodes the genomic information asDB∗(X), DB†(X), DB⊥(X) and encrypts the polynomials as (ctDB∗,ctDB†,ctDB⊥). The process is shown in Algorithm 3. Then the research institute submits the ciphertexts to the commercial cloud service (server).Algorithm 3:Database encoding and encryption.
Input:(αi,di)∈Z232×Ztm,  1≤i≤n, k∈Z. ( 1 )  DB′≜((αi,4,di),…,(αi,1,di))1≤i≤n← Algorithm 1  ((αi,di)1≤i≤n) ( 2 )  (DBl,j∗,DBl,j†,DBl,j⊥)l∈1,…,4,j∈1,…,k≜(cl,j∗,cl,j†,cl,j⊥)l∈{1,…,4},j∈{1,…,k}← Algorithm 2  (DB′) ( 3 ) for l∈1,…,4 do ( 4 ) for j∈1,…,k do c t D B l , j ∗ = RLWE.Enc ( D B l , j ∗ ( X ) , p k ); c t D B l , j † = RLWE.Enc ( D B l , j † ( X ) , p k ); c t D B l , j ⊥ = RLWE.Enc ( D B l , j ⊥ ( X ) , p k ). ( 5 ) output (ctDB∗,ctDB†,ctDB⊥)=(ctDBl,j∗,ctDBl,j†,ctDBl,j⊥)l∈1,…,4,j∈1,…,k


### 4.2.2. Query Encryption

The user (hospital or medical institution) encodes the query(α,d) as X-d∗, X-d†, and X-d⊥, where d=d∗∣d†∣d⊥. Then the user sends the ciphertexts CTQ∗, CTQ†, CTQ⊥ to the server (commercial cloud service):(16)CTQ∗=RGSW.EncX-d∗,pk,CTQ†=RGSW.EncX-d†,pk,CTQ⊥=RGSW.EncX-d⊥,pk.


### 4.2.3. Evaluation Phase

The server computes the hybrid multiplicationsctmult∗, ctmult†, and ctmult⊥ between the ciphertext of genetic database and the query. Let ct=ctmult∗+ctmult†+ctmult⊥. The server converts it into an LWE ciphertext and performs Modulus Switching operations. Then return the resulting ciphertext ctres to the user.(17)ctmult∗⟵CTQ∗⊡ctDB∗,ctmult†⟵CTQ†⊡ctDB†,ctmult⊥⟵CTQ⊥⊡ctDB⊥∈RQ2,ct=RLWE.AddctDB∗,ctDB†,ctDB⊥∈RQ2,ctconv∈ZQN+1⟵RLWE.Convctmult∈RQ2,ctres∈ZqN+1⟵LWE.ModSwitchctconv∈ZQN+1.


### 4.2.4. Decryption Phase

The user decrypts the ciphertextctres with the secret key and gets the value α′ corresponding to the target position d in the database.(18)α′⟵LWE.Decctres∈ZqN+1,sk∈-1,0,1N+1.


## 4.2.1. Database Encryption

The data owner (research institute) encodes the genomic information asDB∗(X), DB†(X), DB⊥(X) and encrypts the polynomials as (ctDB∗,ctDB†,ctDB⊥). The process is shown in Algorithm 3. Then the research institute submits the ciphertexts to the commercial cloud service (server).Algorithm 3:Database encoding and encryption.
Input:(αi,di)∈Z232×Ztm,  1≤i≤n, k∈Z. ( 1 )  DB′≜((αi,4,di),…,(αi,1,di))1≤i≤n← Algorithm 1  ((αi,di)1≤i≤n) ( 2 )  (DBl,j∗,DBl,j†,DBl,j⊥)l∈1,…,4,j∈1,…,k≜(cl,j∗,cl,j†,cl,j⊥)l∈{1,…,4},j∈{1,…,k}← Algorithm 2  (DB′) ( 3 ) for l∈1,…,4 do ( 4 ) for j∈1,…,k do c t D B l , j ∗ = RLWE.Enc ( D B l , j ∗ ( X ) , p k ); c t D B l , j † = RLWE.Enc ( D B l , j † ( X ) , p k ); c t D B l , j ⊥ = RLWE.Enc ( D B l , j ⊥ ( X ) , p k ). ( 5 ) output (ctDB∗,ctDB†,ctDB⊥)=(ctDBl,j∗,ctDBl,j†,ctDBl,j⊥)l∈1,…,4,j∈1,…,k


## 4.2.2. Query Encryption

The user (hospital or medical institution) encodes the query(α,d) as X-d∗, X-d†, and X-d⊥, where d=d∗∣d†∣d⊥. Then the user sends the ciphertexts CTQ∗, CTQ†, CTQ⊥ to the server (commercial cloud service):(16)CTQ∗=RGSW.EncX-d∗,pk,CTQ†=RGSW.EncX-d†,pk,CTQ⊥=RGSW.EncX-d⊥,pk.


## 4.2.3. Evaluation Phase

The server computes the hybrid multiplicationsctmult∗, ctmult†, and ctmult⊥ between the ciphertext of genetic database and the query. Let ct=ctmult∗+ctmult†+ctmult⊥. The server converts it into an LWE ciphertext and performs Modulus Switching operations. Then return the resulting ciphertext ctres to the user.(17)ctmult∗⟵CTQ∗⊡ctDB∗,ctmult†⟵CTQ†⊡ctDB†,ctmult⊥⟵CTQ⊥⊡ctDB⊥∈RQ2,ct=RLWE.AddctDB∗,ctDB†,ctDB⊥∈RQ2,ctconv∈ZQN+1⟵RLWE.Convctmult∈RQ2,ctres∈ZqN+1⟵LWE.ModSwitchctconv∈ZQN+1.


## 4.2.4. Decryption Phase

The user decrypts the ciphertextctres with the secret key and gets the value α′ corresponding to the target position d in the database.(18)α′⟵LWE.Decctres∈ZqN+1,sk∈-1,0,1N+1.


## 4.3. Implementation of Secure Searching

In fully homomorphic encryption scheme, the homomorphic operations are usually achieved by the polynomial additions and polynomial multiplications as well as bootstrapping processes. As bootstrapping involves costly homomorphic decryption operations, and homomorphic decryption operation requires larger ciphertext modules to prevent decryption errors, this leads to inefficiencies of fully homomorphic encryption. The encryption scheme in this paper is a lattice-based somewhat homomorphic encryption scheme. As few homomorphic operations and no bootstrapping processes are involved in our scheme, a smaller module can ensure the correctness of the scheme. Therefore, the scheme succeeds the efficiency of the [KSC17] scheme. For a 10K database, only hundreds of multiplications and additions of polynomials are needed for the commercial cloud server, so the test results can quickly return. Details are provided in the evaluation phase of Section4.2.According to the application scenario of our scheme, we have implemented a three-party (hospital institution, commercial cloud service, and research institute) interactive experimental platform and done experiments on databases of different sizes (database with 428 entries, 10k entries, 100k entries). We implemented our scheme on a 64-bit single core (i7-6700HQ) at 2.60 GHz, with OS Win 7. The experimental data are listed in Tables3 and 4, and they are shown in Figures 5 and 6. The source code of our implementation is available on github https://github.com/lonyliu/genetest.Table 3
Time of secure searching of biomarkers (ms).
DB size(number of entries) Query-Enc DB-Enc Eval Dec 428 22 25 128 1 10K 21 124 634 1 100K 20 857 3247 1Table 4
Storage of secure searching of biomarkers (MB).
DB size(number of entries) Query DB Result 428 160 KB 4 1 10K 160 KB 23 5.6 100K 160 KB 99 24.7Figure 5
Time of secure searching of biomarkers.Figure 6
Storage of secure searching of biomarkers.Experimental results show that our scheme supports secure searching of gene data for all entries in the genome database (compared to about 5‰ incorrect searching for gene data in [KSC17]). What is more, based on guaranteeing high efficiency for secure searching of gene data, our scheme reduces the probability of searching error to less than 2-37.4.


## 5. Conclusion

In this paper, we discussed how to privately perform secure genomic searching on a semitrusted business cloud with homomorphic encryption. Our scheme can support secure searching of multibase mutation for arbitrary length. What is more, we have solved three errors, hash collision error (HCE), coefficient combination error (CCE), and losing of partial coefficient error (LPCE), in [KSC17].Analysis and experimental results show that our scheme can search all the entries in database, compared to about 5‰ incorrect searching for gene data in [KSC17], and the probability of searching error is reduced to less than 2-37.4; thus our scheme can solve the problem of secure searching of gene data based on better homomorphic encryption. We will further study how to eliminate the impact of database capacity on communication traffic in future work.



---

*Source: 4635715-2018-03-20.xml*