Communications in Cryptology IACR CiC

New Attacks on LowMC Using Partial Sets in the Single-Data Setting


Subhadeep Banik, Andrea Caforio, Serge Vaudenay
Subhadeep Banik ORCID
Universita della Svizzera Italiana, Lugano, Switzerland
subhadeep dot banik at usi dot ch
Andrea Caforio ORCID
Ecole Polytechnique Federale de Lausanne, Lausanne, Switzerland
andrea dot caforio at epfl dot ch
Serge Vaudenay ORCID
Ecole Polytechnique Federale de Lausanne, Lausanne, Switzerland
serge dot vaudenay at epfl dot ch


The LowMC family of block ciphers was proposed by Albrecht et al. in Eurocrypt 2015, specifically targeting adoption in FHE and MPC applications due to its low multiplicative complexity. The construction operates a 3-bit quadratic S-box as the sole non-linear transformation in the algorithm. In contrast, both the linear layer and round key generation are achieved through multiplications of full rank matrices over GF(2). The cipher is instantiable using a diverse set of default configurations, some of which have partial non-linear layers i.e., in which the S-boxes are not applied over the entire internal state of the cipher.

The significance of cryptanalysing LowMC was elevated by its inclusion into the NIST PQC digital signature scheme PICNIC in which a successful key recovery using a single plaintext/ciphertext pair is akin to retrieving the secret signing key. The current state-of-the-art attack in this setting is due to Dinur at Eurocrypt 2021, in which a novel way of enumerating roots of a Boolean system of equation is morphed into a key-recovery procedure that undercuts an ordinary exhaustive search in terms of time complexity for the variants of the cipher up to five rounds.

In this work, we demonstrate that this technique can efficiently be enriched with a specific linearization strategy that reduces the algebraic degree of the non-linear layer as put forward by Banik et al. at IACR ToSC 2020(4). This amalgamation yields new attacks on certain instances of LowMC up to seven rounds.


Martin R. Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen, and Michael Zohner. Ciphers for MPC and FHE. In Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I, 430–454. 2015.
Subhadeep Banik, Khashayar Barooti, F. Betül Durak, and Serge Vaudenay. Cryptanalysis of lowmc instances using single plaintext/ciphertext pair. IACR Trans. Symmetric Cryptol., 2020(4):130–146, 2020.
Subhadeep Banik, Khashayar Barooti, Serge Vaudenay, and Hailun Yan. New attacks on lowmc instances with a single plaintext/ciphertext pair. In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology - ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6-10, 2021, Proceedings, Part I, volume 13090 of Lecture Notes in Computer Science, 303–331. Springer, 2021.
Charles Bouillaguet, Hsieh-Chung Chen, Chen-Mou Cheng, Tung Chou, Ruben Niederhagen, Adi Shamir, and Bo-Yin Yang. Fast exhaustive search for polynomial systems in \emph F\(_\mbox 2\). In Cryptographic Hardware and Embedded Systems, CHES 2010, 12th International Workshop, Santa Barbara, CA, USA, August 17-20, 2010. Proceedings, 203–218. 2010.
Itai Dinur. Cryptanalytic applications of the polynomial method for solving multivariate equation systems over GF(2). In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology - EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17-21, 2021, Proceedings, Part I, volume 12696 of Lecture Notes in Computer Science, 374–403. Springer, 2021.
Itai Dinur. Improved algorithms for solving polynomial systems over GF(2) by multiple parity-counting. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, 2550–2564. SIAM, 2021.
Itai Dinur and Adi Shamir. An improved algebraic attack on hamsi-256. In Antoine Joux, editor, Fast Software Encryption, 88–106. Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
Lorenzo Grassi, Daniel Kales, Chistian Rechberger, and Markus Schofnegger. Survey of key-recovery attacks on lowmc in a single plaintext/ciphertext scenario.
Fukang Liu, Takanori Isobe, and Willi Meier. A simple algebraic attack on 3-round lowmc. IACR Cryptol. ePrint Arch., 2021:255, 2021.
Fukang Liu, Willi Meier, Santanu Sarkar, and Takanori Isobe. New low-memory algebraic attacks on lowmc in the picnic setting. IACR Trans. Symmetric Cryptol., 2022(3):102–122, 2022.
Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, R. Ryan Williams, and Huacheng Yu. Beating brute force for systems of polynomial equations over finite fields. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, 2190–2202. SIAM, 2017.
Greg Zaverucha. The picnic signaure algorithm specifications, version 3.0, available at \url

PDFPDF Open access

Submitted: 2024-01-08
Accepted: 2024-03-05
Published: 2024-04-09
How to cite

Subhadeep Banik, Andrea Caforio, and Serge Vaudenay, "New Attacks on LowMC Using Partial Sets in the Single-Data Setting," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/ayzojbkrz.


Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.