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

Subhadeep Banik; Andrea Caforio; Serge Vaudenay

doi:10.62056/ayzojbkrz

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

Authors

Subhadeep Banik, Andrea Caforio, Serge Vaudenay

Subhadeep Banik

Universita della Svizzera Italiana, Lugano, Switzerland
subhadeep dot banik at usi dot ch

Andrea Caforio

Ecole Polytechnique Federale de Lausanne, Lausanne, Switzerland
andrea dot caforio at epfl dot ch

Serge Vaudenay

Ecole Polytechnique Federale de Lausanne, Lausanne, Switzerland
serge dot vaudenay at epfl dot ch

Keywords: LowMC Block Cipher Cryptanalysis

Abstract

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.

References

[ARS⁺15]

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. https://doi.org/10.1007/978-3-662-46800-5_17.

Google Scholar ePrint

[BBDV20]

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. https://doi.org/10.46586/tosc.v2020.i4.130-146.

Google Scholar ePrint

[BBVY21]

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. https://doi.org/10.1007/978-3-030-92062-3_11.

Google Scholar ePrint

[BCC⁺10]

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. https://doi.org/10.1007/978-3-642-15031-9_14.

Google Scholar ePrint

[Din21a]

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. https://doi.org/10.1007/978-3-030-77870-5_14.

Google Scholar ePrint

[Din21b]

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. https://doi.org/10.1137/1.9781611976465.151.

Google Scholar ePrint

[DS11]

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. https://doi.org/10.1007/978-3-642-21702-9_6.

Google Scholar ePrint

[GKRS]

Lorenzo Grassi, Daniel Kales, Chistian Rechberger, and Markus Schofnegger. Survey of key-recovery attacks on lowmc in a single plaintext/ciphertext scenario.

Google Scholar ePrint

[LIM21]

Fukang Liu, Takanori Isobe, and Willi Meier. A simple algebraic attack on 3-round lowmc. IACR Cryptol. ePrint Arch., 2021:255, 2021.

Google Scholar ePrint

[LMSI22]

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. https://doi.org/10.46586/tosc.v2022.i3.102-122.

Google Scholar ePrint

[LPT⁺17]

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. https://doi.org/10.1137/1.9781611974782.143.

Google Scholar ePrint

[Zav]

Greg Zaverucha. The picnic signaure algorithm specifications, version 3.0, available at \url https://github.com/microsoft/Picnic/blob/master/spec/spec-v3.0.pdf.

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/ayzojbkrz

History

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.

License

Copyright is held by the author(s)

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

@article{CiC-1-1-22,
    author = "Banik, Subhadeep and Caforio, Andrea and Vaudenay, Serge",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "New Attacks on Low{MC} Using Partial Sets in the Single-Data Setting",
    volume = "1",
    number = "1",
    date = "2024-04-09",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/ayzojbkrz"
}

TY - JOUR
AU - Banik, Subhadeep
AU - Caforio, Andrea
AU - Vaudenay, Serge
PY  - 2024
TI  - New Attacks on LowMC Using Partial Sets in the Single-Data Setting
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 1
DO  - 10.62056/ayzojbkrz
UR  - https://doi.org/10.62056/ayzojbkrz
AB  - <p> 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.</p><p> 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.</p><p> 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. </p>
ER  -

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.