Private Proofs of When and Where

Uma Girish; Grzegorz Gluch; Shafi Goldwasser; Tal Malkin; Leo Orshansky; Henry Yuen

Paper 2026/136

Private Proofs of When and Where

Uma Girish

, Columbia University

Grzegorz Gluch

, Massachusetts Institute of Technology, University of California, Berkeley

Shafi Goldwasser

, Massachusetts Institute of Technology, University of California, Berkeley

Tal Malkin

, Columbia University

Leo Orshansky

, Columbia University

Henry Yuen

, Columbia University

Abstract

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 generalizes position verification in two ways: 1. enabling entities to prove more sophisticated statements about their locations at different times (for example, "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 standard position verification and post-quantum one-way functions. The central tool in our construction is a primitive we call position commitments, which allow entities to privately commit to their physical position in a particular moment, which is then revealed at some later time.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: position verification quantum cryptography zero knowledge privacy
Contact author(s): lo2433 @ columbia edu
History: 2026-02-13: last of 2 revisions; 2026-01-28: received; See all versions
Short URL: https://ia.cr/2026/136
License: CC BY

BibTeX

@misc{cryptoeprint:2026/136,
      author = {Uma Girish and Grzegorz Gluch and Shafi Goldwasser and Tal Malkin and Leo Orshansky and Henry Yuen},
      title = {Private Proofs of When and Where},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/136},
      year = {2026},
      url = {https://eprint.iacr.org/2026/136}
}