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

Iordanis Kerenidis

Srijita Kundu
email: srijita@cmi.ac.in.

Jamie Sikora
email: jamie.sikora@liafa.univ-paris-diderot.fr.

Optimal bounds for parity-oblivious random access codes

Random access coding is an information task that has been extensively studied and found many applications in quantum information. In this scenario, Alice receives an n-bit string x, and wishes to encode x into a quantum state ρ x , such that Bob, when receiving the state ρ x , can choose any bit i ∈ [n] and recover the input bit x i with high probability. Here we study a variant called parity-oblivious random access codes, where we impose the cryptographic property that Bob cannot infer any information about the parity of any subset of bits of the input, apart from the single bits x i .

.

Introduction

Quantum information theory studies how information is encoded in quantum mechanical systems and how it can be transmitted through quantum channels. A main question is whether quantum information is more powerful than classical information. A celebrated result by Holevo [START_REF] Holevo | Some estimates of the information transmitted by quantum communication channels[END_REF], shows that quantum information cannot be used to compress classical information. In high level, in order to transmit n uniformly random classical bits, one needs to transmit no less than n quantum bits. This might imply that quantum information is no more powerful than classical information. This however is wrong in many situations. In the model of communication complexity, one can show that transmitting quantum information may result in exponential savings on the communication needed to solve specific problems ([Raz99, BCWdW01, BJK04, GKK + 08, RK11]).

One specific information task that has been extensively studied in quantum information is the notion of random access codes (RACs) [START_REF] Nayak | Optimal lower bounds for quantum automata and random access codes[END_REF][START_REF] Ambainis | Dense quantum coding and a lower bound for 1-way quantum automata[END_REF][START_REF] Ambainis | Dense quantum coding and quantum finite automata[END_REF]. In this scenario, Alice receives an n-bit string x, drawn from the uniform distribution, and wishes to encode x into a quantum state ρ x , such that Bob, when receiving the state ρ x , can choose any bit i ∈ [n] and recover the input bit x i with high probability by performing some general quantum operation on ρ x .

RACs have been used in various situations in quantum information and computation, including in communication complexity, non-locality, extractors and device-independent cryptography [BARdW08, INRY07, PZ10, DV10, LPY + 12]. Even though this task seems easier than transmitting the entire input string x, it is known that the length of quantum encodings must be at least Ω(n) [START_REF] Nayak | Optimal lower bounds for quantum automata and random access codes[END_REF]. In fact, the length of classical encodings can be within a logarithmic additive factor of the quantum encodings [START_REF] Ambainis | Dense quantum coding and a lower bound for 1-way quantum automata[END_REF].

On the other hand, a well-known example shows the advantages of quantum RACs by using a single qubit to encode two uniformly random classical bits. In this case, the success of correctly decoding either bit is cos 2 (π/8) [START_REF] Bennett | Quantum cryptography, or unforgeable subway tokens[END_REF][START_REF] Ambainis | Dense quantum coding and a lower bound for 1-way quantum automata[END_REF] while the optimal classical encoding can achieve an average success probability of 3/4. An advantage can also be proven for the case of encoding three classical bits into one qubit as shown by Chuang (see [START_REF] Ambainis | Dense quantum coding and quantum finite automata[END_REF] for details), but not for n ≥ 4 [HIN + 06].

Nevertheless, a question remained of whether there are variants of RACs, for which we can have an asymptotically significant advantage in the quantum case. We show that this is indeed the case for the so-called parity-oblivious RACs (denoted here as PO-RACs). These are the usual RACs with the extra cryptographic property that the receiver cannot infer any information about the parity of any subset of bits of the input, apart from the single bits.

This cryptographic property means, in particular, that once some information about a bit is learned, then no other information can be extracted about any of the other bits. Such a notion has applications in various areas of cryptography. For example, this is a requirement for a class of classical or quantum protocols known as symmetric-private information retrieval schemes (PIR) [START_REF] Gertner | Protecting data privacy in private information retrieval schemes[END_REF][START_REF] Kerenidis | Quantum symmetrically-private information retrieval[END_REF] where one or more servers have a database x, a user chooses an index i and at the end, the user learns x i but no other bit of x, and i remains hidden. A parity-oblivious RAC satisfies the security conditions of a PIR scheme since the index i remains hidden (the RAC is non-interactive) and the user cannot learn more than one bit of the database.

Random access codes that are parity-oblivious have been considered before. For example, the previously mentioned RACs for encoding two or three classical bits in one qubit have this property. It is not hard to check that for any subset of the inputs of size 2 or greater, Bob's reduced density matrix is exactly the same for the cases where the parity is 0 or 1. In other words, Bob has no information about the parity. These encodings violate a non-contextuality inequality developed by Spekkens, Buzacott, Keehn, Toner, and Pryde [SBK + 09]. This inequality is discussed further in Subsection 1.3.

Our results

We say that a random access code where every bit can be decoded with success probability at least 1 2 (1 + α) has bias α. The goal is to find quantum parity-oblivious random access codes with optimal bias.

In this paper, we provide optimal bounds on quantum parity-oblivious random access codes and show that they perform asymptotically better than the optimal classical version.

Theorem 1 (Optimal quantum parity-oblivious random access codes). For any n ∈ N, a quantum parityoblivious random access code of n uniformly random classical bits has bias at most 1 √ n . Moreover, this bound can be achieved using ⌊n/2⌋ qubits and 1 classical bit. This is in contrast to the classical setting where the optimal average-case bias is provably 1/n [SBK + 09]. We comment further on classical encodings in Subsection 1.2.

The main idea of the proof of the upper bound is that quantum encodings can be studied through their relation to non-local games. Such equivalences between encodings and non-local games were previously noted in [START_REF] Oppenheim | The uncertainty principle determines the non-locality of quantum mechanics[END_REF][START_REF] Chailloux | Strong connections between quantum encodings, non-locality and quantum cryptography[END_REF]. A non-local game is a game between two non-communicating parties, who receive some inputs and must produce outputs that satisfy some known predicate. A well-known example is the CHSH game, where the two parties must output bits a and b, whose parity is equal to the logical AND of their inputs x and y. An important quantity of such games is the optimal success probability when the two parties are allowed to share an arbitrary entangled state in the beginning of the protocol. In [START_REF] Chailloux | Strong connections between quantum encodings, non-locality and quantum cryptography[END_REF], it was shown that certain variants of the CHSH game are equivalent to some quantum encodings and their respective success probabilities are equal.

In order to show an upper bound on the bias of quantum PO-RACs, we first define a weaker variant where only the parities of even-size subsets are hidden and the bias is averaged, i.e., not worst-case. An upper bound on the bias of these encodings would imply an upper bound on the bias of general PO-RACs (since we are relaxing both properties defining PO-RACs).

Then, we study a natural non-local game which we call the INDEX game and show that even-parityoblivious encodings with average-case bias are equivalent to the INDEX game. In other words, any INDEX game strategy with bias α yields an even-parity-oblivious encoding with average-case bias α and vice versa. In the INDEX n game (parameterized by n here), Alice receives an n-bit string s, Bob receives an index t ∈ [n], and Alice and Bob are supposed to output bits a and b such that a ⊕ b = s t .

Theorem 2 (Equivalence). For any n ∈ N, there exists a quantum even-parity-oblivious encoding of n uniformly random classical bits with average-case bias α if and only if there exists a quantum INDEX n strategy with bias α.

Last, noting that the INDEX game is an XOR game, i.e., the winning condition depends on the XOR of Alice and Bob's one-bit answers, we use a tight semidefinite programming characterization [START_REF] Cleve | Perfect parallel repetition theorem for quantum XOR proof systems[END_REF] and provide the exact optimal quantum bias.

Theorem 3 (Optimal quantum INDEX game bias). For any n ∈ N, the optimal quantum bias of an

INDEX n strategy is 1/ √ n.
Since the worst-case bias of a quantum PO-RAC is obviously upper bounded by the optimal averagecase bias of a quantum encoding hiding only the even parities, Theorems 2 and 3 show that every PO-RAC of n uniformly random classical bits has bias at most 1/ √ n.

To prove this upper bound is tight, we give an explicit construction of a PO-RAC of n bits with bias 1/ √ n that uses ⌊n/2⌋ qubits and 1 classical bit. This encoding is based on the notion of hyperbits [START_REF] Pawłowski | From qubits to hyperbits[END_REF] and a proof of Tsirelson's theorem [START_REF] Tsirelson | Quantum analogues of the Bell inequalities: The case of two spatially separated domains[END_REF].

We remark that parity-oblivious and even-parity-oblivious encodings both share the same worst-case and average-case bias of 1/ √ n. However, the same is not true if we consider odd-parity-oblivious encodings where the parities are hidden for only odd-size subsets (greater or equal to 3). Consider encoding a six-bit string (x 1 , . . . , x 6 ) where the first three bits are encoded using Chuang's PO-RAC and similarly for the last three bits. It is a straightforward exercise to verify that this is odd-parity-oblivious and that any bit can be decoded with bias 1/ √ 3 > 1/ √ 6. We leave finding the optimal bounds for odd-parity-oblivious encodings an open problem.

Remarks on parity-oblivious classical encodings

We can define parity-oblivious classical encodings similar to the quantum case (see Section 2 for rigorous definitions). Moreover, the equivalence stated in Theorem 2 holds in the classical case as well (remarked in Section 3). To prove a tight upper bound on the bias of even-parity-oblivious classical encodings, we provide the following theorem.

Theorem 4 (Optimal classical INDEX game bias). For any n ∈ N, the optimal classical bias of an

INDEX n strategy is 2 πn (1 + O(1/n)).
This theorem, together with the classical version of the equivalence shows that classical encodings that are even-parity-oblivious have an optimal average-case bias of 2 πn (1+O(1/n)). Note that, asymptotically, this value is the same as the quantum value, that is, having a bias of O(1/ √ n). However, differences arise when one considers encodings that also hide the odd parities. Consider the following proposition of Spekkens, Buzacott, Keehn, Toner, and Pryde.

Proposition 1 (Optimal parity-oblivious classical encodings [SBK + 09]). For any n ∈ N, a parity-oblivious classical encoding of n uniformly random classical bits has average-case bias at most 1/n. Moreover, this bound can be achieved using 1 classical bit.

Thus, there is a difference between the optimal average-case biases of parity-oblivious and even-parityoblivious encodings in the classical setting, in contrast to the quantum setting.

Large non-contextuality inequality violations

The basic primitives in an operational theory are preparations and measurements. A hidden variable model is preparation and measurement non-contextual, if whenever two preparations yield the same statistics for all possible measurements then they have an equivalent representation in the model; and whenever two measurements have the same statistics for all preparations then they have an equivalent representation in the model [SBK + 09]. Similar to non-locality, a non-contextuality inequality is any inequality on probability distributions that follows from the assumption that there exists a hidden variable model that is preparation or measurement non-contextual.

Spekkens, Buzacott, Keehn, Toner, and Pryde [SBK + 09] proved the following non-contextuality inequality (or NC inequality, for short).

Proposition 2 (Non-contextuality inequality [SBK + 09]). In any operational theory that admits a preparation non-contextual hidden variable model, the average-case bias for any parity-oblivious encoding is at most 1/n. Then, they showed that quantum mechanics violates this NC inequality for n ∈ {2, 3}, by noting the previously mentioned parity-oblivious quantum encodings of two and three classical bits into one qubit with respective average-case biases of 1 √ 2 and 1 √ 3 . It was left as an open question whether quantum mechanics violates this NC inequality for n ≥ 4.

Through our analysis, we have shown that the optimal average-case bias for quantum parity-oblivious encodings is 1/ √ n, thus resolving their main open question. This provides a family of NC inequality violations that grow with the input size n. Note, that if there exists a game for which the winning probability of any classical strategy cannot deviate from 1/2 by more than δ 1 and, moreover, there is a quantum strategy with winning probability at least 1/2 + δ 2 , then we can obtain a violation of order δ 2 /δ 1 (see [START_REF] Buhrman | Near-optimal and explicit Bell inequality violations[END_REF] for details). Hence, to quantify the violation of this NC inequality, we consider the ratio of the optimal average-case bias of quantum parity-oblivious encodings and that of any operational theory admitting a preparation non-contextual hidden variable model. More precisely, we show an explicit non-contextuality inequality violation of order √ n.

Theorem 5. For any n ∈ N, there exists an explicit non-contextuality inequality that provides a violation of order √ n.

Note that other large non-contextuality inequality violations have been found, see for example the work of Vidick and Wehner [START_REF] Vidick | Does ignorance of the whole imply ignorance of the parts?[END_REF].

Preliminaries and notation

For two matrices X and Y of the same size, we use X, Y to denote the trace inner product Tr(X * Y ).

Next, we provide the definitions of the quantum and classical encodings and of the non-local games we consider.

Quantum and classical encodings and random access codes

Definition 1 (Quantum encodings with worst-case and average-case biases). A quantum encoding of a string x ∈ {0, 1} n is a set of quantum states {ρ x : x ∈ {0, 1} n } along with a decoding procedure i.e., for each i, a two-outcome measurement {{M i 0 , M i 1 } : i ∈ [n]} for learning the individual bits of x. We say the encoding has worst-case bias α if

Pr[correctly decoding x i ] = M i x i , ρ x ≥ 1 2 (1 + α), for all x ∈ {0, 1} n , i ∈ [n].
We say the encoding has average-case bias α if

E x∼µ({0,1} n ) E i∼µ([n]) Pr[correctly decoding x i ] = 1 2 (1 + α),
where µ is the uniform probability distribution.

Definition 2 (Classical encodings with worst-case and average-case biases). A classical encoding of a string x ∈ {0, 1} n is a set of strings {e(x, r) : x ∈ {0, 1} n , r ∈ {0, 1} m } where r corresponds to private randomness; along with a decoding procedure, i.e., for each i, a function f i for learning the individual bits of x.

We say the encoding has worst-case bias α if

Pr[correctly decoding x i ] = Pr[f i (e(x, r)) = x i ] ≥ 1 2 (1 + α), for all x ∈ {0, 1} n , i ∈ [n],
where the probabilities are taken over all the random coins r. We say the encoding has average-case bias α if

E x∼µ({0,1} n ) E i∼µ([n]) Pr[correctly decoding x i ] = E x∼µ({0,1} n ) E i∼µ([n]) Pr[f i (e(x, r)) = x i ] = 1 2 (1 + α),
where µ is the uniform probability distribution.

Note that we can define average-case biases over non-uniform distributions. However, we have only the need for uniform probability distributions in this paper.

In this paper, we are concerned with quantum encodings which enforce certain cryptographic properties. For example, we enforce that the encoding hides some information about the encoded string x. By information being hidden, we mean that there exists no measurement which yields a correct guess with probability greater than that of randomly guessing. In particular, we consider the case for which certain parities of the encoded string are hidden.

Definition 3 (S-parities). For a string x ∈ {0, 1} n and subset S ⊆ [n], we define its S-parity as x S := i∈S x i .

In the definition above, we usually only care about subsets of size 2 or greater, but we have occasion to consider the singleton sets as well.

Definition 4 (Parity-oblivious and even-parity oblivious encodings). We say a quantum encoding is parityoblivious if it has the cryptographic constraint that every S-parity is hidden, that is,

E x∼µ({0,1} n ) Pr[correctly decoding x S ] = 1 2 , for all S ⊆ [n], |S| ≥ 2.
An even-parity-oblivious quantum encoding is a quantum encoding such that every S-parity is hidden when |S| is even.

In this paper, we examine quantum encodings with varying notions of bias and parity-obliviousness. However, we are primarily concerned with bounding the bias of parity-oblivious random access codes, defined below.

Definition 5 (Parity-oblivious random access codes).

A quantum parity-oblivious random access code of n uniformly random classical bits, denoted here as PO-RAC n , with bias α is a parity-oblivious quantum encoding with worst-case bias α.

Note that the above definition includes the most stringent of both properties. However, as the analysis in this paper shows, the optimal bias for PO-RAC n s is equal to the optimal average-case bias for quantum encodings that are even-parity-oblivious. Thus, our definition of PO-RAC n is not too demanding.

Note that the usual treatment of RACs is to analyze the relationships between n, α, and the dimension of the encoding. Here, we are not concerned with the encoding dimension, but rather the ability to achieve parity-obliviousness.

Non-local games

In a non-local game, two non-communicating parties, Alice and Bob, receive some inputs s and t, respectively, and must output a and b, respectively, such that (s, t, a, b) satisfy some specific condition. For example in the CHSH game, the condition is a ⊕ b = s • t. The goal is to find the optimal quantum (classical) success probability of satisfying the condition when Alice and Bob are allowed to share some initial quantum state (shared randomness).

We define the following non-local game.

Definition 6 (INDEX game). The INDEX n game, parameterized by n here, is the following (XOR) game:

• Alice's input: Alice receives a random s from the set S := {0, 1} n .

• Bob's input: Bob receives a random index t from the set T := [n].

• Winning condition: They win if Alice's output bit a and Bob's output bit b satisfy a ⊕ b = s t .

The choice of initial resource state and local measurement operators (that depend on the respective inputs) comprise a strategy. We say that a strategy has bias α if

E s∼µ({0,1} n ) E t∼µ([n]) Pr[Alice's output a and Bob's output b satisfy a ⊕ b = s t ] = 1 2 (1 + α).
The INDEX game turns out to be equivalent to the Retrieval game studied in [START_REF] Oppenheim | The uncertainty principle determines the non-locality of quantum mechanics[END_REF] which is defined similarly except the first bit of Alice's input is always 0 (otherwise the other n -1 bits are chosen independently and uniformly at random). To see the equivalence, notice that in the INDEX game Alice can take her input s ∈ {0, 1} n , define s ′ = m ⊕ s, where m fixes the specific bit to a specific value, play the Retrieval game strategy with input s ′ to generate a ′ , and then output a := a ′ ⊕ m (Bob plays the same strategy). Thus, any strategy for the Retrieval game with bias α yields a strategy for the INDEX game with bias α as well. We further remark that the quantum bias of the Retrieval game is shown to be 1/ √ n in [START_REF] Oppenheim | The uncertainty principle determines the non-locality of quantum mechanics[END_REF] through the use of uncertainty relations. Using this result, and the equivalence to the INDEX game, we have another proof that the quantum bias of the INDEX game is 1/ √ n.

Equivalence of even-parity-oblivious encodings and INDEX n strategies

In this section we prove the equivalence in Theorem 2, reproduced below.

Theorem 2 (Equivalence). For any n ∈ N, there exists a quantum even-parity-oblivious encoding of n uniformly random classical bits with average-case bias α if and only if there exists a quantum INDEX n strategy with bias α.

From encodings to INDEX strategies

Let us fix an even-parity-oblivious encoding {ρ x : x ∈ {0, 1} n } with average-case bias α. Let B be the Hilbert space used for the encoding. Our goal is to construct a strategy for INDEX n with bias α. For each ρ x , we fix a purification |ψ x of ρ x in the space A ⊗ B. For a ∈ {0, 1}, let a be the n-bit string (a, . . . , a) and s be the bit-wise complement of a string s. Define the following state

|Ω s = 1 √ 2 a∈{0,1} |a O |ψ s⊕a AB = 1 √ 2 |0 |ψ s + 1 √ 2 |1 |ψ s ,
where O is a qubit register containing the value of a. We would like to show that if Bob has the register B of the above state, then he has no information about s. Note that his reduced state is σ s =1 2 ρ s + 1 2 ρ s. The first step is to see that Bob has no information about any parity of s (not even of the values of the singleton bits). Fix an arbitrary, non-empty subset S. The reduced state Bob has for s S = b is given by

σ b S :=    ρ b S if |S| even, 1 2 ρ 0 S + 1 2 ρ 1 S if |S| odd,
where ρ b S := 1 2 n-1 s:s S =b ρ s . This shows that if |S| is odd, then σ 0 S = σ 1 S . If |S| is even (and nonzero), we have ρ 0 S = ρ 1 S since the even parities of the encoding {ρ x : x ∈ {0, 1} n } are hidden (when chosen uniformly at random). Hence, we have σ 0 S = σ 1 S . This means that for any nonempty subset S and measurement M , Bob has a maximum probability of 1/2 of successfully guessing s S .

In the following lemma, we prove that if an encoding reveals no information about the parity of any subset, then the encoding reveals no information about the string. This is intuitively an obvious statement that we rigorously prove below.

Lemma 1. If an encoding {σ

s : s ∈ {0, 1} n } satisfies E s∼µ({0,1} n ) Pr[learn s S ] = 1 2 , for every subset S ⊆ [n] \ ∅, then σ s = σ s ′ for all s, s ′ ∈ {0, 1} n .
Proof. Suppose for a contradiction that there exists s, s ′ ∈ {0, 1} n such that σ s = σ s ′ . Then there exists a subset T ∈ {0, 1} n of size 2 n-1 such that σ T = 1 2 n-1 s∈T σ s is not equal to σ T = 1 2 n-1 s∈ T σ s , see footnote 1 . This means that there exists a two-outcome measurement that outputs 1 if s ∈ T and -1 otherwise, with positive bias. We now show for a contradiction that this measurement must also output a parity of some nonempty subset with positive bias. Define the function f : {0, 1} n → {-1, +1}, as the indicator function of T and let b be the measurement outcome. Then

E s∼µ({0,1} n ) [b • f (s)] > 0.
By taking the Fourier representation of the function, we have

E s∼µ({0,1} n ) [b • f (s)] = E s∼µ({0,1} n )   b • S⊆[n] f (S) (-1) s S   = S⊆[n] f (S) E s∼µ({0,1} n ) [b • (-1) s S ] > 0.
Note that f (∅) = E [f (s)] = 0, implying that there exists a non-empty subset S for which

E s∼µ({0,1} n ) [b • (-1) s S ] = 0,
which is a contradiction.

The above statement means that for each s, we have

Tr OA |Ω s Ω s | = Tr OA |Ω 0 Ω 0 |.
In particular, this means that for any s ∈ {0, 1} n there exists a unitary U s acting on OA such that (U s ⊗ I)|Ω 0 = |Ω s . We use the state |Ω 0 to define the INDEX n strategy:

• Alice and Bob share the state |Ω 0 ∈ A ⊗ B.

• Upon receiving s ∈ {0, 1} n , Alice applies U s on OA such that Alice and Bob share |Ω s . Alice measures register O in the computational basis and outputs the measurement outcome a.

• For Alice's input s and output a, Bob has an encoding ρ x where x := s ⊕ a occurs uniformly at random. Upon receiving t ∈ [n], Bob measures B just as in the encoding to learn x t . He outputs b equal to his guess.

• Alice and Bob win the game if b = s t ⊕ a = x t meaning that they win the game if and only if Bob correctly guesses x t .

Since the encoding has bias α, we see that with this INDEX n strategy, they succeed with probability

E s∼µ({0,1} n ) E t∼µ([n])
Pr[Alice's output a and Bob's output b satisfy a

⊕ b = s t ] = E x∼µ({0,1} n ) E t∼µ([n])
Pr[Bob learns x t from the {ρ x : x ∈ {0, 1} n } encoding]

= 1 2 (1 + α),
as desired.

From INDEX strategies to encodings

Suppose Alice and Bob have a strategy to win the INDEX n game with bias α with starting state |ψ ∈ A⊗B.

On input s ∈ {0, 1} n , Alice performs on her side the corresponding measurement which generates her outcome a. Let ρ s,a be the state that Bob has when Alice has input s and outputs a. Define x := s ⊕ a and let σ x be Bob's encoding of x (a weighted sum of ρ x,0 and ρ x, 0 with the weights given by the corresponding probabilities). We show that {σ x : x ∈ {0, 1} n } is an even-parity-oblivious encoding with average-case bias α.

1. First, it hides the even parities: each even parity of x is equal to an even parity of s, which is hidden from the no-signalling principle.

2. Second, Alice and Bob win the INDEX n game with bias α hence,

1 2 (1 + α) = E s∼µ({0,1} n ) E t∼µ([n]) Pr[Bob learns s t ⊕ a] = E x∼µ({0,1} n ) E t∼µ([n]) Pr[Bob learns x t ],
as desired.

Remark

The above equivalence also holds in the classical setting.

On the structure of optimal INDEX game strategies

In this section, we prove Theorems 3 and 4, reproduced below.

Theorem 3 (Optimal quantum INDEX game bias). For any n ∈ N, the optimal quantum bias of an

INDEX n strategy is 1/ √ n.
Theorem 4 (Optimal classical INDEX game bias). For any n ∈ N, the optimal classical bias of an INDEX n strategy is

2 πn (1 + O(1/n)).

The quantum value

The quantum bias of any XOR game can be found efficiently by solving a semidefinite program (SDP) [START_REF] Cleve | Perfect parallel repetition theorem for quantum XOR proof systems[END_REF]. The optimization takes place over a matrix indexed by s ∈ S and t ∈ T with each entry corresponding to the expectation of the measurement outcome of a fixed game strategy. Such a matrix of inner products can be written as a positive semidefinite matrix and the expectation (or bias) of the game strategy is then an inner product of this matrix and one containing the information of the XOR game. Specifically, the quantum bias of the INDEX n game can be calculated as the optimal value of either SDP below Primal problem (P) supremum: B, X subject to: diag(X) = e X 0

Dual problem (D)

infimum: e, y subject to: Diag(y) B where

• diag(X) is the vector on the diagonal of the square matrix X,

• e is the vector of all ones,

• Diag(y) is the diagonal matrix with the vector y on the diagonal,

• B := 1 2 0 A A ⊤ 0 , where A s,t := (-1) st n2 n .
For (P), consider the positive semidefinite matrix X := Y Y ⊤ , where

Y := √ n 2 n A I T .
To show X is feasible in (P), one can check that each diagonal entry of X is equal to 1 from the definition of A above. Note that B, X := √ n 2 n A, A = 1/ √ n proving that the quantum bias is at least 1/ √ n (since the quantum bias is the maximum of B, X over all feasible X).

For (D), let y := u e S v e T where u, v > 0 (determined later) and e S and e T are the vectors of all ones indexed by entries in S and T , respectively. Then

Diag(y) B ⇐⇒ uI S -1 2 A -1 2 A ⊤ vI T 0 ⇐⇒ uvI T 1 4 A ⊤ A = 1 4n 2 2 n I T ⇐⇒ uv ≥ 1 4n 2 2 n .
From above, if we set v := 1 2n

√ n and u := 1 2 √ n2 n , then y is feasible in (D). Since e, y = 2 n u + nv = 1 √ n , we know the quantum bias is at most 1/ √ n (since the quantum bias is equal to the minimum of e, y over all feasible y). Therefore, the quantum bias is exactly 1/ √ n, as required.

The classical value

We

Pr[b t = s t ] = 1 - 1 n |b ⊕ s| H .
Since their strategies are deterministic, Alice should output the maximum of these two, so

max 1 n |b ⊕ s| H , 1 - 1 n |b ⊕ s| H = 1 2 + 1 2 - 1 n |b ⊕ s| H = 1 2 + 1 2 • 2 n n 2 -|b ⊕ s| H .
Therefore, the classical bias is precisely

A construction of a quantum PO-RAC n with optimal bias

In this section, we give an explicit construction of a quantum PO-RAC n with optimal bias.

Lemma 2 (Optimal PO-RAC n ). For any n ∈ N, there exists a PO-RAC n with bias 1/ √ n that uses ⌊n/2⌋ qubits and 1 classical bit.

Our construction builds upon the previously mentioned RACs for sending 2 (resp. 3) classical bits with bias 1/ √ 2 (resp. 1/ √ 3). These are the vertices from the corners of a square inscribed in an equatorial plane in the Bloch sphere, and the corners of a cube inscribed in the Bloch sphere, respectively. To generalize this idea to an n-cube inscribed in an n-dimensional sphere, we use the intuition of hyperbits which is a way to visualize such unit vectors in a quantum mechanical setting. A full discussion of hyperbits and their equivalence to certain quantum protocols is beyond the scope of this paper, but we refer the interested reader to the work of Pawlowski and Winter [START_REF] Pawłowski | From qubits to hyperbits[END_REF].

We note that, after the publication of this paper, we became aware that a similar encoding had been previously discovered by Wehner [Weh08], but remained unpublished.

The construction

Note Lemma 2 is trivially true for n = 1 as the encoding can just be the bit itself. For the rest of the construction, we assume n ≥ 2. Lemma 4. In the encoding above, the parity of any subset of size 2 or greater is hidden.

Proof. Protocols involving shared entanglement and sending one classical bit have limited guessing probabilities for functions such as parity [START_REF] Pawłowski | From qubits to hyperbits[END_REF]. In particular, it can be shown that the biases α S of learning x S satisfy S⊆{0,1} n \∅ α 2 S ≤ 1.

In the encoding above, we have

S:|S|=1 α 2 S ≥ n • 1 √ n 2 = 1
implying α S = 0 for all S of size 2 or greater, implying it is parity-oblivious.

  where the third equality is derived from the anti-commutation relation. We can writeC = Pr[c = +1] -Pr[c = -1] = ψ|A x ⊗ B t |ψ implying Pr[Bob outputs 0] = Pr[c = +1]

  can assume without loss of generality that Alice and Bob's strategies are deterministic. Define b ∈ {0, 1} n as the string of potential answers Bob gives where b t is the bit that Bob outputs on input t ∈ [n]. Now let us examine Alice's strategy. For a fixed input s, if she outputs 1, they win the game with probability

	E t∼µ([n])	Pr[b t = s t ] =	1 n	|b ⊕ s| H ,
	where |x| H denotes the Hamming weight of a string x ∈ {0, 1} n . If she outputs 0, they win the game with probability
	E
	t∼µ([n])

  2 n E s∼µ({0,1} n ) n 2 -|b ⊕ s| H . The quantity E s∼µ({0,1} n ) n 2 -|b ⊕ s| Hcorresponds to the mean deviation of the uniform binomial distribution. This is a well studied quantity and we know that

To see this, take any subset T ∈ {0, 1} n of size

n-1 . If σT = σ T , then we can find s ∈ T and s ′ ∈ T such that σs = σ s ′ , since all the σi are not equal. We consider the subset T ′ where we add {s ′ } and remove {s} from T . We obtain σ T ′ = σ T ′ .

We note here that the choice of these observables is not unique and there are applications in the literature that use slightly different observables. However, this particular choice reduces the encoding dimension by one qubit when n is odd. For example, for n =

our encoding uses ⌊n/2⌋ = 1 qubit (as opposed to two) just as in the well-known quantum encoding of three classical bits into one qubit.

Acknowledgements

This research was supported by the French National Research Agency, through CRYQ (ANR-09-JCJC-0067) and by the European Union through the ERC project QCC.

Our construction is very similar to a proof of Tsirelson's theorem [START_REF] Tsirelson | Quantum analogues of the Bell inequalities: The case of two spatially separated domains[END_REF]. We start by recursively defining the observables G n,1 , . . . , G n,n , for n ≥ 2, which are used to define the actions of Alice and Bob in the PO-RAC n . For n = 2 and n = 3, we define

We use the n = 3 observables as a base case for a recursive formula:

Note that these act on ⌊n/2⌋ qubits, 2 have eigenvalues ±1, and satisfy the anti-commutation relation

Define the following operators for x ∈ {0, 1} n and t ∈ [n]:

Note that A 2 x = I, for all x ∈ {0, 1} n , and B 2 t = I, for all t ∈ [n], so each have ±1 eigenvalues. The PO-RAC n protocol is defined below.

• Encoding states: Alice chooses a uniformly random x ∈ {0, 1} n , creates ⌊n/2⌋ EPR pairs, and measures the first "halves" with the observable A x to get an outcome a ∈ {-1, +1}. She sends the second "halves" and a to Bob. Bob now has a quantum state encoding the string x.

• Decoding procedure: If Bob wishes to learn x t , he measures his EPR halves with the observable B t to get an outcome b ∈ {-1, +1}. He computes c = ab and outputs 0 if c = +1, and 1 otherwise.

In the next two lemmas, we show that the worst-case bias of this encoding is 1 √ n and that it is parityoblivious, thereby proving Lemma 2. Lemma 3. In the encoding above, Bob can learn x t with bias 1/ √ n, for any x ∈ {0, 1} n , t ∈ [n].

Proof. We can assume at the beginning of the protocol, Alice and Bob share the maximally entangled state

The expectation value of the observable C = A x ⊗ B t in this state is given by:


Dr Paul Thevenon

Dr Olivier Julien

ENAC Q D Tessier

M Maillard

Capgemini F Cabantous

F Amarillo-Fernández

Oliveira De

ESA. BIOGRAPHIES Salgueiro

Margaux Cabantous

Denis Maillard

Detection Performances of Evil Waveform Monitors for the GPS L5 Signal

2004 and obtained in 2007 a research master at ISAE in space

Filipe De Oliveira Salgueiro studied at the Instituto Superior Técnico in Lisbon, Portugal, where he accomplished the Master of Science in Aerospace Engineering in 2014. He has been working since 2012 at the European Space Agency in ESTEC on the Radio Navigation Systems and Techniques Section. Subject of work includes: GNSS integrity, SVS, evil waveforms and other GNSS activities.

ABSTRACT

Evil Waveform (EWF) are signal distortions that can create persistent errors (bias) on the pseudo-range measurement of several meters. They are of particular interest for differential GPS users and for safety critical users. For instance, differential corrections do not remove this bias if the reference receiver and the rover receiver use different receiver parameters (notably RF input bandwidth and correlator spacing). In order to protect Civil Aviation users from this kind of errors, the ICAO has standardized a model for this failure, which can then be monitored by high-integrity systems such as SBAS and GBAS. In parallel to the standardization of the model, a family of Signal Quality Monitoring (SQM) techniques has been established for GPS L1 signal. With the appearance of the new GPS L5 signal, Civil Aviation users will be allowed to benefit from increased positioning performances. However, it is necessary to extend the signal deformation models and detection metrics to this new signal. This study uses data collected from modern receivers to evaluate the performances of SQM techniques on L1 C/A and L5 pilot signals. The methodology for establishing the detection thresholds is detailed and applied to 4 different datasets. The results show that the legacy SQM techniques does not reach the required performances when using modern receivers, which have larger pre-correlation bandwidth. For L5 users, an adaptation of the SQM techniques provides compliant results. The study also discusses the performances experienced by different types of users (from unmonitored independent users to differentially-corrected, protected users) and the dependency of the monitoring performances with regard to the receiver parameters.

INTRODUCTION

Evil Waveforms are signal distortions that are attributed to a payload anomaly. They can create persistent errors (bias) on the pseudo-range measurement of several meters, without the receiver loosing lock. They are a particularly dangerous threat for differential GPS users, because differential corrections do not remove this bias if the reference receiver and the rover receiver use different receiver parameters (notably RF pre-correlation bandwidth and correlator spacing). The first occurrence of Evil Waveform occurred in 1993 on SVN19, with a differentially corrected vertical error up to 8 m when SVN19 was taken into account for the position computation, compared to a position when it was excluded [START_REF] Edgar | A Co-operative Anomaly Resolution on PRN-19[END_REF]. The origin of the error was shown to be at the signal generation unit, onboard the satellite payload. In order to protect Civil Aviation users from this kind of errors, the ICAO has standardized a model for this failure [START_REF]International Standards and Recommended Practices[END_REF], which can then be monitored by high-integrity systems such as SBAS and GBAS. A family of monitoring techniques has been developed and implemented in these systems in order to comply with the ICAO requirements. These techniques, named Signal Quality Monitoring (SQM), are based on the observation of the correlation function of the received signal to check if unexpected deformations are present. A founding work for this category of monitoring technique is described in [START_REF] Phelts | Multicorrelator techniques for robust mitigation of threats to GPS signal quality[END_REF]. However, the ICAO model is only defined for the GPS L1 C/A and GLONASS L1 signals, and SQM has only been standardized for GPS L1 C/A signals. With the introduction of a new signal for Civil Aviation users, it is relevant to study if the existing SQM techniques are efficient to monitor GPS L5 pilot signal. Also, modern receivers have different characteristics for processing GPS L1 C/A signals than receivers used during the initial definition of SQM techniques, notably a larger precorrelation bandwidth. This difference may impact the SQM performances. The aim of this paper is to assess the performances of SQM technique on L5 and modernized GPS L1 C/A receivers.

The paper has the following structure. First, the ICAO EWF Threat Model will be adapted to the GPS L5 signal. Secondly, the existing Signal Quality Monitors will be adapted to the GPS L5 signal case. The process to determine the detection threshold will be described and applied to GPS L5 and GPS L1 C/A signals collected with modern receivers. In a third part, the SQM performances will be studied for different types of users. In a fourth part, the SQM performances will be studied in different region of the User Design Space, corresponding to different receiver parameters. A fifth part will come back on some relevant lessons learned in this study through the use of a limited description of collected data based on correlator output statistics rather than complete time series. The range of parameter values for each TM is given in Table 1.

THREAT MODEL ADAPTATION TO GPS L5 SIGNALS Existing ICAO TM for GPS L1

Adaptation of ICAO TM for GPS L5 signals

The GPS L5 signal is a new signal aiming at providing civil aviation users with a second signal, in addition to GPS L1 C/A. This second signal will provide to be more robust to interferences, and will permit to use dual frequency techniques to have an increased redundancy and also eliminate the first order term of the ionospheric delay, thus decreasing the budget error of the estimated pseudo-ranges and consequently increasing the accuracy of the position. In this analysis, we assume that the adapted threat model will not be impacted by the different carrier frequency and by the presence of a signal in the quadrature channel. More particularly, it is assumed that the pseudo-range measurements are provided by the pilot channel, and that only the pilot channel requires an EWF threat model.

It can be assumed that the signal generation unit onboard GPS satellites has a similar architecture for GPS L1 C/A and GPS L5 signals. Indeed, the modulation of the signal is the same except for the code rate. This assumption is confirmed in [START_REF] Wong | Characterization of Signal Deformations for GPS and WAAS Satellites[END_REF]. When observing the nominal deformations of the signal, they are very similar on L1 and L5 signals. We can therefore suppose from these observations that the same type and generation of components are used for the signal generation, and deduce that the failure mode, and hence the threat model, can be similar. Therefore, the 3 types of Threat Models (A,B,C) are kept for GPS L5. Only the ranges of parameters are to be adapted.

To update the range of parameters for the L5 threat models, it is useful to look at the justification of the L1 C/A threat models given in [START_REF] Phelts | Multicorrelator techniques for robust mitigation of threats to GPS signal quality[END_REF].

The range for Δ is justified by the fact that lead or lags larger than 12% of the chip lengths would be easily detectable by multi-correlator techniques. Assuming that the same order of magnitude affects the L5 signal generation failure, this would relate to a chip length of 120% on L5. In order to be realistic with the tracking of GNSS signal, the lead or lag of a TM-A should be restricted to a value below the chip length. In addition, due to expected monitoring performance, a factor 1/2 has been applied to value for the L1 C/A model: it is expected that EWF with Δ over 60% of L5 chip will be easily detectable.

For the parameter 𝑓 𝑑 , the lower value for its range on L1 (4 MHz) is justified by the presence of specific monitors that would protect the military signal L1 P(Y). Since no such "military monitoring" is present on L5, it is proposed to extend the lower range of this parameter to 1 MHz.

For the upper range of 𝑓 𝑑 , the main limiting factor is the signal generator's output filter bandwidth. For L5 signals, the output filter bandwidth is 24 MHz, instead of 20 MHz for L1 C/A signals. Therefore, higher frequency oscillations may be let out by the satellite payload, which leads to the proposition to extend the higher range of this parameter to 24 MHz. For the parameter 𝜎, lower values than 0.8 MNepers/s would result in unstable oscillation on the chips and are unlikely from a payload manufacturer point of view. Higher values than 8.8 MHz would not add any visible degradation. It is proposed to keep the same parameter range.

This proposition is summarized in Table 2. It is further confirmed when looking at the impact of the TM on the measurements using new modulations. Works like [START_REF] Phelts | Effects of Signal Deformations on Modernized GNSS Signals[END_REF] or [START_REF] Fontanella | A Novel Evil Waveforms Threat Model for New Generation GNSS signals: Theoretical Analysis and Performance[END_REF] show that the pseudo-range bias created by the proposed L5 threat model will have a worst case pseudorange error of similar order of magnitude than the ICAO L1 C/A threat model, ie a few meters, thus confirming the need to monitor this kind of threat.

User design space and protected regions for L1 and L5

The term User Design space refers to the values of precorrelation bandwidth and correlator spacing that a receiver uses for tracking a signal. Indeed, GNSS receivers have specific parameters depending on their manufacturer and targeted audience / cost / performances. The pre-correlation bandwidth corresponds to the bandwidth of the filter of the RF front-end. Low values of pre-correlation bandwidth results in the rounding of the correlation shape, thus decreasing the overall accuracy of the correlation peak tracking. It would also result in the filtering of some of the EWF. The correlator spacing is a parameter of the delay lock loop, corresponding to the spacing between the early correlator and the late correlator. Lower correlator spacing, associated with large bandwidth, will usually permit to reach better tracking accuracy and multipath robustness [START_REF] Van Dierendonck | Theory and Performance of Narrow Correlator Spacing in a GPS Receiver[END_REF]. The chip spacing also depends on the type of discriminator used. For L1 C/A signals, both Early-Minus-Late (E-L) and Double Delta (DD) discriminators are considered, while for L5, only E-L is considered.

These parameters are essential since they will affect the error induced on the pseudo-range measurement by EWF. In particular, for differential users, if the reference and the rover receivers have different user design characteristics, the pseudo-range bias created by the EWF will not be appropriately corrected through differential correction.

Consequently, [START_REF] Phelts | Multicorrelator techniques for robust mitigation of threats to GPS signal quality[END_REF] has defined some protected regions in the user design space, where the users are confirmed to be protected against EWF, either through detection and alert to the user, or by confirming that the EWF will not create an error superior to a required threshold after differential corrections. For the moment, no protected region has been standardized for GPS L5 signal, so the suggested regions are only a proposition of the authors, based on the results presented in this paper. The considered user design spaces and the associated protected regions are shown in Figure 2.

GENERAL DESCRIPTION OF SQM

EWFs create some distortion on the correlation function. The main family of EWF monitoring algorithm, named Signal Quality Monitoring (SQM) [START_REF] Phelts | Multicorrelator techniques for robust mitigation of threats to GPS signal quality[END_REF] is based on the observation of the correlation function of the received signal at different points. By choosing the right combination of correlators, it is possible to observe an anomaly in the symmetry or on the slope of the correlation function.

SQM is based on the observation of 2 kinds of metrics:

 ratio metrics, defined in Eq. 1,  symmetry metrics, defined in Eq. 2.

𝑅 𝑚 = 𝐼 𝐸 𝑚 𝐼 𝑃 , or 𝑅 𝑚 = 𝐼 𝐿 𝑚 𝐼 𝑝
Eq. 1

Δ 𝑚 = 𝐼 𝐸 𝑚 -𝐼 𝐿 𝑚 2𝐼 𝑃 Eq. 2
Where,  𝐼 𝐸 𝑚 , 𝐼 𝐿 𝑚 , 𝐼 𝑃 stands for the early, late and prompt correlator value on the in-phase signal component.  𝑚 is the index corresponding to a particular correlator pair.

These metrics are corrected so that their mean value in absence of EWF is equal to 0. The correction comprises the possible biases due to the definition of the metric and the effects of the pre-correlation filter on the metrics.

In EGNOS and LAAS [START_REF] Phelts | Robust Signal Quality Monitoring and Detection of Evil Waveforms[END_REF], a particular version of SQM algorithm -called SQM2b -is used. It relies on three distinct pairs of correlators: one pair for tracking and two pairs for SQM metrics computation. The final detection test is done by checking if any one of the metrics exceeds a threshold 𝑇.

𝛾 = max ( 𝑅 1 𝑇(𝑅 1 ) , 𝑅 2 𝑇(𝑅 2 ) , Δ 1 𝑇(Δ 1 ) , Δ 2 𝑇(Δ 2 ) ) ≥ 1
The detection threshold is determined with regards to the distribution of the metrics, in order to comply with a false alarm probability. Therefore, there is a need to model the distribution of the metrics, through models or measurements.

ADAPTATION OF SQM TO GPS L5 SIGNAL AND CONSIDERATION OF MODERN GPS L1 C/A RECEIVERS

The same SQM principle has been adapted to the GPS L5 signal. The main difference will be the location of the correlator pairs, which will be farther away from the prompt correlator when expressed in fraction of L5 chips, due to the limited bandwidth of the L5 signal. Indeed the L5 correlation peak is rounded due to this limited bandwidth, which makes the area around the correlation peak inadequate for the observation of distortions.

Also, the study of SQM using modern L1 C/A receivers is of current interest, to check if the legacy SQM2b design is still valid with current monitoring receivers.

The first considered receiver is a commercial receiver dedicated to monitoring stations (Novatel G-III). This receiver has only been used with the GPS L1 signal due to the unavailability of an L5-compatible antenna. This receiver provides 13 correlator outputs on L1 C/A signals.

The other considered receiver is a software receiver operated by the European Space Agency (ESA). This receiver is able to track both GPS L1 C/A and GPS L5 signals. This receiver provides 61 correlator outputs on L1 C/A signals, and 23 correlator outputs on L5 signals.

The values of the receiver parameters used in this study are given in Table 3.

The parameters of the current monitoring stations for EGNOS, called RIMS-C, are recalled in the first column.

Note that the main difference between the considered receivers and the current monitoring receivers is the larger pre-correlation bandwidth used in the RF front-end.

Description of measurement datasets

The new thresholds for L5 and modern L1 C/A receivers are determined through a process aiming at respecting the requirements for false alarm probability (𝑃 𝑓𝑎 ) and missed detection probability (𝑃 𝑚𝑑 ), based on different measurement datasets.

The measurement datasets consist in correlator outputs collected with the considered receivers. They are in 2 forms:  Real time series of correlator outputs from a Novatel G-III receiver,  Statistical parameters (standard deviation) of each correlator outputs from Novatel G-III and ESA receivers. See Figure 3 for an illustration of such data for the ESA L1 dataset.

Four datasets are used in this study, shown in Table 4. They are representative of the receiving conditions of GNSS signals in monitoring stations. In particular, the data coming from the ESA receiver is a concatenation of several data collection done at different sites, thus providing some kind of spatial diversity with regards to the constellation geometry. The considered 𝑃 𝑓𝑎 and 𝑃 𝑚𝑑 required as inputs for the threshold determination are deduced from the initial system requirements and the system implementation. The initial system requirements are:  A false alarm probability 𝑃 𝑓𝑎 0 = 1.5.10 -7 per epoch, per satellite and per metric  A missed detection probability 𝑃 𝑚𝑑 0 = 1.10 -3 per satellite failure  A Maximum Error Range Residuals (MERR) under 3.5m. The MERR is the maximum undetected error tolerable at the airborne receiver after differential corrections. Tolerable means that the error will not produce any hazardous misleading information. The chosen value corresponds to the maximum tolerable error for a GAD B system at 5° elevation [START_REF]Minimum Aviation System Performance Standards for Local Area Augmentation System (LAAS)[END_REF].

The methodology to derive the 𝑃 𝑓𝑎 and 𝑃 𝑚𝑑 required for the threshold determination at the monitoring station level depends on the system implementation, with parameters such as the number of monitoring stations, the number of monitoring receivers per monitoring stations, the voting algorithm, etc. Details on this implementation in the EGNOS system cannot be provided in this article. For this study, the considered 𝑃 𝑓𝑎 is 3.162.10 -4 and the considered 𝑃 𝑚𝑑 is 1.82.10 -2 . Where 𝜎 𝐼 𝐸 𝑚 and 𝜎 𝐼 𝐿 𝑚 are the standard deviations of the early and late correlator outputs of the 𝑚-th correlator pair. This model of the correlator outputs assumes that the different correlators are uncorrelated and that the prompt does not bring any additional noise. 2. Definition of the range of thresholds to be tested: from 3 to 7 standard deviations in order to guarantee the required 𝑃 𝑓𝑎 and to have the better 𝑃 𝑚𝑑 , 3. Selection of all sets of thresholds that ensure the required 𝑃 𝑓𝑎 : the 𝑃 𝑓𝑎 is computed for each set of thresholds thanks to the probability density functions of the four metrics, 4. Identification of the EWF that generate a pseudo-range error above 3.5m on corrected users of the protected regions in the User Design space, 5. Determination of the metrics distribution for the retained EWF: EWF are assumed to only have the impact of shifting the metrics' mean without changing their standard deviation, 6. For each retained EWF parameter, the 𝑃 𝑚𝑑 is calculated from the probability density functions of the four metrics affected by the retained EWF. The worst 𝑃 𝑚𝑑 among these retained EWF for a given threshold set is stored. This step corresponds to the identification of the least detectable EWF by the considered set of thresholds. 7. Determination of the best 𝑃 𝑚𝑑 : Thresholds ensuring the lowest stored 𝑃 𝑚𝑑 are selected.

For real time data sets, thresholds determination has been made following the steps detailed below: 1. Determination of the metrics distribution from the time series of correlator outputs, for satellites between 0 and 15° elevations. 2. Definition of the range of thresholds to be tested: from 10 to 12 standard deviations in order to guarantee the required 𝑃 𝑓𝑎 and to have the better 𝑃 𝑚𝑑 . See the discussion towards the end of the article, on the non-Gaussian behavior of the real datasets, leading to these higher thresholds. 3. Selection of all sets of thresholds that ensure the required 𝑃 𝑓𝑎 : the 𝑃 𝑓𝑎 has been computed for each set of thresholds by normalizing each metric of the data sets by its threshold and incrementing the number of false alarms whenever at least one normalized metric exceeds one. The 𝑃 𝑓𝑎 is then the ratio between the number of false alarms and the total number of data, 1. 𝑃 𝑚𝑑 determination and thresholds selection is then made as in steps 4-7 of the previous description.

The methodology for computing the thresholds is summarized in Figure 4 for real measurements. It is important to note that only criteria #1 is a requirement of ICAO. The other 2 criteria are presented for a qualitative assessment of the SQM algorithms.

Compliance of the 𝑷 𝒎𝒅 of the least detectable EWF with ICAO requirement

The EWF detection threshold methodology requires the computation of the first performance criterion. Indeed, the retained set of thresholds is chosen because it will give the best 𝑃 𝑚𝑑 for the least detectable EWF creating a differential range error above 3.5m for any users of the Protected Regions.

In order to further refine the analysis of the 𝑃 𝑚𝑑 , the analysis has been done for users of each Protected Regions of the User Design Space. It means that once the set of thresholds has been chosen thanks to the previous methodology, the 𝑃 𝑚𝑑 of the least detectable EWF creating a differential range error above 3.5m, for a user of the designated Protected Region, is computed. While the Protected Regions are defined by ICAO for L1, they are not defined for L5. Therefore, the L5 regions are chosen by dividing the User Design Space as shown in Figure 2.

The resulting region-specific 𝑃 𝑚𝑑 are given in Figure 5 and Figure 6. For L1 and L5, some regions highlighted in green are compliant with the required 𝑃 𝑚𝑑 .

For L1, a lot of regions are not compliant, which is quite surprising, since L1 SQM has been validated in prior works. Two causes could be at the origin of this results.  The measurement datasets comprise large punctual errors, associated to very low elevation and to instants leading to loss-of-lock or convergence periods after reacquisition. Therefore, these large errors artificially increase the standard deviation of the dataset, and may also result in non-Gaussian distribution (especially in the tails of the distribution).  The location of the monitoring correlator pairs was not optimized regarding the receiver configurations associated to the datasets.

For L5, the compliance is reached in most of the regions. This kind of results could be used to provide guidance for the definition of protected regions in the L5 User Design Space.

SQM qualitative detection performances for different types of users

This section deals with the performance criteria #2 and #3. For these criteria, an EWF is considered as undetected if the average value of the metrics is below the detection threshold. There is no more consideration of the metrics standard deviation and missed detection probability. Figure 7 shows the exact methodology used for computing these criteria.

These criteria are obtained by testing each values of TM parameter range presented in Table 1 and Table 2. The increment on the parameter range is 0.01 chip for Δ, 1 MHz for 𝑓 𝑑 and 1 MNeper/s for 𝜎 for L1, and 0.1 chip for Δ, 1 MHz for 𝑓 𝑑 and 1 MNeper/s for 𝜎 for L5. Also, a range of parameters of the user design space, consisting of a parameter couple {pre-correlation bandwidth, chip spacing} may be tested for the maximum range error determination, depending on the type of user considered, as explained below.

Figure 7 -Methodology for determining the qualitative SQM detection performance

Different types of users have been defined, depending on the use of SQM algorithms, the user design space and the use of differential corrections. The 5 types of users are:  Independent user. This user does not use SQM and its receiver parameters can take any values in the user design space. This is the worst-case user.  Monitoring station, without SQM. This user is similar to the independent user, except that its receiver parameters are fixed to one set of parameter, detailed in Table 3.  Monitoring station, with SQM. This user is similar to the previous user type, except that SQM is implemented. Therefore, the maximum range error will be chosen among the cases where an EWF is not detected, thus reducing it.  Protected user. This user is protected by SQM, but its receiver parameters can take any values in protected regions of the user design space.  Corrected user. This user is protected by SQM and its receiver parameters can take any values in the protected regions of the user design space. Additionally, differential corrections are used, so that the common range error between the reference station and the user is subtracted from the range error. This user is the best-case user.

In the case of the corrected user on L1, it should be mentioned that the monitoring receiver (RIMS-C for EGNOS) may have a different configuration than the reference receiver (RIMS-A), which computes the differential corrections. The reference receiver has the following parameters: 𝐵𝑊 = 16 MHz, 𝐶𝑠 = 0.1023 chip. For L5, it has been assumed that the reference receiver has the same parameter as the monitoring receiver, ie 𝐵𝑊 = 24 MHz, 𝐶𝑠 = 0.5 chip. Figure 8 shows an example of detection performances of SQM on GPS L5 signals, using the L5 ESA receiver. Figure 9 shows an example of contour plot used for the determination of the maximum range error for undetected EWF. This particular contour plot has been drafted for a corrected user using L5 signals.

Finally, Table 6 and Table 7, placed the end of the article, show the results for SQM detection performances for all types of users for all datasets.

Here are a few conclusions on this part of the study:  Large differences between the different types of users can be observed, showing the importance of the implementation of SQM algorithms and the effectiveness of the limitation of the User Design Space to Protected Regions.  For corrected users (which are the users targeted by a system such as SBAS), users using the L1 signal with modern receivers are found to be affected by large undetected differential pseudo-range error, above the required 3.5 m threshold. Also, the low number of detected EWF confirms that either the detection threshold or the monitor design is not adapted to the monitoring function.  For corrected users, users using L5 signals fulfill the requirement of maximum undetected differential pseudo-range error below 3.5 m. One particularity of this study has been to take into account 2 kinds of data for the threshold computation: statistical data (standard deviation of correlator outputs) and raw data (time series of correlator outputs recorded during 30 hours). Datasets #1 and #2 were collected in order to study the possible limitations of considering statistical data. Indeed, the standard deviation of each correlator computed for dataset #2 is coming from the same time series used in dataset #1.

Gaussian approximation of the metrics distribution

The comparative analysis of the metrics distribution under the different assumptions shows that the distribution of the real correlator outputs is not Gaussian, especially towards the tails of the distribution, as shown in Figure 10.

This notably leads to high values of the metrics, especially at low elevation. This leads to the consideration of a much higher detection threshold for dataset #1, in order to be able to comply with a given 𝑃 𝑓𝑎 , thus leading to worse missed detection performances.

This comparison shows that the use of statistical data lead to optimistic SQM performances, as can be observed when comparing datasets #1 and #2. Datasets #2 provides better performances in terms of 𝑃 𝑚𝑑 than dataset #1, while there are coming from exactly the same measurements.

One way to improve the situation, and make the metrics distribution more Gaussian-shaped, would be to exclude some outliers in the data collection, or to assess the distribution after an elevation mask.

Correlation between the metrics

Another potentially abusive assumption of the statistical dataset was to consider the noise on different metrics as statistically independent, as no correlation coefficient was available. However, in reality, the noise and multipath effects on the correlation function are correlated. Therefore, the metrics' behavior may not reflect reality when considering this uncorrelated correlators. This is shown in Figure 11, where it can be observed that the two Δ metrics are correlated in dataset #1, contrary to the metrics generated from dataset #2.

Figure 12 -Illustration of the correlation between the different SQM metrics

When using a statistical dataset, the sets of detection thresholds are determined together so that the overall test (ie that at least one of the four metrics exceeds its threshold) provides the required 𝑃 𝑓𝑎 , assuming independent Gaussian distribution for each metrics. However, taking into account a correlation between the metrics would yield different sets of thresholds. On the other side, this correlation between metrics is taken into account when considering the real time series.

CONCLUSION AND FUTURE WORK

This paper has presented a methodology to compute the SQM monitoring detection thresholds based on different datasets.

The methodology has been applied to datasets corresponding to three L1 C/A data collection with modern receivers, and one L5 data collection.

Compliance with the required 𝑃 𝑚𝑑 for the least detectable EWF creating a differential range error above 3.5m, requested by ICAO has been assessed. The SQM qualitative detection performances have been determined through the percentage of detected EWF. For undetected EWF, the maximum (differential) pseudorange error is also provided. The SQM detection performances were computed for different types of users.

The study shows that the current implementation of SQM algorithms does not provide satisfactory performances on L1 C/A signals, with modern receivers, and with the detection threshold methodology. On the contrary, L5 signals can be adequately monitored with adapted SQM algorithms.

An other result is the dependency of the SQM detection performances to the region of the User Design space. Some regions are better protected than others, and would comply with the targeted requirement. This analysis by region can be useful to define the protected region for L5 users.

Finally, the use of statistical description of correlator outputs requires some particular attention. Notably, when analyzing true time series of correlator outputs, a non-Gaussian distribution of the metrics can be observed, together with a correlation between the different metrics. It is advised to either restrain the use of statistical description of correlator outputs, and to privilege real time series, or to complexify the modeling of the correlator outputs by introducing correlation between the metrics and a model of outliers. Also, the removal of some data on the real time series, for example, very low elevation data, or data corresponding to the convergence period of the tracking loops after a reacquisition may also be recommended.

Future work on this topic includes the adaptation of the SQM algorithm to modern L1 C/A receivers, by finding a new location of monitoring correlator pairs. With newer receiver, it is also possible to have more correlator pairs, thus opening the possibility to monitor distortions with more than 4 metrics and with more points of the correlation function. Finally, new combination of several metrics to comply with a global 𝑃 𝑓𝑎 may be researched, taking into account the correlation between metrics and other voting scheme than a single threshold crossing.

ACKNOWLEDGMENTS

The authors would like to thank ESA for the support to this activity and for the provision of valuable datasets.

Figure 1 -

 1 Figure 1 -Correlation functions distorted by EWF -1 -0.5 0 0.5 1 -0.2 0 0.2 0.4 0.6 0.8 1 1.2

Figure 2 -

 2 Figure 2 -User design space and protected regions (in green) for (a) GPS L1 C/A Early Minus Late, (b) GPS L1 C/A Double Delta, (c) GPS L5 users

Figure 3 -

 3 Figure 3 -Illustration of statistical data: 1-𝝈 envelope of the correlator outputs for ESA receiver on L1 Determination of detection thresholds

For

  statistical data sets, thresholds determination has been made following the steps detailed below: 1. Determination of the metrics distribution from the data sets by using the standard deviation of the metrics for low elevation (0 to 15°) and assuming that metrics have a Gaussian distribution. Metrics' standard deviations are assumed to follow the formulas given below: 𝜎 𝑅 𝑚 = 𝜎 𝐼 𝐸 𝑚 or 𝜎 𝐼 𝐿 𝑚 𝜎 ∆ 𝑚 = 0.5 * √ 𝜎 𝐼 𝐸 𝑚 2 + 𝜎 𝐼 𝐿 𝑚 2

Figure 4 -

 4 Figure 4 -Methodology for computing the detection threshold from raw data SIMULATION OF SQM DETECTION PERFORMANCES The presented methodology has been applied to the 4 datasets presented in Table 4. The SQM detection performances are assessed on 3 criteria: #1 The 𝑃 𝑚𝑑 of the least detectable EWF creating a differential range error above 3.5 m, #2 The percentage of undetected sets of TM parameters, #3 The maximum range error for undetected EWF.

Figure 5 - 3 Figure 6 -

 536 Figure 5 -𝑷 𝒎𝒅 performances for the different Protected Regions of a L1 C/A user, for datasets #1-3

Figure 8 -Figure 9 -

 89 Figure 8 -Simulation of SQM detection performances on L5 for TM-B

Figure 10 -

 10 Figure 10 -Comparison of the distribution of real 𝚫 𝟏 metrics (dataset #1) and the Gaussian assumption (dataset #2)

Figure 11 -

 11 Figure 11 -Illustration of the correlation of metrics in dataset #1 (red) and dataset #2 (blue) Similar correlation has been observed between the different metrics. The Pearson product moments correlation coefficient 𝜌 𝑥,𝑦 have been computed for couple of metrics in Table5and illustrated in Figure12.𝜌 𝑥,𝑦 = 𝑐𝑜𝑣(𝑋, 𝑌) 𝜎 𝑥 𝜎 𝑦

Table 1 -Threat Model parameters for GPS

 1

				L1 C/A
			[2]
		Δ (chip)	𝜎 (MNepers/s)	𝑓 𝑑 (MHz)
	TM A [-0.12 ; 0.12]	-	-
	TM B	-	[0.8 ; 8.8]	[4 ; 17]
	TM C [-0.12 ; 0.12]	[0.8 ; 8.8]	[7.3 ; 13]

Table 2 -Proposed Threat Model parameters for

 2

	L5

Table 3 -Receiver assumptions for L1 and L5

 3

		RIMS-C, L1	Novatel G-III, L1	ESA, L1 ESA, L5
	Pre-correlation bandwidth (MHz)	16		24
	Pre-correlation filter type		6 th order Butterworth
	Corr. spacing for tracking (chip)	0.10	0.10	0.365	0.5
	Corr. spacing for	0.15,	0.15,	0.15,	1.28,
	monitoring (chip)	0.20	0.20	0.2	1.10

Table 4 -Multipath data sets characteristics

 4

		Type of data	Siting	Frequency band	Receiver
	Data set #1	Time series	Capgemini, Bayonne	L1	Novatel G-III
	Data set #2	Statistical	Capgemini, Bayonne	L1	Novatel G-III
	Data set #3	Statistical	Multiple sites	L1	ESA SW receiver
	Data set #4	Statistical	Multiple sites	L5	ESA SW receiver

Table 5 -correlation coefficient between the different metrics in dataset #1

 5

	Δ 1	Δ 2	𝑅 1	𝑅 2
	Δ 1 1	0.91	0.54	-0.73
	Δ 2 0.91	1	0.45	-0.71
	𝑅 1 0.54	0.45	1	0.17
	𝑅 2 -0.73	-0.71	0.17	1

Table 6 -SQM detection performances results for L1 datasets

 6

				TM-A			TM-B			TM-C
	User type	Dataset	Percentage of		PRE (m)	Percentage of		PRE (m)	Percentage of	PRE (m)
			detected EWF	E-L	DD	detected EWF	E-L	DD	detected EWF	E-L	DD
	Corrected user	Novatel G-III (raw) Novatel G-III (stat)	0 38.5	5.9 1.4	16.3 2.9	0 27	10 7	25.4 5.1	5.4 5.4	10.2 6.3	17.7 7
		ESA (stat)	0	5.9	16.3	7.9	7	6,9	11.5	10.2	17.7

Table 7 -SQM detection performances results for ESA L5 (ESA statistical dataset)

 7

			TM-A		TM-B		TM-C
	User type	SQM	Percentage of detected EWF	PRE (m)	Percentage of detected EWF	PRE (m)	Percentage of detected EWF	PRE (m)
	Independent user Monitoring station	No	NA	9.8 7.8	NA	69.5 67.1	NA	78.5 76.1
	Monitoring station			5.4		15.5		19.6
	Protected user	Yes	28.6	6.5	63	15.8	55.6	19.9
	Corrected user			1.0		2.4		2.5

performed its engineer internship in Capgemini Bayonne working on the adaptation of RIMS-C EWF algorithm on L5 pilot signal. She currently works as a GNSS engineer in Capgemini on signal processing subjects. EGNOS team of Capgemini Bayonne. He is currently in charge of the activities linked to GNSS signal processing.

Francisco Amarillo-Fernández received his Master's Degree in Telecommunication by the Polytechnic University of Madrid (UPM) Spain in 1997, and his Master's Degree in Surveying Engineering by the UPM in 1992.