Anonymous Conference Key Agreement using GHZ states

This example protocol achieves the functionality of quantum conference key agreement. This protocol allows multiple parties in a quantum network to establish a shared secret key anonymously.

Tags: Multi Party Protocols, Quantum Enhanced Classical Functionality, Specific Task

Requirements

We require the following resources for this protocol:

1. A source of n-party GHZ states
2. Private randomness sources
3. A randomness source that is not associated with any party
4. A classical broadcasting channel
5. Pairwise private communication channels

Outline

• First, the sender notifies each receiver in the network anonymously
• The entanglement source generates and distributes sufficient GHZ states to all nodes in the network
• The GHZ states are distilled to establish multipartite entanglement shared only by the participating parties (the sender and receivers)
• Each GHZ state is randomly chosen to be used for either Verification or Key Generation. For Key Generation rounds, a single bit of the key is established using one GHZ state by measuring in the Z-basis
• If the sender is content with the Verification results, they can anonymously validate the protocol and conclude that the key has been established successfully.

Notation

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} : Total number of nodes in the network

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} : Number of receiving nodes

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} : Number of GHZ states used

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} : Security parameter; expected number of GHZ states used to establish one bit of key

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} -partite GHZ state: ${\frac {1}{\sqrt {2}}}(|0\rangle ^{\otimes k}+|1\rangle ^{\otimes k})$

Protocol Description

Protocol 1: Anonymous Verifiable Conference Key Agreement

Input: Parameters Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D}

Requirements: A source of n-party GHZ states; private randomness sources; a randomness source that is not associated with any party; a classical broadcasting channel; pairwise private communication channels

Goal: Anonymoous generation of key between sender and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} receivers

1. The sender notifies the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} receivers by running the Notification protocol
2. The source generates and shares Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} GHZ states
3. The parties run the Anonymous Multipartite Entanglement protocol on the GHZ states
4. For each Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (m+1)} -partite GHZ state, the parties do the following:
   • They ask a source of randomness to broadcast a bit Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} such that Pr$[b=1]={\frac {1}{D}}$
   • Verification round: If b = 0, the sender runs Verification as verifier on the state corresponding to that round, while only considering the announcements of the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} receivers. The remaining parties announce random values.
   • KeyGen round: If b = 1, the sender and receivers measure in the Z-basis.
5. If the sender is content with the checks of the Verification protocol, they can anonymously validate the protocol

Protocol 2: Notification

Input: Sender's choice of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} receivers

Goal: The $m$ receivers get notified

Requirements: Private pairwise classical communication channels and randomness sources

For agent $i=1,...,n$:

1. All agents $j\in \{1,...,n\}$ do the following:
   • When agent $j$ is the sender: If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} is not a receiver, the sender chooses Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} random bits Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{r_{j,k}^i\}_{k = 1}^n} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \bigoplus_{k=1}^n r_{j,k}^i = 0} . Otherwise, if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} is a receiver, the sender chooses Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} random bits such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \bigoplus_{k=1}^n r_{j,k}^i = 1} . The sender sends bit Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_{j,k}^i} to agent Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k}
   • When agent Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} is not the sender: The agent chooses Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} random bits Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{r_{j,k}^i\}_{k = 1}^n} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \bigoplus_{k=1}^n r_{j,k}^i = 0} and sends bit Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_{j,k}^i} to agent Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k}
2. All agents Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k \in \{1,...,n\}} receive Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{r_{j,k}^i\}_{j = 1}^n} , and compute Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_k^i = \bigoplus_{j=1}^n r_{j,k}^i} and send it to agent Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i}
3. Agent Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} takes the received Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{z_k^i\}_{k=1}^n} to compute Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z^i = \bigoplus_{k=1}^nz_k^i} . If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z^i = 1} , they are thereby notified to be a designated receiver.

Protocol 3: Anonymous Multiparty Entanglement

Input: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} -partite GHZ state Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{\sqrt{2}}(|0\rangle^{\otimes n} + |1\rangle^{\otimes n})}

Output: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (m+1)} -partite GHZ state Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{\sqrt{2}}(|0\rangle^{\otimes (m+1)} + |1\rangle^{\otimes (m+1)})} shared between the sender and receivers

Requirements: A broadcast channel; private randomness sources

1. Sender and receivers draw a random bit each. Everyone else measures their qubits in the X-basis, yielding a measurement outcome bit Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_i}
2. All parties broadcast their bits in a random order, or if possible, simultaneously.
3. The sender applies a Z gate to their qubit if the parity of the non-participating parties' bits is odd.

Protocol 4: Verification

Input: A verifier V; a shared state between Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} parties

Goal: Verification or rejection of the shared state as the GHZFailed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle _k} state by V

Requirements: Private randomness sources; a classical broadcasting channel

1. Everyone but V draws a random bit Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_i} and measures in the X or Y basis if their bit equals 0 or 1 respectively, obtaining a measurement outcome Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m_i} . V chooses both bits at random
2. Everyone (including V) broadcasts Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (b_i,m_i)}
3. V resets her bit such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_ib_i = 0 (} mod Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2)} . She measures in the X or Y basis if her bit equals 0 or 1 respectively, thereby also resetting her Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m_i = m_v}
4. V accepts the state if and only if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_im_i = \frac{1}{2}\sum_ib_i (} mod Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2)}

Properties

• Protocol 1 has an asymptotic key rate of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{L}{D}}
• This protocol satisfies the following notions of anonymity:
  • Sender Anonymity: A protocol allows a sender to remain anonymous sending a message to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} receivers, if an adversary who corrupts Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t \leq n-2 } players, cannot guess the identity of the sender with probability higher than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{n-t}}
  • Receiver Anonymity: A protocol allows a receiver to remain anonymous receiving a message, if an adversary who corrupts Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t \leq n-2 } players, cannot guess the identity of the receiver with probability higher than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{n-t}}
• Error correction and privacy amplification must be carried out anonymously and are not considered in the analysis of this protocol.

References

• The protocols and their security analysis, along with an experimental implementation for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = 4} can be found in Hahn et al.(2020)

*contributed by Chirag Wadhwa