Paper 2019/1415

Toward A More Efficient Gröbner-based Algebraic Cryptanalysis

Hossein Arabnezhad-Khanoki and Babak Sadeghiyan


In this paper, we propose a new method to launch a more efficient algebraic cryptanalysis. Algebraic cryptanalysis aims at finding the secret key of a cipher by solving a collection of polynomial equations that describe the internal structure of the cipher, while chosen correlated plaintexts, as what appear in higher order differential cryptanalysis and its derivatives such as cube attack or integral cryptanalysis, forces many linear relation between intermediate state bits in the cipher. In this paper, we take these polynomial relations into account, so it become possible to simplify the equation system arising from algebraic cryptanalysis, and consequently solve the polynomial system more efficiently. We take advantage of Universal Proning technique to provide an efficient method to recover such linear polynomials. Another important parameter in algebraic cryptanalysis of ciphers is to effectively describe the cipher. We employ FWBW representation of S-boxes together with Universal Proning to help provide a more powerful algebraic cryptanalysis based on Gröbner-basis computation. We show our method is more efficient than doing algebraic cryptanalysis with MQ representation, and also than employing MQ together with Universal Proning. To show the effectiveness of our approach, we applied it for the cryptanalysis of several light weight block ciphers. A by-product of employing this approach is that we have achieved such an efficiency to algebraic cryptanalyse 12-round LBlock, 6-round MIBS, 7-round PRESENT and 9-round SKINNY light-weight block ciphers, so far.

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Algebraic CryptanalysisGröbner basisUniversal ProningS-box representation
Contact author(s)
arabnezhad @ aut ac ir
2019-12-06: received
Short URL
Creative Commons Attribution


      author = {Hossein Arabnezhad-Khanoki and Babak Sadeghiyan},
      title = {Toward A More Efficient Gröbner-based Algebraic Cryptanalysis},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1415},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.