Small Quantum Signatures - Reality check needed

Question

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?

Many thanks.

Answer 1

I see two problems with this idea.

The first problem is Shor's algorithm; that's a quantum algorithm that is able to find the cycle length of a group (and if you can solve that problem, it is easy to factor and compute discrete logs). In this case, if we define the group of elements defined by the initial start state in the signature, where $H^n$ is the initial state stepped $n$ times (with the group operation defined as $H^a + H^b = H^{a+b}$), Shor's algorithm should be able to find the cycle length of the group, and as you point out, that allows the attacker to reverse the operation. The only defense I can see it to deliberately select an operation where the above is a semigroup; that is, where the set of elements $H^n$ never come back to the initial state $H^0$, but instead hits a loop later on (and so the first collision $H^x = H^y$ occurs with $x, y > 2^{256}$). I don't know how you would ensure that.

The second problem I foresee is the mathematical structure that you would need within your PRNG; to be able to compute $H^n$ in $o(n)$ time, you need quite a bit of mathematical structure within your PRNG; I would worry that such structure could be exploited by an attacker. For example, in your case of multiplying by a noninvertable matrix, I believe that an attacker can just look at the subspace defined by the nonintertable matrix, and effectively step backwards (by looking only for solutions that are within that subspace). There are methods that appear to be strong against classical computers (e.g. squaring modulo a hard to factor composite), but the ones I can think of run into issues against a Quantum Computer.

Bottom line: I don't believe the idea's quite dead; I do see a number of difficulties in the path.

Answer 2

While Poncho's answer already handles some issues with periodicity, there might be some other, functional issues:

1. You have to make sure that the PRNG can be publicly evaluated on an intermediate value of the chain (to allow verification). If you consider PRNG's like block ciphers in counter mode (or similar constructions) you have the fast accessibility property as setting the counter you obtain the corresponding output. Also, it is not possible to go "backwards". However, without knowing the seed it is also not possible to move forward, hence, verification is impossible.

2. It is not enough to have a PRNG that can be fast forwarded using some trapdoor (that has to be kept secret). This also has to be possible using only public information. The reason is that verification (of a signature on an $n$ bit hash) needs to perform $2^n$ steps (the number is constant because of the inverse chain).

3. Finally, fast forwarding $x$ steps must be doable with significantly less than $x$ operations. The reason is that, as mentioned above, signing and verifying require to perform $a$ steps on chain one and $b$ steps on chain two with $a + b = 2^n$. Consequently, at least one value out of $a, b$ is in the order of $2^n$ where $n$ determines the security of the scheme against exhaustive search.