Hello and welcome to this fundamentals of cryptography course, in this section, the course we're talking
about advanced cryptographic concepts.
In this video, we'll be discussing PUP post quantum cryptography.
And we'll have three main sections in this video.
We're going to start by talking about the need for post quantum cryptography, the why of this problem.
We'll then dive into a couple of the different approaches or types of post quantum cryptography before
we discuss, in the end, the applications of post quantum cryptography.
And so why do we need post quantum cryptography?
So when we talked about public key cryptography or asymmetric cryptography in an earlier section of
the course, we talked about how it's based off a mathematically hard problems, including the factoring
problem, the discrete logarithm problem and the elliptic curve discrete logarithm problem.
And when we discuss hardness in this concept, what we mean is that legitimate operations on these problems.
So, for example, multiplication, in the case of the factoring problem exponentiation and case of
the discrete logarithm problem and point multiplication, the case of the Liptak curb discrete logarithm
problem are relatively easy.
So polynomial complexity, however, the corresponding inverse operations factoring logarithms and division
of elliptic curve points are hard or exponential complexity.
And this imbalance between the complexities of the legitimate and the illegitimate operations is the
basis for the security post quantum cryptography.
If they had equal levels of complexity, it would be impossible to build a system that is both usable.
Letting users actually perform encryption and digital signatures with it and secure.
Meaning that there's no way for an attacker to take a public key and back calculate the corresponding
private key.
And so the problem with these traditional approaches to put to public key cryptography is that quantum
computers break the hardness of these problems.
Shor's algorithm is able to solve these problems in polynomial time, which destroys that imbalance
between legitimate users and attackers.
And so post quantum cryptography is designed to use different problems to create that imbalanced or
asymmetric relationship.
And so multiple different approaches exist for post quantum cryptography and all of them are designed
to use problems that are still considered hard to computers.
One approach is Latisse space cryptography.
And so these are using systems like learning with errors, ring learning with errors, et cetera, which
take advantage of the fact that if you know the latest that you're using, it's easy to perform certain
operations.
But if you're using points on that lattice with some level of error value, much harder to determine
that original lattice, there are multivariate ones which are based off of the difficulty of solving
systems, of multivariate equations.
There are hash based post quantum cryptography algorithms which are based off of the use of hash functions.
And so Shor's algorithm does not break traditional hash functions the same way that it breaks traditional
asymmetric cryptography.
There's a nother quantum algorithm that called Grovers algorithm that can potentially reduce the security
of symmetric crypto systems or potentially hash functions.
But all it requires is that you double the length of that secret key in a symmetric encryption system
to keep it secure or double the length of the hash function output to achieve the same level of security.
And so since this doesn't break the system, it just degrades its effectiveness.
It's possible to still build secure systems based off of it.
There are also code based on post quantum cryptographic systems which rely on error, correcting codes
for their security.
So quantum computers can't achieve that same level of complexity for these types of algorithms.
And then finally, we have a derivative of elliptic curve cryptography, which uses the properties of
super singular elliptic curves.
Not going to dive into the details here.
But this one is promising because these types of algorithms which are are secure against quantum computers,
could help replace traditional elliptic curve cryptographic algorithms, relatively simply.
We're already using elliptic curve cryptography for classical asymmetric cryptography.
And so switching to using super singular elliptic curves in a slightly different way allows us to achieve
security even if we make that switch to quantum computing.
And so these are just examples of problems that are still considered hard for quantum computers.
There's definitely the possibility that someone may create the equivalent of Shor's algorithm for any
of these, which would then break their security, break that asymmetric hardness and make them unusable.
However, many of these have received a lot of research and there are algorithms that are based off
of them that are believed to be secure against quantum computing.
And so why do we care about post quantum cryptography now, like at this point in time, we don't have
quantum computers that come anywhere close to using Shor's algorithm to break classical asymmetric cryptography.
Well, the reason why is that we have certain systems where long lifetimes exist and where the ability
to maintain security for decades may be necessary.
One example is SSL or TIA less.
So this is the protocol that we use to encrypt traffic on the Internet.
And so the Internet is an untrusted communications channel.
You have no idea where your traffic goes between point A to point B. And so it's entirely possible that
somewhere along that route could be collecting copies of everyone's network traffic and waiting till
quantum computers exist to crack the encryption on them and read the messages.
And so, depending on how sensitive that information is, this could be a real threat after quantum
computers become usable.
And so it may be necessary to implement post quantum cryptography on these systems as soon as possible
to protect them against attack in that quantum future.
Another potential application is block chain technology, so block chains are designed to be heavily,
heavily dependent on cryptographic algorithms like hash functions and public key cryptography.
And these systems are also designed to be extremely long lift.
What happens with block chain is every node in the network keeps a copy of the ledger containing all
of the data.
And so if one of those nodes gains access to a quantum computer at some point in time.
And can break the encryption on the ledger.
They can rewrite history.
And so blocking technologies over time will have to transition to post quantum cryptography in a way
that secure and ensures that someone cannot feasibly and effectively rewrite the history of the network
in their favor.
Once quantum computers become a reality.
A third example of systems that may require post quantum cryptography sooner rather than later are embedded
systems.
So if you have chips that are in devices that may live long, long past the.
Existence of usable quantum computers.
Then you have a case where maybe an update will not be possible in the future.
For example, if we talk about critical infrastructure like power, water, et cetera, these systems
typically have such high availability requirements that it's impossible to take them down to update,
upgrade, etc. in most contexts.
And so they're systems that are very, very old, still running.
And so the systems that are being built and put into use today may still be running when quantum computers
become a reality.
And if those quantum computers are able to break the protocols that these systems rely upon, maybe
digital signatures, et cetera, then they could pose a potential threat to critical infrastructure.
So anything like that where you fully expect a particular system to be in service for decades, then
post quantum cryptography may be necessary if those systems rely on public key cryptography.
And so, just as a brief recap, we need post quantum cryptography because we cannot trust public key
cryptography.
The classical algorithms indefinitely, the hard problems we're using today will be broken as soon as
we have a quantum computer that has enough cubits to run the algorithm for large enough keys.
The out Shor's algorithm, which breaks these problems already exists.
It's just waiting for technology to catch up.
And so in order to protect against this, we have post quantum cryptographic algorithms which are based
off of new problems that are still hard for quantum computers to solve.
And these algorithms will need to be in widespread use before quantum computers reached the point of
usability.
However, in some cases this why this use might need to appear sooner rather than later in systems that
have data that may need to be protected.
Beyond the advent of usable quantum computing, if you've gotten better at systems or something that
may not be switched out at before that point, then they need to be changed over as soon as possible
rather than waiting until quantum computers become an imminent threat.
And so ends our discussion of post quantum cryptography.
Thank you.