Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleHybrid approach for solving multivariate systems over finite fields.
Author(s) Faug`ere Jean-Charles, Bettale Luk, Ludovic Perret
TypeArticle in Journal
AbstractIn this paper, we present an improved approach to solve multivariate systems over finite fields. Our approach is a tradeoff between exhaustive search and Gröbner 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.
KeywordsGröbner bases; multivariate cryptography
ISSN1862-2976; 1862-2984/e
URL http://www.degruyter.com/view/j/jmc.2009.3.issue-3/jmc.2009.009/jmc.2009.009.xml
JournalJ. Math. Cryptol.
PublisherDe Gruyter, Berlin
Translation No
Refereed No