English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper we introduce a multistep generalization of theguess-and-determine or hybrid strategy for solving a system of multivariatepolynomial equations over a finite field. In particular, we propose performingthe exhaustive evaluation of a subset of variables stepwise, that is, byincrementing the size of such subset each time that an evaluation leads to apolynomial system which is possibly unfeasible to solve. The decision aboutwhich evaluation to extend is based on a preprocessing consisting in computingan incomplete Grobner basis after the current evaluation, which possiblygenerates linear polynomials that are used to eliminate further variables. Ifthe number of remaining variables in the system is deemed still too high, theevaluation is extended and the preprocessing is iterated. Otherwise, we solvethe system by a Grobner basis computation.  Having in mind cryptanalytic applications, we present an implementation ofthis strategy in an algorithm called MultiSolve which is designed forpolynomial systems having at most one solution. We prove explicit formulas forits complexity which are based on probability distributions that can be easilyestimated by performing the proposed preprocessing on a testset of evaluationsfor different subsets of variables. We prove that an optimal complexity ofMultiSolve is achieved by using a full multistep strategy with a maximum numberof steps and in turn the classical guess-and-determine strategy, whichessentially is a strategy consisting of a single step, is the worst choice.Finally, we extensively study the behaviour of MultiSolve when performing analgebraic attack on the well-known stream cipher Trivium.

A multistep strategy for polynomial system solving over finite fields and a new algebraic attack on the stream cipher Trivium