HFERP -- A New Multivariate Encryption Scheme

Published

April 1, 2018

Author(s)

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

Abstract

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.

Proceedings Title

PQCrypto 2018: The Ninth International Conference on Post-Quantum Cryptography

Volume

10786

Conference Dates

April 9-11, 2018

Conference Location

Fort Lauderdale, FL, US

Pub Type

Conferences

Download Paper

https://doi.org/10.1007/978-3-319-79063-3_19

Local Download

Keywords

Multivariate Cryptography, HFE, encryption, MinRank, Q-rank

Citation

Ikematsu, Y. , Perlner, R. , Smith-Tone, D. , Takagi, T. and Vates, J. (2018), HFERP -- A New Multivariate Encryption Scheme, PQCrypto 2018: The Ninth International Conference on Post-Quantum Cryptography, Fort Lauderdale, FL, US, [online], https://doi.org/10.1007/978-3-319-79063-3_19, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=925152 (Accessed May 10, 2024)