Paper 2014/693

Optimal Proximity Proofs

Ioana Boureanu and Serge Vaudenay


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.

Note: final version

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. Proceedings of Inscrypt'14 (LNCS) to appear.
distance boundingrelay attackaccess control
Contact author(s)
serge vaudenay @ epfl ch
2015-01-16: last of 2 revisions
2014-09-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ioana Boureanu and Serge Vaudenay},
      title = {Optimal Proximity Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2014/693},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.