Paper 2022/1022

New Low-Memory Algebraic Attacks on LowMC in the Picnic Setting

Fukang Liu
Willi Meier
Santanu Sarkar
Takanori Isobe

The security of the post-quantum signature scheme Picnic is highly related to the difficulty of recovering the secret key of LowMC from a single plaintext-ciphertext pair. Since Picnic is one of the alternate third-round candidates in NIST post-quantum cryptography standardization process, it has become urgent and important to evaluate the security of LowMC in the Picnic setting. The best attacks on LowMC with full S-box layers used in Picnic3 were achieved with Dinur's algorithm. For LowMC with partial nonlinear layers, e.g. 10 S-boxes per round adopted in Picnic2, the best attacks on LowMC were published by Banik et al. with the meet-in-the-middle (MITM) method. In this paper, we improve the attacks on LowMC in a model where memory consumption is costly. First, a new attack on 3-round LowMC with full S-box layers with negligible memory complexity is found, which can outperform Bouillaguet et al.'s fast exhaustive search attack and can achieve better time-memory tradeoffs than Dinur's algorithm. Second, we extend the 3-round attack to 4 rounds to significantly reduce the memory complexity of Dinur's algorithm at the sacrifice of a small factor of time complexity. For LowMC instances with 1 S-box per round, our attacks are shown to be much faster than the MITM attacks. For LowMC instances with 10 S-boxes per round, we can reduce the memory complexity from 32GB ($2^{38}$ bits) to only 256KB ($2^{21}$ bits) using our new algebraic attacks rather than the MITM attacks, while the time complexity of our attacks is about $2^{3.2}\sim 2^{5}$ times higher than that of the MITM attacks. A notable feature of our new attacks (apart from the 4-round attack) is their simplicity. Specifically, only some basic linear algebra is required to understand them and they can be easily implemented.

Note: We further developed our ideas in our preliminary work titled "Low-Memory Algebraic Attacks on Round-Reduced LowMC" (

Available format(s)
Attacks and cryptanalysis
Publication info
Published by the IACR in TOSC 2022
LowMC Picnic polynomial method algebraic attack crossbred algorithm low memory
Contact author(s)
liufukangs @ gmail com
willimeier48 @ gmail com
santanu @ iitm ac in
takanori isobe @ ai u-hyogo ac jp
2022-10-11: last of 2 revisions
2022-08-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Fukang Liu and Willi Meier and Santanu Sarkar and Takanori Isobe},
      title = {New Low-Memory Algebraic Attacks on LowMC in the Picnic Setting},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1022},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.