Resumo

Patarin proposed a crytographic trapdoor called Hidden Field Equation (HFE), a trapdoor based on the $M$ultivariate $Q$uadratic ($MQ$) and the Isomorphism of Polynomials (IP) problems. The $MQ$ problem was proved by Patarin et al. to be NP-complete. Although the basic HFE has been proved to be vulnerable to attacks, its variants obtained by some modifications have been proved to be stronger against attacks. The Quartz digital signature scheme based on the HFEv- trapdoor (a variant of HFE) with particular choices of parameters, has been shown to be stronger against algebraic attacks to recover the private key. Furthermore, it generates reasonably short signatures. However, Joux et al. proved (based on the Birthday Paradox Attack) that Quartz is malleable in the sense that, if an adversary gets a valid pair of message and signature, a valid signature to another related message is obtainable with $2^{50}$ computations and $2^{50}$ queries to the signing oracle. Currently, the recommended minimum security level is $2^{112}$. In this paper we compare two Signature Schemes Based on the $MQ$ Problem and Quartz. And also present a novel scheme.