This project aims to implement quantum key distribution (QKD) protocols to exchange cryptographic keys securely. Specifically, the BB84 and E91 protocols were implemented using the Qiskit Python library and quantum simulators to showcase how quantum communication can detect eavesdropping. We simulated noise and eavesdropping and applied methods such as key reconciliation and privacy amplification to enhance security.
Members:
- Alex Shariat Zadeh - [email protected]
- Anton Brömster - [email protected]
- Jonatan Tuvstedt - [email protected]
- Trang Nguyen - [email protected]
- Installation
- Usage
- Problem Description
- Background
- Deliverables
- Documentation of the Project
- Documentation of testing the project
- Discussion
- Contribution
- References
-
Clone the repository:
git clone https://github.com/Glassar/dd2394-Security-Project.git -
Make sure to have python3 and pip installed
-
Install dependencies:
pip install qiskit
pip install qiskit_aer
Run the test file bb84_test.py with python3 bb84_test.py
Run the test file e91_test.py with python3 e91_test.py
Quantum mechanics and quantum computing offer a new way of cryptographic key distribution that is fundamentally secure against undetected eavesdropping. This security stems from a fundamental principle of quantum mechanics: any measurement of a quantum state changes the state itself. In other words, if an eavesdropper intercepts and measures the quantum state before it reaches the intended recipient, the state will be altered, allowing both parties to detect the intrusion.
Using this quality, several QKD protocols have been developed to securely transmit cryptographic keys over open and insecure channels, with the assertion that any unauthorized access to the key will be revealed.
For this project, we have chosen to implement two QKD protocols, specifically the BB84 and E91 protocols. These implementations will be carried out using the Qiskit Python quantum programming library, with the quantum circuits executed on the Qiskit Aer simulator.
In addition to implementing the basic key distribution protocols, we also implemented eavesdropping detection mechanisms for both protocols. These mechanisms use statistical methods to identify deviations in the results between the two parties, indicating the presence of interference that would not occur under normal conditions.
Such interference arises either from noise, given that quantum computers are not foolproof and gate operations or measurements can produce incorrect values, or from an eavesdropper intercepting the key distribution and altering the transmitted quantum states. Therefore, if the detection protocol returns an interference level greater than our safety threshold, then we conclude that eavesdropping has occurred and subsequently discard the results.
Eavesdropping was integrated into both protocols, with an eavesdropper, referred to as Eve, intercepting and measuring a few of the transmissions while ensuring that some information is forwarded to Bob for measurement. However, due to the randomness in how the information is transmitted, which is undetectable, Eve cannot carry out this process perfectly, meaning that there will be interference that we can detect.
Key reconciliation and privacy amplification are crucial steps in QKD protocols as they help ensure that two parties can establish a secret key over an insecure channel. Due to the inherent noise in quantum processes, errors will inevitably occur resulting in Alice's and Bob's keys not being completely identical, even in the absence of eavesdropping. Therefore, to ensure that the final key is usable, these errors must be removed. To reconcile their keys, we implemented an error correction protocol known as the cascade protocol which corrects any remaining errors in Bob's key relative to Alice's key while revealing minimal information and maintaining a high probability of successfully reconciling the two keys.
However, since this process requires us to send information over an insecure channel, we conclude the key distribution process with privacy amplification. The concept of privacy amplification exploits the limited knowledge that the eavesdropper, Eve, has of the initial key which may have been acquired through either eavesdropping of the key distribution or the key reconciliation process. Privacy amplification is achieved by performing a simple has function on the key.
Quantum computing works by applying quantum gates to a system of qubits and subsequently evaluating the values of these qubits. Qubits are the quantum equivalent of a classical bit and can be represented as a two-dimensional complex vector. The absolute value of these complex numbers corresponds to the probability of measuring the qubit in the states 0 and 1, respectively.
For our protocols, we only used a few different quantum gates:
-
H (Hadamard) gates puts a qubit in superposition. When applying the Hadamard gate to a qubit, it transitions into a state of equal probability of measuring either 0 or 1. If a qubit is already in a state then it returns it to its classical state.
-
X (Pauli-X) gate is a NOT gate that flips the state of a qubit from |0⟩ to |1⟩ and vice versa.
-
S (Phase) and T (T-phase) gates rotate the complex vector, 90 degrees, and 45 degrees, respectively, in a way that doesn't directly affect the probability of measuring 0 or 1.
-
CX gate is a controlled-NOT gate, which flips the first qubit if and only if the second qubit is in the state |1⟩ (but if the second qubit only has a certain probability of evaluating to 1 then it only switches the first one with a certain probability).
A bell circuit (see Figure 1) is a simple two-qubit system that will evaluate with equal odds to either |00⟩ or |11⟩, but never |10⟩ or |01⟩ (if we ignore noise).
Figure 1: Quantum circuit for implementing the first Bell state.
We start with two qubits in the |0⟩ state. First, we apply a Hadamard (H) gate for the first qubit, putting it into a superposition with equal likelihoods to evaluate to either 0 or 1. Then we apply a CX gate to both of the qubits, where the first qubit controls the second. That is, if the first qubit evaluates to 1, then we will set the second qubit to 1. This will hold even if we separate the first qubit and the second one by, for example, sending one to Alice and one to Bob, meaning they now have a shared secret bit.
The quantum protocols used in this project require the following communication conditions: the quantum communication is done over a completely open and unsecured channel, and the later comparison of bases as well as key reconciliation is done over an open but authenticated classical channel.
The BB84 protocol was developed by Charles H. Bennett and Gilles Brassard in 1984 and it utilizes a single qubit system. In this protocol, Alice randomly selects a string of bits and a string of one of two bases: either the horizontal/vertical (0/1) or diagonal (+45°/-45°) states. She then transmits a photon for each bit with the corresponding polarization to Bob. Bob randomly chooses a base to measure each bit he receives. If he chose the same bases as Alice for a particular bit, then Bob would with 100% certainty measure the same value as Alice wrote (disregarding noise). However, if they have different bases then what Bob measures will be completely random.
Finally, Alice and Bob share their randomly generated bases and discard any bits where they had different bases, and the resulting string form their shared secret key.
The E91 protocol was created by Artur Ekert in 1991 and is slightly more complex than BB84. This method relies on a Bell circuit that generates a pair of entangled qubits—one of which is sent to Alice and the other to Bob. Both Alice and Bob generate a random series of bases (one for each bit sent), but now they select from three possible bases, which are different rotations of the qubits. In our example, Alice and Bob share only two of the three angles in common, but they could theoretically choose these bases randomly out of a selection.
Both Alice and Bob measure each bit they receive using one of the three bases of their choosing. Alice then flips her bit as if they have the same base, then Alice's bit is guaranteed to be the opposite of Bob's (disregarding noise), while if they have different bases then their measurements are a bit random.
Finally, Alice and Bob share their lists of bases and discard any bits where they don't share a base, and they now have two identical keys.
This repository includes implementations of two quantum key distribution protocols, E91 and BB84. The protocols are implemented in Python, using Qiskit and Qiskit Aer, and simulate the key exchange between two users (Alice and Bob), while also including noise models and eavesdropping. Additionally, the repository includes a key reconciliation technique, used to fix key inconsistencies, and also privacy amplification. The code for each protocol can be located within their corresponding folder bb84 and e91.
Within the bb84 folder, there are five python scripts:
- bb84.py - This file implements the BB84 protocol, which includes a key exchange between two parties - Alice and Bob. Due to this being the most "basic" version of BB84, it does not include any eavesdropping. However, it can include noise. This can be included when running the main file. Also, to run the
mainfunction, a variable object is required. An example of such object can be found within the test-file (namedconfig). - bb84_eaves.py - The structure of this file is quite similar to that of
bb84.py, with the difference being the inclusion of eavesdropping. That being said, themainfunction is ran the same way asbb84.py, with the difference being the inclusion of the parameterthreshold. - bb84_test.py - This is the test file, used to try the bb84-protocol. It includes a series of tests, each including different values (i.e. with/without noise and with/without eavesdropping). To run the test, run command
python3 ./bb84/bb84_test.pyin your terminal - noise.py - The noise file contains the noise protocol. It is defined as a function, called
noise_protocol, and is used to insert noise into the process of key exchange. - spot_checking.py - The spot-checking file includes the function
spot_checkingwhich calculates the number of incorrect bits out of a random sample of Bob's key.
Within the e91 folder, one should find one Python script, namely e91.py. Other than the key exchange, the file also gives the option to simulate an eavesdropper. To run the code, run the sync_bases_and_build_keys function. More information about the code will be presented under Documentation of the project.
Aside the two folders for the respective protocols, there exists another folder. This folder, called key_reconciliation, includes code that relates to key reconciliation and privacy amplification. Within said folder, one should find a file called key_reconciliation.py. More information about the code will be presented under Documentation of the project.
The BB84 QKD protocol with simulated eavesdropping, noise model and spot checking. It uses Qiskit for quantum circuit simulation.
- BB84 protocol
- Noise model
- Spot checking
bb84_protocol(vObject, use_noise=False): Implements the BB84 protocol
- Iterates through bits
- Performs key sifting (keeps bits where Alice and Bob's bases match)
- Returns Alice and Bob's sifted keys
quantumEavesDropping(aBit, aBase, eBase, use_noise=False): Simulates eavesdropping
- Creates a quantum circuit based on Alice's bit and bases
- Applies Eve's bases
- Measures the qubit
- Noise optional
quantumSend(aBit, aBase, bBase, eBase, use_noise=False): Simulates the quantum transmission
- Performs eavesdropping
- Resets the circuit
- Applies Bob's bases
- Measures the qubit
calc_risk(rate, threshold):
- Calculates the risk of eavesdropping based on the error rate and a given threshold.
main(vObject, threshold, use_noise=False): Main function
- Runs the BB84 protocol
- Performs spot checking
- Calculates eavesdropping risk
- Applies key reconciliation
noise_protocol(): Noise model for the quantum simulation
- Adds a depolarizing error (5% probability) to X and H gates
- Adds a readout error (5% probability of flipping the measurement result)
spot_checking(aKey, bKey, numberOfBits): Spot checking to estimate the error rate
- Randomly selects a sample of bits from the keys
- Compares the selected bits between Alice and Bob's keys
- Calculates the error rate
- Returns the error rate and the samples from both keys
-
Eavesdropping simulation: The implementation includes a simulation of an eavesdropper (Eve) attempting to intercept the quantum communication.
-
Noise modeling: Optional noise can be applied to simulate real-world hindrance in QKD.
-
Spot checking: A portion of the sifted key is sacrificed to estimate the error rate and detect potential eavesdropping.
-
Risk calculation: The implementation calculates the risk of eavesdropping based on the observed error rate.
The E91 QKD protocol with simulated eavesdropping, noise model, and spot checking. It uses Qiskit for quantum circuit simulation.
- E91 Protocol
- Key reconciliation and privacy amplification
noise_protocol(): Simulates noise by adding two types of noise.
- Depolarization error - adds a 1% probability of depolarizing error on X and H gates.
- Readout error - adds a readout error with a 5% probability of flipping the measurement result.
- Only applied if the
useNoiseis set toTrue.
send_qubit(alice_base, bobs_base, eve_present=False, eve_base="", eve_intercepts=0): Simulates sending and measuring a qubit between Alice, Bob and (optionally) Eve.
- Sets up a Bell state (entangled pair of qubits).
- Measures the spin projection of Alice's and Bob's qubits in the different bases.
- Returns a 3-bit string of Alice's and Bob's measurements.
- If Eve is present, she measures Bob's qubits using her bases.
def_measure_all_qubits(aliceBases, bobBases, eve_present = False, eveBases = [], eveInterceptions = []): Collects measurement results for all qubits
- Calls
send_qubit()for each qubit.- Returns a list of Alice's, Bob's, and (optionally) Eve's measurements.
sync_bases_and_build_keys(aliceBases, bobBases, eve_present = False, eveBases = [], eveInterceptions = []): Builds the shared key, computes the CHSH correlation and checks for eavesdropping.
- Calls
measure_all_qubits()to get the measurements.- Compares Alice's and Bob's measurement bases.
- Computes the CHSH correlation value.
- Calculate the number of mismatched bits if Eve is present.
- Prints the bases, the shared key, CHSH correlation, and mismatched bits (if Eve is present).
sync_bases_and_build_keys(): Main function
- Executes the E91 protocol with the appropriate parameters.
- Outputs the shared key, CHSH correlation value, and mismatched bits due to interference.
key_reconciliation(alice_key, bob_key, block_size=1, rounds=4): Corrects errors in the shared key.
- Calls
cascade_error_correction()to correct errors in Bob's keys.- Calls
privacy_amplification()to the corrected key to reduce any information an eavesdropper might have gained.- Returns the corrected version of Bob's key -
fixed_keyand a key after privacy amplification -final_key.
cascade_error_correction(alice_key, bob_key, initial_block_size=1, rounds=4): Implements the cascade protocol - an iterative error correction method.
- Iterates through multiple rounds, doubling the block size for each round.
- For each block, it compares parities and uses binary search to locate and correct errors.
- Corrects errors in previous rounds when a new error is found.
- Returns Bob's key.
parity(block): Calculates the parity of a block.
- Returns 0 if the sum is even, 1 otherwise.
binary_search_error(alice_block, bob_block): Performs binary search.
- Divides the block in half, checking the parity of the left block.
- If parity is found, check the left half, otherwise check the right half.
cascade_to_previous_blocks(alice_key, bob_key, error_index, min_block_size): Corrects errors in smaller blocks from previous rounds if error is found in later rounds.
- Starts with half the block size.
- Check parity for each block.
- Calls
binary_search_error()to locate and correct errors.
privacy_amplification(key): Hash function for reconciled key.
- Converts the key to a string using it as a seed.
- Applies the md-5 hash to produce a new key
- Converts the hash to binary string and returns it.
The following section will discuss the testing that we did on the respective protocols, and what result it yielded.
The file used for testing contains a total of five different test cases, each with different values.
- Test case 1: The first test case used the
bb84.pycode, and performed a key exchange without noise and eavesdropping. - Test case 2: The second test case also used the
bb84.pycode. However, this time, it includes noise. - Test case 3: The third test, which used the
bb84_eaves.py, includes eavesdropping (but no noise). - Test case 4: The fourth test is quite similar to test case 3, as it also executes the
bb84_eaves.pycode, but with the difference being that it includes noise, - Test case 5: The fifth test case is the same as test case 4, with the difference being the inclusion of key reconciliation.
As the test cases differed from each other, we were able to grasp how the respective variable conditions affected the key exchange. Also, as the configuration of the variable object stayed the same for all the test cases, it made it easier to evaluate and understand how the basic bb84 protocol operates, and how applying noise and eavesdropping affected the exchange. For the test cases, the configuration that showed the most promising result was the following:
nBits = 1056
sampleDivisor = 2
threshold = 0.25The file used for testing contains a total of five different test cases, each with different values.
- Test case 1: The first test case performs key distribution without noise and eavesdropping.
- Test case 2: The second test case performs key distribution with noise
- Test case 3: The third test case performs key distribution with eavesdropping intercepting 50% of bits, and without noise.
- Test case 4: The fourth test case performs key distribution with eavesdropping intercepting 100% of bits, and without noise.
- Test case 5: The fifth test case performs key distribution with eavesdropping intercepting 100% of bits and with noise.
An important thing to note is that the CHSH test has a higher variance than the lower nBits and as such we ran all our tests with nBits=1024. But this is also significantly slower.
The different test cases let us showcase both the ideal protocol without interference, as well as how real-world difficulties affect it, both separately and combined. And as all tests use the same input we can also observe how the CHSH test value steadily decreases with more and more interference. Note that even with fixed inputs our outputs are non-deterministic as the quantum process also is non-deterministic.
As is shown in the tests for both the BB84 and E91 protocols work to distribute a shared key between two parties using quantum mechanics. And while we do this in a quantum computing simulator, and just pretend to send data it still shows that this technology works even if the infrastructure might not be there.
The benefit of using quantum mechanics to distribute cryptographic keys is that you can physically guarantee that if someone is eavesdropping, then you can detect it. This is the big benefit of quantum key distribution as this ability to learn if someone is eavesdropping is unique to quantum mechanics thanks to the fact that making measurements on quantum states modifies said states.
So both BB84 and E91 has benefits and drawbacks. The main benefit of BB84 is its simplicity with it only utilising a few gates, meaning it would be cheaper and easier to set up the infrastructure for it. It can also use a larger share of the sent bits in its final key with Alice and Bob sharing bases 50% of the time. A drawback with BB84 is its need to use spot checking meaning it needs to sacrifice some of the bits that would otherwise have been used in the final key.
The main strength of E91 is its ability to utilize the bits not being used in the key to calculate if there has been interference. But this comes at the cost of being a much more complex protocol requiring more gates. And the fact that only 2/9 bits can be used in the key as that is the probability of Alice and Bob sharing bases.
There are however several drawbacks. First up is that quantum key distribution requires significant infrastructure that is not going to be in place. While one way of sending the quantum particles is as light through optical cables that are common, the infrastructure to place said particles in a specific quantum state and decode them is not. This will likely be what will hold back quantum key distribution the most as the technology for precise quantum control is expensive with today's most advanced quantum computers only having about a thousand qubits.
In addition to the technical limitations, there are also some more cryptographic limitations. The central one is the fact that while quantum mechanics can guarantee security it has no way of confirming authenticity. This is why we still need to rely on an authenticated classical channel to swap bases to calculate the final key. This means that you still require either a shared secret or classical channels authenticated with a public and private key, which is what quantum key distribution would ideally move away from. At the same time, quantum technology gets better enabling quantum key distribution, it also opens the way for Shor's algorithm can factor large integers effectively which can be used to crack RSA.
To improve efficiency, the work was split into two parts based on the two protocols. While Alex and Anton worked on BB84, Jonatan and Trang worked on E91.
- Key reconciliation in the BB84 and E91 protocol: Implemented method that makes keys match since it is uncertain if the keys are identical due to the noise or eavesdropping, reconciles the two keys to be the same, by comparing segments of their respective keys and correcting differences while revealing minimal information.
- Privacy amplification in BB84 and E91: Implemented using a hash function to hash keys to safeguard them from potential eavesdropping.
- Test cases: Implemented test cases for above
- Documentation: Wrote documentation about BB84 protocol and Key reconciliation and Privacy amplification
As mentioned previously, I worked on the BB84 protocol. But to be more specific, this is what I contributed:
- Implementation of the BB84 protocol: Updated the basic version of the protocol that was originally made by Jonatan. This mostly consisted of making a new output format and altering the structure of the program.
- Eavesdropping and noise simulation: Implemented features to simulate eavesdropping attempts and noise. This included changes in bb84.py and bb84_eaves.py.
- Test cases: Implemented test cases for verification of the BB84 protocol. This included cases where eavesdropping and noise weren't used, test cases where they were used separately, and a test case for when both were active.
- Documentation: Drafted the first version of the
README.mdpage. This included sections: problem statement, deliverables, and references. I also wrote on the later versions of the README.md but why the contribution was smaller (in comparison to the first draft).
- Set up the basics of the project environment: As I had worked with quantum computing Qiskit instructed the rest of the team on how to set it up.
- Made the first draft of the BB84 protocol: Set up the basics of the BB84 protocol to showcase for the rest of the group how this could work.
- Implementation of the E91 protocol: Worked with Trang on implementing the E91 protocol using pair-programming.
- Implementation of eavesdropping and CHSH correlation value: Worked with Trang on implementing a CHSH test and eavesdropping for the E91 protocol using pair programming.
- Adapted the key reconciliation and noise model code for E91: Fixed a few bugs with key reconciliation and tweaked the noise parameters.
- Test cases: Implemented the test cases for E91 to verify it.
- Documentation: Wrote the background section, an overview of the test cases for E91, and the discussion.
- Implementation of the E91 protocol: Implemented the E91 protocol with and without noise by pair-programming with Jonatan by checking the code and giving directions.
- Implementation of eavesdropping and CHSH correlation value: Implemented eavesdropping and the CHSH correlation value by pair-programming with Jonatan by checking the code and giving directions.
- Documentation: Structured the report, reviewed and reworked each section for the final version.