Cryptology ePrint Archive: Report 2014/695

Proof of Proximity of Knowledge

Serge Vaudenay

Abstract: Public-key distance bounding schemes are needed to defeat relay attacks in payment systems. So far, only two such schemes exist, but fail to fully protect against malicious provers. In this paper, we solve this problem. We provide a full formalism to define the proof of proximity of knowledge (PoPoK). Protocols should succeed if and only if a prover holding a secret is within the proximity of the verifier. Like proofs of knowledge, these protocols must satisfy completeness, soundness (protection for the honest verifier), and security (protection for the honest prover). We construct ProProx, the very first fully secure PoPoK.

Category / Keywords: cryptographic protocols / distance bounding, relay attack, access control

Date: received 4 Sep 2014, last revised 16 Jan 2015

Contact author: serge vaudenay at epfl ch

Available format(s): PDF | BibTeX Citation

Note: previous version had a wrong pdf

Version: 20150116:084709 (All versions of this report)

Short URL: ia.cr/2014/695

Discussion forum: Show discussion | Start new discussion