Paper 2010/349

Improved Algebraic Cryptanalysis of QUAD, Bivium and Trivium via Graph Partitioning on Equation Systems

Kenneth Koon-Ho Wong and Gregory V. Bard

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 corresponding system of equations can be split into smaller ones 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 certain 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 in algebraic cryptanalysis on symmetric ciphers are presented. For the QUAD family of stream ciphers, we show how a malicious party can manufacture conforming systems that can be easily broken. For the stream cipher Trivium and its variants, we achieve significant speedups in algebraic attacks launched against them. In each of these cases, the systems of polynomial equations involved are well-suited to our graph partitioning method. These results may open a new avenue for evaluating the security of symmetric ciphers against algebraic attacks.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Extended version of published paper in proceedings of ACISP 2010
Keywords
algebraic attacksgraph partitioningpolynomial equationsTriviumQUAD
Contact author(s)
kk wong @ qut edu au
History
2010-06-18: received
Short URL
https://ia.cr/2010/349
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/349,
      author = {Kenneth Koon-Ho Wong and Gregory V.  Bard},
      title = {Improved Algebraic Cryptanalysis of QUAD, Bivium and Trivium via Graph Partitioning on Equation Systems},
      howpublished = {Cryptology ePrint Archive, Paper 2010/349},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/349}},
      url = {https://eprint.iacr.org/2010/349}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.