An Introduction to Post-Quantum Cryptography

 

 

 Recently an announcement was made by IBM announcing a 433 qubit quantum computer. In lieu of this I've put a bit more effort into my blog today in addressing a field I am quite proficient in, post-quantum cryptography. This blog post should serve as an introduction to the field for anyone of any skill level or knowledge level of the topic. 

                                    

 

 

An Introduction to Post-Quantum Cryptography

Introduction


Post-quantum cryptography is the name given to the field of study involving cryptography protocols that are resistant to a theoretical adversary in possession of a working large-scale quantum computer. Post-quantum cryptography that can be run on classical hardware is a relatively new field, and arose primarily as a response to the contingencies posed to cryptography through efficiently employing Shor’s algorithm. While Shor’s algorithm does provide one of the most formidable risks to current RSA cryptography protocols, it is not the only contingency a quantum computer would pose for contemporary internet security protocols. For an explanation of these contingencies, and a brief technical overview of the fields of quantum computing and cryptography, please read the article I've written on it here.


Post-quantum cryptography could be said to fall into two fields. The first involves cryptographic protocols employed on a classical computer that are resistant to an attack by a quantum computer using a known algorithm. The second revolves around protocols that make use of peculiar properties and effects known in quantum mechanics, such as the no-cloning theorem. An example of the former would be an encryption scheme employing lattices instead of large integers; known as lattice based cryptography. While an example of the latter would be the BB84 encryption protocol that relies on the no-cloning theorem when applied to multiple entangled states.


Lattice based cryptography was first proposed as a workable cryptographic protocol in 1996, when Miklós Ajtai introduced the first lattice-based cryptographic construction whose security could be based on the complexity of well-studied lattice problems. BB84 encryption was developed in 1984 by Charles Bennett and Giles Brassard, and involves multiple entangled qubits that are sent from one party to another. By the rules of quantum mechanics, if an outside observer tries to intercept and read the message it will disturb the state of entanglement and make the message unreadable.


This article will primarily focus on cryptographic protocols that can be employed on classical hardware, though there is certainly much to be said about cryptographic protocols that can only be run on quantum hardware. The quantum internet - if infrastructure is one day set in place in which networks of quantum computers can communicate much like classical computers do now - could easily make use of cryptographic protocols such as BB84. Such a quantum internet would relay information securely leagues ahead of any method currently available on classical hardware, without almost any possibility of outside interception and decryption.


The quantum internet is probably decades away, and so in the meantime classical computers will have to make do with currently extant and developing methods in the case of individual entities gaining access to such hardware. This article will primarily focus on a few families of methods that may hold as contenders to be resistant to methods employed by quantum computers, and then follow up with conclusions and implications for security in the blockchain space and beyond. There are other methods than what will be discussed in each section, and some of these will be glossed over, but it must be said as a disclaimer that this relatively new field is in a constant state of flux currently as methods old and new are tried and fried.


As with the last article in the series, here is a small glossary for some of the terms as they shall be used in this article, if you are already familiar with them feel free to skip ahead to the next section.


Lattice: A repeating multidimensional pattern of data, atoms, molecules, metal or any other sort of “stuff” that forms a crystalline solid. A regularly spaced grid of points going out infinitely in any direction could also be thought of as a lattice.


Vector: A direction as well as magnitude. A set of points that determine the position of one point in space relative to another.


Basis Vector: The designation for a special type of vector that can be used to replicate any part of an infinite lattice using a finite amount of memory.


Trapdoor Function: A function that is easy to compute in one direction, yet difficult to compute in the opposite direction (finding its inverse) without special information, called the "trapdoor".

Trapdoor functions can form the basis of public key asymmetric cryptography in which private keys can be used to “unlock” information hidden in public keys.


NP-hard: A problem is NP-hard if an algorithm for solving it can be translated into one for solving any NP-problem (nondeterministic polynomial time) problem. Perhaps more simply put, an NP-hard problem is a problem that could be considered to take exponentially many steps to get an answer to.






Lattice based cryptography


Of the various cryptographic systems that shall be expounded upon in this article, perhaps one of the largest contenders for what will eventually replace RSA is lattice based cryptography. While RSA relies upon the computational intractability for the problem of finding the prime factors of very large integers, lattice cryptography relies upon the intractability of finding certain properties of a specified lattice that can be used to create a trapdoor function then utilized to create a public key cryptosystem. As of this writing, there are currently no known quantum algorithms for solving lattice problems that perform significantly better than the best known classical algorithms.


Lattice based cryptography, unlike RSA cryptography, appears to be resistant to outside decryption by both quantum computers and classical computers. Many constructions seem to rely upon the inherent intractability of computational lattice problems that cannot be solved efficiently by any currently known methods. A big question one could ask is, will this change one day? This train of thought eventually leads back to the famously posed (and still unsolved) complexity theory question of whether P = NP.


In regards to this, until such a definite answer to the P = NP problem can be found, nearly ANY cryptographic protocol that has been or ever will be created has the possibility of being rendered obsolete by some newly discovered efficient decryption method. Until then, the best any cryptographic protocol can do is work with the knowledge and assumptions that are currently available to them in their construction. However, the more concrete and tested the better. In light of this, lattice problems are some of the most rigorously tested and understood family of hard mathematics problems available.


So, how does lattice based cryptography work? As stated earlier, it is based upon an intractable problem, except unlike RSA which involves factoring large integers it involves finding some property of a lattice. There are different problems that some forms of lattice cryptography rely upon, and as such many different types of protocols can be built up from them. For this article, the example we shall focus on will be based on the Closest Vector Problem and a resultant public key cryptographic protocol that can be built with it.


The closest vector problem can be described simply as this: Given a certain number of basis vectors b used to construct a lattice, and a target vector t, find the lattice point closest to the target vector. Another way to say this is that given a set of values you can use to construct a regularly spaced out grid of points and a target value, find the point on this grid closest to the target value.


For some lattices this is a trivial problem, but we are not bound by 2 or even 3 dimensions when defining the lattice, and the angles between points can be completely random. Given a 10,000 dimensional lattice (which is actually sometimes used in lattice cryptography) finding the answer to this problem can become intractable for even a quantum computer.


Perhaps if I gave you some simple table salt (NaCl) which forms a cubic lattice and then within the table salt lattice I added a single impurity, which sodium and chloride atoms would then be closest to this impurity? This could be looked at as a similar problem to the closest vector problem.


There are a few ways to form a public key cryptography protocol using the Closest Vector Problem, one example is through the GGH/HNF public key cryptosystem. It should be said that this is shown as an example of how one could create a cryptographic protocol using lattice cryptography and is not meant to highlight a replacement for RSA. But rather to demonstrate an example of how by using lattice cryptography one could construct a public key cryptographic protocol. The following is heavy on mathematics, so if you are not interested in this aspect feel free to skip the next few paragraphs.


To begin with, you have two parties, Alice and Bob. Alice has a private key which in this case takes the form of a basis for a lattice, B. The private key basis B is formed such that the basis vectors are quite close to a target value v, while the public key H is formed from basis vectors far away from v. This is a basic formulation of public key lattice cryptography utilizing the closest vector problem. Below is described a version of this called the GGH/HNF scheme.


While the private key takes the form of a “good” basis B, the public key then takes the form of a “bad” basis H describing the same lattice L, L(B) = L(H). The public key H is constructed such that an encrypted message is hidden within a noise vector r added to the point v which is selected appropriately, and that all vectors are selected such that all the coordinates of (r + v) are reduced modulo the corresponding element along the diagonal of the public basis H.


Since we now have public and private key pairs as well as encrypted information, the important part then would be how could Bob decrypt the information hidden within the public key.

(r + v) = r mod H = c, c being the target ciphertext. To find the hidden information r = v - c, one must first find v. The vector v can be found using the private key lattice, v = B[ B-1 (v + r)]. From this you can securely construct cryptographic protocols under the assumption that L(B) = L(H) where L is the same lattice formed from the associated different basis vectors is NP-hard to find using any optimized algorithm, quantum or classical.


All right, that might have been a lot of math to process. I’ll try to explain it in another way. You can describe a lattice or crystalline structure in multiple different ways, if you have a complicated multidimensional lattice made up of thousands of dimensions and repeating patterns within it, two descriptions of the lattice using basis vectors might vary widely in terms of how useful these basis vectors could be in describing a single point relative to the lattice.


With one description of the lattice, the “private key” can easily find this single point relative to the lattice, which with the “public key” description of the lattice would be hard to find. Finding the “private key” description of the lattice from the “public key” description of the lattice is meant to be difficult and intractable; much like finding the prime factors of a large integer is also meant to be infeasible using current RSA protocols. Though lattice based cryptography has the advantage of also being difficult for a quantum computer to find solutions quickly.


This public key protocol is only one type of protocol based off of lattice cryptography. There are other protocols one can construct based on the closest vector problem as well as other well known lattice problems, such as the shortest vector problem that one can also base a whole host of other protocols over.


Lattice based cryptography opens up a whole avenue of possibilities for fully homomorphic encryption standards. Amongst the field of post-quantum cryptography, lattice cryptography by far seems to hold the record for the largest number of research papers compared to the other families of post-quantum cryptography. Lattice cryptography scales well in some cases, as well as having protocols boasting some of the shortest key sizes compared to other post-quantum families, making it less of a strain to implement on existing systems. Because of the volume of research compared to other cryptographic standards, lattice based cryptography is one of the easiest fields of post-quantum cryptography to dive deep into.


While lattice based cryptography holds many promising advantages, it is not without downsides. Even though the key sizes can be made smaller compared to some other methods, they are still larger than current RSA protocols. Sometimes when scaling protocols, this difference in key size can take up an astronomical amount of spacetime storage wise and so become hugely impractical. Though, some newer and developing methods hold promise at reducing this downside dramatically by exploring different problems and schemes.


It must also be mentioned that some lattice based cryptographic protocols, especially on a large scale, might be susceptible to attacks using classical computers. A form of the protocol described as an example above (GGH/HNF) should not be reliably used as a protocol. This isn’t to say that more secure lattice based cryptographic protocols don’t exist however. For the GGH scheme (very similar to the protocol described) it has been shown that every ciphertext reveals information about the plaintext used to generate it, from this the problem of decryption could be turned into a special closest vector problem much easier to solve than the general CVP. This is just to say that some forms of lattice based cryptography have later been shown to have vulnerabilities to classical computing decryption methods.


To summarize, lattice based cryptography is based on largely studied hard math problems involving lattices. Lattice based cryptography is incredibly versatile in terms of what it allows one to build for protocol schemes. Having also the largest number of research publications relating to it in comparison to other families of post-quantum cryptography means it could be easier to find niche or specialized applications to replace current security mechanisms. However, as a closing statement, it should be mentioned that the underlying math problems used in lattice cryptography are hard to solve on average. This is an important quality it shares with RSA encryption protocols, on average solving the prime integers of a number is going to be difficult.


So while there are a few downsides to using lattice based cryptography in place of conventional methods - mainly being spacetime storage for keys - the field is rapidly developing with newer technologies and methods becoming widely available. As added security against a quantum adversary, and simply looking at it as a much needed update to decades old cryptography standards, lattice based cryptography is definitely worth considering to replace current security infrastructure.


Multivariate Cryptography


Multivariate schemes provide the shortest signature among post-quantum algorithms and protocols. Compared to other post-quantum cryptography schemes, schemes based on multivariate problems can be much more efficient space and time wise. In terms of basing a public key protocol on, some of the most efficient and quick methods fall under the family of multivariate cryptography.


Multivariate cryptography is based on a field of computationally intractable hard math problems that involve more than one variable changing quantity. ‘Multi’ in this case means more than one and ‘variate’ means changing or varying; hence, multivariate. Multivariate problems hold promise in the field of post-quantum cryptography as it is possible to build fully homomorphic encryption protocols based on a class of NP-hard problems that can’t be efficiently solved with any classical or quantum algorithm currently known.


As stated in the last section, this is always subject to change. The research publications involving multivariate cryptography are fewer than lattice based cryptography, and so there is perhaps less insight into the possible ways it can be broken than lattice based cryptography, but current research seems to indicate it to be secure for cryptographic protocols.


As stated earlier, multivariate cryptography has some of the shortest key sizes of any post- quantum cryptography protocol. One of the main arguments against making the switch to post-quantum cryptography is that the key sizes are very large compared to current protocols. When some of the key signature sizes scale to be exponentially large in terms of storage, these become largely impractical to implement.


Multivariate cryptography reaches into many advanced fields of mathematics in constructing public key cryptosystems. From operator theory, to chaos theory, to group theory and many others. If you are interested in the mathematics in constructing a public key cryptosystem using Multivariate Quadratics, the following two paragraphs will provide a basic example. If you are not so mathematically inclined, you may skip ahead.


The private key for this type of protocol in this example consists of two affine transformations, S and T, and an easily invertible quadratic map P’. Together when inverted they can form a triple set that can be used to create signatures, (S-1, P’-1 ,T-1). This is the private key and can act as a trapdoor function due to the nature of the public key.


The public key is formed from a composition of the affine transformations and quadratic map. The public key is given as the composition S ⃘ P’ ⃘ T = P, which is meant to be hard to invert and hence where the security comes from. To send a message, simply hash it to form a vector y. To sign the message with your private key, the signature is defined as x = P-1(y) = T-1(P’-1( S-1(y))) which as you can see from earlier is from the triple private key. The receiver of the message, if they have the public key, simply checks P(x) = y and the protocol is complete.


The example above is simply to provide a basic mathematical example of how a multivariate public key crypto system could work, it is by no means wholly rigorous or meant to highlight a replacement for RSA. There are many specific types of multivariate public key cryptography, such as the rainbow scheme, or the unbalanced oil and vinegar scheme, which the rainbow scheme is based on. It is worthwhile to note that while current RSA encryption is based on a set of math problems dating back to the 18th and 17th century, whereas lattice cryptography is based on problems of the 18th and 19th. The problems involving multivariate cryptography are primarily in the domain of mathematical discoveries made in the 20th century.


The basis of the security of multivariate cryptography stems from the difficulty of calculating systems of mathematical chaos. By utilizing a quadratic map in constructing the public and private keys, you introduce a system of equations that while relatively simple and easily described (see Kolmogorov complexity and chaos theory), are highly sensitive to initial conditions. Thus, these equations lend themselves to be hard to predict and hard to invert without hidden trapdoor information.


Multivariate public key cryptography as said before has some real potential in the field of post-quantum cryptography mainly due to it having some of the shortest key sizes compared to schemes based on other methods. This means it has much less of a downside in implementation for replacing existing cryptographic protocols. Its security is backed by the NP-hardness of the problem in solving nonlinear equations over a finite field, making it highly resistant to outside decryption by any known classical or quantum algorithm as of this writing.


While multivariate public key cryptography may show great promise in terms of smaller key sizes and relatively airtight security, there are certain downsides that should be worth mentioning. To begin with, while it certainly could also be looked at as a benefit, multivariate public key cryptography is based on hard math problems that for the most part are less studied than, for example, the hard math problems that the security of lattice based cryptography is founded on. This could mean it might be harder to use known algorithms to circumvent its security protocols in the future. In addition, because it is less studied there could be more unforeseen loopholes likely present themselves.


Lattice based cryptography holds a much larger repertoire of research publications than multivariate based cryptography. Implying multivariate cryptography might be harder to not only understand but also more difficult to implement into niche systems. Multivariate cryptography is versatile enough to construct a public key cryptographic protocol, and many more types of protocols, but lattice based cryptography certainly accommodates a larger number of schemes.


(As a math enthusiast I would like to make the personal comment that the mathematics involving multivariate cryptography is much more beautiful and interesting than the math foundations of any other post-quantum classical cryptography schemes)


On the surface, multivariate cryptography has many promising qualities. Perhaps the most prominent being the relatively small key signature sizes compared to other post-quantum cryptography schemes. The lack of research material compared to some other post-quantum cryptographic protocols might also mean it has a lot of opportunity for development; though might hinder its adoption as a standard. At its heart, it is based on the hardness of problems involving chaos theory, which is looked at as one of the current frontiers of classical mechanics. Perhaps, poetic that it could be adopted as a standard to defend against attacks involving quantum computers, which are based on the frontiers of quantum mechanics.

































Hash based, SSECI based, and other based forms of post-quantum cryptography.


Besides lattice and multivariate based post-quantum cryptography, there are many other types of cryptography that are considered to be secure against quantum and classical adversaries alike. This section will expound upon a few of these but will not provide comprehensive mathematical examples unlike the other sections, which were meant as a way to create a juxtaposition of two completely separate schemes that are known to be resistant to decryption by quantum adversaries. The two main types that shall be gone over in this section are Hash based and Supersingular Elliptic Curve Isogeny based cryptography schemes.


Hash based post-quantum cryptography involves, as the name suggests, cryptographic protocols that are based on creating public and private keys using secure hash functions. The difficulty to crack this type of cryptography primarily rests on the pre-image resistance of said hash functions. Using Grover’s algorithm, this aspect of security might be rendered vulnerable. However, there are protocols developed using Merkle hash trees (such as the Lamport-Diffie one time signature scheme) to create one-time signatures that are provably quantum resistant dependent on the height of a generated merkle tree.


One protocol called XMSS (eXtended Merkle Signature Scheme) is a hash based quantum resistant cryptography scheme that is currently used in the Quantum Resistant Ledger (QRL). The QRL is a decentralized blockchain cryptocurrency that essentially holds the same functionality of the bitcoin public ledger with the added bonus of being resistant to quantum adversaries as well as classical. Hash based cryptographic protocols are resistant to quantum adversaries, but still have a few downsides such as the possibility of low pre-image resistance and in some cases massive key sizes that can make it unwieldy to implement for certain applications.


Supersingular Elliptic Curve Isogeny based cryptography involves hard problems surrounding the isogenies of elliptic curves. Many current cryptographic protocols involve the difficulty of solving problems relating to elliptic curves, but this differentiates itself from this type of protocol by basing itself on mathematical problems involving the isogenies of separate types of elliptic curves. An isogeny is a morphism of algebraic groups. Another way to look at this class of problem is that it works by finding specific similarities between generated elliptic curves. These classes of hard math problems seem to hold promise in being resistant to both quantum and classical adversaries. Due to it being structurally similar to current RSA and elliptic curve cryptography already in use, it might be easier to implement in replacing existing cryptographic systems.


One such public key cryptographic protocol is known as the Supersingular Isogeny Diffie-Hellman Key Exchange (SIDH). SIDH involves an initial curve E in the corresponding supersingular isogeny graph, with shared secrets taking the form of unique isogenies with different degrees between two parties. This forms the basis of an asymmetric key exchange protocol that is so far quantum resistant. Some forms of SSECI based cryptography (such as SIDH) have the added benefit of forward secrecy, which is looked at as a major benefit for a cryptographic system in preventing outside surveillance. Its similarities to current cryptographic protocols are also an added bonus in that it might make a transition to this standard much easier to implement.


These are by far not the only types of post-quantum cryptography that have been developed or ever will be. Another scheme worth mentioning is McEleise (Code based) cryptography, which is based on the hardness of decoding a general linear code, which has protocols that are contenders by NIST along with multivariate and lattice based cryptography protocols to become the new cryptographic standard of the internet.


There are other types of post-quantum cryptography developed or perhaps yet to be developed, but so far the ones mentioned are the most well known families of them. Post-quantum cryptography is a tool. Like any tool, it has its certain applications and uses. It might be the case that one of the schemes mentioned in this article will become the general standard all future cryptographic security is based off of, but nonetheless it will probably be the case that some of these forms of cryptography will most likely find other, even if somewhat niche uses, elsewhere in the cryptoverse.





















Implications and Conclusions


So far this article has primarily provided a brief overview of the main families of post-quantum cryptography. While more attention has been given to Lattice and Multivariate cryptography, this is not meant to bias them as the primary contenders to replace current security protocols. It might be the case that there are other families and methods for cryptographic protocols that are also scalable and efficient that aren’t currently as well known. Hopefully by reading this article, you have more insight into how a post-quantum cryptography protocol would function in practice.


If anything should be stressed about post-quantum cryptography, it is perhaps that it should not be looked at as impractical merely because it has larger key sizes, or that any method that is quantum-proof would necessarily always entail large key sizes. This arises from perhaps one of the primary misconceptions on quantum computers, merely that they are simply faster hardware and not a completely separate paradigm of how to perform computation.


In a sense this is true, quantum computers will have massive computing potential, but the nuance here is that their exponential computational advantage is limited to specialized applications. Otherwise, quantum computers perform just as effectively as a digital classical computer for generalized computational applications. However, the specific applications that quantum computers excel at can have far reaching implications, such as using Shor’s algorithm to efficiently compute the prime factors of large integers and break RSA protocols, but if you want to play Crysis you are probably better off using a regular PC.


Post-quantum cryptography is a new and rapidly expanding field. The coming advent of quantum computers makes practical implementation of such protocols necessary. The process of replacing current security infrastructure is a daunting task that will take years to complete. Due to the time requirement, it is a process that should be started sooner rather than later. The future security of all telecommunications infrastructure depends on having up to date protocols in place.


Even if the future threat of quantum computers was many decades off from being realized, updating and revising cryptographic protocols every decade or so should be looked at as a necessary action to plug up any potential loopholes. Replacing security protocols will be costly and time consuming, but the alternative to this could prove ever more catastrophic. It is what it is, and with that being said I will close this article off from a quote from the Lord of the Rings by J.R.R. Tolkien:


“I wish it need not have happened in my time,” said Frodo. “So do I,” said Gandalf, “and so do all who live to see such times. But that is not for them to decide. All we have to decide is what to do with the time that is given us.”