Improved Attacks on LowMC with Algebraic Techniques

The LowMC family of SPN block cipher proposed by Albrecht et al. was designed specifically for MPC-/FHE-/ZKP-friendly use cases. It is especially used as the underlying block cipher of PICNIC, one of the alternate third-round candidate digital signature algorithms for NIST post-quantum cryptography standardization. The security of PICNIC is highly related to the difficulty of recovering the secret key of LowMC from a given plaintext/ciphertext pair, which raises new challenges for security evaluation under extremely low data complexity.In this paper, we improve the attacks on LowMC under low data complexity, i.e. 1 or 2 chosen plaintext/ciphertext pairs. For the difference enumeration attack with 2 chosen plaintexts, we propose new algebraic methods to better exploit the nonlinear relation inside the introduced variables based on the attack framework proposed by Liu et al. at ASIACRYPT 2022. With this technique, we significantly extend the number of attack rounds for LowMC with partial nonlinear layers and improve the success probability from around 0.5 to over 0.9. The security margin of some instances can be reduced to only 3/4 rounds. For the key-recovery attack using a single plaintext, we adopt a different linearization strategy to reduce the huge memory consumption caused by the polynomial methods for solving multivariate equation systems. The memory complexity reduces drastically for all 5-/6-round LowMC instances with full nonlinear layers at the sacrifice of a small factor of time complexity. For 5-round LowMC instances with a block size of 129, the memory complexity decreases from 286.46 bits to 248.18 bits while the time complexity even slightly reduces. Our results indicate that the security for different instances of LowMC under extremely low data complexity still needs further exploration