
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Comparison of Two Signature Schemes Based on the MQ Problem and Quartz
Routo TERADA Ewerton R. ANDRADE
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E99A
No.12
pp.25272538 Publication Date: 2016/12/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E99.A.2527
Type of Manuscript: PAPER Category: Cryptography and Information Security Keyword: postquantum cryptography, MQ problem, digital signature, quartz, MPKC,
Full Text: PDF(637.7KB)>>
Summary:
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 NPcomplete. 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.

