# Small Quantum Signatures - Reality check needed

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.

• Note that your grand idea would only be a one-time signature scheme. $\;$ – user991 Oct 19 '15 at 20:58
• @RickyDemer: yes, however we know how to turn a one-time signature scheme into a many-times signature scheme (Merkle tree), and it would be shorter than Lamport or Winternitz signatures. – poncho Oct 19 '15 at 21:02
• It would be shorter due to being an exponentially-more-efficient analogue of Winternitz. $\;$ – user991 Oct 19 '15 at 21:06

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.

• Excellent Poncho - thank you! That's just what I was looking for. Ensuring that the sequence never returns to the same state spaces is trivial - if that is all that is required to trump Shors, supurb. The second issue (attacks) I agree, it would need to be strengthened past a simple singular matrix to something with multiple guarantees, so to speak. If you have any further thoughts on how quantum computers could break this system (and what would be needed to thwart it), very much appreciated. I'll code up some solutions and release them. Thanks again! – Zaphod1001 Oct 21 '15 at 8:13

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.

• Nits (your main points are valid): As for (2), actually, the PRNG doesn't need a trapdoor; his scheme would work even if no one could reverse it. As for (3), the reason $n=256$ is not strength against exhaustive search; it's so that the scheme can sign a 256 bit hash. – poncho Oct 22 '15 at 13:44
• @poncho: Regarding (2): How does one verify in reasonable time / (taking $n$ as security parameter) how does one verify in polynomial time? And why do you need a 256 bit hash :-) (You can get away without collision resistance / birthday attacks, but exhaustive search always allows to find a second-preimage...) – mephisto Oct 23 '15 at 8:57
• "How do you verify in polynomial time"; well, presumably the PRNG has some magic way to fast forward $n$ steps in $Poly(\log n)$ steps (which isn't a "backdoor", as presumably anyone can do it). As for a 256 bit hash, well, if this is a signature method, we need to a (circa) 256 bit hash to be secure against birthday attacks against the overall signature method. – poncho Oct 23 '15 at 13:52
• @poncho: "resumably the PRNG has some magic way to fast forward n steps in Poly(logn) steps (which isn't a "backdoor", as presumably anyone can do it)." That's exactly what I point out to be necessary. Regarding the collision resistance: You can get away with weaker requirements not vulnerable to birthday attacks when using randomized hashing. That's why I was talking about exhaustive search... – mephisto Oct 26 '15 at 8:08