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?

  • $\begingroup$ 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. $\endgroup$ – kelalaka Nov 13 '19 at 15:43
  • $\begingroup$ @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. $\endgroup$ – 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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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