Distance-bounding proof of knowledge to avoid real-time attacks

Traditional authentication is based on proving the knowledge of a private key corresponding to a given public key. In some situations, especially in the context of pervasive computing, it is additionally required to verify the physical proximity of the authenticated party in order to avoid a set of real-time attacks. Brands and Chaum proposed distance-bounding protocols as a way to compute a practical upper bound on the distance between a prover and a verifier during an authentication process. Their protocol prevents frauds where an intruder sits between a legitimate prover and a verifier and succeeds to perform the distance-bounding process. However, frauds where a malicious prover and an intruder collaborate to cheat a verifier have been left as an open issue. In this paper, we provide a solution preventing both types of attacks.