Cryptology ePrint Archive: Report 2014/888

Distance Lower Bounding

Xifan Zheng and Reihaneh Safavi-Naini and Hadi Ahmadi

Abstract: 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.

Category / Keywords: cryptographic protocols / Distance bounding, secure erasure

Original Publication (with major differences): ICICS 2014

Date: received 27 Oct 2014, last revised 14 Dec 2014

Contact author: zhengxifan0403 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20141214:180424 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]