Cryptanalysis of hyperchaotic S-box generation and image encryption

1.   Introduction and preliminaries

Similar to congruences on a semigroup, strongly regular relations on a semihypergroup (see ^[1]) play an important role in studying the algebraic structure of a semihypergroup. For example, M. De Salvo, D. Fasino, D. Freni and G. Lo Faro characterize and enumerate certain hypergroup classes based on the partition induced by the smallest strongly regular relation in ^[2,3].

A hypergroupoid $(S, \circ)$ is a nonempty set $S$ together with a hyperoperation, that is a mapping $\circ: S\times S\rightarrow \mathcal{P}^{\ast}(S)$, where $\mathcal{P}^{\ast}(S)$ denotes the family of all nonempty subsets of $S$. If $x\in S$ and $A, B$ are nonempty subsets of $S$, then we denote

A hypergroupoid $(S, \circ)$ is called a semihypergroup if $\circ$ is associative, that is

for every $x, y, z\in S$. If a semihypergroup $S$ contains an element $1$ with the property that

then we say that $1$ is an absolute identity. Clearly, a semihypergroup has at most an absolute identity. If a semihypergroup $S$ has no absolute identity, then we adjoin an extra element $1$ to $S$ and define

Thus $S\cup\{1\}$ becomes a semihypergroup containing an absolute identity. We now define

Let $(S, \circ)$ be a semihypergroup and $\rho$ a binary relation on $S$. If $A$ and $B$ are nonempty subsets of $S$, then we set

and

A binary relation $\rho$ on $S$ is called left strongly compatible if

and right strongly compatible if

A binary relation on $S$ is called strongly compatible if it is both left and right strongly compatible. An equivalence relation on $S$ is called strongly regular if it is strongly compatible.

Let $(S, \circ)$ be a semihypergroup and $\rho$ a strongly regular relation on $S$. We denote by $(a)_{\rho}$ the equivalence $\rho$-class containing $a$. It is well known from ^[1] that the quotient $S/\rho$ is a semigroup with respect to the operation $(x)_{\rho}\star(y)_{\rho} = (z)_{\rho}$ for every $z\in x\circ y$. Let $\rho$ be any relation on a nonempty set $S$. Then $\rho^{\infty}$ denotes the transitive closure of $\rho$, that is, $\rho^{\infty} = \cup_{m\geq 1}\rho^{m}$. The least strongly regular relation (fundamental relation) ^[4] $\beta^{\ast} = \beta^{\infty}$ is the transitive closure of the relation $\beta = \cup_{n\geq 1}\beta_{n}$, where

is the diagonal relation on $S$, and for every integer $n > 1, \beta_{n}$ is defined as follows

A strongly regular relation $\rho$ on $S$ is called commutative if the quotient $S/\rho$ is a commutative semigroup. The least commutative relation ^[5] $\gamma^{\ast} = \gamma^{\infty}$ is the transitive closure of the relation $\gamma = \cup_{n\geq 1}\gamma_{n}$, where

is the diagonal relation on $S$, and for every integer $n > 1, \gamma_{n}$ is defined as follows

By constructing special strongly regular relations on a semihypergroup, we can obtain some special quotient structures (see ^{[6,7,8,9,10,11]}). In this regards, we give a unified method for constructing special strongly regular relations. A strongly regular relation $\rho$ on $S$ is called a band relation if the quotient $S/\rho$ is a band, and a semilattice relation if the quotient $S/\rho$ is a semilattice, that is $\rho$ is both a band relation and commutative. In this paper, we introduce three preliminary relations on a semihypergroup. Using these relations, we construct the commutative relation, the band relation and the semilattice relation generated by a given binary relation. As consequences, the least commutative relation, the least band relation and the least semilattice relation on $S$ are given. Moreover, we show that the set of all commutative relations, the set of all band relations and the set of all semilattice relations on $S$ are complete lattices.

2.   Commutative relations, band relations and semilattice relations

Let $(S, \circ)$ be a semihypergroup and $\rho$ a binary relation on $S$. We denote by $\rho^{rs}$ the relation $\rho\cup\rho^{-1}\cup 1_{S}$ on $S$. It is obvious that $\rho^{rs}$ is the smallest reflexive and symmetric relation containing $\rho$. Let $\{\rho_{i}\mid i\in I\}$ be the family of all strongly regular relations on $S$ containing $\rho$. Then the relation $\bigcap\limits_{i\in I}\rho_{i}$ is clearly the least strongly regular relation on $S$ containing $\rho$, which is called the strongly regular relation on $S$ generated by $\rho$. Similarly, the least commutative (resp. band, semilattice) relation on $S$ containing $\rho$, denoted by $\rho^{c}$ (resp. $\rho^{b}$, $\rho^{s}$), is called the commutative (resp. band, semilattice) relation on $S$ generated by $\rho$.

Definition 2.1. Let $\rho$ be a binary relation on a semihypergroup $(S, \circ)$. We define the relation $\rho^{sc}$ on $S$ as

It is easy to see that $\rho^{sc}$ has the following property.

Lemma 2.1. Let $\rho$ and $\sigma$ be two relations on a semihypergroup $(S, \circ)$. Then

($i$) $\rho\subseteq\sigma\Rightarrow \rho^{sc}\subseteq\sigma^{sc}$;

($ii$) $(\rho^{sc})^{-1} = (\rho^{-1})^{sc}$;

($iii$) $(\rho\cup\sigma)^{sc} = \rho^{sc}\cup\sigma^{sc}$.

Lemma 2.2. Let $\rho$ be a binary relation on a semihypergroup $(S, \circ)$. Then $\rho^{sc}$ is the least strongly compatible relation on $S$ containing $\rho$.

Proof. (1) If $(u, v)\in \rho$, then $(u, v)\in (1\circ u\circ 1)\times(1\circ v\circ 1)$. Thus $(u, v)\in \rho^{sc}$ and so $\rho\subseteq\rho^{sc}$.

(2) Let $(u, v)\in \rho$ and $w\in S$. Then

for some $x_{1}, x_{2}, \cdots, x_{m}, y_{1}, y_{2}, \cdots, y_{n}\in S^{1}$ and some $(a, b)\in\rho$. Hence

and so

Therefore, $\rho^{sc}$ is left strongly compatible. In the same way, we can obtain that $\rho^{sc}$ is right strongly compatible.

(3) Suppose that $\sigma$ is a strongly compatible relation on $S$ containing $\rho$. Then for all $x_{1}, x_{2}, \cdots, x_{m}, y_{1}, y_{2}, \cdots, y_{n}\in S^{1}$ and all $(a, b)\in\rho$, we have

Hence, $\rho^{sc}\subseteq\sigma$. □

Lemma 2.3. Let $\rho$ be a binary relation on a semihypergroup $(S, \circ)$. Then $(\rho^{sc})^{\infty}$ is a strongly compatible relation on $S$.

Proof. Let $(u, v)\in(\rho^{sc})^{\infty}$. Then $(u, v)\in(\rho^{sc})^{n}$ for some positive integer $n$. Thus there exist $a_{1}, a_{2}, \cdots, a_{n-1}\in S$ such that

It follows from Lemma 2.2 that

for all $w\in S$. Hence

and so

Similarly,

Therefore, $(\rho^{sc})^{\infty}$ is strongly compatible. □

Denote

Theorem 2.1. Let $\rho$ be a binary relation on a semihypergroup $(S, \circ)$. Then

($i$) $\rho^{c} = (((\rho\cup\mathfrak{C})^{rs})^{sc})^{\infty}$;

($ii$) $\rho^{b} = (((\rho\cup\mathfrak{B})^{rs})^{sc})^{\infty}$;

($iii$) $\rho^{s} = (((\rho\cup\mathfrak{S})^{rs})^{sc})^{\infty}$.

Proof. ($i$) Denote $\delta = (((\rho\cup\mathfrak{C})^{rs})^{sc})^{\infty}$. It is easy to see that $\delta$ is an equivalence relation containing $\rho$ and $\mathfrak{C}$ on $S$. Moreover, by Lemma 2.2 and 2.3, we have $\delta$ is strongly compatible. Therefore, $\delta$ is a strongly regular relation on $S$. Thus $(S/\delta, \star)$ is a semigroup, where the operation $\star$ is defined as

for every $a, b\in S$. Next, we show that $S/\delta$ is commutative. In fact, for any $x\in a\circ b$ and $y\in b\circ a$, we have $x\mathfrak{C}y$ and so $x\delta y$. Hence,

Suppose that $\sigma$ is a commutative relation on $S$ containing $\rho$. It is obvious that $\mathfrak{C}\subseteq\sigma$. Then

Hence

from Lemma 2.1 and 2.2. Therefore,

Thus, we obtain our conclusion.

The conclusions ($ii$) and ($iii$) can be obtained by applying the similar approach in the proof of ($i$). □

From Theorem 2.1, we can obtain the least commutative relation which is also given in another form $\gamma^{\ast}$ (see ^[5]), the least band relation and the least semilattice relation on a semihypergroup.

Corollary 2.1. Let $S$ be a semihypergroup. Then $((\mathfrak{C}^{rs})^{sc})^{\infty}$ (resp. $((\mathfrak{B}^{rs})^{sc})^{\infty}$, $((\mathfrak{S}^{rs})^{sc})^{\infty}$) is the least commutative (resp. band, semilattice) relation on $S$.

3.   The lattices of commutative relations, band relations and semilattice relations

Let $S$ be a semihypergroup. We denote by $C(S), B(S)$ and $SL(S)$ the set of all commutative relations, the set of all band relations and the set of all semilattice relations on $S$ respectively. It is obvious that $C(S), B(S)$ and $SL(S)$ are partially ordered sets under the set inclusion. In the following, we show that $(C(S), \subseteq, \cap, \vee_c)$, $(B(S), \subseteq, \cap, \vee_b)$ and $(SL(S), \subseteq, \cap, \vee_s)$ are complete lattices where $\vee_c, \vee_b$ and $\vee_s$ are defined as

A meet-semilattice ($\cap$-semilattice) $L$ is said to be $\cap$-complete if every subset of $L$ has a minimum element. Dually, a join-semilattice ($\cup$-semilattice) $L$ is said to be $\cup$-complete if every subset of $L$ has a maximum element. A lattice is said to be complete if it is both $\cap$-complete and $\cup$-complete.

Lemma 3.1. (Theorem 2.11 ^[12]) A $\cap$-complete $\cap$-semilattice is a complete lattice if and only if it has a maximum element.

Theorem 3.1. Let $(S, \circ)$ be a semihypergroup. Then $(C(S), \subseteq, \cap, \vee_c)$, $(B(S), \subseteq, \cap, \vee_b)$ and $(SL(S), \subseteq, \cap, \vee_s)$ are complete lattices.

Proof. We just prove that $(C(S), \subseteq, \cap, \vee_c)$ is a complete lattice. Using the similar approach, we can obtain that $(B(S), \subseteq, \cap, \vee_b)$ and $(SL(S), \subseteq, \cap, \vee_s)$ are also complete lattices.

It is obvious that the universal relation $S\times S$ is the maximum element of $C(S)$. From Lemma 3.1, we need only show that $C(S)$ is a $\cap$-complete $\cap$-semilattice. Let $\{\rho_{\alpha}\mid \alpha\in\Gamma\}$ be a family of commutative relations on $S$. Then $\bigcap\limits_{\alpha\in\Gamma}\rho_{\alpha}$ is a commutative relation on $S$. Indeed, we know from ^[13] that $\bigcap\limits_{\alpha\in\Gamma}\rho_{\alpha}$ is a strongly regular relation on $S$. Thus $(S/\bigcap\limits_{\alpha\in\Gamma}\rho_{\alpha}, \star)$ is a semigroup, where the operation $\star$ is defined as

for every $a, b\in S$. For any $x\in a\circ b$ and $y\in b\circ a$, we have $x\mathfrak{C}y$. It follows from $\mathfrak{C}\subseteq\bigcap\limits_{\alpha\in\Gamma}\rho_{\alpha}$ that $x\bigcap\limits_{\alpha\in\Gamma}\rho_{\alpha}y$. Hence, $(S/\bigcap\limits_{\alpha\in\Gamma}\rho_{\alpha}, \star)$ is a commutative semigroup and so $\bigcap\limits_{\alpha\in\Gamma}\rho_{\alpha}\in C(S)$. □

Remark 3.1. Let $(S, \circ)$ be a semihypergroup. We know from Theorem 3.1 that $C(S), B(S)$ and $SL(S)$ are all complete lattices. Moreover, it is easy to see that $SL(S) = C(S)\cap B(S)$ as lattices.

At the end of this paper, we illustrate our main results by the following example.

Example 3.1. Let $S = \{a, b, c, d\}$ with the operation $\circ$ below:

Then $(S, \circ)$ is a semihypergroup. It is obvious that $\mathfrak{S} = \{(a, a), (a, d), (b, b), (c, c), (d, a), (d, d)\}$. Define two relations $\rho_{1} = \{(a, b)\}$ and $\rho_{2} = \{(a, c)\}$. Then we have

Moreover, it is not difficult to verify that $SL(S) = \{\mathfrak{S}, \rho_{1}^{s}, \rho_{2}^{s}, S\times S\}$. Since $\mathfrak{S} = \rho_{1}^{s}\cap\rho_{2}^{s}$ and $\rho_{1}^{s}\vee_s\rho_{2}^{s} = S\times S$, we have $(SL(S), \subseteq, \cap, \vee_s)$ is a complete lattice.

4.   Conclusions

Let $\rho$ be a binary relation on a semihypergroup $S$. In this paper, we characterize the commutative relation $\rho^{c}$ (resp. band relation $\rho^{b}$, semilattice relation $\rho^{s}$) generated by $\rho$ on $S$. Finally, we show that the set of all commutative relations $C(S)$ (resp. band relations $B(S)$, semilattice relations $SL(S)$) on $S$ is a complete lattice.

Acknowledgments

The author thanks the editor and referees whose comments led to significant improvements to this paper. This work is supported by the National Natural Science Foundation of China (No. 11701504), the Guangdong Basic and Applied Basic Research Foundation (No. 2022A1515011081), the Characteristic Innovation Project of Department of Education of Guangdong Province (No. 2020KTSCX159), the Innovative Research Team Project of Zhaoqing University and the Scientific Research Ability Enhancement Program for Excellent Young Teachers of Zhaoqing University.

Conflict of Interest

The author declares no conflict of interest.