Cyber threats and fraud are rising daily to steal public data. Cryptography encrypts information, text messages, and emails using a Cipher algorithm. It ensures authentication and security against these threats and protects them. It is an essential part of Network Security. With an increase in technology involvement, the applications of Cryptography have increased to another level.

In this blog, we will understand the concepts of Post-Quantum Cryptography: Code-based Cryptography and McEliece Cryptosystem. We will also learn in brief about Cryptography and Lattice in Cryptography.

Code-based Cryptography

Code-based Cryptography uses binary Goppa codes to develop a code-based public key cryptosystem. It consists of cryptosystems in which the algorithmic primitive use an error-correcting code C. The error-correcting code C is selected in such a way that it can correct t errors. The private key is a random binary irreducible Goppa code. The public key is a random generator matrix of a randomly permuted version of that code. The cipher-text used here is a codeward to which some errors have been added. These errors can only be accessed by the owner of private key.

There are two types of cryptosystems based on Code-Based Cryptography. These are McEliece Cryptosystem and Niederreiter Cryptosystem. In this article, we will mainly put our eyes on the McEliece Cryptosystem and its concepts.

Features of Code-Based Cryptography

Code-Based Cryptography has several strong features.

Tight Security Reductions

Very fast

Low-complexity encryption and decryption

Easy to understand and implement

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

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_{2}, P be an n × n permutation matrix and G’= SGP. Also, let P = (Z_{2})^{k}, C = (Z_{2})^{n}, 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_{2})^{k} is encrypted by calculating y = xG’ + e, where e ∈ (Z_{2})^{n} is a random error vector of weight t.

A Cipher-text y ∈ (Z_{2})^{n}^{ }can be decrypted using the following steps.

Start with computing y_{1 }= y^{p-1} .

Decode y_{1} using the equation, y_{1} = x_{1} + e_{1}, where x_{1} ∈ C.

Now compute x_{0} ∈ (Z_{2})^{k} such that x_{0}G = x_{1}.

Calculate x = x_{0}^{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_{1 }to get x_{1}= (1, 0, 0, 0, 1, 1, 0). Note that e^{1} 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_{0} = (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.

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.