Paper 2015/407

Higher-Order Cryptanalysis of LowMC

Christoph Dobraunig, Maria Eichlseder, and Florian Mendel

Abstract

LowMC is a family of block ciphers developed particularly for use in multi-party computations and fully homomorphic encryption schemes, where the main performance penalty comes from non-linear operations. Thus, LowMC has been designed to minimize the total quantity of logical "and" operations, as well as the "and" depth. To achieve this, the LowMC designers opted for an incomplete S-box layer that does not cover the complete state, and compensate for it with a very dense, randomly chosen linear layer. In this work, we exploit this design strategy in a cube-like key-recovery attack. We are able to recover the secret key of a round-reduced variant of LowMC with 80-bit security, where the number of rounds is reduced from 11 to 9. Our attacks are independent of the actual instances of the used linear layers and therefore, do not exploit possible weak choices of them. From our results, we conclude that the resulting security margin of 2 rounds is smaller than expected.

Note: updated publication information (ICISC 2015)

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. ICISC 2015
DOI
10.1007/978-3-319-30840-1_6
Keywords
cryptanalysishigher-order cryptanalysisLowMCkey recoveryzero-sum distinguisher
Contact author(s)
maria eichlseder @ iaik tugraz at
History
2016-08-25: revised
2015-05-01: received
See all versions
Short URL
https://ia.cr/2015/407
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/407,
      author = {Christoph Dobraunig and Maria Eichlseder and Florian Mendel},
      title = {Higher-Order Cryptanalysis of LowMC},
      howpublished = {Cryptology ePrint Archive, Paper 2015/407},
      year = {2015},
      doi = {10.1007/978-3-319-30840-1_6},
      note = {\url{https://eprint.iacr.org/2015/407}},
      url = {https://eprint.iacr.org/2015/407}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.