Your extensive posting history on r/birdswitharms and your old fanfiction-heavy livejournal
are both one tiny math problem away from becoming public knowledge.
That math problem is prime number factoring, and the new era of quantum computers may lay
bare your indiscretions, as well as collapse the entire digital economy.
Unless we get us some post-quantum cryptography post-haste.
So, how close are we?
It’s said that quantum computers will threaten the security of our digital civilization because
they can easily overcome the encryption method that underpins almost all of it.
Every email, every online purchase, every login—is secured by the fact that it’s
a lot harder to factor out prime numbers than it is to multiply them together.
Large products of prime numbers become encryption locks, and the prime numbers that go into them
become the keys to the secrets in your inbox.
Your secrets are safe-ish for now because the most powerful classical computers will
take thousands to billions of years to find those factors, depending on the key size.
But in 1994, a mathematician named Peter Shor developed an algorithm - Shor’s algorithm
- that could use a quantum computer to factor a prime number in, well, a human lifetime,
or a human lunchbreak.
Quantum computers did not exist in 1994, but just last year, Google’s quantum computer,
Sycamore, outsped the best classical computers
for a very specific task.
According to the researchers, Sycamore performed calculations to simulate another quantum system
exponentially faster than would have been possible with a pure classical computer.
We’ll talk about exactly what happened here in another episode - but what does this mean
for internet cryptography?
Is it game over?
Not quite - quantum computers need to become far more reliable - have better “fault tolerance”
and/or support vastly more quibits
to do the sort of prime factoring required for decryption.
But those computers will eventually arrive.
So what’s to be done?
One option is to match quantum decryption with new quantum encryption techniques to
replace prime factoring.
We talked about all this in our episode on quantum key distribution - and we’ve also
talked about the challenges.
To distribute a quantum key, you also need a quantum internet to transport quantum states.
This is a far more challenging problem.
Quantum states are insanely fragile and difficult to transport, and the quantum internet may
not arrive before better quantum computers can crack current encryption techniques and
collapse the modern digital world.
Fortunately there is another option - and one that’ll be a lot cheaper than building
a quantum internet.
It turns out there are some ingenious non-quantum ways to thwart the hacking powers of quantum
computers.
Enter post-quantum cryptography, or quantum resistant algorithms - which might replace
our vulnerable prime factoring-based cryptography.
To understand why some algorithms are vulnerable to quantum computing attacks while others
are thought to be quantum resistant, we need to review a bit about bit about encryption.
Prime factoring is an example of what we call a one-way function.
That’s a mathematical operation that’s very easy to figure out in one direction,
but very difficult to reverse.
Let’s start with a more visual example.
Let’s say Alice has a secret shade of yellow, Bob has a secret shade of blue, and there’s
a shade of red that is publicly broadcast.
That’s the public key.
Alice combines her yellow with a public shade of red, which gives her an orange.
Bob combines his blue with red to get a purple.
Alice sends her orange to Bob, and Bob sends his purple to Alice.
Then, Alice combines Bob’s purple with her yellow and Bob combines Alice’s orange with
his blue.
The resulting brown is a shared secret that can be used to encode text between them.
Unless an eavesdropper - Eve - can unmix Alice or Bob’s colors, she can’t figure out
what their shared secret key is.
The current dominant encryption protocol uses prime factors instead of colours, and this
is the RSA protocol after Ron Rivest, Adi Shamir, and Leonard Adleman who came up with
it in 1977.
It works great except for its vulnerability to Shor’s algorithm and quantum computers.
But prime factoring is only one example of a one-way function.
Are there other possibilities that don’t have the same vulnerability?
To understand that, we need a brief word on how quantum computers do their magic.
If you try prime factorization using a classical computer you’re stuck using an algorithm
similar to one that was developed over 2,000 years ago by the Greek mathematician Eratosthenes.
First, divide a number by 2 and see if you get an integer.
If not try 3, 5, 7, 11, 13, and so on.
This is laborious—it takes an insane amount of time to factor large numbers this way.
Or you could run an insane number of computers in parallel to each check every different
factor.
Still effectively impossible
Shor’s algorithm is potentially exponentially faster.
For the full explanation, I’m going to point you to the episodes made by Infinite Series
a while back.
Today we’ll just do the quick version.
It turns out there’s a structure to factorization that can be exploited by quantum computers.
That structure is a period.
For example, let’s consider powers of 2—2, 4, 8, 16, 32, 64, 128, 256, 1024.
If we divide these powers by 5 and look at the remainder (an operation called “mod”)
we get 2, 4, 3, 1, 2, 4, 3, 1, 2, 4, 3, 1—it repeats every four numbers.
It turns out that if you can figure out the period of this sequence you can figure out
the original number - in this case the 2.
The 18th century mathematician Leonhard Euler figured this structure extends to numbers
that are the multiple of two prime numbers — just like our RSA numbers.
That doesn’t help us immediately - for the powers of large numbers, guessing the period
is as hard as guessing the factors.
It would take at least as long, or require at least as many parallel classical computers.
This is where quantum weirdness comes in.
Classical computers store information in bits that are either 0 or 1.
Quantum computers store information in qubits, which, until they give an output, are in a
quantum superposition of 0 and 1, with some probability of either being measured when
you try to read out the qubit.
So a set of qubits can be in any one of a large number of possible states, and each
state represents a different number, each with a different probability.
You can think of each state as being like a parallel processor - but now instead of
processing across different computers, you’re processing in different parts of the quantum
wavefunction - or in different parallel realities if you’re into the Many Worlds interpretation
of quantum mechanics.
The problem with this parallel processing is that you only get one answer when you try
to read out the qubits.
If you tried to use a quantum computer to guess the factors of a prime number, you’d
read out one of the guesses but it’s no more likely to be the correct one than if
you used a classical computer.
But it turns out there’s a way to boost the chances of getting the right answer.
Instead of trying to hold possible prime factors in our quibits, our array of qubits holds
these repeating moduli of Shor’s algorithm - one per quantum state in the superposition.
But now the entire superposition - all elements of the wavefunction are related by the period
of their repetition.
And now it’s possible to perform an operation that suppresses all possible periods besides
besides the correct one - essentially, you cause those incorrect parts of the wavefunction to destructively
interfere, leaving the correct period boosted.
Once you read out that period you can determine the prime factors.
So far, quantum computers are stuck under 100 qubits and none have managed to factor
a number higher than 21 with Shor’s algorithm.
Which, honestly, I can do in my head.
Does that mean I’m a quantum computer?
There are some who might say so - I reserve my opinion.
At any rate, although current technology isn’t there yet, when we figure out how to build
quantum computers with thousands of qubits even the very high digit RSA keys will not be
safe.
So how do we fix this problem?
The answer is to find one-way functions that don’t have a known exploitable quality like
the periodicity of prime factoring.
That’s the goal of a competition currently being run by NIST, the National Institute
for Standards and Technology.
Algorithm applicants have been whittled down from a field of nearly 70 to only 7 finalists
and a couple alternates, which were announced in June.
In 2022, NIST is expected to narrow it down to one or two quantum resistant algorithms.
These will become the new standards for public key encryption and digital signatures—and
they’ll hopefully be able to protect our data from quantum computing attacks.
One of the NIST finalists achieves that through the McEliece cryptosystem, which gets its
name from cryptographer Robert McEliece, who developed the hard math problem back in the
1970s.
The principle behind McEliece is that it’s really difficult to repair errors in large
messages.
That gives us the potential for a one-way function.
Here's a very basic example of error decoding.
Suppose Alice wants to send a message to Bob—”CAT” which is represented by the binary string
1 1 0 1.
Once in a while, Alice sends the code, but a bit flips and she sends 1 0 0 1, which means
DOG.
Bob knows Alice doesn’t have a dog, so he’s pretty sure there’s been an error.
What can he do?
Well, Bob can cross-reference his received message.
He can add an error to each of the codewords.
We’re working in binary, so 1+1=0.
An error of 0100 to CAT (1101) equals DOG (1001), which is the message Bob got.
So Bob can decode his message and know Alice’s true intent.
But decoding errors becomes much, much harder as the codeword size increases—unless you
know some things about the codeword ahead of time.
In the McEliece cryptosystem, the key is to modify the message in a reversible way to
create a very large codeword - then add errors to that codeword.
Unless you know how that modification was done in the first place, it’s essentially impossible to remove the
added errors.
McEliece does this by coding messages into large matrices.
You have a big array of numbers - a matrix - and you scramble it using key matrices and
code your message into the result.
Then you add some errors.
If someone knows the keys - the matrices used to do that scramble in the first place, they can pretty easily eliminate
the errors - find a message that makes sense.
But without those keys it’s near impossible to decode the errors from this gigantic matrix,
and the presence of the errors makes it impossible to brute force the one-way function in the
backwards direction.
McEliece avoids the periodicity that makes RSA vulnerable to Shor’s algorithm.
Computing in parallel universes just isn’t helpful here.
But there’s a reason we haven’t been using McEliece: the public key - this giant matrix
- is, well, giant.
RSA uses public keys on the order of a kilobyte.
To be secure against quantum attacks for the foreseeable future, McEliece would need an
8 Mb public key—8,000 times larger.
Right now, network protocols aren’t built for this and it could cause dramatic slowdowns
in transactions.
This is problem is shared by at least three of the other public key encryption finalists—NTRU,
CRYSTALS-KYBER, and SABER, which are lattice-based cryptosystems.
Lattice-based cryptosystems rely on the difficulty of problems like the shortest vector problem.
Suppose you have an enormous field dotted regularly with points.
Imagine that you’re forming giant parallelepipeds to cover the whole space.
This is the lattice.
But here’s a question: What is the shortest vector, or distance from one point to another
point?
So far there’s no known classical or quantum algorithm that solves it quickly for large
lattices.
Unfortunately, those large lattices are also why the lattice candidates also have large
public keys.
Perhaps a bigger issue than the size of public keys is the question is whether these algorithms
are really robust against quantum and classical attacks.
Well, one important factor in this question is the age of the alorgithm.
The line of thought is basically this: the longer a cryptosystem has been around, the
longer someone has had to break it.
Since they haven’t, age is a good sign.
People have more confidence in a 40 year old system like the McEliece than more recent lattice-based
systems.
So will post-quantum cryptography save digital civilization?
It’s hard to say.
It’s true that these quantum resistant algorithms seem like they will be hard, if not impossible
for quantum computers to crack, but that doesn’t mean no one will come up with a way to do
it.
In fact, there’s no guarantee a classical computer won’t come up with a fast algorithm
to solve them.
Mathematicians and cryptographers have decades of security to point to as proof of their
encrypting and decrypting abilities.
But at the end of the day, quantum key distribution proponents would rather put their faith in
fundamental laws of physics - pretty darn secure if only we had a quantum internet.
In the meantime, post-quantum crypto may be our only hope as black hat quantum hackers
attempt to decrypt your embarrassing emails across the parallel quantum space time.
Last week we talked about a highly speculative idea - lifeforms inside stars, formed from
cosmic strings and magnetic monopoles.
Zoltan asks whether these cosmic necklaces would undergo reactions faster or slower than chemical reactions - so what
would be the timescale of evolution or lifespan of these critters?
The answer is the researchers did not speculate on that, except to say that the reaction timescale
has to be shorter than the timescale for these cosmic necklaces being destroyed.
That destruction is actually slower inside a star than outside - cosmic necklaces can
be locked into the magnetic fields within the solar plasma so they don’t fall apart
immediately.
But we really have no idea how quickly cosmic-string chemistry might proceed.
The theory just isn’t there.
But what can we say?
Timescales may be driven by the timescale of the motion of plasma in the stars and by
the size of these critters.
that timescale is days, and size is kilometers.
That would suggest slower timescales than the evolution of chemical life.
So maybe these things are very ancient and very, very slow.
John Momberg asks if this could all happen with electric monopoles, given that magnetic
monopoles don’t exist.
Well, first let me say that magnetic monopoles may well exist - in fact mainstream grand
unified theory candidates routinely predict them.
Could we do this with electric monopoles which definitely exist?
Well, yes - and it exists.
Electrons and quarks are electric monopoles.
So that bizarre electric monopole-based life is us.
I feel so exotic!
Many of you pointed out science fiction works that had similar critters.
There was Frederik Pohl's "The world at the end of time" has a Plasma creature living
in a star at war with copies of itself.
There’s david brin’s sundiver, and Frank Herbert's "Whipping Star", and several more.
I love when science fiction writers predict things that turn out to be true, but also
things that almost certainly aren’t true - but which still took physicists much longer
to come up with.
Some of you thought it was funny that we would do an episode on life in the sun right after
the potential discovery of life on venus.
Yeah, sorry that our production schedule isn't, like, 30 minutes.
It takes time to do kick ass animations.
The life on venus episode will follow soon, don't worry.
And besides, don't you think it's important to understand possible life in the sun before
we decide what diplomatic relations to develop with the venusians?
Why?
Well, Celsius notes that these sun creatures would have had a very different experience
in their scientific development.
No Copernican revolution for them, where they realised they weren’t the center of the
solar system after all.
The modicrum of humility that humanity developed from that realization would not apply ... so
like, yeah, "we’re creatures made of light and energy and are at the center of the universe,
and we're orbited by specks of dust infested with some sort of mud-based life.
Eww."
So yeah, Probably we should team up with the venusians real quick.