International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Improved Attacks on LowMC with Algebraic Techniques

Authors:
Yimeng Sun , School of Cyber Science and Technology, Shandong University, Qingdao, China; Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China
Jiamin Cui , School of Cyber Science and Technology, Shandong University, Qingdao, China; Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China
Meiqin Wang , School of Cyber Science and Technology, Shandong University, Qingdao, China; Quan Cheng Laboratory, Jinan, China; Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China
Download:
DOI: 10.46586/tosc.v2023.i4.143-165
URL: https://tosc.iacr.org/index.php/ToSC/article/view/11283
Search ePrint
Search Google
Abstract: 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.
BibTeX
@article{tosc-2023-33685,
  title={Improved Attacks on LowMC with Algebraic Techniques},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={023 No. 4},
  pages={143-165},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/11283},
  doi={10.46586/tosc.v2023.i4.143-165},
  author={Yimeng Sun and Jiamin Cui and Meiqin Wang},
  year=2023
}