Cryptanalysis of LowMC instances using single plaintext/ciphertext pair

  • Subhadeep Banik LASEC, École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland
  • Khashayar Barooti LASEC, École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland
  • F. Betül Durak Robert Bosch LLC - Research and Technology Center - Pittsburgh PA, USA
  • Serge Vaudenay LASEC, École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland
Keywords: LowMC, PICNIC Signature Scheme, MITM, 3-xor problem

Abstract

Arguably one of the main applications of the LowMC family ciphers is in the post-quantum signature scheme PICNIC. Although LowMC family ciphers have been studied from a cryptanalytic point of view before, none of these studies were directly concerned with the actual use case of this cipher in PICNIC signature scheme. Due to the design paradigm of PICNIC, an adversary trying to perform a forgery attack on the signature scheme instantiated with LowMC would have access to only a single given plaintext/ciphertext pair, i.e. an adversary would only be able to perform attacks with data complexity 1 in a known-plaintext attack scenario. This restriction makes it impossible to employ classical cryptanalysis methodologies such as differential and linear cryptanalysis. In this paper we introduce two key-recovery attacks, both in known-plaintext model and of data complexity 1 for two variants of LowMC, both instances of the LowMC cryptanalysis challenge.

Published
2020-12-10
How to Cite
Banik, S., Barooti, K., Durak, F. B., & Vaudenay, S. (2020). Cryptanalysis of LowMC instances using single plaintext/ciphertext pair. IACR Transactions on Symmetric Cryptology, 2020(4), 130-146. https://doi.org/10.46586/tosc.v2020.i4.130-146
Section
Articles