Cryptology ePrint Archive: Report 2014/693

Optimal Proximity Proofs

Ioana Boureanu and Serge Vaudenay

Abstract: Provably secure distance-bounding is a rising subject, yet an unsettled one; indeed, very few distance-bounding protocols, with formal security proofs, have been proposed. In fact, so far only two protocols, namely SKI (by Boureanu et al.) and FO (by Fischlin and Onete), offer all-encompassing security guaranties, i.e., resistance to distance-fraud, mafia-fraud, and terrorist-fraud. Matters like security, alongside with soundness, or added tolerance to noise do not always coexist in the (new) distance-bounding designs. Moreover, as we will show in this paper, efficiency and simultaneous protection against all frauds seem to be rather conflicting matters, leading to proposed solutions which were/are sub-optimal. In fact, in this recent quest for provable security, efficiency has been left in the shadow. Notably, the tradeoffs between the security and efficiency have not been studied. In this paper, we will address these limitations, setting the "security vs. efficiency" record straight.

Concretely, by combining ideas from SKI and FO, we propose symmetric protocols that are efficient, noise-tolerant and-at the same time-provably secure against all known frauds. Indeed, our new distance-bounding solutions outperform the two aforementioned provably secure distance-bounding protocols. For instance, with a noise level of 5%, we obtain the same level of security as those of the pre-existent protocols, but we reduce the number of rounds needed from 181 to 54.

Category / Keywords: cryptographic protocols / distance bounding, relay attack, access control

Original Publication (with minor differences): Proceedings of Inscrypt'14 (LNCS) to appear.

Date: received 3 Sep 2014, last revised 16 Jan 2015

Contact author: serge vaudenay at epfl ch

Available format(s): PDF | BibTeX Citation

Note: final version

Version: 20150116:085047 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]