Name
Abstract | ||
|---|---|---|
In this paper, we present an improved approach to solve multivariate systems over finite fields. Our approach is a tradeoff between exhaustive search and Grobner bases techniques. We give theoretical evidences that our method brings a significant improvement in a very large context and we clearly define its limitations. The efficiency depends on the choice of the tradeoff. Our analysis gives an explicit way to choose the best tradeoff as well as an approximation. From our analysis, we present a new general algorithm to solve multivariate polynomial systems. Our theoretical results are experimentally supported by successful cryptanalysis of several multivariate schemes (TRMS, UOV, ... ). As a proof of concept, we were able to break the proposed parameters assumed to be secure until now. Parameters that resists to our method are also explicitly given. Our work permits to refine the parameters to be chosen for multivariate schemes. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1515/JMC.2009.009 | JOURNAL OF MATHEMATICAL CRYPTOLOGY |
Keywords | Field | DocType |
Grobner bases, multivariate cryptography | Multivariate cryptography,General algorithm,Cryptanalysis,Proof of concept,Discrete mathematics,Finite field,Combinatorics,Mathematical optimization,Brute-force search,Multivariate statistics,Algorithm,Multivariate polynomials,Mathematics | Journal |
Volume | Issue | ISSN |
3 | 3 | 1862-2976 |
Citations | PageRank | References |
51 | 1.92 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Luk Bettale | 1 | 111 | 7.18 |
| Jean-Charles Faugère | 2 | 1037 | 74.00 |
| Ludovic Perret | 3 | 546 | 39.06 |