Cryptanalysis of LowMC instances using single plaintext/ciphertext pair

Authors

  • 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

DOI:

https://doi.org/10.46586/tosc.v2020.i4.130-146

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.

Downloads

Published

2020-12-10

Issue

Section

Articles

How to Cite

Cryptanalysis of LowMC instances using single plaintext/ciphertext pair. (2020). IACR Transactions on Symmetric Cryptology, 2020(4), 130-146. https://doi.org/10.46586/tosc.v2020.i4.130-146