Code-based Cryptography and the McEliece Cryptosystem

McEliece Cryptosystem

McEliece Cryptosystem is an asymmetric encryption algorithm. It is the cryptosystem to uses randomization in the encryption algorithm. The algorithm is based on the hardness of decoding a usual linear code (NP-hard). The NP-hard problems are a class of problems that may or may not be Decision Problems but are at least as difficult to solve as the NP-complete problems.

The McEliece Cryptosεεystem is an easy special of decryption of an NP-hard problem using special class of codes. For this class of codes, polynomial-time algorithms exist. One such class is the basis of the McEliece Cryptosystem.

Suppose G is a generating matrix for a linear [n, k, d] Goppa code C, where n = 2^m, d = 2t + 1, and k = n − mt. Let S be a k × k matrix invertible over Z₂, P be an n × n permutation matrix and G’= SGP. Also, let P = (Z₂)^k, C = (Z₂)ⁿ, and K = {(G, S, P, G 0 )},

The matrix G’ is the public key and G, S, and P comprise the private key.

For a public key G’, a plaintext x ∈ (Z₂)^k is encrypted by calculating y = xG’ + e, where e ∈ (Z₂)ⁿ is a random error vector of weight t.

A Cipher-text y ∈ (Z₂)ⁿ can be decrypted using the following steps.

1. Start with computing y₁ = y^p-1 .
2. Decode y₁ using the equation, y₁ = x₁ + e₁, where x₁ ∈ C.
3. Now compute x₀ ∈ (Z₂)^k such that x₀G = x₁.
4. Calculate x = x₀^S-1.

This way the private key P equals

and the public generating matrix G’ equals

Try to understand the process using this example.

Suppose that Paema wants to encrypt the plain-text x= (1,1,0,1) using the vector e = (0, 0, 0, 0, 1, 0, 0) as the random error vector of weight 1. The cipher-text is calculated using the following equation.

When Aamir receives the ciphertext y, he start with computing:

Then he decodes y₁ to get x₁= (1, 0, 0, 0, 1, 1, 0). Note that e¹ is not equal to e. This is because of the multiplication by P^-1. However, P is a permutation matrix and therefore, it only changes the position of the error(s).

Now, Aamir can form x₀ = (1, 0, 0, 0). Finally, he calculates the following text to get the text Paema sent to him.

This is the same text Paema sent to him.

McEliece's Cryptosystem consists of three algorithms- a key generation algorithm, an encryption algorithm, and a decryption algorithm. All these algorithms find applications in different purposes. However, there is no practical application of code-based cryptography is known to us. This might partly be because the code-based cryptography is considered a trade-off between security and efficiency. The huge size of the public key is also taken as a reason behind.

Frequently Asked Questions

Define Confidentiality.

Confidentiality is the term used to describe the level of secrecy of data. If the data is highly-confidential, only the sender and receiver can access the message exchanged between them.

Why do we use Cipher?

Cipher is an algorithm used to transform plain text into cipher text by two methods- Substitution and Transposition.

What is RSA?

RSA is a public key algorithm used to manage keys for digital signatures. It calculates a modulus that is used as a key with recipient’s public key. 

Mention the principles of Cryptography.

The four principles of Cryptography include Data Confidentiality, Data Integrity, Authentication, and Non-repudiation.

Conclusion

Overall, we understood several modules of Code-based Cryptography and the McEliece Ecosystem.

We hope the above discussion helped you understand the concepts of Code-based Cryptography and the McEliece Ecosystem and can be used for future reference whenever needed. To learn more about Cryptography, you can refer to blogs on Security in Cryptography, Signing and Encrypting in Cryptography, Authenticated Encryption in Cryptography, CBC MAC in Cryptography, and Message Authentication Codes in Cryptography.

Recommended Readings:

• Difference between Public Key and Private Key
   

Visit our website to read more such blogs. Make sure you enroll in our courses, take mock tests, solve problems, and interview puzzles. Also, you can pay attention to interview stuff- interview experiences and an interview bundle for placement preparations. Do upvote our blog to help fellow ninjas grow.

Happy Coding!