On the Algebraic Degree of Iterated Power Functions

Clémence Bouvier; Anne Canteaut; Léo Perrin

Paper 2022/366

On the Algebraic Degree of Iterated Power Functions

Clémence Bouvier, Sorbonne University, French Institute for Research in Computer Science and Automation

Anne Canteaut, French Institute for Research in Computer Science and Automation

Léo Perrin, French Institute for Research in Computer Science and Automation

Abstract

New symmetric primitives are being designed to address a novel set of design criteria. Instead of being executed on regular processors or smartcards, they are instead intended to be run in abstract settings such as multi-party computations or zero-knowledge proof systems. This implies in particular that these new primitives are described using operations over large finite fields. As the number of such primitives grows, it is important to better understand the properties of their underlying operations. In this paper, we investigate the algebraic degree of one of the first such block ciphers, namely MiMC. It is composed of many iterations of a simple round function, which consists of an addition and of a low-degree power permutation applied to the full state, usually . We show in particular that, while the univariate degree increases predictably with the number of rounds, the algebraic degree (a.k.a multivariate degree) has a much more complex behaviour, and simply stays constant during some rounds. Such plateaus slightly slow down the growth of the algebraic degree. We present a full investigation of this behaviour. First, we prove some lower and upper bounds for the algebraic degree of an arbitrary number of iterations of MiMC and of its inverse. Then, we combine theoretical arguments with simulations to prove that the upper bound is tight for up to 16265 rounds. Using these results, we slightly improve the higher-order differential attack presented at Asiacrypt 2020 to cover one or two more rounds. More importantly, our results provide some precise guarantees on the algebraic degree of this cipher, and then on the minimal complexity for a higher-order differential attack.

Note: Revised submission after publication to DCC.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Designs, Codes and Cryptography (2022)
DOI: 10.1007/s10623-022-01136-x
Keywords: symmetric cryptography cryptanalysis block cipher finite field algebraic degree MiMC higher order differential attack
Contact author(s): clemence bouvier @ inria fr
anne canteaut @ inria fr
leo perrin @ inria fr
History: 2022-11-04: revised; 2022-03-22: received; See all versions
Short URL: https://ia.cr/2022/366
License: CC BY

BibTeX

@misc{cryptoeprint:2022/366,
      author = {Clémence Bouvier and Anne Canteaut and Léo Perrin},
      title = {On the Algebraic Degree of Iterated Power Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/366},
      year = {2022},
      doi = {10.1007/s10623-022-01136-x},
      url = {https://eprint.iacr.org/2022/366}
}