Paper 2024/1304
Improved Algebraic Attacks on Round-Reduced LowMC with Single-Data Complexity
Abstract
Recently, Picnic3 has introduced several alternative LowMC instances, which prompts the cryptanalysis competition for LowMC. In this paper, we provide new solutions to the competition with full S-box layers under single-data complexity. First, we present a new guess-and-determine attack framework that achieves the best trade-off in complexity, while effectively enhancing two algorithms applicable to 2-round LowMC cryptanalysis. Next, we present a new meet-in-the-middle attack framework for 2-/3-round LowMC, which can gradually reduce the number of variables and narrow down the range of candidate keys in stages. As a result, our 3-stage MITM attacks have both lower time complexity and memory complexity than the best previous 2-round attacks proposed by Banik et al. at ASIACRYPT 2021, with memory reduced drastically by a factor of $ 2^{29.7} \sim 2^{70.4} $.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Published elsewhere. SAC 2024
- Keywords
- LowMCPicnicAlgebraic attackMITMLow memory
- Contact author(s)
-
renxingwei @ iie ac cn
liyongqiang @ iie ac cn
wangmingsheng @ iie ac cn - History
- 2024-08-23: approved
- 2024-08-21: received
- See all versions
- Short URL
- https://ia.cr/2024/1304
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1304,
author = {Xingwei Ren and Yongqiang Li and Mingsheng Wang},
title = {Improved Algebraic Attacks on Round-Reduced {LowMC} with Single-Data Complexity},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1304},
year = {2024},
url = {https://eprint.iacr.org/2024/1304}
}
