Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0107127 · Physical Review Letters

Quantum Solution to the Byzantine Agreement Problem

Matthias Fitzi, Nicolas Gisin, Ueli M. Maurer

Published Nov 1, 2001• 164 citations
arXivHTMLPDF

Abstract

We present a solution to an old problem in distributed computing. In its simplest form, a sender has to broadcast some information to two receivers, but they have access only to pairwise communication channels. Unlike quantum key distribution, here the goal is not secrecy but agreement, and the adversary (one of the receivers or the sender himself) is not outside but inside the game. Using only classical channels this problem is provably impossible. The solution uses pairwise quantum channels and entangled qutrits.

DOI
10.1103/physrevlett.87.217901

Related papers

Quantum Byzantine Agreement with a Single Qutrit

Mohamed Bourennane, Adán Cabello, Marek Żukowski

Quantum mechanics provides several methods to generate and securely distribute private lists of numbers suitably correlated to solve the Three Byzantine Generals Problem. So far, these methods are based on three-qutrit singlet states, four-qubit entangled states, and three or two pairwise quantum key distribution channels. Here we show that the problem can be solved using a single qutrit. This scheme presents some advantages over previous schemes, and emphasizes the specific role of qutrits in basic quantum information processing.

arXiv:1001.1947•Jan 12, 2010•6 citations

Quantum Byzantine Multiple Access Channels

Minglai Cai, Christian Deppe

In communication theory, attacks like eavesdropping or jamming are typically assumed to occur at the channel level, while communication parties are expected to follow established protocols. But what happens if one of the parties turns malicious? In this work, we investigate a compelling scenario: a multiple-access channel with two transmitters and one receiver, where one transmitter deviates from the protocol and acts dishonestly. To address this challenge, we introduce the Byzantine multiple-access classical-quantum channel and derive an achievable communication rate for this adversarial setting.

arXiv:2502.12047•Feb 17, 2025•0 citations

Byzantine agreement with two quantum-key-distribution setups

S. Iblisdir, Nicolas Gisin

It is pointed out that two separated quantum channels and three classical authenticated channels are sufficient resources to achieve detectable broadcast.

arXiv:quant-ph/0405167•Physical Review A•Sep 29, 2004•22 citations

Quantum Byzantine agreement via Hardy correlations and entanglement swapping

Ramij Rahaman, Marcin Wieśniak, Marek Żukowski

We present a device-independent quantum scheme for the Byzantine generals problem. The protocol is for three parties. Party $C$ is to send two identical one-bit messages to parties $A$ and $B$. The receivers $A$ and $B$ may exchange two one-bit messages informing the other party on the message received from $C$. A bit-flipping error in one of the transmissions does not allow the receiving parties to establish what was the message of $C$. Our quantum protocol is based on Hardy's argument, which uses a set of conditions impossible for classical systems, but satisfied by predictions for a unique two-qubit state. The scheme has the feature that if the messages of the Byzantine protocol are readable (that is give an unambiguous bit value for any of the receivers), then any error by $C$ (cheating by one of the commanding generals) is impossible. $A$ and $B$ do not have to exchange protocol messages to be sure of this.

arXiv:1408.1540•Physical Review A•Oct 1, 2015•19 citations

Secure Distributed Systems Using Quantum Communication Channels

Clara Bianchi

Distributed systems -- spanning cloud computing, edge networks, and federated databases -- rely on classical cryptographic channels whose security rests on computational hardness assumptions increasingly threatened by advances in quantum computing. Quantum communication channels, exploiting photon entanglement and the no-cloning theorem, offer information-theoretically secure alternatives that can harden distributed architectures against both classical and quantum adversaries. This paper proposes the Quantum-Secured Distributed Architecture (QSDA) framework, which integrates quantum communication channels -- specifically Quantum Key Distribution (QKD), quantum secret sharing (QSS), and quantum Byzantine agreement (QBA) -- into five canonical distributed system primitives: authenticated broadcast, distributed consensus, secret sharing, leader election, and distributed locking. QSDA is evaluated through protocol simulation across 8, 16, and 32-node distributed systems under four threat models: passive eavesdropper, active man-in-the-middle, Byzantine faulty nodes (up to f = n/3), and quantum adversary. Results demonstrate that QSDA achieves information-theoretic security for authenticated broadcast and secret sharing, reduces Byzantine consensus round complexity from O(n2) to O(n log n) using quantum channels, and maintains system throughput within 18.4% of classical baseline despite quantum channel overhead. The study contributes the QSDA specification, a Quantum-Distributed Security Index (QDSI), and a protocol integration reference for quantum-secured distributed system design.

Quantum Frontiers Journal•Jul 4, 2025•0 citations

Detectable byzantine agreement secure against faulty majorities

Matthias Fitzi, Daniel Gottesman, Martin Hirt +2 more

It is well-known that n players, connected only by pairwise secure channels, can achieve Byzantine agreement only if the number t of cheaters satisfies t < n/3, even with respect to computational security. However, for many applications it is sufficient to achieve detectable broadcast. With this primitive, broadcast is only guaranteed when all players are non-faulty ("honest"), but all non-faulty players always reach agreement on whether broadcast was achieved or not. We show that detectable broadcast can be achieved regardless of the number of faulty players (i.e., for all t < n). We give a protocol which is unconditionally secure, as well as two more efficient protocols which are secure with respect to computational assumptions, and the existence of quantum channels, respectively.These protocols allow for secure multi-party computation tolerating any t < n, assuming only pairwise authenticated channels. Moreover, they allow for the setup of public-key infrastructures that are consistent among all participants --- using neither a trusted party nor broadcast channels.Finally, we show that it is not even necessary for players to begin the protocol at the same time step. We give a "detectable Firing Squad" protocol which can be initiated by a single user at any time and such that either all honest players end up with synchronized clocks, or all honest players abort.

ACM Symposium on Principles of Distributed Computing (PODC)•Jul 21, 2002•73 citations
We present a solution to an old problem in distributed computing. In its simplest form, a sender has to broadcast some information to two receivers, but they have access only to pairwise communication channels. Unlike quantum key distribution, here the goal is not secrecy but agreement, and the adversary (one of the receivers or the sender himself) is not outside but inside the game. Using only classical channels this problem is provably impossible. The solution uses pairwise quantum channels and entangled qutrits.
Quantum mechanics provides several methods to generate and securely distribute private lists of numbers suitably correlated to solve the Three Byzantine Generals Problem. So far, these methods are based on three-qutrit singlet states, four-qubit entangled states, and three or two pairwise quantum key distribution channels. Here we show that the problem can be solved using a single qutrit. This scheme presents some advantages over previous schemes, and emphasizes the specific role of qutrits in basic quantum information processing.
In communication theory, attacks like eavesdropping or jamming are typically assumed to occur at the channel level, while communication parties are expected to follow established protocols. But what happens if one of the parties turns malicious? In this work, we investigate a compelling scenario: a multiple-access channel with two transmitters and one receiver, where one transmitter deviates from the protocol and acts dishonestly. To address this challenge, we introduce the Byzantine multiple-access classical-quantum channel and derive an achievable communication rate for this adversarial setting.
We present a device-independent quantum scheme for the Byzantine generals problem. The protocol is for three parties. Party CCC is to send two identical one-bit messages to parties AAA and BBB. The receivers AAA and BBB may exchange two one-bit messages informing the other party on the message received from CCC. A bit-flipping error in one of the transmissions does not allow the receiving parties to establish what was the message of CCC. Our quantum protocol is based on Hardy's argument, which uses a set of conditions impossible for classical systems, but satisfied by predictions for a unique two-qubit state. The scheme has the feature that if the messages of the Byzantine protocol are readable (that is give an unambiguous bit value for any of the receivers), then any error by CCC (cheating by one of the commanding generals) is impossible. AAA and BBB do not have to exchange protocol messages to be sure of this.
Distributed systems -- spanning cloud computing, edge networks, and federated databases -- rely on classical cryptographic channels whose security rests on computational hardness assumptions increasingly threatened by advances in quantum computing. Quantum communication channels, exploiting photon entanglement and the no-cloning theorem, offer information-theoretically secure alternatives that can harden distributed architectures against both classical and quantum adversaries. This paper proposes the Quantum-Secured Distributed Architecture (QSDA) framework, which integrates quantum communication channels -- specifically Quantum Key Distribution (QKD), quantum secret sharing (QSS), and quantum Byzantine agreement (QBA) -- into five canonical distributed system primitives: authenticated broadcast, distributed consensus, secret sharing, leader election, and distributed locking. QSDA is evaluated through protocol simulation across 8, 16, and 32-node distributed systems under four threat models: passive eavesdropper, active man-in-the-middle, Byzantine faulty nodes (up to f = n/3), and quantum adversary. Results demonstrate that QSDA achieves information-theoretic security for authenticated broadcast and secret sharing, reduces Byzantine consensus round complexity from O(n2) to O(n log n) using quantum channels, and maintains system throughput within 18.4% of classical baseline despite quantum channel overhead. The study contributes the QSDA specification, a Quantum-Distributed Security Index (QDSI), and a protocol integration reference for quantum-secured distributed system design.
It is well-known that n players, connected only by pairwise secure channels, can achieve Byzantine agreement only if the number t of cheaters satisfies t < n/3, even with respect to computational security. However, for many applications it is sufficient to achieve detectable broadcast. With this primitive, broadcast is only guaranteed when all players are non-faulty ("honest"), but all non-faulty players always reach agreement on whether broadcast was achieved or not. We show that detectable broadcast can be achieved regardless of the number of faulty players (i.e., for all t < n). We give a protocol which is unconditionally secure, as well as two more efficient protocols which are secure with respect to computational assumptions, and the existence of quantum channels, respectively.These protocols allow for secure multi-party computation tolerating any t < n, assuming only pairwise authenticated channels. Moreover, they allow for the setup of public-key infrastructures that are consistent among all participants --- using neither a trusted party nor broadcast channels.Finally, we show that it is not even necessary for players to begin the protocol at the same time step. We give a "detectable Firing Squad" protocol which can be initiated by a single user at any time and such that either all honest players end up with synchronized clocks, or all honest players abort.