john31415926

There is general agreement that hash-based signatures will be an important root of trust since they have well-understood security properties. This would give you the ability to do secure updates as we learn more about the security of various algorithms and the progress of quantum computing.

We like the lattice-based approaches such as NewHope and Frodo. The arithmetic is very simple, even if the sizes are a bit large and the error distributions a little mysterious to mere mortals.

It will require new algorithms. For something like Bitcoin, you need secure signatures and there are well-understood hash-based solutions.

For example, there is a Quantum Resistant Ledger

From an intuitive view, NP-complete problems don't generically work because it seems like you need some extra structure like commutativity or a trapdoor to make a key-agreement or key-encryption scheme. When you add the extra structure, you may end up in a subclass that is weaker than expected. Historically, this has happened quite often, knapsack problems being one example.

The other issue is asymptotic versus concrete security. You have to fix parameters for a crypto scheme in such a way that it is efficient, both in terms of time and space. Then, you have to carefully cost how long it will take various algorithms to solve the problem. For example, SAT is the canonical NP-complete problem, but there has been a lot of active research on better algorithms and heuristics and also faster implementations.

Right now, there are open questions on both the asymptotic security of new assumptions, eg, the supersingular isogeny scheme (an earlier non-supersingular variant was broken) and also the concrete parameter choices, eg, lattice dimensions.

Since you have a good background already, I'd really suggest diving into the research literature! It's ok to skip the hard parts. As an applied researcher, skimming is a very valuable skill.

For example, take a look at the New Hope paper. You can work through the polynomial arithmetic and the overall protocol without much mathematics. The hard part is the error distributions, but me, and probably a lot of other people, are skipping that too :)

Regarding cryptanalysis, it's still a very active area! Especially with all the new post-quantum algorithms, there's a lot of work to be done in the theory area.

Yes. First, symmetric key cryptography is not as severely impacted as public key cryptography. Mainly you'll have to double your key size, e.g., from AES-128 to AES-256. So, in the worst case, we could find ways to distribute keys out-of-bands, e.g., a secure token for Amazon, Facebook, etc. Second, public key signatures are possible using hash-based signature algorithms.

The main challenge is public key encryption and agreement, i.e., the replacements for RSA and Diffie-Hellman. There are several leading contenders for new hard problems, including problems based on lattices, codes, multivariate polynomials.

Google was recently able to test NewHope, a lattice-based scheme on a wide scale and the results were promising.

So, in theory, we think it's possible, but there's still a lot of work left to select particular candidates and get them through the standardization process. See in particular NIST's current efforts.