# Accurate and Efficient Trajectory-based Contact Tracing with Secure Computation and Geo-Indistinguishability

arXiv: https://arxiv.org/abs/2303.02838 · HTML: https://mlsanity.com/paper/2303.02838/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Mar 2023.

## Built on by (most cited first, 1 of 1)

- [Leveraging the Spatial Hierarchy: Coarse-to-fine Trajectory Generation via Cascaded Hybrid Diffusion](https://mlsanity.com/paper/2507.13366/) (2025)

## Abstract (arXiv)

Contact tracing has been considered as an effective measure to limit the transmission of infectious disease such as COVID-19. Trajectory-based contact tracing compares the trajectories of users with the patients, and allows the tracing of both direct contacts and indirect contacts. Although trajectory data is widely considered as sensitive and personal data, there is limited research on how to securely compare trajectories of users and patients to conduct contact tracing with excellent accuracy, high efficiency, and strong privacy guarantee. Traditional Secure Multiparty Computation (MPC) techniques suffer from prohibitive running time, which prevents their adoption in large cities with millions of users. In this work, we propose a technical framework called ContactGuard to achieve accurate, efficient, and privacy-preserving trajectory-based contact tracing. It improves the efficiency of the MPC-based baseline by selecting only a small subset of locations of users to compare against the locations of the patients, with the assist of Geo-Indistinguishability, a differential privacy notion for Location-based services (LBS) systems. Extensive experiments demonstrate that ContactGuard runs up to 2.6× faster than the MPC baseline, with no sacrifice in terms of the accuracy of contact tracing.