Inverse matrices with applications in public-key cryptography

Abstract

The applications of non-square binary matrices span many domains including mathematics, error-correction coding, machine learning, data storage, navigation signals, and cryptography. In particular, they are employed in the McEliece and Niederreiter public-key cryptosystems. For the parity check matrix of these cryptosystems, a systematic non-square binary matrix $H$ with dimensions $m\times n$ , $n>m$ , $m=n-k$ , there exist $2^{m(n-m)}$ distinct inverse matrices. This article presents an algorithm to generate these matrices as well as a method to construct a random inverse matrix. Then it is extended to non-square matrices in arbitrary fields. This overcomes the limitations of the Moore-Penrose and Gauss-Jordan methods. The application to public-key cryptography is also discussed.

Introduction

Inverses of systematic binary matrices play a crucial role in many applications in digital communications, ¹ navigation systems, ² data storage, ³ and code-based cryptography. ⁴ These matrices can be constructed using the Gauss-Jordan (GJ) ⁵ and Moore-Penrose (MP)^6,7 methods. An invertible matrix must have full rank. A matrix with $m$ rows and $n$ columns, $n>m$ , has full rank if its rows are linearly independent. The GJ algorithm is widely used to solve linear systems of equations of the form $Ax=b$ ⁸ and can be used to construct inverses of non-square matrices. The MP method provides a unique inverse matrix that has applications in data analysis and machine learning. ⁹

Non-square binary matrices are important in several domains including error-correction coding and code-based cryptography. ^{10 11} In this article, a method is presented to construct all inverses of a binary matrix and an algorithm is given to provide a random inverse of a binary matrix. It is shown that this method is more efficient than the MP and GJ methods. Finite fields, also known as Galois fields (GFs), are fundamental mathematical structures with applications in various domains, including cryptography, signal processing, error correction, and data transmission. ^{12 13} In cryptography, finite fields play an important role, forming the basis of secure communication protocols and encryption algorithms. Elliptic curve cryptography ¹⁴ and the advanced encryption standard heavily rely on arithmetic operations in finite fields to ensure robust security.^15,16 Finite fields are also employed for Goppa codes, ¹⁷ generalized Reed-Solomon (GRS) codes,^17,18 and BCH codes. ¹⁹

Broumandnia ²⁰ employed matrix inversion in $GF(256)$ to enhance digital image encryption, improving both security and encryption speed. The algorithm proposed by Tiplea and Dragoi ²¹ for constructing inverses in finite fields depends on selecting an appropriate range transformation for each inverse. These algorithms simplify the construction of inverse matrices in various fields, including finite fields, real fields, and complex fields. Theyi divide the inverse matrix into two parts: one selected in a random base while the second, approximately half the size of the original matrix, is constructed. This significantly reduces the complexity of inverse matrix construction which is of great value when dealing with large matrices. In the analysis section, the limitations associated with GJ elimination when dealing with large-sized matrices ²² and the challenges posed by the MP method in the context of finite fields ²¹ will be discussed. The application of the proposed approach to public-key cryptography (PKC) is also considered.

Linear block codes

In communication systems, redundancy is employed to detect and correct errors caused by noisy channels. An encoder maps a message $\mathit{m}=(m_1,m_2,\dots ,m_k)$ to a codeword $\mathit{c}=(c_1,c_2,\dots ,c_n)$ , $n>k$ . A binary block code has $2^k$ distinct messages of length $k$ and thus $2^k$ codewords. A set of codewords is referred to as a $C(n,k)$ block code, where $n$ is the length of a codeword and $k$ is the dimension of the code. A code $C(n,k)$ is linear if its codewords form a vector subspace of dimension $k$ in the $n$ -dimensional vector space. Then a set of $k$ linearly independent codewords ${\mathit{g}}_1,{\mathit{g}}_2,\dots ,{\mathit{g}}_k$ forms a generator matrix $G$ . A generator matrix in systematic form can be expressed as follows

$$G_{k\times n}=(I_k|P_{k\times (n-k)})$$

(1)

where $I_k$ is the $k\times k$ identity matrix and $P$ is a $k\times (n-k)$ parity matrix so that

$$G=\left(\begin{array}{ccccccc}& |& p_{1,1}& p_{1,2}& p_{1,3}& \cdots & p_{1,(n-k)}\\ & |& p_{2,1}& p_{2,2}& p_{2,3}& \cdots & p_{2,(n-k)}\\ I_k& |& p_{3,1}& p_{3,2}& p_{3,3}& \cdots & p_{3,(n-k)}\\ & |& ⋮& ⋮& ⋮& & ⋮\\ & |& p_{k,1}& p_{k,2}& p_{k,3}& \cdots & p_{k,(n-k)}\end{array}\right)$$

The $(n-k)\times n$ parity check matrix $H$ satisfies the condition $G{H}^T=\mathbf{0}$ and is a basis for the dual space of the code $C_{n,k}$ . ¹¹ A parity check matrix in systematic form is given by

$$H_{(n-k)\times n}=(P_{(n-k)\times k}^T|I_{n-k})$$

(2)

where $P_{(n-k)\times k}^T$ is the transpose of $P_{k\times (n-k)}$ .

Non-square inverse matrix

The parity check matrix $H$ is a full-rank binary matrix with dimensions $m\times n$ , where $n>m$ and $m=n-k$ . Therefore, the inverse of the parity check matrix $H^{-1}$ has dimensions $n\times m$ and satisfies $H{H}^{-1}=I_m$

$$H{H}^{-1}=\left(\begin{array}{ccccc}{p}_{1,1}& p_{2,1}& p_{3,1}& \cdots & p_{n,1}\\ p_{1,2}& p_{2,2}& p_{3,2}& \cdots & p_{n,2}\\ p_{1,3}& p_{2,3}& p_{3,3}& \cdots & p_{n,3}\\ ⋮& ⋮& ⋮& & ⋮\\ p_{1,m}& p_{2,m}& p_{3,m}& \cdots & p_{n,m}\end{array}\right)\times \left(\begin{array}{ccccc}{a}_{1,1}& a_{1,2}& a_{1,3}& \cdots & a_{1,m}\\ a_{2,1}& a_{2,2}& a_{2,3}& \cdots & a_{2,m}\\ a_{3,1}& a_{3,2}& a_{3,3}& \cdots & a_{3,m}\\ ⋮& ⋮& ⋮& & ⋮\\ a_{n,1}& a_{n,2}& a_{n,3}& \cdots & a_{n,m}\end{array}\right)=I_m$$

(3)

This is a linear system with $m^2$ equations and $mn$ variables. Consequently, there are $2^{m(n-m)}$ solutions for $H^{-1}$ . It was shown by Esmaeili ²³ that the inverse parity check matrix $H^{-1}$ is not unique, and there are $2^{k\times m}$ possible matrices.

Inverse matrix construction method

The equation $H{H}^{-1}=I_m$ is a linear system with $m^2$ equations and $mn$ variables, resulting in $mk$ more variables than equations. This article introduces a method to reduce the number of variables, thereby creating a linear system with $m^2$ equations and variables. This approach enables the construction of all inverse matrices for the parity check matrix $H$ . The proposed method is based on the observation that $H^{-1}$ has $m$ columns, each of which can have $2^k$ values. This leads to a set of $2^k$ distinct vectors for each column in the matrix.

Let $Z_i$ be a set of $2^k$ column vectors of length $n$ , $1\le i\le m$ , such that the $i$ th column of $H^{-1}$ belongs to a set $Z_i$ comprising $2^k$ column vectors, as shown below

$$Z_i=\left\{\begin{array}{ccccc}{z}_{1,1}& z_{1,2}& z_{1,3}& \cdots & z_{1,2^k}\\ z_{2,1}& z_{2,2}& z_{2,3}& \cdots & z_{2,2^k}\\ ⋮& ⋮& ⋮& & ⋮\\ z_{k,1}& z_{k,2}& z_{k,3}& \cdots & z_{k,2^k}\\ ---& ---& ---& --& ---\\ z_{(k+1),1}& z_{(k+1),2}& z_{(k+1),3}& \cdots & z_{(k+1),2^k}\\ z_{(k+2),1}& z_{(k+2),2}& z_{(k+2),3}& \cdots & z_{(k+2),2^k}\\ ⋮& ⋮& ⋮& & ⋮\\ z_{n,1}& z_{n,2}& z_{n,3}& \cdots & z_{n,2^k}\end{array}\right\}$$

(4)

Hence, there are $2^k$ columns in each set. Now considering that there are $2^k$ possibilities for a $k$ -bit representation, the $Z_i$ are partitioned into two subsets, $Z_i^1$ and $Z_i^2$ . $Z_i^1$ encompasses rows $1$ to $k$ , while $Z_i^2$ includes rows $k+1$ to $n$ . The first subset, $Z_i^1$ , comprises all $2^k$ possible binary vectors of length $k$ , ranging from all zeros to all ones. By defining the values of subset $Z_i^2$ with dimensions $k\times m$ , this approach effectively reduces to $mk$ variables, resulting in a linearsystem with $m^2$ equations and variables. The subsets $Z_i^1$ and $Z_i^2$ can be represented as follows

$$Z_i^1=\left\{\begin{array}{ccccc}{z}_{1,1}& z_{1,2}& z_{1,3}& \cdots & z_{1,2^k}\\ z_{2,1}& z_{2,2}& z_{2,3}& \cdots & z_{2,2^k}\\ z_{3,1}& z_{3,2}& z_{3,3}& \cdots & z_{3,2^k}\\ ⋮& ⋮& ⋮& & ⋮\\ z_{k,1}& z_{k,2}& z_{k,3}& \cdots & z_{k,2^k}\end{array}\right\}$$

(5)

$$Z_i^2=\left\{\begin{array}{ccccc}{z}_{(k+1),1}& z_{(k+1),2}& z_{(k+1),3}& \cdots & z_{(k+1),2^k}\\ z_{(k+2),1}& z_{(k+2),2}& z_{(k+2),3}& \cdots & z_{(k+2),2^k}\\ z_{(k+3),1}& z_{(k+3),2}& z_{(k+3),3}& \cdots & z_{(k+3),2^k}\\ ⋮& ⋮& ⋮& & ⋮\\ z_{n,1}& z_{n,2}& z_{n,3}& \cdots & z_{n,2^k}\end{array}\right\}$$

(6)

The elements in $Z_i^2$ , $z_{(k+b),d}$ , $1\le b\le n-k$ and $1\le d\le 2^k$ , must satisfy

$$\left(\begin{array}{ccccc}{p}_{1,1}& \cdots & p_{k,1}& |& \\ p_{1,2}& \cdots & p_{k,2}& |& I_{n-k}\\ ⋮& \ddots & ⋮& |& \\ p_{1,(n-k)}& \cdots & p_{k,(n-k)}& |& \end{array}\right)\times \left(\begin{array}{c}{z}_{1,d}\\ z_{2,d}\\ ⋮\\ z_{k,d}\\ ---\\ z_{(k+1),d}\\ z_{(k+2),d}\\ ⋮\\ z_{n,d}\end{array}\right)=\left(\begin{array}{c}1\\ 0\\ ⋮\\ 0\end{array}\right)$$

(7)

Hence, when $b=1$

$$\begin{array}{rl}{z}_{(k+1),d}& =1+p_{1,1}{z}_{1,d}+p_{2,1}{z}_{2,d}+\cdots +p_{k,1}{z}_{k,d},\\ & 1\le d\le 2^k,\end{array}$$

and if $b\ne 1$

$$z_{(k+b),d}=p_{1,b}{z}_{1,d}+p_{2,b}{z}_{2,d}+\cdots +p_{k,b}{z}_{k,d},1\le d\le 2^k,$$

so that

$$\left(\begin{array}{ccccc}{p}_{1,1}& \cdots & p_{k,1}& |& \\ p_{1,2}& \cdots & p_{k,2}& |& I_{n-k}\\ ⋮& \ddots & ⋮& |& \\ p_{1,(n-k)}& \cdots & p_{k,(n-k)}& |& \end{array}\right)\times \left(\begin{array}{c}{z}_{1,d}\\ z_{2,d}\\ ⋮\\ z_{k,d}\\ ---\\ z_{(k+1),d}\\ z_{(k+2),d}\\ ⋮\\ z_{n,d}\end{array}\right)=\left(\begin{array}{c}0\\ 1\\ ⋮\\ 0\end{array}\right)$$

(8)

When $b=2$

$$\begin{array}{rl}{z}_{(k+2),d}& =1+p_{1,2}{z}_{1,d}+p_{2,2}{z}_{2,d}+\cdots +p_{k,2}{z}_{k,d},\\ & 1\le d\le 2^k,\end{array}$$

and if $b\ne 2$

$$z_{(k+b),d}=p_{1,b}{z}_{1,d}+p_{2,b}{z}_{2,d}+\cdots +p_{k,b}{z}_{k,d},1\le d\le 2^k.$$

Similarly, the columns of $Z_{n-k}$ must satisfy

$$\left(\begin{array}{ccccc}{p}_{1,1}& \cdots & p_{k,1}& |& \\ p_{1,2}& \cdots & p_{k,2}& |& I_{n-k}\\ ⋮& \ddots & ⋮& |& \\ p_{1,(n-k)}& \cdots & p_{k,(n-k)}& |& \end{array}\right)\times \left(\begin{array}{c}{z}_{1,d}\\ z_{2,d}\\ ⋮\\ z_{k,d}\\ ---\\ z_{(k+1),d}\\ z_{(k+2),d}\\ ⋮\\ z_{n,d}\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ ⋮\\ 1\end{array}\right)$$

(9)

so when $b=n-k$ the result is $1$ and when $b\ne n-k$ the result is $0$ . Thus, if $b=n-k$

$$z_{n,d}=1+p_{1,(n-k)}{z}_{1,d}+p_{2,(n-k)}{z}_{2,d}+\cdots +p_{k,(n-k)}{z}_{k,d}),$$

and if $b\ne n-k$

$$z_{(k+b),d}=p_{1,b}{z}_{1,d}+p_{2,b}{z}_{2,d}+\cdots +p_{k,b}{z}_{k,d},1\le d\le 2^k.$$

Example

Consider a code $C(n,k)$ with $k=3$ and $n=6$ having generator matrix

$$G=(I_k|P_{k\times (n-k)})=\left(\begin{array}{cccccc}1& 0& 0& 0& 1& 1\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 1& 1& 0& 1\end{array}\right)$$

and

$$H=(P^T|I_{n-k})=\left(\begin{array}{cccccc}0& 1& 1& 1& 0& 0\\ 1& 1& 0& 0& 1& 0\\ 1& 0& 1& 0& 0& 1\end{array}\right)$$

The sets of columns are $Z_1,Z_2$ , and $Z_3$ resulting in $2^{k\times (n-k)}=2^{3\times 3}=512$ possible matrices. The sets $Z_i^1$ and $Z_i^2$ can be expressed as

$$Z_i^1=\left\{\begin{array}{cccccccc}0& 1& 0& 1& 0& 1& 0& 1\\ 0& 0& 1& 1& 0& 0& 1& 1\\ 0& 0& 0& 0& 1& 1& 1& 1\end{array}\right\}$$

and

$$Z_i^2=\left\{\begin{array}{ccccc}{z}_{(k+1),1}& z_{(k+1),2}& z_{(k+1),3}& \cdots & z_{(k+1),8}\\ z_{(k+2),1}& z_{(k+2),2}& z_{(k+2),3}& \cdots & z_{(k+2),8}\\ z_{(k+3),1}& z_{(k+3),2}& z_{(k+3),3}& \cdots & z_{(k+3),8}\end{array}\right\}$$

Combining $Z_i^1$ and $Z_i^2$ gives

$$Z_i=\left\{\begin{array}{cccccccc}0& 1& 0& 1& 0& 1& 0& 1\\ 0& 0& 1& 1& 0& 0& 1& 1\\ 0& 0& 0& 0& 1& 1& 1& 1\\ --& --& --& --& --& --& --& --\\ z_{4,1}& z_{4,2}& z_{4,3}& z_{4,4}& z_{4,5}& z_{4,6}& z_{4,7}& z_{4,8}\\ z_{5,1}& z_{5,2}& z_{5,3}& z_{5,4}& z_{5,5}& z_{5,6}& z_{5,7}& z_{5,8}\\ z_{6,1}& z_{6,2}& z_{6,3}& z_{6,4}& z_{6,5}& z_{6,6}& z_{6,7}& z_{6,8}\end{array}\right\}$$

For $i=1$ , we have

$$\left(\begin{array}{cccccc}0& 1& 1& 1& 0& 0\\ 1& 1& 0& 0& 1& 0\\ 1& 0& 1& 0& 0& 1\end{array}\right)\times \left(\begin{array}{c}0\\ 0\\ 0\\ -\\ z_{4,1}\\ z_{5,1}\\ z_{6,1}\end{array}\right)=\left(\begin{array}{c}1\\ 0\\ 0\end{array}\right)$$

so

$$\begin{array}{rl}& z_{4,1}=1+(0)(0)+(1)(0)+(1)(0)=1\\ & z_{5,1}=(1)(0)+(1)(0)+(0)(0)=0\\ & z_{6,1}=(1)(0)+(0)(0)+(1)(0)=0\end{array}$$

The elements of $Z_1^2$ are

$$\begin{array}{rl}{z}_{4,d}& =1+p_{1,1}{z}_{1,d}+p_{2,1}{z}_{2,d}+p_{3,1}{z}_{3,d}\\ z_{5,d}& =p_{1,2}{z}_{1,d}+p_{2,2}{z}_{2,d}+p_{3,2}{z}_{3,d}\\ z_{6,d}& =p_{1,3}{z}_{1,d}+p_{2,3}{z}_{2,d}+p_{3,3}{z}_{3,d}\end{array}$$

so

$$Z_1=\left\{\begin{array}{cccccccc}0& 1& 0& 1& 0& 1& 0& 1\\ 0& 0& 1& 1& 0& 0& 1& 1\\ 0& 0& 0& 0& 1& 1& 1& 1\\ --& --& --& --& --& --& --& --\\ 1& 1& 0& 0& 0& 0& 1& 1\\ 0& 1& 1& 0& 0& 1& 1& 0\\ 0& 1& 0& 1& 1& 0& 1& 0\end{array}\right\}$$

The elements of $Z_2^2$ are

$$\begin{array}{rl}{z}_{4,d}& =p_{1,1}{z}_{1,d}+p_{2,1}{z}_{2,d}+p_{3,1}{z}_{3,d}\\ z_{5,d}& =1+p_{1,2}{z}_{1,d}+p_{2,2}{z}_{2,d}+p_{3,2}{z}_{3,d}\\ z_{6,d}& =p_{1,3}{z}_{1,d}+p_{2,3}{z}_{2,d}+p_{3,3}{z}_{3,d}\end{array}$$

so

$$Z_2=\left\{\begin{array}{cccccccc}0& 1& 0& 1& 0& 1& 0& 1\\ 0& 0& 1& 1& 0& 0& 1& 1\\ 0& 0& 0& 0& 1& 1& 1& 1\\ --& --& --& --& --& --& --& --\\ 0& 0& 1& 1& 1& 1& 0& 0\\ 1& 0& 0& 1& 1& 0& 0& 1\\ 0& 1& 0& 1& 1& 0& 1& 0\end{array}\right\}$$

The elements of $Z_3^2$ are

$$\begin{array}{rl}{z}_{4,d}& =p_{1,1}{z}_{1,d}+p_{2,1}{z}_{2,d}+p_{3,1}{z}_{3,d}\\ z_{5,d}& =p_{1,2}{z}_{1,d}+p_{2,2}{z}_{2,d}+p_{3,2}{z}_{3,d}\\ z_{6,d}& =1+p_{1,3}{z}_{1,d}+p_{2,3}{z}_{2,d}+p_{3,3}{z}_{3,d}\end{array}$$

so

$$Z_3=\left\{\begin{array}{cccccccc}0& 1& 0& 1& 0& 1& 0& 1\\ 0& 0& 1& 1& 0& 0& 1& 1\\ 0& 0& 0& 0& 1& 1& 1& 1\\ --& --& --& --& --& --& --& --\\ 0& 0& 1& 1& 1& 1& 0& 0\\ 0& 1& 1& 0& 0& 1& 1& 0\\ 1& 0& 1& 0& 0& 1& 0& 1\end{array}\right\}$$

Hence, to construct $2^{k\times (n-k)}=2^{3\times 3}=512$ inverses, we select a random column vector from each set, namely, $Z_1$ , $Z_2$ , and $Z_3$ . With $2^k=2^3=8$ possible choices for each set, resulting in a total of $8\times 8\times 8=512$ possible $H^{-1}$ .

Random inverse matrix construction

The inverse of a parity check matrix can be partitioned into two sections $A_1$ and $A_2$ , where $A_1$ comprises rows $1$ to $k$ and $A_2$ comprises rows $k+1$ to $n$ so that

$$H^{-1}=\left(\begin{array}{cccc}{a}_{1,1}& a_{1,2}& \cdots & a_{1,(n-k)}\\ a_{2,1}& a_{2,2}& \cdots & a_{2,(n-k)}\\ a_{3,1}& a_{3,2}& \cdots & a_{3,(n-k)}\\ ⋮& ⋮& & ⋮\\ a_{k,1}& a_{k,2}& \cdots & a_{k,(n-k)}\\ ---& ---& --& ---\\ a_{(k+1),1}& a_{(k+1),2}& \cdots & a_{(k+1),(n-k)}\\ a_{(k+2),1}& a_{(k+2),2}& \cdots & a_{(k+2),(n-k)}\\ a_{(k+3),1}& a_{(k+3),2}& \cdots & a_{(k+3),(n-k)}\\ ⋮& ⋮& & ⋮\\ a_{n,1}& a_{n,2}& \cdots & a_{n,(n-k)}\end{array}\right)=\left(\begin{array}{c}{A}_1\\ -\\ A_2\end{array}\right)$$

(10)

A random inverse of a parity check matrix can be obtained using the following steps.

1. Select a random matrix $A_1$ with dimensions $(n-k)\times k$ .

2. Construct the corresponding matrix $A_2$ with dimensions $(n-k)\times (n-k)$ .

If $n=20$ and $k=12$ , $A_1$ consists of $n-k=8$ randomly selected binary vectors with $k=12$ rows. One such matrix is

$$A_1=\left(\begin{array}{cccccccc}1& 1& 0& 1& 0& 1& 0& 1\\ 0& 0& 1& 1& 0& 1& 0& 0\\ 1& 0& 0& 0& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 0& 0\\ 1& 0& 1& 0& 0& 0& 1& 1\\ 1& 1& 1& 1& 1& 1& 0& 0\\ 0& 1& 0& 0& 0& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 0& 0\\ 0& 0& 1& 0& 1& 1& 0& 0\\ 1& 1& 0& 1& 0& 0& 0& 1\\ 0& 0& 1& 1& 1& 1& 0& 0\\ 0& 1& 0& 1& 1& 0& 1& 1\end{array}\right)$$

The corresponding elements of $A_2$ are

$$A_2=\left(\begin{array}{ccccc}{a}_{(k+1),1}& a_{(k+1),2}& a_{(k+1),3}& \cdots & a_{(k+1),(n-k)}\\ a_{(k+2),1}& a_{(k+2),2}& a_{(k+2),3}& \cdots & a_{(k+2),(n-k)}\\ a_{(k+3),1}& a_{(k+3),2}& a_{(k+3),3}& \cdots & a_{(k+3),(n-k)}\\ ⋮& ⋮& ⋮& & ⋮\\ a_{n,1}& a_{n,2}& a_{n,3}& \cdots & a_{n,(n-k)}\end{array}\right)$$

(11)

where

$$a_{(k+b),d}={\displaystyle \sum _{i=1}^k{p}_{ib}{a}_{id},(b\ne d)}$$

and

$$a_{(k+b),d}=1+{\displaystyle \sum _{i=1}^k{p}_{ib}{a}_{id},(b=d)}$$

In general, this can be expressed as

$$a_{(k+b),d}=2^{|b-d|}mod2+\sum _{i=1}^k{p}_{ib}{a}_{id}$$

(12)

For example, $a_{(k+1),1}$ in $A_2$ is given by

$$a_{(k+1),1}=1+p_{11}{a}_{11}+p_{21}{a}_{21}+\cdots +p_{k1}{a}_{k1}$$

Let $A_1$ be a $k\times (n-k)$ matrix consisting of $n-k$ column vectors, and $A_2$ be the $(n-k)\times (n-k)$ matrix with entries determined based on $A_1$ . If $B_1=P_{(n-k)\times k}^T$ and $B_2=I_{n-k}$ , then

$$H{H}^{-1}=\left(\begin{array}{c}{B}_1|B_2\end{array}\right)\times \left(\begin{array}{c}{A}_1\\ -\\ A_2\end{array}\right)=B_1{A}_1+B_2{A}_2=I_{n-k}$$

so

$$A_2=(B_2{)}^{-1}(B_1{A}_1+I_{n-k})$$

(13)

which gives

$$\begin{array}{rl}H{H}^{-1}& =\left(\begin{array}{c}{B}_1|B_2\end{array}\right)\times \left(\begin{array}{c}{A}_1\\ -\\ A_2\end{array}\right)=\left(B_1|B_2\right)\times \left(\frac{\begin{array}{c}{A}_1\end{array}}{B_1{A}_1+I_m}\right)\\ & =B_1{A}_1+B_2(B_1{A}_1+I_m)\\ & =B_1{A}_1+B_1{A}_1+I_m=I_m.\end{array}$$

Inverse matrix construction analysis

This section compares the computation time of the proposed algorithm for random inverse matrices with the MP method. Table 1 presents the computation time for several values of $n$ and $k$ . This shows that the proposed method has a lower time for all values.

Table 1.

Random inverse matrix computation time.

Matrix size	Moore-Penrose (MP) (ms)	Proposed (ms)
$n=500$ , $k=213$	$94$	$16$
$n=1568$ , $k=524$	$2172$	$594$
$n=2048$ , $k=768$	$5109$	$2368$
$n=2896$ , $k=1024$	$14,735$	$5211$

The computational complexity is now considered in terms of the number of arithmetic operations. To solve a system of $v$ equations with $v$ unknowns, the number of arithmetic operations needed to obtain the row echelon form (REF) with the GJ method is $v(v+1)/2$ divisions, $(2v^3+3v^2-5v)/6$ multiplications, and $(2v^3+3v^2-5v)/6$ additions/subtractions. ²⁴ Then, the reduced REF is constructed to solve the system of linear equations which doubles the number of operations which gives a total of $4/3v^3+3v^2-7/3v$ . Hence, for a parity check matrix $H$ with dimensions $(n-k)\times n$ , the GJ computational complexity to obtain the inverse is $4/3(n-k{)}^3+3(n-k{)}^2-7/3(n-k)$ (excluding the nullspace and vector set calculations). The MP algorithm requires $(n-k{)}^2(2n-1)$ arithmetic operations to obtain the full-rank matrix $H{H}^T$ and an additional $(n-k)(2n^2-2nk-n)$ operations to obtain $H^{-1}=H^T[H{H}^T{]}^{-1}$ (excluding determinant calculations). Thus, the computational complexity for the MP method is $(n-k{)}^2(4n-1)-n(n-k)$ . The proposed approach requires no arithmetic operations for constructing $A_1$ as it is determined through random selection. Constructing $A_2$ requires $(2k-1)(n-k{)}^2+(n-k)$ arithmetic operations. Table 2 presents the number of arithmetic operations required with the MP, GJ, and proposed algorithms for constructing a random inverse matrix. This shows that the proposed method has lower computational complexity.

Table 2.

Computational complexity for three algorithms.

GJ	MP	Proposed
$4/3(n-k{)}^3+3(n-k{)}^2-7/3(n-k)$	$(n-k{)}^2(4n-1)-n(n-k)$	$(2k-1)(n-k{)}^2+(n-k)$

Table 3.

Multiplication in $GF(2^4)$ with irreducible polynomial $x^4+x+1$ .

$\times$	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
2	0	2	4	6	8	A	C	E	3	1	7	5	B	9	F	D
3	0	3	6	5	C	F	A	9	B	8	D	E	7	4	1	2
4	0	4	8	C	3	7	B	F	6	2	E	A	5	1	D	9
5	0	5	A	F	7	2	D	8	E	B	4	1	9	C	3	6
6	0	6	C	A	B	D	7	1	5	3	9	F	E	8	2	4
7	0	7	E	9	F	8	1	6	D	A	3	4	2	5	C	B
8	0	8	3	B	6	E	5	D	C	4	F	7	A	2	9	1
9	0	9	1	8	2	B	3	A	4	D	5	C	6	F	7	E
A	0	A	7	D	E	4	9	3	F	5	8	2	1	B	6	C
B	0	B	5	E	A	1	F	4	7	C	2	9	D	6	8	3
C	0	C	B	7	5	9	E	2	A	6	1	D	F	3	4	8
D	0	D	9	4	1	C	8	5	2	F	B	6	3	E	A	7
E	0	E	F	1	D	3	2	C	9	7	6	8	4	A	B	5
F	0	F	D	2	9	6	4	B	1	E	C	3	8	7	5	A

The proposed algorithm simplifies the construction of inverse matrices and can construct all $2^{k\times m}$ inverses of a given non-square matrix in any field. In contrast, the MP method constructs pseudo-inverses, and as indicated by Tiplea and Dragoi, ²¹ it encounters challenges with finite fields. GJ elimination encounters difficulties with large matrices as noted by Xin and George. ²² The task of selecting row combinations using the GJ algorithm is known to be NP-hard, and the time complexity increases exponentially. ²²

Random inversion of non-systematic binary and finite fields matrix

Let $B$ a full rank non-square matrix with dimensions $m\times n$ , $m<n$ , such that

$$B_{m\times n}=\left(\begin{array}{cccccccc}{b}_1& B_1& b_2& B_2& \cdots & b_y& B_x& b_{y+1}\end{array}\right)$$

(14)

where $B_1,B_2,\dots ,B_x$ are matrices with $m$ rows and $n_1,n_2,\dots ,n_x$ columns, respectively, such that $n_1+n_2+\cdots +n_x=n-m$ , and $b_1,b_2,\dots ,b_{y+1}$ are column vectors with $m$ rows, $y+1=m$ .

The $B_i$ , $i=1,\dots ,x$ , and $b_j$ , $j=1,\dots ,y+1$ , can be a null matrix $B$ and null vector $b$ , respectively. A full-rank matrix $B$ must have $m$ linearly independent column vectors $b_j$ $(j=1,\dots ,y+1)$ . For example, the following matrix $B$ is a full rank matrix with rank $5$ where $B_1$ , $B_2$ , and $B_4$ are null matrices.

If $A$ is the inverse of $B$ , then $B_{m\times n}{A}_{n\times m}=I_{m\times m}$ with

$$A_{n\times m}=\left(\begin{array}{c}{a}_1\\ A_1\\ a_2\\ A_2\\ ⋮\\ a_y\\ A_x\\ a_{y+1}\end{array}\right)$$

(15)

where $A_1,A_2,\dots ,A_x$ , are matrices with $n_1$ , $n_2$ , $\dots$ , $n_x$ rows, respectively, such that $n_1+n_2+\cdots +n_x=n-m$ , $a_1,a_2,\dots ,a_{y+1}$ are the row vectors with $m$ columns, where $y+1=m$ .

Hence, $A$ is the inverse of $B$ so the product of $B$ and $A$ will result in the identity matrix

$$\begin{array}{r}BA=\left(\begin{array}{c}{b}_1{B}_1{b}_2{B}_2\cdots b_y{B}_x{b}_{y+1}\end{array}\right)\times \left(\begin{array}{c}{a}_1\\ A_1\\ a_2\\ A_2\\ ⋮\\ a_y\\ A_x\\ a_{y+1}\end{array}\right)=I_m\end{array}$$

(16)

$${\displaystyle \sum _{i=1}^x{B}_i{A}_i+{\displaystyle \sum _{j=1}^{y+1}{b}_j{a}_j=I_m}}$$

(17)

A random matrix $A$ can be generated by randomly selecting $A_1,A_2,\dots ,A_x$ and constructing the corresponding row variables $a_1,a_2,\dots ,a_{y+1}$ .

Define $A_a$ and $B_b$ as

$$(A_a{)}_{m\times m}=\left(\begin{array}{c}{a}_1\\ a_2\\ ⋮\\ a_{y+1}\end{array}\right),(B_b{)}_{m\times m}=\left(\begin{array}{cccc}{b}_1& b_2& \dots & b_{y+1}\end{array}\right)$$

(18)

Then

$$\begin{array}{rl}& {\displaystyle \sum _{i=1}^x{B}_i{A}_i+B_b{A}_a=I_m}\\ & B_b{A}_a=I_m+{\displaystyle \sum _{i=1}^x{B}_i{A}_i}\end{array}$$

(19)

$$A_a=(B_b{)}^{-1}(I_m+{\displaystyle \sum _{i=1}^x{B}_i{A}_i})$$

(20)

so the columns of $B_b$ are linearly independent, resulting in a determinant of $1$ . Therefore, $B_b$ is a nonsingular matrix. Consequently, by selecting random matrices $A_i$ , $A_a$ can be constructed as described. Note that for complex and real number inverse matrices, $A_a$ can be constructed using (20). For example, consider B with dimensions m = 5 and n = 9 such that Then $A_{9\times 5}$ is

$$A_{9\times 5}=\left(\begin{array}{c}{a}_1\\ a_2\\ a_3\\ A_3\\ a_4\\ a_5\end{array}\right)$$

where $A_3$ can be randomly selected as

$$A_3=\left(\begin{array}{ccccc}0& 1& 1& 0& 1\\ 1& 1& 0& 0& 0\\ 1& 0& 1& 1& 1\\ 0& 1& 1& 1& 0\end{array}\right)$$

Given matrices $B_3$ and $(B_b{)}_{m\times m}$ the inverse of $(B_b{)}_{m\times m}$ is

$$(B_b{)}^{-1}=\left(\begin{array}{ccccc}0& 1& 1& 0& 1\\ 1& 0& 0& 0& 1\\ 1& 0& 1& 1& 0\\ 1& 1& 0& 0& 0\\ 1& 1& 0& 0& 1\end{array}\right)$$

Therefore, $A_a$ can be constructed as

$$A_a=(B_b{)}^{-1}(I_5+B_3{A}_3)$$

where Having $A_3$ and $A_a$ , the inverse matrix $A$ can be constructed as where $B_{(5\times 9)}\times A_{(9\times 5)}=I_5$ .

Finite field random inverse

A finite field has a finite number of elements and is also known as a Galois field denoted $GF(p^r)$ where $p$ is a prime number and $r$ is a positive integer. In $GF(p^r)$ , the elements are polynomials of degree less than $r$ with coefficients in $GF(p)$ . Addition and multiplication of polynomials are performed modulo an irreducible polynomial of degree $r$ . Table 3 illustrates multiplication in the finite field $GF(2^4)$ with irreducible polynomial $x^4+x+1$ .

Consider $GF(2^4)$ with matrix $B$

$$=\left(\begin{array}{cccccc}{b}_1& B_1& b_2& b_3& B_3& b_4\end{array}\right)$$

so there is no $B_2$ and $B_1$ , $B_3$ , and $B_b$ are Therefore, $(B_b{)}^{-1}$ can be constructed as

$$(B_b{)}^{-1}=\left(\begin{array}{cccc}9& C& C& 7\\ B& 3& E& F\\ 1& 4& E& 9\\ 4& 1& 2& 1\end{array}\right)$$

Now by random selection of $A_1$ and $A_3$

$$A_1=\left(\begin{array}{cccc}5& 4& 5& 2\end{array}\right),A_3=\left(\begin{array}{cccc}F& 9& B& 9\\ 0& 9& D& 5\end{array}\right)$$

$A_a$ can be constructed as

$$A_a=(B_b{)}^{-1}(I_4+B_1{A}_1+B_3{A}_3)$$

$$A_a=\left(\begin{array}{cccc}9& C& C& 7\\ B& 3& E& F\\ 1& 4& E& 9\\ 4& 1& 2& 1\end{array}\right)\times (\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right)+\left(\begin{array}{cccc}5& 4& 5& 2\\ A& 8& A& 4\\ 5& 4& 5& 2\\ 8& F& 8& E\end{array}\right)+\left(\begin{array}{cccc}6& E& A& F\\ 2& 1& 3& D\\ 1& 7& F& 9\\ 5& 7& 8& 7\end{array}\right))$$

$$A_a=\left(\begin{array}{cccc}9& C& C& 7\\ B& 3& E& F\\ 1& 4& E& 9\\ 4& 1& 2& 1\end{array}\right)\times \left(\begin{array}{cccc}2& A& F& D\\ 8& 8& 9& 9\\ 4& 3& B& B\\ D& 8& 0& 8\end{array}\right)$$

and $A$ is then where $B_{(4\times 7)}\times A_{(7\times 4)}=I_4$ in $GF(2^4)$

$$\left(\begin{array}{ccccccc}2& 1& 3& 8& 5& A& 8\\ D& 2& E& C& 3& 1& 6\\ C& 1& 1& 4& 8& 6& F\\ E& 7& 0& 2& E& 0& C\end{array}\right)\times \left(\begin{array}{cccc}B& 5& 5& 9\\ 5& 4& 5& 2\\ 4& 9& 3& 7\\ 6& 9& 5& 3\\ F& 9& B& 9\\ 0& 9& D& 5\\ 5& 8& 5& 5\end{array}\right)=I_4$$

Prime field random inverse

In a prime field $GF(p)$ , the elements are the integers less than $p$ with addition and multiplication modulo $p$ . For example, in $GF(7)$ , the elements are $(0,1,2,3,4,5,6)$ , and arithmetic is done modulo $7$ so $3+5=1$ in $GF(7)$ as $3+5mod7=1$ .

From (16) to (19)

$${\displaystyle \sum _{i=1}^x{B}_i{A}_i+B_b{A}_a=I_m}$$

and modulo $p$

$$B_b{A}_a=I_m-{\displaystyle \sum _{i=1}^x(B_i{A}_i)modp}$$

(21)

$$A_a=(B_b{)}^{-1}(I_m-{\displaystyle \sum _{i=1}^x(B_i{A}_i)})modp.$$

(22)

Consider $GF(7)$ and the matrix $B$ given by

$$=\left(\begin{array}{ccccc}{B}_1& b_2& b_3& b_4& B_4\end{array}\right)$$

with Randomly selecting matrices $A_1$ and $A_4$ as

$$A_1=\left(\begin{array}{ccc}1& 6& 6\\ 1& 6& 2\end{array}\right),A_4=\left(\begin{array}{ccc}1& 6& 1\end{array}\right)$$

gives

$$A_a=(B_b{)}^{-1}(I_3-B_1{A}_1-B_4{A}_4)$$

which yields

$$A_a=\left(\begin{array}{ccc}2& 5& 3\\ 1& 0& 4\\ 0& 4& 6\end{array}\right)\times (\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right)-\left(\begin{array}{ccc}1& 6& 0\\ 3& 4& 3\\ 0& 0& 2\end{array}\right)-\left(\begin{array}{ccc}2& 5& 2\\ 6& 1& 6\\ 5& 2& 5\end{array}\right))$$

$$A_a=\left(\begin{array}{ccc}2& 5& 3\\ 1& 0& 4\\ 0& 4& 6\end{array}\right)\times \left(\begin{array}{ccc}-2& -11& -2\\ -9& -4& -9\\ -5& -2& -6\end{array}\right)mod(7)$$

$$A_a=\left(\begin{array}{ccc}2& 5& 3\\ 1& 0& 4\\ 0& 4& 6\end{array}\right)\times \left(\begin{array}{ccc}5& 3& 5\\ 5& 3& 5\\ 2& 5& 1\end{array}\right)$$

resulting in so $A$ can constructed as where $B_{(3\times 6)}\times A_{(6\times 3)}=I_3$ in $GF(7)$ .

PKC application

The proposed method for constructing random inverse matrices can be employed with the PKC by Haidary Makoui et al. ²⁵ This involves the generation of public and private keys for encryption, decryption, digital signatures, and verification.

Public Key Infrustructure

$(pk,pr)$ $\leftarrow$ $Gen(\lambda )$ generates a public key $pk$ and a private key $pr$ where $\lambda$ is the key generation scheme.

The proposed algorithm uses the following matrices 25 :

$\bullet$ Matrix $G$ of size $k\times n$ .

$\bullet$ Matrix $H$ of size $(n-k)\times n$ ,

$\bullet$ Non-singular scrambling matrix $S$ of size $k\times k$ .

$\bullet$ Permutation matrix $P$ of size $n\times n$ .

$\bullet$ Non-singular matrix $L$ of size $(n-k)\times (n-k)$ .

Key Generation Algorithm $Gen(\lambda )$

1. Obtain $G$ and $H$ for the block code $C(n,k)$ .

2. Select a random inverse of the parity check matrix using a randomly generated matrix $A_1$ and constructing the corresponding matrix $A_2$

$$H^{-1}=\left(\frac{A_1}{A_2}\right).$$

3. Conceal the generator matrix $G$ in a similar manner to the McEliece cryptosystem

$$p_1=G^{{}^{\prime }}=SGP.$$

4. Apply matrices $L$ and $P$ to conceal $H^{-1}$

$$p_2=L^{-1}(H^{-1}{)}^{T}P.$$

5. Digital signature verification requires

$$p_3=P^{-1}(H^{-1}H{)}^{T}P.$$

6. Construct a parity check matrix $H^{\prime }$ corresponding to $G^{{}^{\prime }}$

$$H^{\prime }=L^{T}H(P^{-1}{)}^T\text{ where }Q=H^{{}^{\prime }T}=P^{-1}{H}^{T}L.$$

7. Public key: $pk$ $\leftarrow$ $(p_1,p_2,p_3)$ .

8. Private key: $pr$ $\leftarrow$ $(S^{-1},P^{-1},G,Q)$ .

The public key $pk=(p_1,p_2,p_3)$ satisfies the following relationships. The algorithms for signing, verification, and integrity check in the code-based digital signature scheme have the following relationships. The public key $pk=(p_1,p_2,p_3)$ satisfies

$$(p_1)(p_3)=\mathbf{0},(p_2)(p_3)=p_2,(p_3)(p_3)=p_3$$

(23)

The public key $pk=(p_1,p_2,p_3)$ and $Q$ are related as follows

$$(p_1)(Q)=\mathbf{0},(p_2)(Q)=\mathit{I},(p_3)(Q)=Q$$

(24)

There are $2^{k\times (n-k)}$ possible inverse matrices so the probability of an adversary constructing a private key from the public key is $2^{-(k\times (n-k))}$ . ²⁵ Thus, the probability of successful forgery by discovering the secret key is negligible for reasonable values of $n$ and $k$ .

$$Pr[(Adv,\gamma )=1]<\frac{1}{2^{k\times (n-k)}}$$

PKC based on a dual inverse matrix uses a generalized non-square inverse matrix as in the code-based cryptosystem by Haidary Makoui et al. ²⁷ where the dual inverse matrix serves as both the transpose and inverse of the parity check matrix.

The probability of a ciphertext distinguishability attack against the McEliece code-based cryptosystem is $\left(\begin{array}{c}n-t\\ k\end{array}\right)/\left(\begin{array}{c}n\\ k\end{array}\right)$ . ²⁶ For the algorithm by Haidary Makoui et al. ²⁷ this is

$$\frac{1}{2^{k\times (n-k)}}<<\left(\begin{array}{c}n-t\\ k\end{array}\right)/\left(\begin{array}{c}n\\ k\end{array}\right).$$

Therefore, it provides greater security compared to the McEliece cryptosystem so smaller key sizes can be employed without compromising the security.

Conclusion

This article considered the construction of inverse matrices for a non-square matrix $H$ . The proposed approach involves column sets $Z_i$ with column $i$ of $H^{-1}$ corresponding to a subset of $Z_i$ . This facilitates the construction of all possible inverse matrices. An algorithm was given to construct an inverse matrix from matrices $A_1$ and $A_2$ , where $A_1$ has $n-k$ random binary vectors and $A_2$ is obtained based on $A_1$ . The computational complexity of the proposed approach was shown to be lower than the MP and GJ methods. The extension to arbitary fields including finite fields was demonstrated. Finally, the application to PKC was illustrated.

Footnotes

Declaration of conflicting interests

The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship and/or publication of this article.

ORCID iD

Farshid Haidary Makoui

Notes