Cryptology ePrint Archive: Report 2014/114

Prover Anonymous and Deniable Distance-Bounding Authentication

Sebastien Gambs and Cristina Onete and Jean-Marc Robert

Abstract: In distance-bounding authentication protocols, a verifi er confi rms that a prover is (1) legitimate and (2) in the verifi er's proximity. Proximity checking is done by running time-critical exchanges between both parties. This enables the verifi er to detect relay attacks (a.k.a. ma fia fraud). While most distance-bounding protocols o ffer resistance to mafi a and distance fraud as well as to impersonation attacks, only few protect the privacy of the authenticating prover.

One exception is the protocol due to Hermans, Peeters, and Onete developed in 2013, which o ffers strong privacy guarantees with respect to a Man-in-the-Middle adversary. However, this protocol provides no privacy guarantees for the prover with respect to a malicious verifi er, who can fully identify the prover. Having in mind possible verifi er corruption or data leakage from veri fiers to a centralized server, we suggest that stronger privacy properties are needed.

In this paper, we propose an efficient distance-bounding protocol that gives strong prover privacy guarantees even with respect to the veri fier or to a centralized back-end server, storing prover information and managing revocation and registration. Specifi cally, we formally model and de fine prover anonymity, a property guaranteeing that verifi ers infer only the legitimacy of the prover but not his identity, and deniability, which ensures that the back-end server cannot distinguish prover behavior from malicious verifi er behavior (i.e., provers can deny that they authenticated). Finally, we present an efficient protocol that achieves these strong guarantees, give exact bounds for each of its security properties, and prove these statements formally.

Category / Keywords: cryptographic protocols / distance-bounding, deniability, anonymity, privacy, provable security

Original Publication (with minor differences): Proceedings of ACM AsiaCCS 2014

Date: received 14 Feb 2014, last revised 15 Oct 2015

Contact author: cristina onete at gmail com

Available format(s): PDF | BibTeX Citation

Note: Protocol modification, following a comment by Serge Vaudenay, whose input we are grateful for.

Version: 20151015:065312 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]