McEliece post quantum cryptography

Question

Can someone explain me in basic simplistic english if possible how does McEliece asymmetric encryption works and why its quantum safe ? Thanks in advance.

Answer 1

How does the McEliece asymmetric encryption work?

The intuition is really quite simple here. Assume you have a message of $k$ bits. You then use a specific mathematical operation to create a larger intermediate value of $n$ bits with $n>k$ such that it is not immediately obvious what the original message was and such that you can recover up to $t$ bit-errors using a specific algorithm. You then actually introduce $t$ random bit errors into your message to get your ciphertext.

Decryption is essentially reversing the above knowing the special values used to "obfuscate" the original message and the algorithm to remove the errors.

The idea behind the security of this scheme is that you cannot be sure for every bit that you are seeing whether it has been changed or not and through the "obfuscation" a wrong guess will yield essentially unrelated values when trying to invert the "obfuscation".

why its quantum safe?

The entire reason is that we don't know how to (efficiently) break it if we had a quantum computer even though we have thought about this for more than 20 years.

Answer 2

Maybe not as basic and simplistic as @SEJPM's description, but here goes.

The ciphertext $c$ obtained by encoding the message using the public-key matrix $\hat{G}$ and by adding some random artificial noise to it, basically simulating a noisy channel (like in radio transmission, you always catch some cosmic noise):

$$c = \overbrace{m\hat{G} + e}^{\text{hard}} = m(SGP) + e = mS(GP)+e$$

Not knowing the secret inverse transformation (the secret key), the attacker faces a (presumably) hard problem, since $\hat{G}$ looks like a random code (if it is truly random, the problem is NP-hard -- this means it is very hard and can take exponential time to solve). You can think of this as a discrete version of the least-squares problem. Knowing the trapdoor, i.e., the secret invertible matrix $S$ and the secret permutation $P$, the instance can be transformed into an easy one:

$$cP^{-1} = ((mS)GP+e)P^{-1} = (mS)G + eP^{-1} = \underbrace{\hat{m}G + \hat{e}}_{\text{easy}}$$

This is easy under the circumstance that $G$ defines a code which is efficiently decodable, meaning that there exists piece of code that can correct the errors in reasonable time. Note that the permutation $P$ acts on the error $e$ only by swapping the elements around. So, for instance, $P:(0,1,0)\mapsto (1,0,0)$. It does not change the number of errors. Hence, the same number of errors can be added in the encryption as the code is able to correct.