Privacy protection model

Differential privacy is a recent privacy definition that provides a strong privacy guarantee. It guarantees that an adversary learns nothing more about an individual from the released data set, regardless of whether her record is present or absent in the original data. Informally, a differentially private output is insensitive to any particular record. Therefore, from an individual's point of view, the output is computed as if from a data set that does not contain her record.

Definition (ε-Differential Privacy) [12] A randomized algorithm Ag is differentially private if for all data sets D and D' whose symmetric difference contains at most one record (i.e., |D Δ D'| ≤ 1), and for all possible anonymized data sets $\widehat{D}$,

A standard mechanism to achieve differential privacy is to add random noise to the true output of a function. The noise is calibrated according to the sensitivity of the function. The sensitivity of a function is the maximum difference of its outputs from two data sets that differ only in one record. This is also known as Laplacian mechanism [12].

Privacy attack model

The likelihood ratio test [13] provides an upper bound on the power of any method for the detection of an individual in a cohort, using the following formula:

where x_j is either 0 (i.e., major allele) or 1 (i.e., minor allele), m is the number of SNPs, p_j is the allele frequency of SNP j in the population and ${\widehat{p}}_j$ is that in a pool.

Anonymization algorithm

The proposed algorithm first divides the genomic data into blocks and then generalizes each block. Thus, the algorithm divides the raw data into several equivalence groups, where all the records within a group have the same block values. Finally, the algorithm publishes the noisy counts of the groups. Next we elaborate each line of the algorithm.

Dividing the raw data (Line 1). Algorithm 1 first divides the raw genomic data into multiple blocks. Each block consists of a number of SNPs. For example, the raw genomic data of Table ​Table11 can be divided into 4 blocks as shown in Table ​Table2,2, where each block consists of two SNPs. These blocks are treated like different attributes and thus enable the proposed algorithm to anonymize high-dimensional genomic data effectively. We denote each block by $A_i^{snp}$ and thus $A^{snp}=\cup A_i^{snp}$.

Note that the sizes of all the blocks do not need to be equal. For example, if there were nine SNPs in Table ​Table11 instead of 8, it would be impossible to have all blocks of size two. In such a case, the last block can be bigger than the other blocks. In principle, each block may have a different size, and the proposed algorithm can handle such a scenario.

We do not use any heuristic to determine the size of each block. Experimental results suggest that six SNPs per block yield good result. However, this number may vary depending on the data set in question. It is an interesting research problem to design a heuristic that can determine the optimal size of each block so as to maximize the data utility for a given data set.

Generating the taxonomy tree (Line 2). A taxonomy tree of a block $A_i^{snp}$ specifies the hierarchy among the values. Figure ​Figure11 presents the taxonomy trees of Blocks 1 − 4 (ignore the dashed curve for now) in Table ​Table2.2. A cut of the taxonomy tree for a block $A_i^{snp}$, denoted by Cut_i, contains exactly one value on each root-to-leaf path (more discussion follows).

Open in a separate window

Figure 1

Taxonomy tree of blocks.

Ideally, the data owner should provide a taxonomy tree for each block as the knowledge of the taxonomy tree is domain specific. However, if no taxonomy tree is provided, Algorithm 1 can generate it by scanning the data set once for each block. For each unique value that appears in the data set, a leaf node is created from the root node Any1. For example, four unique values (i.e., AG CC, AA CC, AG CT, and GG CT) appear in Table ​Table22 for Block 1; therefore, the corresponding taxonomy tree also has four leaves as shown in Figure ​Figure1.1. All the generated taxonomy trees have only two levels (i.e., root and the leaf nodes). However, a data owner can define a multilevel taxonomy tree for each block [14]. Multilevel taxonomy tree provides more flexibility and may preserve more data utility; further investigation is needed to validate the benefit of multilevel taxonomy trees.

Data anonymization (Lines 3-8). Anonymization starts by creating a single root partition by generalizing all values in $\cup A_i^{snp}$ to the topmost value in their taxonomy trees (Line 3). The initial Cuti contains the topmost value for each block $A_i^{snp}$ (Line 4).

The specialization starts from the topmost cut and pushes down the cut iteratively by specializing some value in the current cut. The general idea is to anonymize the raw data by a sequence of specializations, starting from the topmost general state as shown in Figure ​Figure2.2. A specialization, denoted by v → child(v), where child(v) is the set of child values of v, replaces the parent value v with a child value. The specialization process can be viewed as pushing the "cut" of each taxonomy tree downwards. Figure ​Figure11 shows a solution cut indicated by the dashed curve corresponding to the anonymous Table ​Table33.

Open in a separate window

Figure 2

Tree for partitioning records.

At each iteration, Algorithm 1 randomly selects a candidate v Cut_i for specialization (Line 6). Candidates can be selected based on their score values, and different heuristics (e.g., information gain) can be used to determine candidates' scores. In future work, we will investigate how to design a scoring function tailored to a specific data utility requirement.

Then, the algorithm specializes v and updates Cut_i (Line 7). Algorithm 1 specializes v by recursively distributing the records from the parent partition into disjoint child partitions with more specific values based on the taxonomy tree. The algorithm terminates after a given number of specializations.

Example 1 Consider Table ​Table1with1with ε = 1 and h = 2. Initially the algorithm creates one root partition containing all the records that are generalized to Any₁, Any₂, Any₃, Any₄. Cut_i includes {Any₁, Any₂, Any₃, Any₄}. Let the first specialization be Any₂ → {CC GG, CT AG}. The algorithm creates two new partitions under the root, as shown in Figure ​Figure2,2, and splits data records between them. Cut_i is updated to {Any₁, Any₃, Any₄}. Suppose that the next specialization is Any₄ → {AA CC, AG CT }, which creates further specialized partitions, as illustrated in Figure ​Figure22.

Returning the noisy counts (Line 9). Finally, Algorithm 1 computes the noisy count of each leaf partition to construct the anonymous data table $\widehat{D}$ as shown in Table ​Table3.3. The number of leaf partitions is at least 2^h and the exact number depends on the taxonomy tree of the blocks.

Publishing the true counts of each partition violates differential privacy; therefore, a random variable Lap(Δf/ε) is added to the true count of each leaf partition, where Δf = 1.

Privacy analysis

We now analyze the privacy implication of each of the above steps and quantify the information leakage in terms of privacy budget.

Line 1. The algorithm divides the raw data into blocks, where the block size is a given constant irrespective of the given data set. Since the block generation process is data independent, this step does not require any privacy budget. However, if a heuristic were used to determine the block size, then a portion of privacy budget should be allocated to satisfy differential privacy.

Line 2. We assume that the data owner provides the taxonomy trees. In such a case, this step incurs no privacy leakage and no privacy budget is consumed as the taxonomy trees are generated from public knowledge that is independent of any particular data set.

On the other hand, the alternative approach that we outlined, for a scenario when the taxonomy trees are not provided, needs additional treatment to satisfy differential privacy. It is because, for a different data set $\widehat{D}$, a taxonomy tree may have one more or less leaf node. We argue that taxonomy trees represent the domain knowledge, and therefore, should be part of public information.

Lines 3-8. The algorithm selects a candidate for specialization randomly (Line 7) and iteratively creates child partitions based on the given taxonomy trees (Line 8). Both operations are independent of the underlining data set (the selection process is random and the partitioning process is fixed due to the given taxonomy trees), and therefore no privacy budget is required for the h number of iterations.

Line 9. The algorithm adds Laplace noise Lap(1/ε) to the true count of each leaf partition and the requisite privacy budget is ε due to the parallel composition property [15]. The Parallel composition property guarantees that if a sequence of computations are conducted on disjoint data sets, then the privacy cost does not accumulate but depends only on the worst guarantee of all the computations. Since the leaf partitions are disjoint (i.e., a record can fall into exactly one leaf partition), the total privacy cost (i.e., the budget required) for this step is ε.

In conclusion, Line 1, Line 2, Lines 3-8, and Line 9 use 0, 0, 0, and ε privacy budgets, respectively. According to the sequential composition property of differential privacy [15], any sequence of computations that each provides differential privacy in isolation also provides differential privacy in sequence. Therefore, Algorithm 1 satisfies ε-differential privacy.