Revision History for: Quantum Collision Detection
- 2026-04-15 at 16:04 by Mina Doosti
implements Anonymous Transmission
Introduction
This protocol [1] is a quantum primitive for anonymous networks that allows a group of $n$ players to determine whether more than one player wishes to send at the same time. In other words, it detects whether a collision has occurred among potential senders, while preserving sender anonymity.
The protocol is designed as a subroutine for anonymous communication. Before attempting an anonymous transmission, the players run collision detection to ensure that there is either exactly one sender or more than one. If a collision is detected, the transmission attempt is aborted or postponed.
A notable feature of this protocol is that it is traceless: after the protocol ends, the public transcript does not reveal which players attempted to send. This distinguishes it from earlier classical collision-detection approaches used in anonymous communication settings.
Related Paper(s)
Outline
A group of $n$ players shares several $n$-qubit GHZ states of the form $|\\\Psi\\\rangle = (|0\\\rangle^{\\\otimes n} + |1\\\rangle^{\\\otimes n})/\\\sqrt{2}$. The goal is to determine whether exactly one player wants to send, or whether multiple players want to send simultaneously.
The protocol proceeds in $\\\lceil \\\log n \\\rceil + 1$ rounds. In each round, a differently rotated GHZ state is used. Any player who wishes to send applies a phase rotation to his share of that state. Then all players apply Hadamard gates, measure in the computational basis, and broadcast their outcomes.
By checking the parity of the total number of measurement outcomes equal to $1$, the players can detect whether a collision has occurred. If the parity is odd in any round, then more than one player wanted to send. If the parity is even in every round, then exactly one player wanted to send.
The protocol is intended for the honest-but-curious setting for this subroutine: it correctly detects collisions provided that no user actively disrupts the protocol.
Assumptions
- There are $n$ players in the network.
- The players share $\\\lceil \\\log n \\\rceil + 1$ copies of the $n$-qubit GHZ state $|\\\Psi\\\rangle = \\\frac{|0\\\rangle^{\\\otimes n} + |1\\\rangle^{\\\otimes n}}{\\\sqrt{2}}.$
- The players have access to a classical broadcast channel.
- A designated player, or the state-distribution process, can prepare the rotated versions of the GHZ states required by the protocol.
- The protocol assumes that players do not actively disrupt the collision-detection procedure. In particular, the correctness argument is given for the case where players follow the protocol honestly.
- The protocol is used as a subroutine before anonymous transmission, in order to determine whether there is exactly one sender.
Requirements
Network stage: multi-party anonymous communication network.
- Shared resource: $\\\lceil \\\log n \\\rceil + 1$ shared $n$-qubit GHZ states.
- Classical communication: one broadcast round per collision-detection round.
- Nodal capabilities:
- Application of single-qubit phase rotations,
- Application of Hadamard gates,
- Computational-basis measurement,
- Authenticated broadcast of classical outcomes.
Notation
- $n$: number of players.
- $V$: the set of players.
- $|\\\Psi\\\rangle$: the $n$-qubit GHZ state $|\\\Psi\\\rangle = \\\frac{|0\\\rangle^{\\\otimes n} + |1\\\rangle^{\\\otimes n}}{\\\sqrt{2}}.$
- $j$: the round index, where $0 \\\leq j \\\leq \\\lceil \\\log n \\\rceil.$
- $R_z(\\\theta)$: the single-qubit phase rotation
$$ R_z(\\\theta) = \\\left( \\\begin{array}{cc} 1 & 0 \\\\\\\\\ 0 & e^{i\\\theta} \\\end{array} \\\right) $$
up to an irrelevant global phase convention. - $U_j$: the initial rotation used to prepare the $j$-th resource state $U_j = R_z\\\!\\\left(-\\\frac{\\\pi}{2^j}\\\right) \\\otimes I^{\\\otimes (n-1)}$.
- $|t_j\\\rangle$: the rotated GHZ state used in round $j$, that is $|t_j\\\rangle = U_j |\\\Psi\\\rangle.$
- $k$: the number of players who want to send.
- $k_j$: the total number of measurement outcomes equal to $1$ in round $j$.
Properties
- Total number of rounds: $\\\lceil \\\log n \\\rceil + 1$.
- The protocol detects whether the number of interested senders is greater than $1$.
- Correctness:
- Correctness for the no-collision case: if exactly one player wants to send, then in every round the combined effect of the sender’s rotation cancels the initial offset in the shared state, and the protocol does not report a collision.
- Correctness for the collision case: if $k \\\geq 2$ players want to send, then there exists a round $j$ such that
$$
k = 2^j m + 1
$$
for some odd integer $m$. In that round, the accumulated phase produces the state
$$
\\\frac{|0\\\rangle^{\\\otimes n} – |1\\\rangle^{\\\otimes n}}{\\\sqrt{2}}
$$
up to a global phase, which is detected by an odd parity of the measurement outcomes.
- Correctness for the no-collision case: if exactly one player wants to send, then in every round the combined effect of the sender’s rotation cancels the initial offset in the shared state, and the protocol does not report a collision.
- Collision-detection guarantee: using $\\\lceil \\\log n \\\rceil + 1$ rounds, the protocol detects every case with
$$
2 \\\leq k \\\leq n.
$$ -
Anonymity: the public information consists only of the broadcast measurement outcomes. These outcomes reveal whether a collision occurred, but not which players attempted to send.
-
Tracelessness: after the protocol ends, the communication transcript and later inspection of local randomness do not identify the players who expressed interest in sending.
-
Limitation: the protocol is not designed to handle active disruptors in this form. A malicious player can disturb the shared entangled resource and force failure.
Technical Description
Input: each player privately decides whether he wants to send.
Output: the players learn whether there is a collision, i.e. whether more than one player wants to send.- Resource preparation
- The players share $\\\lceil \\\log n \\\rceil + 1$ copies of the GHZ state
$$
|\\\Psi\\\rangle = \\\frac{|0\\\rangle^{\\\otimes n} + |1\\\rangle^{\\\otimes n}}{\\\sqrt{2}}.
$$ - For each round $j$ with $0 \\\leq j \\\leq \\\lceil \\\log n \\\rceil,$
a designated player prepares the rotated state $|t_j\\\rangle = U_j |\\\Psi\\\rangle,$
where
$$
U_j = R_z\\\!\\\left(-\\\frac{\\\pi}{2^j}\\\right) \\\otimes I^{\\\otimes (n-1)}.
$$
- The players share $\\\lceil \\\log n \\\rceil + 1$ copies of the GHZ state
- Round $j$: For each round $j$ with $0 \\\leq j \\\leq \\\lceil \\\log n \\\rceil,$, all players perform the following steps:
- Every player who wants to send applies the rotation $R_z\\\!\\\left(\\\frac{\\\pi}{2^j}\\\right)$ to his own qubit of the shared state $|t_j\\\rangle$.
- Every player applies a Hadamard gate $H$ to his qubit.
- Every player measures his qubit in the computational basis.
- Every player broadcasts his measurement outcome.
- Let $k_j$ denote the total number of broadcast outcomes equal to $1$.
- If $k_j$ is odd, the players conclude that a collision has occurred and terminate the protocol.
- Final decision
- If there exists at least one round $j$ such that $k_j$ is odd, output: collision detected.
- If $k_j$ is even for every round $0 \\\leq j \\\leq \\\lceil \\\log n \\\rceil,$
output: exactly one player wants to send.
Experimental Implementations
No experimental implementation was reported in the original proposal. The protocol is introduced as a theoretical primitive for anonymous quantum networks based on shared multipartite entanglement and broadcast communication.
Further Information
No content has been added to this section, yet!
References
- M. Christandl and S. Wehner. Quantum Anonymous Transmissions. In ASIACRYPT 2005.
- M. Waidner and B. Pfitzmann. Unconditional sender and recipient untraceability in spite of active attacks – some remarks. Technical Report, Universität Karlsruhe, 1989.
- 2026-04-15 at 16:04 by Mina Doosti
implements Anonymous Transmission
Introduction
This protocol [1] is a quantum primitive for anonymous networks that allows a group of $n$ players to determine whether more than one player wishes to send at the same time. In other words, it detects whether a collision has occurred among potential senders, while preserving sender anonymity.
The protocol is designed as a subroutine for anonymous communication. Before attempting an anonymous transmission, the players run collision detection to ensure that there is either exactly one sender or more than one. If a collision is detected, the transmission attempt is aborted or postponed.
A notable feature of this protocol is that it is traceless: after the protocol ends, the public transcript does not reveal which players attempted to send. This distinguishes it from earlier classical collision-detection approaches used in anonymous communication settings.
Related Paper(s)
Outline
A group of $n$ players shares several $n$-qubit GHZ states of the form $|\\\Psi\\\rangle = (|0\\\rangle^{\\\otimes n} + |1\\\rangle^{\\\otimes n})/\\\sqrt{2}$. The goal is to determine whether exactly one player wants to send, or whether multiple players want to send simultaneously.
The protocol proceeds in $\\\lceil \\\log n \\\rceil + 1$ rounds. In each round, a differently rotated GHZ state is used. Any player who wishes to send applies a phase rotation to his share of that state. Then all players apply Hadamard gates, measure in the computational basis, and broadcast their outcomes.
By checking the parity of the total number of measurement outcomes equal to $1$, the players can detect whether a collision has occurred. If the parity is odd in any round, then more than one player wanted to send. If the parity is even in every round, then exactly one player wanted to send.
The protocol is intended for the honest-but-curious setting for this subroutine: it correctly detects collisions provided that no user actively disrupts the protocol.
Assumptions
- There are $n$ players in the network.
- The players share $\\\lceil \\\log n \\\rceil + 1$ copies of the $n$-qubit GHZ state $|\\\Psi\\\rangle = \\\frac{|0\\\rangle^{\\\otimes n} + |1\\\rangle^{\\\otimes n}}{\\\sqrt{2}}.$
- The players have access to a classical broadcast channel.
- A designated player, or the state-distribution process, can prepare the rotated versions of the GHZ states required by the protocol.
- The protocol assumes that players do not actively disrupt the collision-detection procedure. In particular, the correctness argument is given for the case where players follow the protocol honestly.
- The protocol is used as a subroutine before anonymous transmission, in order to determine whether there is exactly one sender.
Requirements
Network stage: multi-party anonymous communication network.
- Shared resource: $\\\lceil \\\log n \\\rceil + 1$ shared $n$-qubit GHZ states.
- Classical communication: one broadcast round per collision-detection round.
- Nodal capabilities:
- Application of single-qubit phase rotations,
- Application of Hadamard gates,
- Computational-basis measurement,
- Authenticated broadcast of classical outcomes.
Notation
- $n$: number of players.
- $V$: the set of players.
- $|\\\Psi\\\rangle$: the $n$-qubit GHZ state $|\\\Psi\\\rangle = \\\frac{|0\\\rangle^{\\\otimes n} + |1\\\rangle^{\\\otimes n}}{\\\sqrt{2}}.$
- $j$: the round index, where $0 \\\leq j \\\leq \\\lceil \\\log n \\\rceil.$
- $R_z(\\\theta)$: the single-qubit phase rotation
$$ R_z(\\\theta) = \\\left( \\\begin{array}{cc} 1 & 0 \\\\\\\\\ 0 & e^{i\\\theta} \\\end{array} \\\right) $$
up to an irrelevant global phase convention. - $U_j$: the initial rotation used to prepare the $j$-th resource state $U_j = R_z\\\!\\\left(-\\\frac{\\\pi}{2^j}\\\right) \\\otimes I^{\\\otimes (n-1)}$.
- $|t_j\\\rangle$: the rotated GHZ state used in round $j$, that is $|t_j\\\rangle = U_j |\\\Psi\\\rangle.$
- $k$: the number of players who want to send.
- $k_j$: the total number of measurement outcomes equal to $1$ in round $j$.
Properties
- Total number of rounds: $\\\lceil \\\log n \\\rceil + 1$.
- The protocol detects whether the number of interested senders is greater than $1$.
- Correctness:
- Correctness for the no-collision case: if exactly one player wants to send, then in every round the combined effect of the sender’s rotation cancels the initial offset in the shared state, and the protocol does not report a collision.
- Correctness for the collision case: if $k \\\geq 2$ players want to send, then there exists a round $j$ such that
$$
k = 2^j m + 1
$$
for some odd integer $m$. In that round, the accumulated phase produces the state
$$
\\\frac{|0\\\rangle^{\\\otimes n} – |1\\\rangle^{\\\otimes n}}{\\\sqrt{2}}
$$
up to a global phase, which is detected by an odd parity of the measurement outcomes.
- Correctness for the no-collision case: if exactly one player wants to send, then in every round the combined effect of the sender’s rotation cancels the initial offset in the shared state, and the protocol does not report a collision.
- Collision-detection guarantee: using $\\\lceil \\\log n \\\rceil + 1$ rounds, the protocol detects every case with
$$
2 \\\leq k \\\leq n.
$$ -
Anonymity: the public information consists only of the broadcast measurement outcomes. These outcomes reveal whether a collision occurred, but not which players attempted to send.
-
Tracelessness: after the protocol ends, the communication transcript and later inspection of local randomness do not identify the players who expressed interest in sending.
-
Limitation: the protocol is not designed to handle active disruptors in this form. A malicious player can disturb the shared entangled resource and force failure.
Technical Description
Input: each player privately decides whether he wants to send.
Output: the players learn whether there is a collision, i.e. whether more than one player wants to send.- Resource preparation
- The players share $\\\lceil \\\log n \\\rceil + 1$ copies of the GHZ state
$$
|\\\Psi\\\rangle = \\\frac{|0\\\rangle^{\\\otimes n} + |1\\\rangle^{\\\otimes n}}{\\\sqrt{2}}.
$$ - For each round $j$ with $0 \\\leq j \\\leq \\\lceil \\\log n \\\rceil,$
a designated player prepares the rotated state $|t_j\\\rangle = U_j |\\\Psi\\\rangle,$
where
$$
U_j = R_z\\\!\\\left(-\\\frac{\\\pi}{2^j}\\\right) \\\otimes I^{\\\otimes (n-1)}.
$$
- The players share $\\\lceil \\\log n \\\rceil + 1$ copies of the GHZ state
- Round $j$: For each round $j$ with $0 \\\leq j \\\leq \\\lceil \\\log n \\\rceil,$, all players perform the following steps:
- Every player who wants to send applies the rotation $R_z\\\!\\\left(\\\frac{\\\pi}{2^j}\\\right)$ to his own qubit of the shared state $|t_j\\\rangle$.
- Every player applies a Hadamard gate $H$ to his qubit.
- Every player measures his qubit in the computational basis.
- Every player broadcasts his measurement outcome.
- Let $k_j$ denote the total number of broadcast outcomes equal to $1$.
- If $k_j$ is odd, the players conclude that a collision has occurred and terminate the protocol.
- Final decision
- If there exists at least one round $j$ such that $k_j$ is odd, output: collision detected.
- If $k_j$ is even for every round $0 \\\leq j \\\leq \\\lceil \\\log n \\\rceil,$
output: exactly one player wants to send.
Experimental Implementations
No experimental implementation was reported in the original proposal. The protocol is introduced as a theoretical primitive for anonymous quantum networks based on shared multipartite entanglement and broadcast communication.
Further Information
No content has been added to this section, yet!
References
- M. Christandl and S. Wehner. Quantum Anonymous Transmissions. In ASIACRYPT 2005.
- M. Waidner and B. Pfitzmann. Unconditional sender and recipient untraceability in spite of active attacks – some remarks. Technical Report, Universität Karlsruhe, 1989.