Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

HFERP -- A New Multivariate Encryption Scheme

Published

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

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 April 16, 2024)
Created March 31, 2018, Updated October 12, 2021