Linear codes [19] are originally used for digital communication and are based on coding theory. Coding theory is an important study that attempts to minimize data loss due to errors introduced in transmission from noise, interference, or other forces. Data to be transmitted are encoded by the sender as linear codes which are decoded by the receiver. Data encoding is accomplished by adding additional information to each transmitted message, to enable the message to be decoded even if errors occur.
Different codes are being studied to provide solutions to various problems occurring in applications. The most prominent type of error-correcting code is called linear code. The linear codes can be represented by k x n matrices, where k is the length of the original messages, and n is the length of the encoded message. It is computationally difficult to decode messages without knowing the underlying linear code. This hardness underpins the security of the code-based cryptosystem, which includes all cryptosystems, symmetric or asymmetric, whose security relies, partially or totally, on the hardness of decoding in a linear error-correcting code, possibly chosen with some particular structure or in a specific family of linear codes.
Linear codes [70,71] are linear block codes over an alphabet 𝐴=𝐹𝑞�=��, where 𝐹𝑞�� denotes the finite field with 𝑞=𝑝𝑙�=�� elements 𝑙∈𝑁𝑥�∈��, p prime. The alphabet is often assumed to be binary, that is 𝑝=2�=2, 𝑙=1�=1, 𝑞=2�=2, 𝐹2={0,1}�2={0,1}. The encoding of the source bits is done in blocks of predefined length k, giving rise to the name “block code”.
The following are the matrices used in code-based cryptography.
A generator matrix G of an [𝑛,𝑘][�,�] code C is a 𝑘×𝑛�×� matrix G such that 𝐶={𝑥𝐺:𝑥∈𝐹𝑘2}�={��:�∈�2�}. Generator matrix is of the form (𝐼𝑘∣𝑄)(��∣�), where 𝐼𝑘�� is the (𝑘×𝑘)(�×�) identity matrix and Q is a 𝑘×(𝑛�×(�-𝑘)�) matrix (redundant part).
A parity-check matrix H of an [𝑛,𝑘][�,�] code C is an (𝑛(�−𝑘)×𝑛�)×� matrix H, such that 𝐶={𝑐:∈𝐹𝑛2:𝐻𝑐𝑇=0}�={�:∈�2�:���=0}.
Parity-check matrix H is generated from the generator matrix as 𝐻=(𝑄𝑇∣𝐼𝑛−𝑘)�=(��∣��−�).
Encoding process applies an injective 𝐹2�2–linear function 𝑓𝑐:𝐹𝑘2→𝐹𝑛2��:�2�→�2� on an input block of length k, i.e., every codeword can be generated by multiplying a source vector 𝑥∈𝐹𝑘2�∈�2� with 𝐺𝐶=𝑥·𝐺∣𝑥∈𝐹𝑘2≤𝐹𝑛2��=�·�∣�∈�2�≤�2�. Hence, the matrix G corresponds to a map 𝐹𝑘2→𝐹𝑛2�2�→�2� mapping a message of length k to an n-bit string. This encoding process corresponds to encryption in code-based cryptography.
The decoding process is about finding the closest codeword 𝑥∈𝐶�∈� to a given 𝑦∈𝐹𝑛2�∈�2�, assuming that there is a unique closest codeword. Decoding a generic binary code of length n and without knowing anything about its structure requires about 2(0.5+𝑜(1))×𝑛𝑙𝑜𝑔2(𝑛)2(0.5+�(1))×����2(�) binary operations, assuming a rate ≈1/2≈1/2. The following are the common decoding techniques [71]: