{'fraction_non_alphanumeric': 0.03652773473814688, 'fraction_numerical': 0.008676789587852495, 'mean_word_length': 4.147956131605184, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Anonymity for practical quantum networks

Quantum communication networks have the potential to revolutionise information and communication technologies. Here we are interested in a fundamental property and formidable challenge for any communication network, that of guaranteeing the anonymity of a sender and a receiver when a message is transmitted through the network, even in the presence of malicious parties. We provide the first practical protocol for anonymous communication in realistic quantum networks.

A crucial yet challenging functionality required in any network is the ability to guarantee the anonymity of two parties, the Sender and the Receiver, when they wish to transmit a message through the network. In a realistic network, anonymity should be guaranteed in the presence of malicious parties. We would additionally like that this happens in an information-theoretic setting, meaning without making any assumptions neither on the number nor on the computational power of these malicious parties, who might in fact have a quantum computer in their hands. For this, we need to assume that the agents have private pair-wise channels, which in the quantum setting can be substituted by public quantum channels and QKD protocols, and a broadcast channel.
In the classical setting, anonymity, as well as any multiparty secure computation, is possible with informationtheoretic security when there is an honest majority of agents. Here we do not wish to assume such an honest majority. Broadbent and Tapp [5] showed how to anonymously transmit a classical message, as well as a number of other secure protocols, in the absence of an honest majority, albeit under the strong assumption of the existence of a simultaneous broadcast channel.
In the quantum setting, the first work to deal with the anonymity of quantum messages was that of Christandl and Wehner [6]. In their work, one assumes that the n agents share a perfect n-party GHZ state, i.e., the state 1 √ 2 (|0 n + |1 n ) [7]. Under this assumption, they provide protocols with perfect anonymity both for the broadcast of a classical bit and for the creation of an EPR pair between a Sender and a Receiver. Then, they combine the two protocols in order to transmit a quantum message using a teleportation scheme [8]. This first creates an EPR pair anonymously between Sender and Receiver, and then the Sender transmits the two classical outcomes of her measurements anonymously. The advantage of this protocol is that it only involves local operations and classical communication (LOCC) once the GHZ state is shared between the agents. However, it requires the assumption that a perfect GHZ state has been honestly shared between the agents. More recently, Lipinska et al. [9] showed how to perform a similar protocol starting from trusted W states, albeit only probabilistically.
In order to remedy the drawback of a perfect shared quantum state, Brassard et al. [10] devised a different protocol, which includes a verification stage for ensuring that the shared state is at least symmetric with respect to the honest agents, and hence perfect anonymity is preserved. This test involves each agent performing a controlled-NOT operation between her initial quantum bit (qubit) and n − 1 fresh ancilla qubits that she then sends to all other agents. Each agent then measures n−1 qubits in the subspace spanned by the all zeros and all ones strings and if the measurement accepts then the protocol continues with the remaining n-party GHZ state. While the authors manage in this way to preserve perfect anonymity, their protocol cannot be easily implemented, since each agent needs to perform a size-n quantum circuit and also to have access to quantum communication with all other agents.
We address this problem by considering quantum anonymous transmission in the presence of an untrusted source that may not be producing the GHZ state. Our two main ingredients are the Christandl-Wehner protocol for anonymous entanglement [6], and a protocol for verifying GHZ states described in Ref. [11]. We then present a new notion of approximate anonymity that is appropriate for realistic quantum networks, and show a practical and efficient protocol to achieve such anonymity in the transfer of a quantum message.
Anonymous classical protocols.-We first provide the details of a few known anonymous classical protocols. First, there exists a classical private protocol from Ref. [5], LogicalOR, where each agent inputs a single bit and the protocol computes the logical OR of these bits. The correctness of this protocol is 1 when all agents input 0, and 1 − 2 −S after S rounds when any agent inputs 1. Privacy here means that only the agent can know their input. This is built using another protocol Parity [5]; however contrary to the the Parity protocol, LogicalOR does not assume a simultaneous broadcast channel, which is quite impractical. We give both protocols in Appendix A.
We will use the LogicalOR protocol in order to create the functionality RandomBit, given in Protocol 1, which allows the Sender to anonymously choose a random bit according to some probability distribution D, which in our case will be the uniform distribution. The correctness and privacy of RandomBit follow directly from the properties of LogicalOR, namely the only thing the malicious agents learn is the bit chosen by the Sender, but not who the Sender is. We then extend the Random-Bit functionality to define a RandomAgent functionality, where the Sender privately picks a random agent by performing the RandomBit protocol log 2 n times.   Last, we need the Notification functionality [5], given in Protocol 2, where the Sender anonymously notifies an agent as the Receiver. Note that we use the same security parameter S throughout for simplicity, however this is not required.

Protocol 1 RandomBit
Anonymous entanglement with perfect trusted GHZ states.-In addition to the previous classical protocols, we will need the Anonymous Entanglement protocol from Ref. [6], given in Protocol 3. Here, it is assumed that the agents share a state which in the honest case is the GHZ state, and that the Sender and Receiver know their respective identities. It is not hard to see that assuming the initial state is a perfect GHZ state, then the protocol creates an EPR pair between the Sender and the Receiver perfectly anonymously.
Efficient verification of GHZ states.-The last ingredient we use is the Verification protocol for GHZ states from the work of Pappa et al. [11] that was also implemented for 3-and 4-party GHZ states in McCutcheon et

Protocol 3 Anonymous Entanglement [6]
Input: n agents share a GHZ state. Goal : EPR pair shared between Sender and Receiver.
1: Each agent, apart from the Sender and Receiver, applies a Hadamard transform to their qubit. They measure in the computational basis and broadcast their outcome.  al. [12]. There, one of the agents, the Verifier, would like to verify how close the shared state is to the ideal state. Let k be the number of honest agents. The verification protocol is then given in Protocol 4. From the proofs in Refs. [11] and [12], one can see that the perfect state always passes the verification test, and, more interestingly, a soundness statement can also be proven. As in [11], we take the ideal n-party state to be |Φ n 0 , given by: where ∆(y) = i y i denotes the Hamming weight of the classical n-bit string y. This state is equivalent to the GHZ state up to local unitaries. Let a fidelity measure of the state |Ψ shared between the n agents be given by F ′ (|Ψ ) = max U F (U |Ψ , |Φ n 0 ), where U is some operation on the space of the malicious agents. This can then be written in terms of probability of pass-Protocol 4 Verification [11,12] Input: n agents share state |Ψ . Goal : GHZ verification of |Ψ for k honest agents.
1: The Verifier generates random angles θj ∈ [0, π) for all agents including themselves (j ∈ [n]), such that j θj is a multiple of π. The angles are then sent out to all the agents in the network.

3:
The state passes the verification test when the following condition is satisfied: if the sum of the randomly chosen angles is an even multiple of π, there must be an even number of 1 outcomes for Yj, and if the sum is an odd multiple of π, there must be an odd number of 1 outcomes for Yj. We can write this condition as ing the test with the state |Ψ , denoted by P (|Ψ ), as F ′ (|Ψ ) ≥ 4P (|Ψ ) − 3 [12].
For our purposes, we will use below a version of this verification protocol that is similar to the Symmetric Verification protocol in Ref. [11]. There, it was shown that with the use of a trusted common random string it was possible for all agents to take random turns verifying the validity of the GHZ state. This leads to the guarantee that if the state is accepted a large number of times before the agents decide to use it, then with high probability, when the state is used it should be very close to the correct one.
Anonymity for realistic quantum networks.-All the quantum protocols we have seen that are used to achieve anonymity assume perfect operations and achieve perfect anonymity. In practice, of course, no operation can be perfect and hence perfect anonymity is unattainable. Nevertheless, it is still possible to define an appropriate notion of anonymity that is relevant for practical protocols.
We define the notion of an ǫ−anonymous protocol, where for any number n − k of malicious agents out of n agents in total, the malicious agents, even when they have in their possession the entire quantum state that corresponds to the protocol, can only guess who the Sender is (even when the Receiver is malicious) or who the Receiver is, with probability that is bounded by 1 k + ǫ. The perfect anonymity is defined when ǫ is equal to 0.
Efficient anonymous quantum message transmission.-We will now show how to devise an efficient ǫ-anonymous protocol for quantum message transmission. For simplicity we assume there is only one Sender. If not, the agents can run a simple classical protocol in the beginning of the protocol in order to deal with collisions (multiple Senders) and achieve the unique Sender property. See also Refs. [5] and [6] for details.
Moreover, for simplicity we will describe a protocol where we distribute one EPR pair between the Sender and the Receiver. Then one can perform anonymous teleportation of the classical measurement results, using in particular the Fixed Role Anonymous Message Transmission functionality as was described in Ref. [5]. In case we want to increase the fidelity of the transmitted quantum message, we can further use the subroutines from Brassard et al. [10] which first create a number of non-perfect EPR pairs, then distill one pair and then perform the teleportation. Given that our main contribution is the efficient anonymous protocol for the GHZ verification, we do not provide here these details that are explained in Ref. [5].
Our scheme is outlined in Protocol 5.

Protocol 5 ǫ-Anonymous Entanglement Distribution
Input: Security parameter S. Goal : EPR pair created between Sender and Receiver with ǫ-anonymity.
1: The Sender notifies the Receiver: The agents run the Notification protocol.
2: GHZ state generation: The source generates a state |Ψ and distributes it to the agents. (i) Run the RandomAgent protocol, where the Sender inputs a uniformly random j ∈ [n], to get output j.
(ii) Agent j runs the Verification protocol as the Verifier, and if she accepts the outcome of the test they return to step 2, otherwise the protocol aborts.
If at any point in the protocol, the Sender realises someone does not follow the protocol, she stops behaving like the Sender and behaves as any agent.
We are now ready to analyse the above protocol. First, note that if the state is a perfect GHZ state and the operations of the honest agents are perfect, then the anonymity of the protocol is perfect.
In step 1, the agents run the Notification protocol which is perfectly anonymous. In the second step, the GHZ state is shared between the agents, which does not affect the anonymity. Note that the role of the source can be played by an agent, as long as the choice of the agent is independent of who the Sender is. In step 3(a), the agents run the RandomBit protocol which is also perfectly anonymous. The analysis of the step 3(b) follows from the analysis of the Symmetric Verification protocol in Ref. [11]. The only difference here is that instead of using a common random string, it is the Sender who picks the randomness uniformly. Thus, since the input of the Sender completely determines the outcome of the protocol, the Sender can immediately see if her choice does not correspond to the outcome, and hence only continues if the randomness is perfectly uniform.
Let C ǫ be the event that the above protocol does not abort and that the state used for the Anonymous Entanglement protocol is such that no matter what operation the malicious agents do to their part, the fidelity of the state with the GHZ state is at most √ 1 − ǫ 2 . Then, we prove the following Theorem for the honest agents: Proof sketch. The probability of event C ǫ is given by the probability of the state being used and all the tests being passed in the previous rounds. This in turn will depend on the success probability of RandomBit, and if the agent chosen to act as the Verifier is honest. Given that a state of fidelity F ′ (|Ψ ) passes the verification protocol with probability P (|Ψ ), we can then determine this bound by following the proof in Ref. [11]. The full proof is given in Appendix B.
By taking S = log 2 ( 4n (1− √ 1−ǫ 2 )δ ), we have Pr[C ǫ ] ≤ δ. Let us assume for simplicity that when the event C ǫ is true, which happens with probability at most δ, the malicious agents can perfectly guess the Sender or the Receiver. We will now see that when the event C ǫ is false, which happens with probability at least 1 − δ, the malicious agents cannot guess the Sender or the Receiver with probability much higher than a random guess. Note that C ǫ being false means that the fidelity of the shared state with the GHZ state is at least √ 1 − ǫ 2 . By doing enough runs, we can ensure that the probability of C ǫ is negligible.
We then prove anonymity as follows: Theorem 2. If the agents share a state |Ψ such that min where U is an operator on the space of the malicious agents, then the probability that the malicious agents can guess the identity of the Sender is given by: Proof sketch. First, we show that when the shared state is close to the GHZ state, then the fidelity between the final state of the protocol when the Sender is agent i, |Ψ i , and the final state of the protocol when the Sender is agent j, |Ψ j , is high. Then, we show that when the fidelity between the states |Ψ i and |Ψ j is close to 1, the probability that the malicious agents can guess the identity of the Sender is close to a random guess. The full proof is given in Appendix C.
Finally, we consider the entangled state created anonymously between the Sender and Receiver. Although we have not considered a particular noise model, our analysis incorporates a reduced fidelity of |Ψ , the state shared by all the agents at the beginning of the protocol. We can carry this forward to the resulting anonymously entangled state, if we assume all the agents are honest and have followed the protocol. We find that the fidelity of the final entangled state with the EPR pair will be at least the fidelity of |Ψ with the GHZ state. After the entangled state has been constructed, the Sender and Receiver can perform anonymous teleportation of any quantum message |φ by anonymously sending a classical message with the teleportation results. Our final statement is then given in Corollary 3.

Corollary 3. Using Protocol 5, we can achieve an ǫanonymous protocol for quantum message transmission.
Discussion.-We have proposed a practical protocol for anonymous quantum communications in the presence of malicious parties and an untrusted source. The verification step is carried out using a protocol that has been experimentally demonstrated [12], and is tolerant to losses and noise by design. Our protocol achieves in this full adversarial scenario an approximate notion of anonymity that we call ǫ-anonymity and which is relevant in the context of realistic quantum networks.
While the scheme in Ref. [10] results in an exponential scaling, their protocol is not easily implementable. Recent work in Ref. [9] provides a protocol for anonymous transmission using the W state rather than the GHZ state. While this is beneficial in terms of robustness to noise, the protocol creates the anonymously entangled state only with a probability 2/n. Furthermore, the security analysis considers only the semi-active adversarial scenario, which requires a trusted source.
Our anonymous quantum communication protocol opens the way to the integration and implementation of this fundamental functionality into quantum networks currently under development.
We first give the Parity protocol from [5], by which a set of n agents can privately determine the parity of their inputs, in Protocol 6. Note that although this uses a simultaneous broadcast channel, we only use the modified version of this protocol (as given in the LogicalOR protocol afterwards), which just requires a regular broadcast channel.
This protocol is then used to construct the LogicalOR protocol [5], by which a set of n agents can privately determine the logical OR of their inputs. Due to repeating the protocol with different orderings of the agents each time, the simultaneous broadcast channel is no longer required. This is given in Protocol 7.
If all agents input x i = 0, then the LogicalOR protocol is correct with probability 1, however if any agent inputs x i = 1, then the correctness is (1 − 2 −S ). In Protocol 5, the functionality RandomBit is used to pick between the verification and use of the state. This in turn calls LogicalOR. In an honest run, the outcome of Random-Bit is the outcome of the Sender, and so if any agent Protocol 6 Parity [5] Input: {xi} n i=1 . Goal : Each agent gets yi = n i=1 xi.
1: Each of the n agents wants to input their bit xi. Every agent i chooses random bits {r j i } n j=1 such that n j=1 r j i = xi.
2: Every agent i sends their jth bit r j i to agent j (j can equal i).
3: Every agent j computes zj = n i=1 r j i and reports the value in the simultaneous broadcast channel.

4:
The value z = n j=1 zj is computed, which equals yi.
1: The agents agree on n orderings, with each ordering having a different last participant. behaves dishonestly the Sender will abort. The functionality RandomAgent, which also calls LogicalOR, is simply a repetition of RandomBit, and so the same argument holds here.

Appendix B
First, we prove the soundness of the protocol.
Proof. Our aim is to bound the probability that the fidelity of the state |Ψ used for anonymous transmission is given by F (U |Ψ , |Φ n 0 ) ≤ √ 1 − ǫ 2 , where U is an operator on the space of the malicious agents.
First, we consider the probability that the state is used in round l. For this to happen, the Sender must get the result of all S coin flips to be heads (x = 0), which happens with probability 2 −S . The Sender then calls RandomBit with her input as 0. The output of RandomBit will then be 0 with probability 1, since all agents input 0 (note that the Sender can see if any agent behaves dishonestly and inputs 1, as the output of RandomBit can then be 1, and so the Sender will abort).
Second, we consider the probability that the state is tested in all (l − 1) previous rounds. Here, the Sender must input 1 to RandomBit. First, the probability of the Sender not getting all S coin flips to be 0 is given by 1 − 2 −S . Then, the probability that RandomBit will give an output of 1 is given by 1 − 2 −S after S rounds. Malicious agents will not affect the output, since even if they input 1 to RandomBit, the output will still be 1. Thus, the overall probability is given by Finally, we consider the probability that all the (l − 1) tests have passed. In our protocol, a randomly chosen agent j runs the Verification protocol as the Verifier. If the Verifier is honest (which happens with probability k n ), the probability that the test is passed with a state |Ψ is given by P (|Ψ ). If the Verifier is malicious (with probability n−k n ), we take the probability to be 1 as the worst case scenario. Then, we can write the probability that all (l − 1) tests have passed as n−k n + k n P (|Ψ ) l−1 .
Note that from [11], the probability that a state |Ψ with fidelity F will pass the test is given by P (|Ψ ) ≤ 3 4 + F 4 . Thus, the total probability of event C ǫ at the l th repetition of the protocol is: We then take the integral to upper bound this probability as follows: Since each honest agent does not know which other agents are honest or malicious, we can further upperbound this in terms of a security statement for the honest agents: If the agents take S = log 2 ( 4n (1− √ 1−ǫ 2 )δ ), they get Pr[C ǫ ] ≤ δ. The number of runs of the protocol is given by 2 S = 4n (1− √ 1−ǫ 2 )δ . Thus, they can make this probability of failure negligible by doing a large number of runs.
Appendix C Next, we prove the anonymity of the protocol as given in Theorem 2. For simplicity of the proof, recall that we denote the ideal state by |Φ n 0 , which can be obtained from the GHZ state by applying a Hadamard and a phase shift √ Z to each qubit. The Sender's transformation now becomes σ x σ z . Further, we also define the state: and note that σ x σ z |Φ n 0 = |Φ n 1 , σ x σ z |Φ n 1 = − |Φ n 0 . We consider two cases here: first, when all the agents are honest (Lemma 4), and secondly, when we have malicious agents who could apply some operation on their part of the state (Lemma 5).
Lemma 4. If all the agents are honest, and they share a state |Ψ such that F (|Ψ , |Φ n 0 ) = √ 1 − ǫ 2 , then for every honest agent i, j who could be the Sender, we have that F (|Ψ i , |Ψ j ) ≥ 1 − ǫ 2 , where |Ψ i is the state after agent i has applied the Sender's transformation.
Proof. If we have F (|Ψ , |Φ n 0 ) = | Ψ|Φ n 0 | 2 = √ 1 − ǫ 2 , then from [11] we can write the state shared by all the agents as: If agent i is the Sender, then she applies σ x σ z , and the state becomes: Instead, if agent j is the Sender and she applies σ x σ z , the state becomes: The fidelity is then given by: Lemma 5. If some of the agents are malicious, and they share a state |Ψ such that min where U is an operator on the space of the malicious agents, for every honest agent i, j who could be the Sender, we have that F (|Ψ i , |Ψ j ) ≥ 1 − ǫ 2 , where |Ψ i is the state after agent i has applied the Sender's transformation.
Recall that in this case, from [11] we can write: where note that |χ contains both honest and malicious parts, of which the honest part is orthogonal to both Φ k 0 and Φ k 1 . We want to find the closeness of the states |Ψ i , |Ψ j , which are the states after the σ x σ z operation is applied by either agent i or j who is the Sender. These states are given by: The fidelity is then given by: However, although the overall state |Ψ is normalised, the malicious agents' part of the state is not. Thus, we need to determine a bound on ψ 0 |ψ 0 and ψ 1 |ψ 1 . We have: Since this is the minimum value we can get by applying some unitary, in general we have: It was shown in [11] that we can write for any k, n: and using this, we get: Using the triangle inequality, we have: Using the Cauchy-Schwarz inequality, we have: Since the overall state |Ψ is normalised, we have χ ′ |χ ′′ ≤ 1 − √ 1 − ǫ 2 . Thus, we get our expression for fidelity as: which gives D(|Ψ i , |Ψ j ) ≤ ǫ.
We are now ready to prove Theorem 2.
Theorem 2. If the agents share a state |Ψ such that min U F (U |Ψ , |Φ n 0 ) = √ 1 − ǫ 2 , where U is an operator on the space of the malicious agents, then the probability that the malicious agents can guess the identity of the Sender is given by: Proof. We will now show that if the agents share close to the GHZ state, then the Sender remains anonymous. From Theorem 1, we saw that the probability that the state used for anonymous transmission satisfies F (U |Ψ , |Φ n 0 ) ≤ √ 1 − ǫ 2 is given by Pr[C ǫ ] ≤ δ for the honest agents, where δ depends on the number of runs of the verification protocol. Thus, by doing enough runs, we can make this very small, and so we have that the state used for anonymous transmission will be close to the GHZ state, as given by F (U |Ψ , |Φ n 0 ) ≥ √ 1 − ǫ 2 . From the previous proof, we saw that if F (U |Ψ , |Φ n 0 ) ≥ √ 1 − ǫ 2 , the distance between the states if agent i or j was the Sender is D(|Ψ i , |Ψ j ) ≤ ǫ. A malicious agent who wishes to guess the identity of the Sender would make some sort of measurement to do so. Thus, we wish to find the maximum success probability of a measurement that could distinguish between the k states that are the result of the Sender (who can only be an honest agent) applying the σ x σ z transformation.
The success probability of discriminating between k states is given by k i=1 p i Tr(Π i ρ i ). From Lemma 5, we know that the distance between any two states after the Sender's transformation is upper-bounded by ǫ. Thus, if we take |α = |Ψ j , then we know that the state in any round is of distance ǫ away from this same state |α .
For any POVM element P , we can write the trace distance between two states ρ, σ as Tr P (ρ − σ) ≤ D(ρ, σ). Thus, we have for a POVM element Π i and for states |Ψ i , |α : Assuming that each honest agent has an equiprobable chance of becoming the Sender, the probability that the malicious agents can guess the identity of the Sender is bounded by: Tr(Π i |α α|) + ǫ (35)