Want to know how quantum computers really work? And why they can crack our best encryption systems? And how we might combat this? In this post, which is from a paper I wrote for a cybersecurity class where I went a bit above and beyond the assignment, I will go over these things. This post is long, but if you are interested in this, you might find it rewarding.

The paper this is copied from is here: https://authortomharper.com/wp-content/uploads/2023/01/Thomas-Harper-Project-IAAS221.pdf

The PDF version of this article contains the three appendixes (on quantum gates, mathematical background on algebraic structures such as rings, and quantum computer hardware and how it works) and two glossaries (one on notation and one on definitions) that will be referenced throughout this post, so if you would like more, then click the above link. Also, the PDF in the above link looks nicer, so it might be worthwhile reading that instead of this post, but if you’re the type that doesn’t like clicking links then this post is here for you.

I’ve copied the full reference section to the bottom of this post in case you’re interested in further reading.

Also, let me know in the comments if there are any formatting issues on this post. I copy-pasted from the PDF file and some of the subscripts and superscripts may have screwed up (I think I fixed them all, but I may have missed some).

First a bit of levity (and actually a decent introduction to how quantum computers actually work):

Now onto the main event.

Abstract

Encryption is necessary to ensure the security of online communications. Many different methods of encryption are available. The Rivest–Shamir–Adleman (RSA) cryptosystem is a commonly used public-key cryptosystem that uses prime factorization with large numbers. This is known as a one-way function (OWF), since it is much easier to multiply two very large prime numbers than to factor the product of those numbers using conventional computers. Quantum computers will be able to perform the factoring much faster than conventional computers, thereby making the RSA cryptosystem insecure. An algorithm, known as Shor’s algorithm, has already been discovered that will be able to crack RSA encryption once quantum computing hardware is sufficiently developed. It is therefore important to formulate methods of post-quantum cryptography (PQC) to ensure the security of RSA encryption before quantum computers become widely operational. Since 2016 the National Institute of Standards and Technology (NIST) has been running a competition in which teams attempt to formulate PQC systems. As of 2022, there are four contenders remaining. All four use some form of lattice-based cryptography, which is thought to be safe even from quantum computers. No known conventional nor quantum algorithm yet exists that can crack lattice-based cryptosystems in less than polynomial time, making them NP-hard even for non-deterministic computers. As such, lattice-based cryptography is a good candidate for PQC.
Keywords: modulus, RSA cryptosystem, qubit, Shor’s algorithm, post-quantum cryptography, lattice-based cryptography

Cryptography

For as long as humans had need of information security, they have used cryptography (alternatively, cryptology). The threat posed by those who might exploit information, such as in politics, diplomacy, or war, necessitated various methods of concealing that information. The ancient Greeks, for instance, are thought to have used what is called a scytale, which is a ribbon containing letters that can wrap helically around an object of a particular diameter (Djekic, 2013). When wrapped around the object, the letters align so as to formulate words.

Later inventions include substitution cyphers, such as the one purportedly used by Julius Caesar (hence the moniker Caesar cypher) that rotates the letters by a certain amount around the alphabet (Luciano, 1987). In such a scheme, the sender and receiver would know how much the letters are rotated and could therefore quickly decipher the message. The rotation measure, then, would be the secret key shared symmetrically between the sender and receiver.

A Caesar cypher would not be terribly difficult for an eavesdropper to crack, if they knew about how the cypher works. Other forms of substitution cypher can be used, which do not simply rotate around the alphabet, but make rotations of rotations or more randomly substitute each letter, thereby making a brute force approach to cracking it much more difficult. This is where modern cryptography, invented by 8^th and 9^th century Arab scholars, took off (Khan D. , 1996; Singh, 1999). For instance, the frequency analysis of Al-Kindi (Alkindus) in his ca. 850 C.E. treatise Deciphering Cryptographic Messages examined a message for how often certain letters show up and then compared that to how often letters show up in natural writing, thereby giving a good estimate of the substitution scheme being used (Al-Kadit, 1992; Al-Tayeb, 2003).

As cryptography grows in sophistication, so do techniques for breaking the cryptosystem. This was never clearer than during World War II, when both sides, particularly the Allies, poured a great deal of effort in breaking the cryptosystems of enemy communications. The work in Bletchley Park is renowned in practically mythological proportions among cryptanalysts and computer scientists, not only for how much determination was put into cracking the German Lorenz and Enigma codes (Turing, 1942), and the security measures employed, dubbed Ultra (Hinsley, 1993), to ensure the enemy did not suspect they were being eavesdropped upon, but also as the impetus for the invention of modern computers. Alan Turing, the father of modern computers, worked at Bletchley Park, and his work there motivated the invention of the lauded Turing machine, the template for modern computer programs (Turing, 1986; Turing, 2004).

The first Data Encryption Standard (DES) for cryptography using computers was put forth by IBM in the 1970’s and accepted by NIST in 1977 (NIST, 1977). It has since been superseded multiple times (NIST, 1988; NIST, 1993; NIST, 1999) and then by Advanced Encryption Standard (AES) (Nechvatal, 2001; NIST, 2001). At the same time as the first DES, the Diffie-Hellman key exchange system and RSA cryptosystem came out in 1976 and 1977 respectively (Diffie & Hellman, 1976; Rivest, 1978; Singh, 1999). The sophistication of these cryptosystems is motivated by what is sometimes called Kerchkoffs’s Principle (named after Auguste Kerckhoffs who proposed it in 1883) or Shannon’s Maxim (put forth by Claude Shannon, regarded as the father of information theory, in the mid-20^th century) (Kerckhoffs, 1883; Shannon, 1949; Khan D. , 1996). This is a precautionary principle that says one should always assume that an eavesdropper is capable of immediately understanding your cryptosystem. Or, put more pithily: “the enemy knows the system being used” (Shannon, 1949, p. 662). This principle is to ensure that the users of a cryptosystem are not overconfident that nobody could be listening in on communications, as is famously what happened with the Axis powers in World War II.

Abiding by this principle is why, although quantum computer technology is still in its infancy (Benioff, 1980; Feynman R. P., 1982; Feynman R. P., 1986), there has been a lot of emphasis put on coming up with cryptosystems that are secure against quantum computers (NIST, 2022a).

The primary advantage of quantum computing is the speed with which it can handle certain types of problems, able to arrive at solutions exponentially quicker than conventional computers (Feynman R. P., 1986; Nielsen & Chuang, 2000; Hidary, 2019). As a result, quantum computing promises both great benefits to scientific and technological progress, but it also poses many potential hazards. Quantum computing technology is rapidly developing (Arute, 2019; Chan, 2019; HPC Wire, 2022; Rolston-Duce, 2022) (Figure 1), and as such, if cryptography is to remain secure, it will need to do two things:

• Use cryptographic algorithms that cannot be cracked by an eavesdropper using a quantum computer (or conventional computer) in any practical amount of time. In other words, it must be secure.
• Be able to be decrypted by the legitimate senders and receivers who possess the relevant keys fast enough to be practical as a cryptosystem. In other words, it must be practicable.

In what follows, I will discuss why our current cryptosystems are insecure against quantum computing by examining the popular RSA cryptosystem and how Shor’s algorithm used on a quantum computer can break RSA. Then I will discuss the potential solutions to this problem in the NIST competition for what is known as post-quantum cryptography (PQC).

RSA Encryption

Current cryptosystems are predicated on the idea of one-way functions (OWF), which are easy to compute in one direction but extremely difficult to do the inverse calculation (Goldreich, 2001). One way in which quantum computing poses a risk is that its ability to rapidly compute difficult problems, such as the inverse of OWF’s, stands to make our current methods of encryption obsolete (Mermin, 2006; Houston-Edwards, 2017b). A popular method of OWF encryption is what is known as public-key cryptography (Rivest, 1978; Stallings, 1990). In public-key cryptography, a public key is shared between two people, say Alice and Bob, who want to pass messages to one another. The public key is set by Alice, who also has a private key that is kept secret. Bob can then encrypt his message with Alice’s public key and send it to her. Anyone else who intercepts the message will not be able to decrypt it since it requires both the public and private keys to decrypt. When Alice receives it, however, she can decrypt the message using her private key.

A common public-key cryptosystem is the RSA (Rivest–Shamir–Adleman) cryptosystem (Rivest, 1978), which uses prime factorization with very large numbers as its OWF. This is done in the following way (Houston-Edwards, 2017a; Houston-Edwards, 2017b). We have our two people, Alice and Bob, where Bob wants to send a secure message to Alice. As discussed, in order to do this, Bob must have the public key set by Alice. The public key consists of two numbers denoted n and e. The number  is the product of two large primes p and q such that

This number n will be used as the modulus for Alice’s public key. The modulus is a concept in modular arithmetic, which is essentially cyclical arithmetic, like on a clock. A clock is a mod 12 system. What this means is, say it is 2 o’clock. What time will it be after nine hours? It will be

That is the same as in normal arithmetic. But what about if it is 2 o’clock and then eleven hours pass? Then we will have

We have cycled back around and started over from one. This cyclical behavior works for any modulus, where, for instance, if we have a mod 5 the cycle goes from 0 to 4 (it is usually standard to begin from 0 instead of 1) and so

The same would work for any modulus  so that

In our modular arithmetic, we can still do multiplication and exponentiation. So, for instance, in our  system, we can do

And for x^k = y mod N with N = 5

 

An interesting property with prime numbers is that if we have the greatest common divisor of x and N, denoted g.c.d.(x,N) = 1, then x and N are said to be coprime or relatively prime. If we choose an x and N that are coprime, then when we raise x to successive positive integer powers k we get a repeating pattern. If we use, say, x = 2 and N = 7 we get Table 1.

In general, we have that if 𝑥 and 𝑁 are coprime, then this will work for all

Observe that in the example in Table 1 we have the repeating pattern of 2, 4, 1, with a period of three. Importantly, it is also the case that the last number in the period will always be 1 when 𝑥 and 𝑁 are coprime. The length of the period 𝑟 will be a signature of the particular 𝑥 and 𝑁 such that

For now, this appears an interesting curiosity, but it will become important later when I cover Shor’s algorithm (Shor, 1994). Let us get back to Alice and Bob sending encrypted messages using the RSA cryptosystem. I said Alice generated a number 𝑛 which was obtained from 𝑛 = 𝑝𝑞 and will be used as the modulus for her encryption. First, she needs a number 𝑒 which falls between 1 and 𝜆(𝑛)

Where 𝑒 and 𝜆(𝑛) are coprime, i.e., the greatest common divisor g.c.d.(𝑒,𝜆(𝑛)) = 1. The number 𝜆(𝑛) is called the Carmichael’s totient function (Carmichael, 1910) and is the smallest positive integer 𝑚 such that

 

Meaning that a^m and 1 congruent modulo 𝑛 and that 𝑎 and 𝑛 are coprime, which means that

 

And g.c.d.(𝑎,𝑛) = 1. As an example, we have for 𝑛 = 5 that 𝜆(𝑛) = 𝑚 ⟶ 𝜆(5) = 4 since the set of numbers 𝑎 that are coprime with 5 is 𝑎∈{1,2,3,4} and

 

If we had 𝑚 = 3 or 𝑚 = 2 then it would not satisfy the (mod 5) criteria, and so 𝑚 = 4 is the smallest positive integer that satisfies a^m ≡ 1 (mod 𝑛) for 𝑛 = 5. Alice now has the public key of 𝑛 and 𝑒, but still needs something for a private key. This is denoted as 𝑑 and is calculated as

In other words, it is the modular multiplicative inverse of 𝑒 modulo 𝜆(𝑛), which means that

Which gives us

Now, after all this, Alice has 𝑛 and 𝑒 as her public key (think 𝑒 for encryption), and 𝑑 and the private key (think 𝑑 for decryption). And so, when Bob wants to send an encrypted message 𝑀 to Alice, he can use Alice’s public key (𝑒,𝑛) and, using Optimal Asymmetric Encryption Padding (OAEP) (Bellare M. a., 1995; RSA Laboratories, 1999) to turn his message 𝑀 into an integer 𝑚, and then encrypt it

And then Alice, upon receiving the ciphertext 𝑐 can decrypt it with her private key 𝑑 to retrieve the integer 𝑚

As a simple example, we can use the prime numbers

Giving us 𝑛 of

And then 𝜆(𝑛) is the lowest common multiple (l.c.m.) of one less than our our prime numbers, i.e., 𝑝 − 1 and 𝑞 − 1, and is

We then find an 𝑒 that is both less than and coprime to 12, which can be any number between 1 and 12 that does not have a common divisor other than 1 with 12. It is often best to use a prime number, since then we already know that it is only divisible by 1, meaning we only need to show that 𝜆(35) = 12 is not divisible by our 𝑒. It is also possible to simply use 𝜆(35) − 1 which for us is 11, which also happens to be prime (this may not always occur). We can thus use

We then must find the modular multiplicative inverse of 𝑒, which in this case also happens to be

Since

Where we end up with a remainder of 1 after division by the modulus

The public key is then (𝑒,𝑛) = (11, 35) and the message is

And the private key of 𝑑 = 11 gives the decryption

Say we want to encrypt the number 𝑚 = 23, we then do

And then to decrypt we do

Which gives us back our original number.

In practice, Alice would use prime numbers 𝑝 and 𝑞 that are much larger, making prime factorization of 𝑛 extremely difficult, i.e., much more difficult than the prime factorization of 35 into 5 and 7. It is the difficulty of prime factorization that makes decryption without both the public and private keys exceedingly difficult for a conventional computer using brute force algorithms.

Quantum Computation

Since 2015, the National Institute of Standards and Technology (NIST) has recommended that the modulus for the RSA key length be 2048 bits (Barker & Dang, 2015), which is a number with some 617 digits. The record for cracking an RSA key was set in 2020, with a key length of 829 bits, a 250-digit number, which took 2700 core-years using Intel Xeon and the general number field sieve algorithm (Zimmermann, 2020; Lenstra, 1993). Using a conventional computer, cracking a 2048-bit RSA key could take millions of years using the general number field sieve algorithm, and much longer using brute force tactics.

Quantum computers, on the other hand, can make such computations much faster. In quantum computing, instead of using 0 and 1 as the states of the logic gate, it uses a unit vector in complex 2D Hilbert space (Hilbert D. R., 2009; Hilbert D. R., 1928). This can be given in Dirac bra-ket notation (Dirac, 1939; Dirac, 1958) as a linear combination of states as follows

Where the coefficients 𝛼,𝛽∈ℂ and are normalized so that 𝛼𝛼* + 𝛽𝛽* = 1 (where the superscript * indicates complex conjugate) and the ket vectors |0⟩ and |1⟩ are orthonormal bases such that

This vector can be represented as in Figure 2 in what is called a Bloch sphere (Bloch, Nuclear Induction, 1946; Feynman R. P., 1957; Bloch & Rabi, 1945; Stroud, 1972), with

The e^iφ is a phase factor which does not affect the global probability amplitude (see Appendix C for how this is carried out on an actual quantum computer). And so, the Bloch spheres for the zero-superposition and uniform superposition would look like Figure 3.

.

To perform the computations, the quantum computer uses the superposition of the quantum system, called a qubit (portmanteau of quantum bit). This is done essentially by preparing the quantum system in a superposition of all states and then using a quantum algorithm to destructively interfere with “incorrect” states (i.e., states that represent the incorrect solution to the problem) until only the state representing the correct solution remains (Figure 4).

We can think of it like this. If we want to find a factor of 𝑛 with a conventional computer, we could use a brute force method. This means that our computer would see if 2 divides 𝑛, and if that does not work, it would then check if 3 divides 𝑛, and if that does not work, it would check if 4 divides 𝑛, and so on up to 𝑛 − 1 or whenever the computer found a number that divided 𝑛.

We could instead have multiple computers, perhaps even up to 𝑛 − 1 computers, working in parallel, each one checking to see if its single assigned number divides 𝑛. This obviously becomes extremely computationally expensive when we have 𝑛 with 600+ digits, since there are not enough computers in the universe to do this.

Enter the quantum computer. Since a qubit is a linear combination of multiple states, it can essentially hold all the possible solutions for factors of 𝑛 all at once (Houston-Edwards, 2017b).

Where each |𝑝 = 𝑖⟩ is a possible factor for 𝑛 = 𝑝𝑞. The problem is that when we measure our system, there is a 1/𝑛 chance of randomly getting one of the states, making it no better (and perhaps worse) than the brute force method with conventional computers. This means we need some way of amplifying the |𝑝 = 𝑖⟩ that has the correct value for 𝑖 while removing those states that do not have the correct value for 𝑖. Doing this will use what is called the quantum Fourier transform (QFT) which will be discussed later (Coppersmith, 1994).

A single qubit is not enough for most quantum calculations, and so quantum entanglement is exploited to generate a much larger space of possible quantum states (Bernhardt, 2019; Qiskit, 2022a). Effectively what this means is that we cannot differentiate the state of one quantum system from another (the state is described by a single Hamiltonian), and so for two particles that we can call particle 𝐴 and particle 𝐵 we get the entangled quantum state denoted by |𝐴⟩⨂|𝐵⟩ where ⨂ is the tensor product of our two Hilbert spaces H_A and H_B. More explicitly, this gives us

Where a₀, a₁, b₀, b₁ are probability amplitudes. When we “FOIL” it out we get

We can set the probability amplitude products equal to a single letter

As before, we have that 𝑝𝑝* + 𝑞𝑞* + 𝑟𝑟* + 𝑠𝑠* = 1. But we also have that if the two particles are not entangled, then 𝑝𝑠 = 𝑞𝑟, but if they are entangled, then 𝑝𝑠 ≠ 𝑞𝑟 since 𝑞|0⟩_A|1⟩_B + 𝑟|1⟩_A|0⟩_B represents that the particles cannot be differentiated from each other (i.e., it could be that particle 𝐴 is in state |0⟩ and particle 𝐵 is in state |1⟩, or it could be the other way around).

With two particles 𝐴 and 𝐵, they each have their own 2D Hilbert space H_A and H_B, so the tensor product of these two spaces is a 4D space with the basis

Giving the 4×4 identity matrix

We can make the Controlled NOT (CNOT) quantum gate (equivalent of exclusive OR gate, i.e., XOR gate, see Appendix A for more on quantum gates) (Barenco, 1995; Nielsen & Chuang, 2000) by switching the last two columns

What this allows us to do is entangle an unentangled pair of electrons |𝐴⟩ and |𝐵⟩. If we have our unentangled pair of electrons as

Where now we see that 𝑝𝑠 ≠ 𝑞𝑟, meaning our particles are entangled.

Entanglement increases the number of particles in a quantum register and allows for a greater number of possible states of the system (IBM, 2022). For instance, if our register has three entangled particles, then we have (Qiskit, 2022a)

And in general, for 𝑛 qubits in the quantum register there will be 2ⁿ probability amplitudes.

The same method of destructive interference discussed above is used on the register, but it allows for computations on problems containing much more information. Think of it like this: a conventional computer with 64-bits can perform computations with larger numbers than a 32-bit conventional computer, so a 2-qubit quantum computer would be able to perform computations on larger numbers than a 1-qubit quantum computer. Quantum computations make quantum computers significantly faster at solving certain kinds of problems than conventional computers (Figure 5). This means that once quantum computers are sufficiently advanced (Arute, 2019), the use of algorithms like that of Peter Shor (Shor, 1994; Mermin, 2006) will make RSA (Rivest–Shamir–Adleman) cryptosystems (Rivest, 1978) insecure. This is because quantum computers can solve the prime factorization with many fewer operations than conventional computers.

Shor’s Algorithm

Here is how Shor’s algorithm works (Houston-Edwards, 2017b; Mermin, 2006; Qiskit, 2022c). Say Bob wants to send an encrypted message to Alice. To do this, Alice shares her public key with Bob, which contains the modulus 𝑛, as discussed above. Since this is part of the public key, a hacker Eve can gain access to it. Because Alice and Bob are using the RSA cryptosystem, Eve knows that their 𝑛 is equal to the product of two prime numbers 𝑝 and 𝑞 such that

The first thing Eve will do is pick a number 1 < 𝑎 < 𝑛 that is coprime to 𝑛, meaning that the greatest common divisor is 1, i.e., g.c.d.(𝑎,𝑛) = 1. This can be done using the Euclidean algorithm (Khan S. , 2013; Zhou, 2010). If Eve finds that g.c.d.(𝑎,𝑛) > 1 then 𝑎 is a factor of 𝑛 and Eve has succeeded. However, if g.c.d.(𝑎,𝑛) = 1 then Eve will need to do more work.

The next step is to compute the period 𝑟 of 𝑎 mod 𝑛. Remember, the period is how many times the computation is repeated before the remainder gets back to one, i.e., that a^r = 1 mod 𝑛. Let us say, for instance, that we have 𝑛 = 35 and we use 𝑎 = 8, since those are coprime. We find that

And so, Eve finds that the period is 𝑟 = 4. Eve will need to have 𝑟 be even for this to work out, and so if 𝑟 ends up being odd, Eve will have to go back and pick a different 𝑎. In this case, Eve was lucky the first time and got an even number 𝑟. The reason for this is because we will need to factor out 𝑎𝑟 and so will need a^r/2 to proceed. Eve will also need to know that

If this is not satisfied, Eve will again have to go back and pick a different 𝑎. Next, Eve can use the fact that she knows

Which means that a^r − 1 is a multiple of 𝑛 such that

Eve can then factor a^r − 1 to obtain

And use that 𝑛 = 𝑝𝑞 to get

Which tells Eve that 𝑝 divides one of the two parentheses in the numerator and 𝑞 divides the other one. The reason we needed a^r/2 + 1 ≢ 0 mod 𝑛 was to ensure that 𝑝 divides only one of them and 𝑞 divides only one of them. In other words, Eve can safely say that

Using the example of 𝑛 = 35 and 𝑎 = 8 we have that

And so

With 7 and 5 being the two prime numbers that multiply together to get 35.

In practice, if Eve is using a conventional computer, she will find that obtaining the period 𝑟 is computationally extremely difficult and time consuming. But if Eve has a quantum computer, she will be able to find 𝑟 much faster. This is where Shor’s algorithm really comes into play.

As discussed earlier, when using a quantum computer, the different potential factors of 𝑛 are represented in the superpositions of the qubits. When measuring the system there will be an equal probability of finding one of the states. As such, there needs to be a way of amplifying the components of the superpositions representing the correct factors of 𝑛 and reducing those that are incorrect factors. This is done using the quantum Fourier transform (QFT) (Coppersmith, 1994; Qiskit, 2022b).

To understand QFT we first need to discuss the Hadamard gate (Sylvester, 1867; Hadamard, 1893), which is a 1-qubit QFT (Appendix A). Earlier I described the CNOT gate, which is a type of quantum gate. The Hadamard gate is another quantum gate and is represented by the matrix

What the Hadamard gate does is switch from the 𝑧-basis to the 𝑥-basis on the Bloch sphere (Figure 6). Recall that the 𝑥-basis represented the phase (Figure 3). This means, similar to a typical Fourier transform, it is transforming from one domain to another, in this case from what is called the counting basis (or the 𝑧-basis) into the Fourier basis (or the 𝑥-basis).

The QFT works much the same way, except now it is doing it with multiple qubits, which cannot really be illustrated with a Bloch sphere. The QFT is given by (Qiskit, 2022b)

Where 𝜙_k are our vector components in the Fourier basis, 𝜓_j are our vector components in the counting basis, and e^i2π(jk)/N indicates a number of phase shifts. We can look at how this works for the Hadamard gate for a single qubit |Ψ⟩ = 𝛼|0⟩ + 𝛽|1⟩ where 𝜓₀ = 𝛼, and 𝜓₁ = 𝛽, and 𝑁 = 2 so that

Which is the same as using the Hadamard operator

For larger systems, just a single Hadamard gate will not suffice, and so we also need the phase gate, called the controlled rotation or CROT, which is

Which gives the QFT in general for 𝑁 = 2ⁿ as

Where we can see that |0⟩ does not change but |1⟩ is rotated (counterclockwise) around the 𝑧-axis.

Now, with these rotations, we can exploit the roots of unity found in complex analysis (Figure 7). While in the Fourier basis, for each qubit in our register, we rotate the vector once, with each qubit rotating by an angle determined by the roots of unity. For instance, if we have four qubits, one will remain where it is (𝑁 = 1), one will oscillate back and forth (𝑁 = 2), one will make rotations of 120° (𝑁 = 3), and the last will make rotations of 90° (𝑁 = 4). It does one of these rotations for each of the terms of our linear combination (i.e., each component of our superposition). When it lands on the final member of the period, i.e., 𝑎^k ≡ 1 mod 𝑛, we stop and measure which direction the vector is pointing (i.e., what the phase is). Whichever root of unity is equal to the period 𝑟 will be the one that does not end up back at the starting point when a period is over.

As an example, let us look at 𝑎 = 2 and 𝑛 = 7. For this, our superposition will be

This is a simple case, so we know that the period will repeat 2,4,1 over and over again, giving us 𝑟 = 3. But let us look at it with our algorithm. With the 𝑁 = 2, 3, 4 roots of unity (skipping the trivial case of 𝑁 = 1) we find that the 𝑁 = 2 and 𝑁 = 4 cancel out while the 𝑁 = 3 amplifies because they point in the same direction (Figure 8).

For 𝑎^k mod 7 all rotations around the roots of unity will cancel out except for 𝑁 = 3, which will be amplified, telling us that our period is 𝑟 = 3. Now, equipped with the period, our hacker Eve would be able to discover (𝑎^r/2 − 1)(𝑎^r/2 + 1) = 𝑘𝑝𝑞 and obtain 𝑝 and 𝑞.

Lattice-Based Cryptography

Once quantum computer technology arrives at the point where it is able to run Shor’s algorithm, the RSA cryptosystem will be insecure (Shor, 1994; Mermin, 2006; IBM Quantum, 2022; Qiskit, 2022c). This demands the development of new cryptosystems to protect against these vulnerabilities. The National Institute of Standards and Technology (NIST) has been running a competition in which groups come up with post-quantum cryptography (PQC) algorithms, such as the McEliece cryptosystem (McEliece, 1978) and Lattice based cryptography (Ajtai M. , 1996; Ajtai M. a., 1997; Regev, 2005; Hoffstein, 1998; Kwiatkowski, 2019). As of 2022, there are four selected algorithms still in the running (NIST, 2022a).

Lattice based cryptography uses the fact that finding the smallest non-zero vector in an 𝑛-dimensional lattice is extremely difficult, even for a quantum computer (Regev, 2005). This is known as the SVP or the Shortest Vector Problem (van Emde Boas, 1981; Manohar, 2016; Nguyen, 2010). See Appendix B for a more in-depth review of the mathematical background, but I will explain it here briefly. Say we have a vector space 𝑉 with the Euclidean norm ℓ² and a basis in ℝ^m that is

With our basis 𝑏₁, 𝑏₂,…, 𝑏_n in 𝑚 dimensions such that

And 𝑚 ≥ 𝑛. For our purposes we can use the case where 𝑚 = 𝑛 and therefore [𝑏₁, 𝑏₂,…, 𝑏_n] is a square matrix that we can write as

Where ℝ^n×n is the set of all real-numbered 𝑛×𝑛 matrices. Our lattice is then

And so, a lattice would be

Which is the points in 2D Euclidean space ℝ² with integer coordinates, which have basis

Which would give us the same lattice (Figure 9). Indeed, it is the case that every lattice with a rank of 𝑛 ≥ 2 can have infinitely many bases (Nguyen, 2010; Manohar, 2016).

The bases are found when the fundamental parallelepiped 𝒫(𝐆) and the lattice Λ only have an intersection at the point zero

Since zero is the only coordinate in 𝒫(𝐆) that is an integer.

A basis must satisfy two properties: they must be vectors that are (1) linearly independent and (2) span the entire space. (1) means that each basis cannot use any of the other bases to describe them, and (2) means that any point in the space (i.e., the lattice) must be able to be described using the basis (there are no points in the lattice that cannot be described by linear combinations of the bases). What we might think of as the natural basis is the one that uses the shortest distances, like those shown on the left side in Figure 9. But it would not be invalid to use a basis that is 𝑏₁ = (2  0)^T and 𝑏₂ = (0  2)^T, or, indeed, as shown on the right side of Figure 9, we could alternatively have used

What we then want to do is find the smallest non-zero vector, which is denoted as 𝜆₁(Λ) where this is the shortest in what is called the successive minima of the lattice 𝜆_i(Λ). To find this, we take an open ball 𝐵_r(𝑝) at a point 𝑝 (usually at 𝑝 = 0) and then find 𝑥 such that

Where 𝑟 is the radius of the open ball 𝐵_r(𝑝). The successive minima are defined so that

What this means is that each successive 𝜆_i(Λ) must be the next larger open ball to include lattice points in the next dimension. For instance, if we have a 2D rectangular lattice (Figure 10), then 𝜆₁(Λ) is the smallest open ball that includes the next nearest lattice point, and 𝜆₂(Λ) is the radius of the next larger open ball that includes the nearest lattice point in a second dimension.

At first the SVP may appear to be an easy problem. However, if this is done in many dimensions, even on the order of hundreds of dimensions, and using long bases instead of short, then the problem becomes an NP-hard problem, requiring greater than 𝑂(𝑛²) time to compute (Papadimitriou, 1993; Sipser, 2014; van Leeuwen, 1994; Peikert, 2009). Indeed, there is no known way to solve it quickly, even with a quantum computer, which makes the SVP a good candidate as a secure cryptosystem.

There are three variants of what is called the closest vector problem (CVP). These are known as the decisional, optimization, and search CVP, which are defined in the following ways.

The most common types of lattice problems are the shortest vector problem using the decisional variant, which is called G_APSVP, and the shortest independent vectors problem, or SIVP. There are also the generalized independent vectors problem (GIVP) and the discrete Gaussian sampling problem (DGS). The definitions of these are

In general, we have that the probability at some point 𝐱 in the lattice is

Where 𝑐 = 0 at the origin. And the distribution for some set 𝐴 is

From this, the definition of 𝐷_A,k (the general form of 𝐷_ℒ,𝑟) is

Post-Quantum Cryptosystem Competition at NIST

The selected PQC from NIST, (Table 2) use lattice-based cryptosystems (NIST, 2022a).

CRYSTALS-KYBER (Cryptographic Suite for Algebraic Lattices)

For the sake of brevity, I will focus only on the CRYSTALS-KYBER system, primarily pulling from (Botros, 2019) and (Avanzi, 2021).

Using modular learning with errors (MLWE), the public key consists of a 𝑘×𝑘 matrix 𝐀̂ (where 𝐀̂ is a matrix 𝐀 after use of a number-theoretic transform (NTT)) with polynomial elements from the modulo 𝑞 ring ℛ_q=ℤ_q[𝑥]/(𝑥ⁿ + 1) (see Appendix B). The CRYSTALS-KYBER system in particular uses the prime number 𝑞 = 3329 and order 𝑛 = 256 such that

In learning with errors (LWE) (Regev, 2005; Stehlé, 2009; Langlois, 2012; Lyubashevsky V. C., 2013; Bonnoron, 2017; Chen H. L., 2020; Albrecht, 2021; Boudgoust, 2022) we are given an 𝑛-dimensional lattice where we need to find linearly independent vectors s₁, s₂, s₃, …, 𝑠_n that minimize max_(i)‖𝑠_i‖. This is often made simpler by requiring that max_(i)‖𝑠_i‖ is within an approximation factor 𝛾(𝑛) ≥ 1 off from the real vector 𝐬. To find max_(i)‖𝑠_i‖ using LWE we are given positive integers 𝑛 and 𝑞 (lattice dimensions and modulus, respectively) with a probability density function 𝜒 over the interval 𝕋=ℝℤ⁄≅[0,1) and then must find the vector 𝐬 using random 𝑎∈ℤⁿ_q and 𝜀∈𝕋 (uniformly sampled) such that we have the equations

Where, given many (𝑎_i,𝑏_i) and an error 0 ≤ 𝜀 < 1, the vector 𝐬 must be calculated. When we have that 𝜀 = 0 this is a standard Gaussian elimination problem and takes 𝑛 equations to find a single 𝑠_i, corresponding to a single bit of our message. When instead we have 𝜀 > 0 then it requires 2ⁿ equations and 𝑂(2ⁿ) time to obtain the first bit of the message. We can use instead matrices such that 𝑎_ij∈𝐀 and 𝑏_ij∈(1/q)𝐀𝒔+𝒆 where 𝐀∈ℤ_q^m×m. For the CRYSTALS-KYBER system, the 𝐬 vector that we are trying to find (i.e., the shortest vector) and 𝐞, the error, are 𝑘-dimensional vectors so that 𝐛 = (1/𝑞)〈𝐀̂,𝐬〉+𝐞.

The number-theoretic transform (NTT) (Toom, 1963; Cook, 1969) is done in order to perform more efficient multiplications in ℛ_q=ℤ_q[𝑥](𝑥ⁿ + 1). NTT is a generalization of the fast Fourier transform (Cooley & Tukey, 1965). Briefly, it works as follows. If we have a polynomial 𝑓(𝑥) = Σ_i=0^n-1 f_ixⁱ∈ℛ_q then the NTT is

With 𝜔 = 3844 and 𝜓 = √𝜔 = 62 and each 𝑓_i randomly sampled from a centered binomial distribution 𝐵𝜂 with 𝜂 = 2 or 𝜂 = 3 such that {0,1}^2𝜂∈𝐵_𝜂 (see Glossary: Notation and Parameters). The inverse is

For instance, using the polynomial (𝑥²⁵⁶ + 1) we can factor it into 128 degree 2 polynomials modulo 𝑞 like

Where 𝜁 are the 256 roots of unity. And so, the NTT of 𝑓∈ℛ_q is

This makes the multiplication of two polynomials 𝑓,𝑔∈ℛ_q much more efficient using

Key construction is done in two steps. The first step (Figure 11) generates a chosen-ciphertext attacks (CCA) secure key encapsulation mechanism (KEM).

This is done similar to (Lyubashevsky V. C., 2013), but instead of ℤ_q uses a polynomial ring ℤ_q[𝑥]/〈𝑓(𝑥)〉 like in (Hoffstein, 1998). It also utilizes a method made by (Alkim, 2015) to generate a public matrix (Figure 12).

The second step (Figure 13) is to generate the Kyber.CCAKEM IND-CCA2-secure KEM (indistinguishability against chosen-ciphertext attacks (IND-CCA) KEM) (Rackoff, 1992) using a variation of the Fujisaki–Okamoto transform (Fujisaki, 2013; Hofheinz, 2017).

The Fujisaki–Okamoto transform converts asymmetric or symmetric encryption schemes into a stronger hybrid encryption scheme, i.e., strong in the sense of indistinguishability against adaptive chosen-ciphertext attacks (IND-CCA) in the random oracle model (Bellare & Rogaway, 1993).

Conclusions

As it stands, online banking, email, e-commerce, Transport Layer Security (TLS), and Virtual Private Networks (VPN) use what is called the public key infrastructure (PKI) (Copeland, 2021). To decrypt such messages, a person or business requires a private key in addition to the public key. Without the private key, the time it would take to break the encryption would be hundreds or even thousands of years. With quantum computers, a potential eavesdropper will not require the private key to be able to break the encryption in as short as eight hours (Ryan-Mosley, 2019).

As a result, post-quantum cryptography will be important in many arenas, such as in the realms of the military (Parker, 2021), national security (DHS, 2022), diplomacy (Shafeeq, 2022), and business (IBM, 2018; Buchholz, 2021). Indeed, in July of 2022, NIST already selected twelve businesses to begin using their post-quantum cryptosystems (NIST, 2022b) (Figure 14). Further, there are startups that are attempting to come up with their own methods of post-quantum cryptography (StartUs Insights, 2020; Tracxn, 2022).

Changing to PQC will not be an easy process (Chen L. , 2017; Barker W. W., 2021). For one, in the currently developing PQC’s, the key sizes can still be quite large, making them unsuitable for many uses. Similarly, decryption can still be computationally burdensome. Indeed, the NIST white paper (Barker W. W., 2021) says

On the other hand, existing protocols might need to be modified to handle larger signatures or key sizes (e.g., using message segmentation). Implementations of new applications will need to accommodate the demands of post-quantum cryptography and allow the new schemes to adapt to them. In fact, post-quantum cryptographic requirements may actually shape some future application standards.

These new PQC algorithms will also mean replacing cryptographic libraries, validation tools, hardware, operating systems, and procedures used by administrators and users alike. There will need to be new documentation for standards and procedures of installation, maintenance, and administration. Further, businesses and other organizations will need to catalogue where cryptography is implemented and for what reason, but most IT and information security do not keep records of every system using cryptography. As such, these organizations will need to come up with protocols and methods for identifying where and how these cryptosystems are employed, and then coming up with a means for prioritizing which systems need to be replaced with PQC’s.

The NIST white paper (Barker W. W., 2021) says that identifying where PQC should be implemented will require

• Outreach to SDOs to raise awareness of necessary algorithm and dependent protocol changes (e.g., Internet Engineering Task Force [IETF], International Organization for Standardization/International Electrotechnical Commission [ISO/IEC], American National Standards Institute/International Committee for Information Technology Standards [ANSI/INCITS], Trusted Computing Group [TCG])
• Discovery of all instances where Federal Information Processing Standards and NIST Special Publication 800-series documents will need to be updated or replaced
• Identification of automated discovery tools to assist organizations in identifying where and how public-key cryptography is being used in their systems
• Development of an inventory of where and for what public-key cryptography is being used in enterprises

Regardless of these difficulties, it is necessary that PQC measures be formulated and implemented. Estimates for when quantum computers will reach a level of advancement sufficient to reliably crack current encryption schemes range anywhere between five years and twenty years (Shankland, 2021). As a result, the pains of migrating to PQC will likely be much less than the pain of not migrating to PQC. Neglecting to do this could potentially result in a wild-west-like anarchy of hacks and leaks of personal and vital information from individuals and organizations alike.

The topic of quantum computers and post-quantum cryptography is much larger than this report could ever hope to fully cover. Here I have discussed only a single current public key cryptosystem, namely RSA, and only took a cursory look at a single one of the numerous PQC’s being developed to supersede our current cryptosystems, namely CRYSTALS-KYBER. And even there I hardly did justice to the sophistication and complexity of the PQC. Yet I hope this report has at least indicated at how serious the issue is, and at how difficult it may be to fully implement a regime of post-quantum cryptography.

—

Again, if you want to see the two glossaries of terms, and the three appendixes, see the PDF version of this article.

—

References

Ajtai, M. (1996). Generating Hard Instances of Lattice Problems. Electron. Colloquium Comput. Complex.,
3., 99–108. doi:10.1145/237814.237838

Ajtai, M. a. (1997). A Public–Key Cryptosystem with Worst–Case/Average–Case Equivalence. Electronic
Colloquium on Computational Complexity. Retrieved from https://eccc.weizmann.ac.il/report/1996/065/

Albrecht, M. &. (2021). Lattice Attacks on NTRU and LWE: A History of Refinements. Cryptology ePrint
Archive. Retrieved from https://eprint.iacr.org/2021/799

Alexander, T. N.–A. (2020). Qiskit pulse: programming quantum computers through the cloud with pulses. Quantum Science and Technology, 5. doi:https://doi.org/10.1088/2058–9565/aba404

Al–Kadit, I. A. (1992). The origins of cryptology: The Arab contributions. Cryptologia, 97–126. doi:10.1080/0161–119291866801

Alkim, E. L. (2015). Post–quantum key exchange – a new hope. Cryptology ePrint Archive. Retrieved from https://eprint.iacr.org/2015/1092

Al–Tayeb, T. (2003, June 9). Al–Kindi, Cryptography, Code Breaking and Ciphers. Retrieved November 8, 2022, from Muslim Heritage: https://muslimheritage.com/al–kindi–cryptography/

Anderson, P. W., & Rowell, &. J. (1963). Probable Observation of the Josephson Tunnel Effect. Phys. Rev. Lett., 230–232. doi:10.1103/PhysRevLett.10.230

Arute, F. e. (2019). Quantum Supremacy Using a Programmable Superconducting Processor. Nature, pages 505–510. doi:https://doi.org/10.1038/s41586–019–1666–5

Avanzi, R. B. (2021). CRYSTALS–Kyber Algorithm Specifications And Supporting Documentation.

Bacon, D. (2001). Decoherence, control, and symmetry in quantum computers. University of California, Berkeley. Retrieved from https://arxiv.org/abs/quant–ph/0305025

Bai, S. a. (2013). An improved compression technique for signatures based on learning with errors. Cryptology ePrint Archive. Retrieved from https://eprint.iacr.org/2013/838

Bardin, J. C. (2020a, August). Quantum Computing. pp. 24–44. Retrieved from https://par.nsf.gov/servlets/purl/10195986

Bardin, J. C. (2020b). Microwaves in Quantum Computing. IEEE Journal of Microwaves, 403–427. doi:10.1109/JMW.2020.3034071

Barenco, A. B. (1995). Elementary gates for quantum computation. Physical Review, 3457–3467. doi:https://doi.org/10.1103/PhysRevA.52.3457

Barends, R. K. (2013). Coherent Josephson Qubit Suitable for Scalable Quantum Integrated Circuits. Physical Review Letters, 080502. doi:10.1103/PhysRevLett.111.080502

Barker, E. a. (2015). Recommendation for Key Management Part 3: Application–Specific Key Management Guidance. Gaithersburg: National Institute of Standards and Technology U.S. Department of Commerce. doi:http://dx.doi.org/10.6028/NIST.SP.800–57pt3r1

Barker, W. W. (2021). Getting Ready for Post–Quantum Cryptography: Exploring Challenges Associated with Adopting and Using Post–Quantum Cryptographic Algorithms. NIST. Retrieved from https://nvlpubs.nist.gov/nistpubs/CSWP/NIST.CSWP.04282021.pdf

Bauch, J.–D. (2014). Lattices over polynomial Rings and Applications to Function Fields. Arxiv. Retrieved from https://www.tesisenred.net/bitstream/handle/10803/283357/jdb1de1.pdf?sequence=1

Bellare, M. a. (1995). Optimal Asymmetric Encryption — How to encrypt with RSA. Lecture Notes in Computer Science. Retrieved from https://cseweb.ucsd.edu/~mihir/papers/oaep.pdf

Bellare, M., & Rogaway, P. (1993). Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. CM Conference on Computer and Communications Security, (pp. 62–73). Retrieved from https://cseweb.ucsd.edu/~mihir/papers/ro.pdf

Benioff, P. (1980). The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines. Journal of Statistical Physics, 563–591. doi:10.1007/bf01011339

Bernhardt, C. (2019). Quantum Computing for Everyone. Cambridge: Massachusetts Institute of Technology.

Bernstein, D. J. (2019a). Decisional second–preimage resistance: When does SPR imply PRE? Retrieved from https://eprint.iacr.org/2019/492.pdf

Bernstein, D. J. (2019b). The SPHINCS+ Signature Framework. Retrieved from https://sphincs.org/data/sphincs+–paper.pdf

Bloch, F. (1946). Nuclear Induction. Physical Review, 460–474. doi:10.1103/PhysRev.70.460

Bloch, F. a. (1945). Atoms in Variable Magnetic Fields. Rev. Mod. Phys., 237–244. doi:10.1103/RevModPhys.17.237

Bogdanov, A. a. (2007). Pseudorandom bits for polynomials. 8th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), (pp. 41–51). doi:10.1109/FOCS.2007.42

Bonnoron, G. &. (2017). A note on Ring–LWE security in the case of Fully Homomorphic Encryption. Lecture Notes in Computer Science (pp. 27–43). Springer, Cham. doi:https://doi.org/10.1007/978–3–319–71667–1_2

Bose, S. N. (1924). Plancks Gesetz und Lichtquantenhypothese. Zeitschrift für Physik, 178–181. doi:10.1007/BF01327326

Botros, L. M. (2019). Memory–Efficient High–Speed Implementation of Kyber on Cortex–M4. Cryptology ePrint Archive. Retrieved from https://eprint.iacr.org/2019/489

Bouchiat, V. D. (1998). Quantum Coherence with a Single Cooper Pair. Physica Scripta, 165–170. Retrieved from http://ursula.chem.yale.edu/~batista/classes/CHEM584/Cooperpair.pdf

Boudgoust, K. C.–L. (2022). On the Hardness of Module Learning With Errors with Short Distributions. Cryptology ePrint Archive. Retrieved from https://eprint.iacr.org/2022/472

Boylestad, R. (2015). Introductory Circuit Analysis. Pearson. Retrieved from https://www.amazon.com/Introductory–Circuit–Analysis–Robert–Boylestad/dp/0133923606/

Buchholz, S. D. (2021, April 15). A business leader’s guide to quantum technology. Retrieved from Deloitte: https://www2.deloitte.com/us/en/insights/topics/innovation/quantum–computing–business–applications.html

Carmichael, R. (1910). Note on a new number theory function. Bulletin of the American Mathematical Society, 16, 232–238. doi:10.1090/S0002–9904–1910–01892–9

Chan, R. (2019, January 13). Business Insider. Retrieved from IBM unveils the world’s first quantum computer that businesses can actually use to solve previously impossible problems: https://www.businessinsider.com/ibm–unveils–ibm–q–system–one–the–first–commercial–quantum–computer–2019–1

Chen, H. L. (2020). On the Concrete Security of LWE with Small Secret. Cryptology ePrint Archive. Retrieved from https://eprint.iacr.org/2020/539

Chen, L. (2017). Cryptography Standards in Quantum Time: New Wine: New Wine in an Old Wineskin? IEEE Security & Privacy, 51–57. doi:https://doi.org/10.1109/MSP.2017.3151339

Cirac, J. I. (1995). Quantum Computations with Cold Trapped Ions. Phys. Rev. Lett., 4091–4094. doi:10.1103/PhysRevLett.74.4091

Combescot, R. (2022). Superconductivity: An Introduction. Cambridge University Press. Retrieved from https://www.amazon.com/Superconductivity–Introduction–Roland–Combescot/dp/110842841X/

Cook, S. A. (1969). On the Minimum Computation Time of Functions. Transactions of the American Mathematical Society, 291–314. doi:10.1090/S0002–9947–1969–0249212–8

Cooley, J. W., & Tukey, a. J. (1965). An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation, 297–30. doi:10.2307/2003354

Cooper, L. N. (1956). Bound Electron Pairs in a Degenerate Fermi Gas. Phys. Rev., 1189—1190. doi:10.1103/PhysRev.104.1189

Copeland, W. F. (2021, October 6). Quantum computing will break today’s encryption standards – here’s what to do about it. Retrieved November 6, 2022, from Verizon: https://www.verizon.com/about/news/quantum–computing–encryption–standards

Coppersmith, D. (1994). An approximate Fourier transform useful in quantum factoring. Yorktown Heights: IBM Research Division. Retrieved from https://arxiv.org/pdf/quant–ph/0201067.pdf

Cory, D. G. (1997). Ensemble quantum computing by NMR spectroscopy. Proceedings of the National Academy of Sciences of the United States of America, 1634–1639. doi:https://doi.org/10.1073/pnas.94.5.1634

Cross, A. W. (2019). Validating quantum computers using randomized model circuits. Phys. Rev., 100(3), 032328. doi:10.1103/PhysRevA.100.032328

DHS. (2022, October 4). Post–Quantum Cryptography. Retrieved from Homeland Security: https://www.dhs.gov/quantum

Diffie, M., & Hellman, M. (1976). New directions in cryptography. EEE Transactions on Information Theory, 644–654. doi:10.1109/TIT.1976.1055638

Dilmegani, C. (2021, April 18). Quantum Hardware Components, Interfaces & Challenges. Retrieved November 6, 2022, from AI Multiple: https://research.aimultiple.com/quantum–computing–hardware/

Dirac, P. (1939). A new notation for quantum mechanics. Mathematical Proceedings of the Cambridge Philosophical Society, 416–418. doi:10.1017/S0305004100021162

Dirac, P. (1958). The Principles of Quantum Mechanics (4 ed.). Clarendon Press.

Djekic, M. (2013, November 25). A Scytale – Cryptography of the Ancient Sparta. Retrieved November 8, 2022, from Australian Science: http://ozscience.com/technology/a–scytale–cryptography–of–the–ancient–sparta/

Ducas, L. A. (2013). Lattice Signatures and Bimodal Gaussians. Cryptology ePrint Archive. Retrieved from https://eprint.iacr.org/2013/383

Einstein, A. (1924). Quantentheorie des einatomigen idealen Gases. Königliche Preußische Akademie der Wissenschaften, 261–267. Retrieved from https://www.uni–muenster.de/imperia/md/content/physik_ap/demokritov/mbecfornonphysicists/einstein_1924_1925.pdf

Feynman, R. P. (1957). Geometrical Representation of the Schrödinger Equation for Solving Maser Problems. Journal of Applied Physics. doi:https://doi.org/10.1063/1.1722572

Feynman, R. P. (1982). Simulating Physics with Computers. International Journal of Theoretical Physics, 467–488. doi:10.1007/BF02650179

Feynman, R. P. (1986). Quantum mechanical computers. Foundations of Physics, 507–531. doi:10.1007/bf01886518

Fouque, P.–A. J. (2020). Falcon: Fast–Fourier Lattice–based Compact Signatures over NTRU.

Friis, N. O. (2018). Observation of Entangled States of a Fully Controlled 20–Qubit System. Physical Review, 021012. doi:10.1103/PhysRevX.8.021012

Fujisaki, E. O. (2013). Secure Integration of Asymmetric and Symmetric Encryption Schemes. J Cryptol, 80–101. doi:https://doi.org/10.1007/s00145–011–9114–1

Gambetta, J. &. (2019, March 4). Cramming More Power Into a Quantum Device. Retrieved November 7, 2022, from IBM Research Blog: https://www.ibm.com/blogs/research/2019/03/power–quantum–device/

Gentry, C. C. (2007). How to Use a Short Basis: Trapdoors for Hard Lattices and New Cryptographic Constructions. Cryptology ePrint Archive. Retrieved from https://eprint.iacr.org/2007/432

Goldreich, O. (2001). Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press. Retrieved from https://www.amazon.com/Foundations–Cryptography–Basic–Tools–Vol/dp/0521791723/

Graham, T. S. (2022). Demonstration of multi–qubit entanglement and algorithms on a programmable neutral atom quantum computer. Nature, 457–462. doi:https://doi.org/10.1038/s41586–022–04603–6

Grumbling, E. a. (2019). Quantum Computing: Progress and Prospects. Washington, DC: National Academy of Sciences. doi:https://doi.org/10.17226/25196

Hadamard, J. (1893). Résolution d’une question relative aux déterminants. Bulletin des Sciences Mathématiques, 240–146.

Hendrickx, N. W. (2020). A single–hole spin qubit. Nature Communications. doi:https://doi.org/10.1038/s41467–020–17211–7

Hendrickx, N. W. (2021). An array of four germanium qubits. Nature. doi:https://doi.org/10.1038/d41586–021–01116–6

Henriet, L. L.–O. (2020). Quantum Computing with Neutral Atoms. Quantum. Retrieved from https://arxiv.org/pdf/2006.12326.pdf

Hidary, J. (2019). Quantum computing: an applied approach. Springer. Retrieved from https://www.amazon.com/Quantum–Computing–Approach–Jack–Hidary/dp/3030239217

Hilbert, D. R. (1928). Über die Grundlagen der Quantenmechanik. Mathematische Annalen, 1–30. doi:10.1007/BF01451579

Hilbert, D. R. (2009). David Hilbert’s Lectures on the Foundations of Physics 1915–1927. (U. M.–J. Tilman Sauer (Editor), Ed.) Springer. Retrieved from https://www.amazon.com/Hilberts–Lectures–Foundations–Physics–1915–1927/dp/354020606X

Hinsley, F. H. (1993). Codebreakers: The inside story of Bletchley Park. Oxford: Oxford University Press. Retrieved from https://www.amazon.com/Codebreakers–Inside–Story–Bletchley–Park/dp/0192801325/

Hoffstein, J. P. (1998). NTRU: A ring–based public key cryptosystem. Algorithmic Number Theory (pp. 267–288). Springer, Berlin, Heidelberg. doi:https://doi.org/10.1007/BFb0054868

Hofheinz, D. K. (2017). A Modular Analysis of the Fujisaki–Okamoto Transformation. Cryptology ePrint Archive. Retrieved from https://eprint.iacr.org/2017/604

Houck, A. A. (2009). Life after charge noise: recent results with transmon qubits. Quantum Information Processing, 105–115. doi:10.1007/s11128–009–0100–6

Houston–Edwards, K. (Writer), & Series, P. I. (Director). (2017a). How to Break Cryptography [Motion Picture]. Youtube. Retrieved from https://www.youtube.com/watch?v=12Q3Mrh03Gk

Houston–Edwards, K. (Writer), & Series, P. I. (Director). (2017b). Hacking at Quantum Speed with Shor’s Algorithm [Motion Picture]. Youtube. Retrieved from https://www.youtube.com/watch?v=wUwZZaI5u0c

HPC Wire. (2022, September 27). Quantinuum Sets New Record with Highest Ever Quantum Volume. Retrieved November 14, 2022, from HPC Wire: https://www.hpcwire.com/off–the–wire/quantinuum–sets–new–record–with–highest–ever–quantum–volume/

Hülsing, A. (2017, December 4). SPHINCS+ – The smaller SPHINCS. Retrieved from Andreas Hülsing: https://huelsing.net/wordpress/?p=558

Hülsing, A. J. (2017). NTRU–HRSS–KEM lgorithm Specifications And Supporting Documentation. Retrieved from https://cryptojedi.org/papers/ntrukemnist–20171130.pdf

IBM. (2018). Coming soon to your business – Quantum computing. Armonk: IBM Institute for Business Value. Retrieved from https://www.ibm.com/downloads/cas/OV1V0NLX

IBM. (2022, October 23). Entanglement. Retrieved from IBM Quantum Composer: https://quantum–computing.ibm.com/composer/docs/iqx/guide/entanglement

IBM Quantum. (2022, October 20). Shor’s algorithm. Retrieved from IBM Quantum Composer: https://quantum–computing.ibm.com/composer/docs/iqx/guide/shors–algorithm

Intel. (2015, September 3). Intel Invests US$50 Million to Advance Quantum Computing. Retrieved November 7, 2022, from Intel: https://newsroom.intel.com/news–releases/intel–invests–us50–million–to–advance–quantum–computing/

Jenkins, A. J. (2022). Ytterbium Nuclear–Spin Qubits in an Optical Tweezer Array. Physical Review, 021027. doi:10.1103/PhysRevX.12.021027

Jiang, H. Z. (2017). IND–CCA–secure Key Encapsulation Mechanism in the Quantum Random Oracle Model, Revisited. Cryptology ePrint Archive. doi:10.1007/978–3–319–96878–0_4

Josephson, B. D. (1962). Possible new effects in superconductive tunnelling. Phys. Lett., 251–253. doi:10.1016/0031–9163(62)91369–0

Josephson, B. D. (1974, March). The discovery of tunnelling supercurrents. Bulletin of the European Physical Society, 5, pp. 251–254. Retrieved from https://www.europhysicsnews.org/articles/epn/pdf/1974/03/epn19740503p1.pdf

Kerckhoffs, A. (1883). La cryptographie militaire. Journal des sciences militaires, 5–83. Retrieved from https://www.petitcolas.net/kerckhoffs/crypto_militaire_1_b.pdf

Khan, D. (1996). The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet. Scribner. Retrieved from https://www.amazon.com/Codebreakers–Comprehensive–History–Communication–Internet/dp/0684831309

Khan, S. (2013). The Euclidean Algorithm. Retrieved from Khan Academy: https://www.khanacademy.org/computing/computer–
science/cryptography/modarithmetic/a/the–euclidean–algorithm

Khan, T. M., & Robles–Kelly, &. A. (2020). Machine Learning: Quantum vs Classical. IEEE Access, 8, 219275–219294. doi:10.1109/ACCESS.2020.3041719

Kwiatkowski, K. (2019, June 20). Towards Post–Quantum Cryptography in TLS. Retrieved November 6, 2022, from The Cloudflare Blog: https://blog.cloudflare.com/towards–post–quantum–cryptography–in–tls/

Langlois, A. &. (2012). Worst–Case to Average–Case Reductions for Module Lattices. Cryptology ePrint Archive. Retrieved from https://eprint.iacr.org/2012/090

Le Bellac, M. (2006). A Short Introduction to Quantum Information and Quantum Computation. Cambridge University Press. Retrieved from https://www.amazon.com/Short–Introduction–Quantum–Information–Computation/dp/0521860563/

Lenstra, A. K. (1993). The Development of the Number Field Sieve (1 ed.). Heidelberg: Springer–Verlag. doi:https://doi.org/10.1007/BFb0091534

Loss, D. a. (1998). Quantum computation with quantum dots. Physical Review, 57, 120–126. doi:10.1103/PhysRevA.57.120

Luciano, D. &. (1987). Cryptology: From Caesar Ciphers to Public–Key Cryptosystems. The College Mathematics Journal, 2–17. doi:10.2307/2686311

Lyubashevsky, V. (2009). Fiat–Shamir with Aborts: Applications to Lattice and Factoring–Based Signatures. Lecture Notes in Computer Science. 5912, pp. 598–616. Springer. doi:https://doi.org/10.1007/978–3–642–10366–7_35

Lyubashevsky, V. C. (2013). On Ideal Lattices and Learning with Errors over Rings. Association for Computing MachineryAssociation for Computing Machinery. doi:10.1145/2535925

Manohar, N. (2016, March 21). Hardness of Lattice Problems for Use in Cryptography. Cambridge: the School of Engineering and Applied Sciences Harvard University. Retrieved from https://web.cs.ucla.edu/~nmanohar/nmanohar_files/UndergradThesis.pdf

Manucharyan VE, K. J. (2009). Fluxonium: single cooper–pair circuit free of charge offsets. Science, 113–116. doi:10.1126/science.1175552. PMID: 19797655

Martinez, J. (2022). Decoherence and Quantum Error Correction for Quantum Computing and Communications. doi:10.15581/10171/63013

McEliece, R. J. (1978). A Public–Key Cryptosystem Based on Algebraic Coding Theory. DSN Progress Report, 114–116. Retrieved from https://tmo.jpl.nasa.gov/progress_report2/42–44/44N.PDF

Mermin, D. (2006, March 28). Breaking RSA Encryption with a Quantum Computer: Shor’s Factoring Algorithm. Physics 481–681 Lecture Notes. Cornell University. Retrieved from https://web.archive.org/web/20121115112940/http://people.ccmr.cornell.edu/~mermin/qcomp/chap3.pdf

Metcalfe, M., Boaknin, E., Manucharyan, V., Vijay, R., Siddiqi, I., Rigetti, C., . . . Devoret, M. H. (2007). Measuring the decoherence of a quantronium qubit with the cavity bifurcation amplifier. Physical Review B., 174516. doi:10.1103/PhysRevB.76.174516

Middleton, C. (2021, March 5). What’s under the hood of a quantum computer? Retrieved November 6, 2022, from Physics Today: https://physicstoday.scitation.org/do/10.1063/PT.6.1.20210305a/full/

Moreno–Pineda, E. C. (2017). Molecular Spin Qudits for Quantum Algorithms. Chemical Society Reviews. doi:10.1039/C5CS00933B

Nakamura, Y. Y. (1999). Coherent control of macroscopic quantum states in a single–Cooper–pair box. Nature, 786–788. doi:https://doi.org/10.1038/19718

Nayuki. (2022, September 11). Number–theoretic transform (integer DFT). Retrieved from Project Nayuki: https://www.nayuki.io/page/number–theoretic–transform–integer–dft

Nechvatal, J. E. (2001). Report on the Development of the Advanced Encryption Standard (AES). Journal of Research of the National Institute of Standards and Technology, 106, 511–577. Retrieved from https://nvlpubs.nist.gov/nistpubs/jres/106/3/j63nec.pdf

Nguyen, P. Q. (2010). Hermite’s Constant and Lattice Algorithms. In The LLL Algorithm: Survey and Applications (pp. 19–69). Heidelberg: Springer. doi:https://doi.org/10.1007/978–3–642–02295–1

Nielsen, M. A. (2011). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press. Retrieved from https://www.amazon.com/Quantum–Computation–Information–10th–Anniversary/dp/1107002176

Nielsen, M. A., & Chuang, I. (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press.

NIST. (1977). Data Encryption Standard. National Institute of Standards and Technology. Retrieved from https://csrc.nist.gov/CSRC/media/Publications/fips/46/archive/1977–01–15/documents/NBS.FIPS.46.pdf

NIST. (1988). Data Encryption Standard. National Institute of Standards and Technology. Retrieved from https://csrc.nist.gov/CSRC/media/Publications/fips/46/1/archive/1988–01–22/documents/NBS.FIPS.46–1.pdf

NIST. (1993). Data Encryption Standard. National Institute of Standards and Technology. Retrieved from https://csrc.nist.gov/publications/detail/fips/46/2/archive/1993–12–30

NIST. (1999). Data Encryption Standard. National Institute of Standards and Technology. Retrieved from https://csrc.nist.gov/publications/detail/fips/46/3/archive/1999–10–25

NIST. (2001). Announcing the Advanced Encryption Standard (AES). National Institute of Standards and Technology. Federal Information Processing Standards Publication 197. Retrieved from https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.197.pdf

NIST. (2022a, July 5). Projects: Post Quantum Cryptography. Retrieved from National Institute of Standards and Technology: https://csrc.nist.gov/Projects/post–quantum–cryptography

NIST. (2022b, July 15). NCCoE Announces Technology Collaborators for the Migration to Post–Quantum Cryptography Projec. Retrieved November 6, 2022, from National Cybersecurity Center of Excellence: https://content.govdelivery.com/accounts/USNIST/bulletins/31f0b39

Olson, B. J. (2014). Circulant Matrices and Their Application to Vibration Analysis. Applied Mechanics Reviews. doi:https://doi.org/10.1115/1.4027722

Papadimitriou, C. (1993). Computational Complexity. Pearson.

Parker, E. (2021). Commercial and Military Applications and Timelines for Quantum Technology. RAND Corporation. doi:https://doi.org/10.7249/RRA1482–4

Peikert, C. (2009). Public–Key Cryptosystems from the Worst–Case Shortest Vector Problem. Proceedings of the Forty–First Annual ACM Symposium on Theory of Computing (pp. 333–342). Bethesda: Association for Computing Machinery. doi:10.1145/1536414.1536461

Piot, N. B.–U. (2022). A single hole spin with enhanced coherence in natural silicon. Nature Nanotechnology, 1072–1077. doi:https://doi.org/10.1038/s41565–022–01196–z

Qiskit. (2022a, 10 20). Quantum computing in a nutshell. Retrieved from Qiskit: https://qiskit.org/documentation/qc_intro.html

Qiskit. (2022b). Quantum Fourier Transform. Retrieved from https://qiskit.org/textbook/ch–algorithms/quantum–fourier–transform.html

Qiskit. (2022c). Shor’s Algorithm. Retrieved from Qiskit: https://qiskit.org/textbook/ch–algorithms/shor.html

Rackoff, C. &. (1992). Non–Interactive Zero–Knowledge Proof of Knowledge and Chosen Ciphertext Attack. Lecture Notes in Computer Science (pp. 433–444). Heidelberg: Springer. doi:https://doi.org/10.1007/3–540–46766–1_35

Ramanandan, S. P. (2022). Coherent Hole Transport in Selective Area Grown Ge Nanowire Networks. Nano Letters, 4269–4275. doi:https://doi.org/10.1021/acs.nanolett.2c00358

Regev, O. (2005). On lattices, learning with errors, random linear codes, and cryptography. Proceedings of the thirty–seventh annual ACM symposium on Theory of computing (STOC ’05) (pp. 84–93). New York: Association for Computing Machinery. doi:10.1145/1060590

Regev, O. (2005). On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. Proceedings of the thirty–seventh annual ACM symposium on Theory of computing (pp. 84–93). New York: Association for Computing Machinery. doi:10.1145/1060590.1060603

Rivest, R. A. (1978). A Method for Obtaining Digital Signatures and Public–Key Cryptosystems. Communications of the ACM, 120–126. doi:10.1145/359340.359342

Rolston–Duce, K. (2022, April 14). Quantinuum Announces Quantum Volume 4096 Achievement. Retrieved November 14, 2022, from Quantinuum: https://www.quantinuum.com/pressrelease/quantinuum–announces–quantum–volume–4096–achievement#

Roth, T. E. (2021). An Introduction to the Transmon Qubit for Electromagnetic Engineers. IEEE Antennas and Propagation Magazine, 2–14. doi:10.1109/MAP.2022.3176593

RSA Laboratories. (1999). RSA Security Inc. Public–Key Cryptography Standards (PKCS. Bedford. Retrieved from http://www.di–srv.unisa.it/~ads/corso–security/www/CORSO–9900/oracle/pkcsv21.pdf

Ryan–Mosley, T. J. (2019, May 30). How a quantum computer could break 2048–bit RSA encryption in 8 hours. Retrieved November 6, 2022, from MIT Technology Review: https://www.technologyreview.com/2019/05/30/65724/how–a–quantum–computer–could–break–2048–bit–rsa–encryption–in–8–hours/

Saki, A. A. (2019). Study of Decoherence in Quantum Computers: A Circuit–Design Perspective. Retrieved from https://arxiv.org/abs/1904.04323

Schneiderman, J. F. (2007). Quasiparticle Poisoning and Quantum Coherence in a Differential Charge Qubit. Retrieved from https://arxiv.org/abs/0705.0695

Schreyvogel, C. P. (2015). Active charge state control of single NV centres in diamond by in–plane Al–Schottky junctions. Scientific reports, 12160. doi:https://doi.org/10.1038/srep12160

Shafeeq, M. (2022, August 31). Emerging Potential of Quantum Computing. Retrieved from Modern Diplomacy: https://moderndiplomacy.eu/2022/08/31/emerging–potential–of–quantum–computing/

Shankland, S. (2021, May 24). Quantum computers could crack today’s encrypted messages. That’s a problem. Retrieved November 6, 2022, from CNET: https://www.cnet.com/tech/computing/quantum–computers–could–crack–todays–encrypted–messages–thats–a–problem/

Shannon, C. E. (1949). Communication Theory of Secrecy Systems. The Bell System Technical Journal, 28, 656–715. doi:10.1002/j.1538–7305.1949.tb00928.x

Shor, P. W. (1994). Algorithms for Quantum Computation: DIscrete Logarithms and Factoring. IEEE Computer Society, 124–134. doi:10.1109/SFCS.1994.365700

Shuo Ma, A. P. (2022). Universal Gate Operations on Nuclear Spin Qubits in an Optical Tweezer Array of Yb171 Atoms. Physical Review, 021028. doi:10.1103/PhysRevX.12.021028

Singh, S. (1999). The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. Anchor. Retrieved from https://www.amazon.com/Code–Book–Science–Secrecy–Cryptography/dp/0385495323/

Sipser, M. (2014). Introduction to the Theory of Computation (3 ed.). Cengage.

Smith–Goodson, P. (2019, November 23). Quantum Volume: A Yardstick To Measure The Performance Of Quantum Computers. Retrieved November 14, 2022, from Forbes: https://www.forbes.com/sites/moorinsights/2019/11/23/quantum–volume–a–yardstick–to–measure–the–power–of–quantum–computers/?sh=3cc5f8dd5bf4

Stallings, W. (1990). Cryptography and Network Security: Principles and Practice. Prentice Hall.

StartUs Insights. (2020, June). 5 Top Emerging Quantum Cryptography Solutions. Retrieved from StartUs Insights: https://www.startus–insights.com/innovators–guide/5–top–emerging–quantum–cryptography–solutions/

Stehlé, D. R. (2009). Efficient Public Key Encryption Based on Ideal Lattices. Lecture Notes in Computer Science (pp. 617–635). Tokyo: Springer. doi:10.1007/978–3–642–10366–7_36

Stroud, C. R. (1972). Superradiant Effects in Systems of Two–Level Atoms. Phys. Rev., 1094–1104. doi:https://doi.org/10.1103/PhysRevA.5.1094

Sylvester, J. (1867). Thoughts on inverse orthogonal matrices, simultaneous sign successions, and tessellated pavements in two or more colours, with applications to Newton’s rule, ornamental tile–work, and the theory of numbers. Philosophical Magazine, 461–475.

Tinkham, M. (1986). Introduction to superconductivity. Medtech. Retrieved from https://www.amazon.com/Introduction–Superconductivity–Michael–Tinkham/dp/9385998730/

Toom, A. (1963). The Complexity of a Scheme of Functional Elements Realizing the Multiplication of Integers. Soviet Mathematics–Doklady, 714–716. Retrieved from http://toomandre.com/my–articles/engmat/MULT–E.PDF

Tracxn. (2022, October 12). Top Quantum Computing in Cybersecurity Startups. Retrieved from Tracxn: https://tracxn.com/d/trending–themes/Startups–in–Quantum–Computing–in–Cybersecurity

Turing, A. M. (1942). Turing’s Treatise on the Enigma. Retrieved from https://www.archives.gov/files/press/press–releases/2015/images/turing–enigma–treatise.pdf

Turing, A. M. (1986). A.M. Turing’s ACE report of 1946. In A.M. Turing’s ACE report of 1946 and other papers. Retrieved from https://mitpress.mit.edu/9780262031141/a–m–turings–ace–report–of–1946–and–other–papers/

Turing, A. M. (2004). Intelligent machinery. In B. Copeland (Ed.), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma (pp. 395–432). Clarendon Press. Retrieved from https://www.amazon.com/Essential–Turing–Philosophy–Artificial–Intelligence/dp/0198250800/

van Emde Boas, P. (1981). Another NP–complete problem and the complexity of computing short vectors in a lattice. Amsterdam: University of Amsterdam, Department of Mathematics.

van Leeuwen, J. (1994). Handbook of Theoretical Computer Science. The MIT Press. Retrieved from https://www.amazon.com/Handbook–Theoretical–Computer–Science–Vol/dp/0262720205

Vandersypen, L. M. (2019). Quantum computing with semiconductor spins. Physics Today, 38–45. doi:https://doi.org/10.1063/PT.3.4270

Wang, K. X. (2022). Ultrafast coherent control of a hole spin qubit in a germanium quantum dot. Nature Communications. doi:https://doi.org/10.1038/s41467–021–27880–7

Wang, R. D. (2019). Gate Tunable Hole Charge Qubit Formed in a Ge/Si Nanowire Double Quantum Dot Coupled to Microwave Photons. Nano Letters, 1052–1060. doi:https://doi.org/10.1021/acs.nanolett.8b04343

Watzinger, H. J.–J. (2018). A germanium hole spin qubit. Nature Communications. doi:10.1038/s41467–018–06418–4

Wie, C.–R. (2020). Two–Qubit Bloch Sphere. Physics, 383–396. doi:https://doi.org/10.3390/physics2030021

Wolfowicz, G. &. (2016). Pulse Techniques for Quantum Information Processing. eMagRes, 5, 1515–1528. doi:10.1002/9780470034590.emrstm1521

Zhou, J. J. (2010). Extended Euclid algorithm and its application in RSA. The 2nd International Conference on Information Science and Engineering, (pp. 2079–2081). doi:10.1109/ICISE.2010.5691644

Zimmermann, P. (2020, February 28). Factorization of RSA–250. Universite de Lorraine, Nancy. Retrieved from https://listserv.nodak.edu/cgi–bin/wa.exe?A2=NMBRTHRY;dc42ccd1.2002