Cryptanalysis of the extension field cancellation cryptosystem
| Autor: | Ludovic Perret, Olive Chakraborty, Jean-Charles Faugère |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Discrete mathematics
business.industry Applied Mathematics 020206 networking & telecommunications Cryptography Field (mathematics) 0102 computer and information sciences 02 engineering and technology Encryption System of linear equations 01 natural sciences Computer Science Applications Gröbner basis 010201 computation theory & mathematics Scheme (mathematics) ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION 0202 electrical engineering electronic engineering information engineering Cryptosystem Algebraic number business Mathematics |
| Zdroj: | Designs, Codes and Cryptography. 89:1335-1364 |
| ISSN: | 1573-7586 0925-1022 |
| DOI: | 10.1007/s10623-021-00873-9 |
| Popis: | In this article, we present algebraic attacks against the Extension Field Cancellation ( $$\texttt {EFC}$$ ) scheme, a multivariate public-key encryption scheme which was published at PQCRYPTO’2016. First, we present a successful Grobner basis message-recovery attack on the first and second proposed parameters of the scheme. For the first challenge parameter, a Grobner-based hybrid attack has a $$2^{65}$$ bit complexity which beats the claimed 80 bit security level. We further show that the algebraic system arising from an $$\texttt {EFC}$$ public-key is much easier to solve than a random system of the same size. Briefly, this is due to the apparition of many lower degree equations during the Grobner basis computation. We present a polynomial-time method to recover such lower-degree relations and also show their usefulness in improving the Grobner basis attack complexity on $$\texttt {EFC}$$ . Thus, we show that there is an algebraic structural weakness in the system of equations coming from $$\texttt {EFC}$$ and hence makes the scheme not suitable for encryption. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink