Paper 2023/1872

Integral Multiset: A Novel Framework for Integral Attacks over Finite Fields

Weizhe Wang, Shanghai Jiao Tong University
Deng Tang, Shanghai Jiao Tong University

In recent years, symmetric primitives that focus on arithmetic metrics over large finite fields, characterized as arithmetization-oriented (\texttt{AO}) ciphers, are widely used in advanced protocols such as secure multi-party computations (MPC), fully homomorphic encryption (FHE) and zero-knowledge proof systems (ZK). To ensure good performance in protocols, these \texttt{AO} ciphers are commonly designed with a small number of multiplications over finite fields and low multiplicative depths. This feature makes \texttt{AO} ciphers vulnerable to algebraic attacks, especially integral attacks. While a far-developed analysis for integral attacks on traditional block ciphers defined over $\mathbb{F}_2$ exists, there is still a lack of research on this kind of attacks over large finite fields. Previous integral attacks over large finite fields are primarily higher-order differential attacks, which construct distinguishers by simply utilizing algebraic degrees without fully exploiting other algebraic properties of finite fields. In this paper, we propose a new concept called \textit{integral multiset}, which provides a clear characterization of the integral property of multiset over the finite field $\mathbb{F}_{p^n}$. Based on multiplicative subgroups of finite fields, we present a new class of integral multisets that exhibits completely different integral property compared to the previously studied multisets based on vector subspaces over the finite field $\mathbb{F}_2$. In addition, we also present a method for merging existing integral multisets to create a new one with better integral property. Furthermore, combining with monomial detection techniques, we propose a framework for searching for integral distinguishers based on integral multisets. We apply our new framework to some competitive \texttt{AO} ciphers, including \textsf{MiMC} and \textsf{Chaghri}. For all these ciphers, we successfully find integral distinguishers with lower time and data complexity. Especially for \textsf{MiMC}, the complexity of some distinguishers we find is only a half or a quarter of the previous best one. Due to the specific algebraic structure, all of our results could not be obtained by higher-order differential attacks. Furthermore, our framework perfectly adapts to various monomial detection techniques like general monomial prediction proposed by Cui et al. at ASIACRYPT 2022 and coefficient grouping invented by Liu et al. at EUROCRYPT 2023. We believe that our work will provide new insight into integral attacks over large finite fields.

Available format(s)
Secret-key cryptography
Publication info
integral attackintegral multisetmultiplicative subgroupmonomial detection
Contact author(s)
SJTUwwz @ sjtu edu cn
dengtang @ sjtu edu cn
2023-12-06: approved
2023-12-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Weizhe Wang and Deng Tang},
      title = {Integral Multiset: A Novel Framework for Integral Attacks over Finite Fields},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1872},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.