On the algebraic degree of iterated power functions
Tóm tắt
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 16,265 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.
Tài liệu tham khảo
Aly A., Ashur T., Ben-Sasson E., Dhooghe S., Szepieniec A.: Design of symmetric-key primitives for advanced cryptographic protocols. IACR Trans. Symm. Cryptol. 2020(3), 1–45 (2020).
Albrecht M.R., Cid C., Grassi L., Khovratovich D., Laftenegger R., Rechberger C., Schofnegger, M.: Algebraic cryptanalysis of STARK-friendly designs: Application to MARVELlous and MiMC. In: Galbraith S.D., Moriai S. (eds.) ASIACRYPT. Volume 11923 of LNCS. Springer, Heidelberg, pp. 319–397 (2019).
Albrecht M. R., Grassi L., Perrin L., Ramacher S., Rechberger C., Rotaru D., Roy A., Schofnegger M.: Feistel structures for MPC, and more. In: Kazue S., Steve S., Ryan Y. A. (eds.) ESORICS 2019, Part II
Albrecht M. R., Grassi L., Rechberger C., Roy A., Tyge T.: MiMC: efficient encryption and cryptographic hashing with minimal multiplicative complexity. In: Cheon J. H., Takagi T. (eds) ASIACRYPT 2016, Part I, volume 10031 of LNCS. Springer, Heidelberg, pp. 191–219 (2016).
Aumasson J-.P., Meier W.: Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi. Rump session of Cryptographic Hardware and Embedded Systems-CHES (2009).
Ben-Sasson E., Bentov I., Horesh Y., Riabzev M.: Scalable, transparent, and post-quantum secure computational integrity. Cryptology ePrint Archive, Report 2018/046 (2018). https://eprint.iacr.org/2018/046.
Ben-Sasson E., Goldberg L., Levit D.: STARK friendly hash—survey and recommendation. Cryptology ePrint Archive. Report 2020/948 (2020). https://eprint.iacr.org/2020/948.
Beyne T., Canteaut A., Dinur I., Eichlseder M., Leander G., Leurent G., Naya-Plasencia M., Léo Perrin Y., Sasaki Yosuke T., Wiemer F.: Out of oddity - new cryptanalytic techniques against symmetric primitives optimized for integrity proof systems. In: Micciancio D., Ristenpart T. (eds.) CRYPTO 2020. Part III, volume 12172 of LNCS. Springer, Heidelberg, pp. 299–328 (2020).
Boura C., Canteaut A.: On the influence of the algebraic degree of \(F^{{-1}}\) on the algebraic degree of \({G} \circ {F}\). IEEE Trans. Inf. Theory 59(1), 691–702 (2013).
Bronchain O., Faust S., Lallemand V., Leander G., Perrin L., Standaert F.-X.: Moe: multiplication operated encryption with trojan resilience. IACR Trans. Symmet. Cryptol. 2021(1), 78–129 (2021).
Charpin P.: Handbook of Finite Fields. Chapter PN and APN functions. CRC Press, Boca Raton (2013).
Das P.: The number of permutation polynomials of a given degree over a finite field. Finite Fields Their Appl. 8(4), 478–490 (2002).
Eichlseder M., Grassi L., Lüftenegger R., Øygarden M., Rechberger C., Schofnegger M., Wang Q.: An algebraic attack on ciphers with low-degree round functions: application to full MiMC. In: Moriai S., Wang H. (eds.) ASIACRYPT 2020. Part I, volume 12491 of LNCS. Springer, Heidelberg, pp. 477–506 (2020).
Gamrath G., Anderson D., Bestuzheva K., Chen W. K., Eifler L., Gasse M., Gemander P., Gleixner A., Gottwald L., Halbig K., Hendel G.: The SCIP Optimization Suite 7.0. Technical report, Optimization (2020).
Gamrath G., Anderson D., Bestuzheva K., Chen W. K., Eifler L., Gasse M., Gemander P., Gleixner A., Gottwald L., Halbig K., Hendel G.: The SCIP Optimization Suite 7.0. ZIB-Report 20-10, Zuse Institute Berlin (2020).
Gold R.: Maximal recursive sequences with 3-valued recursive crosscorrelation functions. IEEE Trans. Inf. Theory 14, 154–156 (1968).
Herschfeld A.: The equation \(2^x - 3^y = d\). Bull. Am. Math. Soc. 42(4), 231–234 (1936).
Knudsen L. R.: Truncated and higher order differentials. In: Preneel B. (ed.) FSE’94, vol. 1008. LNCS. Springer, Heidelberg, pp. 196–211 (1995).
Konyagin S., Pappalardi F.: Enumerating permutation polynomials over finite fields by degree. Finite Fields Their Appl. 8(4), 548–553 (2002).
McEliece J.R.: Finite Fields for Computer Scientists and Engineers. Springer Verlag, Berlin (1987).
Nyberg K.: Differentially uniform mappings for cryptography. In: Helleseth T (ed.) EUROCRYPT’93, vol. 765. LNCS. Springer, Heidelberg, pp. 55–64 (1994).
Wells C.: The degrees of permutation polynomials over finite fields. J. Comb. Theory 7(1), 49–55 (1969).