Recursive Cheating Strategies for the Relativistic F_Q Bit Commitment Protocol

Abstract

In this paper, we study relativistic bit commitment, which uses timing and location constraints to achieve information theoretic security. Using those constraints, we consider a relativistic bit commitment scheme introduced by Lunghi et al. This protocol was shown secure against classical adversaries as long as the number of rounds performed in the protocol is not too large. In this work, we study classical attacks on this scheme. We use the correspondence between this protocol and the CHSH_Q game—which is a variant of the CHSH game—to derive cheating strategies for this protocol. Our attack matches the existing security bound for some range of parameters and shows that the scaling of the security in the number of rounds is essentially optimal.

1. Introduction

1.1. Context and State of the Art

The goal of relativistic cryptography is to exploit the no superluminal signaling (NSS) principle in order to perform various cryptographic tasks. NSS states that no information carrier can travel at a speed greater than the speed of light. Note that NSS is closely related to the non-signaling principle that says that a local action performed in a laboratory cannot have an immediate influence outside of the lab. NSS is more precise since it gives an upper bound on the speed at which such an influence can propagate. Apart from this physical principle, we want to ensure information-theoretic security meaning that the proposed schemes cannot be attacked by any classical (nor quantum) computer, even with infinite computing power. This is in contrast with used schemes, which most often rely on computational assumptions such as the hardness of factoring [1].

The idea of using physical assumptions laws to ensure information theoretic security for cryptographic schemes is not a new one. The most striking example in recent years is Quantum Key Distribution (QKD), which allows two distant parties to distill a secret key with information-theoretic security [2]. The main idea of QKD is to exchange quantum states on an insecure quantum channel and check a posteriori whether they have been disturbed. If not, it means that no eavesdropper was tampering with the quantum channel and the quantum states can be safely used to distill a secret. In fact, this work provided that the quantum states are not too noisy. QKD is quite practical and has indeed been widely deployed, but, at the same time, it requires dedicated hardware and can only work today provided the two parties are not too far away from each other, at most a few hundred kilometers (see for instance [3] for the current record).

The idea of using the NSS principle for cryptographic protocols originated in a pioneering work by Kent in 1999 [4] as a way to physically enforce a non communication constraint between the different agents of one party (the idea of splitting up a party into several agents dates back to [5], but without an explicit implementation proposal). The original goal of Kent was to bypass the no-go theorems for quantum bit-commitment [6,7]. Interestingly, this original protocol was classical and allowed for several rounds that increased the lifespan of the protocol. However, the protocol required to exchange messages whose length scaled exponentially in the number of rounds (i.e., the commitment time) and a feasible implementation was not possible for a large number of rounds. A subsequent work [8] improved this scaling, but, to our knowledge, no precise time/security tradeoff is available for this protocol.

More recently, quantum relativistic bit commitment protocols were developed where the parties exchange quantum systems, with the hope that combining the no superluminal signaling principle with quantum theory will lead to more secure (but less practical) protocols [9,10,11]. In particular, the protocol [10] was implemented in [12]. We note that the scope of relativistic cryptography is not limited to bit commitment. For instance, there was recently some interest (sparked again by Kent) for position–verification protocols [13,14,15], but, contrary to the case of bit commitment, it was shown that secure position–verification is impossible both in the classical and the quantum settings [16,17].

The original idea of [5] was recently revisited by Crépeau et al. [18] (see also [19]). Based on this work, Lunghi et al. devised a multi-round bit commitment protocol involving only four agents, two for Alice and two for Bob [20]. They managed to prove that this protocol, which we call the “${\mathbb{F}}_Q$ protocol” from now on, remains secure for several rounds, against classical attacks. Unfortunately, this proof was rather inefficient since the complexity of the protocol (the size of the messages the agents need to exchange at each round) scaled exponentially with the number of rounds. Recently, two papers improved the security proof and showed that the complexity of the protocol in fact only scales logarithmically with the number of rounds [21,22], implying that the commitment time is essentially unlimited:

Theorem 1

([21,22]). The ${\mathbb{F}}_Q$ relativistic m-round bit commitment protocol is ε-binding with $\epsilon =\mathcal{O}(\frac{m}{\sqrt{Q}})$ against classical adversaries, meaning that Alice’s cheating probability is at most $\frac{1}{2}+\mathcal{O}(\frac{m}{\sqrt{Q}})$.

While the two proofs of this fact are very different, they rely to some extent on the analysis of ${\mathsf{CHSH}}_{\mathsf{Q}}$, a non-signaling game that generalizes the well-known $\mathsf{CHSH}$ game to the case where inputs and outputs are not restricted to being bits, but rather belong to ${\mathbb{F}}_Q$ the Galois Field of order Q.

Notice that, in the way the cheating probability is defined, a perfectly secure protocol will have cheating probability of $\frac{1}{2}$ for both Alice and Bob and an $\epsilon$-secure (here $\epsilon$-binding) protocol will have a cheating probability of $\frac{1}{2}+\epsilon$. The protocol has (stand-alone) security when $\epsilon$ is small.

Theorem 1 shows that the protocol is secure as long as $m\ll \sqrt{Q}$, but it was not known for larger values of Q, in particular when m approaches, or even exceeds $\mathsf{\Omega }(\sqrt{Q})$. Very recently, this protocol has been implemented by keeping the agents 7 km apart with a validity time of 24 h [23]. In addition, it is important to know that the number of bits sent at each round is $log(Q)$ and therefore Q can be efficiently made exponentially big in the security parameter.

Until now, no cheating strategy has been proposed for this scheme.

1.2. Contributions

Our main contribution is to present the first attack on the ${\mathbb{F}}_Q$ protocol. We show the following.

Theorem 2.

There exists an attack on the m-round ${\mathbb{F}}_Q$ protocol in which Alice’s cheating probability is

$$1-{\displaystyle \frac{1}{2}}{\left(\left(1-{\displaystyle \frac{1}{Q}}\right)\left(1-\omega ({\mathsf{CHSH}}_Q)\right)\right)}^{\lfloor \frac{m-1}{3}\rfloor },$$

where $\omega ({\mathsf{CHSH}}_{\mathsf{Q}})$ is the classical value of the ${\mathsf{CHSH}}_{\mathsf{Q}}$ game and $m\ge 3$.

In [24], it was shown for any prime p and integer n that

$$\omega ({\mathsf{CHSH}}_{\mathsf{Q}})=\left\{\begin{array}{cc}\mathsf{\Omega }(\sqrt{\frac{1}{Q}}),\hfill & \mathrm{if}Q=p^{2n},\hfill \\ \mathcal{O}(Q^{-\frac{1}{2}-{\epsilon }_0}),\hfill & \mathrm{if}Q=p^{2n+1},\hfill \end{array}\right.$$

where ${\epsilon }_0$ is a constant proven to be positive.

In particular, Theorem 2, combined with the above bound, shows that the upper bound of [21,22] (Theorem 1) is essentially optimal when considering an even prime power:

Corollary 1.

For any integer n, prime number p and $Q=p^{2n}$, there is a cheating strategy for Alice that achieves success probability

$$1-\frac{1}{2}{\left(1-\mathsf{\Omega }(\frac{1}{\sqrt{Q}})\right)}^{\lfloor \frac{m-1}{3}\rfloor }.$$

• If $m\ll \sqrt{Q}$, then the above cheating probability is equal to $\frac{1}{2}+\mathsf{\Omega }(\frac{m}{\sqrt{Q}})-o(\frac{m}{\sqrt{Q}})$.
• If $m=t\sqrt{Q}$, then the above cheating probability is lower bounded by $1-O(e^{-\frac{t}{3}})$, which quickly approaches 1 as t increases.

From the above bounds, we can conclude that, up to constant factors, our attack is optimal when Q is an even power of a prime.

We note also that there is an upper bound on the value of ${\mathsf{CHSH}}_{\mathsf{Q}}$ when Q is an odd power of a prime. In this case, we have $\omega ({\mathsf{CHSH}}_{\mathsf{Q}})=\mathsf{\Omega }(Q^{-2/3})$ [24,25]. From there, we have the following.

Corollary 2.

For any integer n, prime number p and $Q=p^{2n+1}$, there is a cheating strategy for Alice that achieves success probability

$$1-\frac{1}{2}{\left(1-\mathsf{\Omega }(Q^{-2/3})\right)}^{\lfloor \frac{m-1}{3}\rfloor }.$$

Therefore, if $m=t{Q}^{\frac{2}{3}}$, then Alice can cheat with probability $1-O(e^{-\frac{t}{3}}),$ which quickly converges to 1 as t increases.

This result also shows that even an improved bound on $\omega ({\mathsf{CHSH}}_{\mathsf{Q}})$ variants presented in [26] cannot be used to improve—except in the constants—the security of the ${\mathbb{F}}_Q$ protocol, at least for even prime powers of Q.

Our second contribution is an extension of this attack to more realistic scenarios from the attacker’s point of view. In the relativistic model, we assume that cheating Alice can perform communications between ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$ such that both agents of Alice know exactly the whole transcript of the protocol, except the last round message sent to the other Alice. Proving security in this setting allows us to minimize the spacetime requirements in order to achieve security.

However, our attack also assumes this power for cheating Alice, and this could be very challenging in practice. Therefore, we introduce the notion of propagation time, which corresponds to the number of rounds $\rho$ that can pass until the Alices are able to send some information to one another. In the original model, this propagation time is two rounds. We extend Theorem 2 to the following setting:

• The propagation time $\rho$ can be larger than 2;
• The two Alices know the bit they want to reveal only after $k_0\ge 1$ rounds. We call $k_0$ the decision time.

Showing that the attack works in this setting ensures that simple countermeasures consisting of increasing the distance between the two pairs will not significantly reduce the efficiency of the attack. We show the following.

Theorem 3.

For any propagation time $\rho \ge 2$, and any decision time $k_0$, there exists an attack on the m-round ${\mathbb{F}}_Q$ protocol, where Alice’s cheating probability is

$$1-{\displaystyle \frac{1}{2}}{\left((1-{\displaystyle \frac{1}{Q}})\left(1-\omega ({\mathsf{CHSH}}_{\mathsf{Q}})\right)\right)}^{\lfloor \frac{m-k_0-1}{\rho +1}\rfloor }$$

for $m\ge k_0+2$.

In Section 2, we present the ${\mathbb{F}}_Q$ protocol as well as the ${\mathsf{CHSH}}_{\mathsf{Q}}$ game. In Section 3, we present our main result, namely the attack on the ${\mathbb{F}}_Q$ protocol. In Section 4, we present the extension of this attack to more realistic scenarios.

2. Preliminaries

2.1. Bit Commitment

Bit commitment is a cryptographic primitive between two distrustful parties Alice and Bob, which consists of two phases: a Commit phase and a Reveal phase. Alice has a random bit d at the beginning of the protocol. In the commit phase, Alice will commit to this value d by performing some communication protocol such that, at the end of the commit phase, Bob knows no information about d. In the second phase, the reveal phase, Alice and Bob also perform some communication, which results in Alice revealing d. A desired property here is that Alice is unable to reveal a bit different from the one chosen during the commit phase.

In some sense, a bit commitment protocol simulates a digital safe. In the commit phase, Alice writes her input d on a piece of paper, puts that paper into the safe and sends the safe to Bob. If Bob has no information about the key safe, then he cannot open it and therefore has no information about d. In the reveal phase, Alice would send to Bob the key to open the safe. However, she cannot change the value of the bit in the safe because Bob has control of the safe. This primitive has been widely studied. However, bit commitment can only be performed with computational security in most usual models.

We now give a formal definition of the bit commitment scheme.

Definition 1.

A bit commitment scheme is an interactive protocol between Alice and Bob with two phases, a Commit phase and a Reveal phase.

• Commit phase. Alice chooses a uniformly random input d that she wants to commit to. To do so, Alice and Bob perform a communication protocol that corresponds to this commit phase.
• Reveal phase. Alice interacts with Bob in order to reveal d. To do so, they perform a second communication protocol, where, at the end, Bob should know the value revealed by Alice. Bob, depending on this revealed value and the interaction with Alice, outputs “Accept” or “Reject”.

We also define the following security requirements for the commitment scheme.

Definition 2.

A bit commitment protocol is said to be correct if when both players are honest, Bob never outputs “Reject”.

A cheating strategy S for Alice can be therefore decomposed into a cheating strategy $S_{commit}$ for the commit phase and $S_{reveal}$ for the reveal phase and we will usually write $S=(S_{commit},S_{reveal})$. The goal of a cheating Alice is to choose the value she wants to reveal only after the commit phase. The reveal strategy $S_{reveal}$ will depend on the value d she wants to reveal. We denote by $S_{reveal}(d)$ Alice’s cheating strategy in the reveal phase for a fixed d.

Definition 3.

For a fixed cheating strategy $S=(S_{commit},S_{reveal})$ for Alice, we define Alice’s cheating probability $P_A^{\ast }(S)$ as

$$\begin{array}{cc}\hfill P_A^{\ast }(S):=& \frac{1}{2}Pr[\mathit{Alice}\mathit{successfully}\mathit{reveals}d=0|(S_{\mathit{commit}},S_{\mathit{reveal}}(0))]+\hfill \\ & \frac{1}{2}Pr[\mathit{Alice}\mathit{successfully}\mathit{reveals}d=1|(S_{\mathit{commit}},S_{\mathit{reveal}}(1))].\hfill \end{array}$$

Definition 4.

We define Alice’s optimal cheating probability $P_A^{\ast }$ as

$$P_A^{\ast }:=\underset{S=(S_{commit},S_{reveal})}{max}{P}_A^{\ast }(S).$$

We say that a bit commitment is ε sum-binding if $P_A^{\ast }\le \frac{1}{2}+\epsilon$.

Here, we used one of several possible definitions for the binding property. This definition is weak, since it doesn’t necessarily behave well under composition. In order to prove security, even for relativistic bit commitment protocols, some stronger definitions of security are used (see for example [22]). While using a stronger security definitions strengthens upper bounds on the cheating probability, it is by using the weakest security definition that we have the strongest lower bounds on those cheating probabilities. Since in this paper, we present cheating strategies, i.e., lower bounds, we use the weak notion of sum-binding.

Another security condition we want to ensure is the hiding property. At the end of the commit phase, we don’t want Bob to have a lot of information about the committed bit d. This means that to ensure the hiding property, we will only be interested in a cheating Bob’s strategy during the commit phase, and a cheating strategy $S^B$ for Bob will be a strategy that he will use to try to learn d after the commit phase.

Definition 5.

For a fixed cheating strategy $S^B$ for Bob, we define his cheating probability $P_B^{\ast }(S^B)$ as

$$P_B^{\ast }(S^B):=Pr\left[\mathit{Bob}\mathit{guesses}d\mathit{after}\mathit{the}\mathit{Commit}\mathit{phase}\right|S^B].$$

Definition 6.

We define Bob’s optimal cheating probability $P_B^{\ast }$ as

$$P_B^{\ast }:=\underset{S^B}{max}{P}_B^{\ast }(S^B).$$

We say that a bit commitment is ε-hiding if $P_B^{\ast }\le \frac{1}{2}+\epsilon$.

2.2. Relativistic Bit Commitment

A relativistic bit commitment scheme is a commitment scheme where we use physical property that no information carrier can travel faster than the speed of light. In order to take advantage of this principle, we split Alice (resp. Bob) into two agents ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$ (respectively, ${\mathcal{B}}_1$ and ${\mathcal{B}}_2$). For each $i\in \{1,2\}$, ${\mathrm{Alice}}_i$ interacts only with ${\mathrm{Bob}}_i$. If we put the two pairs $({\mathcal{A}}_1,{\mathcal{B}}_1)$ and $({\mathcal{A}}_2,{\mathcal{B}}_2)$ far apart, and use some timing constraints, we can create some non-signaling type scenarios. Here, we will only use the property that the two honest Bobs know their respective location. In particular, there is no trust needed regarding the location of the cheating parties.

The security definitions for relativistic bit commitment are the ones we presented in the section above. We will now describe the ${\mathbb{F}}_Q$ relativistic bit commitment scheme. This description will consist of four phases: the preparation phase, the commit phase, the sustain phase and the reveal phase. The preparation phase is some preprocessing phase that can be done anytime before the protocol. The sustain phase can be seen as a part of the reveal phase and corresponds to the time where the committed bit is safe. We assume here that the two Alices know at the beginning of the sustain phase the bit d they want to reveal. In Section 4, we will relax this requirement.

The single-round ${\mathbb{F}}_Q$ protocol—The single-round version corresponds to the protocol introduced by Crépeau et al. [18] (see also [19]). Both players, Alice and Bob, have agents ${\mathcal{A}}_1,{\mathcal{A}}_2$ and ${\mathcal{B}}_1,{\mathcal{B}}_2$ present at two spatial locations, 1 and 2, separated by a distance D. We consider the case where Alice makes the commitment. The protocol (followed by honest players) consists of four phases: preparation, commit, sustain and reveal. The sustain phase in the single-round protocol is trivial and simply consists in waiting for a time less than $D/c$, which is the time needed for light to travel between the two locations. The bit commitment protocol goes as follows:

• Preparation phase: ${\mathcal{A}}_1,{\mathcal{A}}_2$ (resp. ${\mathcal{B}}_1,{\mathcal{B}}_2$) share a random number $a\in {\mathbb{F}}_Q$ (resp. $x\in {\mathbb{F}}_Q$);
• Commit phase: ${\mathcal{B}}_1$ sends x to ${\mathcal{A}}_1$, who returns $y=a+d\times x$ where $d\in \{0,1\}$ is the committed bit;
• Sustain phase: ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$ wait for some time $\tau <D/c$;
• Reveal phase: ${\mathcal{A}}_2$ reveals the values of d and a to ${\mathcal{B}}_2$ who checks that $y=a+d\times x$.

The multi-round protocol—The protocol above was recently extended to a multi-round commitment scheme [20]. The main idea to increase the commitment time is to delay the reveal phase and have ${\mathcal{A}}_2$ commit to the string a instead of revealing it. In fact, the new sustain phase will now consist of many rounds where the active players (i.e., the player who commits in that given round and the corresponding player for Bob) alternate between locations 1 and 2, separated by a distance D. The m-round bit commitment protocol goes as follows:

• Preparation phase: ${\mathcal{A}}_1,{\mathcal{A}}_2$ (resp. ${\mathcal{B}}_1,{\mathcal{B}}_2$) share m random numbers $a_1,...,a_m$ (resp. $x_1,...,x_m$) $\in {\mathbb{F}}_Q$.
• Commit phase: ${\mathcal{B}}_1$ sends $x_1$ to ${\mathcal{A}}_1$, who returns $y_1=d\times x_1+a_1$, where $d\in \{0,1\}$ is the committed bit.
• Sustain phase: for each round k, with $2\le k<m$, ${\mathcal{B}}_{k\mathrm{mod}2}$ sends $x_k$ to ${\mathcal{A}}_{k\mathrm{mod}2}$, who returns $y_k=x_k\times a_{k-1}+a_k$.
• Reveal phase: ${\mathcal{A}}_1$ reveals d and $y_m=a_{m-1}$ to ${\mathcal{B}}_1$. Bob checks that $y_m={\alpha }_{m-1}$, where we recursively define ${\alpha }_0:=d$, ${\alpha }_i:=y_i-x_i\ast {\alpha }_{i-1}$. We defined ${\alpha }_i$ such that it corresponds to what $a_i$ “should be”.

The main idea of the multi-round protocol is to delay the reveal phase in order to increase the commitment time. This delay is obtained by making the passive Alice commit to the value of the string she was supposed to reveal in the previous round. Since each round increases the total commitment time by $D/c$, modulo the time needed for the various algebraic manipulations in ${\mathbb{F}}_Q$, one sees that the required number of rounds scales linearly with the commitment time one wishes to achieve.

We require that round j finishes before any information about $x_{j-1}$ reaches the other Alice. For any j, we therefore have the following: active Alice has no information about $x_{j-1}$. This means that $y_j$ is independent from $x_{j-1}$. This will be crucial in order to show security of the protocol. One important thing to notice is that d, the bit Alice wants to reveal can be decided just after the commit phase. Therefore, $y_1$ is independent of d but all the other messages $y_2,...,y_m$ can depend on d.

Both of those protocols are perfectly hiding. Moreover, from Theorem 1, the multi-round protocol is $\epsilon$ sum-binding, with $\epsilon =O(\frac{m}{\sqrt{Q}})$.

2.3. The ${\mathsf{CHSH}}_{\mathsf{Q}}$ Game

A crucial tool for our attack (and for the previous security analysis) is the ${\mathsf{CHSH}}_Q$ two-player game introduced by Buhrman and Massar [27]. This game is a natural generalization of the $\mathsf{CHSH}$ game to the field ${\mathbb{F}}_Q$, where two cooperating but non-communicating parties, Alice and Bob, are, respectively, given an input x and y chosen uniformly at random from ${\mathbb{F}}_Q$, and must output two numbers $a,b\in {\mathbb{F}}_Q$. They win the game whenever the condition $a+b=x\times y$ is satisfied. The value of a game G, denoted $\omega (G)$, corresponds to the maximum probability of winning the game. A recent result by Bavarian and Shor [24] establishes bounds on $\omega ({\mathrm{CHSH}}_Q)$. They show the following.

Proposition 1.

For any prime p and integer n, we have

$$\omega ({\mathsf{CHSH}}_{\mathsf{Q}})=\left\{\begin{array}{cc}\mathsf{\Omega }(\sqrt{\frac{1}{Q}}),\hfill & ifQ=p^{2n},\hfill \\ \mathcal{O}(Q^{-\frac{1}{2}-{\epsilon }_0}),\hfill & ifQ=p^{2n+1},\hfill \end{array}\right.$$

for some absolute constant ${\epsilon }_0>0$.

We define a variant of the ${\mathsf{CHSH}}_{\mathsf{Q}}$ game, which we call ${{\mathsf{CHSH}}_{\mathsf{Q}}}^{\gamma }$, which will be well defined for any $\gamma \in [0,1]$. We will use this variant in Section 4, when we will have longer propagation and decision times.

Definition 7.

In $CHSH{Q}^{\gamma }$, Alice receives $x=0$ with probability γ and a random element $x\in {\mathbb{F}}_Q^{\ast }$, each with probability $\frac{1-\gamma }{Q-1}$. Bob receives an input y according to the same probability distribution. They output, respectively, a and b in ${\mathbb{F}}_Q$, and they win the game iff $a+b=x\times y$.

In short, ${{\mathsf{CHSH}}_{\mathsf{Q}}}^{\gamma }$ is the same game as ${\mathsf{CHSH}}_{\mathsf{Q}}$, but the input distribution of each player is slightly biased towards 0. We have by definition ${{\mathsf{CHSH}}_{\mathsf{Q}}}^{\frac{1}{Q}}={\mathsf{CHSH}}_{\mathsf{Q}}$. When playing ${{\mathsf{CHSH}}_{\mathsf{Q}}}^{\gamma }$, we have:

• The probability that Alice and Bob get $(0,0)$ is ${\gamma }^2$.
• The probability that they get an element $(0,i)$ or $(i,0)$ with $i\in {\mathbb{F}}_Q^{\ast }$ is equal to $\frac{\gamma (1-\gamma )}{Q-1}$ for each such element.
• The probability that they get an element $(i,j)$ with $i,j\in {\mathbb{F}}_Q^{\ast }$ is equal to $\frac{{(1-\gamma )}^2}{{(Q-1)}^2}$ for each such element.

In [24], the authors used a shifting technique to show that any strategy for ${\mathsf{CHSH}}_{\mathsf{Q}}$ can be balanced into a strategy with equal winning probability for each input. The technique use relies on adding a random shift to each of the inputs and changing the strategy accordingly. Inspired by those techniques, we can show:

Lemma 1.

For any $\gamma \in [0,1]$, $\omega (CHSH{Q}^{\gamma })\ge \omega ({\mathsf{CHSH}}_{\mathsf{Q}})$.

Proof. 

As randomized strategies are nothing more than linear combinations of deterministic strategies, of which winning probability is given by the same linear combination, we can assume that all used optimal strategies are deterministic without loss of generality.

We consider an optimal strategy $S=(s_1,s_2)$ for the $\mathsf{CHSH}$ game i.e., function $s_1,s_2:{\mathbb{F}}_Q\to {\mathbb{F}}_Q$ such that ${Pr}_{x,y}[s_1(x)+s_2(y)=xy]=\omega ({\mathsf{CHSH}}_{\mathsf{Q}})$, where the probability is over a uniform choice of x and y. We define $p_{x,y}:=1$ if $s_1(x)+s_2(y)=xy$ and 0 otherwise, which implies ${\mathbb{E}}_{xy}{p}_{xy}=\omega ({\mathsf{CHSH}}_{\mathsf{Q}})$.

Let $Z_{u,v}$ be the winning probability using S when considering the following input distribution: Alice receives $x=u$ with probability $\gamma$ and a random element $x\in {\mathbb{F}}_Q-\left\{u\right\}$, each with probability $\frac{1-\gamma }{Q-1}$. Bob receives an input $y=v$ with probability $\gamma$ and a random element $y\in {\mathbb{F}}_Q-\left\{v\right\}$, each with probability $\frac{1-\gamma }{Q-1}$:

$$\begin{array}{c}\hfill Z_{u,v}:={\gamma }^2{p}_{u,v}+\frac{\gamma (1-\gamma )}{Q-1}\left(\sum _{x\in {\mathbb{F}}_Q-\left\{u\right\}}{p}_{xv}+\sum _{y\in {\mathbb{F}}_Q-\left\{v\right\}}{p}_{uy}\right)+\frac{{(1-\gamma )}^2}{{(Q-1)}^2}\sum _{\begin{array}{c}x\in {\mathbb{F}}_Q-\left\{u\right\}\\ y\in {\mathbb{F}}_Q-\left\{v\right\}\end{array}}{p}_{xy}.\end{array}$$

(1)

In particular, $Z_{0,0}$ corresponds to the probability of winning ${{\mathsf{CHSH}}_{\mathsf{Q}}}^{\gamma }$ when using strategy S. One can check that ${\mathbb{E}}_{u,v}\left[Z_{u,v}\right]=\omega ({\mathsf{CHSH}}_{\mathsf{Q}})$, where the probability is over a uniform choice of u and v. This means that we can fix a pair $(u,v)$ such that $Z_{u,v}\ge \omega ({\mathsf{CHSH}}_{\mathsf{Q}})$.

We now consider the strategy $S^{\prime }=(s_1^{\prime },s_2^{\prime })$, where $s_1^{\prime }(x)=s_1(x+u)-xw$ and $s_2^{\prime }(y)=s_2(y+v)-yu-uv$. $S^{\prime }$ wins for $(x,y)$ precisely when S wins for $(x+u,y+v)$. Indeed:

$$\begin{array}{c}\hfill \begin{array}{ccc}{s}_1^{\prime }(x)+s_2^{\prime }(y)=xy\hfill & \iff \hfill & s_1(x+u)-xv+s_2(y+v)-yu-uv=xy\hfill \\ & \iff \hfill & s_1(x+u)+s_2(y+v)=(x+u)(y+v).\hfill \end{array}\end{array}$$

(2)

Similarly, as before, we define $p_{xy}^{\prime }=1$ if $s_1^{\prime }(x)+s_2^{\prime }(y)=x\times y$ and 0 otherwise. From the above equivalence, we have $p_{x,y}^{\prime }=p_{(x+u),(y+v)}$. We also define

$$\begin{array}{c}\hfill Z_{u,v}^{\prime }:={\gamma }^2{p}_{u,v}^{\prime }+\frac{\gamma (1-\gamma )}{Q-1}\left(\sum _{x\in {\mathbb{F}}_Q-\left\{u\right\}}{p}_{xv}^{\prime }+\sum _{y\in {\mathbb{F}}_Q-\left\{v\right\}}{p}_{uy}^{\prime }\right)+\frac{{(1-\gamma )}^2}{{(Q-1)}^2}\sum _{\begin{array}{c}x\in {\mathbb{F}}_Q-\left\{u\right\}\\ y\in {\mathbb{F}}_Q-\left\{v\right\}\end{array}}{p}_{xy}^{\prime }.\end{array}$$

(3)

Notice that $Z_{0,0}^{\prime }$ corresponds to the probability of winning ${{\mathsf{CHSH}}_{\mathsf{Q}}}^{\gamma }$ when using strategy $S^{\prime }$. Moreover, for any $(x,y)$, we have $Z_{x,y}^{\prime }=Z_{x+u,y+v}$. From there, we conclude

$$\begin{array}{c}\hfill \omega ({{\mathsf{CHSH}}_{\mathsf{Q}}}^{\gamma })\ge Z_{0,0}^{\prime }=Z_{u,v}\ge \omega ({\mathsf{CHSH}}_{\mathsf{Q}}),\end{array}$$

(4)

which proves the desired result. ☐

3. Attack with Perfect Conditions

In this section, we present our construction of a cheating strategy that will be essentially optimal for some values of Q. The protocol is perfectly hiding. Therefore, we are only interested in the binding property, i.e., in cheating Alice.

The idea of the attack is the following. Every three rounds (or more in Section 4), Alice’s agents have an occasion to play a ${\mathsf{CHSH}}_{\mathsf{Q}}$ game. If they win this game, which happens with probability $\omega ({\mathsf{CHSH}}_{\mathsf{Q}})$, they can easily fool Bob (with the provided strategy, sending only zeros until the reveal phase is fine). If they do not manage to win the ${\mathsf{CHSH}}_{\mathsf{Q}}$ game, they just try again three rounds later. More precisely, for each step of three rounds, the last two rounds are used to play the ${\mathsf{CHSH}}_{\mathsf{Q}}$ game. The first one allows ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$ to determine if they won during the previous step, or calculate a corrective factor $\eta$ if they did not. Thus, for a m-round protocol, Alice’s agent can play roughly $\frac{m}{3}$ such ${\mathsf{CHSH}}_{\mathsf{Q}}$ games. As it is sufficient for them to win one of these games, we see that cheating probability grows exponentially with the number of rounds. Moreover, at each of these sets of three rounds, an additional factor $(1-\frac{1}{Q})$ appears. Indeed, if at the third round of the set Bob sends a 0, Alice is also in a situation in which she can cheat because this 0 makes Alice’s error collapse to zero. However, the contribution of this additional factor can be neglected (it is only $\mathcal{O}(\frac{1}{Q})$, compared to the $\mathcal{O}(\frac{1}{\sqrt{Q}})$ given by ${\mathsf{CHSH}}_{\mathsf{Q}}$).

We assume for now that the propagation time of the information is two rounds. This means that when ${\mathrm{Alice}}_{(i\mathrm{mod}2)}$ receives $x_i$, the other Alice will know the value of $x_i$ at round $i+2$. Therefore, a cheating strategy for Alice is described by a m-tuple of functions $S=(s_1,...,s_m)$, where each $s_i$ corresponds to Alice’s output function at round i. The function $s_1$ is a function of $x_1$ and $s_i$ is a function of $(x_0,...,x_{i-2},x_i)$ for $i\ge 1$, where we use the convention $x_0=d$. For each $i\ge 1,x_i\in {\mathbb{F}}_Q$ and the output space of each $s_i$ is ${\mathbb{F}}_Q$.

Consider any fixed cheating strategy S for Alice. At the end of the protocol, Bob checks that $y_m={\alpha }_{m-1}$. When we expand ${\alpha }_{m-1}$ as a function of $(d,x_1,...,x_{m-1})$, the checking condition, which we call ${\mathcal{C}}_m$, becomes

$$\begin{array}{c}\hfill y_m=y_{m-1}-x_{m-1}\left(y_{m-2}-x_{m-2}\left(...\dots -x_2(y_1-d·x_1)...\right)\right).\end{array}$$

(5)

If Equation (5) is not verified, Alice is caught cheating. On the other hand, if ${\mathcal{C}}_m$ is verified, then Bob cannot distinguish an honest Alice from a dishonest one, and he does not abort.

Let ${\mathcal{C}}_m(S,d,x_1,...,x_{m-1})$ be the event that corresponds to the above equality being verified. Alice’s cheating probability using S, which we denote $g_m(S)$, is therefore

$$\begin{array}{c}\hfill g_m(S):=\underset{d,x_1,...,x_{m-1}}{Pr}\left[{\mathcal{C}}_m(S,d,x_1,...,x_{m-1})\right],\end{array}$$

(6)

where d is a uniformly random bit and $x_1,...,x_{m-1}$ are uniformly random elements of ${\mathbb{F}}_Q$. We also define $g_m:={max}_S{g}_m(S)$, which is Alice’s maximal cheating probability in ${\mathcal{P}}_m$. In this section, we present a cheating strategy S for Alice such that

$$\begin{array}{c}\hfill g_m(S)=\frac{1}{2}+\frac{1}{2}\left(1-{\left(1-\omega ({\mathsf{CHSH}}_{\mathsf{Q}})\right)}^{\lfloor \frac{m-1}{3}\rfloor }\right),\end{array}$$

(7)

which will prove Theorem 2. In order to do so, we first modify protocol ${\mathcal{P}}_m$ to make it more symmetric (Section 3.1). Then, we describe our attack (Section 3.2) and we prove its cheating probability (Section 3.3).

3.1. Symmetrization of the Protocol

We want to describe a recursive strategy for protocol ${\mathcal{P}}_m$. Unfortunately, this protocol induces a difference between Alice’s strategy at round $1\le k<m$ and her strategy at round m. Because of that, it is difficult to study the protocol recursively.

We therefore consider a modified protocol ${\mathcal{P}}_m^{\prime }$, which, as we will show, is a bit easier than ${\mathcal{P}}_m$ to win, but harder than ${\mathcal{P}}_{m+1}$. In this modified version, at round m, ${\mathrm{Bob}}_{m\mathrm{mod}2}$ sends an additional random string $x_m\in {\mathbb{F}}_Q$, and ${\mathrm{Alice}}_{m\mathrm{mod}2}$ returns $y_m=x_m\times a_{m-1}$ instead of $y_m=a_{m-1}$. All other rounds are unchanged. Similarly, as for ${\mathcal{P}}_m$, a cheating strategy for Alice $S^{\prime }$ can be described as a m-tuple of functions $(s_1^{\prime },...,s_m^{\prime })$ that give Alice’s outputs $y_i$ depending on her accessible information at round i.

Bob checks now that $y_m=x_m\times {\alpha }_{m-1}$, and, therefore, the condition Alice must satisfy to win is modified into ${\mathcal{C}}_m^{\prime }(S^{\prime },d,x_1,...,x_m)$, where

$$\begin{array}{c}\hfill {\mathcal{C}}_m^{\prime }(S^{\prime },d,x_1,...,x_m)\iff y_m=x_m\left(y_{m-1}-x_{m-1}\left(y_{m-2}-x_{m-2}\left(...\dots -x_2(y_1-d·x_1)...\right)\right)\right).\end{array}$$

(8)

By expanding ${\mathcal{C}}_m^{\prime }(S^{\prime },d,x_1,...,x_m)$, it can be written down as:

$$\begin{array}{ccc}{y}_m=\hfill & & x_m·y_{m-1}\hfill \\ & -\hfill & x_m·x_{m-1}·y_{m-2}\hfill \\ & +\hfill & x_m·x_{m-1}·x_{m-2}·y_{m-3}\hfill \\ & ⋮\hfill & ⋮\hfill \\ & -\hfill & {(-1)}^m{x}_m·x_{m-1}·x_{m-2}·\dots ·x_1·d,\hfill \end{array}$$

(9)

or using a compact form:

$$\begin{array}{c}\hfill {\mathcal{C}}_m^{\prime }(S^{\prime },d,x_1,...,x_m)\iff y_m=\sum _{i=1}^{m-1}\left({(-1)}^{m-i+1}{y}_i·\prod _{j=i+1}^m{x}_j\right)-{(-1)}^{m}d·\prod _{j=1}^m{x}_j.\end{array}$$

(10)

For a cheating strategy $S^{\prime }$, Alice’s winning probability $g_m^{\prime }(S^{\prime })$ for this modified protocol is therefore defined as

$$\begin{array}{c}\hfill g_m^{\prime }(S^{\prime }):=\underset{d,x_1,...,x_m}{Pr}\left[{\mathcal{C}}_m^{\prime }(S^{\prime },d,x_1,...,x_m)\right]\mathrm{and}{g}_m^{\prime }:=\underset{S^{\prime }}{max}{g}_m^{\prime }(S^{\prime }).\end{array}$$

(11)

We show the following

Lemma 2.

$\forall m\ge 2$, we have $g_m\le g_m^{\prime }\le g_{m+1}.$

Proof. 

• For the first inequality, let us consider the optimal strategy $S=(s_1,...,s_m)$ for ${\mathcal{P}}_m$, where $s_k$ is Alice’s strategy at round k (i.e., a function that outputs $y_k$ when given Alice’s knowledge at round k). Alice’s cheating probability for ${\mathcal{P}}_m$ is $g_m(S)$. Consider the following strategy $S^{\prime }:=(s_1,...,s_{m-1},s_m^{\prime })$ for ${\mathcal{P}}_m^{\prime }$, where $s_m^{\prime }(d,x_1,...,x_{m-2},x_m):=x_m·s_m(d,x_1,...,x_{m-2})$. $S^{\prime }$ allows for winning on ${\mathcal{P}}_m^{\prime }$ at least as efficiently as S on ${\mathcal{P}}_m$ because $S^{\prime }$ wins whenever S does. Indeed, suppose that S is a winning strategy for a given $(d,x_1,...,x_{m-1})$. This means that ${\mathcal{C}}_m(S,d,x_1,...,x_{m-1})$ is satisfied or equivalently:

  $$\begin{array}{c}\hfill s_m(d,x_1,...,x_{m-2})=y_{m-1}-x_{m-1}\left(y_{m-2}-...\dots -x_2(y_1-d·x_1)...\right).\end{array}$$

  (12)
  Then, since $s_m^{\prime }(d,x_1,...,x_{m-2},x_m)=x_m·s_m(d,x_1,...,x_{m-2})$, we get

  $$\begin{array}{c}\hfill s_m^{\prime }(d,x_1,...,x_{m-2},x_m)=x_m\left(y_{m-1}-x_{m-1}\left(y_{m-2}-...\dots -x_2(y_1-d·x_1)...\right)\right),\end{array}$$

  (13)

  which implies ${\mathcal{C}}_m^{\prime }(S^{\prime },d,x_1,...,x_m)$, for any $x_m$. From there, we immediately get

  $$\begin{array}{c}\hfill g_m=g_m(S)\le g_m^{\prime }(S^{\prime })\le g_m^{\prime }.\end{array}$$

  (14)
• For the other inequality, we fix an optimal strategy $S^{\prime }=(s_1,...,s_m)$ for ${\mathcal{P}}_m^{\prime }$. We consider the following strategy $S:=(s_1,...,s_m,\overline{0})$ for ${\mathcal{P}}_{m+1}$, where $\overline{0}$ is the function that always outputs 0, no matter the inputs. This means that, when performing S, we always have $y_{m+1}=0$. S is at least as good to win ${\mathcal{P}}_{m+1}$ as $S^{\prime }$ is to win ${\mathcal{P}}_m^{\prime }$. Indeed, if for a tuple $(d,x_1,...,x_m)$, $S^{\prime }$ wins on ${\mathcal{P}}_m^{\prime }$, then ${\mathcal{C}}^{\prime }(S^{\prime },d,x_1,...,x_m)$ holds or equivalently

  $$\begin{array}{c}\hfill y_m=x_m\left(y_{m-1}-x_{m-1}\left(y_{m-2}-x_{m-2}\left(...\dots -x_2(y_1-d·x_1)...\right)\right)\right).\end{array}$$

  (15)
  From there, we immediately have

  $$\begin{array}{c}\hfill y_{m+1}=0=y_m-x_m\left(y_{m-1}-x_{m-1}\left(y_{m-2}-x_{m-2}\left(...\dots -x_2(y_1-d·x_1)...\right)\right)\right),\end{array}$$

  (16)

  which implies ${\mathcal{C}}_{m+1}(S,d,x_1,...,x_m)$. From there, we immediately get

  $$\begin{array}{c}\hfill g_m^{\prime }=g_m^{\prime }(S^{\prime })\le g_{m+1}(S)\le g_{m+1}.\end{array}$$

  (17)

☐

The above lemma shows in particular how to transform a strategy for ${\mathcal{P}}_m^{\prime }$ into a strategy for ${\mathcal{P}}_{m+1}$ with at least as good cheating probability. This means that we can study ${\mathcal{P}}_m^{\prime }$ instead of ${\mathcal{P}}_{m+1}$. The first inequality shows that we do not lose much doing so.

The above equations can be hard to follow because of the alternating − signs. In order to simplify calculations, each $y_i$ will be mapped to ${\tilde{y}}_i:={(-1)}^{i+1}{y}_i$. We will mostly use ${\tilde{y}}_i$ from now on instead of $y_i$. With this notation, Alice’s victory condition ${\mathcal{C}}_m^{\prime }(S^{\prime },d,x_1,...,x_m)$ for the protocol becomes:

$$\begin{array}{c}\hfill \sum _{i=1}^m\left(\widetilde{y_i}\prod _{j=i+1}^m{x}_j\right)=d\prod _{j=1}^m{x}_j.\end{array}$$

(18)

In the description of the protocol, when we say that Alice outputs ${\tilde{y}}_i=v$ for any v, then this means that Alice outputs $y_i={(-1)}^{i+1}v$.

In the next section, we present a cheating strategy for protocol ${\mathcal{P}}_m^{\prime }$.

3.2. Description of the Attack

In the previous section, we transformed protocol $\mathcal{P}$ into a slightly modified protocol ${\mathcal{P}}^{\prime }$, which has extra symmetries and for which it will be simpler to construct a recursive cheating strategy. In this section, we describe this strategy for ${\mathcal{P}}^{\prime }$.

More precisely, we define recursively a strategy with a step of three rounds. The idea is that ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$ will use the two first rounds to play a ${\mathsf{CHSH}}_{\mathsf{Q}}$ game and will use the third round as a waiting in order for both players to know whether they won the game or not.

To initialize, we consider the following strategy for ${\mathcal{P}}_3^{\prime }$:

• ${\mathcal{A}}_1$ always outputs ${\tilde{y}}_1=0$.
• ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$ perform the optimal strategy for the ${\mathsf{CHSH}}_{\mathsf{Q}}$ game with inputs $x_1$ and $x_2$. Let a and b be their respective outputs.
• ${\mathcal{A}}_2$ outputs ${\tilde{y}}_2=d\times a$ for round 2 and ${\mathcal{A}}_1$ outputs ${\tilde{y}}_3=x_3\times d\times b$ for round 3. Recall that this means Alice outputs $y_2=-(d\times a)$ and $y_3=x_3\times d\times b$.

With this strategy, ${\mathcal{C}}_3^{\prime }$ becomes $x_3\times d\times (a+b-x_1\times x_2)=0$. Alice wins if $x_3=0$, if $d=0$, or if $a+b=x_1\times x_2$. These events are independent, which gives $g_3^{\prime }\ge 1-\frac{1}{2}(1-\frac{1}{Q})(1-\omega ({\mathsf{CHSH}}_Q))$.

We now describe a strategy for $k+3$ rounds using a strategy for k rounds. We fix a cheating strategy $S_k^{\prime }$ for Alice for ${\mathcal{P}}_k^{\prime }$ and we present a cheating strategy $S_{k+3}^{\prime }$ for ${\mathcal{P}}_{k+3}^{\prime }$.

Recursive Description of a cheating strategy $S_{k+3}^{\prime }$ given $S_k^{\prime }$

• Rounds 1 to k: Alice performs the strategy $S_k^{\prime }$ to get outputs ${\tilde{y}}_1,...,{\tilde{y}}_k$.
• Round $k+1$: Alice always outputs ${\tilde{y}}_{k+1}=0$.
• Rounds $k+2$ and $k+3$: From round $k+2$, ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$ both know $d,x_1,...,x_k$. Let

  $$\eta :=d\prod _{j=1}^k{x}_j-\sum _{i=1}^k(\widetilde{y_i}\prod _{j=i+1}^k{x}_j).$$

  ${\mathcal{A}}_{(k+2)\mathrm{mod}2}$ and ${\mathcal{A}}_{(k+3)\mathrm{mod}2}$ perform the optimal strategy for ${\mathsf{CHSH}}_{\mathsf{Q}}$ on respective inputs $x_{k+2}$ and $x_{k+1}$ to get respective outputs a and b. Their outputs of the protocol are, respectively, ${\tilde{y}}_{k+2}=\eta ·a$ and ${\tilde{y}}_{k+3}=\eta ·b·x_{k+3}$. Notice that, if $\eta =0$, which will correspond to the strategy $S_k^{\prime }$ succeeding to achieve ${\mathcal{C}}_k^{\prime }$, and Alice outputs ${\tilde{y}}_{k+2},{\tilde{y}}_{k+3}=0$ independently of a and b.

In the next section, we will prove the cheating probability achieved by this strategy, which will imply our main theorem.

3.3. Analysis

Lemma 3.

$\forall k\ge 2$, $g_k^{\prime }$ satisfies:

$$1-g_{k+3}^{\prime }(S_{k+3}^{\prime })\le (1-{\displaystyle \frac{1}{Q}})\left(1-\omega ({\mathsf{CHSH}}_{\mathsf{Q}})\right)(1-g_k^{\prime }(S_k^{\prime })).$$

Proof. 

We consider ${\mathcal{P}}_{k+3}^{\prime }$. Alice’s winning condition ${\mathcal{C}}_{k+3}^{\prime }$ is:

$$\begin{array}{c}\hfill \sum _{i=1}^{k+3}\left(\widetilde{y_i}\prod _{j=i+1}^{k+3}{x}_j\right)=d\prod _{j=1}^{k+3}{x}_j,\end{array}$$

(19)

or by taking apart the last three terms:

$$\begin{array}{cc}& {\tilde{y}}_{k+3}\hfill \\ +\hfill & x_{k+3}·{\tilde{y}}_{k+2}\hfill \\ +\hfill & x_{k+3}·x_{k+2}·{\tilde{y}}_{k+1}\hfill \\ +\hfill & x_{k+3}·x_{k+2}·x_{k+1}·{\displaystyle \sum _{i=1}^k}\left(\widetilde{y_i}{\displaystyle \prod _{j=i+1}^k}{x}_j\right)\hfill \\ =\hfill & x_{k+3}·x_{k+2}·x_{k+1}·d{\displaystyle \prod _{j=1}^k}{x}_j.\hfill \end{array}$$

(20)

Recall that $\eta :=d{\displaystyle \prod _{j=1}^k}{x}_j-{\displaystyle \sum _{i=1}^k}(\widetilde{y_i}{\displaystyle \prod _{j=i+1}^k}{x}_j)\in {\mathbb{F}}_q$. Using $\eta$, we get:

$$\begin{array}{c}\hfill {\mathcal{C}}_{k+3}^{\prime }\iff {\tilde{y}}_{k+3}+x_{k+3}·{\tilde{y}}_{k+2}+x_{k+3}·x_{k+2}·{\tilde{y}}_{k+1}=x_{k+3}·x_{k+2}·x_{k+1}·\eta .\end{array}$$

(21)

Recall from our protocol description that ${\tilde{y}}_{k+2}=\eta \times a$ and ${\tilde{y}}_{k+3}=\eta \times b\times x_{k+3}$, where a and b are the Alice’s outputs of the ${\mathsf{CHSH}}_{\mathsf{Q}}$ game. From there, we have

$$\begin{array}{ccc}{\mathcal{C}}_{k+3}^{\prime }\hfill & \iff \hfill & {\tilde{y}}_{k+3}+x_{k+3}·{\tilde{y}}_{k+2}+x_{k+3}·x_{k+2}·{\tilde{y}}_{k+1}=x_{k+3}·x_{k+2}·x_{k+1}·\eta \hfill \\ & \iff \hfill & x_{k+3}·b·\eta +x_{k+3}·a·\eta +0=x_{k+3}·x_{k+2}·x_{k+1}·\eta \hfill \\ & \iff \hfill & \eta ·x_{k+3}·(a+b-x_{k+1}·x_{k+2})=0\hfill \\ & \iff \hfill & (x_{k+3}=0)\vee (\eta =0)\vee (a+b=x_{k+1}·x_{k+2}).\hfill \end{array}$$

(22)

These three events $(x_{k+3}=0)$; $(\eta =0)$; $(a+b=x_{k+1}\times x_{k+2})$ are independent as:

• $(x_{k+3}=0)$ only depends on $x_{k+3}$, and happens with probability $\frac{1}{Q}$.
• $(\eta =0)$ only depends on $d,x_1,...,x_k$, and happens with probability $g_k^{\prime }(S_k^{\prime })$.
• $(a+b=x_{k+1}\times x_{k+2})$ only depends on $x_{k+1}$ and $x_{k+2}$ (${\mathcal{A}}_1$ and ${\mathcal{A}}_2$ optimally play the ${\mathsf{CHSH}}_{\mathsf{Q}}$ game on inputs $x_{k+1},x_{k+2}$, ignoring any unnecessary information). This happens therefore with probability $\omega ({\mathsf{CHSH}}_Q)$.

Thus, this particular strategy gives

$$\begin{array}{c}\hfill g_{k+3}^{\prime }(S_{k+3}^{\prime })=Pr\left[{\mathcal{C}}_{k+3}^{\prime }\right]=1-(1-g_k^{\prime }(S_k^{\prime }))(1-\frac{1}{Q})(1-\omega ({\mathsf{CHSH}}_{\mathsf{Q}}))\end{array}$$

(23)

or equivalently

$$\begin{array}{c}\hfill 1-g_{k+3}^{\prime }(S_{k+3}^{\prime })\le (1-{\displaystyle \frac{1}{Q}})\left(1-\omega ({\mathsf{CHSH}}_{\mathsf{Q}})\right)(1-g_k^{\prime }(S_k^{\prime })).\end{array}$$

(24)

☐

We can now prove our main theorem, restated below

Theorem 2.

$\forall m\ge 3$, we have:

$$g_m\ge 1-{\displaystyle \frac{1}{2}}{\left(\left(1-{\displaystyle \frac{1}{Q}}\right)\left(1-\omega ({\mathsf{CHSH}}_{\mathsf{Q}})\right)\right)}^{\lfloor \frac{m-1}{3}\rfloor }.$$

Proof. 

By iterating the above lemma, we obtain

$$\begin{array}{c}\hfill 1-g_{3k}^{\prime }(S_{3k}^{\prime })\le {\left(\left(1-{\displaystyle \frac{1}{Q}}\right)\left(1-\omega ({\mathsf{CHSH}}_{\mathsf{Q}})\right)\right)}^{k-1}(1-g_3^{\prime }(S_3^{\prime })).\end{array}$$

(25)

Combining this with the initialization step $g_3^{\prime }(S_3)\ge 1-\frac{1}{2}(1-\frac{1}{Q})(1-\omega ({\mathsf{CHSH}}_Q))$ gives

$$\begin{array}{c}\hfill g_{3k}^{\prime }\ge g_{3k}^{\prime }(S_{3k})\ge 1-{\displaystyle \frac{1}{2}}{\left(\left(1-{\displaystyle \frac{1}{Q}}\right)\left(1-\omega ({\mathsf{CHSH}}_{\mathsf{Q}})\right)\right)}^k.\end{array}$$

(26)

Using the symmetrization lemma (Lemma 2), we immediately get

$$\begin{array}{c}\hfill g_{3k+1}\ge g_{3k}^{\prime }\ge 1-{\displaystyle \frac{1}{2}}{\left(\left(1-{\displaystyle \frac{1}{Q}}\right)\left(1-\omega ({\mathsf{CHSH}}_{\mathsf{Q}})\right)\right)}^k.\end{array}$$

(27)

If m can be written $m=3k+1$ for some k, we have

$$\begin{array}{c}\hfill g_m\ge 1-{\displaystyle \frac{1}{2}}{\left(\left(1-{\displaystyle \frac{1}{Q}}\right)\left(1-\omega ({\mathsf{CHSH}}_{\mathsf{Q}})\right)\right)}^{\frac{m-1}{3}}.\end{array}$$

(28)

Since $g_m$ is an increasing function, we have for all $m\ge 3$:

$$\begin{array}{c}\hfill g_m\ge 1-{\displaystyle \frac{1}{2}}{\left(\left(1-{\displaystyle \frac{1}{Q}}\right)\left(1-\omega ({\mathsf{CHSH}}_{\mathsf{Q}})\right)\right)}^{\lfloor \frac{m-1}{3}\rfloor }.\end{array}$$

(29)

☐

4. Generalization

In the previous section, we assumed that ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$ can communicate very efficiently, meaning that the propagation time $\rho$ is two rounds. With such a propagation time, relativistic constraints ensure that at a given round k, Alice cannot use any information concerning round $k-1$. However, we supposed that she knows everything about the rounds $k-2$ and before. Notice that she obviously has access to the information of round $k-2$ because it occurs at the same place than round k.

What happens if ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$ cannot reliably share their knowledge so fast? In this case, the propagation time $\rho$ will be larger, and at any round k, Alice knows everything about rounds $1,2,...,k-\rho$ with. We use an even propagation time without loss of generality since computations rotate between two places, and Alice always knows what happened at rounds $k-2$, $k-4$, etc. In this situation, we will show that ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$ cannot just play the ${\mathsf{CHSH}}_{\mathsf{Q}}$ game. They will have to play the ${\mathsf{CHSH}}_{\mathsf{Q}}^{\gamma }$ game, for some $\gamma$ that will be specified later.

Another restriction that we do on the cheating players is that ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$ may need some time to determine the bit d they want to decommit to. We call $k_0$ the round starting from which both ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$ know if they try to reveal $d=0$ or $d=1$.

In this more practical setting, we propose the following recursive variant of our attack, for $k>k_0$, for any propagation time $\rho \ge 2$.

Recursive Description of a Cheating Strategy $S_{k+\rho +1}$ given $S_k$

• Rounds 1 to k: Alice performs the strategy $S_k$ to get outputs ${\tilde{y}}_1,...,{\tilde{y}}_k$.
• Rounds $k+1$ to $k+\rho -1$: Alice outputs ${\tilde{y}}_{k+1},...,{\tilde{y}}_{k+\rho -1}=0$.
• Rounds $k+\rho$ and $k+\rho +1$: From round $k+\rho$, ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$ both know $d,x_1,...,x_k$. Let

  $$\eta :=d\prod _{j=1}^k{x}_j-\sum _{i=1}^k(\widetilde{y_i}\prod _{j=i+1}^k{x}_j).$$

  ${\mathcal{A}}_1$ also knows $X={\prod }_{j\mathrm{odd}:k+1\le j\le k+\rho }{x}_j$ and ${\mathcal{A}}_2$ knows $Y={\prod }_{j\mathrm{even}:k+1\le j\le k+\rho }{x}_j$. ${\mathcal{A}}_{(k+\rho )\mathrm{mod}2}$ and ${\mathcal{A}}_{(k+\rho +1)\mathrm{mod}2}$ perform the optimal strategy for ${\mathsf{CHSH}}_{\mathsf{Q}}^{\gamma }$ with $\gamma :=1-{(1-\frac{1}{Q})}^{\frac{\rho }{2}}$ on respective inputs X and Y to get respective outputs a and b. Their outputs of the protocol are, respectively, ${\tilde{y}}_{k+\rho }=\eta ·a$ and ${\tilde{y}}_{k+\rho +1}=\eta ·b·x_{k+\rho +1}$.

Lemma 4.

$\forall k\ge k_0$, we have

$$g_{k+\rho +1}^{\prime }\ge \left(1-{\displaystyle \frac{1}{Q}}\right)\left(1-\omega ({\mathsf{CHSH}}_{\mathsf{Q}})\right)g_k^{\prime }+1-\left(1-{\displaystyle \frac{1}{Q}}\right)\left(1-\omega ({\mathsf{CHSH}}_{\mathsf{Q}})\right).$$

Proof. 

This demonstration will be similar to Lemma 3. We consider the cheating strategy described above. Alice’s winning condition ${\mathcal{C}}_{k+\rho +1}^{\prime }$ is:

$$\begin{array}{c}\hfill \sum _{i=1}^{k+\rho +1}\left(\widetilde{y_i}\prod _{j=i+1}^{k+\rho +1}{x}_j\right)=d\prod _{j=1}^{k+\rho +1}{x}_j,\end{array}$$

(30)

or by separating the last $\rho +1$ terms:

$$\begin{array}{cc}& {\tilde{y}}_{k+\rho +1}\hfill \\ +\hfill & x_{k+\rho +1}·{\tilde{y}}_{k+\rho }\hfill \\ +\hfill & 0\hfill \\ ⋮\hfill \\ +\hfill & 0\hfill \\ +\hfill & \left({\displaystyle \prod _{j=k+1}^{k+\rho +1}}{x}_j\right){\displaystyle \sum _{i=1}^k}\left(\widetilde{y_i}{\displaystyle \prod _{j=i+1}^k}{x}_j\right)\hfill \\ =\hfill & \left({\displaystyle \prod _{j=k+1}^{k+\rho +1}}{x}_j\right)d{\displaystyle \prod _{j=1}^k}{x}_j,\hfill \end{array}$$

(31)

where d is the bit Alice wants to reveal.

Recall that $\eta :=d{\displaystyle \prod _{j=1}^k}{x}_j-{\displaystyle \sum _{i=1}^k}(\widetilde{y_i}{\displaystyle \prod _{j=i+1}^k}{x}_j)$, which allows to simplify ${\mathcal{C}}_{k+\rho +1}^{\prime }$ as follows:

$$\begin{array}{cc}\hfill {\mathcal{C}}_{k+\rho +1}^{\prime }& \iff {\tilde{y}}_{k+\rho +1}+x_{k+\rho +1}·{\tilde{y}}_{k+\rho }=\left(\prod _{j=k+1}^{k+\rho +1}{x}_j\right)·\eta ,\hfill \end{array}$$

(32)

$$\begin{array}{c}\iff {\tilde{y}}_{k+\rho +1}+x_{k+\rho +1}·{\tilde{y}}_{k+\rho }=X·Y·\eta .\hfill \end{array}$$

(33)

In her cheating strategy, Alice answers ${\tilde{y}}_{k+\rho }=a\times \eta$ and ${\tilde{y}}_{k+\rho +1}=x_{k+\rho +1}\times b\times \eta$, where a and b are Alices’ answers when playing the ${{\mathsf{CHSH}}_{\mathsf{Q}}}^{\gamma }$ game, on inputs X and Y. Thus,

$$\begin{array}{c}\hfill {\mathcal{C}}_{k+\rho +1}^{\prime }\iff (x_{k+\rho +1}=0)\vee (\eta =0)\vee (a+b=XY).\end{array}$$

(34)

The three events $(x_{k+\rho +1}=0)$; $(\eta =0)$; $(a+b=XY)$ are independent. The first one occurs with probability $\frac{1}{Q}$, the second one with probability $g_k^{\prime }$. For the third one, notice that X is a product of $\frac{\rho }{2}$ uniformly random number in ${\mathbb{F}}_Q$. Therefore, we have $Pr[X=0]=1-{(1-\frac{1}{Q})}^{\frac{\rho }{2}}=\gamma$ and for any $z\in {\mathbb{F}}_Q^{\ast }$, $Pr[X=z]=\frac{1-\gamma }{Q-1}$. Y satisfies the same probability distribution. Therefore, $Pr[a+b=XY]$ is exactly the probability of winning the ${{\mathsf{CHSH}}_{\mathsf{Q}}}^{\gamma }$ game using its optimal strategy.

This gives:

$$\begin{array}{c}\hfill g_{k+\rho +1}^{\prime }\ge 1-\left(1-{\displaystyle \frac{1}{Q}}\right)(1-g_k^{\prime })\left(1-\omega ({{\mathsf{CHSH}}_{\mathsf{Q}}}^{\gamma })\right).\end{array}$$

(35)

Then, using Lemma 1:

$$\begin{array}{c}\hfill g_{k+\rho +1}^{\prime }\ge 1-\left(1-{\displaystyle \frac{1}{Q}}\right)(1-g_k^{\prime })\left(1-\omega ({\mathsf{CHSH}}_{\mathsf{Q}})\right),\end{array}$$

(36)

i.e.,

$$\begin{array}{c}\hfill g_{k+\rho +1}^{\prime }\ge \left(1-{\displaystyle \frac{1}{Q}}\right)\left(1-\omega ({\mathsf{CHSH}}_{\mathsf{Q}})\right)g_k^{\prime }+1-\left(1-{\displaystyle \frac{1}{Q}}\right)\left(1-\omega ({\mathsf{CHSH}}_{\mathsf{Q}})\right).\end{array}$$

(37)

☐

Theorem 3.

For any $k_0\ge 1$ and $\rho \ge 2$, for any $m\ge k_0+\rho +1$, we have

$$g_m\ge 1-{\displaystyle \frac{1}{2}}{\left((1-{\displaystyle \frac{1}{Q}})\left(1-\omega ({\mathsf{CHSH}}_{\mathsf{Q}})\right)\right)}^{\frac{m-k_0-1}{\rho +1}}.$$

Proof. 

We use the recursive inequality from Lemma 4, and the trivial initialization $g_{k_0}^{\prime }\ge \frac{1}{2}$. This gives us $\forall k\ge k_0$, and we have

$$\begin{array}{c}\hfill g_{k_0+k(\rho +1)}^{\prime }\ge 1-{\displaystyle \frac{1}{2}}{\left((1-{\displaystyle \frac{1}{Q}})\left(1-\omega ({\mathsf{CHSH}}_{\mathsf{Q}})\right)\right)}^k,\end{array}$$

(38)

and, by using Lemma 2,

$$\begin{array}{c}\hfill g_{k_0+k(\rho +1)+1}\ge 1-{\displaystyle \frac{1}{2}}{\left((1-{\displaystyle \frac{1}{Q}})\left(1-\omega ({\mathsf{CHSH}}_{\mathsf{Q}})\right)\right)}^k.\end{array}$$

(39)

If m can be written $m=k_0+k(\rho +1)+1$, we have $k=\frac{m-k_0-1}{\rho +1}$ and

$$\begin{array}{c}\hfill g_m\ge 1-{\displaystyle \frac{1}{2}}{\left((1-{\displaystyle \frac{1}{Q}})\left(1-\omega ({\mathsf{CHSH}}_{\mathsf{Q}})\right)\right)}^{\frac{m-k_0-1}{\rho +1}}.\end{array}$$

(40)

In order, to conclude, notice that $g_m$ is an increasing function in m. We can therefore conclude that

$$\begin{array}{c}\hfill g_m\ge 1-{\displaystyle \frac{1}{2}}{\left((1-{\displaystyle \frac{1}{Q}})\left(1-\omega ({\mathsf{CHSH}}_{\mathsf{Q}})\right)\right)}^{\lfloor \frac{m-k_0-1}{\rho +1}\rfloor }.\end{array}$$

(41)

☐

5. Conclusions

In this paper, we presented a cheating strategy for the ${\mathbb{F}}_Q$ relativistic bit commitment protocol, which has recently become the most widely studied relativistic bit commitment protocol. We show that the security analysis presented in [21,22] is essentially tight, at least when Q is an even power of a prime. Regarding the non-locality approach of [21], this means that even recent improvements on non-locality bounds presented in [26] cannot be used to substantially improve the security analysis of the protocol. An obvious open question is to extend the above results to all values of Q.

We also extended this result in a more realistic scenario. This shows that our cheating strategy can be easily implemented.

The finality of the relativistic model is to be secure against quantum adversaries so an important open question is to show the security of this protocol (or another multi-round relativistic bit commitment) against quantum adversaries. Both the composability approach of [22] and the non-locality approach of [21] fail in the quantum setting. One possible approach would be to find designs other than the ${\mathbb{F}}_Q$ protocol. The cheating strategy from this paper can be easily adapted to other similar constructions and can be seen as a guideline of what to avoid in order to have a secure protocol.