Security analysis of the Louis protocol for location privacy

Many location-based services for alerting persons of nearby friends have been deployed in practice. A drawback of most approaches to providing such services is that friends always learn each other´s location even when they are not actually nearby. The Louis protocol proposed by Zhong, Goldberg and Hengartner aims to ensure that a friend´s location is revealed to another friend if and only if the friends are actually nearby. The protocol lets a third party learn whether the friends are nearby, without the third party learning their location. The third party communicates the answer to the person who invokes the service. A key feature of the protocol is that a person can detect misbehavior by the third party or the person´s friend. This paper reveals a flaw in the way the protocol handles the detection of the misbehaving party, leading to an unauthorized disclosure of a person´s location. Two alternatives for fixing the flaw in the protocol are proposed and a heuristic analysis is given.