**Partitioning Multivariate Polynomial Equations via Vertex Separators for Algebraic Cryptanalysis and Mathematical Applications**

*Kenneth Koon-Ho Wong and Gregory V. Bard and Robert H. Lewis *

**Abstract: **We present a novel approach for solving systems of polynomial
equations via graph partitioning. The concept of a
variable-sharing graph of a system of polynomial equations is
defined. If such graph is disconnected, then the system of
equations is actually two separate systems that can be solved
individually. This can provide a significant speed-up in
computing the solution to the system, but is unlikely to occur
either randomly or in applications. However, by deleting a small
number of vertices on the graph, the variable-sharing graph
could be disconnected in a balanced fashion, and in turn the
system of polynomial equations are separated into smaller ones of
similar sizes. In graph theory terms, this process is equivalent to
finding balanced vertex partitions with minimum-weight vertex
separators.

The techniques of ﬁnding these vertex partitions are discussed, and experiments are performed to evaluate its practicality for general graphs and systems of polynomial equations. Applications of this approach to the QUAD family of stream ciphers, algebraic cryptanalysis of the stream cipher Trivium and its variants, as well as some mathematical problems in game theory and computational algebraic geometry are presented. In each of these cases, the systems of polynomial equations involved are well-suited to our graph partitioning method, and constructive results are discussed.

**Category / Keywords: **Balanced vertex partitions, graph partitioning, polynomial systems of equations, QUAD, Trivium, resultants, algebraic cryptanalysis.

**Publication Info: **submitted to a journal.

**Date: **received 11 Jul 2009

**Contact author: **bard at fordham edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20090714:030400 (All versions of this report)

**Short URL: **ia.cr/2009/343

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]