{'fraction_non_alphanumeric': 0.03269068449470116, 'fraction_numerical': 0.00929808813086992, 'mean_word_length': 4.540791329522678, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Collusion-Resilient Probabilistic Fingerprinting Scheme for Correlated Data

In order to receive personalized services, individuals share their personal data with a wide range of service providers, hoping that their data will remain confidential. Thus, in case of an unauthorized distribution of their personal data by these service providers (or in case of a data breach) data owners want to identify the source of such data leakage. Digital fingerprinting schemes have been developed to embed a hidden and unique fingerprint into shared digital content, especially multimedia, to provide such liability guarantees. However, existing techniques utilize the high redundancy in the content, which is typically not included in personal data. In this work, we propose a probabilistic fingerprinting scheme that efficiently generates the fingerprint by considering a fingerprinting probability (to keep the data utility high) and publicly known inherent correlations between data points. To improve the robustness of the proposed scheme against colluding malicious service providers, we also utilize the Boneh-Shaw fingerprinting codes as a part of the proposed scheme. Furthermore, observing similarities between privacy-preserving data sharing techniques (that add controlled noise to the shared data) and the proposed fingerprinting scheme, we make a first attempt to develop a data sharing scheme that provides both privacy and fingerprint robustness at the same time. We experimentally show that fingerprint robustness and privacy have conflicting objectives and we propose a hybrid approach to control such a trade-off with a design parameter. Using the proposed hybrid approach, we show that individuals can improve their level of privacy by slightly compromising from the fingerprint robustness. We implement and evaluate the performance of the proposed scheme on real genomic data. Our experimental results show the efficiency and robustness of the proposed scheme.


INTRODUCTION
In today's data-driven world, individuals share vast amount of personal information with several service providers (SPs) to receive personalized services. During such data sharings, data owners usually do not want SPs to share their personal data with other third parties. Such issues are typically addressed via a consent (or data usage agreement) between a data owner and an SP to determine how much the SP gains the ownership of the user's data. However, user's data may often end up in the hands of unauthorized third parties since (i) SPs sometimes share (or sell) users' personal information without their authorization or (ii) databases of SPs are sometimes breached (e.g., due to insufficient or non-existing security measures).
When such a leakage occurs, data owners would at least like to know the source of it to keep the corresponding SP(s) liable due to the leakage. If techniques exist to help the data owners identify the source of the data leakages, SPs (knowing potential consequences) will be hesitant to share users' data without their authorization or they will take more serious security measures against data breaches. Thus, it is crucial to develop such techniques that can be used when sharing personal data with untrusted SPs and that are robust against various attacks that may be launched by malicious SPs. In this work, we propose such a technique by focusing on sequential personal information, such as genomic data, location data, or financial data. Similar techniques exist for multimedia to prevent copyrighted content being copied or shared without the authorization of the data owner. Digital watermarking [23] is a technique to prove the ownership of digital content by embedding a mark into it, in which embedded watermarks can be the same for each copy of digital object. In order to detect the source of an illegal distribution, different mark should be used for each copy. Digital fingerprinting [35] is a technique to identify the recipient of a digital object by embedding a unique mark (called fingerprint) into the digital object. The aim of fingerprinting is to identify the guilty agent who is responsible for data leakage. Watermarking and fingerprinting techniques have been developed for different types of digital content, such as audio, video, software, relational databases, graphs, and maps. However, such techniques are not directly applicable for our scenario (sharing personal correlated data) because (i) they (especially for multimedia) utilize the high redundancy in the data, (ii) the embedded marks need to be large, which reduces the utility of shared data, and (iii) they do not consider the correlations between data points.
In this work, we propose a fingerprinting technique for sequential data having correlations between data points.
We consider several different malicious behaviour that can be launched by the malicious SPs against the proposed fingerprinting scheme including: (i) flipping data points, (ii) using a subset of the data points, (iii) utilizing the correlations in the data, and (iv) colluding SPs to identify and/or distort the fingerprint.
The proposed fingerprinting scheme essentially relies on adding controlled noise into particular data points in the original data. We build a correlation model (that captures the statistics in the data) and add the fingerprint to the data that is consistent with the nature of the data. By doing so, we avoid malicious SPs identify and distort the added fingerprint using the auxiliary information about the data model. We also consider colluding SPs (that receive different fingerprinted copies of the same data) who aim to detect and distort the fingerprints. The proposed fingerprinting scheme utilizes Boneh-Shaw codes [5] to improve its collusion resistance and integrates such codes with a novel algorithm to also provide robustness against other types of malicious behavior, such as flipping or utilizing correlations in the data (that are not considered by Boneh-Shaw codes). Furthermore, we propose a detection algorithm that identifies the suspects based on the similarity of their copies with leaked data and selects one of them by checking Boneh-Shaw codes embedded in their copies. Besides providing robustness against the aforementioned attacks, the proposed scheme also keeps the data utility high by controlling the fraction of fingerprinted data points.
In most data sharing scenarios, individuals also want to share their personal information with the SPs under certain privacy guarantees. Several existing techniques rely on adding controlled noise on the shared data to provide privacy guarantees (including large tech companies, such as Google [10] and Apple [28]). Realizing these similar methodologies between the proposed scheme and privacy-preserving data sharing, we also propose a scheme that provides both privacy and liability (i.e., robust fingerprinting) while sharing personal data with the SPs. Here, the main challenge is the conflicting goals between data privacy and robust fingerprinting. To provide higher privacy, the same (or similar) noise pattern should be used at each new sharing of the data (e.g., by maximizing the overlap between noisy data points across different sharings). On the other hand, for robust fingerprinting, shared noise patterns should be unique to identify the source of a potential data leakage (e.g., by minimizing the overlap between noisy data points across different sharings). Thus, we propose a scheme that controls the size of this overlapping region to identify a sweet-spot between privacy and robust fingerprinting.
We implement the proposed fingerprinting scheme for genomic data sharing using a real-life genomic dataset. Via simulations, we show the robustness of the proposed scheme against various types of attacks that can be launched against a fingerprinting scheme. We show that the proposed scheme is efficient and scalable in terms of its running time. We also study the balance between fingerprint robustness and data privacy via simulations on genomic data.
The rest of the paper is organized as follows. We summarize the related work in Section 2. We describe the problem settings in Section 3. We propose the probabilistic fingerprinting scheme in Section 4 and explain how to utilize Boneh-Shaw codes to resist collusion attacks in Section 5. We propose a hybrid approach in Section 6 to provide privacy and liability together. We present our experimental results in Section 7. We discuss more about our scheme based on our evaluation results in Section 8 and conclude the paper in Section 9.

RELATED WORK
Digital watermarking is the act of embedding an owner-specific mark into a digital object (e.g., an image, song, or video) to prove the ownership of the object [9]. Digital watermarks are typically used for copyright and copy protection of multimedia content [8,21]. The techniques to watermark audio [4,14], image [7,32], and video [12,27] have been developed. Watermarking techniques have also been proposed for text documents [2,6,29], graphs [11,24,37], maps [17,31,36], time-series data such as electrocardiograms [15,26], and spatiotemporal (trajectory) datasets [13,20]. In general, watermarking schemes (i) benefit from the high redundancy in the data, (ii) mostly aim to prove ownership of the digital object, and (ii) do not consider robustness against various types of attacks (that are discussed in Section 3.2).
Digital fingerprinting is similar to watermarking in a sense that it also embeds a mark into the object. However, fingerprinting can be seen as a personalized version of watermarking since embedded mark (i.e., fingerprint) is different in each copy of data with the objective to identify the recipient if data is disclosed to a third party without authorization of data owner. Since each copy is different in fingerprinting, malicious recipients can collude and detect fingerprinted points by comparing their copies. Boneh and Shaw proposed a general fingerprinting solution for binary data that is robust against collusion [5]. Their scheme constructs fingerprinting codes in such a way that the attackers cannot detect some of the fingerprints due to inclusion of overlapped fingerprints in each copy. However, fingerprint length needs to be significantly long to guarantee robustness against collusion, which reduces the utility of the data. Furthermore, they do not consider complex attacks against the fingerprinting algorithms, such as using correlations in the data for detecting fingerprinted points. Due to such limitations, their codes cannot be used directly for personal data sharing.
As we explain in Section 5.2.2, we utilize Boneh-Shaw codes to improve the robustness of the proposed scheme against collusion attacks.
Some other fingerprinting schemes have been proposed for multimedia [35], relational databases [16,18,19], and sequential data [3]. Similar to multimedia watermarking schemes, fingerprinting schemes for multimedia also utilize the high redundancy in digital object, which are not applicable to personal data sharing (which typically includes less redundancy). Fingerprinting schemes for relational databases [16,18,19] insert fingerprint by altering the least significant bits of some attributes in selected tuples. Since databases consist of numerous tuples, the redundancy is much higher compared to personal data. Moreover, these techniques do not consider correlations between attributes.
The scheme proposed for sequential data [3] is inefficient due to solving an optimization problem in each step of the algorithm. In addition, the objective of the optimization problem (i.e., minimizing the probability of identifying the whole fingerprint in a collusion attack) is unrealistic, because the attackers do not need to identify the whole fingerprint to perform a successful attack; they can achieve their goal by modifying some of the fingerprinted points. Therefore, in this work we develop an efficient fingerprinting scheme which is robust against various types of attacks. Furthermore, to the best of our knowledge, for the first time we study the fingerprinting robustness and privacy together in a data sharing scheme.

SYSTEM MODEL, THREAT MODEL, AND ROBUSTNESS MEASURES
In this section, we present our system model, threat model, and robustness measures.

System and Data Model
We show our system model in Figure 1. We assume a data owner (Alice) with a sequence of data points X = [x 1 , x 2 , . . . , x l ], where l is the length of the data and each x i can have a value from the set D = {d 1 , d 2 , . . . , d m }.
Alice wants to share her data with multiple service providers (SPs) to receive a service from these SPs related to her data. We represent these SPs with a set S and each SP with an index such that SP i ∈ S. We assume Alice wants to add a unique fingerprint in each sharing to detect the source of data leakage in the case of an unauthorized data sharing by any of these SPs. Hence, for each SP i ∈ S, Alice creates a unique fingerprinted copy X ′ i = [x ′ i,1 , . . . , x ′ i,l ] of original data X by changing the values of some data points. We list the frequently used symbols in Table 1.
Changing the states of more data points for fingerprinting increases the chance of Alice to detect the malicious SP(s) who leaks her data. However, fingerprinting naturally degrades the utility of shared data and one of our goals is to minimize this degradation while providing a robust fingerprinting scheme. We define the utility of a shared copy X ′ , fingerprinted). On one hand, the aim of Alice is to detect the source of data leakage in case her data is shared without her consent by an SP (or collusion of multiple SPs). On the other hand, the aim of the malicious SPs is to avoid being detected while sharing as many data points as possible. A malicious SP i may avoid being detected by Alice by changing the states of some data points in its copy X ′ i or excluding them in its unauthorized sharing. Multiple malicious SPs may also collude to detect fingerprinted data points. Furthermore, background knowledge about the data can be used to detect fingerprinted data points (we discuss more on the threat model in Section 3.2). One such auxiliary information that malicious SPs can use is correlations in the data.
Original data owned by Alice (data owner).
Possible values (states) of a data point.
Fingerprinted copy shared with S P i .
Data leaked by malicious SP(s).

S
The set of all SPs receiving a fingerprinted copy from Alice. C The set of colluding SPs in the collusion attack.
The probability of sharing data point x j as d k in the proposed scheme. n The number of colluding SPs in the collusion attack. p The probability of fingerprinting a data point in the proposed scheme.
The probability of flipping a data point in the flipping attack and removing a data point in the subset attack. p e The estimation of p by the colluding SPs. If p is publicly known, p e = p. We assume that data is correlated and in this work, for clarity of presentation, we consider pairwise correlations between consecutive data points. The proposed mechanism can also be extended to consider more complex correlations, which may result in eliminating more possible values with low correlations. Thus, we let P(x j+1 = d β |x j = d α ) values be publicly available for any j ∈ {1, . . . , l − 1} and d α , d β ∈ D. This model represents the inherent characteristics of different data types, such as location patterns or genomic data. For instance, consecutive data points that are collected with small differences in time are correlated in location patterns. Similarly, in genomic data, point mutations (e.g., single nucleotide polymorphisms) may have pairwise correlations between each other (e.g., linkage disequilibrium [25]).
Therefore, a malicious SP may use such correlations to detect and exclude fingerprinted data points (e.g., the ones that are not compliant with the expected correlation model) in its unauthorized data sharing.

Threat Model
In this section, we present the attacks which may be performed by malicious SPs (attackers). We consider these attacks when developing the proposed scheme and we evaluate the robustness of the proposed scheme against these attacks in Section 7. In all of these attacks, the main goals of the attacker(s) are (i) to avoid being detected by the data owner and (ii) to share as much correct data point as possible (i.e., not to further distort the data). The attacker(s) needs to modify the values of some data points in its copy to distort the fingerprint. These modifications in the data mostly cause utility loss for the attacker(s). Note however that in some cases, such as in the collusion attack, utility of the attackers may improve as a result of the attack. Let Y = [y 1 , . . . , y l ] be the leaked copy of Alice's data X. The utility of the attacker(s)

Subset
Attack. This attack is similar to flipping attack, but here, a malicious SP excludes (removes) some randomly chosen data points before leaking data, instead of flipping them. We denote the probability of excluding a data point as p s . This attack is not as powerful as the flipping attack because flipping data points might create a fingerprint pattern that looks similar to some other SP's fingerprint pattern, and hence Alice may falsely accuse an innocent SP. However, to succeed in the subset attack, the malicious SP needs to exclude almost all of the fingerprinted data points.

Correlation Attack.
As discussed, the correlations between consecutive data points are assumed to be publicly known. A malicious SP can use these correlations to degrade the robustness of the fingerprinting mechanism (we will define the robustness of the mechanism later). Assume the malicious SP i receives X ′ i = {x ′ i,1 , . . . , x ′ i,l } from Alice and let two data points in the received data be is low, then the attacker infers that either x ′ i, j or x ′ i, j+1 is fingerprinted with a high probability. After detecting such a pair, the malicious SP may change their values or exclude them before unauthorized sharing. In other words, the malicious SP combines the correlation attack with flipping or subset attacks.
Since flipping attack can be more powerful (as discussed in Section 3.2.2), we assume the malicious SP combines correlation attack with flipping attack as follows: For two consecutive data points x j and x j+1 , the malicious SP i checks the conditional probability of x j+1 having the value of x ′ i, j+1 given x j having the value of x ′ i, j . If this probability is less than a threshold τ c , the malicious SP changes the value of x ′ i, j+1 to a different value from the set D that provides the highest conditional probability (correlation) between x ′ i, j and x ′ i, j+1 . Otherwise (i.e., if the the conditional probability is greater than or equal to τ c ), the malicious SP flips the value of x ′ i, j+1 with probability p f (as in the flipping attack). By doing so, the malicious SP (i) distorts the fingerprint with a high probability (by distorting the data points that are not compliant with the inherent correlations in the data) and (ii) adds random noise to the data to further reduce the chance of being detected by the data owner. Following a similar strategy, the malicious SP checks all pairs up to x ′ i,l −1 and x ′ i,l . If the malicious SP does not combine correlation attack with flipping attack, Alice can perform a similar correlation attack on X ′ i and obtain a similar result with the malicious SP. Therefore, the randomness in the flipping attack makes it difficult for Alice to detect the malicious SP.

Collusion Attack.
If multiple malicious SPs collude, by comparing their copies, they may detect and distort the fingerprinted data points. The goal of the colluding SPs is to share a single copy of data owner's data without being detected. One well-known collusion attack against fingerprinting schemes, called majority attack in the literature [18], is when colluding SPs compare all their received data points and choose to share the data value that is observed by the majority of the colluding SPs. However, doing such an attack alone cannot be successful for attackers if there is no randomness in the attack. Otherwise, similar to correlation attack, data owner (Alice) can simulate the majority attack of the colluding SPs (and identify the malicious SPs easily). Therefore, collusion attack should also be combined with flipping attack. Furthermore, the colluding SPs can also use correlations to perform a more successful attack. In Section 5, we explain how such an attack (i.e., collusion attack combined with correlation and flipping attacks) can be performed against the proposed fingerprinting scheme in detail.

Robustness Measures
One common requirement of fingerprinting schemes is their robustness against malicious attacks that may destroy or distort the embedded fingerprint. This is important because such attacks may cause the data owner to accuse an innocent SP due to the data leakage, and hence cause false positives in the fingerprint detection algorithm. Therefore, a fingerprinting scheme is considered as robust if it resists malicious attacks and allows the detection of the guilty SP that leaks the data after performing an attack. In this work, we assume that the detection algorithm always returns a guilty SP when Alice observes an unauthorized copy of her data. The proposed detection methods compute a score for each SP having a copy of Alice's data and identify the guilty SP based on these scores. In order to quantify the robustness of the proposed scheme, we use the accuracy (a) of the detection algorithm which is defined as the probability of detecting the guilty SP from the leaked data. In [18], misattribution false hit (f h A ) is defined as a robustness measure (defined as the probability of detecting an incorrect fingerprint from the leaked data). Therefore, our robustness measure a is If collusion attack occurs, the accuracy of the detection algorithm can be evaluated by the probability of correctly identifying one or all colluding SPs. In [35], the possible goals for designing the fingerprinting schemes are defined as "catch one", "catch many", and "catch all". In catch one scenario, the goal is to design the scheme to maximize the probability of catching one of the colluding SPs, while seeking to minimize the probability of falsely accusing an innocent user. In the other scenarios, the probability of falsely accusing the innocent SPs (f h A ) increases. Hence, most collusion resistant fingerprinting schemes, such as Boneh-Shaw codes [5], aim to catch one of the colluding SPs. Since we utilize Boneh-Shaw fingerprinting codes in our proposed scheme, we also aim to catch one of the colluding SPs in case of collusion attack. Thus, we define a as the probability of detecting one guilty SP from the leaked data.

PROBABILISTIC FINGERPRINTING SCHEME FOR CORRELATED DATA
In this section, we propose our probabilistic fingerprinting scheme which considers correlations in data (considering the attack in Section 3.2.3). We also present two techniques for the data owner to detect the source of data leakage. In Section 5, we will improve this scheme to also consider colluding malicious SPs.

Proposed Fingerprinting Algorithm
Assume data owner (Alice) has a sequence of data points X = [x 1 , . . . , x l ] and she wants to share her data with an SP i Alice determines a fingerprinting probability p (for each data point), which means approximately p · l data points will be fingerprinted (i.e., their value will be changed) when sharing l data points with SP i . Lower p values increase the utility of shared data (by changing values of fewer data points), however they also decrease the robustness of the fingerprint (i.e., chance of the data owner to detect the source of data leakage).
Under these settings, a naive algorithm fingerprints each data point with the same probability, without considering correlations in the data. Hence, each data point is shared correctly (x ′ i, j = x j ) with probability 1 − p and incorrectly/fingerprinted (x ′ i, j x j ) with probability p. For each fingerprinted (incorrectly shared) data point, the shared state is selected among (m − 1) states in D with equal probability. However, if Alice applies this naive probabilistic fingerprinting scheme, a malicious SP can detect some of the fingerprinted data points using the correlations and distort the fingerprint via flipping, as discussed in Section 3.2.3.
In order to prevent such an attack, one needs to consider the correlations in the fingerprinting scheme. In our proposed probabilistic fingerprinting scheme, for each data point x j , considering the correlations in the data, we assign a different probability for sharing each different state of this data point in D. Let P x j ,d k be the probability of sharing data The proposed scheme assigns a P x j ,d k value for all j ∈ {1, 2, . . . , l } and k ∈ {1, 2, . . . , m}. By doing so, unlike the naive approach, we consider the correlations in the data, and hence prevent a malicious SP to detect and distort fingerprints. We propose an iterative algorithm that starts from the first data point x 1 and assigns probabilities P x 1 ,d 1 , . . . , P x 1 ,d m . Since we consider correlations between consecutive data points, for the first data point x 1 , similar to the naive approach, Alice shares the correct value with probability 1 − p and each incorrect value with probability p/(m − 1). Based on these probabilities, the algorithm selects a value for x ′ i,1 from the set D. For the subsequent data points, the algorithm computes the fingerprinting probabilities by checking the correlation with the preceding data points.
Let the shared value of x j−1 (i.e., x ′ i, j−1 ) be d α . The algorithm checks the conditional probabilities P(x j = d k |x j−1 = d α ) for all d k ∈ D. If the algorithm decides to share x j as d k , and if P( To eliminate such correlation attack, the proposed algorithm uses a threshold τ and sets P This means that the algorithm never selects d k as . After assigning all probabilities, the algorithm chooses one of the values from D based on the assigned probabilities and sets the value of x ′ i, j accordingly. Since the proposed algorithm considers correlations between consecutive data points, it may result in changing the value of high number of consecutive data points or sharing the correct value for high number of consecutive data points to prevent malicious SPs from detecting and distorting the fingerprint. As a result of this, total number of fingerprinted points in the original data may significantly deviate from the expected number (p · l). For instance, if p is selected as 0.2, we expect to fingerprint approximately 20% of total data points. However, considering correlations may cause fingerprinting significantly more (or fewer) data points than anticipated. To prevent this, we dynamically decrease (or increase) the fingerprinting probability p depending on number of currently fingerprinted data points as follows.
To keep the average number of fingerprinted data points as p · l, the proposed algorithm divides the data points into blocks consisting of ⌈1/p⌉ data points. We expect (on the average) one fingerprinted data point in each block. Therefore, the algorithm keeps a count of the number of fingerprinted data points at the end of each block. If the ratio of fingerprinted data points is less than p, the algorithm sets the fingerprinting probability for the next block as p · (1 + θ ). Here, θ is a design parameter in the range [0, 1) and we evaluate the selection of θ in Section 7. If the ratio of fingerprinted data points is greater than p, the algorithm sets the fingerprinting probability for the next block as p · (1 − θ ).
The steps of the proposed scheme are also shown in Algorithm 4.1. For each SP, Alice executes the same algorithm with a different seed value and stores the fingerprint pattern of each SP to use it in the detection in case her data is shared without her consent. If the data size and number of SPs are large, Alice can also just store the seed value for each SP. Figure 2 shows a toy example to illustrate the execution of the proposed algorithm (Algorithm 4.1). Each step shows one execution of the outer loop of Algorithm 4.1 for deciding the value of one data point. In the first step, probabilities are assigned just by using p. In the next steps, correlation values are also used to determine the probabilities that are used to choose the shared values (x ′ i, j ). When the correlation is less than τ = 0.05, the algorithm assigns 0 for the probability of selecting the corresponding value. At the end of each block (a block includes 5 data points in the example), the algorithm checks the total number of fingerprinted values. Since the expected number of fingerprinted points in a block is 1 and the algorithm fingerprinted 2 data points, the fingerprinting probability is adjusted as p · (1 − θ ) = 0.1 for the second block.

Detecting the Source of Data Leakage
Let the leaked copy of Alice's data be Y = [y 1 , . . . , y l ]. The goal of Alice is to detect the SP that leaks her data. Here, we propose two methods that can be used by Alice to detect the source of the data leakage. Both methods compute a score (probability or similarity) for each SP (with whom Alice previously shared her data) to be guilty for leaking Y.
Alice chooses the SP that has the highest score as the guilty SP. Note that, the size of the leaked data may not be equal ALGORITHM 4.1: Probabilistic fingerprinting scheme without considering the collusion attack.
input : Original data X = [x 1 , x 2 , . . . , x l ], fingerprinting probability p, probability adjustment parameter θ , block size ⌈1/p ⌉, correlation threshold τ , pairwise correlations between data points. output : Fingerprinted copy distribute the remaining probability (1 -(sum of assigned probabilities)) by assigning P to the size of the Alice's data (i.e., l) if subset attack is performed. In that case, we represent excluded data points with d 0 (that is not in set D).

Probabilistic Detection.
In [22], considering the data leakage problem, the authors compute the probability of being guilty for each agent (SP) with some independence assumptions (to efficiently compute the probabilities). We adapt their detection method to our problem setting as follows: For each leaked data point y j , Alice identifies each SP i that received the corresponding data point as y j (i.e., x ′ i, j = y j ). Thus, for each data point y j , Alice constructs a set V j consisting of such SPs (that received the leaked state of the data). Alice assumes that each SP in V j can be guilty for leaking y j with a probability 1/|V j |. For instance, if the value of y j is shared with 4 SPs, each of these SPs is considered as guilty for sharing y j with probability 0.25. Eventually, an SP i is considered as guilty with probability . At the end, Alice identifies the guilty SP as the one with highest probability of being guilty.

Similarity-Based Detection.
Another efficient way of detecting the guilty SP is computing the similarity of fingerprinted data shared with each SP with the leaked data. For an SP i , Alice compares the leaked data Y with the copy X ′ i and counts the matching data points in the fingerprint pattern. In other words, Alice checks the size of the following set: Alice also counts the fingerprinted data points Step 1 Step 3 , Step 4 , Step Similarity-based detection is easy to implement and it efficiently detects the guilty SP if there is no collusion between the SPs or the number of colluding SPs is small. However, when the number of colluding SPs increases, the similarity scores of SPs become very close to each other and the detection performance of similarity-based detection decreases.
Probabilistic detection differs from similarity-based detection by considering the number of SPs having the leaked data point (i.e., |V j |). In similarity-based detection, the effect of each data point to the similarity score is same. However, in probabilistic detection, the probability of being guilty is computed by multiplying (1 − 1 |V j | ) values, and hence the effect of each data point to the probability of being guilty is different. In Section 7, we compare the performance of these two detection techniques in terms of their accuracy to identify the guilty SP.

CONSIDERING COLLUDING SERVICE PROVIDERS
As discussed in Section 3.2.4, the colluding SPs may distort the fingerprint via the majority attack. However, lack of randomness in this attack may result in detection of colluding SPs by Alice. Here, we first show a strong attack against the proposed fingerprinting scheme (also against the existing fingerprinting schemes in general) by integrating colluding SPs, correlations in the data (in Section 3.2.3), and the flipping attack (in Section 3.2.1). Then, we propose utilizing Boneh-Shaw codes [5] to improve robustness against such a strong attack that also involves colluding SPs.

Probabilistic Majority Attack
As discussed, the goal of the colluding SPs is to share (leak) a copy of the data without being detected by the data owner (Alice). In a standard collusion attack, the colluding SPs compare their received values for each data point and select the most observed value to share. We propose an advanced collusion attack called "probabilistic majority attack" (to distinguish it from the standard majority attack), in which the colluding SPs decide the value of each leaked data point by considering (i) all observed values for that data point, (ii) correlation of that data point with the others, and (iii) the probability of adding a fingerprint to a data point (p). If the colluding SPs do not know the fingerprinting probability p, we assume they use an estimated probability p e in their attack (p e = p if p is publicly known).
Let the set of colluding SPs be C and |C| = n. The goal of the colluding SPs is to create a copy Y = [y 1 , y 2 , . . . , y l ] to share and avoid being detected by Alice. In this attack, the colluding SPs first decide the value of each data point y j by computing a probability P y j ,d k for each possible state d k ∈ D of y j . To compute P y j ,d k , colluding SPs first check their received values for data point j. Let c j,d k be the number of observations of d k for data point j by n colluding SPs (in C).
In the standard majority attack, the colluding SPs choose d k with the maximum c j,d k value as the value of y j (assuming it is the original value of the data point) to avoid detection by Alice. However, it is possible (with lower probability) that other values with lower c j,d k may also be the original value of y j . For example, assume there are three colluding SPs and let D = {d 1 , d 2 , d 3 }. For a data point j, observing two d 1 s (c j,d 1 = 2) and one d 2 (c j,d 2 = 1) is not enough to conclude that d 1 is the original value (x j ) of data point j. It is also possible (with probability (p/2) 3 ) that the original value is d 3 and all three colluding SPs received fingerprinted (noisy) values from Alice.
Thus, in the probabilistic majority attack, the attackers compute such probabilities for each d k ∈ D using their estimated fingerprinting probability p e and also using publicly known pairwise correlations between the data points.
As discussed in Section 3.2.3, correlations can be used to detect and distort fingerprinted data points by the attackers.
Therefore, the attackers tend to select each leaked value that have high correlation with the previous shared (leaked) values. In order to integrate the correlations with the collusion attack, the conditional probabilities (due to correlations) are used as weights to determine the sharing probabilities of colluding SPs (P y j ,d k ). The colluding SPs first compute the weighted probability values (referred as t j,d k ) and then compute P y j ,d k by normalizing the weighted probability values.
The weighted probability for d k value of a data point j is computed as follows: Here, (1 − p e ) c j,d k · ( p e m−1 ) n−c j,d k is the probability of d k to be the original value of data point j by assuming each data point is fingerprinted with probability p e . The conditional probability P(x j = d k |x j−1 = y j−1 ) is used as a weight. Then, P y j ,d k is computed by normalizing t j,d k values as The colluding SPs decide on the value of each shared point y j proportional to these probabilities. Therefore, the malicious SPs do not necessarily select the value observed by the majority. By doing so, we allow the malicious SPs to further distort the fingerprint compared to the standard majority attack.
Furthermore, existing techniques to prevent collusion attacks (e.g., Boneh-Shaw codes) assign common fingerprints to multiple SPs, which allows data owner to detect colluding SPs with a high chance. However, to avoid such detection, the attackers may flip some random data points before they leak the data. Thus, in the probabilistic majority attack, we also let colluding SPs flip each y j with probability p f (as discussed in Section 3.2.1).

Integrating Boneh-Shaw Codes
In order to provide robustness against collusion attacks, Boneh and Shaw proposed fingerprinting codes for detecting one of the colluding SPs [5]. The effectiveness of their codes depend on the "marking assumption", which states that colluding SPs cannot detect the fingerprint if all of them have the same fingerprint. Hence, when the colluding SPs have the same value for the same data point j, it is assumed that they choose this value as y j as the leaked data point.
However, Boneh-Shaw codes do not consider correlation and flipping attacks, and hence their detection method is not successful when colluding SPs also utilize the correlations in the data and use the flipping attack. Although Boneh-Shaw codes are defined for binary data, we apply these codes to non-binary data. We briefly describe the Boneh-Shaw codes in Section 5.2.1 and show how to utilize these codes in the proposed scheme in Section 5.2.2.

Boneh-Shaw Codes.
Boneh-Shaw codes [5] are designed to detect one of the colluding SPs with probability at least (1 − ω), where at most c SPs can collude, under the marking assumption (in the original paper [5], the error probability is represented as ϵ, here we use ω to prevent confusion with privacy parameter ϵ in differential privacy).
Note that c is the maximum number of colluding SPs, for which the detection technique can provide robustness (i.e., detect one of the colluding SPs) with high probability (ω-error) and n represents the actual number of colluding SPs in the collusion attack. Boneh-Shaw codes are defined as binary codes, in which each codeword consists of zeros and ones. In order to fingerprint data, some data points are selected from the original data and XOR'ed with the permuted codeword in order to prevent colluding SPs from detecting and distorting the fingerprint (the number of data points must be equal to the length of the codeword). The same permutation must be used for each SP and the permutation must be hidden from SPs. The data points that are XOR'ed with ones in the codeword becomes fingerprinted. Therefore, the ones in the binary code represent fingerprints.
In Boneh-Shaw (c,r )-codes, the first codeword consists of (c − 1) · r ones, ith codeword consists of (i − 1) · r zeros and (c − i) · r ones, and the last (cth) codeword consists of (c − 1) · r zeros. For instance, the four codewords of (4, on the marking assumption, they create [RRRRRR111] (as the leaked data), where R is a randomly selected bit. To detect the source of the leakage (i.e., the guilty SP), the data owner checks each r -bit block, observes that the third block consists of all ones and the second block contains a zero with high probability, and concludes that the recipient of the third codeword is involved in the collusion. However, it is also possible that the colluding SPs create [010111111], which leads the data owner to accuse the owner of the second codeword. Thus, increasing r decreases the error in detection (ω), but it also increases the length of the fingerprint (and hence decreases the utility of the shared data).

Using Boneh-Shaw Codes in the Proposed Scheme.
The marking assumption of [5] does not consider the flipping attack and correlation attack which are included in the probabilistic majority attack. If the colluding SPs flip some of the bits randomly or based on correlations, the data owner may accuse an SP who is not involved in the collusion. Therefore, it is not possible to directly use Boneh-Shaw codes and their detection algorithm in our scenario. Instead, we utilize Boneh-Shaw codes to assign shared (i.e., overlapping) fingerprints between different SPs.
In Algorithm 4.1, Alice creates fingerprinted copy of each SP independently. Hence, the fingerprints of two SPs may be the same for some random data points. Here, we explicitly assign overlapping fingerprints using Boneh-Shaw codes to improve robustness against collusion attacks. In order to adopt binary codes into our scheme, we consider ones as fingerprinted data points and zeros as the original data points. Therefore, when a data point is fingerprinted using Boneh-Shaw codes, the same value is also used as a fingerprint in the copies for other SPs if their codewords also include one for the same data point.
We integrate the Boneh-Shaw codes into our scheme as follows: Alice creates the first fingerprinted copy of her data X ′ 1 (to share with SP 1 ) as described in Algorithm 4.1. Approximately p ·l data points are fingerprinted in X ′ 1 . Let f be the number of fingerprinted data points for SP 1 . We want to use some portion of these f data points as Boneh-Shaw codes.
Then, Alice decides the value of c and r such that (c − 1) · r ≤ f to apply Boneh-Shaw codes for the next sharings. As mentioned, c and r are design parameters of Boneh-Shaw codes determining the length of codes and error in detection (ω). We represent (c − 1) · r as f 1 , which is the length of Boneh-Shaw codeword. Here, c is the number of Boneh-Shaw codewords that Alice can create and r is the block size, as explained in Section 5.2.1. If Alice wants to share her data with more than c SPs, she assigns the same Boneh-Shaw codewords in a similar order. SP c+1 receives the same codeword with SP 1 , SP c+2 receives the same codeword with SP 2 , and so on. In this way, although same Boneh-Shaw codewords are assigned to some SPs, since other parts of their fingerprints will be different, the proposed detection algorithm can still identify the guilty SP using the entire fingerprint. If f 1 = f , Alice uses all fingerprint of SP 1 for Boneh-Shaw codes in later sharings of her data (with other SPs). This provides better robustness against collusion attacks, since the number of overlapping fingerprints is high. However, in this case, the robustness for the attacks performed by single SP (e.g., flipping or correlation attack) will become weak because the number of unique fingerprints is low. Therefore, we set f 1 approximately equal to f /2 to detect the guilty SP even the attack is performed by single SP or multiple SPs.
Alice randomly selects f 1 of f fingerprinted points in X ′ 1 . These f 1 fingerprinted data points are considered as the first codeword in Boneh-Shaw codes. For her next sharing with the second SP (SP 2 ), Alice randomly selects f 2 = f 1 − r of f 1 points to assign the same fingerprints to SP 2 (i.e., x ′ 2, j = x ′ 1, j for these f 2 data points). Furthermore, Alice, assigns the original value for the remaining r points (i.e., x ′ 2, j = x j for these r data points). In other words, the Boneh-Shaw codeword of SP 2 consists of r zeros and f 1 − r ones.
In order to assign approximately p · l fingerprinted points to SP 2 , the fingerprinting probability of SP 2 is selected as , probability adjustment parameter θ , block size ⌈1/p ⌉, correlation threshold τ , pairwise correlations between data points. output : Fingerprinted copy 16 distribute the remaining probability (1 -(sum of assigned probabilities)) by assigning P x j ,d k directly proportional to the value of P (

Detection Algorithm
Here, we propose a detection algorithm for the proposed collusion-resilient fingerprinting scheme. In practice, when Alice realizes that a copy Y of her data is leaked without her consent, she cannot know whether Y is leaked by single SP (by performing flipping or correlation attack) or multiple SPs (by performing collusion attack). Therefore, Alice cannot use the detection techniques in Section 4.2 or the detection technique of Boneh-Shaw codes directly. We propose a detection algorithm that utilizes both techniques. As we show in the experimental evaluations, similarity-based x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 1 2 0 2 1 0 2 2 1 1 1 0  detection in Section 4.2 performs slightly better than probabilistic detection. Hence, here, we describe the detection algorithm using similarity-based detection. It can also be implemented using probabilistic detection technique similarly.
First, Alice needs to determine whether her data is leaked by single SP or multiple SPs. In order to do so, she initially computes a similarity score (sim i ) for each SP i (that received her data) as explained in Section 4.2.2. Each score is a number in the range [0, 1]. If there is a collusion of two SPs and the colluding SPs observe different values for a data point, they select either of these values with equal probabilities. Thus, we expect that they damage approximately half of the fingerprinted data points (this will be more if the collusion includes more than 2 SPs). Hence, we assume that there is an attack by single SP if the similarity score of an SP is greater than 0.5. In such a case, Alice identifies the SP with the highest similarity score as guilty. Otherwise, there is a collusion attack with high probability, and hence Alice identifies the suspects according to their similarity scores and returns one of them utilizing the detection technique of Boneh-Shaw codes.
Let the index of SP with maximum similarity score be max. Alice generates a suspect list by including ⌊1/sim max ⌋ SPs having highest similarity scores. Hence, if sim max is greater than 0.5, there will be just one SP in the suspect list and the algorithm will return SP max as guilty. In such case, Alice concludes that there is no collusion attack with high probability. If sim max is less than or equal to 0.5, there will be more than one suspects, which means that a collusion attack is performed with high probability. In this case, the algorithm returns one of the suspects using the detection method of Boneh-Shaw codes [5] as follows: In Boneh-Shaw codes, it is expected that the colluding SPs create a copy Therefore, the detection algorithm may fail against such an attack. To avoid this, we defineB 1 as a block having majority of points as one andB R as a block having majority of points as zero. Then, the algorithm checks all suspects in the suspect list starting from SP max (having the highest similarity score). If (max)th block isB 1 and (max − 1)th block is there is no such an SP, the algorithm returns SP max as guilty.
The steps of the proposed detection algorithm are also shown with an example in Figure 4. After checking the similarity of leaked data with the fingerprinted data points of each SP, the algorithm adds ⌊1/sim max ⌋ = 2 SPs into the suspect list. When the algorithm checks the 1st and the 2nd blocks of leaked data for SP 2 , it does not return SP 2 as guilty since both blocks areB R . Then, it checks the 3rd and the 4th blocks of leaked data for SP 4 and returns SP 4 as guilty since the 4th block isB 1 and the 3rd block isB R .

USING FINGERPRINTING FOR PRIVACY-PRESERVING DATA SHARING
Here, we explore how the proposed fingerprinting technique can also provide privacy-preserving data sharing guarantees for the data owner. We develop a mechanism in which the added fingerprint (to provide liability) can also used to provide privacy. When sharing data with untrusted parties, local differential privacy (LDP) is a commonly used concept for providing (statistical) privacy guarantees [10,33]. LDP-based mechanisms typically add controlled noise to data points to guarantee that an untrusted data collector cannot determine the original value of a data point from the reported (perturbed) value. Thus, one trivial idea is to use the noise pattern added by the LDP-based mechanism as the fingerprint. However, one major challenge about this idea is the conflicting objectives of fingerprinting and privacy mechanism.
To show these conflicting objectives via an example, assume that a data owner shares her data with multiple SPs using an LDP-based mechanism by adding noise to different data points based on the LDP parameter (ϵ) at each sharing.
In that case, if two or more SPs collude, they can recover (infer the actual values of) most of the noisy data points by just aggregating their received data and selecting the data values that are observed by the majority of them (i.e., similar to performing a standard majority attack). Thus, such a sharing strategy is not preferred for the privacy objective. To overcome this problem, the data owner can just choose to add noise to her data once and share the same noisy data with all the SPs. On the other hand, a fingerprinting mechanism requires the data owner to share different fingerprint patterns with the SPs to uniquely identify the source of an unauthorized sharing. This implies that the robustness of the fingerprinting scheme and the privacy of the shared data are inversely proportional.
In order to consider both privacy and liability at the same time, we propose a hybrid approach as follows: When Alice (data owner) shares her data with the first SP using the proposed algorithm, she selects a parameter λ in the range ([0, 1]) to determine her privacy level in the fingerprinting scheme. She randomly selects λ · f of f fingerprinted points as the overlapping fingerprints. These fingerprinted points are shared the same with all the SPs. Thus, for each new data sharing, Alice first inserts λ · f overlapping fingerprints and then applies the proposed fingerprinting algorithm for the remaining fingerprints. While higher λ values provide higher privacy, lower λ values provide better fingerprint robustness. In Section 7.5, we show this trade-off between fingerprint robustness and privacy for different values of λ.

EVALUATION
To evaluate its robustness and utility, we implemented the proposed fingerprinting algorithm (in Section 5.2) and the detection algorithm (in Section 5.3). We here present our experimental evaluations.

Data Model and Settings
We evaluated the proposed scheme on a genomic data sharing scenario. Due to the fast decrease in the cost of sequencing, nowadays, individuals can obtain their genome sequences easily. This trend has also led individuals to share their genomic data with medical institutions and direct-to-consumer service providers for various genetic tests or research purposes. Since genomic data contains sensitive personal information, such as the risk of developing particular diseases, sharing genomic data without the authorization of the data owner causes privacy violations. Therefore, fingerprinting genomic data can be a solution or disincentive to prevent its unauthorized sharing. Furthermore, genomic data contains inherent pairwise correlations between point mutations (single nucleotide polymorphisms -SNPs), which makes genomic data an ideal usecase to evaluate the proposed scheme. SNP is the variation of a single nucleotide (from the set {A,T , C, G}) in the population. For each SNP position, only two different nucleotides can be observed: (i) major allele, which is observed in the majority of the population and (ii) minor allele, which is observed rarely. Moreover, each SNP consists of two nucleotides, one is inherited from the mother and the other from the father. Thus, each SNP is represented by the number of its minor alleles, and D = {0, 1, 2} for genomic data.
We used a dataset that consists of 7690 SNPs belonging to 99 people from Central European ethnicity [1]. Using this dataset, we computed the pairwise correlations between SNPs to build our correlation model. Unless stated otherwise, we set the data size l = 1,000, fingerprinting probability p = 0.1, and the correlation threshold of the algorithm τ = 0.05.
The threshold τ is used in the algorithm to prevent adding fingerprints causing low correlation. Note that the attacker has its own correlation threshold τ c in its correlation attack. We evaluate the effect of τ c on utility and robustness in Section 7.3. We choose the data size as 1,000 to show the robustness of the proposed scheme for a relatively small data.
As we show via experiments later, robustness increases with the increasing data size because as data size increases, we obtain more fingerprinted data points for the same fingerprinting probability p. As expected, utility of the data owner (as introduced in Section 3.1) decreases linearly with increasing fingerprinting probability and we observed that the average utility is 0.8 when p is 0.1.
We expect to change the value of approximately p · l = 100 data points as fingerprint for each SP, and (as discussed in Section 5.2.2) we used approximately half of the fingerprinted data points for Boneh-Shaw codes. We set the number of Boneh-Shaw codes (c) as 10 and the block size of Boneh-Shaw codes (r ) as 5. Hence, (c − 1) · r = 45 fingerprinted data points of first SP were used for Boneh-Shaw codes. Another design parameter in the algorithm is θ , which is used to dynamically adjust fingerprinting probability p to keep the number of fingerprinted data points close to p · l. θ can have any value in the range [0, 1). Although the selection of θ does not have a significant effect on the average number of fingerprinted data points in each shared copy, it has a significant effect on the standard deviation. As shown in Table 2, increasing θ decreases the standard deviation and the number of fingerprinted data points for each SP is close to each other for higher θ values. Therefore, θ values close to 1 provide almost p · l = 100 fingerprinted data points for each SP. However, for θ values close to 1, the fingerprinting probability becomes close to 0 for some blocks within the algorithm where p · (1 − θ ) is used as fingerprinting probability. This may cause an attacker to understand the values of the data points in these blocks. For instance, if the algorithm adds two fingerprints in the first block (including 1/p = 10 data points), the fingerprinting probability reduces to p · (1 − θ ) (close to 0 for higher values of θ ) in the second block. Therefore, an attacker may understand that all data values in the second block are the original values with very high probability by detecting two fingerprints in the first block (e.g., via a correlation or collusion attack). Hence, we set θ = 0.5 in our experiments, which provides a reasonable standard deviation, as shown in Table 2. We repeated all experiments 10 times for each individual in the dataset (totally 99 individuals), and hence all results are given as the average of 990 executions. Table 2. The effect of θ on the standard deviation of the number of fingerprinted data points in each fingerprinted copy.

Flipping and Subset Attacks
In this experiment, we compared the flipping and subset attacks in terms of their effect on the fingerprint robustness.
Also, to compare the similarity-based and probabilistic detection techniques (which are the basic building blocks of the proposed detection algorithm in Section 5.3), we implemented them for this experiment. We set the total number of SPs (that received the data owner's fingerprinted data) to 1,000. Figure 5 shows the accuracy (a) of the similarity-based detection technique and probabilistic detection technique for different values of p f (probability of flipping a data point in flipping attack) and p s (probability of removing a data point in subset attack). From these results, we can conclude that (i) similarity-based detection provides slightly better accuracy than the probabilistic detection, (ii) flipping attack is more powerful than subset attack, and (iii) the attacker needs to flip at least half of the data points to avoid being detected, which decreases the utility of the attacker U Y (defined in Section 3.2) to negative values. For the rest of the experiments, we use the detection algorithm described in Section 5.3, which is based on the similarity-based detection technique (that is shown to perform better than probabilistic detection).
To observe the effect of the total number of SPs on robustness, we computed a by changing the number of SPs that receives a fingerprinted copy from Alice and we show our results in Table 3. We observed similar results with Figure 5 even the data is shared with 10,000 SPs. If data is shared with 10,000 SPs and any of these SPs leaks its copy by flipping up to 44% of the data points, similarity-based technique detects the guilty SP with 99% accuracy. As we also show in Figure 5, a malicious SP obtains almost 0 utility by flipping 44% of the data points. We computed the utility of the attacker (U Y ) as described in Section 3.2 by assigning equal utility for each data point. Hence, an attacker needs to share data with negative utility after subset or flipping attack to avoid being detected.

Correlation Attack
We implemented the correlation attack described in Section 3.2.3 to evaluate the robustness of the proposed scheme. We set the total number of SPs (that received the data owner's fingerprinted data) to 1,000. As before, we set the correlation threshold of the algorithm (decided by data owner) as τ = 0.05. Therefore, the fingerprinted copies did not include consecutive pairs of data points whose correlation is less than 0.05. Note however that the correlation threshold of the attack τ c is determined by the attacker. We also implemented the naive fingerprinting scheme described in Section 4, in which each data point is fingerprinted with probability p. As described in Section 3.2.3, in correlation attack, data points whose correlation with the previous data point is less than the correlation attack threshold τ c is flipped and the remaining data points are flipped with probability p f . Figure 6 shows the comparison of the proposed scheme with the naive approach for different values of τ c when p f = 0.2. The proposed scheme provides 100% detection accuracy up to τ c = 0.2 and accuracy decreases to 98% when τ c = 0.25. However, as also shown in Figure 6, the utility of the attacker (U Y ) reduces to 0.263 when τ c = 0.25. The utility of the attacker is almost constant for τ c < 0.05, because the proposed algorithm guarantees that there is no pairs of data points whose correlation is less than correlation threshold of the algorithm (τ = 0.05). We also observed that the naive approach is not robust against correlation attacks and the attacker can easily prevent detection by utilizing the correlations in the data. This clearly shows the importance of considering correlations in the data within the fingerprinting algorithm.
Furthermore, we observed the robustness against correlation attack for different values of fingerprinting probability p. As shown in Table 4, the robustness increases when the p increases because the number of fingerprinted data points is directly proportional to p. We also obtained similar results (as in Table 3) for the effect of the total number of SPs on robustness.

Collusion Attack
As mentioned in Section 3.2.4, in a standard collusion attack, colluding SPs select (and share) the most commonly observed value for each data point. In this attack, although the utility of the data leaked by the colluding SPs (U Y ) is high, detection techniques can detect the colluding SPs with high probability. Hence, we defined a probabilistic majority attack in Section 5.1 that also includes correlation and flipping attacks. With this attack, the colluding SPs decrease the accuracy of the detection algorithm by reducing the utility of data. In this section, we first compare the utility and robustness under these two attacks. We set c = 10 and r = 5 as the Boneh-Shaw parameters. Hence, we can create 10 different Boneh-Shaw codewords with block size of 5. Note that c is the number of codewords and Alice can share her data more than c SPs in the proposed scheme by repeating codewords as we discussed before. We set the total number of SPs (that received data owner's data) to 10, τ c = 0.1, and p f = 0.1. We quantified both utility and fingerprint robustness for different values of number of colluding SPs (n). As shown in Figure 7, using probabilistic majority attack decreases the colluding SPs' probability of being detected by reducing the data utility. Since the probabilistic majority attack is more powerful than the standard one for the colluding SPs, we perform the probabilistic majority attack for the rest of the experiments.
As mentioned, Boneh-Shaw codes are not designed to be robust against majority attacks. They assume the colluding SPs decide the value of a data point randomly if they observe more than one value in their copies. Hence, Boneh-Shaw codes do not provide guarantees against the proposed probabilistic majority attack (including flipping). Furthermore, in order to provide the robustness guarantees of Boneh-Shaw codes, the number of fingerprinted points needs to be high. For instance, to create Boneh-Shaw codes for c = 10 with 90% robustness guarantee, the block size needs to be greater than 1,000 and we need more than 10,000 fingerprinted data points. Fingerprinting such a high number of data points also decreases the utility of the data owner (U i ) significantly. Therefore, direct use of Boneh-Shaw codes do not provide guarantees, especially for small data sizes (we only use approximately p · l = 100 data points for fingerprinting in our experiments). To show these shortcomings, we implemented Boneh-Shaw codes as a standalone fingerprinting scheme and observed its robustness against the probabilistic majority attack using the same parameters with the previous experiment ( Figure 7). We observed 55% detection accuracy when the number of colluding SPs was 2 (for the same scenario, the accuracy of the proposed scheme is more than 99%, as shown in Figure 7). Therefore, we conclude that using Boneh-Shaw codes as a standalone fingerprinting scheme does not provide robustness against probabilistic majority attack (which includes correlation and flipping attacks). While our proposed scheme utilizes the Boneh-Shaw codes to increase its robustness against collusion attacks, Algorithm 5.1 generates unique fingerprints to provide robustness against correlation and flipping attacks.
We also evaluated the robustness of the proposed scheme by increasing the number of SPs receiving fingerprinted copies Alice's (data owner's) data. Due to the size of the data, we selected c = 10 and r = 5 in our experiments. We can create 10 different Boneh-Shaw codewords with these parameters. In such a scenario, if Alice wants to share her data with more than 10 SPs, she assigns the same 10 codewords to other SPs. Therefore, Boneh-Shaw codewords of SPs whose index values are equivalent in modulo c = 10 are same where their remaining unique fingerprints are generated by the Algorithm 5.1. For instance, all SP 1 , SP 11 , and SP 21 receive the same Boneh-Shaw fingerprints in our proposed scheme. We show the robustness of the proposed scheme for different values of number of SPs in Table 5. We observed that the detection accuracy of Alice reduces when she shares her data with more SPs. For instance, increasing the number of SPs from 50 to 100 decreased the accuracy from 0.824 to 0.759 in our experiments when the number of colluding SPs (n) was selected as 3. Note that flipping probability (p f ) was selected as 0.1 in these experiments.
Next, we evaluated the effect of flipping probability (p f ) on fingerprint robustness during a collusion attack. Our results are shown in Figure 8. Increasing p f reduces the robustness and the utility considerably. When there is no flipping (p f = 0) in the probabilistic majority attack, Alice detects one of 3 colluding SPs among 100 SPs (that she shared Table 5. Fingerprint robustness (a) of the proposed scheme for different values of number of SPs (that received data owner's data) (| S |) and n (the number of colluding SPs). Another important parameter for the fingerprinting scheme is data size. In our experiments we used a data with 1,000 SNPs (l = 1, 000). Therefore, we just changed the state of approximately 100 data points as a fingerprint when fingerprinting probability p was selected as 0.1. By keeping the same fingerprinting probability, increasing data size allows to change more data points as fingerprint. With more fingerprinted data points, the data owner can detect the colluding SPs with higher accuracy. To show the effect of data size (i.e., l) on robustness, we conducted experiments by increasing data size (we kept c = 10 and increased r proportional to data size). As shown in Table 6, Alice detects one of 3 colluding SPs among 100 SPs with 99.7% accuracy when l = 5, 000 and p f = 0.1. Thus, we observed that the robustness of the proposed scheme significantly improves with increasing data size.

Privacy-Preserving Fingerprinting
As we explained in Section 6, both the proposed scheme and LDP-based mechanisms change the values of some points in data before sharing. However, while the goal of fingerprinting schemes is to provide robustness, LDP-based mechanisms aim to guarantee privacy of the individuals. To show the trade-off between fingerprint robustness and privacy, we first implemented the randomized response (RR) mechanism [34] which satisfies ϵ-LDP when the state of each data point is correctly shared with probability e ϵ /(e ϵ + 2) for genomic data with three possible states. Also, each of the incorrect two values can be shared with a probability of 1/(e ϵ + 2). To compare LDP with the proposed scheme, we set e ϵ /(e ϵ + 2) = 0.9, for which RR satisfies LDP with ϵ = 2.89. As the privacy metric, we used the average estimation error, which is a commonly used to quantify genomic privacy [30]. This metric quantifies the average distance of the copy created by colluding SPs (Y) from the original data (X) as E = ( l j=1 ||x j − y j ||)/l. We set the number of SPs (that received the data) to 10 and performed the probabilistic majority attack described in Section 5.1 with 3 colluding malicious SPs by setting both of the flipping probability (p f ) and the correlation threshold of the colluding SPs (τ c ) to 0.1. Although RR mechanism is similar to naive probabilistic scheme described in Section 4, all SPs receive the same copy in RR to guarantee LDP (as discussed in Section 6). Since fingerprint robustness is defined as detecting one colluding SP (in Section 3.3), and all SPs have the same copy, we observed 0.3 detection accuracy (a) for the RR mechanism, which is equivalent to randomly accusing any SP that received the data. We also observed E as 0.279 when the probabilistic majority attack was performed for the RR mechanism.
Next, we also implemented the hybrid scheme described in Section 6. In this scheme, the parameter λ determines the amount of overlapping fingerprints which are included in the copy of each SP. Hence, the proposed fingerprinting scheme (in Section 5.2.2) is equivalent to the hybrid approach when λ = 0. Figure 9 shows both fingerprint robustness (a) and privacy (E) provided by the hybrid scheme for different values of λ. When λ is selected as 1 we observed similar robustness compared to the RR mechanism. However, the hybrid scheme provides slightly higher error (better privacy) than the RR mechanism since the correlations in the data are considered in hybrid scheme as opposed to the RR mechanism. Privacy improves with decreasing fingerprint robustness and when λ increases, the loss in the robustness is significantly higher than the gain in the privacy. We observed that for values of λ that are below 0.5, the proposed hybrid scheme provides both high fingerprint robustness and reasonable privacy.

DISCUSSION
In this section, based on our experimental results we further discuss about considering privacy and liability together, the practicality of the proposed scheme, and the application of the proposed scheme to different domains.

Fingerprint Robustness and Privacy
When individuals share their personal data with SPs, they want to protect their privacy as well as to identify source of a potential data leakage in case of illegal distribution of their data. As shown in Section 7.5, techniques to protect the privacy of individuals (such as LDP-based mechanisms) do not let individuals to detect the source of unauthorised sharing. Similarly, fingerprinting techniques to provide liability for unauthorized sharing of personal data do not consider the privacy of the individuals. In this work, for the first time, we studied liability and privacy together and proposed a hybrid approach to provide privacy and fingerprint robustness together. Although it is not possible to achieve the highest privacy and the highest fingerprint robustness at the same time (due to their conflicting objectives), we showed that it is possible to achieve a scheme that provides reasonable privacy and fingerprint robustness at the same time. We anticipate that this work will pave the way towards a new research direction to achieve privacy and liability using a single mechanism. We plan to study this problem extensively in the future and develop novel mechanisms that provide formal privacy and robustness guarantees.

Complexity and Practicality
In the proposed fingerprinting algorithm (Algorithm 5.1), each data point sequentially decides on a probability for each possible value in set D and inserts the fingerprints accordingly. Hence, the complexity of fingerprinting algorithm is Θ(l · m). To detect the guilty SP in case of data leakage, the data owner needs to compare all fingerprint patterns (given to all SPs) with the leaked data. Since the expected value of fingerprinted data points is p · l in each fingerprinted copy, the complexity of the detection algorithm is Θ(|S| · p · l), where |S| is the number of SPs that received a fingerprinted copy. Note that this is also the storage complexity for Alice if she stores all the fingerprint patterns. As mentioned before, if Alice does not want to store all fingerprint patterns, she can just store the seed value for each SP and check the similarity of fingerprint patters by running the fingerprinting algorithm again in case of data leakage. Note that this slightly increases the complexity of detection algorithm since it requires Alice to run the fingerprinting algorithm along with the detection algorithm. Thus, we conclude that the running times of both fingerprinting algorithm and detection algorithm grow linearly with the design parameters.
To show the practicality of the proposed scheme, we observed its running time using a computer with 1.8 GHz Dual-Core Intel Core i5 processor and 8 GB memory. Based on our experiments, we measured the average running time of fingerprinting algorithm to create one fingerprinted copy as 0.15 ms. and the average running time of detection algorithm as 3.11 ms. when |S| = 1000, l = 1000, p = 0.1, and m = 3. These results also show the efficiency and practicality of the proposed scheme.

Application of the Proposed Scheme to Other Domains
In the evaluations, we implemented the proposed fingerprinting scheme for genomic data sharing. However, the proposed scheme can be used for sharing other types of personal data, such as location data. Here, we briefly discuss the differences for the application of the proposed algorithm between genomic data and location data. For different data types, the main difference from genomic data will be the set of possible values for data points (D). For genomic data, D contains three values for all data points. However, when location data is considered, D can be the set of point of interests (POIs) at which Alice can be located at a specific time. Hence, for each data point, the set D may be different.
The size of D for location data will also be larger, and hence the running time of the fingerprinting algorithm will be higher for location data. In terms of robustness, we expect an improvement for location data application due to having more possible values for each data point. In genomic data, when a data point is fingerprinted, its value must be one of two remaining values, and hence providing the same fingerprint for a data point to multiple SPs is very likely for genomic data. However, when Algorithm 5.1 adds a fingerprint to a location data point for two different SPs, the probability of adding the same fingerprint is lower (due to size of D), which improves the uniqueness of the fingerprints. As discussed before, uniqueness of the fingerprints increases fingerprint robustness.

CONCLUSION
We have proposed a probabilistic fingerprinting scheme that also considers the correlations in the data during fingerprint insertion. First, we have shown how to assign probabilities for the sharing decision of each data point that are consistent with the inherent correlations in the data. Then, we have described the integration of Boneh-Shaw codes into the proposed algorithm to improve fingerprint robustness against collusion attacks. We have also proposed a detection algorithm that initially selects the suspects based on similarity scores and decides the guilty SP using the detection technique of Boneh-Shaw codes. Furthermore, to provide privacy along with fingerprint robustness, we have proposed a hybrid approach that controls the trade-off between privacy and fingerprint robustness. Our experimental results on genomic data show that the proposed fingerprinting scheme is robust against a wide range of attacks and it can also provide reasonable privacy by slightly degrading the fingerprint robustness. The proposed scheme is a first step for sharing personal data with service providers by providing both liability and privacy guarantees at the same time.