Genomic datasets are often associated with sensitive phenotypes. Therefore, the leak of membership information is a major privacy risk. Genomic beacons aim to provide a secure, easy to implement, and standardized interface for data sharing by only allowing yes/no queries on the presence of specific alleles in the dataset. Previously deemed secure against re-identification attacks, beacons were shown to be vulnerable despite their stringent policy. Recent studies have demonstrated that it is possible to determine whether the victim is in the dataset, by repeatedly querying the beacon for his/her single nucleotide polymorphisms (SNPs). In this work, we propose a novel re-identification attack and show that the privacy risk is more serious than previously thought. Using the proposed attack, even if the victim systematically hides informative SNPs (i.e., SNPs with very low minor allele frequency -MAF-), it is possible to infer the alleles at positions of interest as well as the beacon query results with very high confidence. Our method is based on the fact that alleles at different loci are not necessarily independent. We use the linkage disequilibrium and a high-order Markov chain-based algorithm for the inference. We show that in a simulated beacon with 65 individuals from the CEU population, we can infer membership of individuals with 95% confidence with only 5 queries, even when SNPs with MAF less than 0.05 are hidden. This means, we need less than 0.5% of the number of queries that existing works require, to determine beacon membership under the same conditions. We further show that countermeasures such as hiding certain parts of the genome or setting a query budget for the user would fail to protect the privacy of the participants under our adversary model. 1 2 and AstraZeneca's project of sequencing two million individuals [9] . Even though such million-sized genomic datasets are invaluable resources for research, sharing the data is a big challenge due to re-identification risk. Several studies in the last decade have shown that removal of personal identifiers from genomic data is not enough and that individuals can be re-identified using allele frequency information [6, 12, 8, 15, 3] . Genomic data-sharing beacons (referred to as beacons from now on) are the gateways that let users and data owners exchange information without -in theory-disclosing any personal information. A user who wants to apply for access to the dataset can learn whether individuals with specific alleles of interest are present in the beacon through an online interface. More specifically, the user submits a query, asking whether a genome exists in the beacon with a certain nucleotide at a certain position, and the beacon answers "yes" or "no". Beacons are easy to set up systems that provide very restricted access to the stored data. The Beacon Project is an initiative by the Global Alliance for Genomics and Health (GA4GH) which creates policies to ensure standardized and secure sharing of genomic data. Beacons were considered safe as allele frequencies are not involved in the query result and the binary answers for allele presence seem far from being informative for an attack. However, in 2015, Shringarpure and Bustamante introduced a likelihood-ratio test (LRT) that predicts if an individual is in the beacon or not, by repeatedly querying the beacon for SNPs of the victim (dubbed the SB attack) [13]. The method does not use the allele frequencies and can compensate sequencing errors. They show that they could re-identify an individual in a beacon with 65 European individuals from the 1000 Genomes Project [14] with 250 queries (with 95% confidence). In their scheme, both the queries posed and the answers received from the beacon are assumed to be independent, therefore the hypothesis is tested based on a binomial test. Very recently, the work by Raisaro et al. showed that if the attacker has access to the MAFs of the population, s/he can sort the victim's SNPs and query the SNPs starting from the one with the lowest MAF (dubbed the Optimal attack) [10] . Unlike the SB attack, queries are not random in this case. As low MAF SNPs are more informative, Raisaro et al. show that fewer queries are needed to re-identify an individual. Furthermore, Raisaro et al. proposed countermeasures against re-identification attacks such as adding noise to the beacon results and assigning a budget to beacon members which limits the number of informative queries that can be asked on each member. 1 Linkage disequilibrium (LD) is a measurement for SNP correlations that shows which SNP positions are likely to be inherited together.
The original attack has been improved by REF in terms of number of queries needed to determine the presence of an individual in a beacon.
Re-Identification of Individuals in Genomic Data-Sharing Beacons via Allele Inference
bioRxiv
Biology