TY - JOUR
AU - Liu, Fukang
AU - Meier, Willi
AU - Sarkar, Santanu
AU - Isobe, Takanori
PY - 2022/09/09
Y2 - 2023/09/22
TI - New Low-Memory Algebraic Attacks on LowMC in the Picnic Setting
JF - IACR Transactions on Symmetric Cryptology
JA - ToSC
VL - 2022
IS - 3
SE - Articles
DO - 10.46586/tosc.v2022.i3.102-122
UR - https://tosc.iacr.org/index.php/ToSC/article/view/9851
SP - 102-122
AB - <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>
ER -