Paper 2021/255
Low-Memory Algebraic Attacks on Round-Reduced LowMC
Fukang Liu, Takanori Isobe, and Willi Meier
Abstract
With the proposal of Picnic3, it has become interesting to investigate the security of LowMC with a full S-box layer. To significantly improve the efficiency of the Picnic signature, the designers of Picnic3 recommended to use the 4-round LowMC as the underlying block cipher, which has been shown to be insecure with 2 chosen plaintexts by Liu-Isobe-Meier. However, the attack scenario is very different and constrained in Picnic as the attacker is only allowed to know one single plaintext-ciphertext pair under the same key for LowMC. Recently, Banik et al. proposed guess-and-determine attacks on reduced LowMC in the Picnic setting. A major finding in their attacks is that the 3-bit S-box of LowMC can be linearized by guessing a quadratic equation. Notably, the attack on 2-round LowMC with a full S-box layer can be achieved with time complexity
Note: Further apply our techniques to instances with a partial S-box layer and solve the LowMC challenges with r=floor(n/s).
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- LowMClinearizationkey recoveryalgebraic attackXL
- Contact author(s)
-
liufukangs @ 163 com
takanori isobe @ ai u-hyogo ac jp
willimeier48 @ gmail com - History
- 2021-12-26: last of 3 revisions
- 2021-03-03: received
- See all versions
- Short URL
- https://ia.cr/2021/255
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/255, author = {Fukang Liu and Takanori Isobe and Willi Meier}, title = {Low-Memory Algebraic Attacks on Round-Reduced {LowMC}}, howpublished = {Cryptology {ePrint} Archive, Paper 2021/255}, year = {2021}, url = {https://eprint.iacr.org/2021/255} }