Byzantine Generals in a Spy Game
Trojan Horse and countermeasures in reliable broadcast.
In continuation of the previous episodes, Byzantine Generals turn to Quantum and to Bayes.
🤓 Hi! I’m the geek on duty. If you wish, you can ignore my comments intended to deepen certain aspects related to quantum computing and cryptographic functionalities.
Let us remember that the quantum solutions to the Byzantine general agreement make it possible to unveil more traitors within the circle of the generals than in the classical solutions.
In the previous articles, the confrontations of lieutenants in a hunt for traitors take place on an equal footing. One of the advantages of a configuration with four generals rather than two is the emergence of a majority consensus. In a three-general configuration, if both lieutenants are cleared in the test, then the commanding general is cheating. But there’s no way of knowing who the target is. In the four-general configuration, however, after two confrontations with no traitor detection, the commanding general is considered the traitor. The target of the commander’s cheating is identified and that lieutenant can logically carry out the order sent to the other two. This amounts to an error correction.
This protocol differs from the original proposed by Fitzi et al. Their distribution-&-testing protocol does not involve sharing the results of a reserved part of the copies to establish a table of error incidences for all possible scenarios. In the original version, one lieutenant is tested by the other during the broadcast session.
Malicious attacks of different types can be envisaged. All those relating to secure classical channels are out of consideration here: assume perfect secrecy in a post-quantum cryptography world. The interest is in attacks on the quantum side of the protocol.
🤓 The quantum solutions to Byzantine general’s agreement have several similarities to quantum key distribution (QKD). As explained in this early 2022 review, an array of attacks can be imagined in optical QKD systems. These attacks can target either the encoder, the quantum channel or the decoder. The creation of backdoors in quantum communications via laser damage has already been described by Makarov et al. Other kinds of Trojan horse attacks on technical implementation and side leakage channels of information were described by Lucamarini et al. and by Molotkov for instance. However, QKD’s unconditional security can be assumed if a detailed list of requirements is met. These papers provide inspiration for the design of similar attacks in quantum solutions to the Byzantine General agreement.
Most attacks on the quantum system simply result in sabotage without further consequences. Indeed, there is a phase of entanglement check just after the qubit measurements and before the traitor hunt: a part of the results, drawn at random, is reserved for consistency verification. If this condition is not met, the protocol aborts.
Now suppose some lieutenants magically acquire the ability to evade lie detection. In the three-general configuration, such a lieutenant can abort the process at will: sabotage!
In the four-general configuration, this is impossible due to the majority consensus. But two treacherous lieutenants with the magical gift can persuade a loyal one to carry out the opposite of the order actually sent: putsch!
Sabotage and putsch are theoretically feasible and will be demonstrated here on quantum hardware. It will also be shown that well-calibrated quantum noise in the system can be an effective countermeasure.
An elementary toy model of Trojan horse attack suitable for simulation on hardware has been implemented. The code was written in Python, using the open-source quantum computing package Qiskit. The model was tested on a superconducting quantum computing system of IBM Q. The putsch version is illustrated in this article.
🤓 The code can be accessed in this GitHub notebook under Apache License 2.0.
Quantum Putsch
Note that from here the conspiracy and its actors are just as metaphorical as Lamport’s Byzantine army.
The Toy Model
An important source of inspiration was the Trojan horse attack in QKD described by Lucamarini et al.
Practical Security Bounds Against the Trojan-Horse Attack in Quantum Key Distribution,
M. Lucamarini, I. Choi, M. B. Ward, J. F. Dynes, Z. L. Yuan, and A. J. Shields, Phys. Rev. X 5, 031030.
DOI 10.1103/PhysRevX.5.031030, URL, Creative Commons Attribution 3.0 Licence
🤓 Contrarily to this QKD Trojan horse attack, the encoding is doctored in our demo model. Through leakage channels, the eavesdropper gets knowledge about the results of the measurements made by the “commanding general”.
On the seven-qubit superconducting quantum devices available currently in ibm-q/open/main, such as ibm-nairobi or ibm-oslo, the layout allows two ancillary qubits to increase the circuit fidelity thanks to a high-level transpilation. But in this case, an undercover agent can create leakage channels. Let’s call him Evin. The quantum circuit is doctored: two CNOT gates are inserted at the end. The control qubits of the CNOT gates are those destinated for the commanding general, and the target qubits are the ancillaries.
🤓 The highly entangled state is modified when leakage channels are added:
The Conspiracy
Let’s imagine the following example. Carol and Dave are hawks. They know Alice is reluctant to attack. They agree to get rid of Alice if she sends a retreat order and to put her rival, the pugnacious Eve, in charge. Evin measures the ancillary qubits and passes the results through a secret and secure classical channel to Eve.
The Rigged Traitor Hunt
Eve has a close copy of Alice’s confidential results thanks to Evin. In the phase following the distribution and measurement of the qubits, Carol and Dave learn which part of the results is for hunting and not for entanglement checking. Then, as soon as Alice sends the order to retreat, Carol and Dave know the certifying index list associated with this order. They should avoid using these indexes in exchanges with Bob during the traitor hunt. The conspirators create an index list of the same length valid for the opposite order. Carol and Dave will use this forged list in the hunt and pose as loyal lieutenants.
🤓 Note that from the check data, the conspirators can simulate their scheme beforehand to see if it has a chance of succeeding. They purposely construct an alternate table of incidences of error using Eve’s result list rather than Alice’s.
Let’s look at the output:
In the program output, when testing Dave, Bob observes an error rate of 33% for the original and 34% for the doctored circuit. When testing Carol, he observes 38% for the original and 34% for the doctored circuit. Here is the explanation:
The Putsch
From now on, Bob is convinced that Alice is a traitor. It only remains for the conspirators to win Bob over to their cause. Alice is deposed without being able to give any proof denouncing the scheme. Eve takes command of the operations and an onslaught is launched on the besieged city.
🤓 Alice could argue that the certifying index list used by Carol and David is inconsistent with her results and therefore does not come from her, but it will be her word against theirs.
For an external observer, this cannot be distinguished from a Byzantine reliable broadcast where no receiver is faulty. To interpret the metaphor, this amounts to a broadcasted value being flipped in all receivers despite a non-faulty server.
🤓 Here the allegory is deliberately dramatized, culminating in a full onslaught to emphasize its catastrophic consequences. In a real distributed system, the correct value broadcast by the server would simply be ignored.
Countermeasures
Now is the time to examine the possible way of escaping such conspiracies. Not only in our toy model, but possibly in other scenarios, in different types of quantum systems, and for different numbers of parties.
The wrong way would be to entrust the entanglement to a general. This one could easily modify the system and get close copies of any other’s results.
Prohibiting auxiliary qubits is a solution. But in the real world, spontaneous or created leakage channels could be exploited for malicious attacks anyway.
🤓 In their four-general protocol demonstrated experimentally on a photonic system, Gaertner et al. have already shown that an intercept-resend attack altering the entanglement can be revealed by further analysis of the acquired data. This finding helps to understand the following means of protection, even a different one, against the Trojan horse attack that concerns us here.
The protocol can be secured thanks to the presence of an adequate level of quantum noise in the original circuit. If an attack occurs, the noise will increase due to deeper circuits, more two-qubit gates, and additional qubit measurements. The fidelity would be lower than expected for the complete results of each general, and for the part of the results pooled for the entanglement check. The change will also increase the expected error incidences in the table used for Bayesian inference. The shift of the hypergeometric distributions previously described will appear.
🤓 In realistic environments, security is assured when noise is present under two conditions. First, the individual quantum gate and measurement errors in the system must be known, constant, and of adequate level. Second, the circuit must be optimized to ultimately allow sufficient distances between the two hypergeometric distributions for faithful vs. traitor in all scenarios. This way, a doctored circuit cannot be confused with the original circuit.
Conclusion:
Perhaps you feel right now somewhat far from a problem of quantum-assisted data validation in a distributed computing system. If you think in terms of server and receivers, however, such an attack has disturbing characteristics. In the three-general version, a receiver wishing to flip a bit may repeatedly interrupt the transmission until the server finally sends an unintended flipped one. In the four-general version, two receivers must conspire but they can manage to succeed in one attempt. If a quantum solution is used in blockchains, such a Trojan horse attack might at some point be used to validate an alternative ledger.
Despite its toy nature and its difficult feasibility as such in the real world of communications, this model shows that Trojan horse attacks altering the entanglement can be detected in relatively noisy systems.
This episode concludes this Quantum Byzantine Generals series.
I hope you enjoyed this mixture of ancient Greek Culture, today’s Geek Culture, and tomorrow’s quantum warfare.
I acknowledge the use of IBM Quantum services for the testing on hardware. The views expressed are those of the author, and do not reflect the official policy or position of IBM or the IBM Quantum team.
