0
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ You might want to add at least a security "argument" if not a proof to the concept. Writing this might already tell you possibly existing problems (I do not claim that there are problems). $\endgroup$
    – mephisto
    Dec 9, 2015 at 10:54

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.