Paper 2007/129

An Algebraic Analysis of Trivium Ciphers based on the Boolean Satisfiability Problem

Cameron McDonald, Chris Charnes, and Josef Pieprzyk


Trivium is a stream cipher candidate of the eStream project. It has successfully moved into phase three of the selection process under the hardware category. No attacks faster than the exhaustive search have so far been reported on Trivium. Bivium-A and Bivium-B are simplified versions of Trivium that are built on the same design principles but with two registers. The simplified design is useful in investigating Trivium type ciphers with a reduced complexity and provides insight into effective attacks which could be extended to Trivium. This paper focuses on an algebraic analysis which uses the boolean satisfiability problem in propositional logic. For reduced variants of the cipher, this analysis recovers the internal state with a minimal amount of keystream observations.

Note: Revision of results.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Algebraic AnalysisBoolean SatisfiabilityTriviumeStream
Contact author(s)
cmcdonal @ ics mq edu au
2007-12-18: last of 3 revisions
2007-04-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Cameron McDonald and Chris Charnes and Josef Pieprzyk},
      title = {An Algebraic Analysis of Trivium Ciphers based on the Boolean Satisfiability Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2007/129},
      year = {2007},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.