In a Multi-Prover environment, how little spatial separation is sufficient to assert the validity of an NP statement in Perfect Zero-Knowledge ? We exhibit a set of two novel Zero-Knowledge protocols for the 3-COLorability problem that use two (local) provers or three (entangled) provers and only require exchanging one edge and two bits with two trits per prover. This greatly improves the ability to prove Zero-Knowledge statements on very short distances with very basic communication gear.
In a Multi-Prover environment, how little spatial separation is sufficient to assert the validity of an NP statement in Perfect Zero-Knowledge ? We exhibit a set of two novel Zero-Knowledge protocols for the 3-COLorability problem that use two (local) provers or three (entangled) provers and only require exchanging one edge and two bits with two trits per prover. This greatly improves the ability to prove Zero-Knowledge statements on very short distances with very basic communication gear.
We initiate the study of relativistic zero-knowledge quantum proof of knowledge systems with classical communication, formally defining a number of useful concepts and constructing appropriate knowledge extractors for all the existing protocols in the relativistic setting which satisfy a weaker variant of the special soundness property due to Unruh (EUROCRYPT 2012). We show that there exists quantum proofs of knowledge with knowledge error 1/2 + negl(η) for all relations in NP via a construction of such a system for the Hamiltonian cycle relation using a general relativistic commitment scheme exhibiting the fairly-binding property due to Fehr and Fillinger (EUROCRYPT 2016). We further show that one can construct quantum proof of knowledge extractors for proof systems which do not exhibit special soundness, and therefore require an extractor to rewind multiple times. We develop a new multi-prover quantum rewinding technique by combining ideas from monogamy of entanglement and gentle measurement lemmas that can break the quantum rewinding barrier. Finally, we prove a new bound on the impact of consecutive measurements and use it to significantly improve the soundness bound of some existing relativistic zero knowledge proof systems, such as the one due to Chailloux and Leverrier (EUROCRYPT 2017).
The existing multi-prover interactive proof framework suffers from incompleteness in terms of soundness and zero-knowledge that is not completely addressed in the literature. The problem is that the existing definitions of what is local, entangled and no-signalling are not rich enough to capture the full generality of multi-prover interaction. In general, existing proofs do not take into account possible changes in locality either during a protocol's execution or when protocols are composed together. This is especially problematic for zero-knowledge, as composing commitments is the only known way of achieving zero-knowledge outside of some NP-intermediate languages.
In this work, we introduce the locality hierarchy for multiparty (multi-round) interaction, and for the first time a complete definition of multi-round multiparty no-signalling distributions and strategies. Within this framework, we define the locality of a protocol which involves the provers, verifiers, simulators and distinguishers. We show that an existing protocol for NEXP [BFL90] and a zero-knowledge variant we introduce are sound in a local sense, but are zero-knowledge in a sense that is even stronger than usually understood. All prior claims of zero-knowledge proofs in the multi-prover model were actually incorrect. Finally, we present similar constructions for entangled and no-signalling prover sets for NEXP and EXP based on [IV12] and [KRR14] using new multi-prover commitment schemes.
Single-prover interactive proofs can recognize PSPACE; if certain complexity assumptions are made, they can do so in zero-knowledge. Generalizing to multiple non-communicating provers extends this class to NEXP, and at the same time removes the complexity assumption needed for zero-knowledge. \n \nHowever, it was recently discovered that the non-communication condition might be insufficient to guarantee soundness. The provers can form joint randomness through non-local computation without communicating. This could break protocols that rely on the statistical independence of the provers. \n \nIn this work, we analyze multi-prover interactive proofs under the constraint of statistical isolation which prohibits non-local computation. We show that there exists perfect zero-knowledge proofs for NEXP under statistical isolation.
The recent MIP*=RE theorem of Ji, Natarajan, Vidick, Wright, and Yuen shows that the complexity class MIP* of multiprover proof systems with entangled provers contains all recursively enumerable languages. Prior work of Grilo, Slofstra, and Yuen [FOCS '19] further shows (via a technique called simulatable codes) that every language in MIP* has a perfect zero knowledge (PZK) MIP* protocol. The MIP*=RE theorem uses two-prover one-round proof systems, and hence such systems are complete for MIP*. However, the construction in Grilo, Slofstra, and Yuen uses six provers, and there is no obvious way to get perfect zero knowledge with two provers via simulatable codes. This leads to a natural question: are there two-prover PZK-MIP* protocols for all of MIP*? In this paper, we show that every language in MIP* has a two-prover one-round PZK-MIP* protocol, answering the question in the affirmative. For the proof, we use a new method based on a key consequence of the MIP*=RE theorem, which is that every MIP* protocol can be turned into a family of boolean constraint system (BCS) nonlocal games. This makes it possible to work with MIP* protocols as boolean constraint systems, and in particular allows us to use a variant of a construction due to Dwork, Feige, Kilian, Naor, and Safra [Crypto '92] which gives a classical MIP protocol for 3SAT with perfect zero knowledge. To show quantum soundness of this classical construction, we develop a toolkit for analyzing quantum soundness of reductions between BCS games, which we expect to be useful more broadly. This toolkit also applies to commuting operator strategies, and our argument shows that every language with a commuting operator BCS protocol has a two prover PZK commuting operator protocol.
Identity verification is the process of confirming an individual's claimed identity, which is essential in sectors like finance, healthcare, and online services to ensure security and prevent fraud. However, current password/PIN-based identity solutions are susceptible to phishing or skimming attacks, where malicious intermediaries attempt to steal credentials using fake identification portals. Alikhani et al. [Nature, 2021] began exploring identity verification through graph coloring-based relativistic zero-knowledge proofs (RZKPs), a key cryptographic primitive that enables a prover to demonstrate knowledge of secret credentials to a verifier without disclosing any information about the secret. Our work advances this field and addresses unresolved issues: From an engineering perspective, we relax further the relativistic constraints from 60m to 30m, and significantly enhance the stability and scalability of the experimental demonstration of the 2-prover graph coloring-based RZKP protocol for near-term use cases. At the same time, for long-term security against entangled malicious provers, we propose a modified protocol with comparable computation and communication costs, we establish an upper bound on the soundness parameter for this modified protocol. On the other hand, we extend the two-prover, two-verifier setup to a three-prover configuration, demonstrating the security of such relativistic protocols against entangled malicious provers.
Zero-knowledge and multi-prover systems are both central notions in classical and quantum complexity theory. There is, however, little research in quantum multi-prover zero-knowledge systems. This paper studies complexity-theoretical aspects of the quantum multi-prover zero-knowledge systems. This paper has two results: 1.QMIP* systems with honest zero-knowledge can be converted into general zero-knowledge systems without any assumptions. 2.QMIP* has computational quantum zero-knowledge systems if a natural computational conjecture holds. One of the main tools is a test (called the GHZ test) that uses GHZ states shared by the provers, which prevents the verifier's attack in the above two results. Another main tool is what we call the Local Hamiltonian based Interactive protocol (LHI protocol). The LHI protocol makes previous research for Local Hamiltonians applicable to check the history state of interactive proofs, and we then apply Broadbent et al.'s zero-knowledge protocol for QMA \cite{BJSW} to quantum multi-prover systems in order to obtain the second result.