Editing GHZ-based Quantum Anonymous Transmission
The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then publish the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 1: | Line 1: | ||
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> | * '''Network:''' The network consists of <math>n</math> players that are fully identified and [[completely connected]] with pairwise [[authenticated]] classical and quantum channels. | ||
* ''' | * '''Timing:''' [[Synchronous]] and [[asynchronous]] setting are both considered. | ||
* ''' | * '''Message size:''' The size of messages (quantum and classical) are unbounded. | ||
* '''Shared resources:''' The nodes do not share any prior entanglement or classical correlations. | |||
* '''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.]] | |||
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)]]. | |||
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: | |||
* 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. | |||
* | * 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). | ||
* <math> | </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== | ||
**<math>n:</math> number of nodes | |||
**<math>t:</math> number of failures | |||
**<math>p:</math> fairness of the Oblivious Common Coin | |||
**<math>k:</math> security parameter of the VQSS scheme used to implement the Oblivious Common Coin | |||
**<math>b_i:</math> input bit of player <math>i</math> | |||
**<math>d:</math> the agreement value at the end of the protocol | |||
{{ | ===Relevant Parameters=== | ||
The number of players <math>n</math> and the number of failures <math>t</math> are previously introduced parameters of the agreement protocol. The Quantum Oblivious Common Coin protocol has a single parameter <math>k</math> (used in Verified Quantum Secret Sharing scheme), but it is unclear from the works [[Quantum Byzantine Agreement#References|(1), (3)]] how this influences the guarantees of the protocol. Also note that the fairness <math>p</math> of the Quantum Oblivious Common Coin is not a parameter, but rather a result of the specific implementation of the protocol. The global Byzantine Agreement protocol can then tolerate up to <math>t < \left \lfloor{pn}\right \rfloor </math>. The Quantum Oblivious Common Coin subroutine proposed by [[Quantum Byzantine Agreement#References|(3)]] has <math>p > \frac{1}{3}</math> (synchronous case, <math>p > \frac{1}{4}</math> asynchronous case). | |||
==Hardware Requirements== | |||
*Network stage: [[:Category: Quantum Computing Network Stage|(Fault-tolerant) Quantum computing network stage]][[Category:Quantum Computing Network Stage]] | |||
*Relevant network stage parameters: Required number of qubits <math>q</math>. | |||
*Benchmark values: The number of qubits <math>q</math> required is precisely known for a finite instance of the protocol. This is calculated in [[Quantum Byzantine Agreement#References|(1)]] for <math>n = 5</math>. They pick the smallest possible security parameter <math>k = 2</math> (of the VQSS scheme) and start calculating the required resources. Summarizing they find that each node requires <math>\sim 200</math> operational qubits, on which quantum circuits of depth <math>\sim 2000</math> must be run. The consumed number of Bell pairs is 648 and the total classical communication cost is 21240 bits. It is not entirely clear if these are the expected costs or the cost per round. | |||
*In more asymptotic sense it is known that the required number of qubits per node grows rapidly with the number of nodes <math>n</math>, making it therefore, demanding on qubit requirements. | |||
==Properties== | ==Properties== | ||
The protocol- | |||
<math> | * solves the problem in <math>O(1)</math> expected number of rounds, in particular independent of <math>n</math> and <math>t</math>, whereas classically a lower bound of <math>\Omega(\sqrt{n / \log(n)})</math> is known [[Quantum Byzantine Agreement#References|(3), (6)]]; | ||
* tolerates <math>t \leq n/3</math> (synchronous) or <math>t \leq n/4</math> (asynchronous) Byzantine failures; | |||
* reaches ''agreement'' (each player outputs the same bit) under the ''validity'' condition (the agreement value was proposed by at least one player) and is guaranteed to ''terminate eventually'' (infinite executions occur almost never - i.e. have probability measure zero). | |||
== | ==Pseudo Code== | ||
Receiver <math>R</math> is determined before the start of the protocol. <math>S</math> holds a message qubit <math>|\psi\rangle</math>. | Receiver <math>R</math> is determined before the start of the protocol. <math>S</math> holds a message qubit <math>|\psi\rangle</math>. | ||
# Nodes run a collision detection protocol and determine a single sender <math>S</math>. | # Nodes run a collision detection protocol and determine a single sender <math>S</math>. | ||
# A trusted source distributes <math> | # A trusted source distributes <math>N</math>-partite GHZ state to every player, <math>|GHZ\rangle = \frac{1}{\sqrt{2}} (|0^N\rangle + |1^N\rangle)</math>. | ||
* Anonymous entanglement: | |||
## Sender <math>S</math> and receiver <math>R</math> do not do anything to their part of the state. | ## Sender <math>S</math> and receiver <math>R</math> do not do anything to their part of the state. | ||
## Every player <math>j \in [ | ## Every player <math>j \in [N] \setminus \{S,R\}</math>: | ||
### Applies a Hadamard transform to her qubit, | ### Applies a Hadamard transform to her qubit, | ||
### Measures this qubit in the computational basis with outcome <math>m_j</math>, | ### Measures this qubit in the computational basis with outcome <math>m_j</math>, | ||
Line 48: | Line 57: | ||
## <math>S</math> applies a phase flip <math>Z</math> to her qubit if <math>b=1</math>. | ## <math>S</math> applies a phase flip <math>Z</math> to her qubit if <math>b=1</math>. | ||
## <math>R</math> picks a random bit <math>b' \in_R \{ 0,1 \}</math> and broadcasts <math>b'</math>. | ## <math>R</math> picks a random bit <math>b' \in_R \{ 0,1 \}</math> and broadcasts <math>b'</math>. | ||
## <math>R</math> applies a phase flip <math>Z</math> to her qubit, if <math>b \oplus \bigoplus_{j \in [ | ## <math>R</math> applies a phase flip <math>Z</math> to her qubit, if <math>b \oplus \bigoplus_{j \in [N] \setminus \{S,R\}} m_j = 1</math>. <div style='text-align: right;'>''<math>S</math> and <math>R</math> share anonymous entanglement <math>|\Gamma\rangle_{SR} = \frac{1}{\sqrt{2}} (|00\rangle + |11\rangle)</math>.''</div> | ||
# <math>S</math> uses the quantum teleportation circuit with input <math> | # <math>S</math> uses the quantum teleportation circuit with input <math>\ket{\psi}</math> and anonymous entanglement <math>|\Gamma\rangle_{SR}</math>, and obtains measurement outcomes <math>m_0, m_1</math>. | ||
# The players run a protocol to anonymously send bits <math>m_0,m_1</math> from <math>S</math> to <math>R</math> (see | # The players run a protocol to anonymously send bits <math>m_0,m_1</math> from <math>S</math> to <math>R</math> (see Discussion for details). | ||
# <math>R</math> applies the transformation described by <math>m_0,m_1</math> on his part of <math> | # <math>R</math> applies the transformation described by <math>m_0,m_1</math> on his part of <math>\ket{\Gamma}_{SR}</math> and obtains <math>\ket{\psi}</math>. | ||
==Further Information== | ==Further Information== | ||
* To determine the sender <math>S</math> (Step 1) one can run either a classical collision detection protocol of [[GHZ State based Quantum Anonymous Transmission#References| | * To determine the sender <math>S</math> (Step 1) one can run either a classical collision detection protocol of [[GHZ State based Quantum Anonymous Transmission#References|(4)]] or a quantum collision detection protocol of [[GHZ State based Quantum Anonymous Transmission#References|(6)]]. The quantum version of the protocol requires additional <math>(\left\lceil \log N \right\rceil + 1)</math> GHZ states. | ||
* To determine the receiver <math>R</math> during the protocol one can incorporate an additional step using a classical receiver notification protocol of [[GHZ State based Quantum Anonymous Transmission#References| | * To determine the receiver <math>R</math> during the protocol one can incorporate an additional step using a classical receiver notification protocol of [[GHZ State based Quantum Anonymous Transmission#References|(4)]]. | ||
* To send classical teleportation bits <math>m_0,m_1</math> (Step 5) the players can run a classical logical OR protocol of [[GHZ State based Quantum Anonymous Transmission#References| | * To send classical teleportation bits <math>m_0,m_1</math> (Step 5) the players can run a classical logical OR protocol of [[GHZ State based Quantum Anonymous Transmission#References|(4)]] or anonymous transmission protocol for classical bits with quantum resources of [[GHZ State based Quantum Anonymous Transmission#References|(6)]]. The quantum protocol requires one additional GHZ state for transmitting one classical bit. | ||
* The anonymous transmission of quantum states was introduced in [[GHZ State based Quantum Anonymous Transmission#References| | * The anonymous transmission of quantum states was introduced in [[GHZ State based Quantum Anonymous Transmission#References|(6)]]. | ||
* The problem was subsequently developed to consider the preparation and certification of the GHZ state [[GHZ State based Quantum Anonymous Transmission#References| | * The problem was subsequently developed to consider the preparation and certification of the GHZ state [[GHZ State based Quantum Anonymous Transmission#References|(3), (5)]]. | ||
* In [[GHZ State based Quantum Anonymous Transmission#References| | * In [[GHZ State based Quantum Anonymous Transmission#References|(5)]], it was first shown that the proposed protocol is information-theoretically secure against an active adversary. | ||
* In [[GHZ State based Quantum Anonymous Transmission#References| | * In [[GHZ State based Quantum Anonymous Transmission#References|(1)]] a protocol using another multipartite state, the W state, was introduced. The reference discusses noise robustness of both GHZ-based and W-based protocols and compares the performance of both protocols. | ||
* Other protocols were proposed, which do not make use of multipartite entanglement, but | * Other protocols were proposed, which do not make use of multipartite entanglement, but utilize solely Bell pairs to create anonymous entanglement [[GHZ State based Quantum Anonymous Transmission#References|(2)]]. | ||
==References== | ==References== | ||
Line 68: | Line 77: | ||
#[https://ieeexplore.ieee.org/document/4077005 Bouda et al (2007)] | #[https://ieeexplore.ieee.org/document/4077005 Bouda et al (2007)] | ||
#[https://arxiv.org/abs/0706.2010 Broadbent et al (2007)] | #[https://arxiv.org/abs/0706.2010 Broadbent et al (2007)] | ||
#[https://arxiv.org/abs/ | #[https://arxiv.org/abs/quant-ph/9901035 Brassard et al (2007)] | ||
#[https:// | #[https://link.springer.com/chapter/10.1007/11593447_12 Christandl et al (2005)] | ||
==Further Information== | |||
<div style='text-align: right;'>''contributed by Victoria Lipinska''</div> | <div style='text-align: right;'>''*contributed by Victoria Lipinska''</div> |