International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Nonlinear Approximations in Cryptanalysis Revisited

Authors:
Christof Beierle , SnT, University of Luxembourg
Anne Canteaut , Inria, Paris
Gregor Leander , Horst Görtz Institute for IT Security, Ruhr-Universität Bochum
Download:
DOI: 10.13154/tosc.v2018.i4.80-101
URL: https://tosc.iacr.org/index.php/ToSC/article/view/7362
Search ePrint
Search Google
Presentation: Slides
Abstract: This work studies deterministic and non-deterministic nonlinear approximations for cryptanalysis of block ciphers and cryptographic permutations and embeds it into the well-understood framework of linear cryptanalysis. For a deterministic (i.e., with correlation ±1) nonlinear approximation we show that in many cases, such a nonlinear approximation implies the existence of a highly-biased linear approximation. For non-deterministic nonlinear approximations, by transforming the cipher under consideration by conjugating each keyed instance with a fixed permutation, we are able to transfer many methods from linear cryptanalysis to the nonlinear case. Using this framework we in particular show that there exist ciphers for which some transformed versions are significantly weaker with regard to linear cryptanalysis than their original counterparts.
Video from TOSC 2018
BibTeX
@article{tosc-2018-29247,
  title={Nonlinear Approximations in Cryptanalysis Revisited},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2018, Issue 4},
  pages={80-101},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/7362},
  doi={10.13154/tosc.v2018.i4.80-101},
  author={Christof Beierle and Anne Canteaut and Gregor Leander},
  year=2018
}