A Three-Stage MITM Attack on LowMC from a Single Plaintext-Ciphertext Pair

The block cipher LowMC was proposed by Albrecht et al. at EUROCRYPT 2015 for a low multiplicative complexity. Over the years, LowMC has been receiving widespread cryptanalytic attention. Recently, the digital signature scheme PICNIC3, an alternative third-round candidate in NIST’s Post-Quantum Cryptography competition, has been proposed and utilized LowMC as the underlying block cipher. The security of PICNIC3 can be reduced to the security of underlying LowMC in a single plaintext-ciphertext scenario. However, this scenario results in inapplicability of conventional cryptanalysis method like differential or linear cryptanalysis, which require many chosen plaintexts or ciphertexts. At ASIACRYPT 2021, Banik et al. used a linearization technique of the LowMC SBox and gave a two-stage MITM attack on LowMC instances from a single plaintext-ciphertext pair. In this paper, we revisit the Banik et al.’s work and make a more precise analysis of the independence of multiple-round subkey bits, deriving the method of estimating the success probability of this attack. Then we generalize the two-stage MITM attack into a three-stage MITM attack on LowMC instances with partial SBoxes layers. We add one MITM phase to further filter the reduced candidate set and successfully screen out the full master key bits with lower computational complexity. As a result, we improve Banik et al.’s attack and give a higher-round cryptanalysis for these instances.