Paper 2009/343

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

Kenneth Koon-Ho Wong, 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 finding 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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. submitted to a journal.
Keywords
Balanced vertex partitionsgraph partitioningpolynomial systems of equationsQUADTriviumresultantsalgebraic cryptanalysis.
Contact author(s)
bard @ fordham edu
History
2009-07-14: received
Short URL
https://ia.cr/2009/343
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/343,
      author = {Kenneth Koon-Ho Wong and Gregory V.  Bard and Robert H.  Lewis},
      title = {Partitioning Multivariate Polynomial Equations via Vertex Separators for Algebraic Cryptanalysis and Mathematical Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2009/343},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/343}},
      url = {https://eprint.iacr.org/2009/343}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.