 
\( \ \)

Comparison between the different existing schemes
The authors of [1]} use parameters for which they have 100 bits of security. This means both the underlying \(\) -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 [2]}. The best algorithm for Hamiltonian cycle on a graph \(G\)  with \(n\)  vertices runs in time \(O(1.657^n)\)[3]} so we need \(n \ge 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 \(\mathbb {F}_Q\)  bit commitment scheme with \(Q > 10000n!\)  (to have soundness close to \(1/2\) ) so each round of communication requires at least \(2*\frac{n(n-1)}{2}\log _2(10000*Q)\)  bits of communication. \(\frac{n(n-1)}{2}\)  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 \(\frac{n(n-1)}{2}\)  elements of \(\mathbf {\mathsf {\mathbb {F}_Q}}\)  and then the prover sends back \(\frac{n(n-1)}{2}\)  elements of \(\mathbf {\mathsf {\mathbb {F}_Q}}\) . For \(n = 138\) , this gives a communication of \(1.51 \cdot 10^7 \)  bits which is approximately \(1.89MBytes\) . In order to achieve soundness of \(2^{-100}\) , we use 100 rounds since each round has soundness \(\frac{1}{2}\) .

The protocol of [4]} and its implementation in [1]} 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, [1]} 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}\)  [7]} for \(k \approx 0.4514n\)  and \(w \approx 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 \(\mathbf {\mathsf {\mathbb {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.


Stern's zero-knowledge protocol for the syndrome decoding problem
We now describe Stern's zero-knowledge protocol [8]} for the Syndrome Decoding problem. It uses a commitment scheme that we don't explicit here.
<TABLE>
 \( \ \)
This protocol was shown to be secure in [8]}. We reproduce here the main aspects of this proof.
Completeness
The protocol has perfect completeness. Indeed, in the honest case:

\(|z_2 + z_3|_H= |\sigma ({\mathbf {t}}) \oplus \sigma ({\mathbf {t}}\oplus {\mathbf {e}})|_H = |\sigma ({\mathbf {e}})|_H = w.\)

\({\mathbf {H}}\cdot \sigma ^{-1}\left(\sigma ({\mathbf {t}}\oplus {\mathbf {e}})\right) = {\mathbf {H}}{\mathbf {t}}\oplus {\mathbf {H}}{\mathbf {e}}= {\mathbf {s}}\oplus {\mathbf {s}}^{\prime }\) .

\({\mathbf {H}}\cdot \sigma ^{-1}(\sigma ({\mathbf {t}}))= {\mathbf {H}}{\mathbf {t}}= {\mathbf {s}}^{\prime }.\)


Soundness
We are in the NO case, so there are no vectors \({\mathbf {e}}\)  such that \(|{\mathbf {e}}|_H = w\)  and \({\mathbf {H}}{\mathbf {e}}= {\mathbf {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.

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 = (\sigma || {\mathbf {s}}^{\prime })\) , \(z_2,z_3\) . Let \({\mathbf {e}}_0 = \sigma ^{-1}(z_2) \oplus \sigma ^{-1}(z_3) = \sigma ^{-1}(z_2 \oplus z_3)\) . Since the prover successfully answers challenge 1, we have \(|z_2 \oplus z_3|_H = w\)  hence \(|{\mathbf {e}}_0|_H = w\) . Moreover, since he successfully answers challenges 2 and 3, we have
\( {\mathbf {H}}{\mathbf {e}}_0 = {\mathbf {H}}(\sigma ^{-1}(z_2) + \sigma ^{-1}(z_3)) = {\mathbf {s}}\oplus {\mathbf {s}}^{\prime } \oplus {\mathbf {s}}^{\prime } = {\mathbf {s}}.\) 
Since we are in the NO case, such an \({\mathbf {e}}_0\)  doesn't exist, hence the contradiction.

This means that a cheating prover can cheat with probability at most \(\frac{2}{3}\)  unless he is able to break the binding property of the commitment scheme.

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 \(\sigma ({\mathbf {t}})\)  and \(\sigma ({\mathbf {t}}+{\mathbf {e}})\)  from which he cannot recover any information because \(\sigma \)  is unknown. For the challenge \(c = 2\) , he receives \(\sigma ,{\mathbf {s}}^{\prime },\sigma ({\mathbf {t}}+{\mathbf {e}})\)  hence he can recover \({\mathbf {t}}+~{\mathbf {e}}\) . However, since \({\mathbf {t}}\)  is unknown, this looks like a random vector. For the challenge \(c = 3\)  he receives \(\sigma ,{\mathbf {s}}^{\prime },\sigma ({\mathbf {t}})\)  , which are random elements independent of \({\mathbf {e}}\) .

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 \(\)  presented in Figure REF .
Completeness.
Completeness follows directly from the completeness of Stern's single round, and from the fact that the \(\mathbb {F}_Q\)  string commitment has perfect completeness.

Zero-knowledge.
Stern's signature scheme is perfectly zero-knowledge if the commitment scheme is perfectly hiding, which is the case of the \(\mathbb {F}_Q\)  string commitment. Therefore, the protocol is perfectly zero-knowledge. This zero-knowledge property is also preserved when the scheme is repeated sequentially.

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 \(\mathrm {SD}\)  problem and we consider an all powerful cheating prover that wants to convince the verifier such a solution exists.
In all generality, \(\mathcal {P}_1\)  and \(\mathcal {P}_2\)  can share an entangled state \(|\Phi \rangle \) . Then \(\mathcal {P}_1\)  receives \(B = b_1,b_2,b_3\)  from \(\mathcal {V}_1\)  and \(\mathcal {P}_2\)  receives \(c \in \lbrace 1,2,3\rbrace \)  from \(\mathcal {V}_2\) . They output respectively \(Y = y_1,y_2,y_3\)  and \(ZA = \lbrace (z_{c^{\prime }},a_{c^{\prime }})\rbrace _{c^{\prime } \ne c}\) . The verifiers then come together and perform the verification step. We assume the timing constraints are verified which ensures that \(\mathcal {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^{\mathrm {rel}}_{\mathrm {Stern}}\) , is defined as follows:
<TABLE>The \(``+"\)  and \(``*"\)  operations we use are the one in \(\mathbf {\mathsf {\mathbb {F}_Q}}= \lbrace \overline{0},\dots ,\overline{Q-1}\rbrace \)  where \(\overline{i}\)  is the \(i^{\mbox{th}}\)  element of \(\mathbf {\mathsf {\mathbb {F}_Q}}\) . We do our mapping as follows: If \(z_1 \in \lbrace \overline{0},\dots ,\overline{S_1 - 1}\rbrace \) , then we map \(z_1\)  to the \(z_1^{\mbox{th}}\)  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 \(\lbrace \overline{0},\dots ,\overline{2^n-1}\rbrace \)  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 \ge |S_1|\)  and \(Q \ge 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 \(\frac{2}{3}\)  [8]} from which we can directly derive strategies for this game with 2 classical players that win wp. \(\frac{2}{3}\) . This means we have strategies for which the players win for 2 possible challenges for Bob but not for the third one.
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 REF  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 [11]}, [12]}, 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^{\mathrm {rel}}_{\mathrm {Stern}}\) . As \(Q\)  increases, the entangled value converges to \(\frac{2}{3}\)  which is optimal. We prove the following theorem
Theorem 3
\( \omega ^*(G^{\mathrm {rel}}_{\mathrm {Stern}}) \le \frac{2}{3} + \left(\frac{n!2^{4n}}{Q}\right)^{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 \(\omega ^*(G^{\mathrm {rel}}_{\mathrm {Stern}})\) .

Bounding the value of the game
We can now prove our lower bound on the entangled value of \(G^{\mathrm {rel}}_{\mathrm {Stern}}\) .
[Proof of the lower bound of the game]
Let any \(\delta > 0\)  and consider a finite dimensional projective strategy for Alice and Bob that wins the game \(G^{\mathrm {rel}}_{\mathrm {Stern}}\)  wp. \(\omega ^*(G^{\mathrm {rel}}_{\mathrm {Stern}}) - \delta \) .
Let \(P^{B} = \lbrace P^{B}_{Y}\rbrace \)  and \(Q^c = \lbrace Q^c_{A}\rbrace \)  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^{\prime }},z_{c^{\prime }})\)  for \(c^{\prime } \ne c\) , starting with the one with smallest index. Let \(|\psi \rangle \)  be the quantum state they share.
Fix an input/output pair \(BY\)  for Alice and let \(\sigma ^{BY}\)  be the state held by Bob, conditioned on this pair. For each \(c \in \lbrace 1,2,3\rbrace \) , let \(W_c = \lbrace AZ: V(Y,AZ,B,c)= 1\rbrace \)  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 = 1\) , 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| \le ~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 \((\pi ,{\mathbf {s}}^{\prime })\)  where \(\pi \)  is a permutation on \([n]\)  and \({\mathbf {s}}^{\prime } \in \lbrace 0,1\rbrace ^n\)  and \(z_3\)  has to be mapped to an binary vector, which implies \(|W_2| \le 2^{n}n!\cdot 2^{n} = 2^{2n}n!\) . A similar reasoning for \(c = 3\)  gives \(|W_3| \le 2^{2n}n!\) .
For each \(c \in \lbrace 1,2,3\rbrace \) , let \(Q^c_W = \sum _{AZ \in W_c} 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} = \frac{1}{3}\sum _{c \in \lbrace 1,2,3\rbrace } tr(Q^c_W \sigma ^{BX}).\) 
and also
\(_{BX}[V^{BX}] = \omega ^*(G^{\mathrm {rel}}_{\mathrm {Stern}}) - \delta \) . We now consider the following quantum strategy for Bob that will make him succeed on the 3 challenges: wp. \(\frac{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. \(\frac{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} =\frac{1}{2}\Big (\sum _{\begin{array}{c}AZ_1 \in W_1 \\ AZ_2\in W_2 \\ AZ_3 \in W_3\end{array}}tr\left(Q^3_{AZ_3}Q^2_{AZ_2}Q^1_{AZ_1} \sigma ^{BX}Q^1_{AZ_1}Q^2_{AZ_2}\right) + \\tr\left(Q^3_{AZ_3}Q^1_{AZ_1}Q^2_{AZ_2} \sigma ^{BX}Q^2_{AZ_2}Q^1_{AZ_1}\right)\Big .\) 
Notice that for any 3 projectors, \(P_1,P_2,P_3\) , we have
\(tr(P_3P_2P_1\sigma P_1P_2P_3) = tr(P_3^2P_2P_1\sigma P_1P_2) = tr(P_3P_2P_1\sigma P_1P_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
\(_{BX}\left[E^{BX}\right] = \frac{1}{Q},\) 
claims that our strategy will succeed in answering valid outputs \(A_1,A_2,A_3\)  for the 3 challenges wp. at most \(\frac{1}{Q}\) . In high level, this is a direct consequence of Proposition REF  and of the binding property of the \(\mathbf {\mathsf {\mathbb {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} \ge \frac{9 (V^{BX} - \frac{2}{3})^4}{2|W_1||W_2|}.\) 

Proving this inequality is actually where we had most of the technical difficulty. In order to prove this statement, we generalized the approach of [2]} to 3 measurements and showed that if you can win for the 3 challenges at the same time wp. at most \(\frac{1}{Q}\)  then a quantum adversary can win at most wp. \(\frac{2}{3} + \varepsilon \)  where \(\varepsilon \)  is vanishingly small for \(Q\)  large enough.
We first conclude and then go on proving Equations REF  and REF . To conclude our proof, we have from Equation REF  that
\( E^{BX} \ge \frac{9 (V^{BX} - \frac{2}{3})^4}{2\cdot 2^{4n}n!}.\) 
By taking the expectation on each side, we obtain
\(\frac{1}{Q} &= _{BX}[E^{BX}] \ge _{BX}[\frac{9 (V^{BX} - \frac{2}{3})^4}{2\cdot 2^{4n}n!}] \ge \frac{9 \left(\omega ^*(G^{\mathrm {rel}}_{\mathrm {Stern}}) - \delta - \frac{2}{3}\right)^4}{2\cdot 2^{4n}n!}\) 

where we used the convexity of the function \(x \mapsto x^4 - \frac{2}{3}\) . Since this holds for any \(\delta > 0\) , we take \(\delta \rightarrow 0\)  and have
\( \frac{1}{Q} \ge \frac{9 \left(\omega ^*(G^{\mathrm {rel}}_{\mathrm {Stern}}) - \frac{2}{3}\right)^4}{2\cdot 2^{4n}n!}.\) 
We now prove our two equations. We first prove the following
Lemma 1 (Equation REF ) 
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 \(\frac{1}{Q}\) .

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 = (a^c_{c^{\prime }_1},z^c_{c^{\prime }_1}),(a^c_{c^{\prime }_2},z^c_{c^{\prime }_2})\)  for the 2 different values \(c^{\prime }_1,c^{\prime }_2 \ne c\) .
Assume by contradiction that \(z_{1}^2 = z_1^3 =z_1\) , \(z_{2}^1 = z_2^3 =z_2\) , \(z_{3}^1 = z_3^2 =z_3\) . We map \(z_1\)  to a pair \((\sigma ,{\mathbf {s}}^{\prime })\) , \(z_2,z_3\)  to vectors \( \in \lbrace 0,1\rbrace ^n\) . Passing the 3 winning conditions implies that
\({\mathbf {H}}\sigma ^{-1}\left(z_2 + z_3\right) = {\mathbf {s}}\quad \textrm {and} \quad |\sigma ^{-1}\left(z_2 + z_3\right)| = w.\) 
This implies that \(\sigma ^{-1}\left(z_2 + z_3\right) \)  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^{\prime } \in \lbrace 1,2,3\rbrace \)  st. \(z_{c_1}^{c^{\prime }} \ne z_{c_2}^{c^{\prime }}\)  for the two values \(c_1,c_2 \ne c^{\prime }\) . Because these are valid answers, this means we have
\(z^{c_1}_{c^{\prime }} * b_{c^{\prime }} & = y_{c^{\prime }} - a^{c_1}_{c^{\prime }} \\z^{c_2}_{c^{\prime }} * b_{c^{\prime }} & = y_{c^{\prime }} - a^{c_2}_{c^{\prime }}\) 

From which we get
\( b_{c^{\prime }} = (a_{c_2}^{c^{\prime }} - a_{c_1}^{c^{\prime }})\slash (z_{c_1}^{c^{\prime }} - z_{c_2}^{c^{\prime }}).\) 
where \(\slash \)  is the division in \(\mathbb {F}_Q\) . From there, this means Bob can guess \(b_{c^{\prime }}\)  but from non-signaling, Bob should have no information about \(b_{c^{\prime }}\) . Moreover, notice that Bob knows which \(c^{\prime }\)  to take, it is the index where \(z^{c_1}_{c^{\prime }} \ne z^{c_2}_{c^{\prime }}\) . Since \(b_{c^{\prime }}\)  is a random element from \(\mathbf {\mathsf {\mathbb {F}_Q}}\) , we conclude that Bob can guess this value wp. \(\frac{1}{Q}\)  which concludes the proof.
The next section is devoted to the proof of the second equation.

Proof of Equation  REF
We prove the following
Proposition 2 
Consider 3 projectors \(P_1,P_2,P_3\)  such that for each \(i \in \lbrace 1,2,3\rbrace \) , we can write \(P_i = \sum _{s_i = 1}^{S_i} P^s_i\)  where for each \(i\) , the \(\lbrace P^s_i\rbrace \)  are orthogonal projectors meaning that \(P^s_iP^{s^{\prime }}_i = \delta _{s,s^{\prime }}P^s_i\) . Let \(\sigma \)  be any quantum state.
Let \(V =\sum _i tr(P_i \sigma )\)  and
\(E =\frac{1}{2}\Big (\sum _{s_3 = 1}^{S_3} \sum _{s_2 = 1}^{S_2} \sum _{s_1 = 1}^{S_1} tr\left(P_3^{s_3}P_2^{s_2}P_1^{s_1} \sigma \left(P_1^{s_1}\right) \left(P_2^{s_2}\right)\right) + \\ \sum _{s_3 = 1}^{S_3} \sum _{s_2 = 1}^{S_2} \sum _{s_1 = 1}^{S_1} tr\left(P_3^{s_3}P_1^{s_1}P_2^{s_2} \sigma \left(P_2^{s_2}\right) \left(P_1^{s_1}\right) \right)\Big ).\) 
We have
\(E \ge \frac{9\left(V - \frac{2}{3}\right)^4}{2S_1S_2}\) .

In order to prove our proposition, we first need the following trigonometric lemma.
Lemma 2 
\(\forall \alpha _1,\alpha _2 \in [0,\pi /2[\)  st. \(\cos ^2(\alpha _1) + \cos ^2(\alpha _2) > 1\) , if we define \(c_1 = \cos (\alpha _1),c_2 = \cos (\alpha _2), s_1 = \sin (\alpha _1), s_2 = \sin (\alpha _2)\) , we have
\( \min _{y \in [-s_1,s_1]} \left\lbrace \frac{c^2_2\left(c_1c_2+ ys_2\right)^2}{\left(c_1c_2 + ys_2\right)^2 + s_1^2 - y^2}\right\rbrace  \ge c^2_1 + c^2_1- 1.\) 

Let \(t_1 = \tan (\alpha _1)\)  and \(t_2 = \tan (\alpha _2)\) . Since \(c_1^2 + c_2^2 > 1\) , we have \(\alpha _1 + \alpha _2 < \pi /2\)  and \(t_1t_2 < 1\) .
Let also
\( T(y) =(c_1c_2 + ys_2)^2 \quad ; \quad U(y) =s_1^2 - y^2.\) 
Our goal is hence to minimize the function
\( f(y) =\frac{c_2^2 T(y)}{T(y) + U(y)} \quad \textrm {for } y \in [-s_1,s_1].\) 
We write
\(f^{\prime }(y) & = \dfrac{c^2_2T^{\prime }(y)\left(T(y) + U(y)\right) - c_2^2T(y)\left(T^{\prime }(y) + U^{\prime }(y)\right)}{\left(T(y) + U(y)\right)^2} \\ & = \dfrac{c_2^2 \left(T^{\prime }(y)U(y) - T(y)U^{\prime }(y)\right)}{\left(T(y) + U(y)\right)^2}\) 

and
\(Z_0 & = T^{\prime }(y)U(y) - T(y)U^{\prime }(y) \\ & = (2ys_2^2 + 2c_1c_2s_2)(s_1^2 - y^2) - (y^2s_2^2 + 2yc_1c_2s_2 + c_1^2c_2^2)(-2y) \\& = 2y^2(c_1c_2s_2) + 2y(s_1^2s_2^2 + c_1^2c_2^2) + 2c_1c_2s_1^2s_2 \\& = 2c_1c_2s_2\left(y + \dfrac{s_1^2s_2}{c_1c_2}\right)\left(y + \dfrac{c_1c_2}{s_2}\right)\) 
This implies the equation \(f^{\prime }(y) = 0\)  has 2 solutions \(y_0 = -\frac{s_1^2s_2}{c_1c_2} = -s_1t_1t_2\)  and \(y_1 = -\frac{c_1c_2}{s_2} = -\frac{s_1}{t_1t_2}\) . Notice that only \(y_0\)  lies in the interval \([-s_1,s_1]\)  since \(t_1t_2 < 1\) .
We now write
\(f(-s_1) = f(s_1) = c_2^2\)  and
\(T(y_0) & = \dfrac{1}{c_1^2c_2^2} \left(c_1^2c_2^2 - s_1^2s_2^2\right)^2 \\U(y_0) & = \dfrac{s_1^2}{c_1^2c_2^2}\left(c_1^2c_2^2 - s_1^2s_2^2\right)\) 

which implies
\(f(y_0) & = \frac{c_2^2\left(c_1^2c_2^2 - s_1^2s_2^2\right)}{\left(c_1^2c_2^2 - s_1^2s_2^2\right) + s_1^2} \\& = c_2^2 - s_1^2 & \textrm {using } \left(c_1^2c_2^2 - s_1^2s_2^2\right) = c_2^2 - s_1^2 \\& = c_1^2 + 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_1^2 + c_2^2 - 1 \le f(s_1).\) 
Since \(y_0\)  is the unique point in \([-s_1,s_1]\)  such that \(f^{\prime }(y_0) = 0\)  we can conclude that
\(\min _{y \in [-s_1,s_1]}\lbrace f(y)\rbrace  = f(y_0) = c_1^2 + c_2^2 - 1.\) 
We now prove our proposition for the special case \(S_1,S_2 = 1\)  and for a pure state \(|\Omega \rangle \)  instead of \(\sigma \) .
Proposition 3 
Let \(|\Omega \rangle \)  be a quantum state. Let \(P_1,P_2,P_3\)  be projectors. Let \(V = \frac{1}{3} \left\Vert P_i |\Omega \rangle \right\Vert ^2 = \frac{2}{3} + \varepsilon \)  with \(\varepsilon \ge 0\)  and \(E = \frac{1}{2}\left(\left\Vert P_3P_2P_1 |\Omega \rangle \right\Vert ^2 + \left\Vert P_3P_1P_2 |\Omega \rangle \right\Vert ^ 2\right)\) . We have \( E \ge \frac{9\varepsilon ^4}{2}.\)

Let \(|\phi _i\rangle  = \frac{P_i|\Omega \rangle }{\left\Vert P_i |\Omega \rangle \right\Vert }\) .
We write
\(|\Omega \rangle  = \cos (\alpha _i) |\phi _i\rangle  + \sin (\alpha _i) |\phi _i^\bot \rangle  \ \textrm { for } i \in \lbrace 1,2,3\rbrace .\) 
 This means
\(V = \frac{1}{3} \left(\cos ^2(\alpha _1) + \cos ^2(\alpha _2) + \cos ^2(\alpha _3)\right).\) 
We write
\(|\phi _2\rangle  & = \cos (\alpha _2)|\Omega \rangle  + \sin (\alpha _2)|B\rangle \) 
 for some pure state \(|B\rangle  \bot |\Omega \rangle \)  and
\(|\phi _1\rangle  = \cos (\alpha _1)|\Omega \rangle  + x |A\rangle  + y |B\rangle \) 
 for some pure state \(|A\rangle  \bot |B\rangle \)  and \(|A\rangle  \bot |\Omega \rangle \) . This means we have
\(\cos ^2(\alpha _1) + |x|^2 + |y|^2 = 1.\) 

We also write
\(P_2 = |\phi _2\rangle \langle \phi _2| + P^{\prime }_2 \ \textrm { with } P^{\prime }_2 |\phi _2\rangle  = {\mathbf {0}}.\) 
 We have
\(|W\rangle  = P_2P_1(|\Omega \rangle ) & = \cos (\alpha _1)(P_2 |\phi _1\rangle ) \nonumber \\& = \cos (\alpha _1)\langle {\phi _1}|{\phi _2}\rangle |\phi _2\rangle  + \cos (\alpha _1)P^{\prime }_2|\phi _1\rangle \) 
Notice that \(P_2 |\Omega \rangle  = \cos (\alpha _2)|\phi _2\rangle  = |\phi _2\rangle \langle \phi _2| \cdot |\Omega \rangle \)  hence \(P^{\prime }_2 |\Omega \rangle  = {\mathbf {0}}\) . This implies that \(P^{\prime }_2 |B\rangle  = {\mathbf {0}}\)  and
\(P^{\prime }_2 |\phi _1\rangle  = P^{\prime }_2 (x|A\rangle ) = z |A^{\prime }\rangle \) 

for some \(|A^{\prime }\rangle \)  orthogonal to \(|\Omega \rangle \)  and \(|B\rangle \)  and \(|z| \le |x|\) . So we rewrite
\(\frac{1}{\cos (\alpha _1)}|W\rangle  & = \langle {\phi _1}|{\phi _2}\rangle |\phi _2\rangle  + P^{\prime }_2|\phi _1\rangle  \nonumber \\& = \left(\cos {\alpha _1}\cos (\alpha _2) + \sin (\alpha _2)y\right) |\phi _2\rangle  + z |A^{\prime }\rangle \) 

Let \(u = \left(\cos {\alpha _1}\cos (\alpha _2) + \sin (\alpha _2)y\right)\)  so that
\(|W\rangle  = \cos (\alpha _1)u|\phi _2\rangle  + \cos (\alpha _1)z|A^{\prime }\rangle \) 
 The norm of \(|W\rangle \)  is therefore
\( \left\Vert |W\rangle \right\Vert  = |\cos (\alpha _1)| \sqrt{|u|^2 + |z|^2}.\) 
Let \(|\widetilde{W}\rangle  = |W\rangle /\left\Vert |W\rangle \right\Vert \) . From Equation REF , we have
\(|\langle {\Omega }|{\widetilde{W}}\rangle |^2 & = (\frac{|\cos (\alpha _2)\cos (\alpha _1)u|}{\left\Vert |W\rangle \right\Vert })^2 = \frac{\cos ^2(\alpha _2)u^2}{u^2 + z^2} \\ & \ge \frac{\cos ^2(\alpha _2)u^2}{u^2 + (1 - \cos ^2(\alpha _1) - y^2)} .\) 
Using lemma REF , we obtain \(|\langle {\Omega }|{\widetilde{W}}\rangle |^2 \ge \cos ^2(\alpha _1) + \cos ^2(\alpha _2) - 1\) . We hence write \(|\langle {\Omega }|{\widetilde{W}}\rangle |^2 = \cos ^2(\beta )\)  for some \(\beta \le \alpha _1 + \alpha _2\) . In order to conclude, we define \(Angle(|\psi \rangle ,|\phi \rangle ) = \arccos (|\langle {\psi }|{\phi }\rangle |)\) . The angle function is a distance measure [14]}. We will use several times the trigonometric inequality \(\cos (\rho + \theta ) \ge \cos ^2(\rho ) + \cos ^2(\theta ) - 1\)  for any \(\rho ,\theta \)  with \(\rho + \theta \le \pi /2\)  and we can hence write
\(\left\Vert P_3 |\widetilde{W}\rangle \right\Vert ^2 & \ge |\langle {\phi _3}|{\widetilde{W}}\rangle |^2 \\& = \cos ^2\left(Angle\left(|\phi _3\rangle ,|\widetilde{W}\rangle \right)\right) \\& \ge \cos ^2\left(Angle(|\phi _3\rangle ,|\Omega \rangle ) + Angle(|\Omega \rangle ,|\widetilde{W}\rangle )\right) \\& \ge \cos ^2(\alpha _3 + \beta ) \\& \ge \left(\cos ^2(\alpha _3) + \cos ^2(\beta ) - 1\right)^2 \\& = \left(\cos ^2(\alpha _1) + \cos ^2(\alpha _2) + \cos ^2(\alpha _3) - 2\right)^2 = \varepsilon ^2\) 

From there, we can conclude
\(\left\Vert P_3P_2P_1 |\Omega \rangle \right\Vert ^2 & = \left\Vert P_3 |W\rangle \right\Vert ^2 = \left\Vert P_3 |\widetilde{W}\rangle \right\Vert ^2 \left\Vert W\right\Vert ^2 \\& \ge \varepsilon ^ 2 \left\Vert P_2P_1|\Omega \rangle \right\Vert ^2\) 

In order to conclude, we use \( |y| \le sin(\alpha _1)\)  (Equation REF ) which gives \(|u| \ge \cos (\alpha _1 + \alpha _2)\) , and
\(\left\Vert P_2P_1|\Omega \rangle \right\Vert ^2 = \left\Vert W\right\Vert ^2 \ge \cos ^2(\alpha _1)\cos ^2(\alpha _1 + \alpha _2).\) 
which gives
\(\left\Vert P_3P_2P_1 |\Omega \rangle \right\Vert ^2 \ge \varepsilon ^2 \cos ^2(\alpha _1)\cos ^2(\alpha _1 + \alpha _2)\) 

Similarly, we have
\(\left\Vert P_3P_1P_2 |\Omega \rangle \right\Vert ^2 & = \varepsilon ^2\left\Vert P_1P_2 |\Omega \rangle \right\Vert ^2 \left\Vert P_3 |\widetilde{W}\rangle \right\Vert ^2 \nonumber \\& \ge \varepsilon ^ 2 \cos ^2(\alpha _2)\cos ^2(\alpha _1 + \alpha _2) \) 
\(\frac{1}{2} \left(\left\Vert P_3P_2P_1 |\Omega \rangle \right\Vert ^2 + \left\Vert P_3P_1P_2 |\Omega \rangle \right\Vert ^2\right) \ge \\\frac{\varepsilon ^2}{2}(\cos ^2(\alpha _1) + \cos ^2(\alpha _2))cos^2(\alpha _1 + \alpha _2)\) 
Now, since \(cos^2(\alpha _1) + \cos ^2(\alpha _2) \ge 1 + 3 \varepsilon \)  (from \(V \ge \frac{2}{3} + \varepsilon \) ), we have \(\cos ^2(\alpha _1) + \cos ^2(\alpha _2) \ge 1\)  and \(\cos ^2(\alpha _1 + \alpha _2) \ge \left(\cos ^2(\alpha _1) + \cos ^2(\alpha _2) - 1\right)^2 = (3\varepsilon )^2\) , from which we conclude
\(\frac{1}{2} \left(\left\Vert P_3P_2P_1 |\Omega \rangle \right\Vert ^2 + \left\Vert P_3P_1P_2 |\Omega \rangle \right\Vert ^2\right) \ge \frac{9\varepsilon ^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 [2]}.We need the following statement
Lemma 3 (Proposition 4 from [2]}) 
Let a projector \(P = \sum _{i = 1}^m\)  where \(\lbrace P_i\rbrace _{i \in [m]}\)  are orthogonal projectors. For any pure state \(|\psi \rangle \) , we have
\( \sum _{i = 1}^m P_i |\psi \rangle \langle \psi | P_i \ge \frac{1}{m} P |\psi \rangle \langle \psi | P.\) 

With this lemma, we can prove our main proposition.
[Proof of Proposition REF ]
First, in order to use Proposition REF , we need to work on pure states similarly as in [2]}. Assume \(\sigma \)  is a quantum mixed state in some Hilbert space \({B}\)  and the projectors \(P_i^s\)  act on \({B}\) .
We add an extra Hilbert space
\(\mathcal {E}\) . We consider a purification \(|\Omega \rangle \)  of \(\sigma \)  in \({B}\mathcal {E}\)  and define \(\widetilde{P}_i = P_i \otimes I_E\) , \(\widetilde{P}_i ^s= P_i^s \otimes I_E\) , \(\widetilde{V} = \sum _i tr(\widetilde{P}_i|\Omega \rangle )\)  and
\( \widetilde{E} = \frac{1}{2}\left(\widetilde{E}_1 + \widetilde{E}_2\right)\) 
with
\(\widetilde{E}_1 & =\Big (\sum _{s_3 = 1}^{S_3} \sum _{s_2 = 1}^{S_2} \sum _{s_1 = 1}^{S_1} tr\left(\widetilde{P}_3^{s_3}\widetilde{P}_2^{s_2}\widetilde{P}_1^{s_1} |\Omega \rangle \langle \Omega | \left(\widetilde{P}_1^{s_1}\right) \left(\widetilde{P}_2^{s_2}\right)\right)\\\widetilde{E}_2 & = \sum _{s_3 = 1}^{S_3} \sum _{s_2 = 1}^{S_2} \sum _{s_1 = 1}^{S_1} tr\left(\widetilde{P}_3^{s_3}\widetilde{P}_1^{s_1}\widetilde{P}_2^{s_2} |\Omega \rangle \langle \Omega | \left(\widetilde{P}_2^{s_2}\right) \left(\widetilde{P}_1^{s_1}\right) \right)\Big ).\) 

One can easily check that \(\widetilde{V} = V\)  and \(\widetilde{E} = E\) .
Now, using Lemma REF  twice, we have
\(\widetilde{E}_1 & \ge \frac{1}{S_1} \sum _{s_3 = 1}^{S_3} \sum _{s_2 = 1}^{S_2} tr\left(\widetilde{P}_3^{s_3}\widetilde{P}_2^{s_2}\widetilde{P}_1 |\Omega \rangle \langle \Omega | \widetilde{P}_1 \left(\widetilde{P}_2^{s_2}\right)\right) \\& \ge \frac{1}{S_1S_2}\sum _{s_3 = 1}^{S_3} tr\left(\widetilde{P}_3^{s_3}\widetilde{P}_2 \widetilde{P}_1 |\Omega \rangle \langle \Omega | \widetilde{P}_1 \widetilde{P}_2 \right) \\& = \frac{1}{S_1S_2} tr(\widetilde{P}_3\widetilde{P}_2\widetilde{P}_1|\Omega \rangle \langle \Omega | \widetilde{P}_1\widetilde{P}_2)\) 

Similarly, we can prove
\( \widetilde{E}_2 \ge \frac{1}{S_1S_2} tr(\widetilde{P}_3\widetilde{P}_1\widetilde{P}_2|\Omega \rangle \langle \Omega | \widetilde{P}_2\widetilde{P}_1).\) 
In order to conclude, we use Proposition REF  which directly gives us the desired result.

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 \(\lambda = \frac{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 \(\lambda ^*\)  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) = \lambda ^* P_1+ (1-\lambda ^*)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 \ge P_1\) . Moreover, \((1- \lambda ^*)p^* \le \omega ^*(G^{\mathrm {rel}}_{\mathrm {Stern}})\)  and \(p^* \le 1\) , so \((1-\lambda ^*)p^* \le \min \lbrace \omega ^*(G^{\mathrm {rel}}_{\mathrm {Stern}}),1-\lambda ^*\rbrace \) . We now distinguish 2 cases

If \(\lambda ^* \in [0,1 - \omega ^*(G^{\mathrm {rel}}_{\mathrm {Stern}})]\) , \(P^* \le \lambda ^* P_1 + \omega ^*(G^{\mathrm {rel}}_{\mathrm {Stern}}) P_2\)  and this right hand side is increasing in \(\lambda ^*\) .

If \(\lambda ^* \in [1 - \omega ^*(G^{\mathrm {rel}}_{\mathrm {Stern}}),1]\) , \(P^* \le \lambda ^* P_1 + (1 - \lambda ^*) P_2 = P_2 + \lambda ^*(P_1 - P_2)\)  and this right hand side is decreasing in \(\lambda ^*\)  since \(P_2 \ge P_1\) .

This shows that the best strategy for the prover is to take at the first round \(\lambda ^* = 1 - \omega ^*(G^{\mathrm {rel}}_{\mathrm {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. \(\lambda ^* = 1 - \omega ^*(G^{\mathrm {rel}}_{\mathrm {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,\dots ,X_n\)  are independent random variables taking value in \(\lbrace 0,1\rbrace \) . Let \(X\)  denote their sum, \(p = [X_1]\)  and \(\varepsilon > 0\) . We have
\(\Pr [X \ge pn+ \varepsilon n] & \le 2^{n\left((p+\varepsilon )\log _2(\frac{p}{p+\varepsilon }) + (1-p-\varepsilon )\log _2(\frac{1-p}{1-p-\varepsilon })\right)}, \\\Pr [X \le pn - \varepsilon n] & \le 2^{n\left((p - \varepsilon )\log _2(\frac{p}{p- \varepsilon }) + (1-p+\varepsilon )\log _2(\frac{1-p}{1-p+\varepsilon })\right)}.\) 

In our case, the strategy of the provers outputs `Abort' wp. \(\lambda ^*\)  and they succeed in cheating if there are at most \(F = \lambda R\)  aborts. We use the above Chernoff bound (second equation) with \(n = R, p = \lambda ^* = 1 - \omega ^*(G^{\mathrm {rel}}_{\mathrm {Stern}}), \varepsilon = \lambda ^* - \lambda \)  which bounds the probability that there are less than \(F = \lambda n\)  aborts, and we write
\(P^*(R,F) & \le 2^{R\left(\lambda \log _2(\frac{\lambda ^*}{\lambda }) + (1-\lambda )\log _2(\frac{1-\lambda ^*}{1-\lambda })\right)} \nonumber \\& = 2^{R\left(\lambda \log _2(\frac{1 - \omega ^*(G^{\mathrm {rel}}_{\mathrm {Stern}})}{\lambda }) + (1-\lambda )\log _2(\frac{\omega ^*(G^{\mathrm {rel}}_{\mathrm {Stern}})}{1-\lambda })\right)}\) 

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_{\text{loss}}\) . Let \(CE(R,F,p_{\text{loss}})\)  denote the completeness error and \(\lambda = \frac{F}{R}\) . Using again the Chernoff bound (first equation) with \(R = n, p = p_{\text{loss}}, \varepsilon = \lambda - p_{\text{loss}}\) , we have
\(CE(R,F,p_{\text{loss}}) \le 2^{R\left(\lambda \log _2(\frac{p_{\text{loss}}}{\lambda }) + (1-\lambda )\log _2(\frac{1 - p_{\text{loss}}}{1-\lambda })\right)}.\) 


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.
First scenario, different values of \(n\) .
\( \ \)
<FIGURE>
<FIGURE>
<FIGURE>
<FIGURE>
<FIGURE>
<FIGURE>
<FIGURE>
<FIGURE>

Second scenario, different values of \(n\) .
\( \ \)
<FIGURE>
<FIGURE>
<FIGURE>
<FIGURE>
<FIGURE>
<FIGURE>
<FIGURE>
<FIGURE>
