Private Proofs of When and Where

Position verification schemes are interactive protocols where entities prove their physical location to others; this enables interactive proofs for statements of the form "I am at a location L." Although secure position verification cannot be achieved with classical protocols (even with computational assumptions), they are feasible with quantum protocols.

In this paper we introduce the notion of zero-knowledge position verification, which extends position verification in two ways:

1. enabling entities to prove more sophisticated statements about their locations at different times (for example, proving statements about one's position in the past "I was not near location L at noon yesterday").

2. maintaining privacy for any other detail about their true location besides the statement they are proving.

We construct zero-knowledge position verification from secure position verification and postquantum one-way functions. The central tool in our construction is a primitive we call position commitment, which allows entities to privately commit to their physical position in a particular moment, which is then revealed at some later time.