Methods and devices for privately verifying and enhancing location data are disclosed. A location-based services server receives a possible location of a mobile device. A location verification system determines a detected location of the mobile device. The location-based services server and location verification system communicate using a private set intersection technique to determine whether the possible location corresponds to the detected location without the possible location or detected location being shared. Probabilities associated with the possible and detected locations can also be combined to enhance the accuracy of the possible location.