Introduction to post-quantum cryptography
Daniel J. Bernstein
Department of Computer Science, University of Illinois at Chicago.

1 Is cryptography dead?
Imagine that it’s ﬁfteen years from now and someone announces the successful
construction of a large quantum computer. The New York Times runs a frontpage article reporting that all of the public-key algorithms used to protect
the Internet have been broken. Users panic. What exactly will happen to
cryptography?
Perhaps, after seeing quantum computers destroy RSA and DSA andECDSA, Internet users will leap to the conclusion that cryptography is dead;that there is no hope of scrambling information to make it incomprehensible
to, and unforgeable by, attackers; that securely storing and communicating
information means using expensive physical shields to prevent attackers fromseeing the information—for example, hiding USB sticks inside a locked briefcase chained to a trusted courier’s wrist.
A closer look reveals, however, that there is no justiﬁcation for the leap
from “quantum computers destroy RSA and DSA and ECDSA” to “quantum
computers destroy cryptography.” There are many important classes of cryptographic systems beyond RSA and DSA and ECDSA:••••

Hash-based cryptography. The classic example is Merkle’s hash-tree
public-key signature system (1979), building upon a one-message-signatureidea of Lamport and Diﬃe.
Code-based cryptography. The classic example is McEliece’s hiddenGoppa-code public-key encryption system (1978).
Lattice-based cryptography. The example that has perhaps attracted
the most interest, not the ﬁrst example historically, is the Hoﬀstein–
Pipher–Silverman “NTRU” public-key-encryption system (1998).
Multivariate-quadratic-equations cryptography. One of many interesting examples is Patarin’s “HFEv− ” public-key-signature system (1996),
generalizing a proposal by Matsumoto and Imai.

2•

Daniel J. Bernstein

Secret-key cryptography. The leading example is the Daemen–Rijmen“Rijndael” cipher (1998), subsequently renamed “AES,” the Advanced Encryption Standard.

All of these systems are believed to resist classical computers and quantum
computers. Nobody has ﬁgured out a way to apply “Shor’s algorithm”—thequantum-computer discrete-logarithm algorithm that breaks RSA and DSA
and ECDSA—to any of these systems. Another quantum algorithm, “Grover’s
algorithm,” does have some applications to these systems; but Grover’s algorithm is not as shockingly fast as Shor’s algorithm, and cryptographers caneasily compensate for it by choosing somewhat larger key sizes.
Is there a better attack on these systems? Perhaps. This is a familiar riskin cryptography. This is why the community invests huge amounts of time andenergy in cryptanalysis. Sometimes cryptanalysts ﬁnd a devastating attack,demonstrating that a system is useless for cryptography; for example, every
usable choice of parameters for the Merkle–Hellman knapsack public-key encryption system is easily breakable. Sometimes cryptanalysts ﬁnd attacks thatare not so devastating but that force larger key sizes. Sometimes cryptanalysts study systems for years without ﬁnding any improved attacks, and thecryptographic community begins to build conﬁdence that the best possible
attack has been found—or at least that real-world attackers will not be able
to come up with anything better.
Consider, for example, the following three factorization attacks against
RSA:•

1978: The original paper by Rivest, Shamir, and Adleman mentioned a newalgorithm, Schroeppel’s “linear sieve,” that factors any RSA modulus n—
1/2
1/2
simple operations.
and thus breaks RSA—using 2(1+o(1))(lg n) (lg lg n)
Here lg = log2 . Forcing the linear sieve to use at least 2b operations means
choosing n to have at least (0.5 + o(1))b2 /lg b bits.
Warning: 0.5 + o(1) means something that converges to 0.5 as b → ∞. It
does not say anything about, e.g., b = 128. Figuring out the proper size ofn for b = 128 requires looking more closely at the speed of the linear sieve.

•

1988: Pollard introduced a new factorization algorithm, the “number-ﬁeld
sieve.” This algorithm, as subsequently generalized by Buhler, Lenstra, and1/3
2/3
Pomerance, factors any RSA modulus n using 2(1.9...+o(1))(lg n) (lg lg n)bsimple operations. Forcing the number-ﬁeld sieve to use at least 2 operations means choosing n to have at least (0.016 . . . + o(1))b3 /(lg b)2 bits.
Today, twenty years later, the fastest known factorization algorithms
1/3
2/3
for classical computers still use 2(constant+o(1))(lg n) (lg lg n)operations.
There have been some improvements in the constant and in the details of
the o(1), but one might guess that 1/3 is optimal, and that choosing n tohave roughly b3 bits resists all possible attacks by classical computers.

Introduction to post-quantum cryptography•

3

1994: Shor introduced an algorithm that factors any RSA modulus n using(lg n)2+o(1) simple operations on a quantum computer of size (lg n)1+o(1) .
Forcing this algorithm to use at least 2b operations means choosing n tohave at least 2(0.5+o(1))b bits—an intolerable cost for any interesting valueof b. See the “Quantum computing” chapter of this book for much more
information on quantum algorithms.

Consider, for comparison, attacks on another thirty-year-old public-key
cryptosystem, namely McEliece’s hidden-Goppa-code encryption system. The
original McEliece paper presented an attack that breaks codes of “length n”
and “dimension n/2” using 2(0.5+o(1))n/lg n operations. Forcing this attack to
use 2b operations means choosing n at least (2+o(1))b lg b. Several subsequent
papers have reduced the number of attack operations by an impressively large
2factor, roughly nlg n = 2(lg n) , but (lg n)2 is much smaller than 0.5n/lg n if
n is large; the improved attacks still use 2(0.5+o(1))n/lg n operations. One canreasonably guess that 2(0.5+o(1))n/lg n is best possible. Quantum computers
don’t seem to make much diﬀerence, except for reducing the constant 0.5.
If McEliece’s cryptosystem is holding up so well against attacks, why are
we not already using it instead of RSA? The answer, in a nutshell, is eﬃciency,
speciﬁcally key size. McEliece’s public key uses roughly n2 /4 ≈ b2 (lg b)2 bits,
whereas an RSA public key—assuming the number-ﬁeld sieve is optimal andignoring the threat of quantum computers—uses roughly (0.016 . . .)b3 /(lg b)2
bits. If b were extremely large then the b2+o(1) bits for McEliece would besmaller than the b3+o(1) bits for RSA; but real-world security levels such as
b = 128 allow RSA key sizes of a few thousand bits, while McEliece key sizes
are closer to a million bits.
Figure 1 summarizes the process of designing, analyzing, and optimizing
cryptographic systems before the advent of quantum computers; Figure 2
summarizes the same process after the advent of quantum computers. Bothpictures have the same structure:•••

cryptographers design systems to scramble and unscramble data;
cryptanalysts break some of those systems;
algorithm designers and implementors ﬁnd the fastest unbroken systems.

Cryptanalysts in Figure 1 use the number-ﬁeld sieve for factorization, theLenstra–Lenstra–Lovasz algorithm for lattice-basis reduction, the Faugère algorithms for Gröbner-basis computation, and many other interesting attack
algorithms. Cryptanalysts in Figure 2 have all of the same tools in their arsenal
plus quantum algorithms, notably Shor’s algorithm and Grover’s algorithm.
All of the most eﬃcient unbroken public-key systems in Figure 1, perhaps notcoincidentally, take advantage of group structures that can also be exploited
by Shor’s algorithm, so those systems disappear from Figure 2, and the users
end up with diﬀerent cryptographic systems.

4

Daniel J. Bernstein

Cryptographers:
How can we encrypt,
decrypt, sign, verify, etc.?

Functioning cryptographic systems:
DES, Triple DES, AES,
RSA, McEliece encryption,
Merkle hash-tree signatures,
Merkle–Hellman knapsack encryption,
Buchmann–Williams class-group encryption,
ECDSA, HFEv− , NTRU, etc.

Cryptanalysts:
What can an attacker do using < 2b
operations on a classical computer?
Unbroken cryptographic systems:
Triple DES (for b ≤ 112), AES (for b ≤ 256),
RSA with b3+o(1) -bit modulus,
McEliece with code length b1+o(1) ,Merkle signatures with “strong” b1+o(1) -bit hash,BW with “strong” b2+o(1) -bit discriminant,
ECDSA with “strong” b1+o(1) -bit curve,
HFEv− with b1+o(1) polynomials,
NTRU with b1+o(1) bits, etc.

Algorithm designers and implementors:
Exactly how small and fast
are the unbroken cryptosystems?
Most eﬃcient unbroken cryptosystems:e.g., can verify signature in time b2+o(1)using ECDSA with “strong” b1+o(1) -bit curve
Users
Fig. 1. Pre-quantum cryptography. Warning: Sizes and times are simpliﬁed tob1+o(1) , b2+o(1) , etc. Optimization of any speciﬁc b requires a more detailed analysis;e.g., low-exponent RSA veriﬁcation is faster than ECDSA veriﬁcation for small b.

Introduction to post-quantum cryptography

5

Cryptographers:
How can we encrypt,
decrypt, sign, verify, etc.?

Functioning cryptographic systems:
DES, Triple DES, AES,
RSA, McEliece encryption,
Merkle hash-tree signatures,
Merkle–Hellman knapsack encryption,
Buchmann–Williams class-group encryption,
ECDSA, HFEv− , NTRU, etc.

Cryptanalysts:
What can an attacker do using < 2b
operations on a quantum computer?

Unbroken cryptographic systems:
AES (for b ≤ 128),
McEliece with code length b1+o(1) ,Merkle signatures with “strong” b1+o(1) -bit hash,
HFEv− with b1+o(1) polynomials,
NTRU with b1+o(1) bits, etc.

Algorithm designers and implementors:
Exactly how small and fast
are the unbroken cryptosystems?
Most eﬃcient unbroken cryptosystems:e.g., can verify signature in time b3+o(1)using HFEv− with b1+o(1) polynomials

Users
Fig. 2. Post-quantum cryptography. Warning: Sizes and times are simpliﬁed tob1+o(1) , b2+o(1) , etc. Optimization of any speciﬁc b requires a more detailed analysis.

6Daniel J. Bernstein

2 A taste of post-quantum cryptography
Here are three speciﬁc examples of cryptographic systems that appear to
be extremely diﬃcult to break—even for a cryptanalyst armed with a large
quantum computer.
Two of the examples are public-key signature systems; one of the examples
is a public-key encryption system. All three examples are parametrized by b,
the user’s desired security level. Many more parameters and variants appear
later in this book, often allowing faster encryption, decryption, signing, andveriﬁcation with smaller keys, smaller signatures, etc.
I chose to focus on public-key examples—a focus shared by most of thisbook—because quantum computers seem to have very little eﬀect on secretkey cryptography, hash functions, etc. Grover’s algorithm forces somewhat
larger key sizes for secret-key ciphers, but this eﬀect is essentially uniform
across ciphers; today’s fastest pre-quantum 256-bit ciphers are also the fastest
candidates for post-quantum ciphers at a reasonable security level. (There area few specially structured secret-key ciphers that can be broken by Shor’salgorithm, but those ciphers are certainly not today’s fastest ciphers.) For
an introduction to state-of-the-art secret-key ciphers I recommend the following book: Matthew Robshaw and Olivier Billet (editors), New stream cipher
designs: the eSTREAM ﬁnalists, Lecture Notes in Computer Science 4986,
Springer, 2008, ISBN 978–3–540–68350–6.
2.1 A hash-based public-key signature system
This signature system requires a standard cryptographic hash function H
that produces 2b bits of output. For b = 128 one could choose H as the SHA256 hash function. Over the last few years many concerns have been raised
regarding the security of popular hash functions, and over the next few years
NIST will run a competition for a SHA-256 replacement, but all known attacks
against SHA-256 are extremely expensive.
The signer’s public key in this system has 8b2 bits: e.g., 16 kilobytes forb = 128. The key consists of 4b strings y1 [0], y1 [1], y2 [0], y2 [1], . . . , y2b [0], y2b [1],each string having 2b bits.
A signature of a message m has 2b(2b + 1) bits: e.g., 8 kilobytes for b =128. The signature consists of 2b-bit strings r, x1 , . . . , x2b such that the bits
(h1 , . . . , h2b ) of H(r, m) satisfy y1 [h1 ] = H(x1 ), y2 [h2 ] = H(x2 ), and so on
through y2b [h2b ] = H(x2b ).
How does the signer ﬁnd x with H(x) = y? Answer: The signer starts
by generating a secret x and then computes y = H(x). Speciﬁcally, thesigner’s secret key has 8b2 bits, namely 4b independent uniform random
strings x1 [0], x1 [1], x2 [0], x2 [1], . . . , x2b [0], x2b [1], each string having 2b bits.
The signer computes the public key y1 [0], y1 [1], y2 [0], y2 [1], . . . , y2b [0], y2b [1] as
H(x1 [0]), H(x1 [1]), H(x2 [0]), H(x2 [1]), . . . , H(x2b [0]), H(x2b [1]).

Introduction to post-quantum cryptography

7

To sign a message m, the signer generates a uniform random string r,
computes the bits (h1 , . . . , h2b ) of H(r, m), and reveals (r, x1 [h1 ], . . . , x2b [h2b ])as a signature of m. The signer then discards the remaining x values andrefuses to sign any more messages.
What I’ve described so far is the “Lamport–Diﬃe one-time signature system.” What do we do if the signer wants to sign more than one message?
An easy answer is “chaining.” The signer includes, in the signed message,a newly generated public key that will be used to sign the next message. The
veriﬁer checks the ﬁrst signed message, including the new public key, and canthen check the signature of the next message; the signature of the nth message
includes all n − 1 previous signed messages. More advanced systems, such as
Merkle’s hash-tree signature system, scale logarithmically with the number ofmessages signed.
To me hash-based cryptography is a convincing argument for the existence of secure post-quantum public-key signature systems. Grover’s algorithm is the fastest quantum algorithm to invert generic functions, and is
widely believed to be the fastest quantum algorithm to invert the vast majority of speciﬁc eﬃciently computable functions (although obviously there
are also many exceptions, i.e., functions that are easier to invert). Hash-based
cryptography can convert any hard-to-invert function into a secure public-key
signature system.
See the “Hash-based digital signature schemes” chapter of this book for amuch more detailed discussion of hash-based cryptography. Note that mosthash-based systems impose an extra requirement of collision resistance upon
the hash function, allowing simpler signatures without randomization.
2.2 A code-based public-key encryption system
Assume that b is a power of 2. Write n = 4b lg b; d = lg n; and t = 0.5n/d.
For example, if b = 128, then n = 3584; d = 12; and t = 149.
The receiver’s public key in this system is a dt × n matrix K with coeﬃcients in F2 . Messages suitable for encryption are n-bit strings of “weight t,”i.e., n-bit strings having exactly t bits set to 1. To encrypt a message m, thesender simply multiplies K by m, producing a dt-bit ciphertext Km.
The basic problem for the attacker is to “syndrome-decode K,” i.e., to undo
the multiplication by K, knowing that the input had weight t. It is easy, by
linear algebra, to work backwards from Km to some n-bit vector v such that
Kv = Km; however, there are a huge number of choices for v, and ﬁnding
a weight-t choice seems to be extremely diﬃcult. The best known attacks on
this problem take time exponential in b for most matrices K.
How, then, can the receiver solve the same problem? The answer is thatthe receiver generates the public key K with a secret structure, speciﬁcallya “hidden Goppa code” structure, that allows the receiver to decode in areasonable amount of time. It is conceivable that the attacker can detect the“hidden Goppa code” structure in the public key, but no such attack is known.

8

Daniel J. Bernstein

Speciﬁcally, the receiver starts with distinct elements α1 , α2 , . . . , αn of theﬁeld F2d and a secret monic degree-t irreducible polynomial g ∈ F2d [x]. The
main work for the receiver is to syndrome-decode the dt × n matrix⎞⎛
1/g(α1 ) · · · 1/g(αn )⎜ α1 /g(α1 ) · · · αn /g(αn ) ⎟
⎟
⎜
H=⎜
⎟,
..
..
..
⎠
⎝
.
.
.
α1t−1 /g(α1 ) · · · αnt−1 /g(αn )where each element of F2d is viewed as a column of d elements of F2 in astandard basis of F2d . This matrix H is a “parity-check matrix for an irreducible binary Goppa code,” and can be syndrome-decoded by “Patterson’salgorithm” or by faster algorithms.
The receiver’s public key K is a scrambled version of H. Speciﬁcally, thereceiver’s secret key also includes an invertible dt × dt matrix S and an n ×
n permutation matrix P . The public key K is the product SHP . Given aciphertext Km = SHP m, the receiver multiplies by S −1 to obtain HP m,
decodes H to obtain P m, and multiplies by P −1 to obtain m.
What I’ve described here is a variant, due to Niederreiter (1986), of
McEliece’s original code-based public-key encryption system. Both systems
are extremely eﬃcient at key generation, encryption, and decryption, but—as
I mentioned earlier—have been held back by their long public keys.
See the “Code-based cryptography” and “Lattice-based cryptography”
chapters of this book for much more information about code-based cryptography and (similar but more complicated) lattice-based cryptography, including
several systems that use shorter public keys.
2.3 A multivariate-quadratic public-key signature system
The public key in this system is a sequence P1 , P2 , . . . , P2b ∈ F2 [w1 , . . . , w4b ]:a sequence of 2b polynomials in the 4b variables w1 , . . . , w4b , with coeﬃcientsin F2 = {0, 1}. Each polynomial is required to have degree at most 2, with nosquared terms, and is represented as a sequence of 1 + 4b + 4b(4b − 1)/2 bits,
namely the coeﬃcients of 1, w1 , . . . , w4b , w1 w2 , w1 w3 , . . . , w4b−1 w4b . Overall
the public key has 16b3 + 4b2 + 2b bits; e.g., 4 megabytes for b = 128.
A signature of a message m has just 6b bits: namely, 4b values w1 , . . . , w4b ∈F2 and a 2b-bit string r satisfying
H(r, m) = (P1 (w1 , . . . , w4b ), . . . , P2b (w1 , . . . , w4b )).
Here H is a standard hash function. Verifying a signature uses one evaluationof H and roughly b3 bit operations to evaluate P1 , . . . , P2b .
The critical advantage of this signature system over hash-based signaturesystems is that each signature is short. Other multivariate-quadratic systems
have even shorter signatures and, in many cases, much shorter public keys.

Introduction to post-quantum cryptography

9

The basic problem faced by an attacker is to ﬁnd a sequence of 4b bits
w1 , . . . , w4b producing 2b speciﬁed output bits
(P1 (w1 , . . . , w4b ), . . . , P2b (w1 , . . . , w4b )).
Guessing a sequence of 4b bits is fast but has, on average, chance only 2−2b ofsuccess. More advanced equation-solving attacks, such as “XL,” can succeed
in considerably fewer than 22b operations, but no known attacks have a reasonable chance of succeeding in 2b operations for most quadratic polynomials
P1 , . . . , P2b in 4b variables. The diﬃculty of this problem is not surprising,
given how general the problem is: every inversion problem can be rephrased
as a problem of solving multivariate quadratic equations.
How, then, can the signer solve the same problem? The answer, as in
Section 2.2, is that the signer generates the public key P1 , . . . , P2b with asecret structure, speciﬁcally an “HFEv− ” structure, that allows the signer tosolve the equations in a reasonable amount of time. It is conceivable that theattacker can detect the HFEv− structure in the public key, or in the public key
together with a series of legitimate signatures; but no such attack is known.
Fix a standard irreducible polynomial ϕ ∈ F2 [t] of degree 3b. Deﬁne L as
the ﬁeld F2 [t]/ϕ of size 23b . The critical step in signing is ﬁnding roots of asecret low-degree univariate polynomial over L: speciﬁcally, a polynomial inL[x] of degree at most 2b. There are several standard algorithms that do thisin time bO(1) .
The secret polynomial is chosen to have all nonzero exponents of the form
2i + 2j or 2i . If an element x ∈ L is expressed in the form x0 + x1 t + · · · +x3b−1 t3b−1 , with each xi ∈ F2 , then x2 = x0 +x1 t2 +· · ·+x3b−1 t6b−2 and x4 =ij
x0 +x1 t4 +· · ·+x3b−1 t12b−4 and so on, so x2 +2 is a quadratic polynomial in thevariables x0 , . . . , x3b−1 . Some easy extra transformations hide the structure ofthis polynomial, producing the signer’s public key.
Speciﬁcally, the signer’s secret key has three components:•••

An invertible 4b × 4b matrix S with coeﬃcients in F2 .
A polynomial Q ∈ L[x, v1 , v2 , . . . , vb ] where each term has one of the folijilowing six forms: x2 +2 with  ∈ L, 2i < 2j , 2i + 2j ≤ 2b; x2 vj withi ∈ L, 2i ≤ 2b; vi vj ; x2 ; vj ; . If b = 128 then there are 9446 possible
terms, each having a 384-bit coeﬃcient , for a total of 443 kilobytes.
A 2b × 3b matrix T of rank 2b with coeﬃcients in F2 .

The signer computes the public key as follows. Compute a column vector(x0 , x1 , . . . , x3b−1 , v1 , v2 , . . . , vb ) as S times the column vector (w1 , . . . , w4b ).
2
2
Inside thei quotient ring L[w1 , . . . , w4b ]/(w1 − w1 , . . . , w4b − w4b ), computex=
xi t and y = Q(x, v1 , v2 , . . . , vb ). Write y as y0 + y1 t + · · · + y3b−1 t3b−1
with each yi in F2 [w1 , . . . , w4b ], and compute (P1 , P2 , . . . , P2b ) as T times thecolumn vector (y0 , y1 , . . . , y3b−1 ).
Signing works backwards through the same construction:

10

•

•
•
•

Daniel J. BernsteinStarting from the desired values of P1 , P2 , . . . , P2b , solve the secret linear equations T (y0 , y1 , . . . , y3b−1 ) = (P1 , P2 , . . . , P2b ) to obtain values of(y0 , y1 , . . . , y3b−1 ). There are 2b possibilities for (y0 , y1 , . . . , y3b−1 ); choose
one of those possibilities randomly.
Choose values v1 , v2 , . . . , vb ∈ F2 randomly, and substitute these values into the secret polynomial Q(x, v1 , v2 , . . . , vb ), obtaining a polynomial
Q(x) ∈ L[x].
Compute y = y0 +y1 t+· · ·+y3b−1 t3b−1 ∈ L, and solve Q(x) = y, obtainingx ∈ L. If there are several roots x of Q(x) = y, choose one of themrandomly. If there are no roots, restart the signing process.
Write x as x0 + x1 t + · · · + x3b−1 t3b−1 with x0 , . . . , x3b−1 ∈ F2 . Solve thesecret linear equations S(w1 , . . . , w4b ) = (x0 , . . . , x3b−1 , v1 , . . . , vb ), obtaining a signature (w1 , . . . , w4b ).

This is an example of a class of HFEv− constructions introduced by Patarin
in 1996. “HFE” refers to the “Hidden Field Equation” Q(x) = y. The “−” refers
to the omission of some bits: Q(x) = y is equivalent to 3b equations on bits,
but only 2b equations are published. The “v” refers to the “vinegar” variables
v1 , v2 , . . . , vb . Pure HFE, with no omitted bits and no vinegar variables, is2
breakable in time roughly 2(lg b) by Gröbner-basis attacks, but HFEv− hassolidly resisted attack for more than ten years.
There are many other ways to build multivariate-quadratic public-key systems, and many interesting ideas for saving time and space, producing a huge
number of candidates for post-quantum cryptography; see the “Multivariate
public key cryptography” chapter of this book. It is hardly a surprise thatsome of the fastest candidates have been broken. A recent paper by Dubois,
Fouque, Shamir, and Stern, after breaking an extremely simpliﬁed systemwith no vinegar variables and with only one nonzero term in Q, leaps to theconclusion that all multivariate-quadratic systems are dangerous:
Multivariate cryptographic schemes are very eﬃcient but have a lotof exploitable mathematical structure. Their security is not fully understood, and new attacks against them are found on a regular basis.
It would thus be prudent not to use them in any security-critical applications.
Presumably the same authors would recommend already avoiding 4096-bit
RSA in a pre-quantum world since 512-bit RSA has been broken, would recommend avoiding all elliptic curves since a few special elliptic curves havebeen broken (clearly elliptic curves have “a lot of exploitable mathematicalstructure”), and would recommend avoiding 256-bit AES since DES has beenbroken (“new attacks against ciphers are found on a regular basis”).
My own recommendation is that the community continue to systematicallystudy the security and eﬃciency of cryptographic systems, so that we canidentify the highest-security systems that ﬁt the speed and space requirements
imposed by cryptographic users.

Introduction to post-quantum cryptography

11

3 Challenges in post-quantum cryptography
Let me review the picture so far. Some cryptographic systems, such as RSA
with a four-thousand-bit key, are believed to resist attacks by large classicalcomputers but do not resist attacks by large quantum computers. Some alternatives, such as McEliece encryption with a four-million-bit key, are believed
to resist attacks by large classical computers and attacks by large quantum
computers.
So why do we need to worry now about the threat of quantum computers?
Why not continue to focus on RSA and ECDSA? If someone announces the
successful construction of a large quantum computer ﬁfteen years from now,
why not simply switch to McEliece etc. ﬁfteen years from now?
This section gives three answers—three important reasons that parts ofthe cryptographic community are already starting to focus attention on postquantum cryptography:•••

We need time to improve the eﬃciency of post-quantum cryptography.
We need time to build conﬁdence in post-quantum cryptography.
We need time to improve the usability of post-quantum cryptography.

In short, we are not yet prepared for the world to switch to post-quantum
cryptography.
Maybe this preparation is unnecessary. Maybe we won’t actually needpost-quantum cryptography. Maybe nobody will ever announce the successful
construction of a large quantum computer. However, if we don’t do anything,and if it suddenly turns out years from now that users do need post-quantum
cryptography, years of critical research time will have been lost.
3.1 Eﬃciency
Elliptic-curve signature systems with O(b)-bit signatures and O(b)-bit keys
appear to provide b bits of security against classical computers. State-of-theart signing algorithms and veriﬁcation algorithms take time b2+o(1) .
Can post-quantum public-key signature systems achieve similar levels of
performance? My two examples of signature systems certainly don’t qualify:
one example has signatures of length b2+o(1) , and the other example has keysof length b3+o(1) . There are many other proposals for post-quantum signaturesystems, but I have never seen a proposal combining O(b)-bit signatures, O(b)bit keys, polynomial-time signing, and polynomial-time veriﬁcation.
Ineﬃcient cryptography is an option for some users but is not an option fora busy Internet server handling tens of thousands of clients each second. If you
make a secure web connection today to https://www.google.com, Google
redirects your browser to http://www.google.com, deliberately turning oﬀ
cryptographic protection. Google does have some cryptographically protected
web pages but apparently cannot aﬀord to protect its most heavily used web
pages. If Google already has trouble with the slowness of today’s cryptographic

12Daniel J. Bernstein

software, surely it will not have less trouble with the slowness of post-quantum
cryptographic software.
Constraints on space and time have always posed critical research challenges to cryptographers and will continue to pose critical research challenges
to post-quantum cryptographers. On the bright side, research in cryptography has produced many impressive speedups, and one can reasonably hopethat increased research eﬀorts in post-quantum cryptography will continue
to produce impressive speedups. There has already been progress in several
directions; for details, read the rest of this book!
3.2 Conﬁdence
Merkle’s hash-tree public-key signature system and McEliece’s hidden-Goppacode public-key encryption system were both proposed thirty years ago andremain essentially unscathed despite extensive cryptanalytic eﬀorts.
Many other candidates for hash-based cryptography and code-based cryptography are much newer; multivariate-quadratic cryptography and latticebased cryptography provide an even wider variety of new candidates for postquantum cryptography. Some speciﬁc proposals have been broken. Perhaps a
new system will be broken as soon as a cryptanalyst takes the time to look at
the system.
One could insist on using classic systems that have survived many yearsof review. But often the user cannot aﬀord the classic systems and is forced
to consider newer, smaller, faster systems that take advantage of more recent
research into cryptographic eﬃciency.
To build conﬁdence in these systems the community needs to make surethat cryptanalysts have taken time to search for attacks on the systems. Those
cryptanalysts, in turn, need to gain familiarity with post-quantum cryptography and experience with post-quantum cryptanalysis.
3.3 Usability
The RSA public-key cryptosystem started as nothing more than a trapdoor
one-way function, “cube modulo n.” (Tangential historical note: The original
paper by Rivest, Shamir, and Adleman actually used large random exponents.
Rabin pointed out that small exponents such as 3 are hundreds of times faster.)
Unfortunately, one cannot simply use a trapdoor one-way function as if itwere a secure encryption function. Modern RSA encryption does not simply
cube a message modulo n; it has to ﬁrst randomize and pad the message. Furthermore, to handle long messages, it encrypts a short random string insteadof the message, and uses that random string as a key for a symmetric cipher
to encrypt and authenticate the original message. This infrastructure around
RSA took many years to develop, with many disasters along the way, such as
the “PKCS#1 v1.5” padding standard broken by Bleichenbacher in 1998.

Introduction to post-quantum cryptography

13

Furthermore, even if a secure encryption function has been deﬁned andstandardized, it needs software implementations—and perhaps also hardware
implementations—suitable for integration into a wide variety of applications.
Implementors need to be careful not only to achieve correctness and speed but
also to avoid timing leaks and other side-channel leaks. A few years ago several
implementations of RSA and AES were broken by cache-timing attacks; Intelhas, as a partial solution, added AES instructions to its future CPUs.
This book describes randomization and padding techniques for some postquantum systems, but much more work remains to be done. Post-quantum
cryptography, like the rest of cryptography, needs complete hybrid systems
and detailed standards and high-speed leak-resistant implementations.

4 Comparison to quantum cryptography“Quantum cryptography,” also called “quantum key distribution,” expands a
short shared key into an eﬀectively inﬁnite shared stream. The prerequisite
for quantum cryptography is that the users, say Alice and Bob, both know
(e.g.) 256 unpredictable secret key bits. The result of quantum cryptography is that Alice and Bob both know a stream of (e.g.) 1012 unpredictablesecret bits that can be used to encrypt messages. The length of the output
stream increases linearly with the amount of time that Alice and Bob spend
on quantum cryptography.
This description of quantum cryptography might make “quantum cryptography” sound like a synonym for “stream cipher.” The prerequisite for a
stream cipher—for example, counter-mode AES—is that Alice and Bob bothknow (e.g.) 256 unpredictable secret key bits. The result of a stream cipher
is that Alice and Bob both know a stream of (e.g.) 1012 unpredictable secretbits that can be used to encrypt messages. The length of the output streamincreases linearly with the amount of time that Alice and Bob spend on thestream cipher.
However, the details of quantum cryptography are quite diﬀerent from thedetails of a stream cipher:•••A stream cipher generates the output stream as a mathematical functionof the input key. Quantum cryptography uses physical techniques for Aliceto continuously generate random secret bits and to encode those bits fortransmission to Bob.
A stream cipher can be used to protect information sent through any number of untrusted hops on any existing network; eavesdropping fails because
the encrypted information is incomprehensible. Quantum cryptographyrequires a direct ﬁber-optic connection between Alice’s trusted quantumcryptography hardware and Bob’s trusted quantum-cryptography hardware; eavesdropping fails because it interrupts the communication.
Even if a stream cipher is implemented perfectly, its security is merely
conjectural—“nobody has ﬁgured out an attack so we conjecture that no14•

Daniel J. Bernstein

attack exists.” If quantum cryptography is implemented perfectly then its
security follows from generally accepted laws of quantum mechanics.
A modern stream cipher can run on any commonly available CPU, andgenerates gigabytes of stream per second on a $200 CPU. Quantum cryptography generates kilobytes of stream per second on special hardware
costing $50000.

One can reasonably argue that quantum cryptography, “locked-briefcase
cryptography,” “meet-privately-in-a-sealed-vaultcryptography,” and otherphysical shields for information are part of post-quantum cryptography: they will
not be destroyed by quantum computers! But post-quantum cryptography is,in general, a quite diﬀerent topic from quantum cryptography:•••

Post-quantum cryptography, like the rest of cryptography, covers a wide
range of secure-communication tasks, ranging from secret-key operations,public-key signatures, and public-key encryption to high-level operations
such as secure electronic voting. Quantum cryptography handles only one
task, namely expanding a short shared secret into a long shared secret.
Post-quantum cryptography, like the rest of cryptography, includes somesystems proven to be secure, but also includes many lower-cost systems
that are conjectured to be secure. Quantum cryptography rejects conjectural systems—begging the question of how Alice and Bob can securely
share a secret in the ﬁrst place.
Post-quantum cryptography includes many systems that can be used fora noticeable fraction of today’s Internet communication—Alice and Bob
need to perform some computation and send some data but do not need
any new hardware. Quantum cryptography requires new network hardwarethat is, at least for the moment, impossibly expensive for the vast majority
of Internet users.

My own interests are in cryptographic techniques that can be widely deployed
across the Internet; I see tremendous potential in post-quantum cryptography
and very little hope for quantum cryptography.
To be fair I should report the views of the proponents of quantum cryptography. Magiq, a company that sells quantum-cryptography hardware, has
the following statement on its web site:
Once the enormous energy boost that quantum computers are expected to provide hits the street, most encryption security standards—
and any other standard based on computational diﬃculty—will fall,experts believe.
Evidently these unnamed “experts” believe—and Magiq would like you tobelieve—that quantum computers will break AES, and dozens of other wellknown secret-key ciphers, and Merkle’s hash-tree signature system, andMcEliece’s hidden-Goppa-code encryption system, and Patarin’s HFEv− signature system, and NTRU, and all of the other cryptographic systems discussed in this book. Time will tell whether this belief was justiﬁed!