Files
paper-how-to-use-this-techn…/research/08-privacy-enhancing-technologies.md

82 KiB
Raw Permalink Blame History

Privacy-Enhancing Technologies for Mobility Data

A technical assessment for a privacy-first alternative to raw Bluetooth MAC sniffing

Status: research memo for the PulseCast technical report. Date: 2026-11-14.

Scope. This memo assesses privacy-enhancing technologies (PETs) for a system that estimates urban footfall from Bluetooth Low Energy (BLE) and Wi-Fi observations, publishes heatmaps, and forecasts short-term demand. It assumes:

  • the pedestrian's phone is not under our control and does not run our code;
  • the sensing layer observes ephemeral radio addresses at fixed locations;
  • the product needs per-location counts at 15 min to 1 h resolution, historical aggregates for forecasting, and a public or municipal dashboard;
  • raw trajectories are not a product requirement.

The current PulseCast pilot uses PAX counters and does not sniff MAC addresses. The PET stack below is for a future BLE/Wi-Fi sensing layer that would otherwise collect raw MAC addresses. The memo separates formal guarantees (differential privacy, secure computation), syntactic privacy models (k-anonymity and its extensions), and operational controls (minimization, retention, edge aggregation). It does not treat them as interchangeable.


1. PET overview

PET What it protects Guarantee Trust assumption Main cost Fit for footfall
Central differential privacy (DP) The contribution of one privacy unit to a published aggregate (ε, δ)-DP: a formal bound on one unit's influence, independent of the adversary's auxiliary information A trusted curator holds the raw data Noise; budget accounting; governance Strong. Best utility for counts; needs a trusted aggregator
Local DP Each user's report against the curator and the world ε-DP per report, no trusted curator None for the data, but devices must run the mechanism Very high noise for sparse, high-dimensional data Weak for 15-min counts; usable for large-scale telemetry
Shuffle DP Individual reports against the server, via anonymity Amplified DP, between local and central A trusted shuffler or a mixnet Latency; shuffler operation; validation Medium. Good at scale; overkill for 8–50 sensors
k-anonymity Identity disclosure under a quasi-identifier model Syntactic: each QI combination appears at least k times Adversary's auxiliary knowledge is limited to the QIs Generalization/suppression destroys local signal Weak alone; useful as a secondary check
l-diversity / t-closeness Attribute disclosure within an equivalence class Syntactic; stronger than k-anonymity for specific attacks Known sensitive attribute and distance metric Hard to apply to high-dimensional mobility Weak alone; research/interim use
Secure aggregation Individual contributions to a server Cryptographic: server learns only the sum, below a collusion threshold Threshold of honest participants; correct protocol Communication rounds; dropout handling Good for multi-operator aggregation
Secure multi-party computation (MPC) Inputs to a joint computation Cryptographic: correctness and input privacy under a corruption model Honest majority or preprocessing assumptions Network rounds; malicious security overhead Good for cross-city queries; heavy for a pilot
Homomorphic encryption (HE) Data in computation Cryptographic: computation on ciphertexts Key holder; threshold decryption Ciphertext expansion; limited depth; key management Good for encrypted sums; not for full heatmaps
Trusted execution environment (TEE) Data in use against a privileged operator Hardware-based: confidentiality/integrity, conditional on attestation Hardware vendor and attestation chain; no side channels Attestation infrastructure; side-channel risk Good for production aggregation; not a DP substitute
Federated learning / analytics Raw data locality No privacy guarantee by itself; DP and SecAgg must be added Device-side code; participation Communication; device availability; poisoning Not applicable to passive BLE sniffing
DP synthetic data Individual records in a released dataset (ε, δ)-DP if the generator is DP Correct DP training and evaluation Utility loss; high-dimensional data is hard Good for public release, not live counts
Non-DP synthetic data Nothing formally None; empirical privacy only Generator and evaluation False sense of anonymity Do not claim anonymity
Edge aggregation, ephemeral IDs, minimization Raw data collection and retention Operational, not formal Sensor firmware/hardware; operator Firmware work; audit; calibration Essential first layer

Guarantee hierarchy. DP is the only technique in this table that gives a formal, composable, adversary-agnostic bound on the influence of one privacy unit's data on a published output. Secure computation protects data during a computation but says nothing about the output. k-anonymity and its extensions are syntactic properties that hold only under a specified quasi-identifier and background-knowledge model. Hashing, MAC randomization, and non-DP synthetic data are not privacy guarantees. A production system should compose layers: minimization and edge aggregation to avoid collecting raw data, DP to bound the output, and secure computation or a TEE to reduce trust in the aggregator. No single layer is sufficient.


2. Threat models

2.1 Privacy unit and neighboring relation

A DP guarantee is meaningless without a privacy unit and a neighboring relation. For footfall, the practical choices are:

  • Event-level: one sensor observation of one device in one time bin. This is the weakest unit; it protects a single ping, not a person.
  • Device-day: all observations of one device on one calendar day. This is the natural unit for a daily heatmap and the one this memo recommends.
  • Person-day: all observations of one person on one day. This is the strongest unit, but it is not measurable from MAC addresses: one person may carry two devices, and one device may be shared. A person-day guarantee cannot be honestly claimed from device data alone.

The choice matters. A device that is observed by six sensors in a day contributes six sensor-bin records. If the release is per sensor, the same device appears in six releases. Treating those releases as independent would undercount the privacy loss. The correct approach is to bound each device's total contribution across sensors and bins (for example, at most four sensor-bin pairs per day, analogous to the contribution bound used by Google's COVID-19 Community Mobility Reports) and to set the sensitivity of the release to that bound. Contribution bounding is not an engineering afterthought; it is the step that makes the sensitivity calculation true.

A second distinction is add/remove versus replace neighboring datasets. Add/remove (one device added or removed) gives sensitivity 1 for a count; replace (one device replaced by another) gives sensitivity 2. Most deployed systems use add/remove and should say so.

2.2 Risk categories and attacks

The Article 29 Working Party's anonymisation opinion (2014) identifies three risk categories that a release must resist: singling out, linkability, and inference. Reconstruction is a fourth, emphasized in the DP literature (Dinur and Nissim, 2003). Membership inference (Shokri et al., 2017) and differencing attacks are related risks that matter for an interactive dashboard.

Risk What the adversary does Footfall example What actually helps What does not
Singling out Isolates one individual's record in the release A cell or time bin that contains one device DP; minimum aggregation; suppression (partially) Removing names; pseudonyms
Linkability Links two records about the same person across releases or datasets Same device in Monday's and Tuesday's heatmaps; same device across two sensors Rotating identifiers; aggregation; contribution bounds; DP composition across releases Stable pseudonyms; hashed MACs
Inference Deduces a sensitive attribute from the release Home/work location, religion, health, protest participation DP bounds the influence of one person; coarsening; purpose limitation k-anonymity alone; "anonymized" labels
Reconstruction Recovers the input data from many aggregate answers Arbitrary filters on an API, differenced to isolate a person Query restrictions; budget ledger; DP composition Noise without accounting; unlimited queries
Membership inference Decides whether a specific person is in the data "Was this device in the dataset on Saturday?" DP bounds the advantage; aggregation Pseudonymization; synthetic data without DP
Differencing Subtracts two releases that differ by one person "All visitors" minus "all visitors except sensor S" Consistent noise; budget accounting; no overlapping releases Independent noise that can be averaged out
Sensor compromise Reads raw MACs at the edge Malicious or buggy sensor firmware Secure boot; no raw storage; attestation; audit DP at the aggregator; hashing after collection

2.3 Re-identification case studies

Netflix Prize (2008). Narayanan and Shmatikov linked the "anonymized" Netflix Prize ratings to public IMDb ratings and de-anonymized a large fraction of subscribers, with up to 99% of records recovered under their attack for users with enough ratings. The dataset was high-dimensional and sparse, which made each user's rating pattern nearly unique. Removing names did not make the data anonymous. The lesson for mobility is direct: a trajectory is a high-dimensional, sparse behavioral signature, and auxiliary data (social media, check-ins, transit records) is abundant.

AOL search logs (2006). AOL released search logs with pseudonymous user IDs. The New York Times re-identified user 4417749 from the content of the queries. The lesson: pseudonyms plus rich behavior are not anonymization; the sensitivity is in the behavior, not the identifier.

NYC taxi data (2014). The New York City Taxi and Limousine Commission released 173 million trip records with medallion and driver-license numbers pseudonymized. Anthony Tockar showed that a medallion number, a timestamp, and a public photo of a celebrity entering a cab were enough to identify trips, including pickup and drop-off locations and tips. Pseudonymization was not enough; the linkage came from public information, not from reversing the hash. The lesson: pseudonymous IDs plus spatio-temporal data plus public information equals re-identification; a single auxiliary point can be enough.

Mobility uniqueness (2013, 2015). de Montjoye et al. (2013, 2015) showed that four spatio-temporal points uniquely identify 95% of 1.5 million individuals in a mobile-phone dataset at hourly and cell-tower resolution, and that four points uniquely re-identify 90% of individuals in credit-card metadata. This is the strongest empirical argument against k-anonymity as a primary guarantee for mobility: the data is inherently high-dimensional, and generalization to achieve k-anonymity destroys the local, peaked signal that footfall analysis needs.

Google COVID-19 Community Mobility Reports (2020). Google published a production mobility release using DP. The published description reports Laplace noise at ε = 0.11 per count at the coarser geographic levels (0.22 at the finest), a contribution bound of four category-location pairs per user per day per geographic level, a maximum daily contribution of ε = 1.76, δ = 0, no regions smaller than 3 km², and a post-noise threshold of 100 contributing users. This is a useful existence proof: a city-scale mobility release can use DP, but at coarse spatial and temporal resolution and with an explicit utility cost. It is not a template for a 15-minute, 100-metre public heatmap.

Apple/Google Exposure Notification (2020). The Exposure Notification framework uses rolling proximity identifiers that change about every 15 minutes, on-device matching, and no central storage of raw identifiers. It is a strong example of an architecture that avoids collecting the sensitive data in the first place. It does not transfer to passive BLE sniffing: in Exposure Notification, the phone runs the protocol; in our system, the pedestrian's phone does not.

Wi-Fi and BLE tracking. MAC address randomization is not sufficient. Vanhoef et al. showed that probe-request content, information elements, timing, and sequence numbers can fingerprint devices across MAC rotations, and that some devices leak their real MAC address. Franklin et al. showed that 802.11 driver fingerprints can identify devices passively. Martin et al. showed that Apple's BLE Continuity protocol leaks identifying fields and that predictable sequence numbers allow tracking across address rotations; in some macOS versions, a bug broadcast the public MAC address entirely. The design implication is not "randomize better"; it is "do not collect raw MACs."

2.4 What DP does and does not protect

DP protects the influence of one privacy unit on the output. The bound holds regardless of what auxiliary information the adversary has about the other records; that is what "adversary-agnostic" means. It does not protect:

  • population-level facts that are true regardless of any one person;
  • inferences that an adversary can make from external data without using the release;
  • a sensor or edge node that retains raw MACs before aggregation;
  • the utility of the release;
  • the legal question of whether the output is "anonymous" under GDPR.

A DP release can still be harmful if the privacy unit is too coarse, the contribution bound is wrong, the budget is not enforced, or the released statistic is itself sensitive at the population level (for example, a cell that reveals a protest or a clinic visit even with no individual identified). DP is a necessary component of a privacy argument, not the whole argument.


3. Differential privacy

3.1 Definition and semantics

A randomized mechanism M is (ε, δ)-differentially private if for all neighboring datasets D and D' that differ in one privacy unit, and for all output sets S:

Pr[M(D) ∈ S] ≤ e^ε · Pr[M(D') ∈ S] + δ.

ε = 0, δ = 0 is exact privacy; δ = 0 is pure DP; δ > 0 is approximate DP. The guarantee is with respect to the neighboring relation and the privacy unit, not with respect to a particular adversary or auxiliary dataset.

Interpretation:

  • ε bounds the multiplicative change in the probability of any output when one privacy unit's data is added or removed. ε = 1 permits a change of factor e ≈ 2.72; ε = 0.1 permits about 11%; ε = 10 permits a factor of 22,026.
  • Under pure DP, the optimal membership-inference advantage is at most (e^ε − 1)/(e^ε + 1). This is about 46% at ε = 1, 5% at ε = 0.1, and 0.5% at ε = 0.01. Approximate DP relaxes this bound by a δ-dependent term. These are worst-case bounds, not predictions of a specific attack, but they show why "ε = 1" is not a mild guarantee.
  • δ is the probability of a catastrophic failure of the bound. It should be much smaller than 1/n. A common conservative convention is δ ≤ 1/n²; for n = 10,000 devices, that is 1e-8. If δ = 1e-6, the expected number of affected individuals under the failure event is small, but the choice should be justified, not defaulted.

There is no universal "safe" ε. The common guidance (Dwork and Roth, 2014; Dwork, Kohli, and Mulligan, 2019) that ε around 1 is a reasonable starting point and that ε above 10 is hard to justify is a heuristic, not a theorem. NIST SP 800-226 explicitly says that ε alone is not a sufficient descriptor of a DP guarantee; the evaluation must include the privacy unit, the neighboring relation, the mechanism, the composition, the data, and the threat model. A public release should publish all of these, not just a number.

3.2 Mechanisms for counts

For a function f with L1 sensitivity Δf, the Laplace mechanism releases f(D) + Lap(Δf/ε). For a count with add/remove neighboring data, Δf = 1, so the noise scale is 1/ε. The noise standard deviation is √2/ε, and the 95% confidence interval is approximately ±3/ε.

For a function with L2 sensitivity Δ₂f, the Gaussian mechanism adds N(0, σ²) with

σ = Δ₂f · sqrt(2 ln(1.25/δ)) / ε        (for 0 < ε < 1).

Using the classical calibration at the ε = 1 boundary, δ = 1e-6 gives σ ≈ 5.3 · Δ₂f, and the 95% interval is about ±10.4 · Δ₂f; the exact guarantee should be computed with a modern accountant rather than read off this approximation. The Gaussian mechanism is worse than Laplace for a single count but composes better over many queries. The formula above is conservative; analytical calibration (Balle and Wang, 2018) and Rényi/zCDP accounting can reduce the noise. For integer counts, a discrete Gaussian avoids floating-point rounding leaks; a vetted library should be used rather than a hand-rolled Laplace sampler.

The histogram mechanism is the key utility fact for heatmaps. If each device contributes to at most one cell of a fixed spatial grid in a release, the L1 sensitivity of the entire histogram vector is 1, not the number of cells. Adding Lap(1/ε) to every cell satisfies ε-DP for the whole histogram, and the number of cells does not multiply the budget. This is why a 1,000-cell daily heatmap is feasible while 1,000 separate per-cell queries at ε/1000 each are not. The caveats are:

  • the grid must be fixed in advance; a data-dependent grid requires a different analysis;
  • each device must be counted at most once (deduplicate within the release window);
  • if a device can contribute to k cells, sensitivity is k, and the noise scale is k/ε;
  • if the release is a time series of T bins and a device can appear in every bin, sensitivity is T unless contributions are bounded. This is the central difficulty for 15-minute heatmaps.

For range queries (rectangles, arbitrary map filters), the matrix mechanism and hierarchical decompositions (quadtrees, PrivTree) can answer a workload with less noise than independent per-cell perturbation (Li et al., 2015; Cormode et al., 2012; Zhang et al., 2016). Constrained inference (for example, non-negativity and consistency across a hierarchy) is post-processing and does not consume budget, but it can amplify bias as well as reduce variance (Hay et al., 2010).

3.3 Local, central, and shuffle models

Model Who must be trusted Utility for counts Typical examples Fit
Central DP A curator that sees raw data Best; error scales like 1/(εn) for a bounded count Census TopDown (Abowd et al., 2022), Google Mobility Reports, OpenDP Strong for a city-owned aggregator
Local DP No curator; each device randomizes Worst; error scales like 1/(ε√n) for a bounded mean, and worse in high dimension RAPPOR, Apple's count-mean sketch Weak for sparse 15-min footfall
Shuffle DP A shuffler or mixnet; not the analyst Between local and central; amplification by anonymity Prochlo, Google's shuffle deployments, Apple's distributed aggregation Good at large scale; complex at city scale

The local-versus-central gap is not a constant factor. For bounded means, and for the relative error of counts, local DP's error decreases as 1/√n while central DP's decreases as 1/n; local DP needs roughly quadratically more users for the same accuracy (Duchi, Jordan, and Wainwright, 2013). In high-dimensional settings the gap is worse. A 15-minute footfall bin with 14 devices per sensor is exactly the regime where local DP fails: randomized response on a count with that few contributors produces noise larger than the signal. Local DP is appropriate when the number of contributors per release is large (thousands), or when the query is low-dimensional and the privacy requirement is modest.

The shuffle model recovers some of the central utility by hiding individual messages among many. If each user sends a locally randomized message and a trusted shuffler permutes the messages and strips identities, the effective privacy loss can be amplified from the local ε toward the central regime; in the small-ε, large-n regime the shuffled guarantee is on the order of ε/√n for suitable mechanisms, and frequency estimation approaches the central rate (Erlingsson et al., 2019; Feldman, McMillan, and Talwar, 2021). The guarantee depends on the mechanism, the number of messages, and the shuffler's honesty. Single-message shuffle has strong lower bounds and cannot match central DP for every task; multi-message shuffle is more powerful but requires more communication (Ghazi et al., 2021). A cryptographic mixnet can replace the trusted shuffler, at the cost of latency and operational complexity. For a small city with 8–50 sensors, the shuffle model adds machinery without solving the binding problem, which is the sparse count, not the trust in the aggregator.

3.4 Composition and the privacy budget

DP composes. If a mechanism is applied k times adaptively to the same data, the basic bound is (kε, kδ). Advanced composition gives approximately

( ε · sqrt(2k ln(1/δ')) + kε(e^ε − 1),  kδ + δ' ).

The optimal composition theorem (Kairouz, Oh, and Viswanath, 2015) characterizes the exact degradation. Rényi DP (Mironov, 2017), zero-concentrated DP (Bun and Steinke, 2016), and Gaussian DP (Dong, Roth, and Su, 2022) give tighter accounting for many queries and are the right tools for a production system. The choice of accounting method must be consistent across the system; mixing bounds from different frameworks without care can understate the total.

Two further properties matter for a deployed system. Post-processing immunity: any function of a DP output is DP with the same parameters, so forecasting, smoothing, and visualization that use only DP aggregates do not consume additional budget. Group privacy: protecting a group of k devices (or k events from one device) costs roughly kε under pure DP; the linear degradation is one reason contribution bounding and a device-day unit matter, and one reason repeated releases are dangerous. Neither property removes the need for a budget ledger.

Two structural rules matter more than the exact bound:

  • Sequential composition applies when the same data is queried repeatedly. The budget adds.
  • Parallel composition applies when the queries touch disjoint subsets of the data. The budget is the maximum, not the sum.

For a heatmap, spatial cells in the same time bin are disjoint if each device is counted once, so a single histogram release is one query with sensitivity 1. Time bins are not disjoint for a device that appears in several bins; a device that visits a location at 09:00 and 17:00 contributes to two bins. Unless the release deduplicates per device per window, the time series composes sequentially.

A privacy budget is a ledger, not a suggestion. It must include every release, every query, model selection, hyperparameter tuning, retries, failed queries, and internal dashboards. If the same data is queried twice with independent noise, the privacy loss accumulates; under basic composition it doubles. Averaging repeated queries reduces the noise but not the privacy loss. The budget must be attached to a privacy unit and a time window. "ε = 1" without a unit and a window is not a guarantee.

A worked composition example shows why release cadence dominates the design. Assume 96 fifteen-minute bins per day, 365 days per year, and advanced composition with δ' = 1e-5:

Release cadence Releases/year ε per release Annual ε (advanced) Comment
Every 15 min 35,040 0.01 ≈ 12.5 Already a large annual budget
Every 15 min 35,040 0.1 ≈ 458 Unusable
Hourly 8,760 0.1 ≈ 137 Unusable
Daily 365 0.1 ≈ 13 High but arguable
Weekly 52 0.1 ≈ 4.0 Defensible

The arithmetic is not a measured result, but the conclusion is robust for a small city with the counts assumed here: a live 15-minute public dashboard cannot have a meaningful annual DP budget for a device-day privacy unit. The release cadence must be part of the privacy design, not an afterthought. A system that publishes every 15 minutes and claims "ε = 0.1" per release is either not accounting for composition or is choosing an annual budget in the hundreds.

3.5 Utility loss for counts and heatmaps

For a single count with Laplace noise at ε = 1, the 95% interval is about ±3, independent of the true count. The relative error therefore depends entirely on the count:

True count c 95% interval (ε = 1) Relative half-width
1 ±3.0 ±300%
5 ±3.0 ±60%
10 ±3.0 ±30%
50 ±3.0 ±6%
100 ±3.0 ±3%
1,000 ±3.0 ±0.3%

At ε = 0.1, multiply the interval by 10; at ε = 10, divide by 10. The Gaussian mechanism at ε = 1, δ = 1e-6 has a 95% interval of about ±10.4 for sensitivity 1, which is worse for a single count but better when many queries compose.

This table is the core utility argument for footfall. A cell with 1–5 devices is not usable at ε ≤ 1. A cell with 100 devices is usable at ε = 1 and marginal at ε = 0.1. A daily total per sensor with ~1,000 device-visits is usable at ε = 0.1. The design question is therefore not "what is the best DP mechanism?" but "what spatial and temporal aggregation gives each released cell enough counts to survive the noise?"

Illustrative sizing for a small city. Assume 8 sensors, about 14 devices per sensor per 15-minute bin (consistent with the observed density index scale in the PulseCast pilot, though the true unique-device count is unknown), a 10-cell heatmap, Laplace noise, and advanced composition with δ' = 1e-5:

Release Releases/year Count per cell ε/release 95% interval Annual ε Verdict
15-min per sensor 35,040 14 0.1 ±30 (±214%) ≈ 458 Unusable
Hourly per sensor 8,760 56 0.1 ±30 (±54%) ≈ 137 Unusable
Daily per sensor 365 1,344 0.1 ±30 (±2.2%) ≈ 13 Borderline
Daily 10-cell heatmap 365 1,075 0.1 ±30 (±2.8%) ≈ 13 Borderline
Weekly 10-cell heatmap 52 7,525 0.1 ±30 (±0.4%) ≈ 4 Viable

These are design calculations, not measurements. They assume independent Laplace noise, a fixed grid, one count per device per cell, and the advanced-composition bound. They show the trade-off that matters: fine-grained public heatmaps and strong DP for a device-day unit are incompatible at small-city scale. The honest options are coarser releases, a larger budget with a public justification, or a trusted curator that publishes a one-shot aggregate rather than an interactive dashboard.

Utility loss is not only variance. DP noise can produce negative counts, false hotspots, and spurious peaks; constrained inference and smoothing can repair some of this, but they can also bias the result. Forecasting models trained on noisy aggregates inherit the noise; the model's error may increase, and the increase must be measured, not assumed. A paper that reports a WAPE on raw counts and then claims the same WAPE under DP is making an unverified claim.

3.6 Implementations: Google, Apple, OpenDP

Google. Google's open-source DP library (C++, Java, Go) implements Laplace and Gaussian mechanisms, bounded count/sum/mean, quantiles, selection, and partition selection, with contribution bounding and accounting. PipelineDP and Privacy on Beam provide pipeline-level DP. Google's COVID-19 Community Mobility Reports used the C++ library with Laplace noise, ε = 0.11 per count at the coarser levels (0.22 at the finest), a contribution bound of four category-location pairs per user per day per geographic level, a maximum daily ε = 1.76, and δ = 0; the release also applied a minimum region size of 3 km² and a post-noise threshold of 100 users. Google's Privacy Sandbox Private Aggregation API uses a different architecture: browser worklets contribute encrypted reports, a TEE-backed aggregation service decrypts and sums them, and noise is added before release. The trust model is a TEE plus DP, not a trusted curator alone.

Apple. Apple's local DP deployment uses on-device privatization with count-mean sketches and Hadamard count-mean sketches, designed for large domains and limited communication. The 2017 "Learning with Privacy at Scale" paper describes the client-side algorithms and the server-side estimation; Apple reports task-specific ε values rather than a single global value. Apple's Exposure Notification framework uses rolling proximity identifiers and on-device matching, a different architecture that avoids central raw identifiers. Apple's Private Cloud Compute is a TEE-based cloud architecture with attested, reproducible node software and a transparency log; it is relevant to the "trusted aggregator" layer, not a substitute for DP.

OpenDP. OpenDP is an open-source library with a Rust core and Python bindings. It provides transformations and measurements, sequential and parallel composition, privacy filters that stop a computation when the budget would be exceeded, and contribution-bounding primitives. It is used by DP Creator and SmartNoise. Its guarantee is only as good as the caller's use: the library can enforce composition and sensitivity for the queries it understands, but it cannot choose the privacy unit, the contribution bound, or the release cadence for the analyst. A common failure mode is to use a DP library for the noise but compute the sensitivity by hand and get it wrong.

Implementation Model Strengths Limitations
Google DP library Central Mature; count/sum/mean/quantiles; contribution bounding; used in production mobility C++/Java/Go focus; pipeline integration requires care
OpenDP Central Open source; Rust/Python; composition and privacy filters; auditable Smaller mechanism set; caller must define the threat model
Apple CMS/HCMS Local On-device; large domains; production deployment at scale Local-DP utility; task-specific ε; not for sparse counts
Google Private Aggregation Shuffle/TEE Browser-scale; encrypted reports; TEE aggregation TEE trust; complex; not a general DP query system

3.7 What ε should a municipal footfall release use?

There is no theorem that maps ε to a legal or ethical standard. A defensible process is:

  1. Define the privacy unit (device-day) and the contribution bound (for example, one count per sensor per 15-minute bin and at most four sensor-bin pairs per day).
  2. Choose a release cadence that gives each cell enough counts (daily or weekly, not 15-minute).
  3. Choose a total annual budget in the range of roughly 1–10 for public releases, with a written justification. Below 1 is strong; above 10 is hard to defend for public data. This is a policy judgment, not a mathematical result.
  4. Publish the mechanism, ε, δ, the privacy unit, the contribution bound, the release cadence, and the utility metrics. Do not publish only "ε = 1".
  5. Have the data protection authority or an independent reviewer check the accounting and the utility claims.

The "expose your epsilons" argument (Dwork, Kohli, and Mulligan, 2019) is the right norm: a DP claim without its parameters and threat model is not verifiable. NIST SP 800-226 provides a structured evaluation checklist; it does not certify a particular ε.


4. k-anonymity, l-diversity, and t-closeness

4.1 Definitions

Let QI be a set of quasi-identifiers (age, postal code, timestamp, location) that can be linked to external data. A release is k-anonymous if every combination of QI values appears in at least k records (Sweeney, 2002; Samarati and Sweeney, 1998). The classic implementation generalizes QI values (for example, age 34 → 30–39, a 100 m cell → a 500 m cell) and suppresses records that cannot be generalized.

l-diversity strengthens k-anonymity by requiring each equivalence class to contain at least l distinct values of a sensitive attribute (Machanavajjhala et al., 2006). t-closeness requires the earth mover's distance between the sensitive-attribute distribution in each class and the global distribution to be at most t (Li, Li, and Venkatasubramanian, 2007). Both are attempts to prevent attribute disclosure, not just identity disclosure.

4.2 Why k-anonymity alone is weak

  • Homogeneity attack. If all k records in a class share the same sensitive value, the class reveals that value even though no individual is singled out. k-anonymity does not prevent this; l-diversity does, in principle.
  • Background-knowledge attack. The adversary may know that the target is not in a class, or may know additional attributes that narrow the class. k-anonymity's guarantee is only with respect to the quasi-identifiers it models.
  • Composition attack. Two independently k-anonymous releases can be joined to re-identify individuals (Ganta, Thompson, and Kumar, 2008). k-anonymity does not compose; the privacy loss from multiple releases is not bounded by k.
  • High-dimensional uniqueness. Mobility traces are high-dimensional and sparse. de Montjoye et al. (2013) show that four spatio-temporal points uniquely identify 95% of individuals in a large mobile-phone dataset. Achieving k = 20 on such data would likely require generalization so coarse that the local footfall signal disappears.
  • Suppression leakage. Suppressing cells with counts below k reveals that those cells have between 1 and k−1 devices. Complementary suppression can reduce this, but it is a patch, not a guarantee.
  • Computational hardness. Optimal k-anonymization is NP-hard (Meyerson and Williams, 2004); practical algorithms use heuristics whose privacy properties are hard to verify.

l-diversity addresses homogeneity but not skewness or similarity attacks: a class can have l distinct values that are all close to the sensitive value, or the overall distribution can be skewed. t-closeness addresses the distribution but requires a sensitive attribute, a distance metric, and a global distribution; it is difficult to apply to continuous, high-dimensional mobility data, and it still does not compose.

4.3 Spatial and temporal generalization for mobility

The standard tools are grid coarsening, time binning, and cloaking. Gruteser and Grunwald (2003) introduced spatial and temporal cloaking for location-based services; Casper (Mokbel, Chow, and Aref, 2006) generalized the idea with a privacy-aware query processor. For footfall, these techniques have a direct utility cost:

  • Coarsening a 100 m grid to 500 m merges distinct storefronts and sensors; the heatmap no longer identifies the location that matters.
  • Binning 15 minutes to 1 hour hides the lunch and evening peaks that drive staffing.
  • Cloaking a trajectory to a region and a time window destroys the sequence information that makes mobility data useful for forecasting.

The practical result is that k-anonymity for mobility is either weak (small k, high uniqueness) or useless (large k, no local signal). It is not a good primary guarantee for a public footfall API.

4.4 Practical thresholds

Common practice is not a guarantee:

  • k = 5 is common in health data and is generally considered weak for public release.
  • k = 10–20 is a common public-release range; the choice is policy, not derived from a threat model.
  • Google's COVID-19 Community Mobility Reports used a post-noise threshold of 100 contributing users, but that is a DP release with a threshold, not a k-anonymity guarantee. The threshold is a reliability and privacy filter on top of DP, not a substitute for it.
  • l = 2–3 and t = 0.2 appear in the literature as illustrative choices; they are not universal standards.

NIST SP 800-188 treats k-anonymity as one technique among several and emphasizes that de-identification must be evaluated against a threat model, with re-identification testing and governance. It does not endorse a universal k. The UK ICO's anonymisation code makes a similar point: anonymisation is a risk assessment, not a checkbox.

Recommendation. Do not use k-anonymity as the primary privacy guarantee for a public footfall release. Use DP for the published aggregates. If k-anonymity is used at all, use it as a secondary check on internal data or as a sanity check on cell counts, document the quasi-identifiers and the adversary, and do not claim that it composes or that it prevents attribute inference.


5. Secure aggregation, MPC, federated learning, HE, and TEEs

5.1 Secure aggregation

Secure aggregation lets a server compute the sum of client updates without seeing any individual update. In the Bonawitz et al. (2017) protocol, each client masks its update with pairwise random masks that cancel in the sum, secret-shares the mask with the other clients, and the server reconstructs the sum even if some clients drop out. The server learns the sum, not the inputs, provided it does not collude with enough clients to reconstruct the masks.

  • Guarantee: cryptographic confidentiality of individual contributions against the server and colluding clients below the threshold. It does not protect the sum; if the sum is sensitive (a cell with one device), DP is still required. It does not prevent a malicious client from poisoning the sum; robust aggregation is a separate problem.
  • Cost: communication grows with the number of participants and the dropout threshold; the protocol needs multiple rounds and secret sharing. It is practical for hundreds to thousands of clients per round, not for per-request queries.
  • Fit: good when multiple operators (city, transit authority, private sensor vendors) want to aggregate counts without revealing their raw data to each other. For a single city-owned aggregator, it adds complexity without removing the main trust assumption.

5.2 Secure multi-party computation

MPC computes an arbitrary function over private inputs (Yao, 1986; Goldreich, Micali, and Wigderson, 1987). Secret-sharing-based protocols are efficient for addition and counts; garbled circuits are efficient for comparisons and branching; SPDZ-style protocols provide malicious security with preprocessing (Damgård et al., 2012). The guarantee depends on the corruption model: semi-honest (parties follow the protocol) versus malicious (parties may deviate), and honest-majority versus dishonest-majority.

  • Guarantee: correctness and input privacy, conditional on the corruption model and the protocol assumptions. MPC does not provide DP; the output can still leak.
  • Cost: network rounds and bandwidth; malicious security adds substantial overhead; cross-city WAN latency dominates.
  • Fit: joint cross-city forecasting or benchmarking without sharing raw counts. It is overkill for a single-city pilot with a trusted aggregator, and it does not solve the sparse-cell utility problem.

5.3 Homomorphic encryption

Additive HE (for example, Paillier, 1999) supports encrypted sums: each party encrypts its count, the aggregator adds ciphertexts and multiplies them by plaintext weights, and the key holder decrypts the total. Fully homomorphic encryption (Gentry, 2009; BGV/BFV; CKKS for approximate arithmetic, Cheon et al., 2017) supports arbitrary computation but is orders of magnitude slower, has limited multiplicative depth, and requires bootstrapping or large parameters.

  • Guarantee: confidentiality of inputs during computation; the output is decryptable by the key holder. HE does not provide DP, and the output can leak. Threshold decryption distributes the key, but collusion and key management remain.
  • Cost: ciphertext expansion, key management, limited operations, and a much higher computational cost than plaintext aggregation. Additive HE is practical for counts; FHE is not yet practical for full heatmap smoothing or model training at city scale.
  • Fit: encrypted aggregation of counts across mutually distrustful parties. It is a complement to DP, not a replacement.

5.4 Trusted execution environments

A TEE provides isolated execution with attestation: Intel SGX, AMD SEV-SNP, ARM Confidential Compute Architecture. The code and data are protected from the host operating system and the cloud operator, conditional on the hardware and the attestation chain.

  • Guarantee: confidentiality and integrity against a privileged operator, subject to the TEE's threat model. It is not a mathematical guarantee against a malicious hardware vendor, a physical attacker, or side-channel leakage. SGX in particular has a history of side-channel and fault attacks (Van Bulck et al., 2018; Kocher et al., 2020) and a limited enclave memory.
  • Cost: attestation infrastructure, reproducible builds, key management, and operational complexity. Performance is near-native for many workloads, but I/O and memory limits matter.
  • Fit: a TEE-backed aggregation service for a multi-tenant production system, especially when the aggregator is a cloud provider rather than the city. Google's Private Aggregation API and Apple's Private Cloud Compute are production examples. A TEE does not replace DP: it protects the data in use, while DP protects the output.

5.5 Federated learning and federated analytics

Federated learning trains a model across devices without centralizing raw data. FedAvg aggregates local updates (McMahan et al., 2017); secure aggregation hides individual updates; DP-FedAvg adds clipping and noise at the user level (McMahan et al., 2018). Federated analytics computes aggregates on devices and returns only the aggregates.

  • FL is not a privacy guarantee. Gradients can leak training data (Zhu, Liu, and Han, 2019), membership inference can succeed (Shokri et al., 2017), and the server sees the updates unless SecAgg is used. FL must be combined with DP and SecAgg to make a privacy claim.
  • Federated analytics requires device-side code. It works when the phone runs the app and the app can compute the aggregate. It does not work for passive BLE sniffing, where the pedestrian's phone is not participating. In our architecture, "on-device" means the sensor or edge node, not the pedestrian's phone.
  • Fit: relevant only if PulseCast ships a companion app or partners with a transit app. For the sensing layer described here, FL is not applicable, and claiming it would be misleading.

5.6 Trade-off summary

PET What it removes What it does not remove Cost Best use
Central DP Trust in the analyst; bounds output leakage Trust in the curator Low compute; governance City-owned aggregator; published aggregates
Local DP Trust in the curator Utility loss; device compromise Low compute; high noise Large-scale telemetry
Shuffle DP Trust in the server (with a shuffler) Trust in the shuffler/mixnet; validation Latency; infrastructure Large-scale analytics
Secure aggregation Server's view of individual updates Sum leakage; poisoning; collusion Communication Multi-operator aggregation
MPC Parties' view of each other's inputs Output leakage; corruption assumptions Network rounds Cross-city queries
HE Computation on plaintext Output leakage; key management Compute; ciphertext size Encrypted sums
TEE Cloud operator's view of data in use Side channels; vendor trust; output leakage Attestation; operations Production aggregation
FL Raw data centralization Gradient leakage; membership inference Device coordination App-based sensing

The composition rule is simple: use the weakest trust assumption that the deployment can support, and add DP at the output regardless. For a city-owned pilot, central DP is sufficient and honest. For a multi-operator production system, add SecAgg or a TEE, but keep DP as the output guarantee.


6. Synthetic data for mobility

6.1 Why synthetic data

Synthetic data can support public release, model development, scenario simulation, and cross-city sharing without publishing raw records. The main families are:

  • Statistical synthesis: independent sampling, iterative proportional fitting, Bayesian networks (PrivBayes; Zhang et al., 2017), and marginal-based methods (AIM; McKenna et al., 2022).
  • Deep generative models: GANs, VAEs, and diffusion models, including DP variants (DP-GAN; Xie et al., 2018; PATE-GAN; Jordon, Yoon, and van der Schaar, 2019).
  • Mobility-specific generators: sequence models and GANs for trajectories (MoveSim; Feng et al., 2020), and flow models such as Deep Gravity (Simini et al., 2021).
  • Agent-based simulation: activity-based travel demand models that generate plausible daily schedules from population and land-use data.

These are not equivalent. A synthetic count table (sensor × time) is low-dimensional and relatively easy to synthesize with DP. A synthetic trajectory dataset is high-dimensional, sparse, and much harder to protect.

6.2 Fidelity metrics

There is no single fidelity score. A credible evaluation reports several:

Dimension Metric What it checks
Marginal distributions Kolmogorov–Smirnov, total variation, chi-square Whether each column's distribution is preserved
Correlations Pairwise correlation difference, mutual information Whether dependencies survive
Predictive utility Train-on-synthetic, test-on-real (TSTR); propensity mean squared error (pMSE) Whether the synthetic data is useful for the downstream task
Coverage Precision/recall, density, discriminator AUC Whether rare modes are represented or collapsed
Mobility-specific Trip-length distribution, origin-destination matrix similarity, radius of gyration, temporal profile, unique locations Whether the synthetic data looks like mobility, not just like a table

For a footfall count table, the relevant metrics are the hourly/weekly profile, the spatial correlation between sensors, the weather/holiday response, and the forecast error of a model trained on synthetic data. For a trajectory dataset, the relevant metrics are trip lengths, OD flows, radius of gyration, and the distribution of dwell times. Reporting only a discriminator AUC is not enough; a synthetic dataset can fool a discriminator and still leak.

6.3 Privacy metrics

Formal. If the generator is (ε, δ)-DP, then the synthetic dataset is (ε, δ)-DP by post-processing, and any model trained on it is also DP. This is the only formal guarantee. A non-DP generator has no formal guarantee, regardless of how realistic the output looks.

Empirical. Privacy is evaluated with attacks:

  • Membership inference: can an adversary tell whether a target record was in the training data? Report AUC or advantage over a baseline (Shokri et al., 2017; van Breugel et al., 2023).
  • Attribute inference: can an adversary infer a sensitive attribute from the synthetic data plus auxiliary knowledge?
  • Singling out: can an adversary isolate a unique record?
  • Linkability: can an adversary link a synthetic record to a real record or to another dataset?
  • Distance to closest record (DCR) and nearest-neighbor distance ratio (NNDR): heuristics for memorization. A small DCR suggests the generator copied a training record; a large DCR does not prove privacy.
  • Anonymeter: a framework that quantifies singling out, linkability, and inference risk for synthetic tabular data, aligned with the GDPR risk categories (Giomi et al., 2023).

The empirical results must be compared with a baseline (random guessing, or a non-private synthetic dataset) and reported with confidence intervals. A single attack with a low success rate does not prove privacy; a single attack with a high success rate disproves it.

6.4 Risks

  • Synthetic data is not automatically anonymous. Stadler, Oprisanu, and Troncoso (2022) evaluated a range of generative models and found that synthetic data either fails to prevent inference attacks or fails to retain utility; the privacy-utility trade-off is unpredictable. The paper's title, "Anonymisation Groundhog Day," is the right warning: the same claims recur without the guarantees.
  • Memorization. GANs and diffusion models can reproduce rare training records, especially with small datasets or overfitting. DCR is a useful screen but not a proof.
  • Attribute inference. Even if no record is copied, the synthetic data can preserve correlations that reveal sensitive attributes (for example, a rare diagnosis correlated with a location).
  • Mobility-specific rare events. A VIP's commute, a protest, a clinic visit, or a night-shift pattern may be rare enough to be memorized or inferred. Aggregation and DP are essential.
  • Privacy washing. A vendor may call a dataset "synthetic" and imply anonymity without a DP guarantee or an attack evaluation. Do not repeat that claim.

6.5 Fit for footfall

Synthetic data is a good fit for public release and model development, not for the live dashboard:

  • A DP-synthesized daily count table can be released for research and reproducibility, with a formal guarantee and an Anonymeter evaluation.
  • A synthetic trajectory dataset should be avoided unless there is a clear need and a DP generator; the risk is high and the utility is hard to validate.
  • For forecasting, train on DP aggregates rather than synthetic raw trajectories. Synthetic data can augment rare scenarios, but the model must be validated on real aggregates, and the evaluation must report the noise level.

7.1 Architecture

Pedestrian devices
  │  BLE / Wi-Fi advertisements with ephemeral addresses
  ▼
Sensor / edge node
  │  1. Count unique ephemeral addresses per time bin
  │  2. Rotate a secret salt per bin; destroy it after the bin
  │  3. Never write raw MACs, RSSI, probe requests, or sequences
  │  4. Emit only (sensor_id, bin_start, count)
  ▼
Edge aggregator (city-owned in the pilot)
  │  5. Enforce contribution bounds across sensors and bins
  │  6. Add DP noise (Laplace for single releases; Gaussian/RDP for many)
  │  7. Maintain a privacy budget ledger
  ▼
Aggregate store (counts only)
  │  8. Train forecasting models on DP aggregates
  │  9. No raw trajectories; no per-device records
  ▼
Dashboard / API
  │ 10. Fixed grid and time bins; no arbitrary filters
  │ 11. Post-processing: smoothing, constrained inference, visualization
  │ 12. Publish the budget, mechanism, and utility metrics

The design principle is collect less, aggregate early, publish with a bound. The sensor is the privacy boundary: if raw MACs never leave the sensor, and the firmware is not compromised, the aggregator cannot leak them. The aggregator is the trust boundary: if it is city-owned and audited, central DP is realistic. The dashboard is the attack surface: if it allows arbitrary queries, even a DP release can be differenced; a fixed release schedule is safer than an interactive query API.

7.2 Layer-by-layer guarantees

Layer Mechanism Guarantee Trust assumption Failure mode
Capture Count unique ephemeral addresses; rotating salt; no raw storage Operational: no raw MAC retention Sensor firmware and hardware Compromised sensor; firmware bug; physical access
Edge aggregation Sum counts; drop identifiers; contribution bounds Architectural: only counts leave Edge operator Small counts; cross-bin linkage
Central DP Laplace/Gaussian; OpenDP; budget ledger Formal: (ε, δ)-DP for each release Aggregator is trusted and correct Wrong sensitivity; budget overrun; implementation bug
Query restrictions Fixed grid/time bins; no raw exports; rate limits Operational: reduces attack surface API operator Differencing through allowed queries; metadata leaks
Secure aggregation / TEE (production) Encrypted aggregation; attestation Cryptographic/hardware: confidentiality against the server/cloud Threshold or hardware vendor Collusion; side channels; attestation bypass
Forecasting Train on DP aggregates; post-processing DP inherited from the aggregates Model pipeline Noise propagation; overfitting to noise; utility loss
Synthetic data (optional) DP synthesis; Anonymeter evaluation DP if the generator is DP Synthesis pipeline Utility loss; memorization if not DP
Governance DPIA; transparency; audit; retention Accountability, not a technical guarantee Institution Policy drift; insider access; scope creep

7.3 On-device processing, minimization, and identifier hygiene

The cheapest privacy control is not collecting the data. For a passive sensing layer, this means the sensor, not the cloud, is where the privacy boundary sits.

On-device means the sensor or edge node. The pedestrian's phone does not run our code, so "on-device processing" cannot mean federated learning on the phone. It means the sensor counts locally and emits only a count. This is a weaker architecture than a participant app, but it is the only one available for passive BLE/Wi-Fi sensing.

Data minimization. Collect only what the product needs: a count per sensor per time bin. Do not collect or retain raw MAC addresses, RSSI time series, probe-request payloads, sequence numbers, or device fingerprints. Apply purpose limitation (footfall analysis for urban operations, not law enforcement or advertising) and storage limitation (aggregates retained for a defined period, raw data never stored). These are GDPR Article 5 principles, but they are also good engineering: data that does not exist cannot leak.

Ephemeral identifiers. BLE devices that support privacy use resolvable private addresses that typically rotate about every 15 minutes; many Wi-Fi devices randomize MAC addresses per network. These are device-side mitigations, not guarantees. Vanhoef et al. (2016), Franklin et al. (2006), and Martin et al. (2019) show that fingerprinting, probe-request content, sequence numbers, and protocol bugs can link devices across rotations. The sensor should treat the address as an ephemeral token, count unique tokens within a bin, and never store the token.

Rotating salts. If the sensor hashes the ephemeral address before counting, the salt determines linkability. A secret random salt per 15-minute bin, destroyed after the bin, prevents cross-bin linkage but also prevents unique daily counts. A daily salt enables unique daily visitors but allows linkage within the day. The rotation period is a privacy/utility knob and should be documented. Hashing without a salt is not anonymization: the MAC space is 2^48, and a known OUI prefix reduces the search space to about 2^24, which is trivial to brute-force. A secret salt makes the hash a keyed pseudonym, and the key becomes a single point of failure; a public salt is brute-forceable. Do not describe either as anonymization.

Edge aggregation. The sensor or a city-owned gateway sums counts and drops identifiers before transmission. The edge node is a trust boundary: secure boot, signed firmware, disabled debug interfaces, no persistent storage, and remote attestation where available. A compromised sensor can still record raw MACs before aggregation; no output-side PET can prevent that. This residual risk must be stated, not hidden.

No raw trajectory retention. If trajectories are not a product requirement, do not store them. If aggregate flows are needed, compute origin-destination matrices at the edge or aggregator and protect them with DP; do not store per-device sequences. Trajectory data is among the most re-identifiable forms of mobility data (de Montjoye et al., 2013), and a "temporary" raw table is a permanent liability.

7.4 Explicit guarantees

What we can guarantee, if the implementation is correct:

  • (ε, δ)-DP for the sequence of published aggregates, with privacy unit = device-day, contribution bound = at most one count per sensor per 15-minute bin and at most k sensor-bin pairs per day, mechanism = Laplace or Gaussian, annual budget = ε_total, and δ = δ_total. The guarantee is with respect to the stated neighboring relation; the bound holds regardless of the auxiliary information the adversary has about the other devices.
  • Post-processing immunity: forecasting, smoothing, and visualization that use only the DP aggregates do not consume additional privacy budget and do not weaken the guarantee, provided they do not access raw data.
  • No raw MAC retention at the sensor, if the firmware is correct and audited. This is an operational guarantee, not a mathematical one.
  • Edge aggregation: only counts leave the sensor, so the aggregator does not receive device-level records. This is an architectural guarantee, conditional on the firmware.

What we cannot guarantee:

  • Anonymity of every pedestrian. DP protects the contribution of a device-day, not the identity of a person. Shared devices, multiple devices per person, and non-smartphone users break the device-person mapping.
  • Protection against a compromised sensor that records raw MACs before aggregation. No output-side PET can prevent that.
  • Protection against inference from external data. DP bounds the influence of the release, not the adversary's other knowledge.
  • Utility for sparse cells. At 15-minute/100 m resolution, noise dominates; the system should not promise a live fine-grained public heatmap.
  • That a particular ε is "safe" in a legal or ethical sense. ε is a parameter, not a certificate.
  • That non-DP synthetic data is anonymous. It is not.
  • That k-anonymity, l-diversity, or t-closeness composes or resists arbitrary auxiliary data. They do not.

What we do not claim:

  • We do not claim federated learning. The pedestrian's phone does not run our code.
  • We do not claim MPC, HE, or TEE in the pilot. The pilot's trust boundary is a city-owned aggregator; those technologies add complexity without a clear threat model at that scale.
  • We do not claim that hashing MAC addresses is anonymization. The MAC space is small; a hash with a public salt is brute-forceable, and a hash with a secret salt is pseudonymization with a key-management problem.
  • We do not claim that MAC randomization protects the sensing layer. It is a device-side mitigation that fingerprinting can defeat.

7.5 What is realistic: pilot versus production

Capability Small-city pilot (8–50 sensors) Production (100–1,000 sensors) Reason
Per-sensor 15-min counts, internal Yes Yes Low-dimensional; access control or DP
Public 15-min heatmap at 100 m No No (with strong DP) Sparse cells; noise dominates
Public hourly heatmap at 250 m Maybe Yes More counts per cell; coarser grid
Public daily heatmap at 100–250 m Yes Yes Enough counts; DP feasible
Forecasting on DP aggregates Yes Yes Post-processing; measure noise impact
Cross-city federated query No Maybe MPC/SecAgg complexity
Synthetic trajectory release No Maybe High risk; needs DP and attack evaluation
Secure aggregation / TEE No Yes Multi-operator trust boundary
Formal DP accounting and audit Basic Full (RDP/zCDP, independent audit) Governance maturity

Pilot. The realistic pilot is 8–50 sensors, a city-owned aggregator, OpenDP or the Google DP library, a fixed daily release plus per-sensor 15-minute counts for internal use, and a DPIA. The main engineering work is sensor firmware (no raw storage, signed firmware, rotating salt), the aggregation pipeline, and the governance materials. The compute cost is negligible; the privacy budget and the release cadence are the binding constraints. A pilot should not attempt MPC, HE, or a TEE unless a specific multi-party trust problem requires it.

Production. A production system with 100–1,000 sensors and multiple operators needs secure aggregation or a TEE-backed aggregation service, formal DP accounting (RDP or zCDP), a budget ledger, independent audit, a transparency report, query restrictions, and incident response. The compute cost of DP remains small relative to the data pipeline; secure computation and governance dominate. Fine-grained public heatmaps remain statistically hard: the production system should publish hourly or daily aggregates at a coarse grid, not a 15-minute 100 m public map.

Performance. DP noise addition is negligible compared with data ingestion, aggregation, and model inference; the latency budget of a dashboard is not threatened by DP. Secure aggregation adds communication rounds and dropout handling; MPC adds network round trips; HE adds orders of magnitude in computation and ciphertext size; a TEE is near-native but requires attestation and careful I/O. For a city-scale count workload (10^4–10^5 counts per day), the DP release is computationally trivial. The hard problems are the privacy budget, the query interface, and the governance, not throughput.

Pilot (deployable now, honest about limits):

  1. Sensor firmware: count unique ephemeral addresses per 15-minute bin; use a secret salt that rotates per bin and is destroyed; never store raw MACs, RSSI, probe requests, or sequences; sign firmware and disable debug interfaces.
  2. Edge aggregation: emit only (sensor_id, bin_start, count); aggregate at a city-owned gateway; enforce contribution bounds across sensors and bins.
  3. Central DP: use OpenDP or the Google DP library; Laplace noise for per-sensor counts; Gaussian/RDP for multi-query releases; publish the privacy unit, contribution bound, ε, δ, and annual budget.
  4. Release policy: per-sensor 15-minute counts for internal operations; daily or weekly heatmaps at 250 m for public release; no arbitrary public filters; no raw exports.
  5. Forecasting: train on DP aggregates; report WAPE under the same noise level; do not compare a DP-trained model to a raw-data model without saying so.
  6. Governance: DPIA, legal basis, retention policy, data protection officer sign-off, public privacy budget, and an audit of the firmware and the aggregation code. A DPIA is required for systematic monitoring of a publicly accessible area on a large scale under GDPR Article 35(3)(c); the DPIA should cover the sensor layer, the aggregation, the release policy, and the re-identification risk.

Production (additional layers):

  1. Secure aggregation or TEE across sensor operators; attestation and reproducible builds; threshold decryption or a hardware root of trust.
  2. Formal accounting with RDP or zCDP; a budget ledger that includes every release, query, model selection, and retry; a privacy filter that blocks over-budget queries.
  3. Independent audit of the DP implementation, the sensitivity calculations, and the firmware; a public transparency report.
  4. Query restrictions: a fixed release schedule, a documented API, rate limits, and no differencing queries. If an interactive API is required, use a DP query system with per-analyst budgets and query restriction.
  5. DP synthetic data for open release, with Anonymeter and membership-inference evaluation; never release non-DP synthetic trajectories.
  6. Incident response: key rotation, firmware update, side-channel review, and a process for revoking a compromised sensor.

What not to do:

  • Do not store raw MACs "for calibration" or "for debugging" in production.
  • Do not hash MACs and call the result anonymous.
  • Do not rely on k-anonymity alone for a public API.
  • Do not use local DP for sparse 15-minute counts and expect useful heatmaps.
  • Do not release non-DP synthetic data with an anonymity claim.
  • Do not claim federated learning without device-side code.
  • Do not claim a TEE makes the output private; TEEs protect data in use, not the released statistic.
  • Do not publish "ε = 1" without the privacy unit, contribution bound, release cadence, and annual budget.

7.7 Open problems

  • Utility of DP at fine spatio-temporal resolution. Adaptive grids, matrix mechanisms for heatmap range queries, and hierarchical models may improve the trade-off, but the sparse-cell limit is fundamental.
  • Forecasting under DP noise. How much WAPE degradation does a given (ε, δ) cause? This is an empirical question for the PulseCast evaluation, not an assumption.
  • Calibration of device counts to people. Device penetration, shared devices, and MAC randomization bias the counts; DP protects devices, not people. A calibration study against manual counts is needed.
  • Cross-sensor contribution bounding. A device observed by many sensors creates a sensitivity problem; the right bound and the right privacy unit for a multi-sensor heatmap are open design questions.
  • Standard privacy budgets for municipal data. There is no accepted ε for city footfall; a public, participatory process is needed, not a vendor default.
  • Regulatory acceptance. DP is not automatically anonymization under GDPR. The legal test remains whether re-identification is reasonably likely in context; a DP release with a strong budget and no auxiliary data may support an anonymization argument, but that is a legal determination, not a mathematical one.
  • Auditing. Independent audits of DP implementations, sensitivity calculations, and firmware are rare; they should be standard for public deployments.

8. Citations

DP foundations and interpretation

  • Abowd, J. M., and Schmutte, I. M. (2019). An Economic Analysis of Privacy Protection and Statistical Accuracy as Social Choices. American Economic Review, 109(1), 171–202. https://doi.org/10.1257/aer.20170627
  • Abowd, J. M., Ashmead, R., Cumings-Menon, R., Garfinkel, S., Heineck, M., Heiss, C., Johns, R., Kifer, D., Leclerc, P., Machanavajjhala, A., Moran, B., Sexton, W., Spence, M., and Zhuravlev, P. (2022). The 2020 Census Disclosure Avoidance System TopDown Algorithm. Harvard Data Science Review, Special Issue 2. https://doi.org/10.1162/99608f92.529e3cb9
  • Dwork, C. (2006). Differential Privacy. ICALP 2006, LNCS 4052, 1–12. https://doi.org/10.1007/11787006_1
  • Dwork, C. (2011). A Firm Foundation for Private Data Analysis. Communications of the ACM, 54(1), 86–95. https://doi.org/10.1145/1866739.1866758
  • Dwork, C., Kohli, N., and Mulligan, D. (2019). Differential Privacy in Practice: Expose your Epsilons! Journal of Privacy and Confidentiality, 9(2). https://doi.org/10.29012/jpc.689
  • Dwork, C., McSherry, F., Nissim, K., and Smith, A. (2006). Calibrating Noise to Sensitivity in Private Data Analysis. TCC 2006, LNCS 3876, 265–284. https://doi.org/10.1007/11681878_14
  • Dwork, C., and Roth, A. (2014). The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science, 9(3–4), 211–407. https://doi.org/10.1561/0400000042
  • Hsu, J., Gaboardi, M., Haeberlen, A., Khanna, S., Narayan, A., Pierce, B. C., and Roth, A. (2014). Differential Privacy: An Economic Method for Choosing Epsilon. IEEE CSF 2014. https://doi.org/10.1109/CSF.2014.35
  • Lee, J., and Clifton, C. (2011). How Much Is Enough? Choosing ε for Differential Privacy. ISC 2011, LNCS 7001, 325–340. https://doi.org/10.1007/978-3-642-24861-0_22
  • NIST (2025). Guidelines for Evaluating Differential Privacy Guarantees. NIST Special Publication 800-226. https://doi.org/10.6028/NIST.SP.800-226
  • Wood, A., Altman, M., Bembenek, A., Bun, M., Gaboardi, M., Honaker, J., Nissim, K., O'Brien, D. R., Steinke, T., and Vadhan, S. (2018). Differential Privacy: A Primer for a Non-Technical Audience. Vanderbilt Journal of Entertainment & Technology Law, 21(1), 209–276.

Mechanisms, composition, and accounting

  • Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. (2016). Deep Learning with Differential Privacy. ACM CCS 2016, 308–318. https://doi.org/10.1145/2976749.2978318
  • Balle, B., and Wang, Y.-X. (2018). Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising. ICML 2018, PMLR 80, 394–403.
  • Bun, M., and Steinke, T. (2016). Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. TCC 2016, LNCS 9563, 635–658. https://doi.org/10.1007/978-3-662-53641-4_24
  • Canonne, C. L., Kamath, G., and Steinke, T. (2020). The Discrete Gaussian for Differential Privacy. NeurIPS 2020.
  • Dong, J., Roth, A., and Su, W. J. (2022). Gaussian Differential Privacy. Journal of the Royal Statistical Society: Series B, 84(1), 3–37. https://doi.org/10.1111/rssb.12454
  • Dwork, C., Naor, M., Pitassi, T., and Rothblum, G. N. (2010a). Differential Privacy under Continual Observation. STOC 2010, 715–724. https://doi.org/10.1145/1806689.1806787
  • Dwork, C., Rothblum, G. N., and Vadhan, S. (2010b). Boosting and Differential Privacy. FOCS 2010, 51–60. https://doi.org/10.1109/FOCS.2010.12
  • Kairouz, P., Oh, S., and Viswanath, P. (2015). The Composition Theorem for Differential Privacy. ICML 2015, PMLR 37, 1376–1385.
  • Mironov, I. (2017). Rényi Differential Privacy. IEEE CSF 2017, 263–275. https://doi.org/10.1109/CSF.2017.11

Counting, histograms, and spatial queries

  • Cormode, G., Procopiuc, C., Srivastava, D., Shen, E., and Yu, T. (2012). Differentially Private Spatial Decompositions. IEEE ICDE 2012, 20–31. https://doi.org/10.1109/ICDE.2012.28
  • Hay, M., Rastogi, V., Miklau, G., and Suciu, D. (2010). Boosting the Accuracy of Differentially Private Histograms through Consistency. PVLDB, 3(1), 1021–1032. https://doi.org/10.14778/1920841.1920970
  • Li, C., Miklau, G., Hay, M., McGregor, A., and Rastogi, V. (2015). The Matrix Mechanism: Optimizing Linear Counting Queries under Differential Privacy. The VLDB Journal, 24(6), 757–781. https://doi.org/10.1007/s00778-015-0398-x
  • Zhang, J., Xiao, X., and Xie, X. (2016). PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions. ACM SIGMOD 2016, 155–170. https://doi.org/10.1145/2882903.2882928

Local and shuffle models

  • Balle, B., Bell, J., Gascón, A., and Nissim, K. (2019). The Privacy Blanket of the Shuffler. CRYPTO 2019, LNCS 11694, 157–186. https://doi.org/10.1007/978-3-030-26953-1_9
  • Bittau, A., Erlingsson, Ú., Maniatis, P., Mironov, I., Raghunathan, A., Lie, D., Rudominer, M., Kifer, D., Balle, B., Kairouz, P., and Kenthapadi, K. (2017). Prochlo: Strong Privacy for Analytics in the Crowd. ACM SOSP 2017, 441–459. https://doi.org/10.1145/3132747.3132769
  • Duchi, J. C., Jordan, M. I., and Wainwright, M. J. (2013). Local Privacy and Statistical Minimax Rates. FOCS 2013, 429–438. https://doi.org/10.1109/FOCS.2013.53
  • Erlingsson, Ú., Feldman, V., Mironov, I., Raghunathan, A., Talwar, K., and Thakurta, A. (2019). Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity. SODA 2019, 2468–2479. https://doi.org/10.1137/1.9781611975482.151
  • Erlingsson, Ú., Pihur, V., and Korolova, A. (2014). RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response. ACM CCS 2014, 1054–1067. https://doi.org/10.1145/2660267.2660348
  • Feldman, V., McMillan, A., and Talwar, K. (2021). Hiding among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling. FOCS 2021, 954–964. https://doi.org/10.1109/FOCS52979.2021.00095
  • Ghazi, B., Golowich, N., Kumar, R., Pagh, R., and Velingker, A. (2021). On the Power of Multiple Anonymous Messages: Frequency Estimation and Selection in the Shuffle Model of Differential Privacy. EUROCRYPT 2021, LNCS 12696, 463–488. https://doi.org/10.1007/978-3-030-77883-5_16
  • Kairouz, P., Oh, S., and Viswanath, P. (2016). Extremal Mechanisms for Local Differential Privacy. Journal of Machine Learning Research, 17(1), 1–51.
  • Warner, S. L. (1965). Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias. Journal of the American Statistical Association, 60(309), 63–69. https://doi.org/10.1080/01621459.1965.10480775

k-anonymity, l-diversity, t-closeness, and re-identification

  • de Montjoye, Y.-A., Hidalgo, C. A., Verleysen, M., and Blondel, V. D. (2013). Unique in the Crowd: The Privacy Bounds of Human Mobility. Scientific Reports, 3, 1376. https://doi.org/10.1038/srep01376
  • de Montjoye, Y.-A., Radaelli, L., Singh, V. K., and Pentland, A. (2015). Unique in the Shopping Mall: On the Reidentifiability of Credit Card Metadata. Science, 347(6221), 536–539. https://doi.org/10.1126/science.1256297
  • Ganta, S. R., Thompson, S., and Kumar, T. N. V. (2008). Composition Attacks on Anonymized Databases. PVLDB, 1(1). Proceedings of VLDB 2008.
  • Gruteser, M., and Grunwald, D. (2003). Anonymous Usage of Location-Based Services through Spatial and Temporal Cloaking. MobiSys 2003.
  • Li, N., Li, T., and Venkatasubramanian, S. (2007). t-Closeness: Privacy Beyond k-Anonymity and l-Diversity. IEEE ICDE 2007, 106–115. https://doi.org/10.1109/ICDE.2007.367856
  • Machanavajjhala, A., Kifer, D., Gehrke, J., and Venkitasubramaniam, M. (2006). l-Diversity: Privacy Beyond k-Anonymity. IEEE ICDE 2006. https://doi.org/10.1109/ICDE.2006.1
  • Meyerson, A., and Williams, R. (2004). On the Complexity of Optimal K-Anonymity. ACM PODS 2004, 223–228. https://doi.org/10.1145/1055558.1055591
  • Mokbel, M. F., Chow, C.-Y., and Aref, W. G. (2006). The New Casper: Query Processing for Location Services without Compromising Privacy. VLDB 2006.
  • Narayanan, A., and Shmatikov, V. (2008). Robust De-anonymization of Large Sparse Datasets. IEEE Symposium on Security and Privacy 2008, 111–125. https://doi.org/10.1109/SP.2008.33
  • Ohm, P. (2010). Broken Promises of Privacy: Responding to the Surprising Failure of Anonymization. UCLA Law Review, 57, 1701–1777.
  • Samarati, P., and Sweeney, L. (1998). Protecting Privacy when Disclosing Information: k-Anonymity and Its Enforcement through Generalization and Suppression. Technical Report SRI-CSL-98-04, SRI Computer Science Laboratory.
  • Sweeney, L. (2002). k-anonymity: A Model for Protecting Privacy. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 10(5), 557–570. https://doi.org/10.1142/S0218488502001648
  • Tockar, A. (2014). Riding with the Stars: Passenger Privacy in the NYC Taxicab Dataset. Neustar Research, September 15, 2014.
  • Barbaro, M., and Zeller, T. (2006). A Face Is Exposed for AOL Searcher No. 4417749. The New York Times, August 9, 2006.
  • Dinur, I., and Nissim, K. (2003). Revealing Information while Preserving Privacy. ACM PODS 2003, 202–210. https://doi.org/10.1145/773153.773173
  • Shokri, R., Stronati, M., Song, C., and Shmatikov, V. (2017). Membership Inference Attacks Against Machine Learning Models. IEEE Symposium on Security and Privacy 2017, 3–18. https://doi.org/10.1109/SP.2017.41

Secure computation, federated learning, HE, and TEEs

  • Bonawitz, K., Ivanov, V., Kreuter, B., Marcedone, A., McMahan, H. B., Patel, S., Ramage, D., Segal, A., and Seth, K. (2017). Practical Secure Aggregation for Privacy-Preserving Machine Learning. ACM CCS 2017, 1175–1191. https://doi.org/10.1145/3133956.3133982
  • Bonawitz, K., Eichner, H., Grieskamp, W., Huba, D., Ingerman, A., Ivanov, V., Kiddon, C., Konečný, J., Mazzocchi, S., McMahan, H. B., Van Overveldt, T., Petrou, D., Ramage, D., and Roselander, J. (2019). Towards Federated Learning at Scale: System Design. MLSys 2019.
  • Cheon, J. H., Kim, A., Kim, M., and Song, Y. (2017). Homomorphic Encryption for Arithmetic of Approximate Numbers. ASIACRYPT 2017, LNCS 10624, 409–437. https://doi.org/10.1007/978-3-319-70694-8_15
  • Damgård, I., Pastro, V., Smart, N., and Zakarias, S. (2012). Multiparty Computation from Somewhat Homomorphic Encryption. CRYPTO 2012, LNCS 7417, 643–662. https://doi.org/10.1007/978-3-642-32009-5_38
  • Gentry, C. (2009). Fully Homomorphic Encryption Using Ideal Lattices. STOC 2009, 169–178. https://doi.org/10.1145/1536414.1536440
  • Goldreich, O., Micali, S., and Wigderson, A. (1987). How to Play any Mental Game. STOC 1987, 218–229. https://doi.org/10.1145/28395.28420
  • Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., et al. (2021). Advances and Open Problems in Federated Learning. Foundations and Trends in Machine Learning, 14(1–2), 1–210. https://doi.org/10.1561/2200000083
  • Lindell, Y. (2020). Secure Multiparty Computation. Communications of the ACM, 63(9), 76–85. https://doi.org/10.1145/3387108
  • McMahan, H. B., Moore, E., Ramage, D., Hampson, S., and Agüera y Arcas, B. (2017). Communication-Efficient Learning of Deep Networks from Decentralized Data. AISTATS 2017, PMLR 54, 1273–1282.
  • McMahan, H. B., Ramage, D., Talwar, K., and Zhang, L. (2018). Learning Differentially Private Recurrent Language Models. ICLR 2018.
  • NIST (2022). Hardware-Enabled Security: Enabling a Layered Approach to Platform Security for Cloud and Edge Computing Use Cases. NIST IR 8320. https://doi.org/10.6028/NIST.IR.8320
  • Paillier, P. (1999). Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. EUROCRYPT 1999, LNCS 1592, 223–238. https://doi.org/10.1007/3-540-48910-X_16
  • Van Bulck, J., Minkin, M., Weisse, O., Genkin, D., Kasikci, B., Piessens, F., Silberstein, M., Wenisch, T. F., Yarom, Y., and Strackx, R. (2018). Foreshadow: Extracting the Keys to the Intel SGX Kingdom with Transient Out-of-Order Execution. USENIX Security 2018.
  • Kocher, P., Horn, J., Fogh, A., Genkin, D., Gruss, D., Haas, W., Hamburg, M., Lipp, M., Mangard, S., Prescher, T., Schwarz, M., and Yarom, Y. (2020). Plundervolt: Software-based Fault Injection Attacks against Intel SGX. IEEE Symposium on Security and Privacy 2020. https://doi.org/10.1109/SP40000.2020.00057
  • Yao, A. C.-C. (1986). How to Generate and Exchange Secrets. FOCS 1986, 162–167. https://doi.org/10.1109/SFCS.1986.25
  • Zhu, L., Liu, Z., and Han, S. (2019). Deep Leakage from Gradients. NeurIPS 2019.
  • Nasr, M., Shokri, R., and Houmansadr, A. (2019). Comprehensive Privacy Analysis of Deep Learning: Passive and Active White-box Inference Attacks against Centralized and Federated Learning. IEEE Symposium on Security and Privacy 2019, 739–753. https://doi.org/10.1109/SP.2019.00065

Synthetic data

  • Feng, J., Yang, Z., Xu, F., Yu, H., Wang, M., and Li, Y. (2020). Learning to Simulate Human Mobility. ACM SIGKDD 2020.
  • Giomi, M., Boenisch, F., Wehmeyer, C., and Tasnádi, B. (2023). A Unified Framework for Quantifying Privacy Risk in Synthetic Data. Proceedings on Privacy Enhancing Technologies, 2023(3). https://doi.org/10.56553/popets-2023-0055
  • Jordon, J., Yoon, J., and van der Schaar, M. (2019). PATE-GAN: Generating Synthetic Data with Differential Privacy Guarantees. ICLR 2019.
  • McKenna, R., Mullins, B., Sheldon, D., and Miklau, G. (2022). AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Data. PVLDB, 15(11), 2599–2612. https://doi.org/10.14778/3551793.3551817
  • Simini, F., Barlacchi, G., Luca, M., and Pappalardo, L. (2021). A Deep Gravity Model for Mobility Flows Generation. Nature Communications, 12, 6576. https://doi.org/10.1038/s41467-021-26752-4
  • Stadler, T., Oprisanu, B., and Troncoso, C. (2022). Synthetic Data – Anonymisation Groundhog Day. USENIX Security 2022, 1451–1468.
  • van Breugel, B., Sun, H., Qian, Z., and van der Schaar, M. (2023). Membership Inference Attacks Against Synthetic Data through Overfitting Detection. AISTATS 2023.
  • Xie, L., Lin, K., Wang, S., Wang, F., and Zhou, J. (2018). Differentially Private Generative Adversarial Network. arXiv:1802.06739.
  • Zhang, J., Cormode, G., Procopiuc, C. M., Srivastava, D., and Xiao, X. (2017). PrivBayes: Private Data Release via Bayesian Networks. ACM Transactions on Database Systems, 42(4), 25. https://doi.org/10.1145/3132704

Deployments and implementations

Regulatory and governance

  • Article 29 Working Party (2011). Opinion 13/2011 on Geolocation Services on Smart Mobile Devices. WP185.
  • Article 29 Working Party (2014). Opinion 05/2014 on Anonymisation Techniques. WP216.
  • European Parliament and Council (2016). Regulation (EU) 2016/679 (General Data Protection Regulation).
  • UK Information Commissioner's Office (2012). Anonymisation: Managing Data Protection Risk Code of Practice.
  • U.S. Department of Health and Human Services. HIPAA Privacy Rule, 45 CFR §164.514.
  • NIST (2015). De-Identification of Personal Information. NIST IR 8053. https://doi.org/10.6028/NIST.IR.8053
  • NIST (2023). De-Identifying Government Datasets: Techniques and Governance. NIST SP 800-188. https://doi.org/10.6028/NIST.SP.800-188

Wireless tracking and ephemeral identifiers

  • Franklin, J., McCoy, D., Tabriz, P., Neagoe, V., Van Randwyk, J., and Snoeren, A. C. (2006). Passive Data Link Layer 802.11 Wireless Device Driver Fingerprinting. USENIX Security 2006.
  • Martin, J., Alpuche, D., Bodeman, K., Brown, L., Fenske, E., Foppe, L., Mayberry, T., Rye, E. C., Sipes, B., and Teplov, S. (2019). Handoff All Your Privacy: A Review of Apple's Bluetooth Low Energy Continuity Protocol. Proceedings on Privacy Enhancing Technologies, 2019(4). https://doi.org/10.2478/popets-2019-0057
  • Vanhoef, M., Matte, C., Cunche, M., Cardoso, L. S., and Piessens, F. (2016). Why MAC Address Randomization is not Enough: An Analysis of Wi-Fi Network Discovery Mechanisms. ACM AsiaCCS 2016, 413–424. https://doi.org/10.1145/2897845.2897883

Empirical and deployment numbers in this memo are sourced from the cited primary literature. Derived quantities (confidence intervals, composition bounds, release-cadence arithmetic) are shown with their assumptions and are labelled as illustrative design arithmetic where they are not direct measurements. The PulseCast pilot's own measurements (8 sensors, ~5 months, ~580 m cluster) are used only as sizing assumptions, not as privacy results.