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 18 Dec 2014
Contact author: serge vaudenay at epfl ch
Available format(s): PDF | BibTeX Citation
Note: A few details corrected.
New appendices added.
Version: 20141218:074534 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]