CatNap: a Protocol for Server-aided Proximity Testing

Abstract

In this talk we will look at the protocol that allows two parties who know their locations on a Euclidean plane to check whether they are within distance R of each other or not. A distinguishing feature of this protocol is that it does not require the parties to communicate with each other directly and be online at the same time. We introduce a pair of servers to which one client may submit their data and go offline with the other client coming online later, finishing the protocol and fetching the matching result.

We build the protocols by combining existing off-the-shelf Cryptographic techniques. Interestingly, the protocol has better parameters (w.r.t. performance and security) than some of the hand-crafted protocols. So the importance of our protocol is in showing what can be achieved in this field “for free” using the generic techniques, and setting the bar for anyone who tries to make a “smarter” protocol for this problem in the future.

During the talk we will have an intro to how Multi-Party Computation protocols work, then show how our CatNap is built from them, and finally discuss the practical implications of this work.