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}$. Our signature scheme is also based on Quartz but we achieve a $2^{112}$ security level against Joux et al.'s attack. It is also more efficient in signature verification and vector initializations. Furthermore, we implemented both the original and our improved Quartz signature and run empirical comparisons.