# Why does solving the underlying polynomial system “break” the multivariate cryptosystem

I was wondering why exactly does solving a polynomial system (directly or indirectly) "break" a multivariate cryptosystem as a digital signature.

I realize that the exact reason differs from system to system, but in general, from what I can see, it then allows attackers to sign messages with a private key that is not theirs. Am I on the right track here?

• If I understand correctly, If someone writes the digital signature as multivariate equations ( algebraic equations) then solves it, the attacker will get the key. The rest is obvious. Why there is quantum tags here unclear for me. – kelalaka Nov 13 '19 at 15:43
• @kelalaka Ok, and the way the key is handled is differed from system to system...makes sense, thanks! In terms of the tag, multivariate cryptography is having a surge in popularity since it can withstand an attack by a quantum computer, so it is being described as "post-quantum crypto". I understand that the tag "quantum-cryptography" was incorrect, however. – João Duarte Nov 14 '19 at 22:21

Multivariate cryptographic schemes that perform digital signatures like HFEv, FLASH and Quartz have something in common. As opposed to enciphering data like in a normal cryptosystem where a public multivariate polynomial $$P(X)$$ is given as:
$$P(X) = P(p_1(x_1,\ldots,x_n),\ldots,p_n(x_1,\ldots,x_n))$$
You input the plaintext bits $$x=(x_1,\ldots,x_n)$$ into $$P(X)$$ right? Well when dealing with digital signatures we do the opposite. This is, as we are the owners of the construction, given $$Y=H(m || salt)$$ where $$m$$ is a message, we can find the plaintext tuple that sends $$X$$ to $$Y=H(m || salt)$$ by inverting the construction:
$$X=P(Y)^{-1} = S^{-1} \circ \varphi^{-1} \circ F^{-1} \circ \varphi \circ T(Y)$$
which clearly yields $$X$$ such that $$P(X)=Y$$. Now Alice sends the tuple $$(m,salt, Y,X)$$ and Bob verifies as $$P(X)=Y=H(m||salt)$$.
Thus if Eve wants to forge digital signatures to trick Bob into thinking she's Alice, Eve must solve either the $$\mathcal{MQ}$$-Problem or the Isomorphism of Polynomials ($$\mathcal{IP}$$) which both are reasonably hard.