Paper 2017/1135

On the Complexity of the Hybrid Approach on HFEv-

Albrecht Petzoldt

Abstract

The HFEv- signature scheme is one of the most promising candidates for post-quantum digital signatures. Most notably here is the short signature size of the scheme. It has long been known that direct attacks against HFEv- systems work more efficiently than against random systems. The reason for this was found by Jintai Ding et al., who proved an upper bound on the degree of regularity of these systems. However, not much is known about the efficiency of the hybrid approach against the HFEv- scheme. In order to find suitable parameter sets for HFEv- for higher levels of security, this topic has to be studied in more detail. In this article we consider this question by performing a large number of computer experiments. As our experiments show, guessing variables does not help to speed up direct attacks against HFEv- systems. Therefore, in the parameter selection of these schemes, we do not have to consider the hybrid approach. Furthermore, we develop in this article a simple formula to estimate the degree of regularity of a determined HFEv- system. Together with our results on the behavior of the hybrid approach, this formula gives us an easy way to estimate the complexity of direct attacks against HFEv- systems.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Multivariate CryptographyHFEv-Direct AttackHybrid Approach
Contact author(s)
albrecht petzoldt @ googlemail com
History
2017-11-27: received
Short URL
https://ia.cr/2017/1135
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1135,
      author = {Albrecht Petzoldt},
      title = {On the Complexity of the Hybrid Approach on HFEv-},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1135},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1135}},
      url = {https://eprint.iacr.org/2017/1135}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.