# Bob's Blog

## Quantum Computing and Quantum-Safe Cryptography

I
recently explained
how asymmetric encryption is absolutely vital for
protecting information and your identity.
I mentioned that we have had two major forms for some time.
**RSA** was publicly described in 1977,
and **Elliptic Curve Cryptography**
or **ECC** was first suggested in 1985.

I mentioned that both base their security on the
difficult of solving a **trapdoor problem,**
a math problem that is *much* harder to solve in one
direction than the other.

Toward the end of that earlier post, I briefly mentioned
the need for what are variously called
**quantum-safe** or
**quantum-resistant** or
**post-quantum**
algorithms.
Because we believe that a large enough
general-purpose quantum computer
could quickly solve the trapdoor problems used by RSA and ECC,
we need new asymmetric ciphers based on totally different
mathematics.

The U.S. National Institute of Standards and Technology
or NIST has been leading a major
project to develop post-quantum cryptography.

## We Need New Trapdoor Functions

The trapdoor problems used so far have been the
**factoring problem**
and the
**discrete logarithm problem.**
They must be replaced.

The security of RSA is based on the difficulty of the factoring problem. Greatly simplified, a private key consists of two large prime numbers, each on the order of 600 to 1200 digits long. The public key is the product of the two primes.

How Diffie-Hellman Works
The security of classic Diffie-Hellman is based on
the difficulty of the discrete logarithm problem, solving:

`g`

^{a} mod p = c

for `a`

, given `g,`

`p`

, and `c`

.

The security of elliptic-curve cryptography also depends on the difficulty of the discrete logarithm problem.

In 1981,
Richard Feynman
suggested
using computing systems
based on quantum mechanics
to simulate and study quantum systems.
It wasn't clear how one might build such a system,
but it was a promising idea.

Richard Feynman,
"Simulating Physics with Computers"

In 1994, Peter Shor published an algorithm
for using a quantum computer to rapidly
find the prime factors of an integer.
Within a year he had also published related algorithms
to rapidly
solve the discrete logarithm problem.

Peter Shor,
"Algorithms for quantum computation:
Discrete logarithms and factoring"
Peter Shor,
"Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer"

Shor's algorithms were understood to require
a quantum computer with
an adequate number of
adequately stable **qubits**
or quantum computational units.
No one knew how to build such a thing,
or even *if* it definitely could be built.
But if it *could* be built,
we knew what the algorithms could do.

So far there have only been proofs of concept, like the 2001 IBM project that used a 7-qubit computer to factor 15 into its prime components 5 and 3. By 2012, teams were factoring 21 into primes 7 and 3. In 2019 they tried but failed to factor 35 into 7 and 5.

A
study in 2023
showed that Shor's algorithm cannot be used in general
until quantum error correction can be worked out.
"Mostly stable" or "stable enough" just isn't good enough
against certain classes of primes.

Jin-Yi Cai,
"Shor's Algorithm Does Not Factor Large Integers
in the Presence of Noise"

We know that Shor's algorithm works.

And, we know how to build a functional (if too unstable) qubit which can do the needed computation.

It's an engineering problem at this point, how to improve and enlarge the physical solution. The theory is understood, it's a matter of making it practical.

In 2023, Oded Regev published a significant speed-up
of Shor's algorithm.

*Quanta Magazine* overview
Oded Regev,
"An Efficient Quantum Factoring Algorithm"

## New Trapdoor Functions

There are three classes of trapdoor functions for which some specific problems are believed to be quantum safe:

**Lattice-based** —
Based on finding the nearest point
in a high-dimensional lattice.
These have been used to develop both
KEM or key encapsulation mechanism schemes including
CRYSTALS-Kyber, FrodoKEM, and others;
and signing algorithms including
CRYSTALS-Dilithium.
These have been selected by NIST.

**Code-based** —
Based on error-correcting codes,
including the McEliece algorithm and variants.
The European Commission's
Post-Quantum Cryptography Study Group
has recommended the
McEliece public-key encryption algorithm.

**Hash-based** —
Based on using hash functions,
NIST selected SPHINCS+ as an algorithm for hash-based
digital signatuves.

Other schemes were initially thought to be promising,
but at least some of the algorithms based on the concepts
have been broken.
**Multivariate cryptography**
uses the solution of nonlinear equations in many variables;
one scheme was broken in February 2022.
**Isogeny-based cryptography**
finds a mapping between two elliptic curves.
The Supersingular Isogeny Diffie-Hellman or SIDH
key exchange protocol
was an initial selection in NIST's competition,
but
it was broken
in July 2022.
The initial break required about 62 minutes on a single
2.60 GHz CPU core of a laptop, definitely a
classical or non-quantum attack.

## Work is Underway

In August 2023, NIST published draft standards for algorithms derived from CRYSTALS-Kyber, CRYSTALS-Dilithium, and SPHINCS+. Those cover module-lattice-based key encapsulation mechanisms, module-lattice-based digital signatures, and stateless hash-based digital signatures.

Nginx, OpenSSL, and Quantum-Safe Cryptography
The **Open Quantum Safe** project
provides shared libraries implementing a variety
of proposed post-quantum algorithms.
I have
experimented with these,
and have managed to get the Nginx web server to support
Kyber and Frodo based KEMs.
However, there really aren't yet any browser clients
that are generally useful with this!

Hopefully we will soon reach the point where both web servers and web browsers will routinely support a range of post-quantum or quantum-safe KEMs.

## Next:

What Does "FIPS" Mean?

People often casually speak of "FIPS compliance", but that could mean multiple things. If it matters — and why else speak of it — we must be careful.

## Latest:

What is "A.I.", or "Artificial Intelligence"?

So-called "A.I." is hype and misunderstanding, here's hoping the next "A.I. Winter" arrives soon.

## Previous:

How Does Asymmetric Cryptography Work?

Asymmetric cryptography is a vital tool, but how does it work? We have two major solutions now, with more on the way. Learn how asymmetric ciphers protect information.

What's the Point of Asymmetric Encryption?

Asymmetric encryption is often described as useful for "small messages", but that's misleading. They're absolutely vital in cryptographic protocols such as key agreement and authentication.

Learn How to Write a Shell Script to Analyze Logs

Write a shell script to analyze logs and generate a report. We'll start by reporting the web server's 20 most popular pages.

How to Start Writing Scripts

Someone asked me, "How can I learn scripting?" It's easy to get started! Bash or Python or whatever!