Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Code-based Cryptography
2.1.
Features of Code-Based Cryptography
3.
McEliece Cryptosystem
4.
Frequently Asked Questions
4.1.
Define Confidentiality.
4.2.
Why do we use Cipher?
4.3.
What is RSA?
4.4.
Mention the principles of Cryptography.
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Code-based Cryptography and the McEliece Cryptosystem

Author Rupal Saluja
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

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.

notion of cryptography

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.

code-based cryptography

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.

  1. Tight Security Reductions
  2. Very fast
  3. Low-complexity encryption and decryption
  4. 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 = 2m, d = 2t + 1, and k = n − mt. Let S be a k × k matrix invertible over Z2P be an n × n permutation matrix and G’= SGP. Also, let P = (Z2)k, C = (Z2)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 ∈ (Z2)k is encrypted by calculating y = xG’ + e, where e ∈ (Z2)n is a random error vector of weight t.

A Cipher-text y ∈ (Z2)n can be decrypted using the following steps.

  1. Start with computing y= yp-1 .
  2. Decode y1 using the equation, y1 = x1 + e1, where x1 ∈ C.
  3. Now compute x0 ∈ (Z2)k such that x0G = x1.
  4. Calculate x = x0S-1.

 

This way the private key P equals

Sample example

and the public generating matrix G’ equals

Sample example

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.

Sample example

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

Sample example

Then he decodes yto get x1= (1, 0, 0, 0, 1, 1, 0). Note that e1 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 x0 = (1, 0, 0, 0). Finally, he calculates the following text to get the text Paema sent to him.

Sample example

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 CryptographySigning and Encrypting in CryptographyAuthenticated Encryption in CryptographyCBC MAC in Cryptography, and Message Authentication Codes in Cryptography.

Recommended Readings:

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!

Previous article
Learning with the Errors- Lattice in Cryptography
Next article
What are Multivariate Cryptography
Live masterclass