Paper 2016/637

On the Security and Key Generation of the ZHFE Encryption Scheme

Wenbin Zhang and Chik How Tan

Abstract

At PQCrypto'14 Porras, Baena and Ding proposed a new interesting construction to overcome the security weakness of the HFE encryption scheme, and called their new encryption scheme ZHFE. They provided experimental evidence for the security of ZHFE, and proposed the parameter set $(q,n,D)= (7,55,105)$ with claimed security level $2^{80}$ estimated by experiment. However there is an important gap in the state-of-the-art cryptanalysis of ZHFE, i.e., a sound theoretical estimation for the security level of ZHFE is missing. In this paper we fill in this gap by computing upper bounds for the Q-Rank and for the degree of regularity of ZHFE in terms of $\log_q D$, and thus providing such a theoretical estimation. For instance the security level of ZHFE(7,55,105) can now be estimated theoretically as at least $2^{96}$. Moreover for the inefficient key generation of ZHFE, we also provide a solution to improve it significantly, making almost no computation needed.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. IWSEC 2016
Keywords
post-quantum cryptographymultivariate public key cryptographyHFEZHFE
Contact author(s)
tslzw @ nus edu sg
History
2016-06-21: received
Short URL
https://ia.cr/2016/637
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/637,
      author = {Wenbin Zhang and Chik How Tan},
      title = {On the Security and Key Generation of the ZHFE Encryption Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2016/637},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/637}},
      url = {https://eprint.iacr.org/2016/637}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.