HFERP - A new multivariate encryption scheme

Yasuhiko Ikematsu, Ray Perlner, Daniel Smith-Tone, Tsuyoshi Takagi, Jeremy Vates

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Citations (Scopus)


In 2016, Yasuda et al. presented a new multivariate encryption technique based on the Square and Rainbow primitives and utilizing the plus modifier that they called SRP. The scheme achieved a smaller blow-up factor between the plaintext space and ciphertext space than most recent multivariate encryption proposals, but proved to be too aggressive and was completely broken by Perlner et al. in 2017. The scheme suffered from the same MinRank weakness that has allowed effective attacks on several notable big field multivariate schemes: HFE, multi-HFE, HFE-, for example. We propose a related new encryption scheme retaining the desirable traits of SRP and patching its weaknesses. We call the scheme HFERP because it utilizes a similar construction as SRP with an HFE primitive replacing the Square polynomial. The effect of this substitution is to increase the Q-rank of the pubic key to such a degree that the MinRank attack is impossible. HFERP still retains the relatively small blow-up factor between the plaintext space and ciphertext space, and is thus a candidate for secure multivariate encryption without an essential doubling in size between plaintext and ciphertext.

Original languageEnglish
Title of host publicationPost-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Proceedings
EditorsTanja Lange, Rainer Steinwandt
PublisherSpringer Verlag
Number of pages21
ISBN (Print)9783319790626
Publication statusPublished - 2018
Event9th International Conference on Post-Quantum Cryptography, PQCrypto 2018 - Fort Lauderdale, United States
Duration: Apr 9 2018Apr 11 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10786 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other9th International Conference on Post-Quantum Cryptography, PQCrypto 2018
Country/TerritoryUnited States
CityFort Lauderdale

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'HFERP - A new multivariate encryption scheme'. Together they form a unique fingerprint.

Cite this