CatNap: Practical and actively secure proximity testing with a napping party based on generic MPC techniques

---

Authors: I. Oleynikov, E. Pagnin, A. Sabelfeld
In: 19th International Conference on Security and Cryptography, 2022
Full Text:

---

Abstract

Proximity testing functionality is at the core of most LocationBased Services (LBS). In a nutshell, proximity testing takes the locations of two clients from them and produces a single bit of result telling whether the clients are within each other’s proximity or not. Currently existing LBS require full trust from their clients; in order to use the service, clients have to disclose their locations in plain and trust that the service will not misuse them. Clamorous precedents of such misuse motivate the search for solutions which would ensure the privacy of client location.

In this paper, we present CatNap, a novel cryptographic protocol to perform proximity testing in a privacy-preserving manner. We focus on Euclidean distance based matching: clients are considered to be in proximity if the Euclidean distance between them is below a chosen threshold value. The protocol involves two clients and two servers. The clients submit their location data to the servers, and then one of them retrieves the proximity testing result. Additionally, our protocol implements the “napping party” feature: the clients do not depend on each other’s presence to submit the data. This property is cricual to make proximity testing practical, because it allows clients to use the functionality without having to be simultaneously online. The CatNap achieves active security and allows any subset of parties to be corrupted as long as one of the two servers is honest. Unlike previous ad-hoc solutions, our protocol relies on a blackbox use of generic Multi-Party Computation (MPC) techniques. Importantly, the MPC building block employed in our protocol can be effortlessly replaced by future, more effcient implementations of the functionality, thus directly improving our performance. We provide a proof of concept implementation of our protocol using off-the-shelf MPC libraries and evaluate its performance in terms of computation and communication cost.

Keywords: Privacy, Proximity-Testing, Multiparty Computation, Active Security.