{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T17:05:07Z","timestamp":1753895107216,"version":"3.41.2"},"reference-count":12,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,1,8]],"date-time":"2024-01-08T00:00:00Z","timestamp":1704672000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,3,5]]},"abstract":"<jats: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.<\/jats:p>\n          <jats: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.<\/jats:p>\n          <jats: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. <\/jats:p>","DOI":"10.62056\/ayzojbkrz","type":"journal-article","created":{"date-parts":[[2024,4,9]],"date-time":"2024-04-09T19:27:10Z","timestamp":1712690830000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":1,"title":["New Attacks on LowMC Using Partial Sets in the Single-Data Setting"],"prefix":"10.62056","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6310-0154","authenticated-orcid":false,"given":"Subhadeep","family":"Banik","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/03c4atk17","id-type":"ROR","asserted-by":"publisher"}],"name":"Universita della Svizzera Italiana","place":["Via Giuseppe Buffi 13, Lugano, 6900, Switzerland"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3019-2897","authenticated-orcid":false,"given":"Andrea","family":"Caforio","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/02s376052","id-type":"ROR","asserted-by":"publisher"}],"name":"Ecole Polytechnique Federale de Lausanne","place":["Lausanne, 1015, Switzerland"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9185-1449","authenticated-orcid":false,"given":"Serge","family":"Vaudenay","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/02s376052","id-type":"ROR","asserted-by":"publisher"}],"name":"Ecole Polytechnique Federale de Lausanne","place":["Lausanne, 1015, Switzerland"]}]}],"member":"48349","published-online":{"date-parts":[[2024,4,9]]},"reference":[{"key":"ref1:lowmc","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1007\/978-3-662-46800-5_17","article-title":"Ciphers for MPC and FHE","volume-title":"Advances in Cryptology - EUROCRYPT 2015 - 34th\n                   Annual International Conference on the Theory and\n                   Applications of Cryptographic Techniques, Sofia,\n                   Bulgaria, April 26-30, 2015, Proceedings, Part I","author":"Martin R. Albrecht","year":"2015"},{"key":"ref2:dinur","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/978-3-030-77870-5_14","article-title":"Cryptanalytic Applications of the Polynomial Method\n                   for Solving Multivariate Equation Systems over\n                   GF(2)","volume-title":"Advances in Cryptology - EUROCRYPT 2021 - 40th\n                   Annual International Conference on the Theory and\n                   Applications of Cryptographic Techniques, Zagreb,\n                   Croatia, October 17-21, 2021, Proceedings, Part I","volume":"12696","author":"Itai Dinur","year":"2021"},{"key":"ref3:bbdv","doi-asserted-by":"publisher","first-page":"130","DOI":"10.46586\/tosc.v2020.i4.130-146","article-title":"Cryptanalysis of LowMC instances using single\n                   plaintext\/ciphertext pair","volume":"2020","author":"Subhadeep Banik","year":"2020","journal-title":"IACR Trans. Symmetric Cryptol."},{"author":"Lorenzo Grassi","key":"ref4:bibid","article-title":"Survey of Key-Recovery Attacks on LowMC in a Single\n                   Plaintext\/Ciphertext Scenario"},{"key":"ref5:bbvy","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-030-92062-3_11","article-title":"New Attacks on LowMC Instances with a Single\n                   Plaintext\/Ciphertext Pair","volume-title":"Advances in Cryptology - ASIACRYPT 2021 - 27th\n                   International Conference on the Theory and\n                   Application of Cryptology and Information Security,\n                   Singapore, December 6-10, 2021, Proceedings, Part\n                   I","volume":"13090","author":"Subhadeep Banik","year":"2021"},{"key":"ref6:alg","first-page":"255","article-title":"A Simple Algebraic Attack on 3-Round LowMC","volume":"2021","author":"Fukang Liu","year":"2021","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref7:fselmc","doi-asserted-by":"publisher","first-page":"102","DOI":"10.46586\/tosc.v2022.i3.102-122","article-title":"New Low-Memory Algebraic Attacks on LowMC in the\n                   Picnic Setting","volume":"2022","author":"Fukang Liu","year":"2022","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"ref8:f2","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/978-3-642-15031-9_14","article-title":"Fast Exhaustive Search for Polynomial Systems in\n                   F\\({}_{\\mbox{2}}\\)","volume-title":"Cryptographic Hardware and Embedded Systems, CHES\n                   2010, 12th International Workshop, Santa Barbara, CA,\n                   USA, August 17-20, 2010. Proceedings","author":"Charles Bouillaguet","year":"2010"},{"author":"Greg Zaverucha","key":"ref9:pic","article-title":"The PICNIC Signaure Algorithm Specifications, Version\n                   3.0, Available at\n  https:\/\/github.com\/microsoft\/Picnic\/blob\/master\/spec\/spec-v3.0.pdf"},{"key":"ref10:ham","isbn-type":"print","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/978-3-642-21702-9_6","article-title":"An Improved Algebraic Attack on Hamsi-256","volume-title":"Fast Software Encryption","author":"Itai Dinur","year":"2011","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642217029"},{"key":"ref11:lok","doi-asserted-by":"publisher","first-page":"2190","DOI":"10.1137\/1.9781611974782.143","article-title":"Beating Brute Force for Systems of Polynomial\n                   Equations over Finite Fields","volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM\n                   Symposium on Discrete Algorithms, SODA 2017,\n                   Barcelona, Spain, Hotel Porta Fira, January 16-19","author":"Daniel Lokshtanov","year":"2017"},{"key":"ref12:dsoda","doi-asserted-by":"publisher","first-page":"2550","DOI":"10.1137\/1.9781611976465.151","article-title":"Improved Algorithms for Solving Polynomial Systems\n                   over GF(2) by Multiple Parity-Counting","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on\n                   Discrete Algorithms, SODA 2021, Virtual Conference,\n                   January 10 - 13, 2021","author":"Itai Dinur","year":"2021"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T21:25:25Z","timestamp":1733865925000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/1\/22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,9]]},"references-count":12,"URL":"https:\/\/doi.org\/10.62056\/ayzojbkrz","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"type":"electronic","value":"3006-5496"}],"subject":[],"published":{"date-parts":[[2024,4,9]]},"assertion":[{"value":"2024-01-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-05","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-1-56"}}