Invariant Subspace of the P-SPN Structure with a Class of Linear Layer Matrix

I.   Introduction

Modern cryptography developed many techniques that go well beyond solving traditional confidentiality and authenticity problems in two-party communications. This includes practical applications of secure multi-party computation (MPC), fully homomorphic encryption (FHE), and zero-knowledge (ZK) proofs using symmetric primitives. Designs of primitives in symmetric cryptography for these applications are usually led by heuristics such as simplifying their arithmetic representations or linear operations being more efficient than nonlinear ones in these scenarios. The latter example is also used in the context of masking, a widespread countermeasure against side-channel attacks in which all the computations are performed on shared secrets.

Motivated by advancements in various application domains, there has been a recent surge in the proposal of novel symmetric cryptographic primitives. There is an increasing number of MPC-/FHE-/ZK-friendly proposals, including LowMC [1], FLIP [2], Kreyvium [3], Rasta [4], Dasta [5], MiMC [6], [7], GMiMC [8], HadesMiMC [9], Ciminion [10], Jarvis and Friday [11], Vision and Rescue [12], Starkad [13], Rubato [14], HERA [15], Poseidon [16], and Poseidon2 [17].

Some of the recalled designs reach the goal of minimizing the total number of multiplications by making use of iterative round functions with a partial S-box layer. These designs are called partial substitution-permutation network (P-SPN) schemes in [18]. They are a variant of SPN schemes, in which an input block is transformed into an output block by applying several alternating rounds of substitution boxes and affine permutations to provide confusion and diffusion. At Eurocrypt 2020, Grassi et al. proposed the HADES design strategy that combines the classical SPN construction with the P-SPN construction [9]. In many cases, the permutation layer is a linear operation defined by the multiplication of the state with a $t\times t$ matrix. In the case of a partial substitution-permutation network, however, part of the substitution layer is replaced by an identity mapping, leading to practical advantages for applications in which nonlinear operations are more expensive than linear operations. In the P-SPN structure schemes, because only part of the S-box of the nonlinear layer has a real nonlinear transformation, when considering the propagation of the subspace path, the value of a considerable part remains unchanged before and after the nonlinear layer, so the linear layer plays a more critical role in the iteration of the scheme.

Design of schemes using the P-SPN structure has obvious performance advantages in various scenarios, was used in the block ciphers Zorro [18] and LowMC [1]. A drawback of this approach is that ‘clean’ security arguments (like the wide trail strategy) are not applicable for P-SPNs, and thus, the security of these designs was argued by more ad-hoc approaches. These turned out to be insufficient,as Zorro was practically broken in literature [19] and the security of the initial versions of LowMC was shown in [20] and [21] to be significantly lower that claimed by the designers.

Bar-On et al. delve into the strategic selection of parameters within the P-SPN structure, specifically addressing the quantity of S-boxes per round [22]. They ultimately validate that the P-SPN structural paradigm is devoid of inherent flaws, advocating its applicability in the design of forthcoming cryptographic algorithms. The fact that the resistance against invariant subspace attacks is related to the degree of the minimal polynomial of the linear layer has already been brought out by Beierle et al. in [23]. They also reported that if the linear layer’s minimal polynomial has a high degree, round constants which guarantee the resistance to all types of invariant attacks, including invariant subspace attack and nonlinear invariant attack, can be easily found. Grassi et al. contribute to the discourse by conducting an exhaustive analysis of the security aspects of the P-SPN and HADES structures under conditions of infinitely long invariant subspace traces and infinite long iterative subspace traces. They explore the ramifications of selecting the linear layer on the overall security posture. Furthermore, they introduce three algorithms that serve as a safety assessment toolkit for designers when making choices regarding the linear layer components. In a culminating revelation, they articulate a sufficient condition that ascertains the absence of infinite long invariant or iterative subspace traces in the algorithm, predicated on the minimal polynomial of the linear layer matrix meeting certain specific criteria [24].

At Eurocrypt 2021, Keller et al. conducted an in-depth examination of the security within the P-SPN component of the Starkad scheme, uncovering a space attack against it. Additionally, they introduced the Keller-Rosemarin conjecture, which pertains to the degree of the minimal polynomial associated with the linear matrix of the scheme [25]. Building upon this foundation, Wang et al. offered a more detailed analysis of the characteristics of the special block matrix [26]. They addressed the conjecture by providing a detailed proof, subsequently unveiling a higher-dimensional subspace for the Starkad scheme. Their research advanced the understanding of special block matrices with unique structural forms, furnishing an upper bound for the degree of the minimal polynomial across various matrix types, including those with special block matrix with circulant blocks. However, the aforementioned studies have limitations, as they only delineate the precise dimension of the invariant subspace for the specific case where $s=1$. This indicates that while significant strides have been made, further investigation is required to generalize these findings to broader scenarios within the field of cryptographic algorithm design.

In the realm of cryptographic analysis, the identification of a subspace trail inherently serves as a distinguisher for the P-SPN scheme under scrutiny. The mere presence of such a trail not only sets it apart from a pseudo-random permutation but also paves the way for potential attacks. A case in point is the preimage attack on the Poseidon hash function, which capitalizes on the existence of these trails, as recently demonstrated in [[27], Sect. 6.2]. Thus, in the case of a “weak” MDS matrix, an attacker can potentially choose an input space of texts for which no S-box is activated [28] in the rounds with partial S-box layers. This exploitable vulnerability was precisely what enabled the attacks on the specific matrices employed in Poseidon, where corresponding vulnerabilities in the hash functions were identified in [25], [27].

Our Contribution. In this paper we study the effect of the special MDS matrix on the security level of P-SPN designs. To mitigate the impact of nonlinear layers on path propagation within subspaces, our study hones in on those subspaces that persistently fail to activate the S-boxes during the scheme's iterations. At this point, our focus shifts to understanding the pivotal role that the properties of the linear layer assume in the security apparatus of the P-SPN structural scheme. Regarding the linear layer matrix ${\bf{M}}$, our investigation endeavors to explore the conditions that give rise to subspaces of substantial large dimensions. The choice of both the quantity and the strategic placement of S-boxes within P-SPN (Permutation-Substitution Permutation Network) structures significantly influences the algorithmic security, necessitating further investigation into the optimization and positioning of these nonlinear components. Our research is dedicated to attaining a comprehensive understanding of the properties of the linear layer and their contribution to the security of P-SPN design. It aims to provide critical insights into enhancing the cryptographic robustness of P-SPN structures, ensuring their resilience against emerging threats and vulnerabilities.

In our work, we investigated the security of the P-SPN’s structure for a class of special matrices.

Firstly, we construct a special block matrix with circulant block ${\bf{M}}$, which is employed in the linear layer matrix of the P-SPN structure schemes. Through the in-depth analysis of this kind of matrix, the properties that can be used effectively are obtained.

In addition, we present the annihilating polynomial of low degree of this special block matrix with circulant block,

In the special block matrix with circulant block ${\bf{M}}$, $c_{i,j}$ represents the elements, and $(l, k)$ denotes the dimensions of the matrix. Moreover, we put forward the range of determining its minimum polynomial degree, which satisfied certain essential conditions. Within this framework, the degree $d$ is associated with the matrix, culminating at a maximum value of $2^k$.

Finally, we provide a lower bound estimate for the dimension of the maximum invariant subspace within the P-SPN structure schemes when it incorporates this specific type of matrix. The estimate is given by $2^{k+l}-sd$, where $s$ denotes the number of S-boxes within the nonlinear layer. On the one hand, for instances of the P-SPN structure schemes where $s=1$, we are able to precisely determine the dimension of its maximum invariant subspace, which is $2^{k+l}-d$. On the other hand, for cases with $s>1$, with some certain specific conditions, our research establishes more compact lower bound for the dimensionality of the maximum invariant subspace,i.e., $t-(sd-2^k\cdot(d/2-1))$.

Previous literature has concluded that no invariant subspace exists when $s=2^k$. However, our work further challenges and refutes that perspective. The specific results are shown in Table 1. This paper presents a series of instance results based on the special block matrix with circulant block and the corresponding number and position of S-boxes. It can be observed that when $l > k$, the dimension of the largest invariant subspace is greater than in the case where $l \leq k$. Therefore, from a design perspective, it is recommended to use parameters with $l > k$ when constructing the linear layer with such matrices.

Table  1.  In accordance with the P-SPN structure scheme and the linear layer matrix configuration presented herein, we delineate the dimensions of the maximum invariant subspaces across various parameter settings. Herein, $s$ denotes the count of S-boxes within the nonlinear layer, $T$ indicates the number of the branch, and $(l, k)$ signifies the order of the matrix. Furthermore, $deg(f)$ is utilized to express the minimal polynomial degree of the linear layer matrix ${\bf{M}}$, and $dim({\cal{U}}_{max})$ represents the dimension of the maximum invariant subspace of the P-SPN structure scheme under the corresponding linear layer.

$(l,k)$	$T$	$deg(f)$	$s$	$dim({\cal{U}}_{max})$
$(2,1)$	$2^3=8$	$2^1$	$1$	$6$
			$2$	$\geq 4$
$(2,2)$	$2^4=16$	$2^2$	$1$	$12$
			$4$	$\geq 4$
$(2,3)$	$2^5=32$	$2^3$	$1$	$24$
$(3,1)$	$2^4=16$	$2^1$	$1$	$14$
			$2$	$\geq 12$
$(3,2)$	$2^5=32$	$2^2$	$1$	$28$
			$4$	$\geq 20$
$(3,3)$	$2^6=64$	$2^3$	$1$	$56$
			$8$	$\geq 24$
$(3,4)$	$2^7=128$	$2^4$	$1$	$112$
$(4,1)$	$2^5=32$	$2^1$	$1$	$30$
			$2$	$\geq 28$
$(4,2)$	$2^6=64$	$2^2$	$1$	$60$
			$4$	$\geq 52$
$(4,3)$	$2^7=128$	$2^3$	$1$	$120$
			$8$	$\geq 88$
$(4,4)$	$2^8=256$	$2^4$	$1$	$240$
			$16$	$\geq 112$
$(4,5)$	$2^9=512$	$2^5$	$1$	$480$
$(5,1)$	$2^6=64$	$2^1$	$1$	$62$
			$2$	$\geq 60$
$(5,2)$	$2^7=128$	$2^2$	$1$	$124$
			$4$	$\geq 116$
$(5,3)$	$2^8=256$	$2^3$	$1$	$248$
			$8$	$\geq 216$
$(5,4)$	$2^9=512$	$2^4$	$1$	$496$
			$16$	$\geq 368$
$(5,5)$	$2^{10}=1024$	$2^5$	$1$	$992$
			$32$	$\geq 480$
$(6,1)$	$2^7=128$	$2^1$	$1$	$126$
			$2$	$\geq 124$
$(6,2)$	$2^8=256$	$2^2$	$1$	$252$
			$4$	$\geq 244$
$(6,3)$	$2^9=512$	$2^3$	$1$	$504$
			$8$	$\geq 472$

 | Show Table

DownLoad: CSV

Structure of the Paper. The rest of paper is organised as follows. In Sect.2, we give some notations and definitions used throughout the paper. Sect.3 introduces special block matrix with circulant block over a binary field and its properties. Then we focus on the annihilating polynomial of low degree of this type of special matrix, as well as puts forward the range of determining its minimum polynomial degree. In Sect.4, we provide the dimension of the largest invariant subspace within the P-SPN structure schemes when it incorporates this specific type of matrix. Finally, we conclude the paper in Sect. 5.

II.   Preliminaries

In this section, we introduce the notations and definitions essential for the concepts and analyses presented throughout this paper.

Notation

$(1)$ The finite fields under consideration are denoted by $\mathbb{F}_q$, where $q = 2^n$ and $n \in \mathbb{N}^+$.

$(2)$ Subspaces are indicated with calligraphic letters, e.g., ${\cal{U}}$. For a given subspace ${\cal{U}} \subset \mathbb{F}_q$, the complementary subspace is denoted by ${\cal{U}}^c \subset \mathbb{F}_q$ such that ${\cal{U}} \oplus {\cal{U}}^c = \mathbb{F}_q$.

$(3)$ Matrices are represented by uppercase bold letters, e.g., ${\bf{M}}$. Additionally, ${\bf{M}}[i,j]$ represents the element at the $i$-th row and $j$-th column of the matrix, and ${\bf{M}}[i,:]$ represents all elements in the $i$-th row of the matrix.

$(4)$ In this paper, we employ the boldface notation ${\bf{0}}$ to denote a fully zeroed matrix or vector;

$(5)$ Vectors are represented by boldface italic capital letters, e.g., ${\boldsymbol{X}}$.

1   Partial SPN Schemes

In this paper, we will focus on P-SPN block ciphers and permutations over $\mathbb{F}_{q}$. All our results are independent of the round keys and constants. For this reason, in the following we do not clearly distinguish between block ciphers and unkeyed permutations, and we just refer to them using the term schemes.

${\bf{Partial\; SPN\; Schemes\; (P-SPN)}}$ [18]. We denote the application of $r$ rounds of a $t$-word P-SPN scheme by $E^{r}\colon \mathbb{F}_{q}^{t}\rightarrow \mathbb{F}_{q}^{t}$. For every input ${\boldsymbol{X}}=(x_{1},\ldots,x_{t}\in \mathbb{F}_{q}^{t})$, the output is defined by $E^{r}({\boldsymbol{X}})=(R_{r}\circ \ldots \circ R_{0})({\boldsymbol{X}}+ c^{0})$, where $R_{i}\colon \mathbb{F}^{t}\rightarrow \mathbb{F}_{q}^{t}$ is defined as $R_{i}({\boldsymbol{X}})=R({\boldsymbol{X}})+c^{i}$, and $c^{i}$ is a publicly known round constant or a secret round key for $i\in \{0,1,\ldots,r\}$.

As shown in Figure 1, let $1\leq s\leq \lceil t/2 \rceil$ be the number of S-boxes per round. We denote by $R$ the composition of the S-box layer and of the linear layer, i.e., we have $R \colon \mathbb{F}_{q}^{t}\rightarrow \mathbb{F}_{q}^{t}$ with

Figure  1.  One round schematic representation of the P-SPN structure.

DownLoad: Full-Size Img PowerPoint

where $S_{i}\colon \mathbb{F}_{q}\rightarrow \mathbb{F}_{q}$ for $i\in \{1,2,\ldots,s\}$ is a nonlinear permutation, and hence $t-s$ input words are unaffected by the S-box layer, which is the only difference to classical SPN schemes. We also assume that the $s$ S-boxes are applied to the first $s$ words.

The linear layer ${\bf{M}}(\cdot)$ is defined by the multiplication with an invertible matrix ${\bf{M}}\in \mathbb{F}_{q}^{t\times t}$, that is, ${\bf{M}}({\boldsymbol{X}})={\bf{M}} \cdot {\boldsymbol{X}}$. In the following, we assume that the matrix ${\bf{M}}$ ensures full diffusion after a finite number of rounds, in the sense that there exists an $r\in \mathbb{N}$ such that every word of the internal state after the application of $r$ rounds depends on every input word $x_{1},\ldots,x_{t}$.

Before going on, we point out that all word-wise (aligned) P-SPN schemes can be written in the above way.

2   Invariant Subspaces

The invariant subspace attack, initially introduced by Leander et al. in 2011, serves as a potent analytical instrument targeted at block cryptographic algorithms in [29].

This paper consider the following a more general property, for each $a\in \mathbb{F}_{q}^{t}$, there is a unique $b\in \mathbb{F}_{q}^{t}$ such that

where the round function $R$ is defined by Equation (1). In this scenario, the intrinsic nature of the subspace ${\cal{U}}$ remains invariant, yet its coset shifts from the original. The value of $b$ is contingent upon both $a$ and to the round key $k$. Consequently, the concept of an invariant subspace is hereby introduced.

Definition 1 (Invariant Subspace Trail)[24] Let ${\cal{U}} \subset \mathbb{F}_{q}^{t}$ be a subspace. The subspace ${\cal{U}}$ is said to generate an $r$-round invariant subspace of the function $E^{r} \colon \mathbb{F}_{q}^{t} \rightarrow \mathbb{F}_{q}^{t}$ if for all $1 \leq i \leq r$ and for all $a_i \in \mathbb{F}_{q}^{t}$, there exists an $a_{i+1} \in {\cal{U}}^{c}$ such that,

The primary objective of this attack is to identify the so-called invariant subspace, which represents a subset of all potential states and key values. This subset is critical for examining the invariance of the scheme's round transformation. The discovery of such a subset enables an attacker to encrypt plaintext that falls within this subset, posit that the master key is also encompassed by it, and ultimately aims to retrieve the corresponding ciphertext that is likewise a member of the subset. This approach is not only instrumental in crafting a key discriminator but also serves as a viable avenue for key recovery efforts, thereby enhancing the cryptanalysts capability to challenge the security of the cryptographic scheme in question.

3   Special Matrice and Circulant Matrix

In the P-SPN structure scheme, in order to achieve the effect of full diffusion, the linear layer matrix of most algorithms adopts MDS matrix selected randomly. In this subsection, we will introduce the definition of the special matrix and circulant matrix.

Special matrices are defined in the following inductive way.

Definition 2 (Special Matrix) [25] Let the matrix ${\bf{M}}_{2^{k}\times 2^{k}}\in \mathbb{F}_{2^{n}}^{2^{k}\times 2^{k}}$, $k\geq 1$. Matrix ${\bf{M}}$ is called a special matrix if it adheres to the following form:

where ${\bf{A}}_{2^{k-1} \times 2^{k-1}}$ and ${\bf{B}}_{2^{k-1} \times 2^{k-1}}$ are matrices that are also classified as special.

A circulant matrix is defined as a square matrix where each row is a cyclic permutation of the first row.

Definition 3 (Circulant Matrix) Let $c_0, c_1, \ldots, c_{2^k-1}$ be $2^k$ elements from a finite field $\mathbb{F}_{2^n}$, where $k \geq 1$. A matrix ${\bf{C}}$ is referred to as a circulant matrix constructed from these elements if it can be represented as:

III.   Special Block Matrix with Circulant Block and Its Properties

In this section we study the properties of a certain class of matrices over binary fields $\mathbb{F}_{2^{n}}$. Focusing on P-SPN schemes which use the same linear layer in each round, here we study the properties that the matrix that defines the linear layer must satisfy in order to prevent infinitely long invariant subspace trails without active S-boxes.

We present the definition of the special block matrix with circulant block based on the prove definitions.

Definition 4 (Special Block Matrix with Circulant Block) Let ${\bf{M}}$ be a matrix of order $(2^l, 2^k)$, which has $2^{l} \times 2^{l}$ blocks. ${\bf{M}}$ is referred to as a special block matrix with circulant block if it can be represented as:

where $i\in \{0,1,\ldots,2^l-1\}$, and each block matrix ${\bf{C}}_i=\text{circ}(c_{i,0},c_{i,1},\ldots,c_{i,2^{k}-1}) \in \mathbb{F}_{2^{n}}^{2^{k}\times 2^{k}}$ is a circulant matrix. When ${\bf{C}}_i$ serves as an element within the matrix, ${\bf{M}}$ is considered to be of a special block matrix with circulant block.

Next, we recommend the concept of the Kronecker Product, a pivotal tool utilized in the meticulous analysis of special block matrix with circulant block.

Definition 5 (Kronecker Product)[30] Let ${\bf{A}}$ be an $m \times n$ matrix and ${\bf{B}}$ be an $s \times t$ matrix. The Kronecker product of ${\bf{A}}$ and ${\bf{B}}$, denoted by ${\bf{A}} \otimes {\bf{B}}$, is an $ms \times nt$ matrix given by

Therefore, we can calculate the following results.

Corollary 1 For the identity matrix ${\bf{I}}_{2^l}$, it holds that ${\bf{I}}_{2^l}\otimes {\bf{I}}_{2}={\bf{I}}_{2^{l+1}}.$ For the substitution matrix ${\bf{P}}$, there is the following trivial result that, Let ${\bf{P}}_{2^{l}\times 2^{l}}=\text{circ}(0, 1,0,\ldots,0)$ be a substitution matrix with dimension $2^{l}\times 2^{l}$. It holds that ${\bf{P}}^{2^l}=I_{2^l}.$

Building upon the aforementioned definitions and corollaries, we introduce the concept of the Kronecker product monomial. This mathematical construct is instrumental in streamlining the computations presented in the subsequent sections of this manuscript.

Definition 6 (Kronecker Product Monomial.) Let $\mu \in \mathbb{F}_{2^l}$ be represented by its Boolean tuple $(\mu_{l-1}, \ldots, \mu_{1}, \mu_{0})$. We define the Kronecker product monomial $\pi_{\mu}(\cdot)$ associated with $\mu$ for the matrix ${\bf{P}}_2$ as follows:

Here, ${\bf{P}}_2$ denotes the substitution matrix of dimension $2 \times 2$.

With this definition in place, we can study the special block matrix with circulant block in detail, and give some properties for subsequent use.

The following Lemma 1 articulates the representation of a special block matrix with circulant blocks through the Kronecker product monomial. This formulation serves as an exceedingly effective and convenient instrument in the demonstration of several subsequent theorems.

Lemma 1 Let ${\bf{C}}_i = \text{circ}(c_{i,0}, c_{i,1}, \ldots, c_{i,2^k-1}) \in \mathbb{F}_{2^n}^{2^k \times 2^k}$ for $i \in \{0, 1\}$. We can represent a special block matrix with circulant blocks ${\bf{M}}$ of order $(2, 2^k)$ as

Furthermore, a special block matrix with circulant blocks ${\bf{M}}$ of order $(2^l, 2^k)$ can be expressed in the form

Proof To establish the preceding result, we begin by decomposing the special block matrix with circulant block ${\bf{M}}_{2^{1+k} \times 2^{1+k}}$ of order $(2, 2^k)$ as follows:

Furthermore, by the inductive hypothesis, we can similarly decompose the special block matrix with circulant block ${\bf{M}}_{2^{(l-1)+k} \times 2^{(l-1)+k}}$ of order $(2^{l-1}, 2^k)$ as:

For the special block matrix with circulant blocks ${\bf{M}}_{2^{l+k} \times 2^{l+k}}$ of order $(2^l, 2^k)$, let ${\bf{M}}'_i$ for $i \in \{1, 2\}$ be the special block matrix with circulant block ${\bf{M}}_{2^{(l-1)+k} \times 2^{(l-1)+k}}$ of order $(2^{l-1}, 2^k)$. Through iterative calculation, we arrive at the following result:

□

Furthermore, we proceed to demonstrate the power results of a special block matrix with circulant block, commencing with an examination of the square matrix scenario. Consider a special block matrix with circulant block ${\bf{M}}$ of order $(2^l, 2^k)$, where ${\bf{C}}_i = \text{circ}(c_{i,0}, c_{i,1}, \ldots, c_{i,2^k-1}) \in \mathbb{F}_{2^n}^{2^k \times 2^k}$ for $i \in \{0, 1, \ldots, 2^l-1\}$ are circulant matrices. Leveraging Lemma 1, we derive the following:

It is evident that the square power of a special block matrix with circulant block constitutes a highly regular block diagonal matrix, an observation of considerable interest. This insight then paves the way for us to discuss the scenarios of other powers.

Moving forward, we initially turn our attention to the results for ${\bf{M}}^p$, where $2 < p < 2^k$. The first case is delineated by the following Theorem 1, which states that ${\bf{M}}^{2^d}$, where $1 < d < k$.

Theorem 1 Let ${\bf{M}}$ be a special block matrix with circulant block of order $(2^l, 2^k)$, where $i \in \{0, 1, \ldots, 2^l-1\}$, and ${\bf{C}}_i = \text{circ}(c_{i,0}, c_{i,1}, \ldots, c_{i,2^k-1})$ are circulant matrices in $\mathbb{F}_{2^n}^{2^k \times 2^k}$. Then, for $1 < d < k$, the matrix ${\bf{M}}^{2^d}$ retains its form as a special block matrix with circulant block, given by

Furthermore, for every $p \in [1, 2^{k-d}-1]$, if the condition

is satisfied, then

Proof To substantiate the preceding result, we invoke Lemma 1 to derive the following sequence of equalities for the special block matrix with circulant block ${\bf{M}}$ of order $(2^l, 2^k)$:

It is a well-established fact that the product of circulant matrices remains a circulant matrix. Furthermore, $({\bf{C}}_i)^{2} = \text{circ} \Big( \sum_{j=0}^{2-1}(c_{i,0+2^{k-1}j})^{2}, \ldots, \sum_{j=0}^{2-1}(c_{i,2^{k-1}-1+2^{k-1}j})^{2} \Big) \otimes {\bf{I}}_{2}$. In general scenarios, we can directly compute that,

For every $s\in[1, 2^{k-d}-1]$, if

then,

□

Expanding upon the preceding discourse, we now address the second scenario, which posits that for ${\bf{M}}^{2^{d}+s}$, where $s \in [1,2^{d}-1]$, and $1 < d < k$, the matrix ${\bf{M}}$ exhibits specific properties that are pivotal for our subsequent analysis.

Theorem 2 Let ${\bf{M}}$ be a special block matrix with circulant block of order $(2^l, 2^k)$, where each ${\bf{C}}_i = \text{circ}(c_{i,0}, c_{i,1}, \ldots, c_{i,2^k-1})$ is a circulant matrix in $\mathbb{F}_{2^n}^{2^k \times 2^k}$ for $i \in \{0, 1, \ldots, 2^l-1\}$. For $s \in [1, 2^{d}-1]$ and $1 < d < k$, it is demonstrated that the matrix ${\bf{M}}^{2^d + s}$ maintains its structure as a special block matrix with circulant block.

Proof To substantiate the preceding result, we invoke Lemma 1. Consequently, let the binary representation of $s$ be $s = (s_{d-1}, s_{d-2}, \ldots, s_0)$, such that $s = \sum_{i=0}^{d-1} s_i 2^i$.

We demonstrate that,

In general scenarios, for all $i' \in [1, d-1]$, define

Then,

When $s_0 = 0$,

Let $d' \in [1, d]$, for every $p \in [1, 2^{k-d'}-1]$, if

then, we have

The subsequent derivation process is analogous to that of Theorem 1, hence we omit an exhaustive explanation here. It is demonstrated that the matrix ${\bf{M}}^{2^d + s}$ maintains its structure as a special block matrix with circulant block.

□

In the initial section of our analysis, we introduce a pivotal property of circulant matrices, which serves as a foundational element in the subsequent proof of the theorem.

Corollary 2 Let ${\bf{C}}_i = \text{circ}(c_{i,0}, c_{i,1}, \ldots, c_{i,2^k-1})$ be a circulant matrix in $\mathbb{F}_{2^n}^{2^k \times 2^k}$ for $i \in \{0, 1, \ldots, 2^l-1\}$. It follows from the work of [26] that,

Furthermore, we derive a special result, namely,

Proof In order to prove the previous result, we can directly substituting the above general conclusion that,

□

Next, we investigate the conclusions for ${\bf{M}}^{2^k}$.

Theorem 3 Let ${\bf{M}}$ be a special block matrix with circulant block of order $(2^l, 2^k)$, where $i \in \{0, 1, \ldots, 2^l-1\}$, and ${\bf{C}}_i = \text{circ}(c_{i,0}, c_{i,1}, \ldots, c_{i,2^k-1})$ are circulant matrices in $\mathbb{F}_{2^n}^{2^k \times 2^k}$. Then, we have the following result:

Proof To prove the previous result, we leverage the insights derived from Lemmas 1, and 2. We commence by observing that,

This expression facilitates the subsequent demonstration:

□

Example 1 Let ${\bf{M}}$ be a special block matrix with circulant block of $\mathbb{F}_2$, with orders $(2^l, 2^k) = (2^3, 2^2)$. The block matrices are defined as follows:

Consequently, it can be demonstrated that,

In conclusion, we have presented a multitude of properties pertaining to special block matrix with circulant block ${\bf{M}}$, which can be effectively harnessed for further analysis. Moving forward, we delve deeper into the discourse on the annihilating polynomial and the minimal polynomial associated with matrices of this nature.

Theorem 4 Consider a special block matrix ${\bf{M}}$ with circulant blocks with order $(2^l, 2^k)$, where $i \in \{0, 1, \ldots, 2^l-1\}$ and each ${\bf{C}}_i = \text{circ}(c_{i,0}, c_{i,1}, \ldots, c_{i,2^{k}-1})$ is a $2^{k} \times 2^{k}$ circulant matrix over the field $\mathbb{F}_{2^n}$. The annihilating polynomial of matrix ${\bf{M}}$ can be articulated as:

where the degree of the polynomial $f$ is $\deg(f)=2^{k}$. Moreover, the minimal polynomial of matrix ${\bf{M}}$ must be a divisor of any of its annihilating polynomials. Therefore, the minimal polynomial of ${\bf{M}}$ is given by:

where $0 < p \leq \deg(f)$. Specifically, for every $p \in [1, 2^{k-d}-1]$ and $1 \leq d < k$, if matrix ${\bf{M}}$ satisfies the condition

then, ${\bf{M}}$ possesses an annihilating polynomial of a lower degree $2^d$, defined as:

Proof To verify the annihilating polynomial for matrix ${\bf{M}}$, we substitute ${\bf{M}}$ directly into the polynomial, we have

This confirms that $f(x)$ is indeed an annihilating polynomial of ${\bf{M}}$, with a degree of $2^k$.

Furthermore, for every $p \in [1, 2^{k-d}-1]$, where $1 \leq d < k$, and given that,

we can deduce that,

This demonstrates that $f(x)$ is an annihilating polynomial of ${\bf{M}}$ with a degree of $2^d$.

□

In order to make the matrix ${\bf{M}}$, as the linear layer of the P-SPN structure scheme, resist invariant subspace attacks, we hope that the number of minimal polynomial is as large as possible. The following inference gives the condition that the degree of the minimal polynomials of ${\bf{M}}$ equal to $2^k$. When the parameter value selected by the designer meets this condition, a safer linear layer matrix is naturally obtained.

Theorem 5 Let ${\bf{M}}$ be a special block matrix with circulant block of order $(2^l, 2^k)$, where for each $i \in \{0, 1, \ldots, 2^l-1\}$, the matrix ${\bf{C}}_i = \text{circ}(c_{i,0}, c_{i,1}, \ldots, c_{i,2^{k}-1})$ is a $2^k \times 2^k$ circulant matrix over the finite field $\mathbb{F}_{2^n}$. The minimal polynomial of matrix ${\bf{M}}$ has a degree of $d = 2^k$ if and only if ${\bf{M}}^{2^{k}}=\Big( \sum_{i=0}^{2^{l}-1} \sum_{j=0}^{2^{k}-1} (c_{i,j})^{2^{k}} \Big) \cdot {\bf{I}}_{2^{k+l}},$ with ${\bf{M}}^{2^{k-1}}\neq \Big( \sum_{i=0}^{2^{l}-1} \sum_{j=0}^{2^{k}-1} (c_{i,j})^{2^{k-1}} \Big) \cdot {\bf{I}}_{2^{k+l}}.$

Proof We begin by establishing the necessity. If the degree of the minimal polynomial of matrix ${\bf{M}}$ is $d = 2^k$, then the polynomial

cannot be an annihilating polynomial of ${\bf{M}}$. In other words,

This is consistent with Theorem 1, which implies that

Next, we address the sufficiency. According to Theorem 4, the minimal polynomial of ${\bf{M}}$ must be of the form

If ${\bf{M}}^{2^{k-1}} \neq \left( \sum_{i=0}^{2^{l}-1} \sum_{j=0}^{2^{k}-1} (c_{i,j})^{2^{k-1}} \right) \cdot {\bf{I}}_{2^{k+l}}$, then $g(x) = \left(x - \sum_{i=0}^{2^{l}-1} \sum_{j=0}^{2^{k}-1} c_{i,j}\right)^{2^{k-1}}$ cannot be an annihilating polynomial of ${\bf{M}}$, leading to the conclusion that $2^{k-1} < d \leq 2^k$.

For the case where $2^{k-1} < d < 2^k$, by Theorem 2, let $d = 2^{k-1} + s$, with $s \in [1, 2^{k-1}-1]$. If

and considering the binary representation of $s$ as $s = (s_{k-2}, s_{k-3}, \ldots, s_0)$, that is, $s = \sum_{i=0}^{k-2} s_i 2^i$, for all $i' \in [0, k-1]$, let

Then, for every $s \in [1, 2^{k-1}-1]$, referring to Equation (3),

are not in the form of a constant multiplication of the identity matrix. Furthermore,

is not an annihilating polynomial of ${\bf{M}}$. Thus, the degree of the minimal polynomial of matrix ${\bf{M}}$ is indeed $2^k$.

□

IV.   Subspaces of special block matrix with circulant block

In this section, we present a lower bound on the dimension of the maximal invariant subspace for P-SPN scheme with special block matrices with circular block. A generic P-SPN scheme means that when the linear layer of the scheme is any type of matrix, the conclusions in Lemma 2 are always valid.

Lemma 2 [26] Consider a P-SPN structure scheme defined over the field $\mathbb{F}_{2^n}$, with a non-linear layer comprising $s$ S-boxes. The output words following the S-box operation are represented by the set ${\cal{J}} = \{j_0, j_1, \ldots, j_{s-1}\}$. The round function $R$ is characterized by Equation (1). Its linear layer is described by an invertible matrix ${\bf{M}}$, with the minimal polynomial $f(x)$ satisfying $\deg(f) = d$, where $d < \lfloor t/s \rfloor$. The matrix ${\bf{A}}$ is defined by:

where $({\bf{M}}^i)[j_m, :]$ denotes the $j_m$-th row of ${\bf{M}}^i$ for $i \in \{0, 1, \ldots, d-1\}$ and $j_m \in {\cal{J}}$. Denote the solution space of ${\bf{A}} \cdot {\boldsymbol{X}} = {\bf{0}}$ by ${\cal{W}}$. A subspace ${\cal{U}} \subset \mathbb{F}_{2^n}^t$ is an invariant subspace of the P-SPN structure if and only if ${\cal{U}} \subseteq {\cal{W}}$. Moreover, the maximum invariant subspace of the scheme, denoted by ${\cal{U}}_{\text{max}} \subseteq {\cal{W}}$, has a dimension of at least $t - sd$, and for all ${\boldsymbol{X}} \in {\cal{U}}_{\text{max}}$, no S-boxes are activated after any rounds of encryption.

Our work establishes the existence of an invariant subspace through the annihilating polynomial of the linear matrix and its degree. According to the definition of matrix ${\bf{A}}$, the invariant subspace ${\cal{U}}$ in Lemma 2 is naturally a necessary and sufficient condition. That is, if ${\cal{U}} \subseteq {\cal{W}}$, then to generate an infinitely long invariant subspace trail without active S-boxes, it must satisfy ${\cal{U}} = {\bf{M}} \cdot {\cal{U}}$. Furthermore, when invariant subspaces exist, our objective is twofold: to construct the maximal invariant subspace and to ascertain its dimension. This dimension is correlated with both the degree of the annihilating polynomial of the linear matrix and the count of S-boxes in the S-box layer.

In the subsequent sections, we shall delve into the maximal invariant subspaces associated with P-SPN structure schemes. Specifically, we focus on instances where the linear layer matrices are characterized as eversible special block matrix with circulant blocks.

Theorem 6 Given the P-SPN structure scheme defined over finite field $\mathbb{F}_{2^{n}}$. The round function $R$ is defined by Equation (1). The linear layer matrix is an reversible special block matrix with circulant blocks ${\bf{M}}$, and its minimal polynomial is $f(x)$, where $deg(f)=d$, and $d < \lfloor t/s \rfloor$. The non-linear layer consists of $s$ S-boxes, and the set ${\cal{J}} = \{j_0, j_1, \ldots, j_{s-1}\}$ denotes the output words following the S-box operations. Subsequently, the dimension of the maximum invariant subspace ${\cal{U}}_{\text{max}}\subseteq \mathbb{F}_{2^{n}}^{t}$ within the scheme at least $t-sd$. Furthermore, for every vector ${\boldsymbol{X}}\in {\cal{U}}_{\text{max}}$, no S-boxes are activated after any S-boxes after any rounds of encryption.

Proof Since ${\bf{M}}$ is an invertible matrix forming a special block matrix with circulant block of order $(2^l, 2^k)$, and with $f(x)$ being an annihilating polynomial of matrix ${\bf{M}}$, we draw upon Lemma 2 to establish the existence of a subspace ${\cal{U}}_{\text{max}}$ with a dimension of at least $t - sd$. For every vector ${\boldsymbol{X}} \in {\cal{U}}_{\text{max}}$, no S-boxes are activated after any number of rounds within the P-SPN layer.

□

By using Theorem 6, we can get that the lower bound of the dimension of the $R$-round maximal invariant subspace of a special block matrix with circulant blocks is $2^{k+l}-sd$, $R$ represents an arbitrary number of iterative rounds.

For the case of $s = 1$, in which the nonlinear layer of the P-SPN structure algorithm has only one S-box, the accurate value of its maximum invariant subspace dimension can be obtained.

Theorem 7 Given the P-SPN structure scheme defined over finite field $\mathbb{F}_{2^{n}}$. The round function $R$ is defined by Equation (1). The linear layer matrix is an reversible special block matrix with circulant block ${\bf{M}}$, and its minimal polynomial is $f(x)$, where $deg(f)=d$, and $d < \lfloor t/s \rfloor$. The non-linear layer consists of a single S-box ($s = 1$), and the set ${\cal{J}} = \{j\}$ denotes the output words following the S-box operations. Subsequently, the dimension of the maximum invariant subspace ${\cal{U}}_{\text{max}}\subseteq \mathbb{F}_{2^{n}}^{t}$ within the scheme is equal to $t-d$. Furthermore, for every vector ${\boldsymbol{X}}\in {\cal{U}}_{\text{max}}$, no S-boxes are activated after any S-boxes after any rounds of encryption.

Proof To establish the preceding result, we initially define $j = (\varepsilon - 1) \cdot 2^k + \xi$, where $1 \leq \varepsilon \leq 2^l$ and $1 \leq \xi \leq 2^k$. We then construct the matrix

where $({\bf{M}}^i)[j, :]$ denotes the $j$-th row of ${\bf{M}}^i$ for $i \in \{0, 1, \ldots, d-1\}$ and $j \in {\cal{J}}$. It is recognized that ${\bf{A}}$ is a $d \times 2^{k+l}$ matrix. The solution space of ${\bf{A}} \cdot {\boldsymbol{X}} = {\bf{0}}$ is denoted by ${\cal{W}}$. Referring to Lemma 2, the maximum invariant subspace of the scheme is represented as ${\cal{W}} = {\cal{U}}_{\text{max}}$.

For any $i \in \{0, 1, \ldots, d-1\}$, given that ${\bf{M}}$ is a special block matrix with circulant block, Theorems 3.1 and 3.2 demonstrate that ${\bf{M}}^i$ is also a special block matrix with circulant block. Furthermore, each matrix ${\bf{M}}^i$ can be distinctly identified by the $2^l$ matrices located in its $\varepsilon$-th row.

For any $1 \leq \xi' \leq 2^k$, the $({\bf{M}}^i)[(\varepsilon -1) \cdot 2^k + \xi', :]$ is derived from $({\bf{M}}^i)[(\varepsilon -1) \cdot 2^k + \xi, :]$ by a cyclic shift of $\xi - \xi'$ positions to the left, expressible as

where ${\bf{P}}$ is a $2^{k}\times 2^{k}$ substitution matrix, and $\xi-\xi'$ is calculated by modulo $2^{k}$.

To proceed with the proof of $\text{rank}({\bf{A}})=d$, we will utilize the method of contradiction.

When $\xi,\; \xi'$ is fixed, for any $i\in \{0,1,\ldots,d-1\}$, $\xi-\xi'$ is fixed, if we assume that $\text{rank}({\bf{A}})<d$, there is a series of constant $a_0,a_1,\ldots,a_{d-1}$ that are not all zero, such that,

For any $1 \leq \xi' \leq 2^{k}$, it follows that,

Consequently, for every $1 \leq \xi \leq 2^{k}$, we have

Since each matrix ${\bf{M}}^i$ can be distinctly identified by the $2^{l}$ matrices located in its $\varepsilon$-th row, it holds for every $1 \leq \varepsilon' \leq 2^{l}$ that

Thus, we can prove that

At this juncture, we can assert that the polynomial $g(x)=\sum_{i=0}^{d-1} a_i x^i$ serves as an annihilating polynomial for the matrix ${\bf{M}}$, with $g(x)$ having a degree of $d-1$. This finding contradicts the established minimal polynomial degree of ${\bf{M}}$, which is $d$, thereby indicating a discrepancy in our assumptions. Therefore, the rank of the matrix ${\bf{A}}$ is $d$, that is, $\text{rank}({\bf{A}})=d$.

Finally, the dimension of the solution space ${\cal{W}}$ of the equation system ${\bf{A}}\cdot {\boldsymbol{X}}={\bf{0}}$ is $\dim({\cal{W}})=t- \text{rank}({\bf{A}})= t-d$, and thus it follows that

□

Utilizing Theorem 7, we deduce that the lower bound of the dimension of the $R$-round maximal invariant subspace of a special block matrix with circulant blocks is $2^{k+l}-d$, $R$ represents an arbitrary number of iterative rounds.

As everyone knows, the choice of both the quantity and the strategic placement of S-boxes within P-SPN structures significantly influences the algorithmic security, necessitating further investigation into the optimization and positioning of these nonlinear components. Next, we will focus on discussing the relevant aspects of this part.

From Lemma 2, previous literature has concluded that no invariant subspace exists when $s=2^k$. However, our work further challenges and refutes that perspective. The specific conclusion is presented in Theorem 8. The specific results are shown in Table 1.

This paper presents a series of instance results based on the special block matrix with circulant block and the corresponding number and position of S-boxes. It can be observed that when $l > k$, the dimension of the largest invariant subspace is greater than in the case where $l \leq k$. Therefore, from a design perspective, it is recommended to use parameters with $l > k$ when constructing the linear layer with such matrices.

Theorem 8 Given the P-SPN structure scheme defined over the finite field $\mathbb{F}_{2^{n}}^{t}$. The round function $R$ is defined by Equation (1). The linear layer matrix is an reversible special block matrix with circulant block ${\bf{M}}$, and its minimal polynomial is $f(x)$, where $deg(f)=d$, and $d < 2 \lfloor(t/s)-1 \rfloor$. The non-linear layer consists of $s = 2^k$ coterminous S-boxes, all aligned within the same block of the corresponding linear matrix. The set ${\cal{J}}=\{j_{0},j_{1},\ldots,j_{s-1}\}$ represents the output words subsequent to the S-box operations. Subsequently, the dimension of the maximum invariant subspace ${\cal{U}}_{\text{max}}\subseteq \mathbb{F}_{2^{n}}^{t}$ within the scheme is determined to be at least $t-s(d/2+1)$. This calculation provides a compact lower bound for the dimension of the subspace. Furthermore, for every vector ${\boldsymbol{X}}\in {\cal{U}}_{\text{max}}$, no S-boxes are activated after any S-boxes after any rounds of encryption.

Proof To substantiate the preceding result, we initially define the index $j_{\xi} = (\varepsilon - 1) \cdot 2^k + \xi$, where $1 \leq \varepsilon \leq 2^l$ and $0 \leq \xi \leq s - 1$. We then construct the matrix

where $({\bf{M}}^i)[j, :]$ denotes the $j$-th row of the matrix ${\bf{M}}^i$ for $i \in \{0, 1, \ldots, d-1\}$ and $j \in {\cal{J}}$. It is established that ${\bf{A}}$ is a $sd \times 2^{k+l}$ matrix. The solution space of ${\bf{A}} \cdot {\boldsymbol{X}} = {\bf{0}}$ is denoted by ${\cal{W}}$. Furthermore, referring to Lemma 2, the maximum invariant subspace of the scheme is represented as ${\cal{W}} = {\cal{U}}_{\text{max}}$.

We are currently considering a scenario where the non-linear layer comprises $s = 2^k$ coterminous S-boxes, all of which are aligned within the same block of the corresponding linear matrix.

For any $i \in \{0, 1, \ldots, d-1\}$, given that ${\bf{M}}$ is a special block matrix with circulant block, Theorems 3.1 and 3.2 demonstrate that ${\bf{M}}^i$ is also a special block matrix with circulant block. Moreover, it is established that each matrix ${\bf{M}}^i$ can be distinctly identified by the $2^l$ matrices located in its $\varepsilon$-th row.

Assuming the S-box is taken from the block in its $\varepsilon$-th row, ${\bf{A}}$ can be represented as shown in Matrix (4). From this matrix, it can obviously be inferred that, the number of rows satisfying $(\sum_{i=0}^{2^l-1}({\bf{C}}_i)^{2^m}, {\bf{0}}, \ldots, {\bf{0}})$ is $\lfloor \log_2 d \rfloor - 1$. Referring to Equation (2), we can deduce that the number of rows satisfying $({\bf{M}}^{2^m + n}(\sum\prod), {\bf{0}}, \ldots, {\bf{0}})$ is

We can directly calculate the rank of ${\bf{A}}$ as

Accordingly, as $1 \leq \varepsilon \leq 2^l$ takes all possible values, we can demonstrate the identical outcome in each scenario.

Therefore, the dimension of the solution space ${\cal{W}}$ of the equation system ${\bf{A}} \cdot {\boldsymbol{X}} = {\bf{0}}$ is

which implies that

□

Example 2 Let ${\bf{M}}$ be a special block matrix with circulant block of $\mathbb{F}_{2}$, with orders $(2^l, 2^k) = (2^3, 2)$. The block matrices are defined as follows: ${\bf{C}}_0 = {\bf{C}}_1 = {\bf{C}}_6 = \text{circ}(1, 0),$ ${\bf{C}}_2 = {\bf{C}}_4 = \text{circ}(0, 1), {\bf{C}}_3 = {\bf{C}}_7 = \text{circ}(1,1),$ ${\bf{C}}_5 = \text{circ}(0, 0).$ where the non-linear layer comprises $s = 2$ coterminous S-boxes, all of which are aligned within the same block of the corresponding linear matrix. Consequently, it can be demonstrated that, ${\bf{M}}^{2^{k}}={\bf{M}}^{2}={\bf{I}}_{2^{4}}$. Thus, $d=2$, and we can derive the matrix ${\bf{A}}$ as follows:

where $\text{rank}({\bf{A}}) = 4$. The solution space of ${\bf{A}} \cdot {\boldsymbol{X}} = {\bf{0}}$ is denoted by ${\cal{W}}$, where $e(\cdot)$ denotes a vector with a $1$ in the subscripted position and $0$s elsewhere. That is,

$dim({\cal{W}})=12$.

V.   Conclusion and Perspectives

In recent years, there has been a surge of interest in symmetric codes designed for multi-party computation, fully homomorphic encryption, and zero-knowledge proofs. The P-SPN structure has emerged as a promising strategy in cryptographic design. However, current research has not yet provided a systematic investigation into the security aspects of the linear layer within this structure. Furthermore, there is a need for a more comprehensive theoretical framework to underpin the design principles, construction techniques, and parameter selection processes. In this paper, we show that the matrix used in P-SPN schemes has a considerable impact on the security level provided by the cryptosystem. We have made several contributions towards both the theoretical understanding and the practical use of MPC-$\setminus$ FHE-$\setminus$ ZK-friendly symmetric cryptographic algorithms. Firstly, we investigate the properties of a special block matrix with circulant block, which is employed in the linear layer matrix of the P-SPN structure schemes. Furthermore, this study also presents the annihilating polynomial of low degree of this type of special matrix, as well as puts forward the range of determining its minimum polynomial degree. Finally, we provide a lower bound estimate for the dimension of the largest invariant subspace within the P-SPN structure schemes when it incorporates this specific type of matrix. On the one hand, for instances of the P-SPN structure schemes where $s=1$, we are able to precisely determine the dimension of its maximum invariant subspace. On the other hand, for cases with $s>1$, with some certain specific conditions, our research establishes more compact lower bound for the dimensionality of the maximum invariant subspace.

Further exploration is needed for various linear layer matrix types, such as Cauchy and Vandermonde matrices. Analyzing these matrices to understand their transformational relationships is crucial. Such analysis will provide designers with intuitive guidelines for selecting appropriate matrices in P-SPN schemes. Our goal extends beyond circulant matrices to identify conditions that confer resistance to invariant subspace attacks across different matrix types, including those over binary and prime fields. We aim to generalize our findings from binary fields to other fields and to consider the impact of active S-boxes. Additionally, developing more effective techniques for invariant subspace attacks is a priority. We foresee achieving these objectives in the near future.