André Chailloux
email: andre.chailloux@inria.fr

Yann Barsamian

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Relativistic zero-knowledge protocol for NP over the internet unconditionally secure against quantum adversaries André Chailloux * and Yann Barsamian †

Inria de Paris, EPI COSMIQ

Relativistic cryptography is a proposal for achieving unconditional security that exploits the fact that no information carrier can travel faster than the speed of light. It is based on spacetime constraints but doesn't require quantum hardware. Nevertheless, it was unclear whether this proposal is realistic or not. Recently, Alikhani et al. [ABC + 21] performed an implementation of a relativistic zero-knowledge for NP. Their implemented scheme shows the feasibility of relativistic cryptography but it is only secure against classical adversaries. In this work, we present a new relativistic protocol for NP which is secure against quantum adversaries and which is efficient enough so that it can be implemented on everyday laptops and internet connections. We use Stern's zeroknowledge scheme for the Syndrome Decoding problem, which was used before in post-quantum cryptography. The main technical contribution is a generalization of the consecutive measurement framework of [START_REF] Chailloux | Relativistic (or 2-prover 1-round) zero-knowledge protocol for np secure against quantum adversaries[END_REF] to prove the security of our scheme against quantum adversaries, and we perform an implementation that demonstrates the feasibility and efficiency of our proposed scheme.

I. INTRODUCTION

a. Context. There is a strong conceptual and practical appeal for building cryptographic schemes which have unconditional security meaning that they cannot be attacked by any classical or quantum computer, even with unlimited computing power. Quantum Key Distribution [START_REF] Bennett | Quantum cryptography: Public key distribution and coin tossing[END_REF] is a prime example of this, and a huge amount of work has been done to understand its security and perform efficient implementations. Relativistic cryptography is another proposal for achieving unconditional security that exploits the no superluminal signaling (NSS) principle. NSS states that no information carrier can travel faster than the speed of light. The interest of relativistic cryptography is that it can perform coin flipping and bit commitment protocols with unconditional security which is known to be impossible even using quantum information [START_REF] Mayers | Unconditionally secure quantum bit commitment is impossible[END_REF][START_REF] Lo | Is quantum bit commitment really possible?[END_REF], so relativistic cryptography and quantum cryptography complete each other well for protocols with unconditional security. In order to perform protocols in relativistic cryptography, there has to be some strict space-time constraints between the different agents performing the protocol but they can be done without quantum hardware. The goal of this work is to show the practicality of relativistic cryptography by presenting a new relativistic zero-knowledge protocol for NP and demonstrating its feasibility in reallife conditions, on standard laptops using a standard internet connection. This is the first time a protocol for relativistic cryptography is implemented in this setting and shows these are much simpler to perform than what we could have expected.

b. Relativistic cryptography. The idea of using the NSS principle for cryptographic protocols started in a work by Kent [Ken99] as a way to physically enforce a no-communication constraint between different agents (a similar idea already existed in multi-prover interactive proofs [START_REF] Ben-Or | Multi-prover interactive proofs: How to remove intractability assumptions[END_REF], but without any explicit implementation proposal). The original goal of Kent was to bypass the no-go theorems for quantum bit-commitment, and there has been many proposals for unconditionally secure relativistic bit commitment [START_REF] Kent | Unconditionally secure bit commitment with flying qudits[END_REF][START_REF] Kent | Unconditionally secure bit commitment by transmitting measurement outcomes[END_REF][START_REF] Kaniewski | Secure bit commitment from relativistic constraints[END_REF]. The original idea of [START_REF] Ben-Or | Multi-prover interactive proofs: How to remove intractability assumptions[END_REF] was also revisited by Crépeau et al. in [START_REF] Crépeau | Two provers in isolation[END_REF]. Based on this work, Lunghi et al. devised a relativistic bit commitment protocol involving only four agents, two for Alice and two for Bob [LKB + 15] -hereafter called the F Q relativistic bit commitment. Their protocol is secure against quantum adversaries and a multi-round variant, with longer duration time, was shown to be secure against classical adversaries [LKB + 15, CCL15, FF15]. While these protocols only seemed of theoretical interest at first, recent implementations have convincingly demonstrated that the required timing and location constraints can be efficiently enforced. In [VMH + 16], the authors performed a 24hour-long bit commitment with the pairs of agents standing 8km apart. c. Relativistic zero-knowledge protocols for NPcomplete problems. One important application of commitment schemes is zero-knowledge protocols. It was first observed in [START_REF] Chailloux | Relativistic (or 2-prover 1-round) zero-knowledge protocol for np secure against quantum adversaries[END_REF] that one can use the single round F Q relativistic bit commitment scheme to construct a relativistic zero-knowledge protocol for the Hamiltonian cycle problem, which is NP-complete with unconditional security even against entangled adversaries. The communication cost of this protocol however becomes quickly prohibitive and the necessary space-time constraints can't be ensured. A more recent proposal [CMS + 20] constructs a variation over the standard 3 coloring zero-knowledge protocol. They manage to drastically reduce the communication at each round. However, the number of repetitions required is quite large to obtain classical security and is prohibitively too large to obtain security against quantum adversaries. This proposal (the variant secure In this letter, we present a new proposal for relativistic zero-knowledge for NP based on the Syndrome Decoding problem. This is an NP-complete problem which is also believed to be hard against quantum computer for random instances. We will use here Stern's zero-knowledge scheme [START_REF] Stern | A new identification scheme based on syndrome decoding[END_REF] which was used before for post-quantum signature schemes with the F Q relativistic string commitment. This protocol will have a moderate amount of communication, but also a small amount of rounds to decrease the soundness error. A comparison between the different schemes is presented in Table I.

Our main technical contribution is to prove the security of this protocol against quantum adversaries. In order to do so, we relate its security to an entangled game and prove a lower bound on this game using a new quantum learning lemma on consecutive quantum measurements, in the similar vein of [START_REF] Chailloux | Relativistic (or 2-prover 1-round) zero-knowledge protocol for np secure against quantum adversaries[END_REF]. We then implement the key steps of this protocol and show it is efficient enough so that the space-time constraints can be satisfied using standard computers and a standard internet connection. The only specific hardware we require are synchronized clocks.

II. PRELIMINARIES

a. The relativistic F Q string commitment. We recall here the relativistic F Q string commitment that we will use in our relativistic zero-knowledge protocol. We consider a prover P that wants to commit a string z ∈ F P to a verifier V. Both parties, have agents respectively P 1 , P 2 and V 1 , V 2 . P 1 , V 1 are at a certain spatial location and P 2 , V 2 at a different spatial location, at a distance D from the first one. The committed string is in F P and we also consider a set F Q ⊇ F P , where Q is a parameter of the commitment scheme. The protocol (when followed by honest players) consists of 3 phases: preparation, commit,and reveal. The string commitment protocol goes as follows.

1. Preparation phase:

P 1 , P 2 (resp. V 1 , V 2 ) share a random number a ∈ F Q (resp. b ∈ F Q ).
2. Commit phase: V 1 sends b to P 1 , who immediately returns y = a + z * b where z ∈ F P is the committed string. We map z ∈ F P as an element of F Q , since F P ⊆ F Q , the operations + and * used are those of F Q .

3. Reveal phase: P 2 reveals the values of z and a to V 2 who checks that y = a + z * b.

This protocol has the following timing properties: let τ 1 the time when V 1 sends b and τ 2 the time when V 2 receives (z, a). If τ 2 -τ 1 < D/c where c is the speed of light then the NSS principle ensures that the message (z, a) is independent of b. The following security properties were proven in [LKB + 15]:

• It is perfectly hiding: the verifiers don't have any information about z after the commit phase.

• It is binding: informally, the provers can change their mind about z after the commit phase only with vanishingly small probability.

b. The syndrome decoding problem. The Hamming weight |v| H of a binary vector is the number of 1 coordinates of this vector.

Problem 1 (Syndrome Decoding -SD(n, k, w)).

• Instance: a matrix H ∈ {0, 1} (n-k)×n , a column vector s ∈ {0, 1} n-k , • Goal: output a column vector e ∈ {0, 1} n such that He = s and |e| H = w.

The Syndrome Decoding problem is NP-complete and also believed to be hard on random instances even against quantum computers. It is the canonical hard problem for code-based cryptography. In order to construct a zeroknowledge protocol for this scheme, we first have to split the instances of our problem into Yes instances and No instances. For the SD(n, k, w) problem, Yes instances are the pairs (H, s) such that a solution (i.e. a vector e ∈ {0, 1} n st. He = s and |e| H = w) exists. No instances are the pairs (H, s) where no such solution exists.

III. OUR PROPOSAL FOR RELATIVISTIC ZERO-KNOWLEDGE FOR NP

A. Brief definition of a zero-knowledge scheme

In a zero-knowledge protocol between a prover P and verifier V, they are given an instance of a computational problem which is either a Yes or a No instance. P wants to convince V that they are in a Yes instance but he doesn't want to reveal any other information to V. Zeroknowledge protocols have many applications in cryptography, for example for identification schemes. If we start from a Yes instance and both players are honest then V should be convinced and always accept (Completeness). If P is honest then V shouldn't learn anything more from its interaction with P than the fact that they have a Yes instance (Zero-knowledge). If we start from a No instance and for any cheating prover P, V should reject with high probability (Soundness). The honest prover could in theory be computationally unbounded, but in our case, we only require a polynomial time prover, which additionally knows a solution to the problem for Yes instances. We give him this solution in an Auxiliary input. However, cheating provers stay computationally unbounded.

B. Description of our 1-round relativistic zero-knowledge protocol for NP

We combine the F Q relativistic string commitment and Stern's 1-round zero-knowledge protocol for SD in order to get our 1-round relativistic zero-knowledge protocol for SD. Again, P and V are split into 2 agents P 1 , P 2 and V 1 , V 2 . In the honest case, we require V 1 , V 2 to be at some distance D. We present this protocol in Figure 1. This description is self-contained but we discuss more in length this protocol as well as Stern's original zeroknowledge protocol in Appendix B, which can be a good start for those not familiar with the scheme. The timing constraints ensure that for each i ∈ {1, 2}, the message sent by P i is independent of the message sent from V j to P j for j = i.

Input: Integers n, k, w, a matrix H ∈ {0, 1} (n-k)×n , a vec- tor s ∈ {0, 1} n-k . A parameter Q used for the commitment.
Auxiliary input (in the Yes case): A column vector e ∈ {0, 1} n such that |e|H = w and He = s. Pre-processing: P1, P2 agree beforehand on a random permutation σ acting on [n], on a random column vector t ∈ {0, 1} n as well as on 3 strings a1, a2, a3 ∈ F Q . Let

s = Ht. Let also z1 = (σ, s ), z2 = σ(t), z3 = σ(t ⊕ e),
where permuting a vector means permuting its coordinates.

Treat each zi as an element of FQ (we choose Q large enough so that we can embed the sets in which z1, z2, z3 are into F Q ).

Protocol:

1. Phase 1: V1 sends 3 random strings b1, b2, b3 ∈ F Q at time τ 1 . P1 sends back yi = ai + bi * zi for each i ∈ {1, 2, 3}. V1 receives these at time θ 1 . 2. Phase 2: V2 sends a uniformly random challenge c ∈ {1, 2, 3} to P2 at time τ 2 . P2 sends z c , a c for the two values c different from c. V2 receives these at time θ 2 .
Checking procedure: The verifier checks the 2 commitments i.e. that y c = a c + b c * z c for c = c, as well as the timing constraints

θ 1 < τ 2 + D/c ; θ 2 < τ 1 + D/c.
He also performs the following checks that come from Stern's zero-knowledge protocol:

• if c = 1, accept iff. |z2 + z3|H = w. • if c = 2, accept iff. H • σ -1 (z3) = s ⊕ s . • if c = 3, accept iff. H • σ -1 (z2) = s .
FIG. 1: 1-round Relativistic zero-knowledge protocol for SD using the F Q commitment scheme.

We prove the security of this scheme. Completeness and the zero-knowledge property follow quite directly from the security of Stern's signature scheme and of the F Q commitment scheme. The main technical contribution of this work is to bound the soundness of this protocol. We prove the following:

Theorem 1. This protocol has perfect completeness, perfect zero-knowledge and has soundness 2 3

+ n!2 4n Q 1/4
if the space-time constraints are satisfied.

This means that for No instances, an all powerful cheating prover can convince the verifier wp. at most

2 3 + n!2 4n Q 1/4
. By taking Q = 10 12 n!2 4n , the soundness becomes 2 3 + 0.001. This seems like a very large Q but recall that sending an element of F Q requires log 2 (Q) and performing additions and multiplications in a field of this size is still very efficient. We give the full proof of this Theorem in Appendix C.

IV. FULL PROTOCOL AND IMPLEMENTATION

Our full loss-tolerant relativistic zero-knowledge protocol for NP is described in Figure 2. We repeat our 1-round protocol R times sequentially and allow for a λ fraction of rounds where the space-time constraints are not satisfied, for eg. because of losses in the signal. We extend our security proof to this full protocol in Appendix D.

a. Timing constraints. We added an extra parameter T shif t that will make the space-time constraints easier to satisfy. For round i, let

T Phase1 i = θ 1 i -τ 1 i and T Phase2 i = θ 2 i -τ 2 i .
In phase 1, V 1 sends 3 strings in F Q , P 1 does a computation and sends back 3 strings in F Q .

In phase 2, V 2 sends a challenge in {1, 2, 3} and gets back 2 messages in F Q . This explains why phase 1 is longer than phase 2. The timing constraints become for each i:

θ 1 i < τ 2 i + D/c ⇒ T Phase1 i -T Shift < D/c (1)
θ 2 i < τ 1 i + D/c ⇒ T Phase2 i + T Shift < D/c (2)
Here, we see why we use T Shift . Since the 2 phases take different times, the first constraint would be harder to achieve than the second one with T Shift = 0. By taking

T Shift to be an estimate of 1 2 T Phase1 i -T Phase2 i
for an average i, we make the two constraints essentially equally hard to satisfy.

b. Our two scenarios. We perform a demonstration of this full scheme using only regular laptops as well as standard network links (ethernet or wifi). We run the experiment in 2 different scenarios.

1. V 1 and P 1 are in the same room and are connected through a direct ethernet cable. V 2 and P 2 are in a different location but also connected through an ethernet cable. The distance between V 1 and V 2 is about 400km

Parameters: (n,k,w) for the SD problem. A parameter Q for the commitment used. A parameter D gives the distance between the 2 verifiers, and a time parameter ∆T to delimit the time of a round, a time parameter T Shift to determine the time shift between the 2 phases of the protocol. A number of rounds R and an allowed fraction of losses λ.

1. The 2 provers and verifiers agree together on an initial time T1 on which they start the protocol.

2. For i from 1 to R: run the 1-round relativistic ZK protocol with the F Q commitment scheme. V1 sends his first message at time τ 1 i = T1 + (i -1) * ∆T , and V2 sends his first message at time

τ 2 i = T1 + (i -1) * ∆T + T Shift . Let θ 1
i the time at which V1 receives the message from P1 and θ 2 i the time at which V2 receives the message from P2.

3. At the end of the protocol, the verifiers check the space-time constraints for each i from 1 to R, i.e. check that θ 1 i < τ 2 i + D/c and θ 2 i < τ 1 i + D/c. Let F be the number of rounds where these space-time constraints are not satisfied.

The verifiers accept if they accept each iteration of

the zero-knowledge protocol when the space-time constraints were satisfied and if F ≤ λR .

FIG. 2: Full loss-tolerant relativistic zero-knowledge protocol for NP 2. V 1 and P 1 (resp. V 2 , P 2 ) are in different cities and communicate through the usual internet. For each i, V i , P i are about 400km away. We put V 1 , V 2 at distance about 9000km.

These scenarios are illustrated by the following, with examples of cities for which these constraints are satisfied, see Figure 3. FIG. 3: Scenarios that we consider for which we demonstrate the feasibility of our full relativistic zero-knowledge protocol for NP.

c. Specific implementation parameters. Our main protocol that achieves 100 bits of quantum security has the following parameters that appear in the two scenar-

R = 340, F = 22, Q = 2 23209 -1, ω * (G rel Stern ) ≤ 2 3 + 2 -138
Let D be the distance between V 1 and V 2 and let D be the distance between V 1 , P 1 (and also between V 2 , P 2 ). Depending on our scenario, we have the following parameters; where c ≈ 299.8km/sec in the speed of light in vacuum. We show in Figures 4 and5 the real running times of the different phases.

In order to prove soundness, the probability that a cheating prover succeeds in the No case is bounded by P * (R, F ). If we use Equation D1 from Appendix D with ω * (G rel Stern ) ≤ 2 3 + 2 -138 and λ = 22 340 , we obtain P * (R, F ) ≤ 2 -103 . For the completeness error, we estimate the probability that the space-time constraint is not satisfied with p loss ≤ 1 1000 , which is larger than what we actually observe. With this estimate, if we define CE(R, F, p loss ) the probability of failure in the honest case, we obtain from Equation D2 that CE(R, F, p loss ) ≤ 2 -102 . We therefore get the following results, valid for the 2 scenarios: Theorem 2. In our experiments, the probability that the verifier rejects an honest run of the protocol is 2 -102 (Completeness error), the soundness is 2 -103 and it is perfect zero-knowledge.

We performed the benchmarks with our working laptops and desktops both in Paris and Strasbourg. In this first scenario, we actually connected two desktops from the same local network of our research group. In the second scenario, we performed a communication between our local laptop in Paris and a distant desktop in Strasbourg, which is 400km away. We use this setup both for analyzing the running time of our protocol between P 1 , V 1 and P 2 , V 2 in the 2 scenarios. While we didn't perform aa fully integrated implementation into a larger cryptographic protocol, the results we obtain show the feasibility and practicality of our relativistic scheme. Also, it is quite flexible on the locations of the verifiers, as shows by our 2 scenarios and we don't use dedicated hardware for the communication and the computation so one could have even more flexibility with better hardware but again, our goal was to show that this protocol can be implemented without specific hardware. Experimental hardwares are Intel Xeon E5-2650 v3 @2.3 GHz (Haswell) and Intel Core i5-6300U CPU @2.4 GHz (Skylake). Our C code does not use parallelism, and was compiled using the GNU C Compiler 7.5.0, and the GNU Multiple Precision Arithmetic Library (https://gmplib.org/) to perform arithmetic operations in F Q (with Q = 2 23 209 -1 in our example).

We also did experiments for other values of n to show to what extent n can be increased before the space-time constraints are not verified anymore. We present our data with increased n in Appendix E and if one requires a larger security, it is always possible to make V 1 , V 2 farther away or to use better hardware. The authors of [ABC + 21] use parameters for which they have 100 bits of security. This means both the underlying NP-instance should require time 2 100 to solve using the best quantum algorithms and the soundness should be 2 -100 . We will use this benchmarking for comparing the different schemes.

• For [START_REF] Chailloux | Relativistic (or 2-prover 1-round) zero-knowledge protocol for np secure against quantum adversaries[END_REF] is the number of bits in the upper triangle of the adjacency matrix. The factor 2 comes from the fact that the verifier first sends n(n-1) 2 elements of F Q and then the prover sends back n(n-1) 2 elements of F Q . For n = 138, this gives a communication of 1.51 • 10 7 bits which is approximately 1.89M Bytes. In order to achieve soundness of 2 -100 , we use 100 rounds since each round has soundness 1 2 .

• The protocol of [CMS + 20] and its implementation in [ABC + 21] uses a graph G with 588 vertices and 1097 edges. The communication is essentially sending a edge which is of size less than 2 bytes. In order to achieve a soundness of 2 -100 , the number of repetition they use is 10 6 . These parameters achieve classical security. If we wanted to achieve quantum security, [ABC + 21] claims that this would require (21 * |E|) 4 * 100 which is more than 10 19 , as well as a third prover/verifier pair.

• The best quantum algorithm for random instances of the syndrome decoding problem requires time at least 2 0.05869n [KT17] for k ≈ 0.4514n and w ≈ 0.1268n. Our protocol uses n = 1704, k = 769, w = 216 in order to have 100 bits of security. At each round, we have to commit to 3 strings of F Q which means the communication at each round is 6 log 2 (Q). We can prove security of our scheme by taking Q = 10 12 n!2 4n , so the communication is 6 log 2 (Q) = 136177 bits which is equal to 17.03KB.

The number of rounds we take is 340, which allows our protocol to be loss tolerant.

Appendix B: Stern's zero-knowledge protocol for the syndrome decoding problem

We now describe Stern's zero-knowledge protocol [START_REF] Stern | A new identification scheme based on syndrome decoding[END_REF] for the Syndrome Decoding problem. It uses a commitment scheme that we don't explicit here.

Stern's single round zero-knowledge protocol for SD.

Input: Integers k, w, a matrix H $ ← -{0, 1} (n-k)×n , a column vector (called the syndrome) s ∈ {0, 1} n-k . Auxiliary input: A column vector e ∈ {0, 1} n such that |e| H = w and He = s. Protocol:

1. The prover picks a random permutation σ acting on [n] and a random column vector t ∈ {0, 1} n . Let s = Ht, z 1 = (σ||s ), z 2 = σ(t), z 3 = σ(t⊕e), where permuting a vector means permuting its coordinates. He commits to z 1 , z 2 and z 3 separately and sends these commitments y 1 , y 2 , y 3 . 2. The verifier sends a uniformly random challenge c ∈ {1, 2, 3}. 3. The prover opens z c for the two values c different from c. 4. The verifier checks the validity of the 2 commitments and also performs the following checks:

• if c = 1, accept iff. |z 2 + z 3 | H = w. • if c = 2, accept iff. H • σ -1 (z 3 ) = s ⊕ s . • if c = 3, accept iff. H • σ -1 (z 2 ) = s .
This protocol was shown to be secure in [START_REF] Stern | A new identification scheme based on syndrome decoding[END_REF].

We reproduce here the main aspects of this proof. a. Completeness The protocol has perfect completeness. Indeed, in the honest case:

1. |z 2 + z 3 | H = |σ(t) ⊕ σ(t ⊕ e)| H = |σ(e)| H = w. 2. H • σ -1 (σ(t ⊕ e)) = Ht ⊕ He = s ⊕ s . 3. H • σ -1 (σ(t)) = Ht = s .
b. Soundness We are in the NO case, so there are no vectors e such that |e| H = w and He = s. We will prove a proposition which is closely related to the soundness (more precisely the 3-special soundness) of the scheme.

Proposition 1. In the NO case, assume the prover manages to successfully answer the 3 challenges at the same time for the same first message, then he is able to successfully produce 2 different openings for the same commitment.

Proof. We will prove this proposition by contradiction. We are in the NO case, and assume the prover successfully answers the 3 challenges from the same first message M 1 = y 1 , y 2 , y 3 . Assume by contradiction that for each challenge, he uses the same openings for the commitment y 1 , y 2 , y 3 , which we call z 1 = (σ||s ), z 2 , z 3 . Let e 0 = σ -1 (z 2 ) ⊕ σ -1 (z 3 ) = σ -1 (z 2 ⊕ z 3 ). Since the prover successfully answers challenge 1, we have |z 2 ⊕ z 3 | H = w hence |e 0 | H = w. Moreover, since he successfully answers challenges 2 and 3, we have

He 0 = H(σ -1 (z 2 ) + σ -1 (z 3 )) = s ⊕ s ⊕ s = s.
Since we are in the NO case, such an e 0 doesn't exist, hence the contradiction. This means that a cheating prover can cheat with probability at most 2 3 unless he is able to break the binding property of the commitment scheme.

c. Zero-knowledge The protocol is known to be zero-knowledge if the commitment scheme is hiding, we sketch the proof here. The verifier doesn't get any information from the commitments from the hiding property of the commitment scheme. If the verifier sends the challenge c = 1, he receives σ(t) and σ(t + e) from which he cannot recover any information because σ is unknown. For the challenge c = 2, he receives σ, s , σ(t + e) hence he can recover t + e. However, since t is unknown, this looks like a random vector. For the challenge c = 3 he receives σ, s , σ(t) , which are random elements independent of e.

Appendix C: Proof of the security of our 1 round relativistic zero-knowledge protocol

The goal of this section is to prove the security of our 1-round relativistic zero-knowledge for NP presented in Figure 1.

a. Completeness. Completeness follows directly from the completeness of Stern's single round, and from fact that the F Q string commitment has perfect completeness.

b. Zero-knowledge. Stern's signature scheme is perfectly zero-knowledge if the commitment scheme is perfectly hiding, which is the case of the F Q string commitment.

Therefore, the protocol is perfectly zero-knowledge. This zero-knowledge property is also preserved when the scheme is repeated sequentially. c. Soundness. Proving soundness against quantum adversaries, is the main technical challenge of this work. We start from a NO instance meaning that there is no solution to the SD problem and we consider an all powerful cheating prover that wants to convince the verifier such a solution exists.

In all generality, P 1 and P 2 can share an entangled state |Φ . Then P 1 receives B = b 1 , b 2 , b 3 from V 1 and P 2 receives c ∈ {1, 2, 3} from V 2 . They output respectively Y = y 1 , y 2 , y 3 and ZA = {(z c , a c )} c =c . The verifiers then come together and perform the verification step. We assume the timing constraints are verified which ensures that P 1 has no information about chall before sending his message Y and P 2 has no information about B 1 , B 2 , B 3 before sending his message ZA.

Any strategy from the provers can be directly related to the strategy for the following 2-player game where the 2 provers play the role of these 2 players and the verifiers play the role of the referee (i.e. they send the random questions to the provers and check the validity of their outputs). This game, that we call G rel Stern , is defined as follows:

2-player game G rel Stern • Alice receives B = b 1 , b 2 , b 3 ∈ R F Q . Bob receives c ∈ R 1, 2, 3. • Alice outputs Y = y 1 , y 2 , y 3 ∈ F Q and Bob out- puts AZ = {(a c , z c } c =c where each a i ∈ F Q . • Each z i is an element of F Q but we interpret z 1 as
an element (σ, s ) of S 1 = P n × {0, 1} n . Similarly, we interpret z 2 , z 3 as vectors in {0, 1} n using a mapping that we detail after the description of the game. If this mapping fails, the game is lost. Otherwise, we first check the constraint y c = a c + z c * b c for c = c. We then check:

1. if c = 1, we also require |z 2 + z 3 | H = w. 2. if c = 2, we also require H • σ -1 (z 3 ) = s ⊕ s . 3. if c = 3, we also require H • σ -1 (z 2 ) = s .
The " + " and " * " operations we use are the one in F Q = {0, . . . , Q -1} where i is the i th element of F Q . We do our mapping as follows: If z 1 ∈ {0, . . . , S 1 -1}, then we map z 1 to the z th 1 element of S 1 , otherwise, we say that the mapping fails. We do the same thing for z 2 , z 3 , if they are in {0, . . . , 2 n -1} then we can map them to binary vectors, otherwise, we say that the mapping fails. In order for this mapping to be well defined, we must take

Q large enough, more precisely Q ≥ |S 1 | and Q ≥ 2 n .
What is the optimal cheating strategy we can expect for this game? There are some strategies that can win Stern's single round zero-knowledge protocol with probability 2 3 [START_REF] Stern | A new identification scheme based on syndrome decoding[END_REF] from which we can directly derive strategies for this game with 2 classical players that win wp. So what we want to show is that there is no strategy for which the players will win for the 3 challenges received by Bob. What we know from Proposition 1 is that they can't give answers for the 3 challenges simultaneously but this doesn't mean they can't answer each challenge separately. This behavior can appear when we consider entangled strategies. For example in magic square game [START_REF] David Mermin | Simple unified form for the major no-hidden-variables theorems[END_REF][START_REF] Peres | Incompatible results of quantum measurements[END_REF], Alice and Bob can't answer all questions at the same time -because all the constraints of the magic square game lead to a contradiction. However, the entangled value of the game is still 1.

Our main contribution is to bound the entangled value of G rel Stern . As Q increases, the entangled value converges to 2 3 which is optimal. We prove the following theorem Theorem 3.

ω * (G rel Stern ) ≤ 2 3 + n!2 4n Q 1/4 .
From this theorem, our result on the soundness of our 1-round relativistic scheme will follow immediately. In the next section, we will prove the bound in ω * (G rel Stern ).

Bounding the value of the game

We can now prove our lower bound on the entangled value of G rel Stern . Proof of the lower bound of the game. Let any δ > 0 and consider a finite dimensional projective strategy for Alice and Bob that wins the game G rel Stern wp. ω * (G rel Stern ) -δ.

Let P B = {P B Y } and Q c = {Q c
A } be respectively Alice's and Bob's projective measurements for their respective inputs B = b 1 , b 2 , b 3 and c. Alice's output is Y = y 1 , y 2 , y 3 and Bob's output AZ corresponds to the 2 pairs (a c , z c ) for c = c, starting with the one with smallest index. Let |ψ be the quantum state they share.

Fix an input/output pair BY for Alice and let σ BY be the state held by Bob, conditioned on this pair. For each c ∈ {1, 2, 3}, let W c = {AZ : V (Y, AZ, B, c) = 1} be the set of winning outputs for Bob where V (Y, AZ, B, c) is the function that outputs 1 if the game is won on inputs/outputs (B, c)/(Y, AZ), and outputs 0 otherwise.

A necessary condition of validity (for a fixed BY ), is that y i = a i + b i * z i for the z i revealed so for each z i , there is a unique valid a i which is y i -b i * z i . For c = Bob outputs a 2 , z 2 , a 3 , z 3 . A necessary condition is that z 2 , z 3 can each be mapped into the set of binary vectors. Since there is a 1 to 1 correspondence between z i and a i , we have |W 1 | ≤ 2 2n . For c = 2, Bob outputs a 1 , z 1 , a 3 , z 3 . A necessary condition is that z 1 can be mapped to an element (π, s ) where π is a permutation on [n] and s ∈ {0, 1} n and z 3 has to be mapped to an binary vector, which implies

|W 2 | ≤ 2 n n! • 2 n = 2 2n n!. A similar reasoning for c = 3 gives |W 3 | ≤ 2 2n n!. For each c ∈ {1, 2, 3}, let Q c W = AZ∈Wc Q c
AZ the projector on the winning outputs for Bob on input c (for the fixed input/output pair BX of Alice). Let V BX be the probability that Alice and Bob win the game for this input. We have

V BX = 1 3 c∈{1,2,3} tr(Q c W σ BX ).
and also E BX [V BX ] = ω * (G rel Stern ) -δ. We now consider the following quantum strategy for Bob that will make him succeed on the 3 challenges: wp. 1 2 , run Q 1 to get output AZ 1 , then on the resulting state, run Q 2 to get output AZ 2 and on the resulting state, run Q 3 to get output AZ 3 . Wp. 1 2 , do the same thing but swap the order ot Q 1 and Q 2 . Let E BX be the probability of success of this strategy. We can write

E BX = 1 2 AZ1∈W1 AZ2∈W2 AZ3∈W3 tr Q 3 AZ3 Q 2 AZ2 Q 1 AZ1 σ BX Q 1 AZ1 Q 2 AZ2 + tr Q 3 AZ3 Q 1 AZ1 Q 2 AZ2 σ BX Q 2 AZ2 Q 1 AZ1
Notice that for any 3 projectors, P 1 , P 2 , P 3 , we have tr(P 3 P 2 P 1 σP 1 P 2 P 3 ) = tr(P 2 3 P 2 P 1 σP 1 P 2 ) = tr(P 3 P 2 P 1 σP 1 P 2 ) hence the expression E BX .

In order to conclude, we use the 2 following equations, which will be proven in upcoming proposition. The first one

E BX E BX = 1 Q , (C1)
claims that our strategy will succeed in answering valid outputs A 1 , A 2 , A 3 for the 3 challenges wp. at most 1 Q . In high level, this is a direct consequence of Proposition 1 and of the binding property of the F Q -relativistic commitment scheme, but we reprove this claim from scratch. We then relate E BX and V BX using a generic proposition on projectors

E BX ≥ 9(V BX -2 3 ) 4 2|W 1 ||W 2 | . (C2)
Proving this inequality is actually where we had most of the technical difficulty. In order to prove this statement, we generalized the approach of [START_REF] Chailloux | Relativistic (or 2-prover 1-round) zero-knowledge protocol for np secure against quantum adversaries[END_REF] to 3 measurements and showed that if you can win for the 3 challenges at the same time wp. at most 1 Q then a quantum adversary can win at most wp. 2 3 + ε where ε is vanishingly small for Q large enough.

We first conclude and then go on proving Equations C1 and C2. To conclude our proof, we have from Equation C2 that

E BX ≥ 9(V BX -2 3 ) 4 2 • 2 4n n! .
By taking the expectation on each side, we obtain

1 Q = E BX [E BX ] ≥ E BX [ 9(V BX -2 3 ) 4 2 • 2 4n n! ] ≥ 9 ω * (G rel Stern ) -δ -2 3 4 2 • 2 4n n!
where we used the convexity of the function x → x 4 -2 3 . Since this holds for any δ > 0, we take δ → 0 and have

1 Q ≥ 9 ω * (G rel Stern ) -2 3 4 2 • 2 4n n! .
We now prove our two equations. We first prove the following Lemma 1 (Equation C1). In the NO case, the probability that Bob successfully outputs 3 valid couples (AZ 1 , AZ 2 , AZ 3 ), on average on BY is at most

= z 3 1 = z 1 , z 1 2 = z 3 2 = z 2 , z 1 3 = z 2 3 = z 3 .
We map z 1 to a pair (σ, s ), z 2 , z 3 to vectors ∈ {0, 1} n . Passing the 3 winning conditions implies that

Hσ -1 (z 2 + z 3 ) = s and |σ -1 (z 2 + z 3 ) | = w.
This implies that σ -1 (z 2 + z 3 ) is a solution to the syndrome decoding problem but since we are in the NO case, such a solution doesn't exist hence the contradiction.

This means there exists c ∈ {1, 2, 3} st.

z c c1 = z c c2
for the two values c 1 , c 2 = c . Because these are valid answers, this means we have

z c1 c * b c = y c -a c1 c z c2 c * b c = y c -a c2 c
From which we get

b c = (a c c2 -a c c1 )/(z c c1 -z c c2
). where / is the division in F Q . From there, this means Bob can guess b c but from non-signaling, Bob should have no information about b c . Moreover, notice that Bob knows which c to take, it is the index z c1 c = z c2 c . Since b c is a random element from F Q , we conclude that Bob can guess this value wp. 1 Q which concludes the proof. The next section is devoted to the proof of the second equation.

Proof of Equation C2

We prove the following Proposition 2. Consider 3 projectors P 1 , P 2 , P 3 such that for each i ∈ {1, 2, 3}, we can write P i = Si si=1 P s i where for each i, the {P s i } are orthogonal projectors meaning that P s i P s i = δ s,s P s i . Let σ be any quantum state. Let V = i tr(P i σ) and

E = 1 2 S3 s3=1 S2 s2=1 S1 s1=1 tr (P s3 3 P s2 2 P s1 1 σ (P s1 1 ) (P s2 2 )) + S3 s3=1 S2 s2=1 S1 s1=1
tr (P s3 3 P s1 1 P s2 2 σ (P s2 2 ) (P s1 1 )) .

We have E ≥

9(V -2 3 ) 4 2S1S2 .
In order to prove our proposition, we first need the following trigonometric lemma.

Lemma 2. ∀α 1 , α 2 ∈ [0, π/2[ st. cos 2 (α 1 ) + cos 2 (α 2 ) > 1, if we define c 1 = cos(α 1 ), c 2 = cos(α 2 ), s 1 = sin(α 1 ), s 2 = sin(α 2 ), we have

min y∈[-s1,s1] c 2 2 (c 1 c 2 + ys 2 ) 2 (c 1 c 2 + ys 2 ) 2 + s 2 1 -y 2 ≥ c 2 1 + c 2 1 -1.
Proof. Let t 1 = tan(α 1 ) and t 2 = tan(α 2 ). Since c 2 1 +c 2 2 > 1, we have α 1 + α 2 < π/2 and t 1 t 2 < 1. Let also T (y) = (c 1 c 2 + ys 2 ) 2 ; U (y) = s 2 1 -y 2 . Our goal is hence to minimize the function

f (y) = c 2 2 T (y) T (y) + U (y) for y ∈ [-s 1 , s 1 ].
We write

f (y) = c 2 2 T (y) (T (y) + U (y)) -c 2 2 T (y) (T (y) + U (y)) (T (y) + U (y)) 2 = c 2 2 (T (y)U (y) -T (y)U (y)) (T (y) + U (y)) 1 = c 2 1 + c 2 2 -1 In order to conclude, we write f (-s 1 ) = c 2 2 ; f (s 1 ) = c 2 2 ; f (y 0 ) = c 2 1 + c 2 2 -1 ≤ f (s 1 ). Since y 0 is the unique point in [-s 1 , s 1 ] such that f (y 0 ) = 0 we can conclude that min y∈[-s1,s1] {f (y)} = f (y 0 ) = c 2 1 + c 2 2 -1.
We now prove our proposition for the special case S 1 , S 2 = 1 and for a pure state |Ω instead of σ. Proposition 3. Let |Ω be a quantum state. Let P 1 , P 2 , P 3 be projectors. Let

V = 1 3 P i |Ω 2 = 2 3 + ε with ε ≥ 0 and E = 1 2 P 3 P 2 P 1 |Ω 2 + P 3 P 1 P 2 |Ω 2 .
We have E ≥ 9ε 4 2 .

Proof. Let |φ i = Pi|Ω Pi|Ω . We write

|Ω = cos(α i )|φ i + sin(α i )|φ ⊥ i for i ∈ {1, 2, 3}. (C3)
This means

V = 1 3 cos 2 (α 1 ) + cos 2 (α 2 ) + cos 2 (α 3 ) .
We write

|φ 2 = cos(α 2 )|Ω + sin(α 2 )|B (C4)
for some pure state |B ⊥|Ω and

|φ 1 = cos(α 1 )|Ω + x|A + y|B (C5)
for some pure state |A ⊥|B and |A ⊥|Ω . This means we have

cos 2 (α 1 ) + |x| 2 + |y| 2 = 1. (C6)
We also write

P 2 = |φ 2 φ 2 | + P 2 with P 2 |φ 2 = 0. (C7)
We have

|W = P 2 P 1 (|Ω ) = cos(α 1 )(P 2 |φ 1 ) = cos(α 1 ) φ 1 |φ 2 |φ 2 + cos(α 1 )P 2 |φ 1 (C8) Notice that P 2 |Ω = cos(α 2 )|φ 2 = |φ 2 φ 2 | • |Ω hence P 2 |Ω = 0. This implies that P 2 |B = 0 and P 2 |φ 1 = P 2 (x|A ) = z|A (C9)
for some |A orthogonal to |Ω and |B and |z| ≤ |x|. So we rewrite

1 cos(α 1 ) |W = φ 1 |φ 2 |φ 2 + P 2 |φ 1 = (cos α 1 cos(α 2 ) + sin(α 2 )y) |φ 2 + z|A (C10) Let u = (cos α 1 cos(α 2 ) + sin(α 2 )y) so that |W = cos(α 1 )u|φ 2 + cos(α 1 )z|A (C11)
The norm of |W is therefore

|W = | cos(α 1 )| |u| 2 + |z| 2 . Let | W = |W / |W . From Equation C11, we have | Ω| W | 2 = ( | cos(α 2 ) cos(α 1 )u| |W ) 2 = cos 2 (α 2 )u 2 u 2 + z 2 ≥ cos 2 (α 2 )u 2 u 2 + (1 -cos 2 (α 1 ) -y 2 )
.

Using lemma 2, we obtain | Ω| W | 2 ≥ cos 2 (α 1 ) + cos 2 (α 2 ) -1. We hence write | Ω| W | 2 = cos 2 (β) for some β ≤ α 1 + α 2 . In order to conclude, we define Angle(|ψ , |φ ) = arccos(| ψ|φ |). The angle function is a distance measure [START_REF] Nielsen | Quantum computation and quantum information[END_REF]. We will use several times the trigonometric inequality cos(ρ+θ) ≥ cos 2 (ρ)+cos 2 (θ)-1 for any ρ, θ with ρ + θ ≤ π/2 and we can hence write

P 3 | W 2 ≥ | φ 3 | W | 2 = cos 2 Angle |φ 3 , | W ≥ cos 2 Angle(|φ 3 , |Ω ) + Angle(|Ω , | W ) ≥ cos 2 (α 3 + β) ≥ cos 2 (α 3 ) + cos 2 (β) -1 2 = cos 2 (α 1 ) + cos 2 (α 2 ) + cos 2 (α 3 ) -2 2 = ε 2
From there, we can conclude

P 3 P 2 P 1 |Ω 2 = P 3 |W 2 = P 3 | W 2 W 2 ≥ ε 2 P 2 P 1 |Ω 2
In order to conclude, we use |y| ≤ sin(α 1 ) (Equation C6) which gives |u| ≥ cos(α 1 + α 2 ), and

P 2 P 1 |Ω 2 = W 2 ≥ cos 2 (α 1 ) cos 2 (α 1 + α 2 ).
which gives

P 3 P 2 P 1 |Ω 2 ≥ ε 2 cos 2 (α 1 ) cos 2 (α 1 + α 2 ) (C12)
Similarly, we have

P 3 P 1 P 2 |Ω 2 = ε 2 P 1 P 2 |Ω 2 P 3 | W 2 ≥ ε 2 cos 2 (α 2 ) cos 2 (α 1 + α 2 ) (C13) 1 2 P 3 P 2 P 1 |Ω 2 + P 3 P 1 P 2 |Ω 2 ≥ ε 2 2 (cos 2 (α 1 ) + cos 2 (α 2 ))cos 2 (α 1 + α 2 )
Now, since cos 2 (α 1 )+cos 2 (α 2 ) ≥ 1+3ε (from V ≥ 2 3 +ε), we have cos 2 (α 1 ) + cos 2 (α 2 ) ≥ 1 and cos 2 (α 1 + α 2 ) ≥ cos 2 (α 1 ) + cos 2 (α 2 ) -1 2 = (3ε) 2 , from which we conclude

1 2 P 3 P 2 P 1 |Ω 2 + P 3 P 1 P 2 |Ω 2 ≥ 9ε 4 2 .
We proved our main proposition for S 1 , S 2 = 1. From there, we can directly go to the general case in similar way than in [START_REF] Chailloux | Relativistic (or 2-prover 1-round) zero-knowledge protocol for np secure against quantum adversaries[END_REF].We need the following statement Lemma 3 (Proposition 4 from [START_REF] Chailloux | Relativistic (or 2-prover 1-round) zero-knowledge protocol for np secure against quantum adversaries[END_REF]). Similarly, we can prove

E 2 ≥ 1 S 1 S 2
tr( P 3 P 1 P 2 |Ω Ω| P 2 P 1 ).

In order to conclude, we use Proposition 3 which directly gives us the desired result.

Appendix D: Security proof of the full scheme and loss-tolerance

Analysis of loss tolerance

We consider the R round protocol where we allow at most F aborts and let λ = F R . An adversary can of course use this allowed number of losses to cheat in the protocol. We consider cheating provers and assume here that the hardware is perfect, which can only help the cheating provers. At the first round, the provers can perform a strategy that aborts with probability λ * and for which they win the game with probability p * conditioned on not aborting. The probability P * (R, F ) of cheating is therefore P * (R, F ) = λ * P 1 + (1 -λ * )p * P 2 .

where P 1 is the probability that the provers win on the R -1 remaining rounds and they have F -1 aborts left, and P 2 is the probability that the provers win on the R -1 remaining rounds and they have F aborts left. While computing P 1 and P 2 is hard, notice that P 2 ≥ P 1 . Moreover, (1 -λ * )p * ≤ ω * (G rel Stern ) and p * ≤ 1, so (1-λ * )p * ≤ min{ω * (G rel Stern ), 1-λ * }. We now distinguish 2 cases

• If λ * ∈ [0, 1 -ω * (G rel
Stern )], P * ≤ λ * P 1 + ω * (G rel Stern )P 2 and this right hand side is increasing in λ * .

• If λ * ∈ [1-ω * (G rel Stern ), 1], P * ≤ λ * P 1 +(1-λ * )P 2 = P 2 +λ * (P 1 -P 2 ) and this right hand side is decreasing in λ * since P 2 ≥ P 1 . This shows that the best strategy for the prover is to take at the first round λ * = 1 -ω * (G rel Stern ). Notice that the above reasoning is independent on the number of remaining rounds or the number of allowed aborts. This means the same argument can be applied to each round. From there, we have that the provers optimal strategy at each round is to perform a strategy that aborts wp. λ * = 1 -ω * (G rel Stern ). In this case, we potentially have p * = 1 so the provers will win all the games where they don't abort but they will most probably abort too often, for well chosen parameters. Let P * losses (R, F ) be the probability that the provers perform less than F aborts with this strategy. We use the following Chernoff bound Proposition 4 (Additive Chernoff bound). Suppose X 1 , . . . , X n are independent random variables taking value in {0, 1}. Let X denote their sum, p = E[X 1 ] and ε > 0. We have Pr[X ≥ pn + εn] ≤ 2 n((p+ε) log 2 ( p p+ε )+(1-p-ε) log 2 ( 1-p 1-p-ε )) , Pr[X ≤ pn -εn] ≤ 2 n((p-ε) log 2 ( p p-ε )+(1-p+ε) log 2 ( 1-p 1-p+ε )) .

In our case, the strategy of the provers outputs 'Abort' wp. λ * and they succeed in cheating if there are at most F = λR aborts. We use the above Chernoff bound (second equation) with n = R, p = λ * = 1 -ω * (G rel Stern ), ε = λ * -λ which bounds the probability that there are less than F = λn aborts, and we write

P * (R, F ) ≤ 2 R λ log 2 ( λ * λ )+(1-λ) log 2 ( 1-λ * 1-λ ) = 2

  FIG.4: T Phase1 and T Phase2 for Scenario 1 with 10000 rounds, times are aggregated in intervals of size 0.01ms.

  1. Scenario 1: D = 400km, D = 10m, D/c ≈ 1.33ms, ∆ T = 2ms, T shif t = 0.5ms. With these parameters, the space-time constraints are satisfied for T P hase1 i < 1.83ms and T P hase2 i < 0.83ms. 2. Scenario 2: D = 9000km, D = 400km, D/c ≈ 30ms, ∆ T = 40ms, T shif t = 2.5ms. With these parameters, the space-time constraints are satisfied for T P hase1 i < 32.5ms and T P hase2 i < 27.5ms.

  FIG.5: T Phase1 and T Phase2 for Scenario 2 with 10000 rounds, times are aggregated in intervals of size 0.1ms.

  Appendix A: Comparison between the different existing schemes

2 3 .

 3 This means we have strategies for which the players win for 2 possible challenges for Bob but not for the third one.

)

  Fix an input/output BY with B = b 1 , b 2 , b 3 and Y = y 1 , y 2 , y 3 . Assume by contradiction that Bob can output 3 valid couples AZ 1 , AZ 2 , AZ 3 with AZ c = (for the 2 different values c 1 , c 2 = c. Assume by contradiction that z 2 1

R λ log 2

 2 (1-ω * (G rel Stern ) λ )+(1-λ) log 2 ( ω * (G rel Stern ) 1-λ ) (D1)

TABLE I

 I

	: Parameters for different zero-knowledge
	proposals for 100 security bits (see Appendix A for
	more details).
	against classical adversaries) was recently implemented
	using some dedicated hardware [ABC + 21].

  . The best algorithm for Hamiltonian cycle on a graph G with n vertices runs in time O(1.657 n )[Bjö14] so we need n ≥ 138 in order to achieve 100 bits of security. The best running time is actually performed by a classical algorithm, we don't know a better quantum algorithm for this problem. This protocol requires to commit each bit of the upper triangle of the adjacency matrix of G using the relativistic F Q bit commitment scheme with Q > 10000n! (to have soundness close to 1/2) so each round of communication requires at least 2 * n(n-1)

2 log 2 (10000 * Q) bits of communication. n(n-1)

2

  Let a projector P = m i=1 where {P i } i∈[m] are orthogonal projectors. For any pure state |ψ , we have Proof of Proposition 2. First, in order to use Proposition 3, we need to work on pure states similarly as in [CL17]. Assume σ is a quantum mixed state in some Hilbert space B and the projectors P s i act on B. We add an extra Hilbert space E. We consider a purification |Ω of σ in BE and define P i = P i ⊗ I E , P s i = P s i ⊗ I E , V = i tr( P i |Ω ) and

				m i=1	P i |ψ ψ|P i ≥	1 m	P |ψ ψ|P.
	With this lemma, we can prove our main proposition.
						E =	1 2	E 1 + E 2
	with
	S3		S2	S1
	E 1 =					tr P s3 3 P s2 2 P s1 1 |Ω Ω| P s1 1	P s2 2
	s3=1	s2=1	s1=1
	S3	S2		S1
	E 2 =					tr P s3 3 P s1 1 P s2 2 |Ω Ω| P s2 2	P s1 1	.
	s3=1	s2=1	s1=1
	One can easily check that V = V and E = E. Now,
	using Lemma 3 twice, we have
	E 1 ≥	1 S 1	S3 s3=1	S2 s2=1	tr P s3 3 P s2 2 P 1 |Ω Ω| P 1 P s2 2
	≥	1 S 1 S 2	S3 s3=1	tr P s3 3 P 2 P 1 |Ω Ω| P 1 P 2
	=	1 S 1 S 2	tr( P

3 P 2 P 1 |Ω Ω| P 1 P 2 )

Acknowledgments. AC and YB were supported by ANR DEREC <ANR-16-CE39-0001-01>.

Analysis of the completeness error

We can also use the above Chernoff bound to bound the completeness error, i.e. the probability that the protocol aborts when all players are honest. We allow up to F aborts and assume we have parameters for which the signal doesn't arrive in time with some probability p loss . Let CE(R, F, p loss ) denote the completeness error and λ = F R . Using again the Chernoff bound (first equation) with R = n, p = p loss , ε = λ -p loss , we have

Appendix E: Other parameters

The plots we present in the main text correspond to n = 1704 which allows us to have 100 bits of security. We present here the plots for other values of n, for our 2 scenarios, to present the scaling of our scheme.