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

##### 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)
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

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.