|
|
| Line 1: |
Line 1: |
| | | The GHZ-based quantum anonymous transmission protocol implements the task of [[Quantum Anonymous Transmission]] in a <math>N</math>-node quantum network. The protocol uses <math>N</math>-partite [[GHZ state]] to enable two parties, sender <math>S</math> and receiver <math>R</math>, to establish a link which they use to transmit a quantum message. Importantly, the quantum message is transmitted in a way that the identity of <math>S</math> is unknown to every other node, and the identity of <math>R</math> is known only to <math>S</math>. |
| The classical problem of Byzantine agreement [[Quantum Byzantine Agreement#References|(8)]] is about reaching agreement in a network of <math>n</math> players out of which <math>t</math> players may be faulty. Each player starts with an input bit <math>b_i</math> and the goal is for all correct players to output the same bit <math>d</math> [[agreement]], under the constraint that <math>d = b_i</math> at least for some node <math>i</math> [[validity]]. The [[hardness]] of this task depends on the [[failure model]] of the faulty (sometimes called [[adversary]]) players. In Byzantine agreement, the faulty players are assumed to show the most severe form of failure known as Byzantine failures. In this model, faulty players behave arbitrarily, can collude and even act maliciously trying to prevent correct players from reaching agreement. Byzantine agreement is an important problem in classical distributed systems, used to guarantee consistency amongst distributed data structures. | |
|
| |
|
| '''Tags:''' [[:Category: Quantum Enhanced Classical Functionality|Quantum Enhanced Classical Functionality]][[Category: Quantum Enhanced Classical Functionality]], [[:Category: Multi Party Protocols|Multi Party Protocols]] [[Category: Multi Party Protocols]], [[:Category:Specific Task|Specific Task]][[Category:Specific Task]], GHZ state, anonymous transmission | | '''Tags:''' [[:Category: Quantum Enhanced Classical Functionality|Quantum Enhanced Classical Functionality]][[Category: Quantum Enhanced Classical Functionality]], [[:Category: Multi Party Protocols|Multi Party Protocols]] [[Category: Multi Party Protocols]], [[:Category:Specific Task|Specific Task]][[Category:Specific Task]], GHZ state, anonymous transmission |
| ==Assumptions== | | ==Assumptions== |
| * '''Network:''' The network consists of <math>n</math> players that are fully identified and [[completely connected]] with pairwise [[authenticated]] classical and quantum channels. | | Availability of the following is assumed: |
| * '''Timing:''' [[Synchronous]] and [[asynchronous]] setting are both considered. | | * Pairwise [[authenticated]] private classical channels |
| * '''Message size:''' The size of messages (quantum and classical) are unbounded. | | * [[Broadcast]] channel |
| * '''Shared resources:''' The nodes do not share any prior entanglement or classical correlations.
| | * [[Trusted]] [[multipartite]] source |
| * '''Failure:''' At most <math>t < n/3</math> (synchronous) or <math>t < n/4</math> (asynchronous) Byzantine node failures are assumed. Byzantine failures are allowed to behave arbitrarily and collude to try and prevent the honest players from reaching agreement. The most severe model is used: Byzantine failures are [[adaptive]], [[computationally unbounded]] and have [[full-information]] (full information of quantum states is modeled by giving a classical description of the state to the adversaries). [[Link failures]] are not considered.
| |
|
| |
|
| ==Outline== | | ==Outline== |
| [[File:ByzantineAgreementFig.PNG|50px|frame|Schematic representation of an execution of a Byzantine Agreement protocol with <math>n = 5</math> nodes and <math>t = 1</math> Byzantine failure. The red bits indicate the input value of each node, whereas the green bit represents the output. The solution shown satisfies the ''agreement'' and ''validity'' properties. The quantum Byzantine agreement protocol in the most strong model requires constant expected number of rounds, whereas a classical lower bound of <math>{\Omega}(\sqrt{n / \log(n)})</math> is known.]] | | The presented GHZ-based quantum anounymous transmission protocol is based on the work of [[GHZ State based Quantum Anonymous Transmission#Refrences|(6)]]. The goal of the protocol is to transmit a quantum state <math>|\psi</math> from the sender <math>S</math> to the receiver <math>R</math>, while keeping the identities of <math>S</math> and <math>R</math> anonymous. We assume that there is exactly one receiver which is determined before the start of the protocol. The protocol consists of the following steps. |
| Here we will sketch the outline of the protocol by Ben-Or [[Quantum Byzantine Agreement#References|(3)]] that solve Byzantine Agreement using quantum resources. A very nice summary of this protocol is also presented in [[Quantum Byzantine Agreement#References|(1)]].
| | * ''Collision detection:'' Nodes run a collision detection protocol to determine a single sender <math>S</math>. |
| The main idea of this protocol is for each player to classically send its proposed value/decision (a valid message) to every other player and then collaborate to determine what a majority of honest players proposed. In the case where adversaries make this difficult, a `good-enough' random coin is globally flipped (using quantum resources, explained below), which is then classically post-processed to reach agreement among the honest parties. More precisely, the protocol is outlined as follows. Each round consists of the following steps:
| | * ''State distribution:'' A trusted source distributes the <math>N</math>-partite GHZ state. |
| | | * ''Anonymous entanglement:'' <math>N-2</math> nodes (all except for <math>S</math> and <math>R</math>) measure in the <math>X</math> basis and broadcast their measurement outcome. <math>S</math> and <math>R</math> broadcast random dummy bits. The parity of measurement outcomes allows to establish an entangled link between <math>S</math> and <math>R</math> which is called [[anonymous entanglement]] (AE). |
| * Each player transmits its input to every other player. If one player receives more than 2/3 of the same values from the other players (including his own), then he changes his input also to this value (if that player already did not have the same choice). Otherwise, the same player executes a Quantum Oblivious Common Coin subroutine and sets his input to the outcome of this routine. | | * ''Teleportation:'' Sender <math>S</math> teleports the message state <math>|\psi\rangle</math> to the receiver <math>R</math> using the established anonymous entanglement. Classical message $m$ associated with teleportation is also sent anonymously. |
| * Then each player sequentially executes two classical subroutines to bias the agreement value towards <math>0</math> or <math>1</math> (outcomes of a coin flip). This guarantees that if the non-faulty players are in agreement, then they will terminate and successfully output the correct agreement value <math>d</math> (not an outcome of coin flip). | |
| </br> | |
| | |
| '''[[Quantum Oblivious Common Coin]] subroutine:''' The heart of this protocol comes from the quantum enhanced [[Oblivious Common Coin]]. At the end of this subroutine, each player outputs a random bit, such that with a least probability value (called the [[fairness]]) <math>0</math> or <math>1</math>. Intuitively, this subroutines tosses a common coin, where all players get either heads or tails, each with fairness probability, but there may be executions where all players do not get the same output and no common coin is actually tossed. Since the players do not know whether the outcomes are all equal or not, this type of coin tossing is referred to as oblivious common coin tossing. In particular, using quantum resources, this task can be achieved in constant rounds (in the defined model). The implementation of this subroutine makes use of a weakened version of [[Verifiable Quantum Secret Sharing]] (VQSS).
| |
|
| |
|
| ==Notations Used== | | ==Notations Used== |
| Line 31: |
Line 25: |
| * Relevant parameters to establish one anonymous link: <math>k=1</math> round of quantum communication per node, circuit depth <math>m=1</math>, <math>q=1</math> physical qubits per node. | | * Relevant parameters to establish one anonymous link: <math>k=1</math> round of quantum communication per node, circuit depth <math>m=1</math>, <math>q=1</math> physical qubits per node. |
| * Quantum memories, single-qubit Pauli gates and single-qubit measurements at the end nodes. | | * Quantum memories, single-qubit Pauli gates and single-qubit measurements at the end nodes. |
| * Trusted multipartite GHZ source.
| |
| * Pairwise authenticated private classical channels.
| |
| * Broadcast channel.
| |
|
| |
|
| ==Properties== | | ==Properties== |