In this work, we report the experimental realization of a zero-knowledge protocol involving two separated verifier–prover pairs; security is enforced via the physical principle of special relativity

Experimental relativistic zero-knowledge proofs. Pouriya Alikhani, Nicolas Brunner, Claude Crépeau, Sébastien Designolle, Raphaël Houlmann, Weixu Shi, Nan Yang & Hugo Zbinden. Nature volume 599, pages 47–50 (2021). Nov 3 2021. https://www.nature.com/articles/s41586-021-03998-y

Abstract: Protecting secrets is a key challenge in our contemporary information-based era. In common situations, however, revealing secrets appears unavoidable; for instance, when identifying oneself in a bank to retrieve money. In turn, this may have highly undesirable consequences in the unlikely, yet not unrealistic, case where the bank’s security gets compromised. This naturally raises the question of whether disclosing secrets is fundamentally necessary for identifying oneself, or more generally for proving a statement to be correct. Developments in computer science provide an elegant solution via the concept of zero-knowledge proofs: a prover can convince a verifier of the validity of a certain statement without facilitating the elaboration of a proof at all1. In this work, we report the experimental realization of such a zero-knowledge protocol involving two separated verifier–prover pairs2. Security is enforced via the physical principle of special relativity3, and no computational assumption (such as the existence of one-way functions) is required. Our implementation exclusively relies on off-the-shelf equipment and works at both short (60 m) and long distances (≥400 m) in about one second. This demonstrates the practical potential of multi-prover zero-knowledge protocols, promising for identification tasks and blockchain applications such as cryptocurrencies or smart contracts4.

Introduction.

In a foreign city where you know absolutely no one, you go to an automatic teller machine to obtain a handful of local cash. You have never heard of the bank owning that teller machine, yet when requested for your Personal Identification Number to obtain money you blindly provide it. No joke, you give away that super unique information to a complete stranger. But why? Because of the cash you get in return? There is actually zero solid reason to trust that teller machine. You should never have to give away this private information to anyone at all! But how could we prove who we are without giving away such a secret piece of data? The idea behind zero-knowledge proofs was born in the middle of the 1980’s [1] and formalises the possibility to demonstrate knowledge of a secret information without divulging it. A natural application is the task of identification, where a user can demonstrate their identity via the knowledge of a secret proof of a mathematical statement they created and published. A well-known example is the RSA cryptosystem [2] in which the mathematical secret is the factorisation into two huge prime numbers of an even larger number. In this work we consider the problem of three-colouring of graphs: an instance is a graph (nodes and edges attaching some of them to one another) and a proof of three-colourability assigns to each vertex one out of three possible colours in a way that any two vertices connected by an edge have different colours, see Fig. 1(a). Some graphs are three-colourable, some are not, and the general problem of deciding whether a graph is three-colourable has no known efficient solution. However, given a colouring it is extremely easy to efficiently check whether the end points of every edge are assigned different colours. For this reason, three-colourability is a problem in NP, the class of all problems that are efficiently verifiable given a solution. Moreover, it is also NP-complete because an instance of any problem in NP can be efficiently simulated by an instance of three-colourability, so that if this latter were in P, the class of all problems efficiently solvable, then we would have P = NP, an equality which has been the most famous challenge of theoretical computer science for the last half century and which remains unsolved. A zero-knowledge proof for three-colourability has been introduced in Ref. [3] by assuming the existence of one-way functions, that is, functions that can be efficiently computed but for which finding a preimage of a particular output cannot. The zero-knowledge proof guarantees that upon participation to such an interaction, a prover would convince a verifier of the validity of the statement when it is indeed valid (completeness), would not convince the verifier when it is invalid (soundness), while not allowing the latter to improve their ability to find a three-colouring (zero-knowledge), but this is under the assumption that one-way functions exist. It is widely believed that a zero-knowledge proof for any NP-complete problem such as three-colourability is not possible without this extra computational assumption. If not, this would lead to vast implications in the world of complexity [4]. However, this feature is generally undesirable as it significantly weakens the long-term security of such zero-knowledge protocols, which are used, e.g., in certain crypto-currencies [5]. This may have important consequences, as security would be fully compromised if the specific one-way function used in the protocol is (later) found to be efficiently invertible. This aspect is particularly relevant given recent advances on quantum computing [6, 7]. 

Remarkably, it is possible to devise zero-knowledge protocols without the need of any computational assumption. The key idea, as developed by Ben-Or, Goldwasser, Kilian and Wigderson [9], is to generalise the interactive proof model such that several provers are now trying to convince a verifier of the three-colourability of a graph in perfect zero-knowledge without the need of any further assumption. Intuitively, this approach reflects the strategy used by police investigators when interrogating suspects in separate rooms in order to discern the truth more easily: it is harder to collectively lie about the validity of a statement when interrogated separately. The key difference between the multi-prover scenario and the original definition of interactive proof rests in the possibility to prevent several provers from talking to each other, a single prover always being able to talk to themself. This naturally suggests the use of spatial separation to enforce the impossibility to communicate [10, 11], at least for some short period of time: assuming the principle of special relativity (nothing can signal faster than the speed of light) and sending queries to the different provers simultaneously, there is a short time window during which they are physically unable to signal between each other. So far, these ideas have been mainly of purely theoretical interest, as known protocols required extremely large information transfer between the provers and verifiers, which prohibited their implementation.

In this work, we report experimental realisations of relativistic zero-knowledge proofs for an NP-complete problem (three-colourability). Specifically we develop an efficient implementation of the protocol recently established in Ref. [12] for two separated verifier-prover pairs. In practice, key challenges involve the generation of adequate large three-colourable graphs, as well as an efficient management of the randomness shared between the provers, achieved via suitable error-correcting codes. We report on two experiments: first, using Global Positioning System (GPS) clocks to synchronise the two verifiers, we performed the protocol at a distance of 400 m; second, using a triggering fibre between the two verifiers, we conducted the same test at a shorter distance of 60 m. In both cases, the full running time was about one second. The first implementation shows that the protocol at large distances is rather effortless since the wide relativistic separation only demands a moderate speed on the provers’ side; the second one demonstrates a clear potential for serviceable applications. Importantly, the security is enforced by relativistic constraints, and does not rely on any computational hypothesis such as the existence of one-way functions. Note that the aforementioned NP-completeness guarantees that any application based on a problem in NP can be (polynomially) cast into an instance of our protocol. For example, if you trust the Advanced Encryption Standard (AES) as a secure cryptographic primitive, you can transform AES instances into three-colourable graphs. Our implementation achieves security against classically correlated provers and we discuss the prospects of extending the security to the general case of quantum-mechanically correlated provers below.