2F - A New Method for Constructing Efficient Multivariate Encryption Schemes

Published

September 28, 2022

Author(s)

Daniel Smith-Tone

Abstract

The Support Minors method of solving the MinRank problem has contributed to several new cryptanalyses of post-quantum cryptosystems including some of the most efficient multivariate cryptosystems. While there are a few viable multivariate schemes that are secure against rank methods, the most prominent schemes, particularly for encryption, are not particularly efficient. In this article we present a new generic construction for building efficient multivariate encryption schemes. Such schemes can be built from maps having rank properties that would otherwise be damaging, but are immune to traditional rank attack. We then construct one such efficient multivariate encryption scheme and show it to be about 100 times faster than other secure multivariate encryption schemes in the literature.

Proceedings Title

Proceedings of PQCrypto 2022: The Thirteenth International Conference on Post-Quantum Cryptography

Volume

13512

Conference Dates

September 28-30, 2022

Conference Location

virtual, DC, US

Conference Title

PQCrypto 2022

Pub Type

Conferences

Download Paper

https://doi.org/10.1007/978-3-031-17234-2_10

Local Download

Keywords

Multivariate Cryptography, MinRank, encryption

Citation

Smith-Tone, D. (2022), 2F - A New Method for Constructing Efficient Multivariate Encryption Schemes, Proceedings of PQCrypto 2022: The Thirteenth International Conference on Post-Quantum Cryptography, virtual, DC, US, [online], https://doi.org/10.1007/978-3-031-17234-2_10, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=935191 (Accessed October 10, 2025)