CN110660450A - Safety counting query and integrity verification device and method based on encrypted genome data - Google Patents

Abstract

The present invention proposes a method for securely sharing and computing genome data on a not-so-honest cloud server. First, the method proposed in the present invention processes the biomedical data to ensure the privacy and integrity of the shared data. Secondly, the proposed method of the present invention uses the hashMap method to store data, which improves the encryption efficiency and efficiently realizes the secure count query. The present invention uses the existing single nucleotide polymorphism (SNP) sequence database to evaluate the method of the present invention, and experiments show that completing the count query is more flexible, easy to implement and high security for practical applications.

Description

A secure counting query and integrity verification device based on encrypted genomic data and method

technical field

The invention relates to the technical field of biological information, in particular to a secure count query and integrity verification device based on encrypted genome data.

Background technique

The practice of clinical medicine plays a vital role in healthcare, and the study of genomics is gaining popularity. The study of genomics can also help to identify potential associations between diseases and certain genes. To this end, biomedical researchers have conducted large-scale surveys of patients' clinical status and DNA sequence data. Most of the genetic data are analyzed. Both are based on the NIH Genome-Wide Association Study (GWAS). In order to improve the accuracy of research, data from different sources needs to be aggregated, and various services for sharing and storing data have been established for this purpose, such as the database of genotype and phenotype (dbGaP) in the United States and the Welcome Trust Biotechnology in the United Kingdom. bank plan. Genomic data concerns the privacy of patients, and a breach of the data could lead to many social and legal issues. For example, health insurance companies may refuse to insure personal information about mutations in genes that are known to have a specific cancer likelihood. Based on the sensitivity of genetic data, sharing genetic data among multiple institutions requires privacy-preserving methods to store and access genomic data.

Biomedical research is increasingly reliant on a large amount of genomic and clinical data, which has attracted much attention from scholars on how to ensure the privacy of the corresponding individuals and the overall security of the system when sharing and managing these data. In the past, to protect the sensitive information of subjects, multiple organizations shared data to remove important identifiers that could identify individuals. However, research has shown that subject identities can be easily deduced using automated methods. In order to protect the privacy of data, current research uses encrypted protocols to share, manage and analyze biomedical data, and outsource encrypted data to third-party cloud service providers with huge storage and computing resources. At the same time, third parties have also become potential targets that may cause the privacy of research subjects to be violated.

Security frameworks exist in the prior art to manage clinical genomic data in a centralized database in a specific form, and these frameworks propose methods for the secure sharing and storage of genomic data on a less-than-honest cloud service. First, the data owner sends the clinical information to a third-party organization for encryption and authentication, and the third-party organization sends a large amount of aggregated data to a cloud service for storage in a certain structure. Afterwards, the cloud service executes queries (such as the number of patient records with hypertension and specific genomic variant signatures) on behalf of the researcher, and returns the query results to the researcher. However, directly returning the query results to the researcher cannot rule out that attackers attack the researcher and capture the encryption protocol, and there are still data risks.

SUMMARY OF THE INVENTION

In order to carry out scientific research without revealing the identity of the data subject while querying shared medical data, the present invention proposes a security counting query and integrity verification device based on encrypted genome data, including a data owner terminal, a certification authority server, Cloud server, agency terminal, researcher terminal;

The certification authority terminal receives and encrypts the patient record from the data owner terminal;

The data owner terminal processes the patient's genomic data in the prescribed format and sends it to the certification authority server in clear text;

After the certification authority server obtains the data shared by different data owners, it builds a searchable hash map that aggregates the shared encrypted data, and sends the hash map to the cloud service;

The cloud service obtains encrypted data from the certification body and processes the encrypted query request sent by the agency terminal, executes the query request, and encrypts the query result and sends the query result to the agency terminal;

The researcher terminal responds to the user operation and sends the researcher query request to the agency terminal;

After receiving the researcher's query request, the agency terminal encrypts the query request data and sends the encrypted query request to the cloud server. After obtaining the query result from the cloud server, it decrypts the query result using the private key and sends it to the researcher's terminal.

Further, the cloud server generates a set of SNP data sets for a specific gene and the frequency value of the specific gene in the database, and then normalizes the value to the total number of records;

The cloud server expresses the total number of count queries as:

Among them, D is the database Q is the query, D={S ₁ , S ₂ ,...,S _n } represents the SNP sequence of n patients, and the count query is defined as finding the number of patients in D that satisfy multiple query conditions q of Q, The gene sequence of m SNP sites of a patient is represented as S={d ₁ ,d ₂ ,...,d _m }, where d _i (1≤i≤m) represents the SNP value of the i-th site of the patient.

Further, after receiving the data provided by the data owner, the certification body server creates an Entity of the map for the SNP sequence of each patient, and after all data processing, a mapping table M is generated, which contains the genotype and the genotype of each patient. Phenotypic information, after M is created, for each new record from the data owner, the certification authority server creates and updates the Entity information of M;

Each Entity contains the following:

key: The key value in Entity points to specific data, index value,

geno: indicates the SNP sequence of each patient, the SNP sequence of a patient is expressed as, S={d ₁ , d ₂ ,...,d _m }, sid is the unique identifier of the SNP site, representing a specific position in the gene sequence, Among them, the site identification of base pair d _i is sid=i, (1≤i≤n), which is expressed as

I: the phenotype dataset corresponding to the genome sequence,

count: In the database, the frequency of the current SNP sequence, indicating the total number of records matching the genotype and phenotype,

next: The key value of the next Entity.

Further, the complexity of the hash table created by the certification authority server is O(mn), where m is the number of records in the database, n is the number of different SNP sites in each sequence record, and each Entity is defined as θ. , whose components are denoted as θ(key, geno, I, count, next).

Further, the certification authority server uses the Bloom filter technology to process the phenotype data, inserts the corresponding phenotype into the Bloom filter for each SNPs record in the genome sequence, if multiple phenotypes are associated with the same genome sequence, Then insert them all into the Bloom filter of the genome sequence entity, and each Entity in M contains the Bloom filter value I, representing the phenotypic information corresponding to the genome sequence;

The certification authority server sets the hash function H used in the Bloom filter and the domain of the common alphabet Σ, where the domain of Σ is the set of all possible phenotypes, and for each entity in the genome sequence, inserts in the Bloom filter the corresponding Phenotype, each phenotype in Σ is mapped to a unique number, and that number is plugged into the Bloom filter,

The certification authority server uses the pseudo-random function F to select a random key k, and encrypts each Bloom filter as

The certification authority server sends the private key sk to the agency terminal, and provides the key k of the PRF and the hash function F _k used for Bloomfilter;

The certification authority server matches the location of the phenotype value I _q hash of the query request with the I _i hash location of each Entity;

进行解密。The certification authority server sends the PRF key k to the agency terminal, and uses the formula for the encrypted Bloom filter _I'i

to decrypt.

Further, the certification authority server generates a key pair (pk, sk), where pk is the public key and sk is the private key, and the public key pk is used to encrypt each entity in the hash table, and the encryption of the entity is represented as E. _pk (θ);

并将

发送给云服务器；The certification authority server expresses the hash map in which all entities in the hash map M are encrypted as

and will

Send to cloud server;

The certificate authority server sends the key pair (pk,sk) to the agency terminal.

Further, the cloud server sends the query result R _q to the agency, and the agency terminal decrypts the SNP value with the key sk and uses the Hamming code detection bit to verify the integrity of the data. For the returned query result that meets the query conditions:

R _q ={E _pk (count)|E _pk (B ₁ )|E _pk (B ₂ )|…|E _pk (B _num )|I _i ′}

将

重新计算汉明码检测位为T′；The agency terminal decrypts each SNP value with the private key sk, and the decrypted

Will

Recalculate the Hamming code detection bit as T';

The agency terminal determines whether the data is complete by comparing the correlation between T' and T _q .

If T′=T _q , the agency terminal determines that the data is safe and reliable;

进行纠正并更新哈希图；If T′≠T _q , and T′∈{h _A ,h _C ,h _G ,h _T }, then the agency terminal checks the bit T _q for the returned

make corrections and update the hashmap;

则代理机构终端判定原数据

被篡改，并且被篡改成其它内容，此时对于患者的SNP序列已经不可信，返回的查询结果计数值不可信。If T′≠T _q , and

Then the agency terminal determines the original data

If it has been tampered with and has been tampered with other content, the SNP sequence of the patient is no longer credible, and the returned query result count value is not credible.

The present invention also provides a security counting query and integrity verification method based on encrypted genome data, comprising the following steps:

The certification authority terminal receives and encrypts the patient record from the data owner terminal;

The data owner terminal processes the patient's genomic data in the prescribed format and sends it to the certification authority server in clear text;

After the certification authority server obtains the data shared by different data owners, it builds a searchable hash map that aggregates the shared encrypted data, and sends the hash map to the cloud service;

The cloud service obtains encrypted data from the certification body and processes the encrypted query request sent by the agency terminal, executes the query request, and encrypts the query result and sends the query result to the agency terminal;

The researcher terminal responds to the user operation and sends the researcher query request to the agency terminal;

After receiving the researcher's query request, the agency terminal encrypts the query request data and sends the encrypted query request to the cloud server. After obtaining the query result from the cloud server, it decrypts the query result using the private key and sends it to the researcher's terminal.

The beneficial effects of the present invention are:

(1) The present invention provides a secure system query framework. The invention uses the Paillier cryptosystem to encrypt the gene sequence, stores the encrypted data in a third-party cloud service, and performs a counting query without the cloud service knowing the key, thereby ensuring the privacy of the data. The reference agency decrypts and verifies the query result of the returned encrypted node to ensure the integrity of the data.

(2) The present invention provides a technology for processing raw data. The invention uses the hammering code technology to add detection bits to the gene data, and verifies the reliability of the counting query result by checking the returned query gene sequence.

(3) The model proposed by the present invention provides security guarantees for data privacy, query privacy and output privacy. The query initiator completes the secure interactive query through the agency and the cloud server.

(4) The present invention provides experimental studies to prove the feasibility of the method proposed by the present invention. For the query of 40 SNP loci of 5000 records, the Kantar certification authority server, oglu et al. and Canim et al., took 30 min and 80 s, respectively. The method proposed by the present invention takes 3.9s to execute the same query. Time is significantly shortened.

(5) The method of the present invention allows the outsourcing protocol to match the stored encrypted data and the query command in the cipher text state to complete the counting query. In order to protect data privacy, the present invention uses homomorphic encryption to encrypt genetic data. In order to verify the integrity of the query result, the present invention uses the Hamming code technology to add detection bits to the genomic data, and the query result can be verified based on the error correctability of the Hamming code detection bits, which has the advantages of ensuring the security and integrity of the genome data. good performance.

Description of drawings

FIG. 1 is a structural diagram of an apparatus according to an embodiment of the present invention.

FIG. 2 is a schematic diagram of the test results of an embodiment of the present invention.

FIG. 3 is a schematic diagram of a test result of an embodiment of the present invention.

FIG. 4 is a schematic diagram of the test results of an embodiment of the present invention.

Detailed ways

The present invention proposes a method for securely sharing and computing genome data on a not-so-honest cloud server. First, the method proposed in the present invention processes the biomedical data to ensure the privacy and integrity of the shared data. Secondly, the proposed method of the present invention uses the hashMap method to store data, which improves the encryption efficiency and efficiently realizes the secure count query. The present invention uses the existing single nucleotide polymorphism (SNP) sequence database to evaluate the method of the present invention, and experiments show that completing the count query is more flexible, easy to implement and high security for practical applications.

1 The design principles and beneficial effects of the present invention are described below

In the present invention, the objective of the present invention is to design a counting framework based on the secure query of outsourced genomic data, and determine the number of records in the database that match the query conditions through the counting query. The framework proposed by the present invention uses a secure encryption mechanism to process and store data, and performs security assessment on each stored record queried through a third-party agency terminal. Figure 1 shows the system framework of the present invention. The specific contributions of the present invention are as follows:

(1) The present invention provides a secure system query framework. The invention uses the Paillier cryptosystem to encrypt the gene sequence, stores the encrypted data in a third-party cloud service, and performs a counting query without the cloud service knowing the key, thereby ensuring the privacy of the data. The reference agency terminal decrypts and verifies the returned query result of the encrypted node to ensure the integrity of the data.

(2) The present invention provides a technology for processing raw data. The invention uses the hammering code technology to add detection bits to the gene data, and verifies the reliability of the counting query result by checking the returned query gene sequence.

(3) The model proposed by the present invention provides security guarantees for data privacy, query privacy and output privacy. The query initiator completes the secure interactive query through the agency terminal and the cloud server.

(4) The present invention provides experimental studies to prove the feasibility of the method proposed by the present invention. For the query of 40 SNP loci of 5000 records, the Kantar certification authority server, oglu et al. and Canim et al., took 30 min and 80 s, respectively. The method proposed by the present invention takes 3.9s to execute the same query.

2 The related concepts involved in the present invention are introduced as follows

The human genome contains basic data about human biology and private diagnostic information, and querying personal genomic data is very sensitive. To protect the privacy of data, Ayday et al. propose a privacy protection method and system based on homomorphic encryption, which uses storage and processing units to store sensitive data in encrypted form. Bruekers et al. propose a solution to the semi-honest attacker model, based on finite DNA homomorphic encryption, the complexity of which depends in part on the number of errors to tolerate. Using privacy-enhancing reversible bloom filters (PIBF), Eppstein et al. propose a privacy-preserving comparison method operating on compressed genomic data.

Privacy-preserving protocols for genomic data may also leak sensitive data. For the privacy-preserving query protocols, Atallah et al. proposed the first privacy-preserving sequence comparison algorithm. However, due to its unreasonable intensive computational requirements, Jha et al. introduced a garbled circuit for sequence comparison and distance computation using a secure two-party communication protocol. The main disadvantage of this solution is that it cannot handle large-scale computations. Troncoso-Pastoriza et al. provide DNA matching security privacy protection in a semi-honest environment, and propose a protocol for secure matching by inadvertently evaluating the automaton, but the protocol processing time is slightly longer. In order to improve the communication time problem of the Troncoso-Pastoriza et al. protocol, Blanton and Aliasgari et al. proposed a secure computing outsourcing protocol.

For the security outsourcing of genomic data for counting query, Kantar certification authority server oglu et al. first proposed an encryption model involving two third parties, but this model does not provide query privacy. Perl et al. proposed a method for searching biomedical data using a combination of Bloom filters and homomorphic encryption. They completely outsource the task of searching to a third-party cloud server. Canim et al. used tamper-resistant cryptographic hardware to provide a data storage server (DS), enabling secure storage, sharing, and querying of single third-party genomic data, and the size of the query is limited to the memory size of the tamper-resistant hardware. Xie et al. propose a protocol for a safe meta-analysis of genetic association studies, keeping the data in the premises of the respective data owners. Ignatenko and Petkovic proposed a solution for searching and matching DNA sequences in private DNA databases, representing DNA sequences as context trees for indexing information for privacy-preserving match and similarity searches. Context trees are built using a common compression technique called Context Tree Weighting (CTW).

The invention proposes a privacy and integrity protection method for genome data security count query. The method of the invention allows the outsourcing protocol to match the stored encrypted data and the query command in the cipher text state to complete the counting query. In order to protect data privacy, the present invention uses homomorphic encryption to encrypt genetic data. In order to verify the integrity of the query result, the present invention uses the Hamming code technology to add detection bits to the genomic data, and the query result can be verified based on the error correctability of the Hamming code detection bits, which has the advantages of ensuring the security and integrity of the genome data. good performance.

3. The device model of the present invention will be described below

3.1 System Design

In this section, the security framework proposed by the present invention is introduced. As shown in Figure 1, the framework contains five main players: data owner, certification authority server, cloud server, agency terminal, and researcher terminal. Each entity is responsible for performing different specific tasks to keep the entire system safe and functional. The information flow in this framework consists of two phases: the data integration phase and the query processing phase. During the data integration phase, the certificate authority server receives patient records from the data owner and encrypts them. In the query processing stage, the agency terminal encrypts the researcher's query conditions and sends them to the cloud service to execute the query.

Data owners are composed of multiple institutions that own genomic data, which may be hospitals, academic research institutions, or government research institutions, etc. These institutions process the patient's genomic data in a prescribed format and send it to the certification authority server in clear text.

As a third-party authority, the certification authority server is critical to the security of the framework. The main tasks of the certification authority server:

1) Process the data. After the certification authority server obtains the data shared by different data owners, it constructs a searchable hashMap that aggregates the shared encrypted data, and sends it to the cloud service. The user query operation is basically performed on the encrypted index tree. The index tree contains all records from the shared data, and for additions and deletions of records, the certification authority server can update the tree accordingly.

2) Generate a key. Sensitive data stored in the hash table needs to be encrypted with a key, and the executive agency needs to manage the public key for data encryption and the private key for decryption.

The cloud service obtains encrypted data from the certification authority server, and is responsible for processing encrypted query requests sent by the agency terminal. The cloud server executes the query and sends the encrypted result to the agency terminal.

Agency terminals handle all communications with researchers. After receiving the query request from the researcher, the agency terminal encrypts the query data, sends the encrypted query request to the cloud server, obtains the query result, decrypts it, and sends it to the researcher's terminal.

Scientists represent any individual or organization interested in performing queries on shared data stored in cloud servers. The researcher sends the query request to the agency terminal for encryption. After the agency terminal receives the encrypted query result, it decrypts the result with the private key and sends it to the researcher terminal, and the researcher terminal obtains the final output result.

3.2 Attack Model and Security Target

The goal of the present invention is that the cloud server does not know any information about the shared genome data, and neither the certification authority server nor the cloud server know about the query made by the researcher's terminal. The present invention assumes that the certificate authority server is a trusted entity. The certification authority server performs the same verification role as the NIH's Data Access Committee (DAC), which is responsible for the generation and encryption of hash tables and for verifying the identities of individuals and organizations requesting access to data. In the structural framework of the present invention, the present invention assumes that the cloud server is semi-honest, it itself correctly complies with the protocol, and does not intend to maliciously produce erroneous results. Unlike certification authority servers, cloud servers store a large amount of sensitive data and are also places to perform query processing. When a cloud server is captured, attackers can obtain large amounts of data, forge query results, or provide users with incomplete query results. Once the cloud server is attacked, the harm will greatly exceed the risk caused by the capture of the certificate authority server. Therefore, the present invention focuses on the situation where the cloud server is attacked.

The security objectives of the present invention mainly include the following two points:

(1) Data privacy and query privacy: Data privacy means that the cloud server cannot know the plaintext data stored by the data owner, which ensures that the attacker cannot understand the data stored in the cloud server; query privacy means that the cloud server cannot know the researcher’s terminal query The actual value of the request, which ensures that the query request received by the cloud server cannot be understood or deduced by an attacker.

(2) Data integrity: This goal is to verify the correctness of the query results returned to the researcher's terminal. If the query result returned by the cloud server to the Agency is deleted or forged by the attacker, the Agency can detect it and analyze and correct the query result based on the protocol proposed by the present invention.

4 The data processing method adopted by the present invention will be described below

The human genome is the complete set of genetic information of an organism. The genetic information is located inside the chromosomes, and each chromosome contains genes that are responsible for controlling various functions of the human body. Genome sequence data consists of four bases of nucleotides {A, C, G, T}, and differences in the arrangement of bases on each DNA strand lead to uniqueness between individuals. Most DNA sequences are conserved across the population, and about 0.5% of each individual's DNA differs from the reference genome due to genetic variation. Several types of variation patterns exist in the genome, such as single nucleotide polymorphisms (SNPs), copy number variations (CNVs), and rearrangements. Single nucleotide polymorphism refers to the DNA sequence polymorphism caused by the variation of a single nucleotide on the allele, and it is also the most common form of DNA variation. Most SNPs do not have any effect on human health. But some SNPs directly lead to the occurrence of certain diseases in the human body. Analysis of SNP sequences is common in genomic data studies. The dbGap database contains the patient's genome sequence and corresponding clinical information, and the genome sequence is the site information and diagnosis related to the SNP. The present invention assumes that a sequence S consists of multiple SNPs, expressed as S={α ₁ ,α ₂ ,...,α _γ }, where α _i represents the SNP at the i-th position, which is composed of a pair of nucleotides.

Table 1 Data sequence of SNPs

4.1 Security count query

For the study of genomic data, the most commonly performed task is to determine how many samples in the database satisfy certain characteristics. Count queries are an important step in genetic association studies, helping researchers to pinpoint genes that affect specific diseases in humans. For example, the researchers terminally queried whether there was an association between various SNPs in the DSP1 gene in an individual and diagnosis of Alzheimer's disease. Similar SNP-disease association studies are increasingly common in human genomics studies. For the biological researcher terminal, he needs to get the frequency value of a set of SNP data sets (eg, SNP ₁ =AG∩SNP ₂ =CT∩Diagnosis=Alzheimer's Disease) for a specific gene in the database, and then the value Normalized to the total number of records. For example, given a database D and a query Q, where D={S ₁ , S ₂ , . . . , Sn } represents the SNP sequences of _n patients. A count query can be defined as finding the number of patients in D that satisfy multiple query conditions q of Q. Suppose the gene sequence of m SNP loci of a patient is represented as S={d ₁ ,d ₂ ,...,d _m }, where d _i (1≤i≤m) represents the ith locus of the patient SNP value, then the total number of count queries can be expressed as:

Counting queries are a simple operation if the data is stored in plaintext, and traditional database management systems support counting queries. But database management systems cannot be used to query encrypted data. Then, how does the database respond to the count query of the encrypted value without decrypting the data? The present invention proposes a safe data processing method hashMap in Section 5, which is used to query the number of records under the conditions specified by the user without requiring Decrypt data stored in cloud servers.

4.2 Data encryption

In order to protect patient privacy, the certification authority server needs to encrypt the data in the database to prevent the leakage of sensitive data. In this section, the present invention will provide encryption schemes related to the framework of the present invention.

4.2.1 Hamming code

Hamming code (Hamming Code) is a linear debugging code, which inserts verification code into the transmitted message stream to detect and correct data bit errors that may occur during data storage and transmission. Hamming code utilizes the concept of parity bits, adding specific bits after the data bits to verify the validity of the data. The invention uses the Hamming code technology to process the genetic data, which can not only verify whether the data is valid, but also indicate the wrong information and correct it when the data is wrong.

The implementation principle of Hamming code is to insert k-bit binary data into the original data as a check digit, and change the original n-bit data into z-bit encoding. During encoding, the inequality 2 ^k -1 ≥ z needs to be satisfied, where z=n+k. A special check code is inserted into the 2 ^k-1 (k≥0, 2 k ^-1 <z) bits of the z-bit code obtained by the Hamming code, and the remaining bits are placed in order with the original code. The detailed encoding rules of Hamming code are as follows:

1) Fill in 0 in the 2 ^k-1 bits of the new coding bit (ie, check digit), and then fill in the remaining bits of the new coding with the source code in sequence.

2) The encoding method of the check digit is: the k-th check digit starts from the 2 ^k-1 bit of the new code, and every time the XOR of 2 k-1 bits is calculated, 2 ^{k-1 bits} are skipped, and then calculated The XOR of the next set of ^2k-1 bits, fill in the ^2k-1 bits.

For example, for adenine C in nucleotides, (C) 2 = 1000011, n = 7, from the formula 2 ^k -1 ≥ z, z = n + k, the minimum value of k can be obtained to be 4. Then add a 4-digit detection code:

将0填入新的编码的第1位，表示为00100000011。First fill in 0 in 2 ^k-1 bits, which is represented as 00100000011. The 1st digit check code is located in the 1st digit (2 ^{1 -1} ) of the new code (Hamming code starts from 1 digit), and the XOR of 1, 3, 5, 7, 9, and 11 digits is calculated as

Fill 0 into the first bit of the new code, which is represented as 00100000011.

填入新的编码的第8位表示为011000000011。最终C的二进制汉明码表示为表示为011000000011。The 2nd bit check code is located in the 2nd bit (2 ^2-1 ) of the new code, and the XOR of bits 2, 3, 6, 7, 10, and 11 is calculated as Fill in the second digit of the new code, which is represented as 011000000011. The 3rd bit check code is located in the 4th bit (2 ^3-1 ) of the new code, and the XOR of bits 4, 5, 6, and 7 is calculated as Fill in the 4th bit of the new code and represent it as 011000000011. The 4th bit check code is located in the 8th bit (2 ^4-1 ) of the new code, and the XOR of the 8-11 bits is calculated as

Fill in the 8th bit of the new code and represent it as 011000000011. The final binary Hamming code representation of C is represented as 011000000011.

The invention uses the Hamming code to process the original data and utilizes its error correction function to detect the counting query result. For the four kinds of nucleotides A, C, G, T, calculate the corresponding AS certification authority server I code binary check digit {h _A , h _C , h _G , h _T }, where h _A =0001, h _C =0100, h _G =1101, h _T =0011. Suppose a pair of nucleotides d _i is represented as B _i after adding the detection bit t, where t is the combination of any two elements in the set {h _A , h _C , h _G , h _T }, there are ²⁴ combinations in total. For example, the binary representation of d _i = CC is 1000011 1000011, and after adding detection bits 0100, 0100 to the 1st, 2nd, 4th and 8th bits of each base, it is represented as 01100000011 01100000011.

4.2.2 Paillier cryptosystem

In order to achieve the simplicity and flexibility of the architecture, the present invention uses the Paillier cryptosystem encryption algorithm. The encryption algorithm satisfies semantic security, ensuring that an adversary with limited computing power and ciphertext cannot obtain plaintext information. Paillier cryptosystem is a probabilistic asymmetric algorithm for public key encryption that produces different ciphertexts when the same message is encrypted multiple times. In the Paillier encryption algorithm, a pair of keys is generated, one is the private key sk, and the other is the public key pk. The public and private keys are used for data encryption and decryption, respectively. The Paillier cryptosystem can be defined as follows. (refer to wiki translation)

通过对g进行模块乘法逆运算来确定n的划分顺序：μ＝(L(g^λmodη²))^-1modη，其中L被定义

由此可得公钥(η,g)，私钥(λ，μ)。Key generation phase: randomly select two large prime numbers p and q so that they are independent of each other gcd(pq,(p-1)(q-1))=1. Calculate η=pq and λ=lcm(p-1,q-1), choose a random integer g such that

The division order of n is determined by performing a modular multiplication inverse operation on g: μ=(L(g ^λ mod η ² )) ⁻¹ mod η, where L is defined

From this, the public key (η, g) and the private key (λ, μ) can be obtained.

Encryption stage: For the message ω (0≤m<η) that needs to be encrypted, select a random number γ (0<γ<η) to calculate the ciphertext c: c=g ^ω ·γ ^η modη ² .

解密后的明文表示为：ω＝L(c^λmodη²)·μmodη。Decryption stage: For the ciphertext c that needs to be decrypted,

The decrypted plaintext is expressed as: ω=L(c ^λ modη ² )·μmodη.

Homomorphic property: Assuming there are two data ω ₁ and ω ₂ , the product of their ciphertexts is decrypted as the sum of their corresponding plaintexts: E _sk (E _pk (ω ₁ )·E _pk (ω ₂ )modη ² ) =ω ₁ +ω ₂ modη.

Adding a plaintext is the exponent value of another plaintext, and after decryption, it is the product of the two plaintexts:

其中1≤j≤n。加密过程中每个基因组数据

通过汉明码添加检测位表示为

对

加密可表示为

其中“|”表示将检测位添加到碱基对

中。每个数据加密的密文表示为：Assuming that there are n patients in the database, Data=(S ¹ , S ² ,...,S ⁿ ) represents the gene sequence data set in the database, and the genomic data of the SNP sequence of the jth patient can be expressed as

where 1≤j≤n. Data per genome during encryption

Adding detection bits via Hamming code is expressed as

right

Encryption can be expressed as

Where "|" means that the bit will be detected Add to base pair

middle. The encrypted ciphertext of each data is represented as:

5 The system design of the present invention will be described below

In this section, the present invention will introduce the data processing model used by the present invention. First, the certification body server processes the patient's genetic sequence and clinical information in the database. The patient's clinical information mainly includes some phenotypic disease diagnosis. It is assumed that there are I= _{ I ₁ , I ₂ , . Each patient can have one or more diseases. Afterwards, the genotype and phenotype data of patient cases are discussed how to integrate it into the hashMap. As shown in table1 are the genotype sequences and phenotype types of 5 patients.

5.1 Generate hashMap

After the certification body server receives the data provided by the data owner, it creates an Entity of a hashMap for the SNP sequence of each patient, and after all data processing, a mapping table M is generated, which contains the genotype and phenotype information of each patient. . After M is created, for each new record from the data owner, the certification authority server needs to create and update the Entity information of M. Each Entity contains the following:

key: The key value in the Entity points to the specific data, the index value.

geno: part of the value in Entity. It is the SNP sequence for each patient. For example, the SNP sequence of a patient is represented as S={d ₁ ,d ₂ ,...,d _m }, and sid is the unique identifier of the SNP site, representing a specific position in the gene sequence. The site identification of base pair d _i is sid=i, (1≤i≤n). It can be expressed as

I: The phenotype dataset corresponding to the genome sequence.

count: In the database, the frequency of the current SNP sequence, indicating the total number of records matching the genotype and phenotype.

next: the key value of the next Entity

Table 2 Hash Map for Table1

The complexity of creating the hash table is O(mn), where m is the number of records in the database and n is the number of distinct SNP sites in each sequence record. The present invention defines each Entity as θ, and its components are expressed as θ(key, geno, I, count, next). According to the characteristics of the hash table and the data of table1, the present invention can obtain table2.

5.2 Encrypted hashMap

5.2.1 Encryption of Bloom Filters

Each Entity in M contains a Bloom filter value of I, representing the phenotypic information corresponding to that genomic sequence. The certification authority server uses Bloom filter technology to process the phenotypic data. For each SNPs record in the genome sequence, the corresponding phenotype will be inserted in the Bloom filter. If multiple phenotypes are associated with the same genomic sequence, the present invention inserts all of them into the Bloom filter for that genomic sequence entity.

The certificate authority server sets the hash function H used in the Bloom filter and the domain of the common alphabet Σ. The domain of Σ is the set of all possible phenotypes. For each entity in the genome sequence, the corresponding phenotype will be inserted in the Bloom filter. Each phenotype in Σ is mapped to a unique number, and this number will be interpolated into the Bloom filter.

The length of the Bloom filter on each Entity in M is the same. In order to encrypt the Bloom filter, the present invention uses AES in the CTR mode with a key size of 128 bits. The certification authority server uses a pseudo-random function (PRF) F to select a random key k, and encrypts each Bloom filter as

This encryption process is done while the entity's other data is being encrypted. In addition to sending the private key sk to the agency terminal, the certification authority server also needs to provide the key k of the PRF and the hash function F _k used for the Bloom filter. In order to match phenotypes from a query during a search, the present invention requires matching the location of the _Iq hash of the phenotype value Iq requested by the query with the location of the _Ii hash of each Entity. If all positions set to 1 in _Iq are also set to 1 in _Ii , it means that the phenotype from the query matches the phenotype stored in the tree node.

Since the bloom filters represented at each node of the tree are encrypted, in order to check the position of any of these bloom filters, the present invention first needs to decrypt it. The certificate authority server provides the PRF key k to the agency terminal. Decrypt encrypted Bloom filter _I'i using in-circuit SFE

5.2.2 Paillier Cryptosystem encryption

最后，认证机构服务器将

发送给云服务器。同时，认证机构服务器将密钥对(pk,sk)发送给代理机构终端。The certificate authority server encrypts all entities in M using the Paillier Cryptosystem. The certificate authority server uses the key generation algorithm to generate a key pair (pk,sk) for the homomorphic encryption scheme, where pk is the public key and sk is the private key; each entity in the hash table is encrypted using the public key pk. In order to make the whole search process fast enough while maintaining the security of the system, the present invention only encrypts the sensitive attributes of each entity. Since the cloud server is semi-honest in the system of the present invention, it must be able to ensure that the queryer knows the next key value of the entity, so the present invention does not need to encrypt the next information. The encryption of the entity can be expressed as E _pk (θ). After encryption, each entity is like θ (key, E _pk (geno), E _pk (count), I′ _i , next). All entities in the definition M of the present invention are represented by the encrypted hashMap as

Finally, the certificate authority server will

sent to the cloud server. At the same time, the certificate authority server sends the key pair (pk, sk) to the agency terminal.

5.3 Query encrypted hashMap

执行代理机构终端发送的加密查询请求。查询的主要思想是查询满足查询表型为I_q，并且满足匹配存储在geno中的特定位点的基因序列。云服务器需要知道研究人员终端查询请求中的sid,将存储在Entity中的geno的特定位点的SNP与研究人员终端查询条件中位点的SNP相匹配。由于SNP的值都被加密，并且本发明使用的加密方案是概率性的，云服务器无法确定这些值是否匹配。云服务器可以将加密的valn值发送给代理机构终端，由代理机构终端解密加密的SNP并检查相等性。The cloud server receives the data sent by the certification authority server

Execute the encrypted query request sent by the agency terminal. The main idea of the query is to query the gene sequence that satisfies the query phenotype I _q , and that matches the specific locus stored in the geno. The cloud server needs to know the sid in the researcher's terminal query request, and matches the SNP of the specific site of the geno stored in the Entity with the SNP of the site in the researcher's terminal query condition. Since the values of the SNPs are all encrypted, and the encryption scheme used in the present invention is probabilistic, the cloud server cannot determine whether the values match. The cloud server can send the encrypted valn value to the agency terminal, which decrypts the encrypted SNP and checks for equality.

Suppose that the researcher terminal sends a query request Q _q =(q ₁ ∩q ₂ ∩...∩q _num ∩I _q ), in which there are num query conditions. q _l (1≤l≤num) represents the specific gene value of the SNP at a certain locus. For example, the conditions in the query Q _q are SNP ₂ =CC, SNP ₃ =TT, SNP ₅ =AG, I _q =I ₁ , and q ₁ represents the condition SNP ₂ =CC. The agency terminal adds the detection code B _q = (T _q |q) to the base pair of each query condition q. The query condition is encrypted with the public key pk, and the query condition for each site can be expressed as θ _q (sid, E _pk (B _q )). The encrypted query request is connected as: E _pk (θ _q )=E _pk (θ ₁ )∩E _pk (θ ₂ )∩…∩E _pk (θ _num )∩I _q ′.

For example, perform the above query Q _q operation on M in table2, traverse the SNP values of sid=2, sid=3, and sid=5 of the geno site in each entity, and send these values to an agency terminal for decryption and verification, you can Find the cases in the database that satisfy the query conditions. As shown in Figure 2, only case#1 satisfies the query condition, and the query count result of each researcher terminal is returned as count=1.

5.4 Data Integrity Analysis

The cloud server sends the query result R _q to the agency terminal, and the agency terminal decrypts the SNP value with the key sk. In order to ensure the privacy of the information exchanged between the agency terminal and the cloud server, the present invention adopts the Hamming code detection bit to verify the integrity of the data. For the returned query results that meet the query conditions:

R _q ={E _pk (count)|E _pk (B ₁ )|E _pk (B ₂ )|…|E _pk (B _num )|I _i ′}

本发明将

重新计算汉明码检测位为T′。本发明通过对比T′与T_q的相关性来判定数据是否完整。The agency terminal decrypts each SNP value with the private key sk, and the decrypted

The present invention will

The Hamming code detection bit is recalculated as T'. The present invention determines whether the data is complete by comparing the correlation between T' and _Tq .

1) T′=T _q , in this case, it means that the data is complete and the data is safe and reliable;

进行纠正并可更新hashMap。返回的计数值count已经不可信。2) T′≠T _q , and T′∈{h _A ,h _C ,h _G ,h _T }, indicating that the geno value in the query condition has been tampered with, but it is still four cores of A, C, G, and T. A combination of glucosinolates. can be returned by detecting the bit T _q pair

Make corrections and update hashMap. The returned count value count is no longer reliable.

表示原数据

被篡改，并且被篡改成其它内容，此时对于患者的SNP序列已经不可信，返回的查询结果计数值不可信。3) T′≠T _q , and

represent the original data

If it has been tampered with and has been tampered with other content, the SNP sequence of the patient is no longer credible, and the returned query result count value is not credible.

Regarding the security analysis, the present invention only assumes that the geno sequences in the database are disclosed to the participants, which will lead to serious security problems. The present invention evaluates the security of the privacy protocol and system proposed by the present invention considering the ability of participants to infer information at different stages of the system. The leakage profiles of the different actors in the model proposed by the present invention are given below.

Data leakage in the construction and encryption stage of HashMap: The certification authority server, as a trusted entity, is responsible for the generation and encryption of M, and there is no data leakage on the certification authority server at this stage.

Leakage of the cloud server in each query: During the query execution process, the cloud server does not involve plaintext information at all. Therefore, the data information will not be disclosed to the cloud server during the query stage.

Leakage of each query to the agency terminal and the researcher terminal: The main contribution of the agency terminal is to encrypt the query request from the researcher terminal and send it to the cloud server, receive the query result returned by the cloud server, and decrypt it and return it to the cloud server. Researcher terminal. For the SNP query result returned to the agency terminal, the present invention uses the Hamming code technology to verify, and the researcher's terminal cannot directly infer any information from the Hamming code detection bits. Here, the present invention does not consider any privacy leakage in the output. Therefore, the system is safe and reliable.

6 The experimental analysis data of the present invention will be described below

Since the beginning of the Human Genome Project, researchers have terminally reported a large number of SNPs. The availability of high-quality SNP loci as candidate genes makes it possible to study the association between candidate genes and the whole genome. Linkage disequilibrium (LD) techniques have been widely used to develop high-quality SNP marker maps. When applied to disease-gene mapping, LD is assessed by association analysis, which entails comparing affected disease (eg, a diagnosis of Alzheimer's) to control individuals (eg, no diagnosis of Alzheimer's) ) between allele or haplotype frequencies. Toivonen et al. proposed a LD mapping data mining method called Haplotype Pattern Mining (HPM) for generating simulated SNP datasets. The data privacy protection framework provided by the present invention evaluates its practicality by conducting test experiments using simulated SNP data sets. The source code of the system of the present invention is realized by JAVA program coding language. The experimental environment of the present invention is Intel i7-4710MQ (4-core 1.6GHz) CPU and 8GB memory; the software environment is Windows 10 operating system and IntelliJ IDEA running platform. In the experiment, the present invention provides two different machines to run the cloud server and the certification authority server. In the present invention, the Hamming code technology is used in the experiment to add detection bits to the genetic data, and the 1024-bit Paillier encryption technology is used.

In the safe count query experiments of the present invention, the present invention used four datasets with 500, 1000 and 5000 SNPs and four different queries involving 10, 20, 30 and 40 randomly selected SNP sequences size. The present invention tests the influence of different record numbers on the construction time of the hashMap. The results of the present tests were compared to the index tree method used by Mohammad Zahidul Hasan et al. and the method of M. Canim et al using cryptographichardware SCPs to process sensitive biomedical data. The experimental results show that the method proposed by the present invention is superior in both encryption time and query execution time. This experiment is analyzed from the following three aspects:

(1) HashMap generation time. It refers to the time it takes to process a genome database and build a hashMap using genotypes and phenotypes. The present invention analyzes the creation time of datasets containing 500 and 1000 numbers of SNPs, as shown in Figure 2. Experiments show that with the increase of the number of SNPs, the time required to consume increases continuously. Compared with the creation time of the index tree used by Mohammad Zahidul Hasan et al., the method of the present invention takes more time to create the index tree, but it only occupies a small proportion of the experiment running time in seconds.

(2) Encryption time. In the method of the present invention, the encryption time for data is mainly consumed in encrypting the base pair and count value of each entity. The CTR scheme used in the present invention does not take a long time to encrypt the Bloom filter, which can be ignored. Second, the time to encrypt also depends on the total number of sequences in the SNP dataset. Figure 3, the present invention analyzes the encryption time of data sets with 500 and 1000 SNPs. With the increase of the number of SNPs, the encryption time that needs to be consumed increases continuously, and the method of the present invention has obvious advantages in encryption time compared with the Index Tree. For example, for 1000records, the present invention only needs 2.11min,

(3) Query time. The query time refers to the time taken by the researcher terminal to provide the query request to the return result. To calculate the query time, the present invention randomly selects SNP sequences of size 10, 20, 30 and 40, and executes the query on 5000 records. Figure 4 lists the execution times of these query sizes on an encrypted hashMap. Since the phenotypic information in the entities in the hashMap needs to be searched and matched, the present invention needs to traverse and query all the entities in the hashMap to obtain gene sequences that satisfy the query conditions. In Fig. 2, the present invention provides a comparison between the query time executed by the method of the present invention and the method execution time of the present invention. With the increase of the number of queries, the execution time of the present invention is linearly increased, and the time is in seconds.

Table 3 Comparison of query execution time on 5000 records

By changing the record size of the count query and the total number of query data sets, the present invention analyzes the time to store data using a hashMap and the time to execute a query, and compares with the methods already proposed. The method of the invention effectively protects the privacy of the data by using the hashMap to store the data and using the homomorphic encryption scheme. The method of the present invention supports the storage of large data sets. The processing and encryption of the entity's sensitive data does not have a direct impact on the number of records. The present invention proposes to use the error correction property of Hamming code to add detection bits to the original data, and to verify the integrity of the returned result at the agency terminal, so as to effectively ensure the accuracy of the result returned to the researcher's terminal. These characteristics make the method proposed by the present invention more secure and efficient to perform counting query on encrypted data.

Aiming at the security counting query problem of encrypted genome data, the invention proposes a safe and effective genome data outsourcing method on the basis of analyzing the existing scheme. In order to realize the privacy of data, this method stores the data in the database as a hashMap, and outsources the stored data to a third-party cloud server. By using the third-party agency terminal, the security counting query of the researcher's terminal in the cloud service is realized. In order to verify the integrity of the data, the present invention proposes to use the hammering code technology to add detection bits to the genomic data to ensure that no sensitive genetic data is displayed during the data processing and query execution stages.

Claims (8)

1. a security counting query and integrity verification device based on encrypted genomic data, is characterized in that, comprises data owner terminal, certification authority server, cloud server, agency terminal, researcher terminal; The certification authority terminal receives and encrypts the patient record from the data owner terminal; The data owner terminal processes the patient's genomic data in the prescribed format and sends it to the certification authority server in clear text; After the certification authority server obtains the data shared by different data owners, it builds a searchable hash map that aggregates the shared encrypted data, and sends the hash map to the cloud service; The cloud service obtains encrypted data from the certification body and processes the encrypted query request sent by the agency terminal, executes the query request, and encrypts the query result and sends the query result to the agency terminal; The researcher terminal responds to the user operation and sends the researcher query request to the agency terminal; After receiving the researcher's query request, the agency terminal encrypts the query request data and sends the encrypted query request to the cloud server. After obtaining the query result from the cloud server, it decrypts the query result using the private key and sends it to the researcher's terminal. 2. a kind of security counting query and integrity verification device based on encrypted genome data as claimed in claim 1, is characterized in that, The cloud server generates a set of SNP datasets for a specific gene and the frequency value of the specific gene in the database, and then normalizes the value to the total number of records; The cloud server expresses the total number of count queries as:

Among them, D is the database Q is the query, D={S ₁ , S ₂ ,...,S _n } represents the SNP sequence of n patients, and the count query is defined as finding the number of patients in D that satisfy multiple query conditions q of Q, The gene sequence of m SNP sites of a patient is represented as S={d ₁ ,d ₂ ,...,d _m }, where d _i (1≤i≤m) represents the SNP value of the i-th site of the patient. 3. a kind of security counting query and integrity verification device based on encrypted genome data as claimed in claim 1, is characterized in that, After the certification body server receives the data provided by the data owner, it creates an Entity of the map for the SNP sequence of each patient, and after all data processing, a mapping table M is generated, which contains the genotype and phenotype information of each patient. , after creating M, for each new record from the data owner, the certification authority server creates and updates the Entity information of M; Each Entity contains the following: key: The key value in Entity points to specific data, index value, geno: indicates the SNP sequence of each patient, the SNP sequence of a patient is expressed as, S={d ₁ , d ₂ ,...,d _m }, sid is the unique identifier of the SNP site, representing a specific position in the gene sequence, Among them, the site identification of base pair d _i is sid=i, (1≤i≤n), which is expressed as I: the phenotype dataset corresponding to the genome sequence, count: In the database, the frequency of the current SNP sequence, indicating the total number of records matching the genotype and phenotype, next: The key value of the next Entity. 4. a kind of security counting query and integrity verification device based on encrypted genome data as claimed in claim 3, is characterized in that, The complexity of the hash table created by the certification authority server is O(mn), where m is the number of records in the database, n is the number of different SNP sites in each sequence record, and each Entity is defined as θ, which consists of The part is denoted as θ(key, geno, I, count, next). 5. a kind of security counting query and integrity verification device based on encrypted genome data as claimed in claim 1, is characterized in that, The certification authority server uses the Bloom filter technology to process the phenotype data. For each SNPs record in the genome sequence, insert the corresponding phenotype in the Bloom filter. If multiple phenotypes are associated with the same genome sequence, they will be added. All are inserted into the Bloom filter of the genome sequence entity, each entity in M contains the Bloomfilter value I, indicating the phenotypic information corresponding to the genome sequence; The certification authority server sets the hash function H used in the Bloom filter and the domain of the common alphabet Σ, where the domain of Σ is the set of all possible phenotypes, and for each entity in the genome sequence, inserts in the Bloom filter the corresponding Phenotype, each phenotype in Σ is mapped to a unique number, and that number is plugged into the Bloom filter, The certification authority server uses the pseudo-random function F to select a random key k, and encrypts each Bloom filter as

The certification authority server sends the private key sk to the agency terminal, and provides the key k of the PRF and the hash function F _k used for Bloomfilter; The certification authority server matches the location of the phenotype value I _q hash of the query request with the I _i hash location of each Entity; The certification authority server sends the PRF key k to the agency terminal, and adopts the formula for the encrypted Bloom filterI _i '

to decrypt. 6. a kind of security counting query and integrity verification device based on encrypted genome data as claimed in claim 1, is characterized in that, The certification authority server generates a key pair (pk, sk), where pk is the public key and sk is the private key, and uses the public key pk to encrypt each entity in the hash table, expressing the encryption of the entity as E _pk (θ ); The certification authority server expresses the hash map in which all entities in the hash map M are encrypted as

and will

Send to cloud server; The certificate authority server sends the key pair (pk,sk) to the agency terminal. 7. a kind of security counting query and integrity verification device based on encrypted genome data as claimed in claim 1, is characterized in that, The cloud server sends the query result R _q to the agency, and the agency terminal decrypts the SNP value with the key sk and uses the Hamming code to check the integrity of the data. For the returned query result that meets the query conditions: R _q ={E _pk (count)|E _pk (B ₁ )|E _pk (B ₂ )|…|E _pk (B _num )|I _i ′} The agency terminal decrypts each SNP value with the private key sk, and the decrypted

Will

Recalculate the Hamming code detection bit as T'; The agency terminal determines whether the data is complete by comparing the correlation between T' and T _q . If T′=T _q , the agency terminal determines that the data is safe and reliable; If T′≠T _q , and T′∈{h _A ,h _C ,h _G ,h _T }, then the agency terminal checks the bit T _q for the returned

make corrections and update the hashmap; If T′≠T _q , and

Then the agency terminal determines the original data If it has been tampered with and has been tampered with other content, the SNP sequence of the patient is no longer credible, and the returned query result count value is not credible. 8. A security counting query and integrity verification method based on encrypted genomic data, comprising the following steps: The certification authority terminal receives and encrypts the patient record from the data owner terminal; The data owner terminal processes the patient's genomic data in the prescribed format and sends it to the certification authority server in clear text; After the certification authority server obtains the data shared by different data owners, it builds a searchable hash map that aggregates the shared encrypted data, and sends the hash map to the cloud service; The cloud service obtains encrypted data from the certification body and processes the encrypted query request sent by the agency terminal, executes the query request, and encrypts the query result and sends the query result to the agency terminal; The researcher terminal responds to the user operation and sends the researcher query request to the agency terminal; After receiving the researcher's query request, the agency terminal encrypts the query request data and sends the encrypted query request to the cloud server. After obtaining the query result from the cloud server, it decrypts the query result using the private key and sends it to the researcher's terminal.

Images