Information Technology Reference
In-Depth Information
On the Number of Linearly Independent
Equations Generated by XL
Sondre Rønjom and H avard Raddum
Department of Informatics, University of Bergen, N-5020 Bergen, Norway
sondrer@ii.uib.no, haavardr@ii.uib.no
Abstract.
Solving multivariate polynomial equation systems has been
the focus of much attention in cryptography in the last years. Since most
ciphers can be represented as a system of such equations, the problem of
breaking a cipher naturally reduces to the task of solving them. Several
papers have appeared on a strategy known as
eXtended Linearization
(XL) with a view to assessing its complexity. However, its eciency
seems to have been overestimated and its behaviour has yet to be fully
understood. Our aim in this paper is to fill in some of these gaps in our
knowledge of XL. In particular, by examining how dependencies arise
from multiplication by monomials, we give a formula from which the
eciency of XL can be deduced for multivariate polynomial equations
over
F
2
.
This confirms rigorously a result arrived at by Yang and Chen
by a completely different approach. The formula was verified empirically
by investigating huge amounts of random equation systems with varying
degree, number of variables and number of equations.
Keywords:
XL, Grobner bases, Stream Ciphers.
1
Introduction
The problem of solving multivariate polynomial equations is encountered in
many different fields. This problem has in particular received a great deal of
attention in cryptography. The problem of breaking a cipher is reformulated
as a problem of solving a (very large) system of polynomial equations. Solving
multivariate polynomial equations over
F
2
is known to be NP-hard.
XL was proposed in [10], as a new algorithm for solving multivariate poly-
nomial equations. A parameter
D
is associated with XL, and the complexity of
XL is exponential in
D
. In [10] and [11], the authors try to evaluate for which
D
XL works. For a system with
m
equations in
n
variables they use the esti-
mation
D ≈
n
√
m
, which seems to work fine for special cases, but for general
systems this approximation becomes very inaccurate. For the AES, we estimate
that
D
n
√
m
·
n
√
m
·
4
.
9, which makes
a huge difference, as running time is exponential in
D
. So it is evident that the
early estimations of
D
are inaccurate. This is also shown in [13] where a formula
for estimating
D
is given. This formula applies to quadratic systems over large
fields and is proved to be correct given one more assumption.
≈
2
.
5, and for Serpent it is more like
D
≈
