[CaliforniaKarl]

Asymmetric crypto (RSA, curve25519, etc.) and Diffie-Hellman (including ECDH) are both in danger, thanks to Shor’s algorithm. I think the only thing remaining is large-enough quantum computers.

If I remember correctly, hashes and symmetric crypto are generally safe, and so those recommendations shouldn’t change.

[AgentME]

The effective keysize for symmetric crypto can be cut in half by quantum computers by Grover's algorithm, so just make sure you use 256-bit keys rather than 128-bit keys.

[dsacco]

> I think the only thing remaining is large-enough quantum computers.

That’s a very, very big “only” :).

In any case, there are several compelling computational problems which are (as of current research) post-quantum resistant. They’re based on lattices, error correcting codes, hashes, multivariate polynomials and supersingular elliptic curve isogenies (the latter one being the hot new thing).

Each of those problems has at least a few (but generally many) viable contenders for actual cryptography. Hashes give us very nice signatures, from old-school Winternitz one time signature to merkle trees to current frontrunners like SPHINCS (and its variants). Unfortunately hash-based cryptography can only be used for signatures so far, but they really excel at that.

The ring-LWE problem (and more generally, module-LWE) in lattice cryptography is pretty versatile: we can get fast encryption, signature and encapsulation schemes. The tradeoff is that key sizes run larger. But there is a lot of research into provable security in average-case and worst-case lattice assumptions. The NTRU problem is the other large “school” of lattice cryptography, which mostly has the same problem: very fast, but with larger key sizes.

Error correcting codes give us fewer computational problems to work with than lattices (essentially general decoding and syndrome decoding), but they are extremely well-studied. McEliece remains secure (for binary Goppa codes), which is incredible because it was published only two years after the notion of Diffie-Hellman PKE. Unfortunately most types of error correcting codes are not suitable for cryptography because they have excessive structure. We’ve been mostly stuck with binary Goppa codes for 40 years, though there is exciting work on quasi-cyclic and quasi-dyadic codes in the NIST PQ CFP. Otherwise, similar story as lattices: relatively fast, but very large key sizes.

Isogenies are extremely new and only have a few credible cryptosystems based on them. The most prominent researchers leading this domain are Jao, Longa, de Feo, Plut and Galbraith. The two contenders are SIDH and the NIST proposal succeeding it, SIKE. These have the opposite advantage to lattices and codes, because their key sizes are incredibly small (the smallest among all post-quantum cryptosystems), but their key exchange time is commensurately slower. The additional benefit is that they use much of the same mathematics as traditional elliptic curves, which means you could design hybrid ECDH-like and SIDH-like schemes with a relatively small library.

There are some wonkier proposals (such as Joux’s Mersenne prime one), but these are the ones receiving the most research attention. I wouldn’t say it’s a solved problem, but I’m personally confident there will be mature cryptography available when quantum computers can practically break our current state of the art.