Re: Encryption is complicated enough already
Yeah, I'm a mathematician.
I just tried to read the paper on SPHINCS, written by that Dan J Bernstein guy. I can't see the reasoning for something to be post-quantum-safe, to be honest. It's all described as being so, there's lots of proofs and algorithms written around it, but the actual reasoning for why it's post-quantum safe is dubiously obscured or absent.
It seems to hinge on hash-algorithms not being quantum-attackable but I can't see why that's a valid assumption if someone can build a large enough quantum computer. Presumably the number of items that COULD hash down to a tiny single hash are huge, so you don't know what was actually hashed to get that result.** ("A recent result by Song shows that these proofs are still valid for quantum adversaries")
The rest is about eliminating mid-states of the hash calculations - most hashes started with a number, and then each byte of data you incorporate gives you a new hash. You then use that hash to mix in with the next byte, and so on. Presumably "stateless" hashes don't have those intermediary hashes available, but it's not clear how. (I could be really wrong here, but it suggests that you compute a tree of keys for the size of the message you want to encrypt BEFORE you start, and each key is basically a one-time key used only for that particular part of that message. Then you encrypt each byte/word/whatever individually? It kinda makes sense, but I can't see what it adds, so long as the states are kept secret).
Basically, we just need one bad assumption ("Hashes are safe against quantum, while nothing else is") and the whole thing falls apart.
** This is how I analogise quantum computing, it's vastly inaccurate but it gives you the idea. If you are after, say, two large prime numbers that multiply out to a known number (the basis of public-key cryptography), then in traditional computing you have to basically try all the reasonable combinations until you hit the right one, which can take longer than the age of the universe.
In a quantum computer, you build the machine backwards. Here is a machine that multiplies two numbers, you design it to do so. Then you plug in the ANSWER you want. The magic of quantum effects then automatically provides you with the only state that could have possibly resulted in your desired state given the "circuits" you build and the condition you placed on the answer. Instantaneously.
Presumably a quantum computer, because there is only one right answer, is very good at breaking traditional prime-based public-key cryptography, but when it comes to hashes - well, an entire infinity of data sets could hash to the same value (just not EVERY data set), so just working from the hash backwards doesn't work - you don't gain any knowledge about the actual data that was hashed in the first place.
Thus building the core of encryption on thousands and thousands of tiny such hashes, it's possible that it makes the number of possibilities so vast, even with instantaneous discovery of every single one, that it becomes infeasible.
To me, though, if you had a large enough quantum computer, you could easily get those infinities of answer, and perform a known-plain-text attack and similar by pre-loading the circuits to take account of that as well. Much harder, but still theoretically breakable. I wouldn't know how much more complex, but maybe it does make it complex enough that it's infeasible. There's also talk of time-based hashed and other factors, which might well make it more difficult.
Note that all good encryption methods are immune to known-plaintext attacks.
Could be absolute tosh from a physics point of view, but it's an analogy that appears to work.