Once reserved to a select handful of academics, hobbyists and spies, cryptography today is the bedrock of the modern economy.
Encryption — the dependable custodian of our personal data — bestows an indispensable confidentiality and security to the transactions ingrained in our day-to-day routine: Every call, text, and email we send. Every online purchase we undertake. Every cash deposit or withdrawal we make.
Symmetric Key Encryption
The method of encryption native to the lion’ share of cryptosystems hinges on the process of encoding the plaintext (the unencrypted input) into ciphertext (the encoded output), and the use of a single key (k) shared between 2 or more users. Suppose Alice wishes to send a message (m) to Bob, protected from the eavesdropper Eve. First, an Exclusive Or (XOR) ⊕ operation is applied to the bits of the plaintext and shared key to convert the plaintext into ciphertext (c); encryption is thus defined as follows:
The ciphertext is then sent to Bob, and subsequently decrypted by applying a XOR operation to the ciphertext and shared key, delivering Alice’s original message; decryption is therefore defined as follows:
As such, even if Eve intercepted the ciphertext, she would not be able to decrypt the message without the key. This “one-time pad method” is diagrammatically illustrated below:
Diffie-Hellman Key Exchange
Needless to say, the success of symmetric encryption algorithms is contingent on the exchange of a shared private key over a public communications medium; the Diffie-Hellman key exchange protocol, employed to preclude intruder Eve from intercepting the key, principally entails Alice and Bob’s agreement to establish 2 public numbers: a generator (g) and a prime number (p). Alice subsequently chooses a random number (a), computes u by modulo p, and sends it to Bob, while Bob himself chooses a random number (b), computes v by modulo p, and sends it to Alice. Alice and Bob ultimately compute secret keys Sₘ and Sₙ (respectively) by the same modulo, which are just the same, shared secret key S. This algorithm is depicted below:
In this way, despite noticing the public set {g, u, v}, Eve would need to solve a discrete logarithm problem in order to acquire a or b (and thus compute S) — a problem considered inaccessible to contemporary classical computers.
Shor’s Algorithm
However, the advent and continued development of quantum computing presents a novel opportunity to leverage Shor’s algorithm in calculating discrete logarithms in polynomial time. The problem is therefore a component of the BQP (“Bounded error, Quantum, Polynomial time”) complexity class, with an error probability of at most 1/4 for all instances:
Shor’s algorithm involves calculating the smallest integer α such that gᵃ = x, where some element x of a cyclic group G = ⟨g⟩ is given. The problem can thus be cast as an abelian hidden subgroup problem (HSP) in the (additive) group ℤₙ × ℤₙ, so function f : ℤₙ × ℤₙ → G:
Starting from uniform superposition over ℤₙ × ℤₙ, the hiding function is first computed as follows:
Following measurement of the 3rd register, the quantum state’s symmetry can be exploited by performing a quantum Fourier transform (QFT) over ℤₙ × ℤₙ:
The following flowchart delineates the algorithm which is subsequently implemented — one which can be carried out for any cyclic group G so long as we have a unique representation of the group elements succeeding steps, and we are able to effectively compute products and high powers in G (where the latter can be done rapidly via repeated squaring):
Since the probability of success for each independent attempt is φ(N)/N = Ω(1/log log N), the procedure doesn’t need to be repeated too many times before an invertible ν is found, and the problem is thus solved.
E91 Protocol
Our project is therefore to develop a post-quantum key exchange protocol — that is, a method of securely distributing the secret key between two users. This task, referred to as quantum key distribution, can be accomplished be implementing the E91 protocol to replace Diffie-Hellman key exchange.
Proposed by Artur Ekert in 1991, the protocol uses Bell states (maximally entangled quantum states of two qubits) emitted by a common source via spontaneous parametric down-conversion (SPDC) — a nonlinear optical process in which photons spontaneously split into two entangled photons of lower energies; in accordance with the law of conservation of energy and the law of conservation of momentum, the resulting photon pair has combined energies and momenta equal to the energy and momentum of the original photon and crystal lattice. Moreover, as the index of refraction changes with frequency, only triplets of frequencies will be phase-matched, meaning energy and momentum conservation is simultaneous. This process is portrayed here:
The resulting pairs of ½-spin particles in a singlet state are distributed between Alice and Bob, who measure an observable particle chosen randomly and independently from others from a set of complementary attributes; the two then exchange the bases of their measurements, which can result in a spin state of either +1 (spin up) or −1 (spin down), over the public channel, dividing the particles up into two groups: those with according bases and those with disaccording bases. This operating principle is shown below:
As particles with according bases are anticorrelated (exact opposites in value), they determine the key. Assuming that Alice interprets H, A, and D states as 0, 1, and V (respectively), and Bob does the opposite, the following relationship demonstrates that the key must be identical:
Conversely, disaccording particles can be used to test if Eve listens to the qubits on the quantum channel. Since they don’t participate in the composition of the key, Alice and Bob exchange these particles openly over the public channel, investigating whether the following equation is fulfilled:
If so, the presence of an entangled state indicates the legitimacy of the key; if not, Eve may have altered some of the particles, and the key is thus not secure.
Delineated as theoretically effective, this project (Qrypt) simulates the E91 quantum key distribution protocol with the goal of achieving quantum-safe key exchange. If successful in practice, Qrypt-esque cryptosystems seem likely to play a critical role in securing the future of digital communications. Let’s get building!
Special Thanks
This project is inspired by a Qiskit tutorial, to which I’m grateful for providing the code used and informing much of the corresponding theory.
Singlet States
The first component of the program involves Charlie, the owner of the singlet state preparation device, creating N entangled states |ψₛ⟩ and sending qubits A to Alice and qubits B to Bob via the quantum channel, as illustrated below:
To run the simulation, we define a quantum register (“qr”) with 2 qubits and a classical register (“cr”) with 4 classical bits, as shown here:
We subsequently assign qr[0] and cr[0] to Alice, qr[1] and cr[1] to Bob, and finally cr[2] and cr[3] to Eve; while Alice and Bob use their classical bits to store their measurement results, Eve uses her 2 bits to store measurement results of Alice and Bob’s qubits. After entangling qr[0] and qr[1] via creation of a singlet state, Charlie sends the appropriate qubits to Alice and Bob:
Measurement
In order for Alice and Bob to measure observable, randomly selected particles, we must define the spin projection observables they will use:
Furthermore, for them to perform these measurements in practice, the standard basis Z must have rotational capability. Accordingly, we define the notation of the measurements which Alice and Bob might take, with blocks on the left side representing detectors for X, W, Z, and V observables:
After defining the exact number N of singlet states Charlie prepares (500), we must define strings b and b′, the strings enabling Alice and Bob to choose the directions onto which they will measure the spin projections of their qubits.
We can now combine Charlie’s state preparation device and Alice’s and Bob’s detectors into single circuit, resulting in the creation of 500 (our assigned value for numberOfSinglets) circuits similar to the one rendered here:
Result Compilation
By executing all 500 circuits with a single command, we can model every individual act of singlet state creation, qubit distribution among participants, and measurement of spin projection onto the chosen direction. The following histogram depicts the output (0011) given by execution of the first circuit:
Since the secret key generation process has been modeled without the presence of an eavesdropper, classical bits cr[2] and cr[3] are always 0 (the first two digits); conversely, classical bits cr[0] and cr[1], used to store the participants’ measurement results, must be 1. Notably, the consequent output 0011 is the Python dictionary, in which the keys represent the obtained results, while the values correspond to the counts.
The process by which Alice and Bob record the results of their measurements (as bits of the strings a and a′) can be stimulated by using Python’s regular expressions module re. This foremost entails compiling search patterns, which allow us to find particular results in the outputs, and therefore fill the strings a and a′ with the results of the participants’ measurements:
Base Reveal
In this stage, the participants compare their strings b and b′ via the public classical channel. If Alice and Bob measure the spin projections of their qubits of the i-th singlet onto the same direction, then Alice records the result aᵢ as the bit of the string k, while Bob records the result −aᵢ as the bit of the string k′. The results of the participants’ measurements thus should be perfectly anticorrelated, since the expectation value of the following observable in the singlet state is given by:
In order to verify the absence of mismatches in the keys, we can compare the bits of strings k and k′, as demonstrated below:
Length of the key: 112
Number of mismatching bits: 0As anticipated, no mismatches exist in the secret key of length 112 bits. In any case, since the strings k and k′ are secret, Alice and Bob can’t have any knowledge about potential mismatches in the bits of their keys. In order to ascertain the number of errors, they can perform a random sampling test; this entails Alice’s random selection of 𝛿 bits of her secret key, communication to Bob regarding which she ended up choosing, and the pair’s comparison of the values of these check bits. For large enough values of 𝛿, the number of errors in the check bits will approximate the number of errors in the remaining bits, firmly indicating the overall magnitude of error.
CHSH Correlation Value Test
In the domain of classical physics, it is impossible to create a correlation inherent in the singlet state |Ψₛ⟩. Indeed, supposing Alice and Bob’s choice of basis entail A = Z, A′ = X and B = W, B′=V, where:
Then by measuring the observables X, Z for qubit A and observables W = (Z + X)/√2, V = (Z − X)/√2 for qubit B, the following expectation values can be obtained, facilitating construction of the Clauser-Horne-Shimony-Holt (CHSH) correlation value:
In this particular instance, Alice and Bob seek to confirm that there was no interference in their communication session by calculating the CHSH correlation value using the results they obtained subsequent to measurements of spin projections onto these directions:
This is equivalent to the measurement of observables X ⭙ W, X ⭙ V, Z ⭙ W, and Z ⭙ V. Accordingly, as outlined by the Born-von Neumann statistical postulate, the expectation value of observable E = Σⱼ eⱼ|eⱼ⟩⟨eⱼ|in the state|Ψ⟩ is given by the following expression, where |eⱼ⟩ is the eigenvector of E with corresponding eigenvalue eⱼ, and (P subscript Ψ) represents the probability of obtaining the result eⱼ after measuring the observable E in the state |Ψ⟩:
Similarly, the joint measurement of the observables A and B is given by:
Interestingly, if A and B are the spin projection observables, then the corresponding eigenvalues aⱼ, bₖ = ±1, yielding this corollary:
The probabilities P (on the right side) can thus be calculated as follows, where the numerator is the number of results aⱼ, bₖ, obtained after measuring the observable A ⭙ B, while the denominator quantifies the total number of measurements of the observable A ⭙ B:
Indeed, since Alice and Bob have already revealed their strings b and b′, and thereby information regarding the measurements they performed and the results they obtained, the participants can calculate the corresponding expectation values, and CHSH correlation value, as originally defined. First, we define function chsh_corr, defining the following lists with the counts of measurement results to represent the number of (−1, −1), (−1, 1), (1, −1) and (1, 1) results respectively:
Next, we consider the spins of the qubits of the i-th singlet being projected in all 4 possible directions, iterating our observables counts according to the measurement results obtained:
Finally, we sum the number of results obtained from measurements in each basis and calculate the expectation values of the X ⭙ W, X ⭙ V, Z ⭙ W, and Z ⭙ V observables, before ascertaining the CHSH correlation value:
CHSH correlation value: -2.612In the absence of external interference in the participants’ communication session, the CHSH correlation value is approximately 92% of−2√2; this high proximity attests to the maintained confidentiality of the secret key.
Eavesdropping Simulation
Having previously simulated the E91 quantum key distribution protocol without the presence of an eavesdropper, it is essential to validate cases in which some third party attempts to interfere with the participants’ communication session and obtain a secret key. Indeed, Eve can leverage intercept-resend attacks, in which she intercepts one or both of the entangled qubits prepared by Charlie, measures their spin projections, and prepares new qubits dependent on the retrieved results (|01⟩ or |10⟩), and ultimately sends them to Alice and Bob. This process is schematically represented below:
Like Alice and Bob, Eve must select the directions onto which she will measure the spin projections of the qubits. In our simulation, the eavesdropper randomly chooses one of the observables W ⭙ W or Z ⭙ Z to measure. After preparing the circuits for Eve’s measurements, we define list eveMeasurementChoices, in which the first and second elements of each row represent Eve’s measurement of Alice’s and Bob’s qubits (respectively); we subsequently assign a 50% probability to each of our measurement scenarios:
As administered in the eavesdropper-free simulation, we now create the circuits with the singlet states and detectors of Alice, Bob, and Eve, and execute all 500 prepared, similar circuits on the simulator. The following histogram depicts the output (0100) given by execution of the first circuit, indicating the directions onto which Alice, Bob, and Eve measured the spin projections, with the two digits on the left (01) corresponding to the bits cr[2] and cr[3] used by Eve to store her measurement results:
In order to extract Eve’s results in particular from the outputs, we compile new search patterns and define eveResults, a list identical in structure to eveMeasurementChoices. By extracting a key from the dictionary and transforming it to a string (as seen previously), Alice, Bob, and Eve are able to record the results of their measurements, enabling us to isolate Eve’s specific recordings.
Next, the trio create secret keys using the results obtained after measuring the observables W ⭙ W or Z ⭙ Z ; this is accomplished by comparing Alice’s and Bob’s key strings a and a′ with measurement choices b and b′:
By comparing the lists aliceKey, bobKey, and eveKeys, we are able to calculate the number of mismatching bits in the participants’ keys:
First, a simple rearrangement of the key lengths and Eve-and-participant mismatches grants data regarding the percentage of keys known by Eve:
Eve's knowledge of Alice's key: 94.64 %
Eve's knowledge of Bob's key: 91.96 %Moreover, the CHSH inequality test yields the following result:
CHSH correlation value: -1.821Representing just ~ 64% of our desired value of −2√2, the CHSH correlation value signals to Alice and Bob that the secret key has been compromised. Additionally, as Eve increasingly interferes in the communication session, not only does the extent of her knowledge about the secret keys increase, but the deviation of the CHSH correlation value from −2√2 additionally grows.
Perhaps most importantly, the string of abKeyMismatches denotes the number of mismatching bits: 11, in this particular simulation, indicating instances of successful intervention (barring the possibility of noise having been introduced); after Eve measures the qubits of the singlet state |Ψₛ⟩, she randomly obtains the results −1, 1 or 1, −1. Depending on the outcome, Eve prepares the state |φ₁⟩ = |01⟩ or |φ₂⟩ =|10⟩ — a task automatically achieved by a measurement in the basis in our particular simulation — and sends its qubits to Alice and Bob. Upon measuring the observable W ⭙ W, the participants obtain any combination of results with probability Pφₙ(aᵢ, bⱼ).
Cascade Information Reconciliation
In order to correct the (11) mismatches in the secret keys, Alice and Bob can simply use classical error reconciliation algorithms. Chief among these is the Cascade information reconciliation protocol, which facilitates the detection and removal of discrepancies in the participants’ secret keys, connected through a public noiseless channel.
A single Cascade run consists of multiple iterations (otherwise referred to as “passes”). Suppose we describe a version of the Cascade protocol which uses 4 iterations. Since each iteration corrects some of the bit errors in the key, it is very probable (but not guaranteed) that all bit errors will have been corrected by the end of the final iteration. This schematic summarizes the Cascade protocol’s application to a 16-bit key with 6 mismatches (representing a simplification of our scenario involving a 112-bit key with 11 mismatches):
Within each iteration (except the first), Bob first shuffles the mismatched key, breaking the now-shuffled key up into blocks. By visiting every block, Bob is able to determine each block’s error parity. Should the error parity be even, Bob does nothing; if the error parity is odd, however, Bob runs a binary algorithm to correct exactly one bit error. Although the blocks now all have an even error parity at the end of this iteration, the possibility of each block having a multiple of 2 errors remains. Through a combination of reshuffling in later iterations and the so-called cascading effect, there is a very high probability of finding and correcting any potential masked errors.
Privacy Amplification
The second classical post-processing step — privacy amplification (PA)— attempts to mitigate and compensate for the information leakage in the information reconciliation step by introducing additional layer of randomness at the cost of reducing effective key size. Accordingly, the procedure allows Alice and Bob to distil a secure final key Y from a partially secure bit string. The implementation thereof is premised on the Leftover Hash Lemma, which states that the output of a two-universal hash function applied to an input with sufficiently high entropy is almost uniformly random, facilitating the universal composable security of the final key.
Both participants start with identical, random n-bit binary strings X and X‵, generated by the Cascade information reconciliation module, while Eve holds a quantum system E relative to X. Alice and Bob wish to publicly select a random compression function g : {0, 1}ⁿ → {0, 1}ʳ from a universal₂ hash function family G, before compressing the strings X and X‵ to generate the final key Y and Y‵ respectively, where Y = g(X) and Y‵ = g(X‵). The diagram below summarizes the full PA procedure of procuring secure final keys:
Closing Thoughts
Quantum computing can be viewed as a double-edged sword in relation to the domain of cryptography. On one hand, a quantum implementation of Shor’s algorithm presents an exceptional opportunity to calculate discrete logarithms in polynomial time, and therefore render futile the Diffie-Hellman key exchange protocol at the heart of symmetric key encryption.
However, by exploiting quantum mechanical properties to perform cryptographic tasks, post-quantum cryptosystems can securely distribute a secret key between two users. Qrypt achieves this by implementing the E91 quantum key distribution protocol, in which successfully technician Charlie securely transmits a secret key between the cryptographic couple Alice and Bob, almost entirely shielded from eavesdropper Eve. Furthermore, this process is firmly fail-safed with a Clauser-Horne-Shimony-Holt correlation value test, wherein the proximity of the CHSH from −2√2 indicates the confidentiality of the secret key; in our tests, the CHSH represented 92% of −2√2 in the absence of an external intervention in the participants’ communication session, and just 64% during the eavesdropping simulation.
Subsequent classical post-processing, consisting of a Cascade information reconciliation module and a privacy amplification step, is ultimately utilized to facilitate the detection and removal of 11 discrepancies in the participants’ 112-bit secret keys, connected through a public noiseless channel.
Fast approaching the inevitable dusk of the classical cryptographic era and with the global quantum cryptography market growing at a CAGR of 30.7%, post-quantum cryptosystems such as Qrypt will play an invaluable role in ensuring that we can continue communicating over entrusted mediums and networks securely and confidentially.
Special thanks once again to the team at IBM’s Qiskit for their code and informative tutorial!
