{'fraction_non_alphanumeric': 0.03513441575725313, 'fraction_numerical': 0.010959933614116395, 'mean_word_length': 4.5732984293193715, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Privately Connecting Mobility to Infectious Diseases via Applied Cryptography

Recent work has shown that cell phone mobility data has the unique potential to create accurate models for human mobility and consequently the spread of infected diseases. While prior studies have exclusively relied on a mobile network operator's subscribers' aggregated data in modelling disease dynamics, it may be preferable to contemplate aggregated mobility data of infected individuals only. Clearly, naively linking mobile phone data with health records would violate privacy by either allowing to track mobility patterns of infected individuals, leak information on who is infected, or both. This work aims to develop a solution that reports the aggregated mobile phone location data of infected individuals while still maintaining compliance with privacy expectations. To achieve privacy, we use homomorphic encryption, validation techniques derived from zero-knowledge proofs, and differential privacy. Our protocol's open-source implementation can process eight million subscribers in 70 minutes.


Introduction
Human mobility plays a crucial role in infectious disease dynamics. It leads to more contact between receptive and infected individuals and may introduce pathogens into new geographical regions. Both cases can be responsible for an increased prevalence or an outbreak of an infectious disease [72]. In particular, human travel history has been shown to play a critical role in the propagation of infectious diseases like influenza [32] or measles [40]. Therefore, understanding the spatiotemporal dynamics of an epidemic is closely tied to understanding the movement patterns of infected individuals.
Until a few years ago, researchers had to rely on general data, such as relative distance and population distribution, to model human mobility. This model was then combined with a transmission model of a particular disease into an epidemiological model, which was then used to improve the understanding of the geographical spread of epidemics. Mobile phones and their location data have the unique potential to improve these epidemiological models further. Indeed, recent work [74] has shown that substituting this inaccurate mobility data with mobile phone data leads to significantly more accurate models. Integrating such up-to-date mobility patterns allowed them to identify hotspots with a higher risk of contamination, enabling policymakers to apply focused measures.
While prior studies have exclusively relied on aggregated data of all mobile network operator's subscribers' it may be preferable to contemplate aggregated mobility data of infected individuals only. Indeed, a cholera study [33] observed that although their model succeeded in showing that some mass gatherings had major influences in the course of the epidemic, it performed less well when the cumulative incidence is low. They speculated that demographic stochasticity could be one reason for the bad performance of their model. In other words, the infected individuals' mobility pattern may not be precisely reflected by the population's mobility if the prevalence is low. To mitigate this problem, we propose the usage of infected individuals' mobile phone data, which should lead to an improvement in the predictive capabilities of epidemiological models, especially in highly dynamic situations.

Privacy Goals
Our system should report a heatmap of aggregated mobile phone location data of infected individuals without revealing an individual's location or whether an individual has been infected. To that end we combine various state-of-the-art privacy-preserving cryptographic primitives to design a two-party client-server protocol for which the epidemiological researcher or a health authority inputs patients' identifiers, and the mobile network operator (MNO) inputs its subscribers' location data.
Our solution should, thereby, be able to combine both datasets without leaking the inputs to the other party. Furthermore, no party should be able to gain any information on the other dataset by cheating during protocol evaluation, e.g., by providing malicious inputs. Even if both parties follow the protocol honestly, the resulting heatmap of aggregated location data can still leak sensitive information about individuals. Thus, our protocol must also prevent this inherent output leakage while still preserving the usefulness of the resulting heatmap.

Roadmap
In Section 2, we discuss the relevant related work. Section 3 provides the necessary preliminary definitions and notations. Section 4 first states the problem we want to solve in this article. It then gradually develops a solution by introducing privacy protection mechanisms step by step. In Section 5, we perform a dedicated security and privacy analysis of our solution. Section 6 elaborates on the implementation of our solution as well as demonstrating the performance. Section 7 concludes with a discussion about legal considerations for an actual roll-out and how multiple parties can be included. We defer to the appendix missing proofs of our security analysis (Appendix A) and additional material regarding differential privacy (Appendix C).

Related Work
Numerous research directions have previously sought to model the spread of infectious diseases. Most closely related to this paper is work connecting mobile phone data to infectious diseases.

Mobility and Infectious Diseases
Mobile phone data provides an opportunity to model human travel patterns and thereby enhance understanding of infectious diseases' transmission [72]. Location data derived from call detail records (CDRs) -phone calls and text messages -have been used to understand various infectious diseases' spatial transmission better, see Table 1. Each of the studies got their CDRs from one MNO, which most of the time had the largest market share and coverage. The common understanding is that biases such as Multi-SIM activity and different mobile phone usage across different geographical and socio-economic groups have a limited effect on general estimates of human mobility [73]. The most common model was to assign an individual a daily location. More concretely, each subscriber was assigned to a study area on each day based on the cell tower with the most CDRs or the last outgoing CDR. Further, the primary study area ("home") was computed for each subscriber by taking the study area where the majority of days were spent.
All of the studies emphasized that preserving individuals' privacy is mandatory. In all cases -to the best of our understanding -the involved MNO anonymized the CDRs before handing them over to the health authority. In addition, we found that the MNO aggregated the CDRs in at least two cases. However, none of the studies discussed privacy definitions or the potential risk of de-identification, which is exceptionally high for location data [51]. Therefore, it is hard to assess if they achieved their goal of preserving individuals' privacy.

Exposure Notification
Many technological approaches were developed to help reduce the spread and impact of the Covid-19 pandemic [13,14,23,39,62,70,71]. Most of them focus on exposure notification, where the main challenges include privacy-friendliness, scalability, and utility. These approaches crucially rely on sizable parts of the population using smartphones, enabling Bluetooth, and installing a new app. In contrast, our proposal does not help with contact tracing, but gives potentially useful epidemiological information to health authorities without requiring people to carry around smartphones or installing an app. Indeed, any mobile phone is sufficient.
In subsequent work [45], the authors propose to use a threshold PIR-SUM protocol to allow performing privacy-preserving epidemiological modeling on top of existing contact-tracing information. Their PIR-SUM protocol is based on a multi-server private information retrieval protocol, which is not suitable for our use case where a single entity (e.g., the mobile network operator) holds all location data. While the threshold PIR-SUM protocol can in theory be built using a single-server PIR, these protocols are significantly more expensive than the multi-server PIR they use. Furthermore, their protocols require a mix-net [2] to provide unlinkability of their participants messages, which already requires multiple servers, and it is not immediatly obvious how to apply their ad-hoc MPC protocol to verify the validity of queries to a single-server PIR. For singleserver PIR protocols based on homomorphic encryption, our input validation procedure from Section 4.3 might be an alternative.

PSI-CA and PSI-SUM Protocols
Several works attempt to improve contact tracing by enabling users to query a database, while learning nothing more then the number of intersections using PSI-CA (Private Set Intersection Cardinality) [70,24,26] protocols, or while learning nothing except the sum of the associated values of the items in the intersection using PSI-SUM [47,57] protocols.
While a PSI-SUM protocol perfectly matches our use case in theory, an application of these PSI-SUM protocols in a straightforward fashion for our main scenario in Section 6.6 -where we want to calculate the sum of vectors of length k = 2 15 for a subset of n = 2 23 identifiers -would result in impractical communication cost (multiple TB).
In [54], the authors propose a method to build PSI-SUM from their PIR-withdefault primitive. This approach allows one to greatly reduce the communication to be linear in the smaller set size (the size of the queried subset of the population in our scenario). They present two approaches, where the first one has an expensive setup phase (multiple GB transferred for our scenario) and then has very performant queries. However, our scenario's associated values are temporal location data and would change for new protocol executions, meaning the setup phase would have to be repeated each time. Their second approach does not rely on a setup phase and -for a database size of n = 2 25 identifiers and t = 2 12 queried elements -requires 379 MB of data transfer. However, this again only calculates the sum of a single item. A naive k = 2 15 -times repetition of the approach would again result in impractical communication cost. One could investigate if the protocol can be further optimized for large associated data, since the PSI-part of the protocol does not need to be repeated.
An additional problem of the protocol in [54] is, that it cannot ensure that a query does not contain an item multiple times. Applied to our use case, this leads to problems in combination with differential privacy [27], since a larger noise needs to be added for privacy, limiting utility. The protocol in [45] solves the same issue by executing a separate MPC protocol to ensure that the queries are valid and do not contain duplicates.

Generic Multi-Party Computation
Generic Multi-Party Computation (MPC) protocols allow several parties to securely evaluate a function without having to disclose their respective inputs. Several protocols [78,37,21,22] and efficient implementations for generic MPC exists [1,49], amongst many others.
We do not use generic MPC since all efficient MPC protocols exchange data linear in the size of the computed circuit and are therefore not well suited for the large databases considered in this work. Both, secret sharing and garbled circuit based MPC, would require the (secure) transmission of the server's database (either in secret-shared form or embedded in a circuit) to the client, requiring several GB of communication (e.g., 2 23 × 2 15 matrix of 32 bit integers has a size of 1 TB). Furthermore, the most efficient secret sharing schemes, such as the popular SPDZ [22,21], require a so-called Beaver triple (for multiplying values) which has to be precomputed in an expensive offline phase and can not be reused. Computing enough triples for our protocol (i.e., one triple per database entry) would require 2 38 triples. This triple generation alone would require > 700 hours and more then 1000 TB of communication on our hardware using the MP-SPDZ library [49].

Preliminaries
Here we will first introduce the notations and then describe homomorphic encryption (HE) and differential privacy (DP).
We write vectors in bold lower case letters and matrices in upper case letters. We use x i to access the i-th element of a vector x. For m ∈ N and x ∈ Z, let x m be defined as the vector of powers of x: x m = (1, x 1 , ..., x m−1 ). We denote by c • d the element-wise multiplication (Hadamard product) of the vectors c and d. For a positive integer p, we identify Z p = Z ∩ [−p/2, p/2). For a real number r, r denotes the nearest integer to r.

Homomorphic Encryption
Homomorphic encryption (HE) [35] allows to operate on encrypted data and, thus, has the potential to realize many 2-party protocols in a privacy-preserving manner. Compared to MPC, protocols using HE usually require less data communication and only one communication round, at the cost of more expensive computations.
Modern HE schemes [9,8,31,16,17] base their security on the learning with errors [64] hardness assumption and its variant over polynomial rings [56]. They allow to perform both addition and multiplication on ciphertexts. During the encryption of a plaintext, random noise is introduced into the ciphertext. This noise grows with each homomorphic operation, negligible for additions but significantly for homomorphic multiplications. Once this noise becomes too large and exceeds a threshold, the ciphertext cannot be decrypted correctly anymore. We call such a scheme, that allows evaluating an arbitrary circuit over encrypted data up to a certain depth, a somewhat homomorphic encryption scheme (SHE). The specific depth depends on the choice of encryption parameters, and choosing parameters for larger depths comes, in general, with a considerable performance penalty. In this work, we use the BFV [8,31] SHE scheme to encrypt the inputs of our protocol.
Besides semantic security, two-party protocols based on HE additionally either require the notion of circuit privacy [35], or function [36] (evaluation [3]) privacy, to hide the function applied on the ciphertexts. Function privacy is often easier to achieve than circuit privacy in practice. It requires that the outputs of evaluating different circuits homomorphically on the same encrypted data need to be indistinguishable. In other words, a party decrypting the final result of a function private HE scheme can not learn anything about the circuit applied to the input data. Like many HE schemes, BFV does not naturally provide function privacy, however, it can be added by applying noise flooding [35].

Differential Privacy
Differential privacy (DP) [27] defines a robust, quantitative notion of privacy for individuals. The main idea is that the outcome of a computation should be as independent as possible (usually defined by a privacy parameter ) from the data of a single input. Applied to our use case, DP makes the final heatmap independent to the contribution of any individual, preventing it from leaking sensitive information.
DP is highly compatible with existing privacy frameworks and has successfully been applied to several real-world applications. Recent work [60] showed that DP satisfies privacy requirements set forth by FERPA 5 . Even before this analysis, several businesses were already using DP. For example, Apple [5] and Google [38] have applied differential privacy to gather statistics about their users without intruding on individual's privacy. Recently, the U.S. Census 2020 uses differential privacy as a privacy protection system [11].
The most prevalent technique to achieve DP is to add noise sampled from a zero-centered Laplace distribution to the outcome of the computation. The distribution is calibrated with a privacy parameter and the global sensitivity ∆q of the computation and has the following probability density function: To add noise to a protocol operating on integers, we discretize the Laplace distribution by rounding the sampled value to the nearest integer. For a formal definition of DP, we refer to Appendix C.

Privacy Preserving Heatmap Protocol
We first describe our goal and then introduce each privacy protection mechanism step by step.

The Desired Functionality
Our aim is to accumulate the location data of infected individuals to create a heatmap, assisting governments in managing an epidemic. Two parties controlling two different datasets are involved: A health authority who knows which individuals are infected; and an MNO who knows the location data of their subscribers. More specifically, the MNO knows how long each of their subscribers is connected to which cell towers (CDRs are a subset of this information). Based on this mobility data, our protocol could answer several questions. One in line with epidemiological literature is to look at the individuals' mobility data in the incubation period (e.g., 5-7 days for COVID-19). The final heatmap will show areas with a higher chance of getting infected with the disease. A natural extension would be to study mobility patterns after the incubation period but before confirmation/quarantine. So our protocol is generic regarding the time unit or the granularity of location data. When discussing privacy guarantees that depend on the actual data, we will explicitly outline the chosen setting.
Protocol Description. If the MNO knows which of its subscribers is infected, it can do the following to create the desired heatmap: -Initialize a vector h of k elements with zeros, where k is the total number of cell towers. Each element of this vector corresponds to one cell tower. Let us rewrite this process into a single matrix multiplication. First, we encode all N subscribed individuals into a vector x ∈ Z N 2 , with x i ∈ Z 2 indicating, whether the individual i is infected (x i = 1) or not (x i = 0). Then we encode the location data in a matrix Z = (z 1 , z 2 , . . . , z k ) ∈ Z N ×k such that the vector z j contains all the location data corresponding to the cell tower identified by j. In other words, the i-th element of the vector z j contains the amount of time individual i spent at cell tower j. Now, we can calculate the heatmap as We depict the basic protocol, involving the health authority as a client and the MNO as a server, in Figure 1, assuming the health authority and the MNO already agreed on identifying all subscribed individuals by indices i ∈ 1, ..., N .

Client (Health Authority) Server (MNO)
Input: Remark 1 (Agreeing on database indices). The protocol in Figure 1 already assumes that the two parties agree on the indices of individuals in the database. In practice, the individuals can be identified using several methods, such as phone numbers, mail addresses or government ids. We now give two options to get a mapping from a phone number to a database index, while noting that any other identifier can be trivially used instead: -The MNO and health authority engage in a protocol for Private Set Intersection (PSI) with associated data (e.g., [15,20]). In such a protocol, the health authority and the MNO input their list of phone numbers. The health authority gets as the protocol's output the phone numbers that are in both sets, as well as the associated data from the MNO. The associated data would be the index in the database in our case. -The MNO sends a mapping of all phone numbers to their database index in plain. This approach is efficient and straightforward, but it discloses all subscribed individuals to the health authority. However, this is essentially a list of all valid phone numbers in random order and does not leak anything more than the validity of that number. Still, this may be an issue in some scenarios.
While the PSI-based solution has some overhead compared to the plain one, the performance evaluation in [20] shows that a protocol execution with 2 22 MNO items and 4096 health authority items takes about 1.4 seconds online (excluding a precomputable offline phase taking 467 seconds) with a total communication of 8.3 MB -a minor increase when looking at the overall protocol. While PSI-SUM protocols [47,57,54] could be used to calculate the final heatmap without revealing which identifiers are present in the MNO's set, their additional overhead is not worth the minor privacy gain, considering that for the type of identifier we are using (phone numbers), one can often already publicly check if a phone number is associated with a mobile network operator 6 . We therefore relax our setting to allow revealing which identifiers are present in the MNO's set to take advantage of the reduced communication of our approach compared to the full PSI-SUM approaches mentioned above.
Executing the protocol described in Figure 1 would enable the MNO to learn about infected individuals, which is a massive privacy violation. On the other hand, the health authority could query a single individual's location data by sending a vector x = (1, 0, . . . , 0), violating privacy. In the following, we describe our techniques to protect against these violations.

Adding Encryption
To protect the vector send by the health authority, and therefore who is infected and who is not, we use a HE scheme (KGen, Enc, Dec, Eval). Before executing the protocol, the health authority runs KGen to obtain a secret key sk and an evaluation key evk. We assume that the MNO knows evk, which is required to perform operations on encrypted data, before running the protocol.
In the updated protocol, the health authority now uses sk to encrypt the input vector x and sends the resulting ciphertext vector c ← Enc sk (x) to the MNO. The MNO then uses evk to perform the matrix multiplication on the encrypted input vector and sends the resulting ciphertext vector h * ← Eval evk c T · Z back to health authority. The health authority can now use sk to decrypt the result and get the final heatmap h = Dec sk (h * ).
Informally, if the used HE scheme is semantically secure, then the MNO cannot learn which individuals are infected by the disease and which are not.

Input Validation
In the simple protocol, the health authority could use a manipulated input vector x to include an individual multiple times (e.g., setting the corresponding vector entry to 100 instead of 1). Such an individual could most likely be filtered out in the final heatmap. Since the input vector is encrypted, the MNO cannot trivially check if the vector is malicious or not. Also, comparing encrypted elements is not trivially possible in most HE schemes. However, the required check can be encoded, such that it outputs 0 if everything is correct, and a random value otherwise. We then can add this value to the final output as a masking value which randomizes the MNO's response if the input vector is malicious. We describe how to generate this masking below.
Masking Against Non-Binary Query Vector. Note that the HE schemes plaintext space usually is Z p , i.e., the integers modulo a prime p. Therefore, the inputs to our protocol -the vector x and the matrix Z -consist of elements in Z p . As outlined above, it is crucial to the protocol's privacy that the input vector is binary, i.e., only contains 0s and 1s. If this is not the case, the health authority could arbitrarily modify a single person's contribution to the overall aggregated result. It is essential for DP considerations to bound the maximum possible contribution of a single individual (sensitivity).
Since the MNO only receives an encryption of the input vector, simply checking for binary values is not an option. However, we can use similar techniques to the ones used in Bulletproofs [10] to provide assurance that the query vector x ∈ Z N p contains only binary elements. First, we will exploit the following general observation. Let d = x − 1, then x • d is the zero vector iff x is binary. Note that the MNO can compute an encryption of d from the encrypted input vector. The result of the Hadamard product x • d can be aggregated into a single value by calculating the inner product x, d , which will again be zero if x is binary. The MNO also multiplies x with powers of a random integers y to reduce the probability of the health authority cheating by letting several entries of x cancel each other out during the inner product, which gives the mask: where For the generic case of a vector v and a randomly chosen y, v, y N = 0 will hold for v = 0 only with probability N/p [10]. Using a ν bit modulus p (p ≈ 2 ν ), translates to a soundness error of ν − log 2 (N ) bits. For details of this calculation see Appendix A.1. In particular, if we look at N = 2 23 , ν = 60, parameters sufficient for small nation-states (see Section 6.6), we get 37-bit statistical security. Standard literature suggest a statistical security parameter of at least 40-bit; therefore, we developed a method to enhance the statistical security without significant overhead.
Boosting Soundness. The high-level idea is that we lower the probability of cheating successfully by a random linear combination of separate masks. Intuitively, a malicious health authority would have to guess correctly for every single mask. Thus, the soundness converges to the underlying field size in the number of terms of the linear combination. For our purpose, two terms already suffice for an appropriate security level: where r 1 , r 2 $ ← Z p \{0} are two random values. Therefore, the statistical security level increases to ν − 1 bit (= 59 bits for ν = 60). We refer to Lemma 2 in Appendix A.1 for a proof of this statement.
Applying the Mask. Once the µ bin is calculated, it gets added to the final output of the protocol. However, if the masking value is not zero, we have to make sure that a different random value is added to each element of the output vector to prevent leaking the mask if some output vector values are known beforehand. Therefore, the final mask µ can be calculated using a random vector r The final mask µ is now equal to 0 k if x is a binary vector, random otherwise.
Remark 2 (PSI-SUM with Indices). So far the protocol securely implements a functionality dubbed PSI-SUM with Indices. For completeness, we included a description and its ideal functionality in Appendix B.

Adding Differential Privacy
The aggregated location data can still leak information about the location data of individuals. For example, the health authority could abuse the heatmap to track an individual by just querying him or by querying him alongside individuals from a completely different area. The location data of the targeted individual would be visible as an isolated zone in the resulting heatmap. Applying DP with suitable parameters will protect against such an attack since the overall goal of DP is to decrease the statistical dependence of the final result to a single database entry. In our use case, therefore, DP achieves that it is highly unlikely to distinguish between heatmaps, in which we include a single individual in the accumulation, and heatmaps, in which we do not. Choosing proper parameters, however, highly depends on the underlying dataset. On the one hand, the chosen should be small enough to satisfy privacy concerns; on the other hand, it should be big enough not to overflow the result with noise, creating hotspots on its own. We discuss one method to choose suitable parameters in Section 5.2.

Final Protocol
Finally, with all measures to protect privacy in place, we present the final protocol in Figure 2.

Security & Privacy Analysis
On the one side, the protocol provides input security against a malicious MNO, i.e., even if the MNO deviates from the protocol, it cannot determine the patient's identifiers (see Section 5.1). On the other side, individuals' location data are protected even against a malicious health authority, i.e., the health authority cannot track individuals (see Section 5.2)).

Security
Two-party protocols are usually proven secure with the real-ideal world paradigm [12]. Roughly speaking, one has to prove that the protocol does not leak any additional information than when computed with the help of a trusted third party. The trusted third party is modeled as an ideal functionality presented in Figure 3.
Semi-Honest Security. Before we discuss malicious security, we will show that our protocol achieves semi-honest security.
1. Upon receiving an input (input, sid, P1, P2, x) from a party P1, verify that x ∈ Z N p , else ignore input. Next, record (sid, P1, P2, x). Once x is recorded, ignore any subsequent inputs of the form (input, sid, P1, P2, ·) from P1. 2. Upon receiving an input (input, sid, P1, P2, Z) from party P2, verify that Z ∈ Z N × * p , else ignore input. Proceed as follows: If there is a recorded value   The high-level idea is two-fold. Firstly, by the definition of semantic security, the MNO can not learn anything from encrypted data, hence, we reduce our protocol's security against the MNO's corruption to the semantic security of the underlying HE scheme. Second, function privacy guarantees that the health authority learns nothing more about the MNO's matrix, than what can be derived from the input x and the output h. The formal proof can be found in Appendix A.
Malicious Security. Achieving simulation-based security against a malicious MNO would be similar to verified HE. While some theoretical constructions exist [52], they are not practical.
Instead, we show input security against a malicious MNO, also known as onesided simulation security. This notion has been first considered in the context of oblivious transfer [59], was then formalized [44], and recently used [15] in the realm of PSI. In our protocol, one-sided simulation guarantees that the patients' identifiers are protected even in the presence of a malicious MNO (one that deviates from the protocol). For a formal definition, see Appendix A.
Theorem 1. Let us assume HE is an IND-CPA secure homomorphic encryption scheme that provides function privacy. Then the protocol in Figure 2 securely realizes F Hmap with one-sided simulation in the presence of a maliciously controlled MNO.
Proof. From Lemma 1, we already know that the protocol is secure against semi-honest adversaries. The only thing left to show is input privacy of the health authority against a malicious MNO, i.e., the MNO is not able to learn any information from the health authority's input (patients' identifier). Now, due to the fact that the MNO's view only includes an encryption of the health authority's input, by the semantic security of HE, we have that the MNO learns nothing about the health authority's input.

Privacy
The protocol's output exposes aggregate information, namely the amount of time spent by individuals at a cell tower, to the health authority. In the worst case, only one individual is present in the aggregation. Even in this case the health authority should not be able to single out any individual. To mitigate this threat, we propose to use differential privacy (DP).
Privacy-Utility Tradeoff. It is a challenge to choose the right amount of noise to protect individuals' privacy while still preserving utility. Ultimately, this tradeoff is not only technical but also has to take into account normative considerations [60]. Here, we only explore the technical tradeoff and leave the latter one to policymakers.
There has been limited research specifically addressing the technical tradeoff [53,50,61]. However, the methods of [53,50] are not applicable to our protocol since they require either input from the individuals [50] or "knowing the queries to be computed " [53]. Therefore, we choose to follow [61]'s rigorous method to find real-world parameters for DP.
Choosing the Right . The model in [61] provides a principled approach to choose . It can be split into two major steps resulting in two constraints that have to be satisfied simultaneously. First, one chooses the desired utility by defining a confidence interval. The parameters of the confidence interval give the first constraint on the required minimum number w of infected individuals and . Note that if the health authority does not provide the number of infected individuals w or lies about it, privacy is not affected. Only utility cannot be guaranteed any more.
Further, the method requires setting a bound on the expected privacy harm per individual and estimating the expected cost (baseline cost) of not being part of the outcome (e.g., database breach). This leads to the second constraint on . Every pair of parameters, , and the number of infected individuals w that simultaneously fulfill both constraints, is a reasonable privacy-utility tradeoff choice.
To illustrate this method, we now provide a possible set of values for this example. Choosing these values requires a few assumptions. We want to highlight that our assumptions are, at best, educated guesses. The real-world values have to be adjusted to the concrete circumstances and be discussed by a group of privacy, ethical, legal, epidemiological and policy experts.
First, the time unit is days for consistency with previous epidemiological studies, see Section 2.1. We decided to aim for a margin of error of ±5% with a probability of 0.95 (confidence). In terms of privacy, the method requires us to estimate the expected base costs (harm) that arise for an individual by using the MNO's services (data breach at the MNO would leak the location data), i.e., without even being part of the computation. We assume that without performing our protocol, this probability is less than 0.00001. In the case of a leakage, we set the monetary harm inflicted to an individual to an exemplary amount of $1000 per day. This seems reasonable since most smartphone users divulge exact location data for far less than that amount to companies. Now, we can calculate the expected baseline cost as 0.00001 · $1000 = $0.01 per day of leakage. We think performing the protocol is justified if the cost of participating does not exceed $0.02. We arrive at the following two constraints (see Appendix C.1 for details) which are illustrated in Figure 4. If the health authority wants to release a heatmap to inform the public about hotspots or justify their policies, it must add additional noise to the map. Otherwise, the MNO could subtract the noise, which itself added in the first place, thus removing the protection provided by DP. The addition of noise by both parties does not violate privacy because DP enjoys composability [28]. More concretely, if the heatmap produced by the MNO is 1 -differentially private and the health authority adds noise corresponding to 2 to it, then the final heatmap is ( 1 + 2 )-differentially private. The same methodology as above should be applied to choose 2 . It is crucial to find parameters such that the points (w, 1 ), (w, 2 ), and (w, 1 + 2 ) are in the plot's green area.
To illustrate the trade-off of Figure 4 for a practical example, we performed experiments on the London subset of the publically available gowalla dataset [18]. This dataset consists of thousands of check-in's where each check-in consists of a user-id, GPS coodinates and a timestamp. To stay consistent with the methodology we discuss in the rest of the paper, we mapped all check-in locations to the locations of the nearest cell towers in London and treat multiple check-ins from the same user to the same cell tower as just one check-in. The final dataset consists of 4571 people and 9994 cell towers. Figure 5 depicts a snipped of the original heatmap and the heatmaps resulting by applying DP, having w = 600 randomly chosen infected people and varying . The generated figures visually confirm our expectations based on the calculations above: One can observe that the heatmap without DP (Figure 5a) is very similar to the heatmap with too little noise (Figure 5d), indicating that the noise is not enough to guarantee privacy. On the other hand, the heatmap with too much noise (Figure 5b) clearly provides no utility due to the noise creating too many hotspots. In the correctly parameterized heatmap (Figure 5c), one can observe some difference to Figure 5a due to noise, however the biggest hotspots remain the same. In other words, privacy and utility are preserved. Government officials now can use Figure 5c to set new policies (e.g., closing public locations in the hotspot areas) without the possibility to track the location of individuals.
Remark 3. Several queries could contain the same individual. Since the overall movement pattern for the same individual changes slowly over time, we model this as an identical database. Therefore the total number of queries has to be limited to the total privacy budget. For example, if we follow the values of the analysis above and the health authority queries once a week for two months (= 8 queries), the privacy budget suffices to provide utility as long as the number of infected individuals w is above 750 per week.

Summary and Limitations
To summarize, the patients identifiers are encrypted during the whole protocol, hence, the semantic security of the HE scheme protects the privacy of the patients even if the MNO is cheating. The functional privacy of the HE scheme prevents, that the MNO's computation leaks anything about any location data to the health authority. The binary mask guarantees that each individual is only present at most once in the query and prevents that a cheating health authority can amplify the contribution of individual's location data in the final heatmap. Differential privacy then prevents that location data from individual's can be (a) Original data without noise.
(c) = 0.6: utility is satisfied and privacy is guaranteed (green area in Fig. 4).
(d) = 3: privacy is not guaranteed (above the privacy line in Fig. 4). singled out from the resulting heatmap. Consequently, the location data of individuals is protected even if the health authority is cheating. Hence, all sensitive information is always kept private from other parties during the whole protocol.
Even though privacy of input data is guaranteed, the protocol has some practical limitations. The protocol cannot guarantee, that either the health authority, or the MNO use truthful data in the first place. In other words, malicious health authorities can randomly mark individuals as infected and MNO's can use fake location data to create the heatmap. The protocol then would guarantee privacy of these wrong inputs, but the produced heatmap would be useless. This dependence on the truthfullness of the input data is, unfortunately, a generic problem to any computation (plain and privacy preserving) and can not be prevented by cryptographic measures. We, therefore, propose that independent officials perform a yearly audit, e.g., at the end of the year, of the involved data to expose cheating parties.
Another limitation of our protocol is, that the utility of the heatmap scales with the prevalence of the disease. Concretely, the more people are infected, the smaller the impact of differential privacy on the final outcome. Conversely, the less people are infected the larger the impact of the noise and the utility drops. Thus, for very small prevalences it might not be possible to achieve high utility while maintainig privacy with our protocol.

Implementation & Performance
The data aggregation of our protocol requires only homomorphic ciphertextciphertext addition and homomorphic plaintext-ciphertext multiplication; however, the evaluation of the binary mask additionally requires homomorphic ciphertext-ciphertext multiplication. For our implementation we chose to use the BFV [8,31] SHE scheme, which fulfills these requirements. More specifically we use its implementation in the SEAL v3.6 [65] library, a fast, actively developed open-source library maintained by Microsoft Research.
The computationally most expensive phase in the protocol is the Data Aggregation phase, in which the MNO multiplies a huge matrix to a homomorphically encrypted input vector. Therefore, the main objective of our implementation is to perform this huge matrix multiplication as efficiently as possible.

Packing
Modern HE schemes (including BFV) allow packing a vector of n plaintexts into only one ciphertext. Performing an operation on this ciphertext then is implicitly applied to each slot of the encrypted vector, similar to single-instructionmultiple-data (SIMD) instructions on modern CPUs (e.g., AVX). However, the ciphertext size does not depend on the exact number (≤ n) of encoded plaintexts. The HE schemes support various SIMD operations, including slot-wise addition, subtraction and multiplication, and slot-rotation. However, one can not directly access a specific slot of the encoded vector. We can use the SIMD encoding to speed up the matrix multiplication of our protocol significantly.
In the BFV scheme (and its implementation SEAL), the number of available SIMD slots equals the degree of the cyclotomic reduction polynomial (x n + 1); thus, it is always a power of two. In the ciphertexts, the n slots are arranged as matrix of dimensions (2 × n /2). A ciphertext rotation affects either all rows or all columns of the matrix simultaneously. Therefore, we can think of the inner matrix as two rotatable vectors, which can be swapped.

Homomorphic Matrix Multiplication
Since SEAL does not provide algorithms for plain-matrix times encrypted vector multiplication, we implement the baby-step giant-step (BSGS) optimized matrixvector multiplication [41,42,43] on our own and optimize it to fully leverage all slots (i.e., both rotatable vectors) of the homomorphic ciphertexts.
BSGS Matrix Multiplication. The SIMD encoding can be used to efficiently speed up matrix multiplication by using the diagonal method introduced by Halevi and Shoup [41], and its optimized version based on the BSGS algorithm [42,43]: . 7 Note, that rot(x, j) only has to be computed once for each j < m 1 , therefore, Equation (3) only requires m 1 + m 2 − 2 rotations of the vector x in total.
Extension to Bigger Dimensions. In our protocol, we want to homomorphically evaluate x T · Z = (Z T · x) T , where x ∈ {0, 1} N and Z ∈ Z N ×k p , for big parameters N and k. As described in Section 6.1, the inner structure of the BFV ciphertext consists of two vectors of size n /2 each, and it does not allow a cyclic rotation over the whole input vector of size n. However, a rotation over the whole input vector is required by the BSGS algorithm. Therefore, we only can perform a BSGS multiplication with a ( n /2 × n /2) matrix using this packing. Fortunately, we can use the remaining n /2 slots (i.e., the second vector in the inner structure of the BFV ciphertext) to simultaneously perform a second ( n /2 × n /2) matrix multiplication. Therefore, after a homomorphic BSGS matrix multiplication, the result is a ciphertext c, where each of the two inner vectors encodes the result of a (1 × n /2) × ( n /2 × n /2) vector-matrix multiplication. The sum of those two vectors can easily be obtained by rotating the columns of the ciphertext c and adding it to the first result: Thus, we can use one ( n /2 × n /2) BSGS matrix multiplication and Equation (4) to implement a homomorphic (1 × n) × (n × n /2) = (1 × n /2) vector-matrix multiplication.
Taking this into account, we split the huge (N × k) matrix into n v · n o submatrices of size (n × n /2), with n v = N n and n o = 2k n , padding the submatrices with zeros if necessary. We split the input vector x into n v vectors of size n (padding the last vector with zeros if necessary) and encrypt each of these vectors to get n v ciphertexts c i . The final result of the x T · Z matrix multiplication can be computed with the following equation: where, SubMat(Z, j, i) returns the submatrix of Z with size (n × n /2), starting at row n · j and column n 2 · i, and MatMul(Z, c) performs the homomorphic BSGS matrix multiplication Z · c followed by Equation (4).
Equation (5) produces n o ciphertextsc i , with the final results being located in the first n /2 slots of the ciphertexts. Overall, our algorithm to homomorphically calculate x T · Z requires n v · n o BSGS matrix multiplications and the total multiplicative depth is 1 plaintext-ciphertext multiplication.

Homomorphic Evaluation of the Mask
To calculate the binary vector masking value (Equation (1)), we need to calculate the inner product of two homomorphically encrypted ciphertexts c and d. After an initial multiplication c · d, the inner product requires log 2 ( n /2) rotations and additions, followed by Equation (4) to produce a ciphertext, where the result is encoded in each of the n slots. Our implementation uses rejection sampling and the SHAKE128 algorithm to cryptographically secure sample all the required random values in Z p . The total multiplicative depth to homomorphically evaluate the final mask (Equation (2)) is 1 ciphertext-ciphertext multiplication and 2 plaintext-ciphertext multiplications.

BFV parameters
In BFV, one can choose three different parameters which greatly impact the runtime, security, and the available noise budget (i.e. how much further noise can be introduced until decryption will fail). These paramaters are the degree of the reduction polynomial n = 2 k , the plaintext modulus p, which needs to be prime and p ≡ 1 (mod 2 · n) to enable packing, and the ciphertext modulus q. We test our implementation for a computational security level of κ = 128 bit for different plaintext moduli p using the smallest n (and its default value for q) providing enough noise budget for correct evaluation of our protocol.

Function Privacy and Noise Flooding
Function privacy can be achieved by re-randomization and noise flooding, where the MNO adds an encryption of zero with a sufficiently large noise [35,25] to the protocol's output. Following the smudging lemma [6], one needs to add a ciphertext with noise being λ FP + log 2 (n) + log 2 (n o ) bits larger than the upper bound of our protocol's original output's noise to achieve a statistical distance of 2 λFP between different executions.
We implement noise flooding by creating an encryption of zero (c 0 ) with large noise (in practice, we set the noise as large as possible while ensuring decryption is still possible). Adding c 0 to the output of our protocol (c) results in a ciphertext which has λ FP = noisebudget(c) − noisebudget(c 0 ) − log 2 (n) − log 2 (n o ) statistical function privacy. In our concrete parameter sets, we ensure that λ FP > ν.
However, like most efficient instantiations of function privacy, noise flooding provides security against semi-honest adversaries only (see [25] and contained references), and so our implementation also only provides semi-honest security. Still, once available, our implementation can use efficient maliciously functionprivate FHE schemes instead and benefit from security against a malicious health authority.

Benchmarks
We benchmark our prototype implementation 8 on an c5.24xlarge AWS EC2 instance (96 vCPU @ 3.6 GHz, 192 GiB RAM) running Ubuntu Server 20.04 in the Region Frankfurt with a current price of $4.656 per hour.
In our benchmarks, we focus on evaluating the runtime of the Data Aggregation phase of our protocol. Since in our use cases N is much bigger than k, we implemented multithreading, such that the threads split the number of rows in the matrix (more specifically, the number of submatrices in the rows n v ) equally amongst all available threads. Therefore, each thread has to perform at most nv #threads · n o MatMul evaluations, which will be combined at the end by summing up the intermediate results.
The evaluation of the proving mask with its higher multiplicative depth requires BFV parameters providing a bigger noise budget, however, its actual evaluation does not impact the overall runtime of the protocol since we perform it in an extra thread in parallel to the data aggregation. Furthermore, adding DP, noise flooding, as well as the computations of the health authority (encryption and decryption), have negligible runtime.
The runtime of our protocol is O(n v n o ), i.e., it scales linearly in the number of MatMul evaluations. This can be seen in Figure 6 in which we summarize the runtime of the homomorphic matrix multiplication for different matrix dimensions using only one thread. For real-world matrix dimensions, some added runtime has to be expected due to thread synchronization and the accumulation of the intermediate thread results.
Real World Matrix Dimensions. In our benchmarks, we want to evaluate our protocol with parameters suitable for smaller nation states and set the matrix dimensions to N being larger then the total population of small countries, and k to be larger then the total number of cell towers in these countries. Concretely, we set N = 2 23 and k = 2 15 , parameters enough to evaluate our protocol, for example, for Austria [67,63], Singapore [77,34], Kenya [74], New York City, Paraguay or New Zealand. In Table 2 we list the runtime for a homomorphic (1× 2 23 ) × (2 23 × 2 15 ) matrix multiplication, for different BFV parameters, using (at most) 96 threads. We also provide the total number of MatMul evaluations and the (maximum) number of evaluations per thread. We give performance numbers for a plaintext prime p of size 42 bit, i.e., the smallest size to achieve ν = 41 bit statistical privacy against malicious health authorities using our proving mask.
To capture use cases, where a 42 bit plaintext modulus is not big enough, we also benchmark our protocol for a 60 bit prime p (the maximum value supported by SEAL), providing ν = 59 bit statistical security. Further, we also give the achieved statistical function privacy λ FP in bits for both benchmarks. As Table 2 shows, the MNO's computation takes 70 minutes for a 42 bit plaintext prime and 1 hour 25 minutes for the bigger 60 bit prime. Data Transmission. The data sizes which have to be transmitted between the MNO and the health authority are listed in Table 3. Each row corresponds to a different parameter set from Table 2. The sizes were obtained by storing each of the described elements on the file system on the benchmarking platform. The table lists the size of the ciphertexts (ct), the public key (pk), Galois keys (gk), and relinearization keys (rk). The public key is required for noise flooding to achieve function privacy, whereas Galois keys are required to perform homomorphic rotations. Each rotation index requires one Galois key, plus an additional key for rotating the columns. When using the BSGS algorithm, we need a key for the index 1 to calculate rot(x, j), and a key for the indices k · m 1 , ∀0 < k < m 2 . Also, for masking, we need the keys for the power-of-2 indices to calculate the inner product of two ciphertexts. The relinearization key is required to linearize the result of a ciphertext-ciphertext multiplication. We want to stress that the public key (pk), Galois keys (gk), and relinearization keys (rk) only need to be sent once before our protocol's first evaluation in a data-independent setup phase. Subsequent uses of the protocol can reuse these keys and only require transmitting the ciphertexts. As Table 3 shows, health-authority-to-MNO communication is significantly more extensive than the response of the MNO. The main parts of the communication are the initial ciphertexts and the Galois keys. One reason for the size difference between the ciphertexts in the query and the response is that the parameter k is significantly smaller than N . Another reason is that our implementation performs a so-called modulus-switch after the computation, reducing the ciphertext modulus q to only one of the moduli q i it is composed of. Further observe, that the plaintext modulus p does not affect the communication cost.

Price Estimation for Larger Countries
Here we give an estimate of the costs of evaluating our protocol to create a COVID-19 heatmap for a larger country, more specifically, for Germany. About 83 million people live in Germany, and a total of 80000 cell sites are deployed [46]. With the BFV parameters of the first entry in Table 2, i.e., n = 16384, ν = 41, κ = 128, this corresponds to n v · n o = 5066 · 10 = 50660 MatMul evaluations.
To get n o = 10 MatMul evaluations per thread, we would have to acquire 53 CPU's capable of handling 96 threads each. Assuming a runtime of 30 min per thread (calculated from Table 2), and a price of $4.656/h per CPU, we estimate the cost of evaluating the homomorphic matrix multiplication including the proving mask in a total time of 30 min to $124 using AWS. 9 This estimate shows that it is likely very feasible to create a heatmap once a week to gain valuable insight into the spread of the disease, even for larger countries. We, however, note that care has to be taken when outsourcing this computation to cloud providers to ensure user privacy in accordance to privacy regulations.

Considerations and Conclusion
Our solution shows that privacy-preserving health data analytics is possible even on a national scale. We achieved this by combining three PETs. Each of them has their known limitations, but filtering out their strengths and applying them purposefully lead to a real-world cryptographic protocol. More broadly, we wanted to convey the following message: Even in times of crisis where it is tempting to lower data protection standards for purposes of big data analytics, there are technical methods to keep data protection standards high. And those technical methods are practical and available.
In the following we discuss considerations when instantiating our protocol with multiple health authorities or MNO's, as well as a summary of the key takeaways from a legal case study we conducted. More concretely, we focused on the EU General Data Protection Regulation (GDPR) [29], which is known to be on of the most strict privacy framework.
Multiple MNO's or Health Authorities. Even though it has already been shown that just using the largest MNO of a country for modelling disease dynamics is highly effective in practice [74], one might consider to use data from multiple MNO's. Our protocol can easily be extended to this setting by performing the protocol with each MNO individually and summing up the resulting heatmaps. As long as DP parameters (Section 5.2) are chosen, such that parameters (w i , i ) for the i-th MNO, as well as ( i w i , i i ), fulfill the privacy-utility tradeoff, no additional information is leaked.
Multiple health authorities (e.g., for different provinces in a country) can be included using techniques from [58]. These multiple health authorities can agree on commen public keys, while keeping the decryption key hidden from all parties. After each health authority has agreed on database indices with the MNO (Remark 1), each authority can encrypt their queries using the common public key and the MNO can simply sum them up and proceed with the protocol as usual. After the protocol, the authorities proceed with the keyswitch protocol to output the final heatmap to some specified recipient (e.g., government officials). This adaptation is equivalent to the inital protocol with the same security and privacy guarantees, as long as each patient is registered with only one health authority. Otherwise, the heatmap will be a random output, due to the binary mask.
Legal Considerations. The health authority has used HE for COVID-19 positive individuals' ids, while the MNO has used DP to protected personal data. The MNO does not enter into possession of the decryption key of the health authorities data sets. Therefore, the computations performed should be considered carried out on anonymized data [66], which are data that cannot identify, directly or indirectly, the data subject. In fact, data encrypted both by the health authority and the MNO is not accessible by an entity other than the one carrying out the encryption protocol. Hence, the data should be considered anonymized data -whose processing falls out of the scope of application of the GDPR (Article 29 Working Party) -for all other entities. A similar argument holds for the aggregated location data, which are protected from singling out attacks by DP [19,4]. Nevertheless, the processing of data by health authorities and MNO remains bound to GDPR provisions. In particular, the process to encrypt and make such data inaccessible is a processing activity under the GDPR. Thus, it should comply with legal requirements enshrined in the GDPR. In our use case, a lawful basis for processing personal data can be found in, e.g., Art. 9 (2) (i) GDPR, which deals with data processing in a public health context. It is one reasons why it is likely that there is a legal basis for our protocol.
Therefore, both MNO and health authority's processing activity protected through state-of-the-art PETs should be considered in compliance with GDPR provisions. From a legal perspective, the added value of the provided solution is represented on the one hand by the possibility to transform personal data into anonymized data. On the other hand, the processing activity of anonymizing data and limiting access to personal data ensure data subjects respect their fundamental rights as encoded in the EU privacy and data protection framework.

A Security Proofs
We now prove security using the real-ideal-paradigm [30]. In this paradigm a protocol execution is secure if it behaves the same as when the parties send their input to a trusted third party (the ideal functionality) which does the computation and provides them with the outputs. More formally, an environment should not be able to distinguish between an observation of the protocol with a possible adversary and a simulator interacting with the ideal functionality. More specifically, most of the time, computational indistinguishability is required between the ideal and the real world. In contrast, we require (κ, ν)-indistinguishability to analyze the cheating probability more thoroughly.
We are now interested in the events when the binary mask evaluates to zero even though x / ∈ Z N 2 . This undesired behaviour can only happen in two ways, either α = β = 0 or α = −β. Next, we calculate the probability of these two cases.
First, since r 1 , r 2 = 0 and assuming x = 0 k (x = 0 k is a valid input and should result in a zero mask), we have Pr[α = 0] = Pr[β = 0] = N /p [10]. Hence, Consequently, the probability of α being non-zero is 1 − N /p. Further, the probability of β being −α is 1 /p. Combing these probabilities gives us We get the final probability by putting together Equation (6) and Equation (7) Pr Proof. We use Lemma 2 to prove that to any polynomial time environment the execution π Hmap with a possible adversary A is (κ, ν)-indistinguishable from a simulator S interacting with the ideal functionality F Hmap . More concretely, we claim that as long as the event that x is not binary and at the same time the mask µ = 0 k does not occur, the executions of the ideal and real world are computational indistinguishable. Once we have proven this claim, we are done, since we have already shown that the probability of the above event is exponentially small in the statistical security parameter. Note that for the proof, we have rewritten the protocol in a more formal description π Hmap , see Figure 7. First consider a polynomial time environment which does not corrupt any of the parties. Any meaningful environment will interact with π Hmap or F Hmap in the following way.
S Hmap P1, P2 not corrupted: It starts by sampling a key pair (pk, sk) ← KGen(1 κ ), and sets x ← 0 N . Then it computes c ← Encpk(x). It then instructs P1 to send (sid, P1, P2, pk, c) to P2. On later input of the form (sid, P1, P2, pk, c) from P1 it samples Z ← Z N ×k p . Then it computes h * ← Evalpk(c T · Z + δ + µ). It instructs P2 to send (sid, P1, P2, h * ) to P1. P1 not corrupted, P2 corrupted: Similar as before but it does not have to simulate Z because it learns the input Z from P2. Then it computes Evalpk(c T · Z + δ + µ). P1 corrupted, P2 not corrupted: It learns the input x from P1. Then it proceeds as in the first case until it has to simulate the message to P1. In order to do this it runs a copy of πHmap internally, where it corrupts P1. Thereby, it learns x T · Z + δ + µ and sets h * ← Encpk(x T · Z + δ + µ). P1, P2 corrupted: It learns the inputs x from P1 resp. Z from P2. It runs the protocol with the inputs, and outputs (input, sid, P1, P2, x) and (input, sid, P1, P2, Z) to the ideal functionality, which makes FHmap output (result, sid, P1, P2, x T · Z + δ + µ). Let us now assume to the contrary there is such an environment E that can Definition 2. Let EXEC π,A,E resp. EXEC F ,S,E denote the random variables describing the output of environment E when interacting with an adversary A and parties P 1 , P 2 performing protocol π, resp. when interacting with a simulator S and an ideal functionality F, where only P 1 receives output. Protocol π securely realizes functionality F with one-sided simulation if 1. for any adversary A that controls P 2 there exists a simulator S such that, for any environment E the distribution of EXEC π,A,E and EXEC F ,S,E are indistinguishable, 2. and for any adversary A controlling P 1 the distribution V IEW A π,A (x, y) and V IEW A π,A (x, y ), where |y| = |y | are indistinguishable.

B PSI-SUM with Indices
In Figure 9 we give the ideal functionality for a PSI-SUM with Indices primitive. Such a primitve computes the sum of the private values associated with the intersection elements of two databases and reveals the indices present in the intersection to one party. This can be seen as an relaxed version of the Private Intersection-Sum with Cardinality primitive introduced in [57].

F P SI−Sum
Parameters: t, N ∈ N. Parties P1 and P2.

C Differential Privacy
Definition 3 ( -Differential Privacy [27]). A randomized mechanism A gives -differential privacy if for any neighboring datasets D and D , and any S ∈ Range(A): P r[A(D) = S] ≤ e P r[A(D ) = S].
One can achieve -DP by adding noise from a zero-centered Laplace distribution to the final result of the computation. The noise is calibrated with the privacy budget and the global sensitivity ∆q of the computation q: ∆q = max

C.1 An economic method to choose
We aim to provide a confidence interval for the proportion µ of individuals in the general population (or subpopulation) with a specific property. Assume a database D N and let g : D N → R be the mechanism computing the sample mean with sensitivity 1 /N. If (for privacy reasons), we add Laplace noise ν to the outcome of g, we introduce an error source. Modeling each individual as a random variable with Bernoulli distribution allows us to bound this error by the tail bound. Hence, we can define the utility by a confidence interval with accuracy T ∈ [0, 1], and confidence 1 − α for α ∈ [0, 1] The idea of DP is that an individual's expected harm (cost) of being in the database should be minor. Let E be the expected cost for an individual for being in the database (for a formal definition see [61]). Then the individual's cost of being in the computation g is (e − 1)E.
Let D j w be the j-th column vector of the matrix Z, i.e., the location data corresponding to cell tower j. Then, we define the mechanism as g(D j w ) := # individuals in j w , resulting in sensitivity 1 /w. This setup satisfies the assumption that each individual can be modeled as a Bernoulli experiment. This can be done for every cell tower, and thus covering the heatmap's area. The estimations of the expected baseline cost E = $0.01 already cover the whole heatmap's area (all cell towers).