The McEliece algorithm enjoys simplicity as a post-quantum solution

In 2017, the National Institute of Standards and Technology (NIST) began running a competition to select the best quantum-resistant algorithmic standard. While several finalists employ lattice-based cryptography, these types of algorithms may yet be susceptible to quantum computing.

As Delaram Kahrobaei, a professor of cybersecurity at the University of York, in England, notes “We say that quantum algorithms cannot break them yet, but tomorrow someone comes up with another quantum algorithm that might break them.”

In contrast, code-based algorithms involve including adding a data error. to the code. the code can be decrypted once the error is corrected. Like a classic code, the error can be rather simple to solve (as if deciphering a word by shifting how alphabetic letters are represented).

This is how a promising code-based algorithm named Classic McEliece operates. It’s the only non-lattice based NIST encryption finalist.

And by simply adding random errors to each piece of encoded information, McEliece makes it theoretically impossible to break the code without a key.

Created in the late 1970s, cybersecurity experts have yet to find a vulnerability in the Classic MeEliece system. And many of them suspect that NIST will select the MeEliece algorithm as a top finalist.

Although quantum-resistant, the McEliece algorithm requires slightly more time to encrypt and decrypt information. Nonetheless, McEliece’s proponents are optimistic about its future use and prospects.

As a public-key cryptosystem, the MiEliece algorithm requires different keys for encryption and decryption The mathematical relationship between these keys determines the strength of the encryption.

Fortunately, public encryption eliminates the need to share keys prior to two individuals attempting to communicate with each other (unlike symmetric encryption).

For public-key encryption, the McEliece cryptosystem uses linear and error-correcting codes.

Error-correcting codes ensure that the McEliece cryptosystem data so as to prevent data loss. However, repeating data also makes the message (and data transfer time) much longer. Consequently, coders must balance the need for data repetition with code size.

At the basic level, Linear code is merely a linear combination of codewords that also serves as a codeword. Here, it is being used for error detection.

In this case, the size of the code (N), the size of the message (K), and the maximum number of errors that can be corrected (T) can be used for this purpose.

Hence,

t ≤ | n-k / 2 |

When using linear code, a generator polynomial P(x) can be used to systematically encode your coding. Evaluating this polynomial at different points will form a sort of curve, which can then be approximated using a decoding algorithm).

This polynomial will be represented by a generator matrix- one in which its rows span the entire code.

The main idea is that linear code helps to fortify encryption by deliberately adding random errors to the encoded information. However, this coding merely produces a systematic cryptosystem.

Developing a public key or asymmetric cryptosystem requires randomizing the generator matrix (mentioned above) by multiplying it with a random permutation matrix and a random non-singular matrix.

By doing so, the creator of the public key can then decode the message encrypted by the public key.

if Alice wants to send a message to Bob, Bob must first create a randomized generator matrix by choosing a linear code with specific values for K and P (above). Bob must then multiply the generator matrix for that code by a non-singular matrix and a permutation matrix.

Alice can then encode her message by multiplying it with this randomized generator matrix. She then adds a random error into this message to form the code word. This code word can be sent over an unsecured channel

Bob can then he decrypt the message by first multiplying it by the inverse of the permutation matrix then decoding the message according to his linear code. He then multiplies the decoded message by the inverse of the non-singular matrix as well.