Paper 2026/1429

Structured Search for a Separable Subclass of Generalized Integral Properties

Abstract

Generalized integral properties extend classical integral distinguishers, but their search is hindered by the size of the generalized function space. In this work, we study a structured and tractable subclass of generalized integral properties by restricting the generalized Boolean function to a separable form. This separable restriction decouples the plaintext side from the ciphertext side, thereby casting the search as the interplay between plaintext-side suppression of propagation sources and ciphertext-side cancellation of unknown monomials. On the plaintext side, we consider a structured space generated by linear combinations of basic plaintext structures; on the ciphertext side, we work in a degree-bounded Boolean candidate space. This yields an explicit and controllable search space while still capturing meaningful extensions of classical integral distinguishers. Based on this formulation, we develop two matrix-based solving strategies that avoid exhaustive enumeration of the mapping space. The first is a unified MBM (Matrix--Bipartite graph--Matrix) framework, which reduces the joint search to a Boolean constraint system amenable to MILP. The second is a specialized solver for fixed plaintext structures, where the search for ciphertext-side low-degree mappings is reduced to a linear cancellation system and solved by Gaussian elimination. Experiments confirm the practical effectiveness of the proposed methods. For SPECK and SIMON, our search extends the number of rounds covered by mapping-based integral distinguishers. In particular, for SPECK, whose modular-addition structure makes integral modeling considerably more challenging, the proposed framework still yields improved distinguishers. For PRESNET, RECTANGLE, and SKINNY, our methods identify additional balanced integral properties beyond those captured by previous approaches. These results show that structured search provides a practical way to broaden the reach of automated integral analysis across different cipher families.