Under Submission – The integrity of many location-based services depends on the veracity of locations reported by users. Unfortunately, mobile platform software, apps and users can easily forge their locations, and nearby adversaries may spoof radio signals to mislead a device into thinking it is in a different location. Location Proof Services (LPSes) can validate user locations independently, thereby adding robustness to existing location-based services and enabling entirely new applications. Existing LPSes can attest only discrete locations for which a device has previously obtained proofs, and require either infrastructure support or cannot withstand sophisticated collusion attacks with fictitious devices. ProLoc continuously aggregates time series of device locations from an ordinary location service as well as pairwise Bluetooth (BT) contacts recorded by user devices. Within a secure backend, ProLoc correlates this information. On demand, ProLoc provides a proof that a given device must have resided within a feasible region at a given time in the past, depending on the encounters the device had at the time. Moreover, by correlating data from many devices and leveraging trusted devices, ProLoc can mitigate powerful collusion attacks, involving even large numbers of fictitious devices and multiplicity attacks.