Paper 2023/1872

Inner Product Masked Integral Distinguishers and Integral Sets over Large Finite Fields (Full Version)

Abstract

The security and performance of many advanced protocols heavily rely on the underlying symmetric-key primitives. These primitives, known as arithmetization-oriented (\texttt{AO}) ciphers, focus on arithmetic metrics over large finite fields. Most \texttt{AO} ciphers are vulnerable to algebraic attacks, especially integral attacks. In this work, we explore integral attacks over large finite fields. By combining integral distinguishers with inner product masks, we propose inner product masked (IPM) integral distinguishers and establish a system of equations concerning the inner product mask. Additionally, we provide theoretical lower bounds on the complexity of IPM integral distinguishers in certain cases. For practical applications, we introduce IPM integral sets, which effectively characterize the integral property of sets over the finite field $\mathbb{F}_{p^n}$. Besides the IPM sets based on additive subgroups and multiplicative subgroups, we present a method to obtain sets with improved integral properties by merging existing sets. Exploring different classes of IPM integral sets can help us find lower-complexity integral distinguishers. Combining with monomial detection techniques, we propose a framework for searching for integral distinguishers based on the IPM integral set. Our framework is compatible with various monomial detection techniques, including general monomial prediction proposed by Cui et al. at ASIACRYPT 2022 and coefficient grouping invented by Liu et al. at EUROCRYPT 2023. Previous integral distinguishers over $\mathbb{F}_{2^n}$ were predominantly based on additive subgroups. With IPM integral sets based on multiplicative subgroups and merged sets, we successfully obtain IPM integral distinguishers with lower complexity for \textsf{MiMC}, \textsf{CIMINION}, and \textsf{Chaghri}. We believe that our work will provide new insights into integral attacks over large finite fields.