×

HFERP – a new multivariate encryption scheme. (English) Zbl 1406.94065

Lange, Tanja (ed.) et al., Post-quantum cryptography. 9th international conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9–11, 2018. Proceedings. Cham: Springer (ISBN 978-3-319-79062-6/pbk; 978-3-319-79063-3/ebook). Lecture Notes in Computer Science 10786, 396-416 (2018).
Summary: In 2016, T. Yasuda and K. Sakurai [ICICS 2015, Lect. Notes Comput. Sci. 9543, 236–251 (2016; Zbl 1384.94109)] 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 R. Perlner et al. in 2017 [SAC 2017, Lect. Notes Comput. Sci. 10719, 355–373 (2018; Zbl 1384.94094)]. 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.
For the entire collection see [Zbl 1387.94005].

MSC:

94A60 Cryptography
81P94 Quantum cryptography (quantum-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI