Paper 2022/688

Memory-Efficient Single Data-Complexity Attacks on LowMC Using Partial Sets

Subhadeep Banik, USI Università della Svizzera italiana
Khashayar Barooti, Ecole polytechnique fédérale de Lausanne
Andrea Caforio, Ecole polytechnique fédérale de Lausanne
Serge Vaudenay, Ecole polytechnique fédérale de Lausanne

The LowMC family of block ciphers was first proposed by Albrecht et al. in [ARS+15], specifically targeting adoption in FHE and MPC applications due to its low multiplicative complexity. The construction operates a 3-bit 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 [Din21a], in which a novel way of enumerating the 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. [BBDV20]. This amalgamation yields a drastic reduction in terms of memory complexity across all instantiations of LowMC up to six rounds with a quasi-equivalent time complexity.

Available format(s)
Attacks and cryptanalysis
Publication info
Contact author(s)
subhadeep banik @ protonmail com
khashayar barooti @ epfl ch
andrea caforio @ epfl ch
serge vaudenay @ epfl ch
2022-05-31: approved
2022-05-31: received
See all versions
Short URL
No rights reserved


      author = {Subhadeep Banik and Khashayar Barooti and Andrea Caforio and Serge Vaudenay},
      title = {Memory-Efficient Single Data-Complexity Attacks on LowMC Using Partial Sets},
      howpublished = {Cryptology ePrint Archive, Paper 2022/688},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.