In the recent years, new services and businesses leveraging location-based services (LBS) are rapidly emerging. On the other hand this has raised the incentive of users to cheat about their locations to the service providers for personal benefits. Context-based proofs-of-presence (PoPs) have been proposed to enable verification of users’ location claims. However, as we show in this paper, they are vulnerable to context guessing attacks. To make PoPs resilient to malicious provers we propose two complementary approaches for making context-based PoPs: one approach focuses on surprisal filtering based on estimating the entropy of particular PoPs in order to detect context measurements vulnerable to such attacks. The other approach is based on utilizing longitudinal observations of ambient modalities like noise level and ambient luminosity. It is capable of extracting more entropy from the context to construct PoPs that are hard to guess by an attacker even in situations in which other context sensor modalities fail to provide reliable PoPs.