I Prove, Therefore I Am: Spatiotemporal Multi-Party Computation

AI summary

Overview

Research area: Quantum cryptography and secure multiparty computation (MPC), specifically the new notion the authors call spatiotemporal MPC, which extends MPC to functionalities whose inputs include physical facts such as a party's location, time, or trajectory.

Technical level: Advanced. The paper is written for readers comfortable with the simulation-based (real/ideal) security paradigm, the universally composable (UC) framework, position verification, and lattice-based assumptions such as the quantum hardness of Learning with Errors (QLWE).

Scope (one sentence): The paper introduces definitions and feasibility constructions for secure multiparty computation over inputs that combine ordinary private data with physically authenticated spatiotemporal information.

What This Paper Is About

Standard MPC lets distrustful parties compute on private digital inputs, but it cannot tell whether a claimed location or trajectory is real: a malicious party can simply type in a false one. The authors ask whether MPC can be extended so that the computation uses spatiotemporal information that is both hidden from the other parties and guaranteed to match the party's actual physical state. Their central obstacle is definitional — how does a simulator "extract" a physical property in the real/ideal paradigm — and their answer is to define physical presence operationally, through the ability to pass a sound verification protocol ("I prove, therefore I am").

Key Contributions

1. A new security notion: arguments of spatiotemporal knowledge. In the informal Definition 1, a position-verification protocol Π = ⟨P, V⟩ is an argument of spatiotemporal knowledge if there is an efficient two-stage extractor Ext = (Ext₀, Ext₁) and a sound position-verification protocol Π′ such that, whenever a malicious prover P* convinces V with probability δ, Ext₀^{P*} outputs a spatiotemporal point st* plus auxiliary information aux, and Ext₁^{P*}(st*, aux) convinces V′ in Π′ that it is at st* with probability at least poly(δ) − negl(λ). The auxiliary protocol Π′ is existentially quantified: one sound test suffices to certify the extracted point.

2. A UC-secure definition of spatiotemporal MPC. The authors formulate security in the universally composable framework, extended with the extraction notion above, capturing input privacy, physical consistency (no malicious party can make the functionality act on spatiotemporal data inconsistent with its physical state), and composability. The formal definitions appear as Definitions 14 and 15; the informal Definition 1 is explicitly described as simplified and not matching any single formal definition in the main body.

3. Constructions of commit-and-prove of spatiotemporal knowledge (Theorem 1.1, informal). UC-secure commit-and-prove of spatiotemporal knowledge exists (1) in the common reference string (CRS) model assuming QLWE, with knowledge soundness against quantum-polynomial-time provers without pre-shared entanglement, and (2) in the quantum random oracle model (QROM), with knowledge soundness against QPT provers with unbounded pre-shared entanglement.

4. General-purpose spatiotemporal MPC and its quantum extension (Theorems 1.2 and 1.3, Corollary 1). Assuming semi-honest post-quantum MPC and UC-secure commit-and-prove of spatiotemporal knowledge, UC-secure spatiotemporal MPC exists. Assuming PQ-OWFs, UC-secure MPQC, and UC-secure zero-knowledge commit-and-prove of spatiotemporal knowledge, UC-secure spatiotemporal MPQC exists — where parties hold quantum inputs and classical spatiotemporal information. Combining with prior work, UC-secure post-quantum MPC plus the commit-and-prove protocol yields UC-secure spatiotemporal MPQC.

Main Findings

• Physical presence is defined by what a prover can do, not by a mathematical relation. Rather than encoding "being at point st" as a relation, the framework defines it as the ability to complete a sound spatiotemporal verification protocol. The extracted point is certified by re-using the extracted prover in an auxiliary sound protocol Π′; the contrapositive argument is that a fabricated point could not pass any sound protocol.

• The definition subsumes standard position-verification soundness. When the claimed position is public, the extractor can output that position and take Π′ = Π. The added strength appears when the position is hidden, as in zero-knowledge position verification and in the MPC setting.

• Extraction must respect the adversary's physical resources. The proving strategy produced by Ext₁ must obey the causal and spatial restrictions of the adversarial model; extraction may not introduce a new agent at the claimed position or supply communication or entanglement the adversary did not have, or the verification would certify the extractor's resources instead of the adversary's presence.

• Extraction must be simulatable, not just certifiable. Because extracting information can disturb a quantum adversary's state and change its later behaviour, the authors strengthen operational certification with simulation while extracting. The technical overview describing Sections 2.2–2.4 (the commit-and-prove construction, the classical-computation compiler, and the quantum extension) is cut off in the supplied content.

• Pre-shared entanglement is the key adversarial resource handled in Theorem 1.1. Entanglement distributed among spatially separated components of a malicious prover lets those components coordinate attacks across locations and is described as a significant obstacle to standard extraction; the CRS construction therefore excludes it, while the QROM construction tolerates unbounded amounts.

• The compiler is GMW-style. Commit-and-prove of spatiotemporal knowledge is used in the way traditional commit-and-prove is used in the GMW compiler, upgrading a semi-honest MPC protocol into a maliciously secure one for spatiotemporal functionalities. The authors state that the spatiotemporal setting introduces unique challenges, discussed in their Section 2.

• Plain-model, stand-alone variants are possible. Because a CRS can be generated by quantum-secure coin-flipping, the CRS in Theorem 1.1 can be replaced to obtain plain-model zero-knowledge commit-and-prove of spatiotemporal knowledge, downgrading UC security to stand-alone security; the same substitution applies to Theorems 1.2, 1.3 and Corollary 1. Cited coin-flipping options: constant-round from QLWE plus QFHE; polynomial-round from semi-honest OT or from PQ-OWFs plus quantum communication; constant-round from semi-honest OT with relaxed simulation quality.

• No quantitative evaluation is reported. The supplied content contains no benchmarks, dataset sizes, concrete parameter choices, timing measurements, or implementation results; the constructions are presented as feasibility results.

• Spatiotemporal information is modelled classically. Even in the quantum extension, the authors model spatiotemporal data classically, noting that quantum-mechanical notions of position, relational time, quantum clocks and quantum reference frames have not, to their knowledge, produced a canonical operational model suitable for this cryptographic setting; they leave a quantum analogue to future work.

Methodology in Plain English

The authors start from an observation about other "physical" cryptographic tasks — proofs of quantumness and position verification — that all define a physical property through the ability to pass a test. They reverse the usual order: instead of trying to write down a mathematical relation that means "is at location L at time T", they take passing a sound position-verification protocol as the definition of being there.

Concretely, they design an extractor with two parts. The first part interacts with a malicious prover during the protocol and outputs the spacetime point the prover is effectively using, plus some auxiliary state. The second part uses that auxiliary state to run a fresh, sound position-verification protocol at the extracted point. If the extracted point were fake, this second stage could not succeed — so a successful second stage acts as a certificate. The extractor is constrained to use only the physical resources the adversary itself had, so the certificate is about the adversary, not about the extractor.

With this extraction notion in hand, they define UC security for spatiotemporal functionalities, then build a commit-and-prove protocol that lets a party commit to an ordinary input and to hidden spatiotemporal information and prove statements about them, with the guarantee that the committed spatiotemporal data is physically consistent. This protocol is then plugged into a GMW-style compiler over a semi-honest post-quantum MPC protocol to obtain malicious security for general spatiotemporal functionalities, and the framework is extended to the case where inputs are quantum states.

Why This Matters

Impact on research. The paper opens a new interface between position verification and general-purpose MPC. Existing position-based MPC (Chandran et al.) supports functionalities depending on public locations; zero-knowledge position verification (Girish et al.) is a proof functionality with relaxed soundness — convincing a verifier only that the prover lies within a large region. The authors argue this relaxation is not a defect but an inherent tension: an exact spacetime point in a public statement is revealed by that statement, while a region statement hides the point and cannot by itself drive a functionality. Spatiotemporal MPC is proposed as the reconciliation — fine-grained information used internally, hidden except as implied by the output. The work also contrasts itself with the concurrent notion of quantum localization (Bartusek et al.), where extraction localizes an unclonable quantum object and tracks its trajectory, rather than identifying a party's effective MPC input.

Real-world applications (as given in the paper):

• Privacy-preserving regional analytics: a service provider such as an LLM provider offering different subscription plans across regions, jointly computing conversion rates, demand estimates, fraud rates, or candidate price tiers, where the computation uses locations consistent with participants' actual behaviour while hiding both records and location data.
• Anonymous voting with geography-dependent representation: binding secret ballots to the correct district so the appropriate aggregation rule applies — motivated by the U.S. Electoral College (electors equal to congressional delegation size, winner-take-all except in Maine and Nebraska) and the European Parliament's degressive proportionality; also suggested for shareholder voting, union governance, digital cooperatives, and cross-regional online communities.
• Collaborative augmented reality: preventing a malicious device from manipulating a shared scene via a fictitious location or trajectory, while keeping camera data, spatial maps, and user interactions private.
• Other listed applications: privacy-preserving proximity services, location-dependent access control, collaborative robotics, traffic and mobility analytics, disaster response, contact tracing, and enforcement of geographic or temporal constraints on distributed computations.

Industry relevance. The constructions need little quantum capability beyond running the underlying quantum position-verification protocol, and both quantum position verification and MPC have seen separate implementation progress. The authors suggest that, after cryptographic and systems-level optimization, their protocols could become candidates for near-term (NISQ-era) implementation, potentially giving the first experimental demonstration of spatiotemporal MPC.

Future Directions

• Optimized and black-box constructions. The current protocols are explicitly framed as feasibility results; the authors suggest combining their ideas with MPC-in-the-head techniques to obtain black-box constructions with better modularity and efficiency.

• Round complexity and non-interactive secure computation. The constructions invoke multiple position-verification instances spanning the MPC execution to keep each party at its hidden authenticated position. For two- or three-round protocols, the relevant spatiotemporal interval might be narrowed to when a party sends its response; a formal treatment would require analysing concurrent/parallel security when composed with quantum NISC protocols.

• Integration with other position-verification protocols, including quantum localization. The framework can be instantiated with any "nice" PV protocol whose verdict is a classical predicate over the classical transcript, timing information, and verifier randomness — potentially covering hardware, bounded-retrieval, and bounded-quantum-storage models. Integrating the stronger quantum-localization notion is blocked because its verification relies on a structured classical oracle in the ideal-obfuscation model, yielding no polynomial-size NP verification circuit for the authors' zero-knowledge proofs.

• General physical functionalities, and where the framework breaks. The authors sketch an "argument of quantumness knowledge" extension, but explain that a naive "argument of quantum-depth knowledge" fails: letting the extractor call a depth-d prover repeatedly would let it assemble a computation of arbitrarily large polynomial depth, so the extracted resource would reflect the extractor-plus-prover combination rather than the prover's own capability. Whether this is inherent to MPC over general physical functionalities is left open.

Target Audience

Cryptography researchers working on MPC, UC security, and proof systems; quantum-information researchers working on position verification and unclonable cryptography; and graduate students or advanced practitioners who already know the real/ideal simulation paradigm and want a rigorous entry point into physically grounded secure computation. Readers looking for implementation results, benchmarks, or concrete parameter recommendations will not find them in this paper.

Authors’ abstract

Secure multiparty computation (MPC) enables mutually distrustful parties to compute on private digital inputs. We initiate the study of spatiotemporal MPC, extending this paradigm to functionalities whose inputs additionally depend on physical facts such as the parties' locations, times, or trajectories. Such protocols must simultaneously hide spatiotemporal information and ensure its physical consistency: a malicious party should not be able to make the functionality operate on a spatiotemporal input inconsistent with its actual physical state. The main conceptual challenge is to formulate extraction of spatiotemporal information within the simulation-based security framework. We introduce arguments of spatiotemporal knowledge, following the principle "I prove, therefore I am:" rather than defining physical presence directly through a mathematical relation, we define it operationally through the ability to complete a sound spatiotemporal verification protocol. Accordingly, an extractor recovers a spatiotemporal point from a successful prover and certifies its physical validity by using the extracted prover to succeed in an auxiliary spatiotemporal verification protocol. Building on this notion, we define universally composable (UC) security for spatiotemporal MPC, capturing privacy, physical consistency, and composability. We provide constructions achieving this new MPC notion. We first construct UC-secure commit-and-prove of spatiotemporal knowledge: in the CRS model under LWE against quantum provers without pre-shared entanglement, and in the QROM against quantum provers with unbounded pre-shared entanglement. Using these protocols, we obtain UC-secure spatiotemporal MPC from semi-honest post-quantum MPC. We also extend our framework to support quantum functionalities with classical spatiotemporal input.