I've been thinking a bit lately about how to get quantum resistant signatures fast and (relatively) small.
One idea I've been keen on exploring is finding a crypto PRNG that allows fast-forwarding, e.g. Calculating what the hash will be N states in the future, without the ability of moving backwards.
The grand idea being, with a large fast-fowardable sequence generator, start with random-generated state A (private key), fast forward 2^256 states to get the public key. To sign, you would give a state in the middle, which when iterated N steps ( where N==H==the hash value of the data you're signing) forward to equal the public key. You would need to repeat this with a second private/public pair with N=(2^256-H) to prove the H is correct.
The lovely thing about that of course is your public key could be 32 bytes long (the hash of the 2 end states), and the signature == 2*the initial start positions to reach the public end state, say 2*64 bytes == 128 bytes.
A fatal issue, aka major reason for falling down, is that while many PRNG can be "fast-fowarded" in this way, when the cycle length is known you can in effect reverse by moving ahead (cycle_length-1) steps.
Thus for system to be practical, in order to sign a 256 bit value in this way you need to know that the cycle length is >2^256, and that the cycle length is unknown (and not easily knowable)
As a side note, SHA256 may or may not have multiple cycles. It's also unknown.
I've been looking into a few possibilities involving a vector (X,Y) multiplied into a new X,Y using a singular matrix followed by modulo. (think LCG with singular mixing).
Sure enough the vector seems to have multiple/many cycles depending on the start position.
As I always do, I'm putting far too much time into this without asking the appropriate questions - can quantum computing break these methods anyway using either shors, grovers or some combinatorial magic?
Would like to humbly ask then the experts out there - What are the fatal flaws of the basic approach, based on the realities of quantum computing and math?