### Hash-based Multivariate Public Key Cryptosystems

WANG Hou-Zhen and ZHANG Huan-Guo

##### Abstract

Many efficient attacks have appeared in recent years, which have led to serious blow for the traditional multivariate public key cryptosystems. For example, the signature scheme SFLASH was broken by Dubois et al. at CRYPTO'07, and the Square signature (or encryption) scheme by Billet et al. at ASIACRYPTO'09. Most multivariate schemes known so far are insecure, except maybe the sigature schemes UOV and HFEv-. Following these new developments, it seems that the general design principle of multivariate schemes has been seriously questioned, and there is a rather pressing desire to find new trapdoor construction or mathematical tools and ideal. In this paper, we introduce the hash authentication techniques and combine with the traditional MQ-trapdoors to propose a novel hash-based multivariate public key cryptosystems. The resulting scheme, called EMC (Extended Multivariate Cryptosystem), can also be seen as a novel hash-based cryptosystems like Merkle tree signature. And it offers the double security protection for signing or encrypting. By the our analysis, we can construct the secure and efficient not only signature scheme but also encryption scheme by using the EMC scheme combined some modification methods summarized by Wolf. And thus we present two new schems: EMC signature scheme (with the Minus method -") and EMC encryption scheme (with the Plus method +"). In addition, we also propose a reduced scheme of the EMC signature scheme (a light-weight signature scheme). Precise complexity estimates for these schemes are provided, but their security proofs in the random oracle model are still an open problem.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Multivariate Public Key Cryptosystems
Contact author(s)
wanghouzhen @ 126 com
History
Short URL
https://ia.cr/2010/296

CC BY

BibTeX

@misc{cryptoeprint:2010/296,
author = {WANG Hou-Zhen and ZHANG Huan-Guo},
title = {Hash-based Multivariate Public Key Cryptosystems},
howpublished = {Cryptology ePrint Archive, Paper 2010/296},
year = {2010},
note = {\url{https://eprint.iacr.org/2010/296}},
url = {https://eprint.iacr.org/2010/296}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.