Improved Attacks for Characteristic-2 Parameters of the Cubic ABC Simple Matrix Encryption Scheme

Published

June 28, 2017

Author(s)

Dustin Moody, Ray A. Perlner, Daniel C. Smith-Tone

Abstract

In the last few years multivariate public key cryptography has experienced an infusion of new ideas for encryption. Among these new strategies is the ABC Simple Matrix family of encryption schemes which utilize the structure of a large matrix algebra to construct effectively invertible systems of nonlinear equations hidden by an isomorphism of polynomials. One promising approach to cryptanalyzing these schemes has been structural cryptanalysis, based on applying a strategy similar to MinRank attacks to the discrete differential. These attacks however have been signifi cantly more expensive when applied to parameters using fi elds of characteristic 2, which have been the most common choice for published parameters. This disparity is especially great for the cubic version of the Simple Matrix Encryption Scheme. In this work, we demonstrate a technique that can be used to implement a structural attack which is as efficient against parameters of characteristic 2 as are attacks against analogous parameters over higher characteristic fi elds. This attack demonstrates that, not only is the cubic simple matrix scheme susceptible to structural attacks, but that the published parameters claiming 80 bits of security are less secure than claimed (albeit only slightly.) Similar techniques can also be applied to improve structural attacks against the original Simple Matrix Encryption scheme, but they represent only a modest improvement over previous structural attacks. This work therefore demonstrates that choosing a field of characteristic 2 for the Simple Matrix Encryption Scheme or its cubic variant will not provide any additional security value.

Conference Dates

June 26-28, 2017

Conference Location

Utrecht

Conference Title

PQCrypto 2017: The Eighth International Conference on Post-Quantum Cryptography

Pub Type

Conferences

Download Paper

https://doi.org/10.1007/978-3-319-59879-6

Keywords

multivariate cryptography, differential invariant, MinRank, encryption

Citation

Moody, D. , Perlner, R. and Smith-Tone, D. (2017), Improved Attacks for Characteristic-2 Parameters of the Cubic ABC Simple Matrix Encryption Scheme, PQCrypto 2017: The Eighth International Conference on Post-Quantum Cryptography, Utrecht, -1, [online], https://doi.org/10.1007/978-3-319-59879-6 (Accessed April 26, 2024)