Paper 2015/418

Optimized Interpolation Attacks on LowMC

Itai Dinur, Yunwen Liu, Willi Meier, and Qingju Wang

Abstract

LowMC is a collection of block cipher families introduced at Eurocrypt 2015 by Albrecht et al. Its design is optimized for instantiations of multi-party computation, fully homomorphic encryption, and zero-knowledge proofs. A unique feature of LowMC is that its internal affine layers are chosen at random, and thus each block cipher family contains a huge number of instances. The Eurocrypt paper proposed two specific block cipher families of LowMC, having 80-bit and 128-bit keys. In this paper, we mount interpolation attacks (algebraic attacks introduced by Jakobsen and Knudsen) on LowMC, and show that a practically significant fraction of $2^{-38}$ of its 80-bit key instances could be broken $2^{23}$ times faster than exhaustive search. Moreover, essentially all instances that are claimed to provide 128-bit security could be broken about $1000$ times faster. In order to obtain these results, we had to develop novel techniques and optimize the original interpolation attack in new ways. While some of our new techniques exploit specific internal properties of LowMC, others are more generic and could be applied, in principle, to any block cipher.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Block cipherLowMChigh-order differential cryptanalysisinterpolation attack.
Contact author(s)
dinur @ di ens fr
History
2015-05-05: received
Short URL
https://ia.cr/2015/418
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/418,
      author = {Itai Dinur and Yunwen Liu and Willi Meier and Qingju Wang},
      title = {Optimized Interpolation Attacks on LowMC},
      howpublished = {Cryptology ePrint Archive, Paper 2015/418},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/418}},
      url = {https://eprint.iacr.org/2015/418}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.