A friendly introduction to code-based cryptography
This is the script of the presentation I gave for the Math For All Satellite Conference Clemson 2024. The presentation is aimed at an undergraduate and novice level. No hard math included.
Once upon a time, there were two very good friends Alice and Bob who were avid treasure hunters.
Alice, the explorer keeps her discoveries in a notebook. Bob, the researcher, studies Alice’s discoveries
in his library in town.
Alice goes to various places like rainforests and caves. Her notebooks get wet sometimes and the ink fades.
Here is an excerpt of Alice’s description of a mysterious object.
For each object, she will only keep those four features. She also always uses checkmarks and crosses.
When two legs of a cross fade,…what happens? It becomes a checkmark! Also, when a check mark
gets mixed because of the rain, it may look like a cross or … a dot…
Let’s introduce the concept of repetition code to Alice.
With this technique, she can recover the original symbol when some of the symbols fade or get errors.
To retrieve the information, she will do a majority vote, and most of the time, it leads to the original
symbol!
So now you have the simplest example of a code. This code works and can save Alice tons of trouble.
But, it is not efficient and may not be interesting to use in real-world situations. Coding theory is the
branch of math that studies different codes.
Let’s go back to Alice and Bob again! Each week Alice sends her discovery to Bob via mail. But,…
Eve works at the post office and she is interested in Bob’s life. After all, Bob is famous.
Let us help Alice and Bob set up a secure communication protocol! Turns out, we can also use codes
to hide messages.
We are going to teach them how to use the McEliece cryptosystem.
To show that, we are going to introduce a new code! Instead of using check marks and crosses, let No
be 0 and Yes be 1. Why? Because we can perform arithmetic on numbers, not on symbols.
The message (✓, ×, ✓, ×) will be denoted as
1 0 1 0. We will be working modulo 2, that is
1 + 1 = 0. Let’s define the linear code C.
The matrix G is called the generator matrix of C.
This code is called the Hamming[7, 4] code. It can correct up to 1 error and the first 4 symbols are identical to the original message. That is if we change a 0 into a 1 or a 1 into a 0 one time, we can recover
the codeword. Can we use it to send the message to Bob via mail though? No way, Eve will just read
the message in the first 4 symbols. Let’s then disguise it and introduce two matrices S and P.
We would tell Bob to keep those 3 matrices secret and give any of his correspondence the matrix
That way, all of his correspondence will be hidden from Eve!
How then Alice send a message? Since she is ready to write a letter. we’ll assume she’s home and can do small matrix multiplication.
To send her message (1, 0, 1, 0), Alice compute
and flips one of the numbers. Let’s say she sends
If Eve wants to see the message, she can still open the letter and do some computations. But Bob
has too many letters and Eve has a lot of work to do! Since Eve sees that decrypting Bob’s message is
not worth her time, the communication is now safer!
Upon receiving the letter, Bob will compute
This is now a corrupted codeword of C. Bob knows there will only be one error. He can check that the correct codeword is
Therefore he decodes it to
by reading the first 4 digits. But this is not the correct message yet since he multiplied G with S. He now computes
which is indeed the correct message sent by Alice.
Here is a concise presentation of the McEliece cryptosystem.
Now you know how to use codes to do encryption! If you are interested in learning more, you can
check the following references.
Mary Wootters Coding Theory Playlist. (I am consuming this right now)
Thank you!
