1 INTRODUCTION

In the post-quantum era, the McEliece cryptosystems [1] are considered as possible alternatives to asymmetric cryptosystems whose resistance is currently based on factorization complexity of large integers or discrete logarithmization in a finite group [2]. A prerequisite for constructing the McEliece cryptosystems based on linear codes is the existence of effective (polynomial) decoding algorithms for these codes. Meanwhile, this condition is not sufficient. Although the Reed–Solomon and Reed–Maller codes possess fast decoding algorithms [3], the related McEliece cryptosystems are shown to give way to structural attacks [4, 5]. As found for the McEliece cryptosystems, the more the code is structurally similar to a random code, the more difficult is the analysis of the corresponding McEliece cryptosystem. Among the feasible ways to construct a robust McEeliece cryptosystem, there is the search or the construction of a code with an available effective decoder and a random-like structure.

It is shown in work [6] that for a base code \(C\)disposing the effective majority decoder, one can also construct a decoder for the induced code \(\mathbb{F}_{q}^{l} \otimes C\), \(l \in \mathbb{N}\). In connection with this, the McEliece cryptosystem was developed on the base of an induced code \(\mathbb{F}_{q}^{l} \otimes C\) [7]. If a McEliece cryptosystem based on the code \(C\) is unstable to attacks on keys, one can carefully select the induced code parameters so that the attack on the key of a related cryptosystem based on the induced code \(\mathbb{F}_{q}^{l} \otimes C\) will fail.

This work aims at the development of support splitting algorithms for induced codes and the estimation of its efficiency in finding a secret key of the McEeliece cryptosystem based on the induced code \(\mathbb{F}_{q}^{l} \otimes C\). The monograph has the following structure. The second section provides information on codes, support splitting algorithms and preliminary results on induced codes. The support splitting algorithm for induced codes is considered, as well. The third section gives the example of applying this algorithm in the determination of a secret permutation of a McEliece cryptosystem on the induced code, and its efficiency is compared with that obtained in work [7]. The feasible use of induced codes in the identification algorithm is also within the scope of this study.

2 SUPPORT SPLITTING ALGORITHM FOR INDUCED CODES

2.1 Preliminary Results

Let \({{\mathbb{F}}_{q}}\) be the Galois field with a strength \(q\), where \(q\) is the degree of a prime number. For a vector \({\mathbf{x}}\) from a space \(\mathbb{F}_{q}^{n}\) with dimensionality \(n\), the weight \({\text{wt}}({\mathbf{x}})\) can be found as the power of a set of nonzero coordinates of the vector \({\mathbf{x}}\). Consider a \([n,k,d]\)-code \(C\) with a dimensionality \(k\), a length \(n\) and a code distance \(d\) in a space \(\mathbb{F}_{q}^{n}\). Let \(G(C)\) be a code generator matrix, \(C \subseteq \mathbb{F}_{q}^{n}\). Codes \(C\) and \(D\) with dimensionality \(k\) and length \(n\) are called permutation-equivalent, if there is a permutation \(\sigma \) from a symmetric group \({{S}_{n}}\), acting on the elements of a set \({{I}_{n}} = {\text{\{ }}1,...,n{\text{\} }}\), so that

$$D = \{ \left. {({{c}_{1}},...,{{c}_{n}})} \right|({{c}_{{{{\sigma }^{{ - 1}}}(1)}}},...,{{c}_{{{{\sigma }^{{ - 1}}}(n)}}}) \in C\} .$$

Hence, one uses the common designation \(D = \sigma (C)\). The next step is to determine the invariant and the signature from [8]. For some subset \(J( \subseteq {{I}_{n}})\), designate a set of vectors, obtained from those of the code \(C\) by zeroing the coordinates with numbers from \(J\), by \({{C}_{J}}\). Let \({{\mathcal{L}}_{n}}\) be a set of all codes with a length \(n\), \(\sigma {\kern 1pt} '(C) \ne D\). The mapping \(\mathcal{V}:\mathcal{L} \to E\) is called the invariant over a set \(E\), if any two permutation-equivalent codes \(C\) and \(D\) obey the equality: \(\mathcal{V}(C) = \mathcal{V}(D)\). A signature over a set \(F\) is the mapping \(\mathcal{S}:{{\mathcal{L}}_{n}} \times {{I}_{n}} \to F\), so that any permutation \(\sigma ( \in {{S}_{n}})\) and any code \(C \in {{\mathcal{L}}_{n}}\) are referred to the equality: \(\mathcal{S}(C,i) = \mathcal{S}(\sigma (C),\sigma (i))\). Below we consider only the signatures based on the invariant that meets the following rule:

$$\mathcal{S}(C,i) = \mathcal{V}({{C}_{i}}),$$
((1))

where \({{C}_{i}} = {{C}_{{\{ i\} }}}\). A discriminant of the code \(C\) is a signature \(S\), for which \(i\) and \(j\) from \({{I}_{n}}\) result in \(\mathcal{S}(C,i) \ne \mathcal{S}(C,j).\) Then a full discriminant for the code \(C\) is a signature cal \(\mathcal{S}\), so that \(\mathcal{S}(C,i) \ne \mathcal{S}(C,j)\) for all different \(i\) and \(j\) from \({{I}_{n}}\). The known fact can be summarized by the lemma below.

Lemma 1. Let \(C\) be a \([n,k,d]\)-code, \(\sigma \in {{S}_{n}}\), \(D = \sigma (C)\). The equality \(D = \gamma (C)\) is valid if and only if \(\gamma \in \sigma {\text{PAut}}(C)\), where \(\sigma {\text{PAut}}(C)\) is a factor-class from the factor-set \({{{{S}_{n}}} \mathord{\left/ {\vphantom {{{{S}_{n}}} {{\text{PAut}}}}} \right. \kern-0em} {{\text{PAut}}}}(C)\).

Proof. It is evident, if \(\gamma \in \sigma {\text{PAut}}(C)\), then \(D = \gamma (C)\). Let us prove in the opposite direction. Assume the equality \(D = \gamma (C)\), where \(\gamma \notin \sigma {\text{PAut}}(C)\). Since \(\gamma (C) = \sigma (C)\), then \({{\gamma }^{{ - 1}}}\sigma \in {\text{PAut}}(C)\). Hence \({{\gamma }^{{ - 1}}} = \phi {{\sigma }^{{ - 1}}}\), \(\phi \in {\text{PAut}}(C)\), and consequently \(\gamma \in \sigma {\text{PAut}}(C)\).

Consider the SSA algorithm that finds a permutation \(\sigma {\kern 1pt} '\) for two permutation-equivalent codes \(C\) and \(D = \sigma (C)\) using \(\mathcal{S}\), so that \(D = \sigma {\kern 1pt} '(C)\). Notice that \(\sigma \ne \sigma {\kern 1pt} '\) in the general case, but \({{\sigma }^{{' - 1}}} \in {\text{PAut}}(C)\) by Lemma 1. The permutation σ', returned by the SSA algorithm, will be called suitable. If \(\mathcal{S}\) is the total discriminant, then σ = σ', and the permutation σ will be found at the first iteration of the cycle from this algorithm. As follows from statement 8 of the monograph [8], the complete discriminant fulfills for the code \(C\), when the group of automorphisms \({\text{PAut}}(C)\) of the code C is trivial. Mention that codes with a trivial group of automorphisms exist [9].

According to work [8], even if the complete discriminant of the code \(C\) exists, its calculation may be a computationally difficult task. In this respect, there was proposed the approach [8] that ensures the construction of computationally simple complete discriminants based on incomplete discriminants. Since it considers only signatures based on invariants (see Eq. (1)), the latter have to be computationally simple.

An example of a computationally simple invariant for low-dimensionality codes is the mapping \({{\mathcal{V}}^{W}}:\mathcal{L} \to \mathbb{Z}[X]\) that assigns the code \(C\) to its weight numerator \(\mathcal{W}(C) = \sum\nolimits_{i = 0}^n {{W}_{i}}{{X}^{i}},\) where \({{W}_{i}}\) is the number of vectors with weights \(i\) in the code \(C\), \(\mathbb{Z}[X]\) is the set of polynomials from one variable with coefficients from \(\mathbb{Z}\). Using this invariant, one can construct a signature \({{\mathcal{S}}^{W}}:{{\mathcal{L}}_{n}} \times {{I}_{n}} \to \mathbb{Z}[X]\), determined from the rule \({{\mathcal{S}}^{W}}(C,i) = {{\mathcal{V}}^{W}}({{C}_{i}}) = \mathcal{W}({{C}_{i}})\). Mention that the computation complexity of the invariant \({{\mathcal{V}}^{W}}({{C}_{i}})\) increases in a nonpolynomial order with dimensionality of the code \({{C}_{i}}\). Hence a discriminant in work [8] is based on the computation of weight numerators of the code hull. A hull of the code \(C\) [8] implies the intersection of the code \(C\) with its dual code \({{C}^{ \bot }}\):

$$\mathcal{H}(C) = C \cap {{C}^{ \bot }}.$$
((2))

A choice of this characteristic is due to the fact that the hull dimensionality is typically much less than the dimensionality of the code \(C\), which enables one to efficiently calculate the numerators, as well as to plot computationally simple discriminant even in case of the large dimensionality of the code \(C\).

2.2 Induced Codes and Their Properties

Let \({{C}^{i}}\) be a \([{{n}_{i}},{{k}_{i}},{{d}_{i}}]\)-code with a generator matrix \(G({{C}^{i}})\) and a check matrix \(H({{C}^{i}})\), \(i = 1,2\). The Cartesian product \({{C}^{1}} \times {{C}^{2}}\) of codes \({{C}^{1}}\) and \({{C}^{2}}\) is assumed to be a set in the following form:

$${{C}^{1}} \times {{C}^{2}} = \{ (\left. {{\mathbf{a}}{\kern 1pt} } \right\|{\mathbf{b}}):{\mathbf{a}} \in {{C}^{1}},{\mathbf{b}} \in {{C}^{2}}\} ,$$

where \(\left. {{\mathbf{a}}{\kern 1pt} } \right\|{\mathbf{b}}\) is the concatenation of vectors \({\mathbf{a}}\) and \({\mathbf{b}}\). It is easily to see that the generator and check matrices of the code \({{C}^{1}} \times {{C}^{2}}\) can be presented as

$$\begin{gathered} G({{C}^{1}} \times {{C}^{2}}) = \left( {\begin{array}{*{20}{c}} {G({{C}^{1}})}&{{{O}_{{{{k}_{1}} \times {{n}_{2}}}}}} \\ {{{O}_{{{{k}_{2}} \times {{n}_{1}}}}}}&{G({{C}^{2}})} \end{array}} \right), \\ H({{C}^{1}} \times {{C}^{2}}) = \left( {\begin{array}{*{20}{c}} {H({{C}^{1}})}&{{{O}_{{{{n}_{1}} - {{k}_{1}} \times {{n}_{2}}}}}} \\ {{{O}_{{{{n}_{2}} - {{k}_{2}} \times {{n}_{1}}}}}}&{H({{C}^{2}})} \end{array}} \right), \\ \end{gathered} $$

where \({{O}_{{a \times b}}}\) is a zero \((a \times b)\)-matrix. As follows from definition (2):

$$\mathcal{H}({{C}^{1}} \times {{C}^{2}}) = \mathcal{H}({{C}^{1}}) \times \mathcal{H}({{C}^{2}}).$$
((3))

Lemma 2. Let \({{C}^{i}}\) be a \([{{n}_{i}},{{k}_{i}}]\)-code, \(\mathcal{W}({{C}^{i}}) = \sum\nolimits_{j = 0}^{{{n}_{i}}} W_{j}^{{(i)}}{{X}^{{(i)}}}\) is a numerator of the code \({{C}^{i}}\), \(i = 1,2\). Then the numerator of the code \({{C}^{1}} \times {{C}^{2}}\) takes the form

$$\mathcal{W}({{C}^{1}} \times {{C}^{2}}) = \mathcal{W}({{C}^{1}}) \cdot \mathcal{W}({{C}^{2}}).$$

Proof. Each code vector \({\mathbf{c}}\) from \({{C}^{1}} \times {{C}^{2}}\) can be presented by a concatenation \((\left. {{\mathbf{a}}{\kern 1pt} } \right\|{\mathbf{b}})\) of vectors \({\mathbf{a}}\) and \({\mathbf{b}}\) from codes \({{C}^{1}}\) and \({{C}^{2}}\), respectively. Find the number of weight vectors \(j(0 \leqslant j \leqslant {{n}_{1}} + {{n}_{2}})\) in the code \({{C}^{1}} \times {{C}^{2}}\). For this, consider all kinds of ordered pairs \(({{j}_{1}},{{j}_{2}})\) of nonnegative integers, so that \({{j}_{1}} + {{j}_{2}} = j\). Each pair \(({{j}_{1}},{{j}_{2}})\) in the code \({{C}^{1}} \times {{C}^{2}}\) has a set from \(W_{{{{j}_{1}}}}^{{(1)}} \cdot W_{{{{j}_{2}}}}^{{(2)}}\) of weight vectors \(j\). These sets do not intersect for various pairs. Hence, the code \({{C}^{1}} \times {{C}^{2}}\) contains

$$\sum\limits_{({{j}_{1}},{{j}_{2}}):{{j}_{1}} + {{j}_{2}} = j} {W_{{{{j}_{1}}}}^{{(1)}} \cdot W_{{{{j}_{2}}}}^{{(2)}}} $$

weight vectors \(j\). Then

$$\mathcal{W}({{C}^{1}} \times {{C}^{2}}) = \sum\limits_{j = 0}^{{{n}_{1}} + {{n}_{2}}} {\left( {\sum\limits_{({{j}_{1}},{{j}_{2}}):{{j}_{1}} + {{j}_{2}} = j} {W_{{{{j}_{1}}}}^{{(1)}} \cdot W_{{{{j}_{2}}}}^{{(2)}}} } \right)} {{X}^{j}} = \mathcal{W}({{C}^{1}}) \cdot \mathcal{W}({{C}^{2}}).$$

A tensor product \(A \otimes B\) of matrices \(A = {{({{a}_{{i,j}}})}_{{i = 1,m;j = 1,l}}}\) and \(B\) is implied to be a matrix

$$A \otimes B = \left( {\begin{array}{*{20}{c}} {{{a}_{{1,1}}}B}& \ldots &{{{a}_{{1,l}}}B} \\ \ldots & \ldots & \ldots \\ {{{a}_{{m,1}}}B}& \ldots &{{{a}_{{m,l}}}B} \end{array}} \right).$$

Let \(C\) be a \([n,k,d]\)-code with a generator matrix \(G(C)\), \({{E}_{l}}\) is the unit matrix of the order \(l\). A subspace, generated by the lines of a matrix \({{E}_{l}} \otimes G(C)\), will be designated by \(\mathbb{F}_{q}^{l} \otimes C\) and called the induced code (or the code induced by the code \(C\)) [7]. A generator matrix of this code \(G(\mathbb{F}_{q}^{l} \otimes C) = {{E}_{l}} \otimes G(C)\) has a block structure

$$G(\mathbb{F}_{q}^{l} \otimes C) = \underbrace {\left( {\begin{array}{*{20}{c}} {G(C)}&{{{O}_{{k \times n}}}}& \ldots &{{{O}_{{k \times n}}}} \\ {{{O}_{{k \times n}}}}&{G(C)}& \ldots &{{{O}_{{k \times n}}}} \\ \ldots & \ldots & \ldots & \ldots \\ {{{O}_{{k \times n}}}}&{{{O}_{{k \times n}}}}& \ldots &{G(C)} \end{array}} \right)}_{l\,\,{\text{bloks}}},$$
((4))

where each block line has \(l - 1\) nonzero matrices \({{O}_{{k \times n}}}\) and one matrix \(G(C)\). Since

$$\mathbb{F}_{q}^{l} \otimes C = \underbrace {C \times ... \times C}_{t\,{\text{times}}},$$

then Lemma 2 yields

Corollary 1. Let \(C\) be a \([n,k]\)-code with a generator matrix \(G(C)\) and \(\mathcal{W}(C)\) be a numerator of the code \(C\). Then

(1) \(\mathcal{W}(F_{q}^{l} \otimes C) = \underbrace {\mathcal{W}(C) \cdot ... \cdot \mathcal{W}(C)}_{l\;{\text{times}}}\);

(2) \(\forall i \in \{ 1,...,ln\} \exists j \in \{ 1,...,n\} \): \(\mathcal{W}({{(\mathbb{F}_{q}^{l} \otimes C)}_{i}})\) = \(\mathcal{W}({{C}_{j}}) \cdot \underbrace {\mathcal{W}(C) \cdot ... \cdot \mathcal{W}(C)}_{l - 1\;{\text{times}}}.\)

It also appears that a check matrix of the code \(\mathbb{F}_{q}^{l} \otimes C\) can be written as \(H(\mathbb{F}_{q}^{l} \otimes C) = {{E}_{l}} \otimes H(C)\), where \(H(C)\) is the check matrix of the code \(C\). As follows from Eq. (3), the hull of the code \(\mathbb{F}_{q}^{l} \otimes C\) takes the form

$$\mathcal{H}(\mathbb{F}_{q}^{l} \otimes C) = \mathbb{F}_{q}^{l} \otimes \mathcal{H}(C).$$
((5))

Consider the induced code \(\mathbb{F}_{q}^{l} \otimes C\), \(l \in \mathbb{N}\). A group of automorphisms \({\text{PAut}}(\mathbb{F}_{q}^{l} \otimes C)\) of this code is nontrivial. Indeed, the generator matrix of the code \(\mathbb{F}_{q}^{l} \otimes C\) is presented by a block diagonal structure (4), and any permutation of blocks of this matrix results in a generator matrix of the same code. The permutation of block columns of this matrix is equivalent to the permutation of block lines. There are \(l!\) such block column permutations in total. Hence the group of automorphisms of the code \(\mathbb{F}_{q}^{l} \otimes C\) has a power of at least \(l!\). It yields the following lemma.

Lemma 3. A group of automorphisms \({\text{PAut}}(\mathbb{F}_{q}^{l} \otimes C)\) of the code \(\mathbb{F}_{q}^{l} \otimes C\) contains a subgroup \(\mathcal{G}(\mathbb{F}_{q}^{l} \otimes C)\), being isomorphic to a group \({{S}_{l}}\).

Notice that each element of the group \(\mathcal{G}{\kern 1pt} (\mathbb{F}_{q}^{l} \otimes C)\) has the form

$$\left( {\begin{array}{*{20}{c}} 1& \ldots &n& \ldots &{(l - 1)n + 1}& \ldots &{ln} \\ {(\sigma (1) - 1)n + 1}& \ldots &{\sigma (1)n}& \ldots &{(\sigma (l) - 1)n + 1}& \ldots &{\sigma (l)n} \end{array}} \right),\,\,\sigma \in {{S}_{l}}.$$
((6))

Let \({{I}_{{i,n}}} = \{ i,i + n, \ldots ,i + (l - 1) \cdot n\} \) be, where \(i \in \{ 1, \ldots ,n\} \), \(S({{I}_{{i,n}}})\) is a subgroup of the group \({{S}_{{ln}}}\), where the permutations involve only the elements of a set Ii,n, and the elements of a set \(\{ 1, \ldots ,\ln \} \backslash {{I}_{{i,n}}}\) are fixed. Consider a group Q = \(S({{I}_{{1,n}}}) \times S({{I}_{{2,n}}}) \times \ldots \times S({{I}_{{n,n}}})\)\( \subset {{S}_{{ln}}}\), \(\left| Q \right| = {{(l!)}^{n}}\). It is easy to see that

$$\mathcal{G}(\mathbb{F}_{q}^{l} \otimes C) \subseteq {\text{PAut}}(\mathbb{F}_{q}^{l} \otimes C) \cap Q.$$
((7))

We remind that an orbit of an element \(i \in \{ 1,...,ln\} \) under the action of a subgroup \(\mathcal{G} \subseteq {{S}_{{ln}}}\) is a set \(\{ g(i):g \in \mathcal{G}\} \). Then \({{I}_{{i,n}}}\), \(i = 1,...,n\), are the orbits that form by a subgroup \(\mathcal{G}(\mathbb{F}_{q}^{l} \otimes C)\) on the elements of a set \(\{ 1,...,ln\} \). Expression (7) yields the following auxiliary lemma.

Lemma 4. A length of each orbit, forming under the action of a group \({\text{PAut}}(\mathbb{F}_{q}^{l} \otimes C)\)to the elements of a set \(\{ 1,...,ln\} \) is a multiple of \(l\).

2.3 Support Splitting Algorithm

As aforementioned, two permutation-equivalent codes with a complete discriminant \(\mathcal{S}\) for finding the most suitable permutation require not more than one iteration of the internal cycle of a SSA algorithm. It follows from Lemma 3, there is no complete discriminant for the code \(\mathbb{F}_{q}^{l} \otimes C\), because the group of automorphisms of this code is nontrivial. Consider an algorithm plotting problem for the codes \(\mathbb{F}_{q}^{l} \otimes C\) and \(D = \sigma (\mathbb{F}_{q}^{l} \otimes C)\), which allows a suitable permutation \(\sigma '\) to be determined so that \(\sigma {\kern 1pt} '(\mathbb{F}_{q}^{l} \otimes C) = D\).

Lemma 5. Let \(C\) be a \([n,k,d]\)-code. Then for \(i = 1,...,n\) and any signature \(\mathcal{S}\), found from the rule (1), the following equality is valid:

$$\mathcal{S}(\mathbb{F}_{q}^{2} \otimes C,i) = \mathcal{S}(\mathbb{F}_{q}^{2} \otimes C,i + n).$$
((8))

Proof. According to definition (1), \(\mathcal{S}(\mathbb{F}_{q}^{2} \otimes C,i) = \mathcal{V}({{(\mathbb{F}_{q}^{2} \otimes C)}_{i}})\). Let \(\mathcal{V}({{(\mathbb{F}_{q}^{2} \otimes C)}_{i}})\)\( \ne \mathcal{V}({{(F_{q}^{2} \otimes C)}_{{i + n}}})\) be. For any permutation \(\pi \) from the invariant definition: \(\mathcal{V}({{(\mathbb{F}_{q}^{2} \otimes C)}_{i}})\) = \(\mathcal{V}(\pi ({{(\mathbb{F}_{q}^{2} \otimes C)}_{i}}))\). Consider an arbitrary nontrivial permutation \(\pi \in \mathcal{G}(\mathbb{F}_{q}^{2} \otimes C)\). Hence,

$$\mathcal{V}({{(\mathbb{F}_{q}^{2} \otimes C)}_{i}}) = \mathcal{V}(\pi ({{(\mathbb{F}_{q}^{2} \otimes C)}_{i}})) = \,\,\mathcal{V}(\pi {{(\mathbb{F}_{q}^{2} \otimes C)}_{{\pi (i)}}}) = \mathcal{V}({{(\mathbb{F}_{q}^{2} \otimes C)}_{{\pi (i)}}}).$$

Since π is the nontrivial permutation, then the elements (6) of a group \(\mathcal{G}(\mathbb{F}_{q}^{2} \otimes C)\) for \(l = 2\) result in: \(\pi (i) = i + n\). This is a contradistinction.

Taking the representation (6) into account, Lemma 5 yields a corollary below.

Corollary 2. For the code \(\mathbb{F}_{q}^{l} \otimes C\) and \(i \in \{ 1,...,n\} \), the following equality is valid: \(\mathcal{S}(\mathbb{F}_{q}^{l} \otimes C,i)\) = \(\mathcal{S}(\mathbb{F}_{q}^{l} \otimes C,i + n \cdot k)\), for all \(k = \{ 0, \ldots ,l - 1\} \).

Thus, any signature for the code \(\mathbb{F}_{q}^{l} \otimes C\), determined using the rule (1), has not more than \(n\) various values. The more values the signature has for the code, the fewer cycles of the SSA algorithm are required for finding a suitable permutation.

Lemma 6. If \(\mathcal{G}(\mathbb{F}_{q}^{l} \otimes C) \subset {\text{PAut}}(\mathbb{F}_{q}^{l} \otimes C)\), then any signature for the code \(C\), found from the rule (1), has less than \(n\) values.

Proof. It follows from Corollary 2 that any signature for the code \(\mathbb{F}_{q}^{l} \otimes C\), established from the rule (1), has not more than \(n\) various values. Hence, in according to statement 8 [8], the group \({\text{PAut}}(\mathbb{F}_{q}^{l} \otimes C)\) in a set \(\{ 1,...,ln\} \) leads to the formation of not more than \(n\) different orbits. Let \(\sigma \in {\text{PAut}}(\mathbb{F}_{q}^{l} \otimes C)\backslash \mathcal{G}(\mathbb{F}_{q}^{2} \otimes C)\) be, then there is an element \(i \in \{ 1,...,n\} \), so that \(\sigma (i) \ne i + n \cdot k\) for some \(k \in \{ 0, \ldots ,l - 1\} \). Therefore, it obtains from Lemma 4 that at least one orbit has a length not less than \(2l\). Hence, the group \({\text{PAut}}(\mathbb{F}_{q}^{l} \otimes C)\) favors the formation of not more than \(n - 1\) orbits. Based on statement 8 [8], a signature has not more than \(n - 1\) various values.

Corollary 3. Let a signature 𝒮 be defined in accordance with the rule (1). If 𝒮 for the code \(\mathbb{F}_{q}^{l} \otimes C\) has \(n\) various values, then \({\text{PAut}}(\mathbb{F}_{q}^{l} \otimes C) = \mathcal{G}(\mathbb{F}_{q}^{l} \otimes C)\).

Example 1. Consider a code \({{C}^{1}} \times {{C}^{2}}\) and find a weight numerator of the code \({{({{C}^{1}} \times {{C}^{2}})}_{i}}\), then \(i \in \{ 1,...,{{n}_{1}} + {{n}_{2}}\} \). If \(i \leqslant {{n}_{1}}\), then \(\mathcal{W}({{({{C}^{1}} \times {{C}^{2}})}_{i}})\) = \(\mathcal{W}(C_{i}^{1}) \cdot \mathcal{W}({{C}^{2}})\); if \({{n}_{1}} < i \leqslant {{n}_{1}} + {{n}_{2}}\), then \(\mathcal{W}({{({{C}^{1}} \times {{C}^{2}})}_{i}})\) = \(\mathcal{W}({{C}^{1}}) \cdot \mathcal{W}(C_{{i - {{n}_{1}}}}^{2})\). Hence

$${{\mathcal{S}}^{W}}({{C}^{1}} \times {{C}^{2}},i) = \mathcal{W}({{({{C}^{1}} \times {{C}^{2}})}_{i}}) = \,\,\mathcal{W}(C_{{i - (a - 1) \cdot {{n}_{1}}}}^{a}) \cdot \mathcal{W}({{C}^{b}}),$$
((9))

where

$$a = \left\{ {\begin{array}{*{20}{c}} {1,}&{{\text{at}}\,\,1 \leqslant i \leqslant {{n}_{1}}} \\ {2,}&{{\text{at}}\,\,{{n}_{1}} + 1 \leqslant i \leqslant {{n}_{1}} + {{n}_{2}},} \end{array}} \right.$$

\(b = \{ 1,2\} \backslash \{ a\} \). For \({{C}^{1}} = {{C}^{2}} = C\) one obtains: \({{C}^{1}} \times {{C}^{2}}\) = \(\mathbb{F}_{q}^{2} \otimes C\), thus

$${{\mathcal{S}}^{W}}(\mathbb{F}_{q}^{2} \otimes C,i) = \mathcal{W}(C) \cdot \mathcal{W}({{C}_{j}}),$$
((10))

where

$$j = \left\{ {\begin{array}{*{20}{c}} {i,}&{{\text{at}}\,\,1 \leqslant i \leqslant n} \\ {i - n,}&{{\text{at}}\,\,n < i \leqslant 2n.} \end{array}} \right.$$

If \(C\) is a \([n,k]\)-code, so that \({{\mathcal{S}}^{W}}\)is its complete discriminant, then, according to Corollary 1 and generalizations of formula (10) to the case \(l \geqslant 2\), a signature \({{\mathcal{S}}^{W}}\) for the code \(\mathbb{F}_{q}^{l} \otimes C\) has \(n\) various values. Then it follows from Corollary 3 that a group of automorphisms of the code \(\mathbb{F}_{q}^{l} \otimes C\) is described in a simple manner.

Lemma 7. Let 𝒮 be a signature found from the rule (1). Then for any \(\pi \in Q\) there are the following equalities:

(1) \(\mathcal{S}(\mathbb{F}_{q}^{l} \otimes C,i) = \mathcal{S}(\mathbb{F}_{q}^{l} \otimes C,\pi (i)),\)\(i = 1,...,ln\);

(2) \((\mathcal{S}(\mathbb{F}_{q}^{l} \otimes C,i))_{{i = 1}}^{{ln}} = (\mathcal{S}(\mathbb{F}_{q}^{l} \otimes C,\pi (i)))_{{i = 1}}^{{ln}};\)

(3) \((\mathcal{S}(\mathbb{F}_{q}^{l} \otimes C,i))_{{i = 1}}^{{ln}} = \pi ((\mathcal{S}(\mathbb{F}_{q}^{l} \otimes C,i))_{{i = 1}}^{{ln}}).\)

Proof. The proof of the equality (1) follows from Corollary 2; the equality (2) follows from the equality (1). Prove Statement (3). It appears from Statement (2) that

$$(\mathcal{S}(\mathbb{F}_{q}^{l} \otimes C,i))_{{i = 1}}^{{ln}} = (\mathcal{S}(\mathbb{F}_{q}^{l} \otimes C,\pi (i)))_{{i = 1}}^{{ln}} = (\mathcal{S}(\mathbb{F}_{q}^{l} \otimes C,j))_{{{{\pi }^{{ - 1}}}(j) = 1}}^{{ln}} = \pi ((\mathcal{S}(\mathbb{F}_{q}^{l} \otimes C,j))_{{j = 1}}^{{ln}}).$$

Since \(\pi \) is the arbitrary permutation from the group \(Q\), then the statement is proved.

A symbol \(\sigma Q\) means a factor-class \(\{ \sigma \pi :\pi \in Q\} \) of a factor-set – \({{{{S}_{{nl}}}} \mathord{\left/ {\vphantom {{{{S}_{{nl}}}} Q}} \right. \kern-0em} Q}\).

Lemma 8. If a signature \(\mathcal{S}\) for the code \(\mathbb{F}_{q}^{l} \otimes C\) is determined using the rule (1) and has \(n\) various values, then \(D = \sigma (\mathbb{F}_{q}^{l} \otimes C)\) and

$$(\mathcal{S}(D,i))_{{i = 1}}^{{ln}} = \gamma ((\mathcal{S}(\mathbb{F}_{q}^{l} \otimes C,i))_{{i = 1}}^{{ln}}),$$
((11))

hence \(\sigma \in \gamma Q\).

Proof. It follows from Statement (3) of Lemma 7 and condition (11) that for any\(\pi \in Q\) the following equalities are valid:

$$(\mathcal{S}(D,i))_{{i = 1}}^{{ln}} = \gamma ((\mathcal{S}(\mathbb{F}_{q}^{l} \otimes C,i))_{{i = 1}}^{{ln}}) = \,\,\gamma \pi ((\mathcal{S}(\mathbb{F}_{q}^{l} \otimes C,i))_{{i = 1}}^{{ln}}).$$

Since in accordance with the condition, a signature has a maximum amount of various values \(n\), then \(\sigma \in \gamma Q\) with respect to the construction of a group \(Q\) (\(Q\) is a maximum subgroup that does not change the order of elements in a set \((\mathcal{S}(\mathbb{F}_{q}^{l} \otimes C,i))_{{i = 1}}^{{ln}}\)).

Let \({Q \mathord{\left/ {\vphantom {Q {\mathcal{G}(\mathbb{F}_{q}^{l} \otimes C)}}} \right. \kern-0em} {\mathcal{G}(\mathbb{F}_{q}^{l} \otimes C)}} = \{ {{G}_{i}}\} _{{i = 0}}^{x}\) be a factor-set of a group \(Q\) with respect to a group \(\mathcal{G}(\mathbb{F}_{q}^{l} \otimes C)\), \(x + 1 = {{\left| Q \right|} \mathord{\left/ {\vphantom {{\left| Q \right|} {\left| {\mathcal{G}(\mathbb{F}_{q}^{l} \otimes C)} \right|}}} \right. \kern-0em} {\left| {\mathcal{G}(\mathbb{F}_{q}^{l} \otimes C)} \right|}} = {{{{{(l!)}}^{n}}} \mathord{\left/ {\vphantom {{{{{(l!)}}^{n}}} {l!}}} \right. \kern-0em} {l!}} = {{(l!)}^{{n - 1}}}.\) Let also \(\Omega = \{ {{\omega }_{0}}, \ldots ,{{\omega }_{x}}\} \) be a transversal of a factor-set \({Q \mathord{\left/ {\vphantom {Q \mathcal{G}}} \right. \kern-0em} \mathcal{G}}(\mathbb{F}_{q}^{l} \otimes C)\), or a set of representatives of the adjacency classes \({{G}_{i}} = {{\omega }_{i}}\mathcal{G}(\mathbb{F}_{q}^{l} \otimes C)\), \(i = 0,...,x\). Among the possible plotting schemes of a set \(Q\), there is a \({\text{MakeRepresentatives}}\) algorithm.

Theorem 1. Let \(C\) be a \([n,k]\)-code, \(D = \sigma (\mathbb{F}_{q}^{l} \otimes C)\), \(\mathcal{S}\) is a signature defined from the rule (1) and having \(n\) various values for the code \(\mathbb{F}_{q}^{l} \otimes C\), \(\Omega \) is a transversal of a factor-set \({Q \mathord{\left/ {\vphantom {Q \mathcal{G}}} \right. \kern-0em} \mathcal{G}}(\mathbb{F}_{q}^{l} \otimes C)\). Then there is an algorithm with a computation complexity \(\mathcal{O}(\left| \Omega \right|)\), which finds a suitable permutation \(\sigma {\kern 1pt} '\), so that \(D = \sigma '(\mathbb{F}_{q}^{l} \otimes C)\).

Proof. Let \((\mathcal{S}(D,i))_{{i = 1}}^{{ln}} = \gamma ((\mathcal{S}(\mathbb{F}_{q}^{l} \otimes C,i))_{{i = 1}}^{{ln}})\). This permutation \(\gamma \) can be found by a simple calculation of signatures of codes \(D\) and \(C\). Then Lemma 8 gives \(\sigma \in \gamma Q\). As seen from Lemma 1, a suitable permutation that converts the code \(\mathbb{F}_{q}^{l} \otimes C\) into a code \(D\), is a permutation \(\sigma \pi \), where \(\pi \in {\text{PAut}}(\mathbb{F}_{q}^{l} \otimes C)\). Since the signature has \(n\) various values, then it obtains from Corollary 3 that \({\text{PAut}}(\mathbb{F}_{q}^{l} \otimes C) = \mathcal{G}(\mathbb{F}_{q}^{l} \otimes C)\). Hence a suitable permutation can be established by sorting out the elements in a transversal\(\Omega \). Thus, a suitable permutation can be found via the SSAForTensor algorithm, whose complexity is\(\mathcal{O}(\left| \Omega \right|)\), due to sorting out the elements with respect to a transversal \(\Omega \).

Mention that Theorem 1 in the estimation of complexity of the \({\text{SSAForTensor}}\) algorithm takes only the power of the transversal into account, but neglects the computation complexity of signatures (steps 1 and 2), as well as the complexity of checking the coincidence of two codes (steps 4) and the complexity of constructing a transversal \(\Omega \) used as an input parameter. The coincidence of two codes can be verified by multiplying the generator matrix \({{(\gamma \omega )}^{{ - 1}}}(D)\) by a check matrix \(H(\mathbb{F}_{q}^{l} \otimes C)\) of the code \(\mathbb{F}_{q}^{l} \otimes C\). Thus, the complexity of this test depends polynomially on \(ln\), i.e., the verification can be implemented by the effective way. On the other hand, plotting the effectively computable signatures is an individual task [8]. In particular [8], the effective signatures can be constructed using a numerator of a code hull, which is likely to have a small dimension. As follows from Eq. (5), the hull dimensionality for the induced code increases by \(l\) times in comparison with a hull of the base code. In turn, this may substantially slow down the calculation of numerators of its projection in the general case and complicate the computation of signatures, because it requires that the vectors of the hull projection are sorted out for all coordinates. Plotting a transversal \(\Omega \) is also a complex problem at high enough values \(ln\). The above proposed \({\text{MakeRepresentatives}}\) algorithm has a \(ln\)-nonpolynomial complexity, although it can be done in advance.

Meanwhile, while the code \(\mathbb{F}_{q}^{l} \otimes C\) possess the effectively computational signature, determined from the rule (1) and offering \(n\) various values along with a transversal \(\Omega \), a \({\text{SSAForTensor}}\) algorithm is assumed to be more powerful than \({\text{SSA}}\) at establishing a suitable permutation. This is due to the fact that \({\text{SSA}}\) searches a suitable permutation over the whole adjacency class \(\sigma Q\) and \({\text{SSAForTensor}}\) algorithm makes a search over a set \(\sigma \Omega \) only, whose power is lower by \(l!\) times than \(\left| {\sigma Q} \right|\) because \({{\left| Q \right|} \mathord{\left/ {\vphantom {{\left| Q \right|} {\left| \Omega \right|}}} \right. \kern-0em} {\left| \Omega \right|}} = \left| {\mathcal{G}(\mathbb{F}_{q}^{l} \otimes C)} \right| = l!\,.\)

3 APPLICATION OF INDUCED CODES IN CRYPTOGRAPHY

3.1 A McEliece Cryptosystem Based on Induced Codes

Consider a McEliece cryptosystem based on a \([ln,lk,d]\)-code \(\mathbb{F}_{q}^{l} \otimes C\), where \(C\) is a \([n,k,d]\)-code with a generator matrix \(G(C)\). In this cryptosystem, an open key \({{{\mathbf{k}}}_{{{\text{pub}}}}}\) is a pair \((\widetilde G,t = \left\lfloor {r{{(d - 1)} \mathord{\left/ {\vphantom {{(d - 1)} 2}} \right. \kern-0em} 2}} \right\rfloor )\), and a secret key \({{{\mathbf{k}}}_{{{\text{sec}}}}}\) is a matrix pair \((S,P)\), where \(S\) is a random nondegenerate \((lk \times lk)\)-matrxi, \(P\) is a random permutation \((ln \times ln)\)-matrix, where \(\widetilde G = S \cdot ({{E}_{l}} \otimes G(C)) \cdot P\) with \({{E}_{l}}\) as a unit matrix of dimensions \(l \times l\). The coding rule of an arbitrary message \({\mathbf{s}}( \in \mathbb{F}_{q}^{{lk}})\) has the form

$${\mathbf{z}} = {\mathbf{s}}\widetilde G + {\mathbf{e}},$$
((12))

where \({\mathbf{e}} \in \mathbb{F}_{q}^{{ln}}\) and \({\text{wt}}({\mathbf{e}}) \leqslant t\).

The decoding uses a rule \({\mathbf{s}} = {\text{De}}{{{\text{c}}}_{C}}({\mathbf{z}}{{P}^{{ - 1}}}){{S}^{{ - 1}}}\), where \(De{{c}_{{\mathbb{F}_{q}^{l} \otimes C}}}:\mathbb{F}_{q}^{{ln}} \to \mathbb{F}_{q}^{{lk}}\) is the decoder of the code \(\mathbb{F}_{q}^{l} \otimes C\), which guarantees the correction of \(t\) and less errors and recovers a vector \({\mathbf{s}}\). A McEliece cryptosystem based on the code \(\mathbb{F}_{q}^{l} \otimes C\) will be designated by \({\text{McE}}(\mathbb{F}_{q}^{l} \otimes C)\).

Since the code with a generator matrix \(\widetilde G\) and the code \(\mathbb{F}_{q}^{l} \otimes C\) are permutation-equivalent, the \({\text{McE}}(\mathbb{F}_{q}^{l} \otimes C)\) cryptosystem can be hacked by finding a matrix pair (S',P'), so that \(S{\kern 1pt} '({{E}_{l}} \otimes G(C))P{\kern 1pt} ' = \widetilde G\) [4], and the permutation referred to a permutation matrix \({{P}^{{' - 1}}}P\) belongs to \({\text{PAut}}(\mathbb{F}_{q}^{l} \otimes C)\).

As shown in work [7], if the McE(C) cryptosystem on the base code \(C\) is unstable to attacks, there is an algorithm for establishing a suitable permutation matrix for the \({\text{McE}}(\mathbb{F}_{q}^{l} \otimes C)\) cryptosystem, whose complexity is estimated by \(\mathcal{O}\left( {\tfrac{{(nl)!}}{{{{{(n!)}}^{l}}l!}}} \right)\). Using the Stirling formula, it obtains that

$$\frac{{(nl)!}}{{{{{(n!)}}^{l}}l!}} \approx \frac{{\sqrt {2\pi nl} {{{\left( {\frac{{nl}}{e}} \right)}}^{{nl}}}}}{{{{{\left( {\sqrt {2\pi n} {{{\left( {\frac{n}{e}} \right)}}^{n}}} \right)}}^{l}}\sqrt {2\pi l} {{{\left( {\frac{l}{e}} \right)}}^{l}}}} = \,\,\sqrt {\frac{n}{{{{{(2\pi n)}}^{l}}}}} \cdot {{e}^{l}} \cdot {{l}^{{l \cdot (n - 1)}}}.$$
((13))

Furthermore, a suitable permutation in case of a discriminant existing for the code \(\mathbb{F}_{q}^{l} \otimes C\) can be found using the SSA. Consider the most favorable condition in the viewpoint of the attacker, when the effectively calculated signature \(\mathcal{S}\) with \(n\) various values is known for the code \(\mathbb{F}_{q}^{l} \otimes C\) and a transversal \(\Omega \) is constructed for a factor-set \({Q \mathord{\left/ {\vphantom {Q {\mathcal{G}(\mathbb{F}_{q}^{l} \otimes C)}}} \right. \kern-0em} {\mathcal{G}(\mathbb{F}_{q}^{l} \otimes C)}}\). Thus, the conditions of Theorem 1 are fulfilled, and SSAForTensor can be substituted for \({\text{SSA}}\). It follows from Theorem 1 that the persistence of a cryptosystem \({\text{McE(}}\mathbb{F}_{q}^{l} \otimes C)\) is evaluated by \(\mathcal{O}(\left| \Omega \right|) = \mathcal{O}({{(l!)}^{{n - 1}}})\). Using the Stirling formula gives

$$(l){{!}^{{n - 1}}} \approx \mathop {\left( {\sqrt {2\pi l} \mathop {\left( {\frac{l}{e}} \right)}\nolimits^l } \right)}\nolimits^{n - 1} = \mathop {\left( {\frac{{\sqrt {2\pi l} }}{{{{e}^{l}}}}} \right)}\nolimits^{n - 1} \cdot {{l}^{{l \cdot (n - 1)}}}.$$
((14))

Notice that expressions (13) and (14) are the estimated powers of sets of keys, where suitable permutations are being searched by sorting out via the algorithm [7] and SSAForTensor. According to monograph [10], sorting out with respect to a key set with a power of \({{2}^{{128}}}\) and higher is considered computationally impracticable. In order to compare estimations (13) and (14), take as an example the construction of the induced code \(\mathbb{F}_{q}^{l} \otimes C\) using a double Ride—Maller \([n,k,d]\)-code \(C\), where \(n \in \{ 8,16,32,64,128,256\} \) and \(q = 2\).

Tables 1 and 2 show the values \(lo{{g}_{2}}K\) calculated for a hacked cryptosystem \({\text{McE}}(\mathbb{F}_{2}^{l} \otimes C)\), \(l \in \{ 2,3,4,5,6,7,8,9\} \), where the parameter \(K\) in Table 2 is evaluated from expression (13), and that in Table 1 is obtained from formula (14). The cells highlighted in both tables correspond to the parameters of the induced code \(\mathbb{F}_{2}^{l} \otimes C\), for which the sort complexity is not less than \({{2}^{{128}}}\). A comparative analysis of the corresponding values in tables reveals that hacking based on a SSAForTensor splitting algorithm is much more efficient than that described in work [7]. However, this hacking in selecting parameters \(n\) and \(l\) can also be impracticable.

Table 1.   Values of \(lo{{g}_{2}}\left( {\tfrac{{(nl)!}}{{{{{(n!)}}^{l}}l!}}} \right)\)
Full size table
Table 2.   Values of \(lo{{g}_{2}}({{((l)!)}^{{n - 1}}})\)
Full size table

As shown in monograph [11], the use of induced codes in McEliece cryptosystems causes the weakening of the resilience of a system to attacks on cipher based on the dataset decoding method. The acceptable resilience to these attacks is achieved at large code lengths, which is due to the fact that dimensionality and length of induced codes increase by \(l\) times at a fixed code distance. Meanwhile, a \({\text{McE}}(\mathbb{F}_{2}^{l} \otimes C)\) cryptosystem can be applied when coding involves the error vectors with weights beyond the capacity of a decoder \({\text{De}}{{{\text{c}}}_{{\mathbb{F}_{2}^{l} \otimes C}}}\). So, a shared secret key generation protocol was obtained based on the above cryptosystem [7]. The next subsection is dedicated to another application of induced codes, i.e., their use in cryptographic identification protocols.

3.2 Identification Protocol Based on Induced Codes

An identification protocol based on the complexity in finding the permutation for two permutation-equivalent codes over a binary field was constructed by Girault [12]. Consider this protocol for a case \({{\mathbb{F}}_{q}}\). Let \(H\) be a \((N - K \times N)\)-matrix over a field \({{\mathbb{F}}_{q}}\), shared by all protocol users. Each user \(\mathcal{P}\) randomly chooses a vector \({\mathbf{e}}\) with a small weight \(w\) and calculates \(H{{{\mathbf{e}}}^{ \top }} = {{{\mathbf{s}}}^{ \top }}\). The vector \({\mathbf{s}}\) is a public identifier of a user \(\mathcal{P}\). If the relying party \(\mathcal{V}\) intends to authenticate a user \(\mathcal{P}\), i.e., to check that the authenticated user knows a vector \({\mathbf{e}}\), a 3-step protocol is being implemented.

Step 1:\(\mathcal{P}\) randomly and equally likely choses a permutation \((N \times N)\)-matrix \(P\) and an undegenerated \((N - K \times N - K)\)-matrix \(S\), calculates \(\widetilde H = SHP\) and \({\mathbf{s}}{\kern 1pt} ' = S{\mathbf{s}}\) and sends a matrix \(eH\) and a vector s'to \(\mathcal{V}\).

Step 2:\(\mathcal{V}\) randomly and equally likely choses a bit \(c \in \{ 0,1\} \) and sends it to \(\mathcal{P}\).

Step 3a: If \(c = 0\), then \(\mathcal{P}\) transfers the matrices \(S\) and \(P\) to \(\mathcal{V}\) that verifies that \(SHP = \widetilde H\) and \({\mathbf{s}}{\kern 1pt} ' = S{\mathbf{s}}\).

Step 3b: If \(c = 1\), then \(\mathcal{P}\) transfers \({\mathbf{e}}{\kern 1pt} ' = {{P}^{{ - 1}}}{\mathbf{e}}\) to \(\mathcal{V}\) that verifies that \({\text{wt}}({\mathbf{e}}{\kern 1pt} ') = w\) and \(\widetilde H{\mathbf{e}}{\kern 1pt} ' = {\mathbf{s}}\).

This protocol is running \(m\) times, where a safety parameter \(m\) is chosen so that a proving party fraud probability \({{{1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-0em} 2}}^{m}}\) is less than a predetermined threshold. Let the communication complexity of this protocol to be estimated. In Step 1, the proving party passes \((N - K)(N + 1)lo{{g}_{2}}q\) bit of data. In Step 2, the relying party transfers one bit. The amount of data transferred at Step 3 depends on the bit value \(c\): at \(c = 0\) there are \({{(N - K)}^{2}}lo{{g}_{2}}q + Nlo{{g}_{2}}N\) bit, and at \(c = 1\) there are \(Nlo{{g}_{2}}q\) bit transferred. Taking into account the fact that the bit value \(c\) is chosen randomly and equally likely, then \(m\) iterations result in the following communication complexity of a protocol:

$$\left( {1 + \frac{{3N - K}}{2}} \right)m(N - K)lo{{g}_{2}}q + \,\,N(lo{{g}_{2}}N + {m \mathord{\left/ {\vphantom {m 2}} \right. \kern-0em} 2}lo{{g}_{2}}q) + m\;{\text{bit}}.$$
((15))

As mentioned in work [13], if a matrix \(H\)is selected in a random manner, then the Giraut protocol is unsteady. At the same time, it is possible to calculate the codes with high-dimensionality hulls, because the complexity of the calculation of a signature \({{\mathcal{S}}^{W}}\) proposed in monograph [8] is a linear function of hull dimensionality. These codes can be induced codes \(\mathbb{F}_{q}^{l} \otimes C\), whose hull dimensionality is l times higher than that of the base code \(C\) (see Eq. (5)). If the complexity of the calculation of a signature is neglected in assuming the effective computation of the latter, then the Giraut protocol can be implemented via the Reed–Maller based code \(\mathbb{F}_{q}^{l} \otimes C\) (see Table 1), for which a cell value exceeds \(128\). Remembering that the communicative complexity (15) increases with rising \(N = ln\), it is essential to select the parameters of the induced code that provide the smallest \(ln\) among the permissible values. In the example considered in the previous subsection, a minimally permissible value \(ln\) is \(72 = 9 \cdot 8\).