Exponential sums in linear cryptanalysis

Tim Beyne; Clémence Bouvier

Paper 2024/1755

Exponential sums in linear cryptanalysis

Tim Beyne

, KU Leuven, Ruhr University Bochum

Clémence Bouvier

, Ruhr University Bochum

Abstract

It is shown how bounds on exponential sums derived from modern algebraic geometry, and l-adic cohomology specifically, can be used to upper bound the absolute correlations of linear approximations for cryptographic constructions of low algebraic degree. This is illustrated by applying results of Deligne, Denef and Loeser, and Rojas-León, to obtain correlation bounds for a generalization of the Butterfly construction, three-round Feistel ciphers, and a generalization of the Flystel construction. For each of these constructions, bounds obtained using other methods are significantly weaker. In the case of the Flystel construction, our bounds resolve a conjecture by the designers. Correlation bounds of this type are relevant for the development of security arguments against linear cryptanalysis, especially in the weak-key setting or for primitives that do not involve a key. Since the methods used in this paper are applicable to constructions defined over arbitrary finite fields, the results are also relevant for arithmetization-oriented primitives such as Anemoi, which uses S-boxes based on the Flystel construction.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint.
Keywords: linear cryptanalysis algebraic exponential sums Butterfly Feistel Flystel
Contact author(s): tim beyne @ esat kuleuven be
clemence bouvier @ rub de
History: 2024-10-30: approved; 2024-10-28: received; See all versions
Short URL: https://ia.cr/2024/1755
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1755,
      author = {Tim Beyne and Clémence Bouvier},
      title = {Exponential sums in linear cryptanalysis},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1755},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1755}
}