### On the Algebraic Degree of Iterated Power Functions

##### 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.

Note: Revised submission after publication to DCC.

Available format(s)
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
See all versions
Short URL
https://ia.cr/2022/366

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},
note = {\url{https://eprint.iacr.org/2022/366}},
url = {https://eprint.iacr.org/2022/366}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.