> But in any case, there’s already a push to switch to new cryptographic codes that already exist and that we think are quantum-resistant. An actual scalable Q

> But in any case, there’s already a push to switch to new cryptographic codes that already exist and that we think are quantum-resistant. An actual scalable QC on the horizon would of course massively accelerate that push. Wikipedia has a good review on major subdivisions of Post-Quantum Cryptography. * https://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography In short, in additional to integer factorization and (elliptic) discrete logarithm, there are a lot of others hard problems that can be used to construct public key encryption algorithms. * Lattice-based cryptography A "lattice" is a mathematical structure in abstract algebra. The study of it originally came from the theoretical analysis in solid-state physics on the structure of crystals, and can be understood as a matrix of evenly spaced "dots" in space. Formally, it's a discrete subgroup of an addictive group in an n-dimensional space. * * * * * * * * * * * * * * * * (This is a lattice) There exists several problems about them that are believed to be extremely difficult, called Lattice Problems. One well-known example is the Shortest Vector Problem: given a lattice L in vector space V and a norm N, find the shortest non-zero vector in V, measured by N, in L. There are fast approximate solutions, but under certain circumstances, this is an NP-hard problem, so we assume that we can construct a system, that is difficult to solve, although it's not HP-hard. NTRU is an algorithm that utilized a similar problem about lattice, proposed in 1997, no fundamental problems have been found in the original algorithm, so even after 20 years, it remains unbroken today. OpenSSH contains an implementation that you can use now today. But it requires LARGE (many KiB) public key - there's a large system of polynomials. Also, parameter selection is a question. * Learning With Errors (LWE) In theoretical machine learning, there's a problem called "Learning with Errors". I don't understand this problem well, but basically, we have a system of linear polynomial equations, but with random "noise". Solving this system of equations is believed to be extremely difficult. And interestingly, Oded Regev proved this problem is as difficult as some of the worst Lattice Problems. So LWE is considered a branch of Lattice-based Cryptography. There is also a variant of this problem, called Ring-RWE, which is more efficient for cryptography. Example includes Google's NewHope ciphersuits. Again, LARGE pubkey. * Multivariate cryptography Solving a system of polynomial equations with many variables in a finite field F, y1 = G1(x1, x2, x3) y2 = G2(x1, x2, x3) y3 = G3(x1, x2, x3) ... (G is a polynomial equation) is believed to be a difficult problem, and is NP-hard and NP-complete for a random system. And it has been proved that the case of solving a system of 2rd-order polynomial equations (quadratic equations) is already difficult enough, and this question is called the Multivariate Quadratic Problem. This fact can be used to construct public-key cryptography. However, because the system cannot be random, it's not NP-hard or NP-complete (there is no system that is NP-hard in the entire study of cryptography, otherwise, how do you decrypt it...), but we believe that we can construct a system that is difficult to solve practically. Unfortunately, attempts on creating public-key encryption algorithms is largely unsuccessful, but there are successful digital signature schemes, such as Oil and Vinegar. Again, LARGE pubkey. * Hash-based Cryptography This scheme is proposed by Ralph Merkle in the late 70s, and remains unbroken today. First, generate 2^n pairs of random public and private keys (X, Y), and hash all private keys, let's say we have 4 keypairs. Placing these hash values Y0, Y1, Y2, Y3 at the bottom of a binary tree as leaves. We connect and hash the two surrounding values to obtain the next layer (think blockchains), so hash (Y0 + Y1), hash (Y2 + Y3), and built the tree recursively until we reach the root. H(H(H(Y0) + H(Y1)) + H(H(H(Y2) + H(Y3))) ... 1 node ^ ^ H(H(Y0) + H(Y1)) H(H(Y2) + H(Y3)) ... 2 nodes ^ ^ ^ ^ H(Y0) H(Y1) H(Y2) H(Y3) ... 4 nodes To sign a message, simply select an unused keypair (X, Y) to create the signature. The signature also contains additional information to show that the (X, Y) can be traced to the root of the Merkle Tree (think Bitcoin Wallet?). It has been proved that the its security can be reduced to the security of the underlying hash function. XMSS is such a system, and there is already an RFC standard for it. OpenSSH contains an implementation that you can use now today. The problem is its large keysize and limited number of signatures, and more importantly, it's stateful. Key reuse is FATAL. DJB has an attempt to make a stateless version, called SPHINCS. * Code-Based Cryptography This approach uses the difficulties on decoding error-correction code. Decode a general linear code is NP-hard. First, select a system of code that is easy to decode for us, as the private key, and transform it to a obscured form, as the public key. A classic algorithm is McEliece, it's known since the late 70s, as old as the original Diffie-Hellman, and still remains unbroken today, but it uses binary Goppa codes which requires LARGE keys. * Supersingular Elliptic Curve Isogeny cryptography The math is even beyond description to a layman like me. Basically, "isogeny" is a mathematical structure in abstract algebra, and we can find a bunch of supersingular elliptic curve in the same isogeny, and use the property of this isogeny to encrypt data. Just like the ordinary elliptic curve cryptography, which we use a bunch of points on the same curve and use the property of this group to encrypt data. An example of such algorithm is SIDH, and it's a new candidate for post-quantum Diffie-Hellman exchange, but requires a lot more CPU time.