Fast Forward Hash Signatures

Question

As a follow up to the Q/A session: Small Quantum Signatures - Reality check needed

I have implemented the discussed idea for a new short-quantum-safe signature system using fast-forwarding hash. It creates 32 byte public keys and 129 byte signatures. It is as good as I could get it in the little time I had available.

I have uploaded the source code to GitHub (Java) under MIT licence for the benefit of crypto exchange.
https://github.com/MKAXLACOR/FastForwardHashSignatures

My question then is : are there any obvious errors with the algorithm I have chosen to provide the fast-forwarding function?

I wouldn't mind forwarding this on to Bernstein etc so they can also take a crack at it - however if there are any obvious issues that I need to correct first - would appreciate knowing!
Many thanks.

Answer 1

It is easy to find preimages for the hash function you designed. Remember, to break the scheme it is enough to find any preimage. It is not necessary to find the one used to compute the image. Now, you got public integers $a,b,c,d,$ and $f,g$ as well as a modulo $M$. An $n$-th image is $$P(n) = a*x(n) + c*y(n) \mod M$$ $$Q(n) = b*x(n) + d*y(n) \mod M$$ with $$x(n)= (f * P(n-1) ) + n$$ $$y(n)= (g * Q(n-1) ) + 1$$ hence $$P(n) = afP(n-1) + an + cgQ(n-1) + c \mod M$$ $$Q(n) = bfP(n-1) + bn + dgQ(n-1) + d \mod M$$ leading $$P(n) - an - c = afP(n-1) + cgQ(n-1) \mod M$$ $$Q(n) - bn - d = bfP(n-1) + dgQ(n-1) \mod M.$$ Lets rename to get some more readability. For an attacker knowing an image $y_1 = P(n) - an - c \in\mathbb{Z}_M$, $y_2 = Q(n) - bn - d \in\mathbb{Z}_M$, $a_{1,1}=af$, $a_{1,2}=cg$, $a_{2,1}=bf$, $a_{2,2}=dg$ are all known integers mod $M$. The two unknowns are the primage parts $x_1 = P(n-1)$, $x_2 = Q(n-1)$. Rewriting the system gives $$a_{1,1}x_1 + a_{1,2}x_2 = y_1 \mod M$$ $$a_{2,1}x_1 + a_{2,2}x_2 = y_2 \mod M.$$ I guess from here on you know yourself how to determine $x_1, x_2$. This is one more example why you should not try to cook up something yourself when it comes to crypto.