Avalanche effect and bit independence criterion of perfectly secure Shannon cipher based on matrix power

1.1. Avalanche effect and BIC

Cryptography security analysis methods such as avalanche effect and BIC allow us to evaluate block cipher secrecy by computing elements confusion after changing just one bit [2], determine elements confusion and dependance from other elements [3, 4]. The values of these criteria are commonly calculated by considering the avalanche vector $A^{e_i}$, which describes ciphertext bits change after flipping one bit in the plaintext:

where vector has all entries equal to 0 except for the $i$-th one which is equal to 1, entry $a_1^{e_i}\in \left\{\mathrm{0,1}\right\}$ and function $Enc\left(k,\mu \right)$ is encryption function mapping shared key $k$and plaintext $\mu$ to the ciphertext generally denoted by $c$.

Using expression defined in Eq. (1), we compute the $i$-th bit avalanche $k_{AVAL}\left(i\right)$ effect as follows:

where $k_{AVAL}\left(i\right)$ indicates the number of bits changes after flipping $i$-th bit. The desired value of the avalanche effect is 0.5 for all the bits, meaning that it is infeasible to distinguish which bit changes occur after flipping a random bit of the original message.

The bit independence of the two entries is being calculated by the maximal absolute correlation coefficient between avalanche vector $j$ and $k$ components. According to [2], BIC can be calculated by the formula:

Furthermore, relying on Eq. (3) we can define the overall BIC for the whole ciphertext block $Enc\left(k,m\right)$ as the maximal correlation by checking all available pairs:

Ideally, the value of BIC should be close to 0 hence ensuring that all the bit changes occur statistically independently.

1.2. Perfectly secure Shannon cipher based on matrix power function

The matrix power function (MPF) was introduced in [5], as the following mapping acting on the Cartesian product of the space of square matrices of order $m$ with itself:

The general notation for this mapping is as follows:

where $W,E\in Ma{t}_m\left(\mathbb{S}\right)$ are matrices with entries from semigroup $\mathbb{S}$ and $X,Y\in Ma{t}_m\left(\mathbb{R}\right)$ are matrices with entries from a finite ring of integers $\mathbb{R}$. This mapping allows us to raise the base matrix $W$ to the so-called power matrices $X$ and $Y$.

E. Sakalauskas with co-authors used the MPF in 2020 to propose a perfectly secure Shannon cipher defined over ${\mathbb{Z}}_3$ [1]. This cipher uses a plaintext matrix $M$, private keys $X$ and $Y$ along with a function $f:{\mathbb{Z}}_3\mapsto {\mathbb{G}}_3$, which maps elements of ${\mathbb{Z}}_3$ to elements of the multiplicative Sylow group ${\mathbb{G}}_3=\{\mathrm{1,2},4\}$, which is a subgroup of ${\mathbb{Z}}_7^{*}$. Note, that actions in ${\mathbb{G}}_3$ are performed modulo 7. A key feature of this mapping is that it does not carry over the addition in ${\mathbb{Z}}_3$ to the multiplication in ${\mathbb{G}}_3$ and hence is not an isomorphism. The encryption function can be expressed in a following way:

where $F:Ma{t}_m\left({\mathbb{Z}}_3\right)\mapsto Ma{t}_m\left({\mathbb{G}}_3\right)$ is an entry-wise matrix analogue of the mapping f and $F^{-1}$ is its inverse. Note that since F is not an isomorphism no cancelations in Eq. (6) are possible. We also use $⨀$ to denote Hadamard product of two matrices.

It is worthy noting that the shared key $\left\{X,Y\right\}$ consists of $2m^2$ entries and hence is at least twice the length of the original plaintext given that extra bits may be added at the end message to make it appropriate length. However, the plaintext and ciphertext are roughly the same size.

To decipher the ciphertext, we denote by $T^H$ the inverse of matrix $T$ in Hadamard sense i.e., a matrix satisfying the following relation:

where every entry in the matrix is the unit of the group ${\mathbb{G}}_3$.

Upon receiving the ciphertext its decryption is performed in the reverse order and can be summarized by the following expression:

Perfect secrecy of the presented block cipher and the statistical independency of the ciphertext $C$ from the plaintext $M$ is proven in [1].

In this paper we investigate the avalanche effect and BIC for the presented block cipher in a more general form i.e., we expand the cardinalities of the algebraic structures considered. In other words, we consider the Sylow group ${\mathbb{G}}_q$ of the multiplicative group ${\mathbb{Z}}_p^{*}$ and an additive group ${\mathbb{Z}}_q$. Hence in Eq. (4) we have $W,E\in Ma{t}_m\left({\mathbb{G}}_q\right)$ and $X,Y\in Mat\left({\mathbb{Z}}_q\right)$. Actions in ${\mathbb{G}}_q$ are performed modulo a prime $p=2q+1$.