CBC Mode of MPF Based Shannon Cipher Defined Over a Non-Commuting Platform Group
Commonly modern symmetric encryption schemes (e.g. AES) use rather simple actions repeated many times by defining several rounds to calculate the ciphertext. An idea we previously offered was to trade these multiple repeats for one non-linear operation. Recently we proposed a perfectly secure symmetric encryption scheme based on the matrix power function (MPF). However, the platform group we used was commuting. In this paper, we use a non-commuting group whose cardinality is a power of 2 as a platform for MPF. Due to the convenient cardinality value, our scheme is more suitable for practical implementation. Moreover, due to the non-commuting nature of the platform group, some “natural” constraints on the power matrices arise. We think that this fact complicates the cryptanalysis of our proposal. We demonstrate that the newly defined symmetric cipher possesses are perfectly secure as they were previously done for the commuting platform group. Furthermore, we show that the same secret key can be used multiple times to encrypt several plaintexts without loss of security. Relying on the proven properties we construct the cipher block chaining mode of the initial cipher and show that it can withstand an adaptive chosen plaintext attack.
Symmetric cryptography came a long way from ancient times. One of the fundamental works in this area was presented in Shannon (1949). There the author introduced a concept nowadays known as the Shannon cipher given by a triplet , where is a key generation function, and are encryption and decryption functions, respectively, as defined in Katz and Lindell (2007). Assuming μ is the plaintext to be encrypted, the major requirement of a symmetric encryption scheme is the following:
In the realm of modern symmetric ciphers, the most secure ones possess an essential property of perfect secrecy – a concept initially defined by Shannon himself. One of the most intuitive definitions can be found in various textbooks like Katz and Lindell (2007) or Boneh and Shoup (2020) and states that a symmetric cipher is perfectly secure if the ciphertext c is statistically independent of the encrypted plaintext μ, i.e.
The perfect secrecy property of the one-time pad (OTP) technique was proven by Shannon. To our knowledge, up to our previous works, OTP together with its various modifications remained the only technique with this property. This comes from the fact that perfectly secure ciphers require keys of the same size as the plaintext to be encrypted. Hence, despite achieving this highly desirable property, OTP is mainly viewed as a theoretical concept and is rarely used in practice. Moreover, the OTP falls flat due to its inability to reuse the secret key and becomes an easy prey for active attackers. Interestingly enough, the latter flaw is also the main issue for constructing various encryption modes based on this technique.
Therefore, widely popular symmetric ciphers (e.g. AES) are usually constructed by repeating several rather simple operations multiple times. The more rounds are used, the higher security is achieved. These ciphers can also be adapted for practical implementation via various encryption modes.
Our goal is to show that the perfectly secure cipher can be adaptable for practical implementation. In other words, by using a highly non-linear matrix mapping as opposed to multiple rounds of encryption we can achieve a high-security level while also avoiding the main issue of the OTP.
Recently our research group published a paper (Sakalauskas et al., 2020b), where we introduced a symmetric encryption scheme based on a special case of the so-called MPF mapping. In Sakalauskas and Luksys (2012), authors formally defined MPF as a mapping , where denotes a set of square matrices with entries taken from the specified algebraic structure: a platform semigroup or a finite ring of integers with cardinality determined by the properties of . Let us assume, that matrices and . Then we denote
Our recent research continues the study of MPF applications for symmetric cipher construction but uses a non-commuting platform group. Previously, we published several papers where we proposed new protocols based on MPF defined over non-commuting platform groups (Sakalauskas et al., 2020a; Mihalkovich et al., 2020). In those papers, we proved that the proposed asymmetric cryptographic primitives rely on NP-complete problems (Sakalauskas and Mihalkovich, 2018; Mihalkovich et al., 2020). We used singular matrices to our advantage and showed that non-commuting platform groups and singular matrices contribute to the overall security of the proposed protocols.
In our previous paper (Mihalkovich et al., 2022), we considered the performance of the cipher block chaining (CBC) mode based on MPF mapping. Moreover, we evaluated the computational costs of AES and TDES protocols operating in the CBC mode based on the notion of clock cycles. To achieve a balance between the memory requirements, performance, and statistical properties of our scheme, discussed previously in Levinskas and Mihalkovich (2021), we fixed the main parameters of our cipher at , and . Our results have shown that MPF-based CBC mode outperforms AES-128 by 1.5 times and TDES by roughly 47 times.
Notably, our cipher has another interesting property that was not considered previously in Mihalkovich et al. (2022). Since our cipher is based on matrix operations we can achieve a significant boost of performance speed by implementing parallelization of calculations up to processors during an encryption process of each block. We think that this fact benefits our proposal since other algorithms considered in our previous paper do not have this property.
In this paper, we introduce the CBC mode for our MPF-based cipher and prove its security. We leave the performance evaluation and comparison to other ciphers for our future work. Based on the findings presented in Mihalkovich et al. (2022), we expect to achieve similar results for the to-be-presented CBC mode built on the non-commuting group.
Obviously, singular matrices cannot be used as symmetric keys since the initial message must be restored by applying the same key which is impossible if the inverse matrix does not exist. Hence, to implement the non-commuting platform groups in symmetric encryption we have to define different templates in such a way that power matrices in (3) would be invertible. Furthermore, as opposed to asymmetric encryption presented in Mihalkovich et al. (2020), we also have to make the base matrix W as flexible as possible. In other words, we cannot simply fix a template for the base matrix W since we want to be able to work with any kind of message without having to adapt them to fit a certain requirement. Therefore, we limit ourselves to defining a template for the power matrix Y, thus keeping the restrictions to a minimum.
As mentioned above, we also consider our cipher from the point of view of practical implementation. One obvious drawback of any perfectly secure block cipher is the fact that the encryption key has to be at least as long as the encrypted plaintext. To overcome this obstacle we define the cipher block chaining mode on the basis of our proposal. To prove its resistance against adaptive chosen plaintext attack we define a security game and show that the probability of a win is negligible.
In this paper, we consider a general form of one of the previously explored non-commuting groups, namely the group (Mihalkovich, 2018; Mihalkovich et al., 2020). We define this general form in the next section and present some important facts useful for our goals. These involve the explicit formulas of basic operations and the properties of MPF. In Section 3, we present our main idea – a Shannon cipher based on MPF defined over a non-commuting group. Later in Section 4 we prove the perfect secrecy of our proposal. Moreover, in Section 6 we define the CBC mode of our cipher and consider the security of this scheme in Section 7. As usual, in Section 8 we present our conclusions.
Let us define two generators a and b which do not commute, i.e. . Furthermore, we define the following relations:
We use the notation to better distinguish this group from the plaintext matrix M and the plaintext space . Furthermore, we denote the plaintext bit string by μ and entries of the matrix M by .
Evidently, the identity element can be written as . Furthermore, based on the defined relations and , we can see that all the powers of the generators can be reduced modulo for generator a and modulo 2 for generator b. Using relations , , , it is possible to derive that each element of the group can be represented in the form . Onwards we call this representation a normal form of the element and use it throughout this paper. Obviously, if , we have:
The general representation if is as follows:
The proof of this fact in the special case of was presented in Mihalkovich (2018). Since the idea of the proof remains the same, we omit it to shorten the paper. For this reason, the cardinality of the group is , i.e. the parameter t defines the size of the considered group.
Here we defined the group in its most general form. However, special cases of such groups were previously explored by researchers in group theory. For example, is mentioned in Grundman and Smith (1996), where the authors were discussing the groups of cardinality 16, which are not isomorphic to any other group. A total of seven such groups of size 16 were found. In 2010, authors presented a continuation of their research in Grundman and Smith (2010b). There they considered non-abelian groups of size 32 and one of the mentioned groups was . Similar non-abelian groups were also explored in Michailov (2007) and Grundman and Smith (2010a).
Expanding the idea to greater sizes grants us opportunities to construct symmetric encryption using as a platform group more flexibly. Conveniently, we can now manipulate two parameters, i.e. square matrix size M and platform group size determined by t. Special cases discussed above are obtained when or . As mentioned previously, none of these groups are isomorphic to any other groups of the appropriate cardinality.
Let us now present formulas for the basic operations in . All of the formulas given below are verified using relations , , :
• Multiplication of two elements
• Raising of an element to a power :where notation stands for the integer part of .
• Calculating the inverse of the element :
Explicit proofs of these formulas for a special case of can be found in Mihalkovich (2018). Since the idea of these proofs stays the same, we omit them.
We also introduce an extra notation:
Interestingly enough, by using the group as a platform for MPF we also inflict some “natural” restrictions on the set of symmetric keys. This means that any tuple of matrices, which is outside of the specified domain, cannot be used, since the decryption of the ciphertext results in a scrambled mess. Specifically, if is used as a platform group, then in general we have:
Despite these additional complexities, it is possible to construct a working symmetric encryption protocol. However, we think that these extra complexities may be beneficial for the overall security of our proposal. Similar to the previously published key exchange in Mihalkovich et al. (2020), we define a template for power matrix Y, which can be used to achieve correct decryption. Then, due to inequalities (13), anything which disobeys the chosen template makes the decryption incorrect.
Keeping in mind the essence of symmetric encryption, we have chosen to pick power matrices from a subset of permutation matrices modulo 2, i.e. every square power matrix of size n contains exactly n odd entries whereas the rest of the entries are even. In this special case inequalities, (13) turn to equalities regardless of the choice of W. In the next section, we propose Shannon symmetric encryption protocol with this restriction on the power matrices.
Considering security of our protocol we often refer to the following two mappings and defined below:
Moreover, we define the matrix analogs of these mappings by applying them to each entry of the matrix W of the form (11) entry-wise, i.e. we have:
These mappings will prove helpful to us when showing the validity of the proposed protocol and establishing perfect secrecy property since they allow us to work with the powers of the specific generator.
3The Proposed Shannon Symmetric Encryption Protocol
Before executing the proposed scheme the size of the group , defined by t, the size of square matrices n and the shifting parameter κ, defined below in (18), are published online.
3.1Key Generation Procedure
The key generation procedure consists of the following steps:
1. Generate a binary matrix Δ;
2. Generate matrix with random uniformly selected entries from ;
3. Generate a temporary matrix with random uniformly selected entries from ;
4. Choose a permutation matrix P uniformly from the set of permutation matrices of size ;
5. Define . Calculate using the Gauss-Jordan algorithm.
The result of this procedure is a symmetric key . Note that each time the matrix is generated at Steps 1–3 of the presented process no additional restrictions are applied. Also, since is a permutation matrix, the last step of the presented algorithm is always successful, i.e. is invertible. Hence, all the steps of this procedure are executed exactly once since none of them can fail. We also see that due to the definition of matrix both even and odd entries of are distributed uniformly in the subsets of even and odd elements of respectively.
Let us assume that a message needs to be encrypted using the generated symmetric key . The encryption procedure is as follows:
1. The message is converted to a string of bits of size . If the message is shorter, then extra symbols are added at the end to achieve the appropriate length. Otherwise, the message is too long.
2. The obtained string of bits is transformed to the matrix format by splitting it into separate parts of length t each. The outcome of this step is a matrix which we denote by M.
3. The obtained matrix is split into separate matrices and , where the first bit of each entry of M gets transported to matrix , whereas the rest of bits are written to matrix , hence obtaining powers of generators b and a respectively.
4. The encryption algorithm is as follows:where ∥ denotes the concatenation of two matrices, is the entry-wise shifting by κ bits (e.g. to the right) operator and the addition is performed appropriate modulo, i.e. matrices and Δ are summed modulo 2, and – modulo , and at the last step addition is performed modulo . In all cases, we omit moduli of addition as the appropriate values are usually clear from the context.
5. The matrix C is converted into a string of bits by concatenating its entries in the following way:
Due to the discussed steps, the encryption function is given by:
Upon receiving the ciphertext c the following procedure is performed to decrypt the encrypted message using symmetric key .
1. The ciphertext c is transformed into matrix form C by splitting it into parts of length t.
2. The decryption algorithm is as follows:where is a binary matrix obtained by splitting the first bits of and consists of the leftover bits. Subtraction is to be treated as an inverse of addition in the encryption algorithm (18).
3. Matrices and are concatenated together entry-wise, thus producing matrix .
4. The obtained matrix D undergoes the procedure of transformation to a string of bits by concatenating entries of the matrix in a specific way determined by one of the permutation vectors.
5. Junk symbols are removed, if any. The output of this step is the initial message.
Hence, we can define the decryption function as follows:
3.4Proof of Correctness
Looking at the presented encryption and decryption algorithms we see that due to definitions of these matrices.
Let us consider an intermediate result . Note that entries of matrix T are given by
We now consider the matrix . As claimed in the latter paragraph, the generator b can never be cancelled unless raised to an even power. Hence, as previously, the matrix successfully restores matrix H, i.e. .
Combining these two observations we gain the following result:
The matrix D is now transformed to obtain a string of bits d by concatenating its entries as follows:
Relying on the discussed observations, we conclude that d is the bit string representing the initial message with junk symbols at the end. These can now be dropped to leave us with the initial message.
4Proof of Perfect Secrecy
In this section, we consider the security of the proposed symmetric encryption. Our main goal is to show that our scheme possesses the property of perfect secrecy (2). To achieve this, we start by formulating and proving an important result involving the distribution of the MPF value entries.
Let us assume that the entries of the matrix W are random variables distributed uniformly in and is a permutation matrix modulo 2 with entries uniformly distributed in the subsets of even and odd elements of , respectively. Under these conditions the entries of the MPF exponent value are uniformly distributed in .
Let us apply previously defined mappings and to the matrix W of the form (11). Recall that due to the statement of the lemma, entries of and are uniformly distributed in and , respectively.
Since is a permutation matrix modulo 2, it mixes up the entries of A without changing them. For this reason, the entries of are uniformly distributed in . Hence powers of generator b in matrix E are uniformly distributed in .
We now consider the distribution of the powers of generator a in matrix E. Keeping in mind the properties of permutation matrices, without loss of generality we onwards consider a special case of identity permutation, i.e. we assume that odd entries of the matrix Y are located on its main diagonal. We make a remark regarding the general case of the permutation matrix later in this proof.
Let us focus on the intermediate result and apply mapping to this matrix. We can express every entry as follows:
Note that if Y is a permutation matrix other than identity modulo 2, then the column index changes in the extracted summand. The omitted index in sum (24) changes as well. These are the only two differences in the general case.
Due to construction, all possible values of the sum (24) lie in the subset of even elements of and hence we claim that:
Considering the only odd summand, we can calculate the following probability:
Meshing facts (26) and (27) together we obtain the following result:
This result means that powers of generator a in an intermediate matrix V are distributed uniformly in . Note also that since the term does not play a major part in this calculation, distributions of power of both generators are independent of each other, i.e. powers of generator b do not in any way affect the distribution of powers of generator a.
Similar calculations of probabilities can be performed for the powers of generator a in the matrix . Relying on the uniform distribution of entries of the matrix V and properties of the matrix Y we conclude that powers of generator a in matrix E are distributed uniformly.
Lastly, since the powers of both generators in matrix E are distributed uniformly and are independent of each other, the lemma is valid. □
The probability , where is a fixed matrix defined over , equals:
The proved lemma shows that we have obtained evidence of perfect secrecy property for our protocol. We establish this fact by proving the following theorem:
Let be a random key uniformly chosen from the set of keys and let M be a random matrix chosen from the set of messages in an arbitrary way. Assume also that probability distributions of and M are independent and fully determine the distribution of the matrix C in the set of cipher value matrices together with the encryption algorithm . Under these assumptions, the proposed Shannon cipher in (18) based on MPF is perfectly secure.
Let us consider encryption algorithm (18). Firstly, we turn our attention to matrix and focus on the powers of generator a. Denoting we rewrite each entry of matrix U in the following form:
Due to the statement of the theorem, entries are chosen at random and are uniformly distributed in , whereas entries are random arbitrary distributed values in . For any fixed matrix with entries , we have
We now calculate the conditional probabilities of the entries of matrix U:
Another important property of matrix U is the independence of its entries. Since all , , are independent, for all we have:
Relying on the obtained equalities (31), (32) and (33) we claim that:
Similarly, matrix Δ is chosen uniformly from . For this reason, analogous observation holds for the matrix sum , with probability . However, both sums in the expression of are independent of each other and hence we have:
Let us denote the set of all possible values of the key matrix by . Note that each matrix from this set reduced modulo 2 is a permutation matrix and hence the cardinality of this set is .
We now consider the second step of the encryption algorithm (18), i.e. matrix . Due to Lemma 1, entries of MPF value are uniformly distributed in . All that is left is to explore the conditional probabilities of its entries which are expressed as follows:
We limit ourselves to the matrix form of these calculations since the expression of probability for a single entry of is much more complicated due to restriction on matrix Y.
Since expression (37) is a numerator of conditional probability (36), we obtain the following result:
Comparing this result to the expression (29), we can see that the distributions match and hence draw a conclusion that entries of the matrix are independent of plaintext matrix M.
The proof for the last step of the encryption algorithm is analogous to the proof for the first step since the matrix consists of uniformly distributed in entries whereas the shifting function does not have an impact on the distribution of the entries of the other matrix summand. □
Due to the proven result, we can see that no information about the plaintext is leaked by the encryption algorithm. This is the essential property any good symmetric cipher should possess.
5Comparison With One-Time Pad
A classic example of a perfectly secure cipher is the one-time pad scheme proposed by G. Vernam in the early XX century. It uses a key k the size of the message and a simple XOR operation ⊕ to obtain a ciphertext . Decryption works similarly, i.e. .
However, despite being an ideal cipher, its practical implementation is highly limited. Firstly, the size of the secret key is a big problem, e.g. encrypting a 1GB file requires a key of the same size. Obviously, no user wants to waste his memory space storing such a key. So far in this sense, our cipher seems even worse since the size of the key is about twice the size of the message. Moreover, regardless of any actions we make, the size of the secret key has to be at least the size of the message for our cipher to remain perfectly secure. This fact is called the Shannon theorem.
The logical question now is if we can gain any benefits by using such a key to encrypt a message. To answer this question we consider another flaw in the one-time pad scheme. It is widely known that reusing the same key k to encrypt messages , results in a catastrophe, i.e. any adversary possessing and is able to restore given that the plaintext is known to him since he can perform the following calculation:
This fact can be viewed as gaining an advantage of 1 in winning the following Attack Game aimed at the recovery of data encrypted by a fixed key k:
For a given symmetric cipher defined over define the following attack game:
1. The challenger picks at random a secret key ;
2. The adversary sends a sequence of queries of equal size to the challenger;
3. The challenger calculates the ciphertexts , where , and sends them to the adversary;
4. The adversary outputs a pair , where and . He wins if .
We let the adversary be adaptive, i.e. he can choose his queries based on the ciphertexts obtained from the challenger.
Obviously, for the case of a one-time pad scheme, an adversary requires a single query, i.e. . In fact, the secret key k is trivially recoverable in this case.
Let us denote the event of winning the Attack Game 1 by W.
The advantage of the adversary in winning the Attack Game 1 is given by
Note that due to expression (39) the adversary may not necessarily obtain the secret key k to win the game as long as he can output a working pair . Hence, he has two alternatives to winning: determining the secret key or using the obtained replies to gain a way to output a working pair. The advantage shows how much better than randomly guessing the key can the adversary do.
The symmetric cipher is secure under key reuse if for any poly-bounded number of queries Q the advantage is negligible.
As we have seen one-time pad is not secure under key reuse. We prove the following proposition:
The Shannon block cipher defined by the encryption algorithm (18) and decryption algorithm (20) is secure under key reuse.
Let us consider both alternatives for winning the Attack Game 1.
Firstly, we consider determining the key strategy. Assume that the adversary received ciphertext matrices matching the known message matrices . Here we use the upper indexes for C’s to distinguish challenger responses from intermediate results of the encryption algorithm (18). Hence, an adversary can analyse the following system of equations:
Hence, even knowing the parameter k the adversary cannot use this information to formulate an advantageous system of equations to extract the secret key. As such we conclude that the key determination strategy is not applicable.
Hence we consider the other option, i.e. using the responses to find a way of outputting a working pair. In this scenario, we assume that an adversary obtained matrices . Moreover, we can also assume that the correspondent message matrices are linearly independent and hence form a basis of the linear space . Then he can express each subsequent query , as a linear combination of . Also, since on the same basis can also be used to express the ciphertext matrices , as well as the corresponding response as a linear combination of . Hence, the adversary can get the following results:
For this reason a relation between coefficients and can be viewed as a random permutation mapping , where . Define an adversary who plays the role of challenger to and plays the Attack Game 4.1 (see Boneh and Shoup, 2020) with his challenger. Recall that Attack Game 4.1 is aimed at distinguishing an encryption function from a random permutation. To be self-contained, let us revise this game:
For the block cipher we define two experiments. Then for a value we have an Experiment β:
1. The challenger selects a function as follows:
2. The adversary submits a sequence of queries, i.e. plaintexts in their matrix form , where ;
3. For the i-th query the challenger computes and sends all the ’s to an adversary;
4. outputs .
Whenever receives a query from , he sends it to his challenger and afterward forwards the obtained response back to . Steps 1 and 3 of the Attack Game 1 are performed by ’s challenger. Due to the perfect secrecy of our cipher, ’s advantage in winning the Attack Game 2 on his own is negligible, i.e. he cannot tell apart the encryption function from a random permutation. On the other hand, if can output a working pair with a non-negligible probability p, then can send M as his -st query to his own challenger and achieve an advantage of in Attack Game 2 if . However, to achieve an advantage p, the adversary has to distinguish a specific mapping among other possible permutations with that particular probability. This would imply that not all choices are equally possible and hence it contradicts the perfect secrecy of our cipher.
As such, we see that the only chance the adversary has is to randomly guess a pair and hope for it to work. However, due to the design of Attack Game 1, there are leftover working pairs out of possible pairs. Furthermore, due to restrictions applied to the key matrices , the size of the keyspace is
Then we can evaluate ’s advantage in Attack Game 1 as follows
This result is a significant advantage of our cipher over the one-time pad technique. Specifically, as opposed to a one-time pad we do not need to use a different key whenever we use our scheme to encrypt a message. Furthermore, this beneficial property of our cipher greatly outshines the drawback of using a longer key, since it unlocks the implementation of different types of modes, e.g. CBC. This ability follows from the fact that we have to use the same key to encrypt a large number of blocks. As the one-time pad is insecure under key reuse, no encryption mode can ever be constructed on its basis.
6CBC Mode of the Proposed Block Cipher
The general idea of the CBC mode is to unite encrypted chunks of the message into a chain. To withstand the chosen plaintext attack, our cipher has to be probabilistic. The commonly used solution is to use a randomly generated initialization vector . In our case, we interpret it as a matrix . We use this matrix together with the secret key to create a chain in the following way:
We see that the ciphertext is longer than the plaintext which is a common practice when implementing a CBC mode. As the number of blocks gets larger, the CBC mode of our cipher becomes more efficient as compared to the one-time pad technique. Furthermore, the proof of a perfect secrecy property still holds for a single block . However, we emphasize that when referring to the perfect secrecy property we only consider the initial block cipher. Obviously, as the number of blocks increases, the size of the message surpasses the size of the key and hence the CBC mode is not perfectly secure, which is consistent with the Shannon theorem.
7Resistance Against Chosen Plaintext Attack
In this section, we consider the security of our scheme. More precisely, we turn our attention to the chosen plaintext attack which is aimed at the newly defined CBC mode. Any efficient adversary capable of successfully executing this attack can distinguish a plaintext corresponding to the received ciphertext based on the obtained responses to his queries. Moreover, the adversary is adaptable, which means that he can base his queries on the received information. The formal description of this attack is presented here as the following game:
Attack Game 3.
For a given symmetric cipher defined over define the CBC mode using encryption and decryption functions (44) and (45) respectively. Consider the following attack game:
1. The challenger selects a random key ;
2. The adversary submits a sequence of queries i.e. plaintext pairs of equal lengths, where ;
3. For the i-th query the challenger computes , where is the Experiment indicator, and sends all the ’s to an adversary;
4. outputs .
Note that the challenger of the Attack Game 3 always encrypts either the first or second messages of each query. The essence of the presented Attack Game is that an adversary can win it with a non-negligible probability if he can somehow relate the received ciphertext to the correct message in the pair .
Let us make two important observations. Firstly, the message space of the CBC mode is super-poly. In fact, its size is . Secondly, the number of blocks l is poly-bounded and determined by the length of the plaintext as follows:
For these reasons we rely on a strategy presented in (Boneh and Shoup, 2020) to prove the following claim:
Consider probabilistic cipher . For all efficient adversaries their advantage in Attack Game 3 is expressed as follows:
Before presenting the proof for this theorem, we emphasize that the main adversary in the Attack Game 3 is . However, he also communicates with adversary , who attacks the block cipher ε as in Attack Game 2 and forwards ’s queries to his challenger.
Note that before encrypting the first block of the plaintext a challenger randomly selects an initialization vector and hence the intermediate block consists of random uniformly distributed entries. Hence, by the construction of our scheme the advantage of adversary to win a bit-guessing version (i.e. an adversary wins the game if ) of the Attack Game 3 is given by:
To improve his chances collaborates with another adversary whose purpose is to analyse the original block cipher by playing the Attack Game 2. Adversary wins if he can distinguish between the encrypted block and a random permutation. This is where the perfect secrecy property of our cipher plays a significant role. Due to this property, the entries of the ciphertext matrix are statistically independent of the entries of the original message block . Hence, this behaviour is indistinguishable from a random permutation and thus the adversary cannot gain any significant advantage.
Moreover, since the initialization matrix is selected randomly from a significantly large space of possible values (in fact, the size of this space is super-poly), the responses to multiple queries of the same plaintext are almost always distinct. This claim is based on two facts: choosing the same initialization matrix is practically an impossible random event and the encryption function is a one-to-one mapping. As such, can be estimated in the following way:
The strategy now is to introduce Games 2 and 3 as in the proof of Theorem 5.4 of (Boneh and Shoup, 2020) and evaluate the appropriate results. These games explore the changes influenced by switching from a permutation to a one-to-one mapping and then to many-to-one mapping. These changes are unnoticeable to the adversary under the assumptions that ε is a secure block cipher and the message space is super-poly. Both these assumptions are satisfied for our scheme. We limit ourselves to the essence of these games and leave their detailed description outside of this paper since they are technical and universal for all encryption algorithms. The changes are minor and involve the algebraic structures and actions used in the initial block cipher. In our case – matrix space and entry-wise addition modulo . □
Note that we used the same Attack Game 2 in this proof as in Section 5. This comes from the fact that a good block cipher should be indistinguishable from a random permutation and unpredictable. As it was shown, Attack Game 2 plays an important role in establishing both of these properties.
Let us end this section by presenting an example of computing the . Inspired by the fact that AES encrypts a 128-bit block, we pick the non-commuting group and consider matrices, i.e. public parameters , and the size of the block is bits. Furthermore, we limit the message size by blocks and hence can encrypt bits (64 GB) of information. Then we get the following result:
8Discussion and Conclusions
In this paper, we proposed a new Shannon cipher based on a special case of MPF. Instead of several rounds, our symmetric encryption scheme uses only one round. However, the operations we use are more complex. Moreover, we use a non-commuting platform group in our construction which contributes to the overall security of our cipher.
In our scheme we can manipulate two parameters: the size of square matrices n and the size of the platform group determined by t. This feature makes our scheme flexible and easy to adapt to messages of any length. However, more investigations are needed to make reasonable recommendations for the values of parameters n and t depending on the message length. This is one of the possibilities for future work in this research.
We have proven that our cipher has the property of perfect secrecy and hence the encryption algorithm itself does not leak any information about the plaintext. This is one of the essential properties of a good symmetric encryption scheme.
The perfect secrecy of our block cipher also favourably distinguishes it from a widely used AES scheme, whose perfect secrecy property for a single block to our knowledge has not been established. We also think that a significant boost in the performance of our cipher is because matrix operations can be parallelized and hence the encryption of a single block can be executed on multiple processors. Relying on our findings presented in Mihalkovich et al. (2022), we expect that the non-commuting platform group used in our paper also contributes to the performance of our scheme. Since all powers of the elements of are reduced modulo , the reduction process is much simpler than reducing modulo a prime. For this reason, we think that our proposal can produce better results than those presented in Mihalkovich et al. (2022). However, verifying this claim requires additional research thus far.
Relying on the fact that our cipher is secure under key reuse, we defined a CBC mode for our cipher. As the message becomes longer, its length surpasses the size of the secret key, and hence due to the Shannon theorem, the perfect secrecy property is lost. However, since perfect secrecy also implies semantic security of a block cipher, we claim that the CBC mode can be considered safe in this weaker sense, i.e. an efficient adversary cannot gain a significant advantage in linking a ciphertext c to the correct plaintext.
Moreover, in Section 7 we have shown that the probabilistic cipher can resist an adaptive chosen plaintext attack, i.e. the previously obtained responses to the sent queries in no way help the efficient adversary to gain a significant advantage in Attack Game 3.
Boneh, D., Shoup, V. (2020). A Graduate Course in Applied Cryptography.
Grundman, H.G., Smith, T.L. ((1996) ). Automatic realizability of Galois groups of order 16. In: Proceedings of the American Mathematical Society, AMS ’96. AMS, Rhode Island, USA, pp. 2631–2640.
Grundman, H.G., Smith, T.L. ((2010) a). Galois realizability of groups of order 64. Central European Journal of Mathematics, 8(5): , 846–854.
Grundman, H.G., Smith, T.L. ((2010) b). Realizability and automatic realizability of Galois groups of order 32. Central European Journal of Mathematics, 8: (2), 244–260.
Katz, J., Lindell, Y. ((2007) ). Introduction to Modern Cryptography. CRC Press, New York.
Levinskas, M., Mihalkovich, A. ((2021) ). Avalanche effect and bit independence criterion of perfectly secure Shannon cipher based on matrix power. Mathematical Models in Engineering, 7: (3), 50–53. https://doi.org/10.21595/mme.2021.22234.
Michailov, I. ((2007) ). Groups of order 32 as Galois groups. Serdica Mathematical Journal, 33: (1), 1–34.
Mihalkovich, A. ((2018) ). On the associativity property of MPF over M16. Lietuvos matematikos rinkinys: Lietuvos matematiku draugijos darbai, Serija A, 59: , 7–12.
Mihalkovich, A., Levinskas, M., Makauskas, P. ((2022) ). MPF based symmetric cipher performance comparison to AES and TDES. Mathematical Models in Engineering, 8: (2), 15–25. https://doi.org/10.21595/mme.2022.22517.
Mihalkovich, A., Sakalauskas, E., Luksys, K. ((2020) ). Key exchange protocol defined over a non-commuting group based on an NP-complete decisional problem. Symmetry, 12: , 1389. https://doi.org/10.3390/sym12091389.
Sakalauskas, E., Luksys, K. ((2012) ). Matrix power function and its application to block cipher s-box construction. International Journal of Innovative Computing, Information and Control, 8: (4), 2655–2664.
Sakalauskas, E., Mihalkovich, A. ((2018) ). MPF problem over modified medial semigroup is NP-complete. Symmetry, 10: (11), 571. https://doi.org/10.3390/sym10110571.
Sakalauskas, E., Mihalkovich, A., Uselis, A. ((2020) a). Security analysis of KAP based on enhanced MPF. IET Information Security, 14: (4), 410–418.
Sakalauskas, E., Dindiene, L., Kilciauskas, A., Luksys, K. ((2020) b). Perfectly secure Shannon Cipher construction based on the matrix power function. Symmetry, 12: , 860. https://doi.org/10.3390/sym12050860.
Shannon, C.E. ((1949) ). Communication theory of secrecy systems. The Bell System Technical Journal, 28: (4), 656–715.
Sylow, M.L. ((1872) ). Théorèmes sur les groupes de substitutions. Mathematische Annalen, 5: , 584–594. https://doi.org/10.1007/BF01442913.