Authenticated Distance Bounding Protocol with Improved FAR: Beyond the Minimal Bound of FAR

Distance bounding protocols permit a verifier to compute the distance to a prover by measuring the execution time of n rounds of challenge-response authentication. Many protocols have been proposed to reduce the false acceptance rate of the challenge-response procedure. Until now, it has been widely believed that the lowest bound of the false acceptance rate is (1/2)(n) when n is the number of rounds and the prover can send only one response bit for each round. In this paper, we propose a new distance bounding protocol whose false acceptance rate is (1/3)(n) against the distance fraud attacks and the mafia fraud attacks. To reduce the false acceptance rate, we use two challenge bits for each iteration and introduce a way of expressing three cases with the use of only one response bit, the same bit length as existing protocols. Our protocol is the first distance bounding protocol whose false acceptance rate is lower than the currently believed minimal bound without increasing the number of response bits for each round.