Paper 2022/1022

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

Fukang Liu
Willi Meier
Santanu Sarkar
Takanori Isobe
Abstract

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" (eprint.iacr.org/2021/255).

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Published by the IACR in TOSC 2022
Keywords
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
History
2022-10-11: last of 2 revisions
2022-08-07: received
See all versions
Short URL
https://ia.cr/2022/1022
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1022,
      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{https://eprint.iacr.org/2022/1022}},
      url = {https://eprint.iacr.org/2022/1022}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.