Welcome to the resource topic for 2022/688
Title:
Memory-Efficient Single Data-Complexity Attacks on LowMC Using Partial Sets
Authors: Subhadeep Banik, Khashayar Barooti, Andrea Caforio, and Serge Vaudenay
Abstract: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.
ePrint: https://eprint.iacr.org/2022/688
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .