Paper 2022/019

Algebraic Meet-in-the-Middle Attack on LowMC

Fukang Liu
Santanu Sarkar
Gaoli Wang
Willi Meier
Takanori Isobe

By exploiting the feature of partial nonlinear layers, we propose a new technique called algebraic meet-in-the-middle (MITM) attack to analyze the security of LowMC, which can reduce the memory complexity of the simple difference enumeration attack over the state-of-the-art. Moreover, while an efficient algebraic technique to retrieve the full key from a differential trail of LowMC has been proposed at CRYPTO 2021, its time complexity is still exponential in the key size. In this work, we show how to reduce it to constant time when there are a sufficiently large number of active S-boxes in the trail. With the above new techniques, the attacks on LowMC and \mbox{LowMC-M} published at CRYPTO 2021 are further improved, and some LowMC instances could be broken for the first time. Our results seem to indicate that partial nonlinear layers are still not well-understood.

Available format(s)
Secret-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2022
LowMC LowMC-M algebraic attack linearization key recovery meet-in-the-middle
Contact author(s)
liufukangs @ gmail com
santanu @ iitm ac in
glwang @ sei ecnu edu cn
willimeier48 @ gmail com
takanori isobe @ ai u-hyogo ac jp
2022-09-13: last of 6 revisions
2022-01-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Fukang Liu and Santanu Sarkar and Gaoli Wang and Willi Meier and Takanori Isobe},
      title = {Algebraic Meet-in-the-Middle Attack on LowMC},
      howpublished = {Cryptology ePrint Archive, Paper 2022/019},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.