Efficient privacy-preserving whole-genome variant queries

Abstract

Motivation: Diagnosis and treatment decisions on genomic data have become widespread as the cost of genome sequencing decreases gradually. In this context, disease-gene association studies are of great importance. However, genomic data are very sensitive when compared to other data types and contains information about individuals and their relatives. Many studies have shown that this information can be obtained from the query-response pairs on genomic databases. In this work, we propose a method that uses secure multi-party computation to query genomic databases in a privacy-protected manner. The proposed solution privately outsources genomic data from arbitrarily many sources to the two non-colluding proxies and allows genomic databases to be safely stored in semi-honest cloud environments. It provides data privacy, query privacy and output privacy by using XOR-based sharing and unlike previous solutions, it allows queries to run efficiently on hundreds of thousands of genomic data.

Results: We measure the performance of our solution with parameters similar to real-world applications. It is possible to query a genomic database with 3 000 000 variants with five genomic query predicates under 400 ms. Querying 1 048 576 genomes, each containing 1 000 000 variants, for the presence of five different query variants can be achieved approximately in 6 min with a small amount of dedicated hardware and connectivity. These execution times are in the right range to enable real-world applications in medical research and healthcare. Unlike previous studies, it is possible to query multiple databases with response times fast enough for practical application. To the best of our knowledge, this is the first solution that provides this performance for querying large-scale genomic data.

Availability and implementation: https://gitlab.com/DIFUTURE/privacy-preserving-variant-queries.

Supplementary information: Supplementary data are available at Bioinformatics online.

Fig. 1.

General system architecture of our solution. Genomic variant stores $H_1\dots H_N$ communicate with the two non-colluding proxy servers D₁ and D₂. Users can query all data through these proxy servers in a secure manner

Fig. 2.

Encoding of a single variant

Fig. 3.

Generation of the variant tree

Fig. 4.

Comparison of time performance of our solution and Demmler et al.’s solution (Demmler et al., 2017) under various numbers of variants/numbers of query variants. (a) Runtime with a single patient, a varying number of variants, a fixed variant length = 48 bit, and 5 query variants, (b) runtime with a single patient, 100 000 variants, a fixed variant length = 48 bit and a varying number of query variants

Fig. 5.

Time performance of our solution under various numbers of masks/numbers of patients. (a) Runtime with a varying number of masks, 1 000 000 variants, a fixed variant length = 48 bit, and 5 query variants, (b) Runtime with a varying number of patients, 1 000 000 variants, a fixed variant length = 64 bit and 5 query variants