@article{Liu_Meier_Sarkar_Isobe_2022, title={New Low-Memory Algebraic Attacks on LowMC in the Picnic Setting}, volume={2022}, url={https://tosc.iacr.org/index.php/ToSC/article/view/9851}, DOI={10.46586/tosc.v2022.i3.102-122}, abstractNote={<p>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.<br>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<sup>38</sup> bits) to only 256KB (2<sup>21</sup> bits) using our new algebraic attacks rather than the MITM attacks, while the time complexity of our attacks is about 2<sup>3.2</sup> ∼ 2<sup>5</sup> 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.</p>}, number={3}, journal={IACR Transactions on Symmetric Cryptology}, author={Liu, Fukang and Meier, Willi and Sarkar, Santanu and Isobe, Takanori}, year={2022}, month={Sep.}, pages={102–122} }