Paper 2023/542
A multistep strategy for polynomial system solving over finite fields and a new algebraic attack on the stream cipher Trivium
Abstract
In this paper we introduce a multistep generalization of the guess-and-determine or hybrid strategy for solving a system of multivariate polynomial equations over a finite field. In particular, we propose performing the exhaustive evaluation of a subset of variables stepwise, that is, by incrementing the size of such subset each time that an evaluation leads to a polynomial system which is possibly unfeasible to solve. The decision about which evaluation to extend is based on a preprocessing consisting in computing an incomplete Grobner basis after the current evaluation, which possibly generates linear polynomials that are used to eliminate further variables. If the number of remaining variables in the system is deemed still too high, the evaluation is extended and the preprocessing is iterated. Otherwise, we solve the system by a Grobner basis computation. Having in mind cryptanalytic applications, we present an implementation of this strategy in an algorithm called MultiSolve which is designed for polynomial systems having at most one solution. We prove explicit formulas for its complexity which are based on probability distributions that can be easily estimated by performing the proposed preprocessing on a testset of evaluations for different subsets of variables. We prove that an optimal complexity of MultiSolve is achieved by using a full multistep strategy with a maximum number of steps and in turn the classical guess-and-determine strategy, which essentially is a strategy consisting of a single step, is the worst choice. Finally, we extensively study the behaviour of MultiSolve when performing an algebraic attack on the well-known stream cipher Trivium.
Note: 27 pages.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Polynomial system solvingFinite fieldsCryptanalysis
- Contact author(s)
-
roberto lascala @ uniba it
federico pintore @ uniba it
sharwan tiwari @ tii ae
andrea visconti @ unimi it - History
- 2023-04-17: approved
- 2023-04-16: received
- See all versions
- Short URL
- https://ia.cr/2023/542
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/542,
author = {Roberto La Scala and Federico Pintore and Sharwan K. Tiwari and Andrea Visconti},
title = {A multistep strategy for polynomial system solving over finite fields and a new algebraic attack on the stream cipher Trivium},
howpublished = {Cryptology ePrint Archive, Paper 2023/542},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/542}},
url = {https://eprint.iacr.org/2023/542}
}
