Series: Quadrans Essentials Brings You Post-Quantum Cryptography (a Movie on Secrets Vs. Technology)
In the second article of the Series: Quadrans Essentials we will take you on an exciting journey from the origins of Cryptography all the way to the current state of Post-Quantum Cryptography.
First Thing First
Considering that Cryptography is by no means an easy topic, jumping straight to today’s latest developments and challenges might be extremely confusing.
In fact, it would be like starting to watch a movie from the final scene while skipping over all the twists and turns of the century-long history that brought us to the current state.
To understand where we are heading, it’s fundamental to know where we come from. Let’s do this with a short story about Cryptography.
We have selected a few movies to support our explanation along the way — so get your popcorn ready!
In our story, Alice and Bob need to communicate privately using Cryptography and Eve is the antagonist who wants to spy on them.
The Early Ages
Cryptography is the part of Mathematics that helps us keep information private. Securely exchanging military information is a millennia-old problem that even Egyptian pharaohs and the Roman Empire had to face — that’s why one of the first methods ever used was named after Cesar himself.
The thing is, the only methods available back then were rather elementary and simple; they didn’t even come with “passwords”. These systems were not that different from the ones children make up in school while playing, and are just as easy to break.
Note: Some people mistakenly use the word “Password” when the proper word to use is “Key”.
Later on, the methods that were invented became progressively sophisticated and secure as Mathematics started playing an increasingly important role in designing, testing, securing, proofing, and of course, breaking those codes.
Cryptographic algorithms began to have standards and encryption keys. Some of the most widely known certainly include those that scrambled the alphabet over and over again.
All of these algorithms had one thing in common: they were symmetric, i.e. the key required to unscramble the message was the same used to scramble it. As you can imagine, this was not very efficient.
The main problem with symmetric encryption is that in order to communicate securely, two parties must exchange keys before sending the first encrypted message to each other, and this is a huge limitation.
Here’s the example with Alice and Bob.
Alice and Bob must first meet in a safe place or use a secure channel (which they usually don’t have), verify each other’s identity, and agree on a key to use. Only after these necessary steps can they send secret messages to each other using the chosen key.
With symmetric encryption alone, secure communication over the Internet (such as we use on a daily basis) cannot happen. In fact, any server should first agree to use a specific key with every browser in the world that might connect to it…
Can those symmetric codes be cracked? Sure thing!
The dominant approach to solving them is called brute-forcing and consists of testing lots of random keys as fast as possible until readable content is found.
With this method, time is crucial: brute-forcing will always be successful in the long run, but it can take a gazillion years with complex Cryptography, so what then? The secret may be revealed too late when it is no longer useful and relevant.
Movie Hint #1: To get a better idea of the brute force race, check out the movie The Imitation Game which details the story of how Alan Turing built and used Colossus to crack the Enigma code used by the Germans during World War II.
In this scenario, our Alice and Bob would be German troops, while Eve Her Majesty’s most advanced piece of machinery. This historical event is so fascinating that many great movies have been made about it.
A way to look at this event, which will come in handy later, is this:
When the encryption was done using a (slow) mechanical instrument, the code was cracked using a (way faster) electronic device. The new technology was able to significantly reduce the time taken to overcome the difficulty of reversing the encryption, moving it from centuries to minutes.
Keep that in mind for later.
Going Public
A new form of Cryptography was invented over time: Public-Key Cryptography. This new approach is strongly based on Mathematics and involves the use of two keys: one to encrypt the message (the public key) and one to decrypt the message (the private key).
Returning to our example: now Alice can give Bob her public key out in the open, without worrying about being seen by Eve or anyone else. Why? Because the public key can only be used to encrypt a message intended for Alice, and she can share it over an “insecure” channel without concern since the only way to decrypt the message is via the private key that Alice cleverly keeps to herself.
In very simple words, this is how we can communicate securely over the Internet. In fact, any server can talk privately to any browser without them having to agree or exchange anything first.
The security lies in the fact that anyone with a public key can use it, but there is no way to guess, extract or compute the private key from the public key.
Or is there? Maybe someday? Maybe… with a Quantum computer?
Enter the Quantum Era
Quantum computers are computers that do not use regular chips or simple Boolean logic but are rather based on Quantum Physics.
How do Quantum computers work? Again, here we give you a super-short version: these computers do not use “bits” (the famous “zeros and ones”) but qubits, or quantum bits.
A qubit can be in a complex state or value called superposition: it could be both zero and one at the same time with different probabilities.
If you’ve ever heard of Shroedinger’s Cat Paradox — the cat in the box which is both dead and alive — that’s a qubit. If you haven’t heard of it, you need to catch up on The Big Bang Theory. All 10 seasons.
A common misconception is that “Quantum Computers are faster at brute-forcing,” or that “Quantum computers work by trying every possible combination at once.”
This is false and a dire way to explain Quantum computing that will ultimately lead to false conclusions.
If this were true, then Quantum computers would be faster than classical computers for every problem in the world, and that’s not the case!
Let’s just say that Quantum is a whole new way of doing Mathematics that could lead to huge shortcuts in finding solutions to specific problems.
But here’s the catch: it just happens that Quantum Computers take shortcuts in solving exactly the problems that modern public-key Cryptography is based on!
Here we potentially see history repeating itself. Remember Colossus cracking Enigma?
Quantum computers could potentially be to modern days public key encryption algorithms what Colossus was to Enigma — game over.
If Quantum computers could significantly reduce the time it takes to reverse modern public-key Cryptography… That would be Armageddon of secrets, privacy, secure communication, secure online shopping, not to mention the secrets of many states.
Movie Hint #2: To understand what the end of encryption and privacy could mean, take a look at the old-but-gold Sneakers.
Does this scare you? Well, then you realise the implications and consequences of this in the big picture. But don’t panic, we’re not there yet, although we will eventually.
Quantum computers today are very expensive, hard to engineer, even harder to manufacture, they are bigger than normal computers, more fragile, and they have to be built to solve a specific problem and run a specific algorithm (they are not general-purpose), and sometimes they even get the wrong results. But isn’t that always the case with the newest tech?
There are those who claim based on rumours and some questionable conspiracy theories that nations and advanced technology corporations may be hiding or lowering the true level of Quantum computing they have achieved to disguise their advantage and keep others in the dark.
Other rumours picture the attackers opting for another strategy, that is to record and keep the encrypted data that nowadays cannot be decoded yet, to decrypt them later with a Quantum computer — when they can get their hands on it.
This is the point where we finally get to…
Post-Quantum Cryptography
With Quantum Physics threatening modern Cryptography, new algorithms to protect our secrets must be built to deal with the Quantum threat. That’s what Post-Quantum Cryptography is for.
Post-Quantum Cryptography is defined as “classical Cryptography that withstands attacks from a large Quantum computer.”
Beware of the word classical here.
Classical Cryptography doesn’t use any Quantum properties and doesn’t need any specialised Quantum hardware as it is based on hard mathematical problems (like the Cryptography we have today) that are not vulnerable to Quantum computer attacks.
All computers are tools for doing calculations — since not all calculations are equal, some computers are better for some calculations than others.
Quantum computers are significantly better than today’s ordinary computers at solving some very specific sorts of problems but are simply useless at others.
For example, a Quantum computer has nothing to do with:
✔ Real-time control. Not having any ability for I/O of any sort, a Quantum computer has no capability for controlling real-time devices, such as process control for an industrial plant. Any real-time control would have to be made by a classical computer;
✔ Media playback or recording;
✔ Real-time media processing;
✔ Financial transactions — where balances must be maintained precisely to the penny. Financial applications of a more approximate and statistical nature (e.g., portfolio rebalancing and trade settlement allocation) are more appropriate for Quantum computing.
To avoid being vulnerable to Quantum computer attacks, Post Quantum Cryptography builds specific cryptographic algorithms to tackle those problems that Quantum computers themselves are weak at solving.
In late 2016, the National Institute for Standard and Technology (NIST) ran a competition for Post-Quantum Cryptography Standardisation to find new suitable Quantum resistant public key encryption algorithms to replace the existing ones.
Long story short, here’s what a good Post-Quantum encryption algorithm should do:
✔ Resist the attacks of Quantum computing;
✔ Resist the attacks of classical computing;
✔ Be fast as communication cannot be slowed down;
✔ Run on devices with limited computing resources such as browsers, network devices, smartphones, sensors, IoT devices, etc.
Post-Quantum Cryptography should not be confused with Quantum Cryptography. They are not the same thing, nor are they to be imagined as one being consequential to the other.
Quantum cryptography is Cryptography that uses Quantum computers with specialised equipment such as photon detectors, beam splitters, etc. to do encryption or key distribution.
While Post-Quantum encryption needs to work on your phone, Quantum Cryptography never will. They are different in terms of scope, purpose, role, and technology used.
Wrapping all up
Leveraging technology and Mathematics to unlock our deepest secrets… Cryptography is such a fascinating and challenging subject that it has yet to stop inspiring a long line of cinematic masterpieces.
Cryptography is key for countless applications we use on a daily basis to ensure security and privacy. In fact, our finances, money, nations, and freedom rely on it.
When one of the players in this arms race (Technology and Physics) unleashes a new weapon (the Quantum computer) that could disrupt the rules of the game and put everything at risk, another player (Mathematics) has to bridge the gap and come up with a new strategy, a new way of doing things, or even a new battleground to restore balance for the benefit of all.
That’s what Post-Quantum Cryptography does — it brings a new set of problems that the new challengers can’t solve, keeping the previous players (our browsers, banks, smartphones) in play. Isn’t that brilliant?
Today we use public-key Cryptography on a daily basis without even knowing it or realising it. In the years to come, the same thing will gradually happen with Post-Quantum.
It just makes us wonder what exciting new movies will come out then…
