Paper 2021/1191

A Simpler Model for Recovering Superpoly onTrivium

Stéphanie Delaune, Patrick Derbez, Arthur Gontier, and Charles Prud'homme


The cube attack is a powerful cryptanalysis technique against symmetric cryptosystems, especially for stream ciphers. One of the key step in a cube attack is recovering the superpoly. The division property has been introduced to cube attacks with the aim first to identify variables/monomials that are not involved in the superpoly. Recently,some improved versions of this technique allowing the recovery of the exact superpoly have been developed and applied on various stream ciphers [13,15]. In this paper, we propose a new model to recover the exact superpoly of a stream cipher given a cube. We model the polynomials involved in the stream cipher as a directed graph. It happens that this structure handles some of the monomial cancellations more easily than those based on division property, and this leads to better timing results. We propose two implementations of our model, one in MILP and one in CP, which are up to 10 times faster than the original division property-based model from Hao et al. [13], and consistently 30 to 60 times faster than the monomial prediction-based model from Hu et al. [15].

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. SAC-2021
Contact author(s)
patrick derbez @ irisa fr
2021-09-17: received
Short URL
Creative Commons Attribution


      author = {Stéphanie Delaune and Patrick Derbez and Arthur Gontier and Charles Prud'homme},
      title = {A Simpler Model for Recovering Superpoly onTrivium},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1191},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.