Cryptology ePrint Archive: Report 2022/366

On the Algebraic Degree of Iterated Power Functions

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

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 $x \mapsto x^{3}$. 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.

Category / Keywords: secret-key cryptography / symmetric cryptography, cryptanalysis, block cipher, finite field, algebraic degree, MiMC, higher order differential attack

Date: received 18 Mar 2022, last revised 19 Mar 2022

Contact author: clemence bouvier at inria fr, anne canteaut at inria fr, leo perrin at inria fr

Available format(s): PDF | BibTeX Citation

Version: 20220322:132432 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]