Distance-preserving pseudonymization for timestamps and spatial data

Florian KerschbaumWPES 2007 · DOI

TL;DR

This paper introduces a novel method for pseudonymizing timestamps and spatial data that preserves the ability to compute distances between data points, but only up to a certain threshold. This allows for collaborative intrusion detection without revealing sensitive temporal or spatial information beyond what's necessary for timely event correlation.

What Problem Does This Paper Address?

In collaborative intrusion detection, multiple organizations might want to share security logs to detect threats more effectively. However, sharing raw logs, especially timestamps and location data, poses significant privacy risks. Existing pseudonymization techniques often sacrifice the ability to perform crucial analyses, like determining if events occurred close in time. This paper tackles the challenge of balancing privacy with the utility of log data for intrusion detection, specifically focusing on the need to compare temporal and spatial distances.

Methods

The core of the proposed solution is a pseudonymization technique that "preserves distance" up to a defined threshold d. For timestamps, this involves transforming each timestamp t into a tuple (MAC(l, s), m, MAC(u, s), v). Here, l and u are "grid points" surrounding t determined by d and a random offset r, s is a shared secret key for message authentication codes (MACs), m is the distance from t to l, and v is the distance from t to u.

Trudy (the third party analyzing the data) can then compute the distance |t - t'| between two pseudonymized timestamps if their actual distance is less than d. If the distance is greater than or equal to 2d, Trudy cannot compute it. This is achieved by checking if the pseudonymized tuples share a common grid point. If they do, the distance can be inferred from the m and v values. If they don't share a grid point, the distance is too large to be reliably computed.

The technique is extended to two dimensions for spatial data, using a similar grid-based approach and the cosine law for distance calculation.

Datasets

The paper mentions using "real-world log data" for evaluation but does not specify the datasets by name.

Key Insights and Ideas

  • Distance Preservation as a Privacy-Utility Trade-off: The paper highlights that the ability to compute distances is crucial for intrusion detection, but directly revealing these distances compromises privacy. Their method offers a controlled way to preserve this utility up to a threshold.
  • Grid-Based Pseudonymization: The use of a grid system to discretize time and space, combined with relative distances to grid points, is a novel approach to pseudonymization.
  • Controlled Information Leakage: The method intentionally leaks information about distances below a threshold d while obscuring distances above 2d. This controlled leakage is key to enabling specific analyses without oversharing.
  • Extension to 2D Spatial Data: The successful extension to spatial data demonstrates the broader applicability of the core concept for analyzing correlated events in both time and space.

Key Results

The paper theoretically and empirically demonstrates that their pseudonymization technique allows a third party to:

  • Compute the distance between two timestamps if the distance is less than or equal to an agreed threshold d.
  • Be unable to compute the distance if it is greater than or equal to 2d.
  • This property is also shown to hold for two-dimensional spatial data.

The paper also analyzes the privacy implications, showing that the probability of a distance being computable (i.e., less than 3d) is related to the arrival rate of events and the chosen threshold d. For an example with a=2 (where d = aμ), the expected cluster size of continuously related timestamps is approximately 19.

Limitations and Future Work

  • Limited Utility for Large Distances: The primary limitation is that distances greater than or equal to 2d cannot be computed, which might limit the detection of certain types of intrusions that span larger time or spatial gaps.
  • Privacy is Not Absolute: The paper acknowledges that any mechanism allowing distance computation up to a threshold inherently limits privacy. The attack section demonstrates how Trudy can infer ordering and potentially larger distances through inference over multiple smaller distances.
  • Future Work: The authors suggest extending their work to allow Trudy to perform more complex operations efficiently beyond just distance computations. They also note that the privacy provided is good for sparse data sets.

Summary updated

BibTeX
@inproceedings{kerschbaum2007distance,
  author = {Florian Kerschbaum},
  title = {{Distance-preserving pseudonymization for timestamps and spatial data}},
  booktitle = {WPES},
  year = {2007},
  doi = {10.1145/1314333.1314346},
}
Figure