SPARSE: privacy-aware and collusion resistant location proof generation and verification

Recently, there has been an increase in the number of location-based services and applications. It is common for these applications to provide facilities or rewards for users who visit specific venues frequently. This creates the incentive for dishonest users to lie about their location and submit fake check-ins by changing their GPS data. To solve this issue, different distributed location proof schemes have been proposed to generate location proofs for mobile users. However, these schemes have some drawbacks: (1) they are vulnerable to either Prover-Prover or Prover-Witness collusions, (2) the location proof generation process is slow when users adopt a long private key, and (3) their implementation requires some hardware changes on mobile devices. To address these issues, we propose the Secure, Privacy-Aware and collusion Resistant poSition vErification (SPARSE) scheme to generate private location proofs for mobile users. SPARSE has a distributed architecture designed for ad-hoc scenarios in which mobile users generate location proofs for each other. Since we do not integrate any distance bounding protocol into SPARSE, it becomes an easy-to-implement scheme in which the location proof generation process is independent of the length of the users' private key. We provide a comprehensive security analysis and simulation which show that SPARSE provides privacy protection as well as security properties for users including integrity, unforgeability and non-transferability of the location proofs. Moreover, it achieves a highly reliable performance against collusions.