Comparison of Two Signature Schemes Based on the MQ Problem and Quartz

Ewerton R. ANDRADE

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A    No.12    pp.2527-2538
Publication Date: 2016/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.2527
Type of Manuscript: PAPER
Category: Cryptography and Information Security
post-quantum cryptography,  MQ problem,  digital signature,  quartz,  MPKC,  

Full Text: PDF(637.7KB)>>
Buy this Article

Patarin proposed a crytographic trapdoor called Hidden Field Equation (HFE), a trapdoor based on the Multivariate Quadratic (MQ) and the Isomorphism of Polynomials (IP) problems. The MQ problem was proved by Patarin et al.'s 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 250 computations and 250 queries to the signing oracle. Currently, the recommended minimum security level is 2112. Our signature scheme is also based on Quartz but we achieve a 2112 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.