Cryptology ePrint Archive: Report 2015/890

MI-T-HFE, a New Multivariate Signature Scheme

Wenbin Zhang and Chik How Tan

Abstract: In this paper, we propose a new multivariate signature scheme named MI-T-HFE as a competitor of QUARTZ. The core map of MI-T-HFE is of an HFEv type but more importantly has a specially designed trapdoor. This special trapdoor makes MI-T-HFE have several attractive advantages over QUARTZ. First of all, the core map and the public map of MI-T-HFE are both surjective. This surjectivity property is important for signature schemes because any message should always have valid signatures; otherwise it may be troublesome to exclude those messages without valid signatures. However this property is missing for a few major signature schemes, including QUARTZ. A practical parameter set is proposed for MI-T-HFE with the same length of message and same level of security as QUARTZ, but it has smaller public key size, and is more efficient than (the underlying HFEv- of) QUARTZ with the only cost that its signature length is twice that of QUARTZ.

Category / Keywords: public-key cryptography / post-quantum cryptography, multivariate signature scheme, QUARTZ, HFEv

Original Publication (in the same form): IMACC 2015

Date: received 14 Sep 2015

Contact author: tslzw at nus edu sg

Available format(s): PDF | BibTeX Citation

Version: 20150915:065948 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]