Paper 2014/888

Distance Lower Bounding

Xifan Zheng, Reihaneh Safavi-Naini, and Hadi Ahmadi


Distance (upper)-bounding (DUB) allows a verifier to know whether a proving party is located within a certain distance bound. DUB protocols have many applications in secure authentication and location based services. We consider the dual problem of distance lower bounding (DLB), where the prover proves it is outside a distance bound to the verifier. We motivate this problem through a number of application scenarios, and model security against distance fraud (DF), Man-in-the-Middle (MiM), and collusion fraud (CF) attacks. We prove impossibility of security against these attacks without making physical assumptions. We propose approaches to the construction of secure protocols under reasonable assumptions, and give detailed design of our DLB protocol and prove its security using the above model. This is the first treatment of the DLB problem in the untrusted prover setting, with a number of applications and raising new research questions. We discuss our results and propose directions for future research.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ICICS 2014
Distance boundingsecure erasure
Contact author(s)
zhengxifan0403 @ gmail com
2014-12-14: revised
2014-10-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Xifan Zheng and Reihaneh Safavi-Naini and Hadi Ahmadi},
      title = {Distance Lower Bounding},
      howpublished = {Cryptology ePrint Archive, Paper 2014/888},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.