CRYSTALS-Kyber

Algorithm Specications And Supporting Documentation(version 2.0)
Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint,
Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, Damien Stehlé
April 1, 20191

Changelog
In the following we list the changes from Kyber as submitted to the NIST PQC project in November 2017
and Kyber with round-2 tweaks together with brief explanations of the motivation for the changes.

Changes to the core

Kyber design• Eliminate public-key compression.

As NIST remarked, the Kyber security proof only applies

to a variant of round-1 Kyber that does not compress the public key.

While we strongly believethat this didn't lower actual security, to alleviate any concerns, we decided to not include public-key
compression in round-2 Kyber.

• Change to q = 3329. We balance the increased bandwidth requirement from dropping the public-key
compression by choosing a smaller value of q . Specically, we change q from 7681 to 3329. This change
was enabled by recent results in [65] showing that we do not need to pick q such that 2n | (q − 1) toobtain very fast inplace NTT-based multiplication. Using a q such that n | (q − 1) (and maybe evenn
2 | q − 1) is enough to achieve equal (or even slightly better) performance.
• Change to η = 2. As a consequence of our smaller value of q , we also decrease the noise parameterη . This parameter is now the same for all security levels.
• Update du and dv . We update the ciphertext-compression parameters du and dv to achieve a similarbalance of ciphertext size, failure probability, and security as in round-1 Kyber.

• Update denition of the NTT. Also as a consequence of changing to q = 3329, we need to update256
the denition of the NTT. Instead of decomposing an element a ∈ Zq [X]/(X+ 1) as(a mod X − r1 , . . . , a mod X − r256 ),the NTT now decomposes it as0(a mod X 2 − r10 , . . . , a mod X 2 − r128).
256

In both cases, though, the NTT domain is still an element of Zq.

• Represent public key in NTT domain. As public keys are no longer compressed and as the NTT
is already part of the specication, we also transmit public keys in NTT domain to save several NTT
computations.

• Update sampling of A. Sampling of the public matrix A is updated to work for the new value ofq = 3329.
• Derive nal key using SHAKE-256. Instead of deriving the nal shared key through SHA3-256
we now use SHAKE-256.

This allows to easily derive keys of aritrary length (although this is notsupported by the NIST API).

90s variant ofKyber

As an additional update for round 2, we also present a variant of Kyber that instead of relying on Keccak
for all symmetric primitives, relies on AES and SHA-2. As the design of those primitives is rooted in thelast years of the previous millenium, we refer to this variant as the 90s variant.
The motivation for including this variant is the realization that optimized implementations of Kyberon dierent platforms consistently spend much more than half of the time in Keccak permutations. Benchmarking Kyber thus boils down to benchmarking the performance of Keccak, which is likely to change
dramatically once hardware support becomes available.

The 90s variant is thus meant to showcase theperformance of Kyber if symmetric primitives are accelerated in hardware.
Furthermore, some experiments with post-quantum schemesmost notably the CECPQ1 and CECPQ2
TLS experiments by Googleended up replacing Keccak-based symmetric primitives by AES and SHA-2 toachieve better performance. Should any early adopters want to use Kyber with AES and SHA-2, then wewould rather have one variant of Kyber than a dierent one in each deployment.

2

Editorial changes to the specication
We edited the specication to match the round-2 parameters, xed a few small small mistakes and updated
performance numbers. We also added a section at the end that briey discusses some recent papers that are
relevant for the evaluation of Kyber.

3

Contents
1

Written specication
1.1

3
4

5

6

7

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.3

CPAPKE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Specication of Kyber.CCAKEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.4

Kyber parameter sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

1.5

Design rationale

13

1.2

2

5

Preliminaries and notation.
Specication of Kyber.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Performance analysis

8
11

15

2.1

Implementation considerations and tradeos . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

2.2

Performance of reference and AVX2 implementations . . . . . . . . . . . . . . . . . . . . . . .

17Known Answer Test values

17

Expected security strength

19

4.1

Security denition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2

Rationale of our security estimates. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19
19

4.3

Security Assumption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

4.3.1

Tight reduction from MLWE in the ROM . . . . . . . . . . . . . . . . . . . . . . . . .

19

4.3.2

Non-tight reduction from MLWE in the QROM . . . . . . . . . . . . . . . . . . . . . .

20

4.4

Estimated security strength . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

4.5

Additional security properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

4.5.1

Forward secrecy.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

4.5.2

Side-channel attacks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

4.5.3

Multi-target attacks

4.5.4

Misuse resilience. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

Analysis with respect to known attacks

23

5.1

23

Attacks against the underlying MLWE problem . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.1

Attacks against LWE.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.1.2

Primal attack.

23. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

5.1.3

Dual attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

5.1.4

Core-SVP hardness of Kyber . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

5.1.5

Algebraic attacks.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

5.2

Attacks against symmetric primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

5.3

Attacks exploiting decryption failures26. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Advantages and limitations

28

6.1

Advantages. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

6.2

Comparison to SIDH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

6.3

Comparison to code-based KEMs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

6.4

Comparison to other lattice-based schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

6.4.1

Schemes that build a KEM directly . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

6.4.2

LWE based schemes

6.4.3

Ring-LWE based schemes

6.4.4

NTRU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

6.4.5

Dierent Polynomial Rings. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

6.4.6

Deterministic Noise.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Brief discussion of relevant results since Nov. 2017

4

29
29

30

1 Written specication
Kyber is an IND-CCA2-secure key-encapsulation mechanism (KEM), which has rst been described in [22].
The security of Kyber is based on the hardness of solving the learning-with-errors problem in module lattices(MLWE problem [57]). The construction of Kyber follows a two-stage approach: we rst introduce an INDCPA-secure public-key encryption scheme encrypting messages of a xed length of 32 bytes, which we call

CPAPKE. We then use a slightly tweaked FujisakiOkamoto (FO) transform [40] to construct the

Kyber.

IND-CCA2-secure KEM. Whenever we want to emphasize that we are speaking about the IND-CCA2-secure

CCAKEM.

KEM, we will refer to it as Kyber.

In Subsection 1.1 we give preliminaries and x notation.

In Subsection 1.2 we give a full specica-

CPAPKE. Subsection 1.3 gives details of the transform that we use in Kyber to obtain
Kyber.CCAKEM from Kyber.CPAPKE. Subsection 1.4 lists the parameters that we propose for dierenttion of Kyber.

security levels. Finally, Subsection 1.5 explains the design rationale behind Kyber.

1.1

Preliminaries and notation.

Bytes and byte arrays. Inputs and outputs to all API functions of Kyber are byte arrays. To simplify
notation, we denote by by B the set {0, . . . , 255}, i.e., the set of 8-bit unsigned integers (bytes). Consequently
we denote by Bkthe set of byte arrays of length k and by B∗

the set of byte arrays of arbitrary length (orbyte streams). For two byte arrays a and b we denote by (akb) the concatenation of a and b. For a byte arraya we denote by a + k the byte array starting at byte k of a (with indexing starting at zero). For example,
let a by a byte array of length `, let b be another byte array and let c = (akb) be the concatenation of a andb; then b = a + `. When it is more convenient to work with an array of bits than an array of bytes we makethis conversion explicit via the BytesToBits function that takes as input an array of ` bytes and produces as
output an array of 8` bits. Bit βi at position i of the output bit array is obtained from byte bi/8 at position
i/8 of the input array by computing βi = (bi/8 /2(i mod 8) ) mod 2 .
Polynomial rings and vectors. We denote by R the ring Z[X]/(X n +1) and by Rq the ring Zq [X]/(X n +1),
n0 −1

0

+ 1 is the 2n -th cyclotomic polynomial. Throughout this document, the00values of n, n and q are xed to n = 256, n = 9, and q = 3329. Regular font letters denote elements in R or
Rq (which includes elements in Z and Zq ) and bold lower-case letters represent vectors with coecients in
R or Rq . By default, all vectors will be column vectors. Bold upper-case letters are matrices. For a vectorv (or matrix A), we denote by vT (or AT ) its transpose. For a vector v we write v[i] to denote it's i-th
entry (with indexing starting at zero); for a matrix A we write A[i][j] to denote the entry in row i, columnj (again, with indexing starting at zero).
where n = 2

such that Xn±α to be the
α
α−1
α−1
α
0
0
0
<
r
≤
(resp. −≤r≤) such that r = r mod α. For any
unique element r in the range −
2
2
2
2
+
0
0
0
positive integer α, we dene r = r mod α to be the unique element r in the range 0 ≤ r < α such that0r = r mod α. When the exact representation is not important, we simply write r mod α.

Modular reductions. For an even (resp. odd) positive integer α, we dene r 0 = r mod
0

Rounding. For an element x ∈ Q we denote by dxc rounding of x to the closest integer with ties being
rounded up.

±

Sizes of elements. For an element w ∈ Zq , we write kwk∞ to mean |w modq|. We now dene the `∞∈ R:pkwk∞ = max kwi k∞ , kwk = kw0 k2∞ + . . . + kwn−1 k2∞ .

and `2 norms for w = w0 + w1 X + . . . + wn−1 X

n−1

i

k

Similarly, for w = (w1 , . . . , wk ) ∈ R , we denekwk∞ = max kwi k∞ , kwk =ip

kw1 k2 + . . . + kwk k2 .

Sets and Distributions. For a set S , we write s ← S to denote that s is chosen uniformly at random from

S . If S is a probability distribution, then this denotes that s is chosen according to the distribution S .
5Compression and Decompression. We now dene a function Compressq (x, d) that takes an elementx ∈ Zq and outputs an integer in {0, . . . , 2d − 1}, where d < dlog2 (q)e. We furthermore dene a function
Decompressq , such thatx0 = Decompressq Compressq (x, d), d(1)
is an element close to x  more specically|x0 − x mod± q| ≤ Bq :=

l q k
.
2d+1

The functions satisfying these requirements are dened as:

Compressq (x, d) = d(2d /q) · xc mod+ 2d ,Decompressq (x, d) = d(q/2d ) · xc .
WhenCompressq or Decompressq is used with x ∈ Rq or x ∈ Rqk , the procedure is applied to eachcoecient individually.
The main reason for dening the Compressq and Decompressq functions is to be able to discard some
low-order bits in the ciphertext, which do not have much eect on the correctness probability of decryption
 thus reducing the size of ciphertexts.
Yet, the Compressq and Decompressq are also used for another purpose than compression, namely toperform the usual LWE error correction during encryption and decryption.

More precisely, in line 20 of

the encryption procedure (Algorithm 5) the Decompressq function is used to create error tolerance gaps bysending 0 to 0 and 1 to dq/2c. Later on, on line 4 of the decryption procedure (Algorithm 6), the Compressq

Tfunction is used to decrypt to a 1 if v − su is closer to dq/2c than to 0, and decrypt to a 0 otherwise.

Symmetric primitives. The design of Kyber makes use of a pseudorandom function PRF : B 32 × B → B ∗∗× B × B → B ∗ . Kyber also makes use of two hash functions→ B 32 and G : B ∗ → B 32 × B 32 and of a key-derivation function KDF : B ∗ → B ∗ .

and of an extendable output function XOF : B
H: B∗

NTTs, multiplication, and bitreversed order. A very ecient way to perform multiplications in Rq is
via the so-called number-theoretic transform (NTT).

8

For our prime q = 3329 with q − 1 = 2· 13, the base eld Zq contains primitive 256-th roots of unity but
256+ 1 of R factors into 128 polynomialsof degree 2 modulo q and the NTT of a polynomial f ∈ Rq is a vector of 128 polynomials of degree one.

not primitive 512-th roots. Therefore, the dening polynomial X

Simple in-place implementations of the NTT without reordering outputs these polynomials in bit-reversedorder and we dene the NTT in this way. Concretely, let ζ = 17 be the rst primitive 256-th root of unity
modulo q , and {ζ, ζ3, ζ 5 , . . . , ζ 255 } the set of all the 256-th roots of unity. The polynomial X 256 + 1 cantherefore be written as

X

256

+1=

127
Y

2

(X − ζ

2i+1(X 2 − ζ 2br7 (i)+1 )

i=0

i=0
where

)=

127
Y

br7 (i) for i = 0, . . . , 127 is the bit reversal of the unsigned 7-bit integer i. This latter ordering of thefactors is useful for compatibility with the idiosyncrasies of AVX instructions. Then the NTT of f ∈ Rq isgiven by(f mod X 2 − ζ 2br7 (0)+1 , . . . , f mod X 2 − ζ 2br7 (127)+1 )256This vector of linear polynomials is then serialized to a vector in Zq(2)

in the canonical way. Moreover, inorder to not introduce additional data types and facilitate in-place implementations of the NTT we dene

NTT : Rq → Rq to be the bijection that maps f ∈ Rq to the polynomial with the aforementioned coecient
vector. Hence,

NTT(f ) = fˆ = fˆ0 + fˆ1 X + · · · + fˆ255 X 255

6

with

fˆ2i =

127X

f2j ζ (2br7 (i)+1)j ,(3)

f2j+1 ζ (2br7 (i)+1)j .

(4)

j=0

fˆ2i+1 =

127
X
j=0

We would like to stress that even though we write fˆ as a polynomial in Rq , it has no algebraic meaning
as such. The natural algebraic representation ofNTT(f ) = fˆ is as 128 polynomials of degree 1 as in (2)using the denitions for fˆi from (3) and (4). That is,NTT(f ) = fˆ = (fˆ0 + fˆ1 X, fˆ2 + fˆ3 X, . . . , fˆ254 + fˆ255 X).
NTT and its inverse NTT−1 we can compute the product f · g of two elements f, g ∈ Rq very e−1ciently as NTT(NTT(f ) ◦ NTT(g)) where NTT(f ) ◦ NTT(g) = fˆ◦ ĝ = ĥ denotes the basecase multiplication
Using

consisting of the 128 productsĥ2i + ĥ2i+1 X = (fˆ2i + fˆ2i+1 X)(ĝ2i + ĝ2i+1 X) mod X 2 − ζ 2br7 (i)+1of linear polynomials.
When we apply

NTT or NTT−1 to a vector or matrix of elements of Rq , then this means that therespective operation is applied to each entry individually. When we apply ◦ to matrices or vectors it meansthat we perform a usual matrix multiplication, but that the individual products of entries are the above
basecase multiplications.
Throughout the document we will write

NTT and NTT−1 whenever we refer to the concrete functions asdened above and use normal-font NTT whenever we refer to the general technique.

Uniform sampling in Rq . Kyber uses a deterministic approach to sample elements in Rq that are
statistically close to a uniformly random distribution. For this sampling we use a function Parse : B∗→ Rq ,

which receives as input a byte stream B = b0 , b1 , b2 , . . . and computes the NTT-representation â = â0 +â1 X + · · · + ân−1 X n−1 ∈ Rq of a ∈ Rq . Parse is described in Algorithm 1 (note that this description assumes
that q = 3329).
Algorithm 1 Parse : B ∗ → Rqn
Input: Byte stream B = b0 , b1 , b2 · · · ∈ B ∗Output: NTT-representation â ∈ Rq of a ∈ Rq

i := 0j := 0while j < n do

d := bi + 256 · bi+1
if d < 19q thenâj := dj := j + 1
end ifi := i + 2
end while
return â0 + â1 X + · · · + ân−1 X n−1
The intuition behind the function Parse is that if the input byte array is statistically close to a uniformly
random byte array, then the output polynomial is statistically close to a uniformly random element of Rq . It
represents a uniformly random polynomial in Rq because

NTT is bijective and thus maps polynomials withuniformly random coecients to polynomials with again uniformly random coecients.

7

Sampling from a binomial distribution. Noise in Kyber is sampled from a centered binomial distribution Bη for η = 2. We dene Bη as follows:2η

Sample (a1 , . . . , aη , b1 , . . . , bη ) ← {0, 1}

and output

ηX(ai − bi ).

i=1
When we write that a polynomial f ∈ Rq or a vector of such polynomials is sampled from Bη , we mean thateach coecient is sampled from Bη .
For the specication of Kyber we need to dene how a polynomial f ∈ Rq is sampled according to Bη
deterministically from 64η bytes of output of a pseudorandom function (we x n = 256 in this description).
This is done by the function CBD (for centered binomial distribution) dened as described in Algorithm 2.

Algorithm 2 CBDη : B 64η → Rq
Input: Byte array B = (b0 , b1 , . . . , b64η−1 ) ∈ B 64η
Output: Polynomial f ∈ Rq

(β0 , . . . , β512η−1 ) := BytesToBits(B)for i from 0 to 255 do

Pη−1
a := j=0 β2iη+jPη−1b := j=0 β2iη+η+j
fi := a − b

end forreturn f0 + f1 X + f2 X 2 + · · · + f255 X 255

Encoding and decoding. There are two data types that Kyber needs to serialize to byte arrays: byte
arrays and (vectors of ) polynomials. Byte arrays are trivially serialized via the identity, so we need to dene
how we serialize and deserialize polynomials. In Algorithm 3 we give a pseudocode description of the function

Decode` , which deserializes an array of 32` bytes into a polynomial f = f0 + f1 X + · · · + f255 X 255 (we again`
x n = 256 in this description) with each coecient fi in {0, . . . , 2 − 1}. We dene the function Encode` as
the inverse of Decode` . Whenever we apply Encode` to a vector of polynomials we encode each polynomial
individually and concatenate the output byte arrays.

Algorithm 3 Decode` : B 32` → Rq
Input: Byte array B ∈ B 32`
Output: Polynomial f ∈ Rq

(β0 , . . . , β256β−1 ) := BytesToBits(B)for i from 0 to 255 do

fi :=

P`−1

j
j=0 βi`+j 2

end forreturn f0 + f1 X + f2 X 2 + · · · + f255 X 255

1.2

Specication of

Kyber.CPAPKE

CPAPKE is similar to the LPR encryption scheme that was introduced (for Ring-LWE) by Lyuba-

Kyber.

shevsky, Peikert, and Regev in the presentation of [61] at Eurocrypt 2010 [62]; the description is also in thefull version of the paper [63, Sec. 1.1]. The roots of this scheme go back to the rst LWE-based encryption
scheme presented by Regev in [81, 82], with the main dierence being that the underlying ring is not Zq andboth the secret and the error vectors have small coecients. The idea of using a polynomial ring (instead ofZq ) goes back to the NTRU cryptosystem presented by Hostein, Pipher, and Silverman in [47], while thesymmetry between the secret and the error was already employed in very similar cryptographic schemes in[6, 60] with the security justication from [10].

8The main dierence from the LPR encryption scheme is to use Module-LWE instead of Ring-LWE. Also,
we adopt the approach taken by Alkm, Ducas, Pöppelmann and Schwabe in [7] for the generation of the
public matrix A.

Furthermore, we shorten ciphertexts by rounding o the low bits as in learning-with-rounding-based schemes [13, Eq. 2.1], which is a common technique for reducing ciphertext size also in
LWE-based schemes (c.f. [71, 77]).

CPAPKE is parameterized by integers n, k, q, η, du , and dv .

Parameters. Kyber.

As stated before,

throughout this document n is always 256 and q is always 3329. Furthermore, throughout this document ηis always 2. The values of k , du and dv vary for dierent security levels.
Using the notation of Subsection 1.1 we give the denition of key generation, encryption, and decryption

CPAPKE public-key encryption scheme in Algorithms 4, 5, and 6. A more high-level view ofof the Kyber.

these algorithms is given in the comments.

Algorithm 4 Kyber.CPAPKE.KeyGen(): key generation
Output: Secret key sk ∈ B 12·k·n/8
Output: Public key pk ∈ B 12·k·n/8+32

d ← B 32
2: (ρ, σ) := G(d)3: N := 0
4: for i from 0 to k − 1 do
5:for j from 0 to k − 1 do
6:Â[i][j] := Parse(XOF(ρ, j, i))
1:. Generate matrix Â ∈ Rqk×k in NTT domain

end forend for
9: for i from 0 to k − 1 do
7:
8:

10:
11:
12:
13:
14:
15:
16:

. Sample s ∈ Rqk from Bη

s[i] := CBDη (PRF(σ, N ))N := N + 1
end forfor i from 0 to k − 1 do

. Sample e ∈ Rqk from Bη

e[i] := CBDη (PRF(σ, N ))N := N + 1
end forŝ := NTT(s)18: ê := NTT(e)19: t̂ := Â ◦ ŝ + ê+
20: pk := (Encode12 (t̂ modq)kρ)+
21: sk := Encode12 (ŝ modq)
22: return (pk , sk )17:

. pk := As + e. sk := s9Algorithm 5 Kyber.CPAPKE.Enc(pk , m, r): encryption
Input: Public key pk ∈ B 12·k·n/8+32
Input: Message m ∈ B 32
Input: Random coins r ∈ B 32
Output: Ciphertext c ∈ B du ·k·n/8+dv ·n/8

N := 0t̂ := Decode12 (pk )3: ρ := pk + 12 · k · n/8
4: for i from 0 to k − 1 do
5:for j from 0 to k − 1 do
6:ÂT [i][j] := Parse(XOF(ρ, i, j))
1:
2:. Generate matrix Â ∈ Rqk×k in NTT domain

end forend for
9: for i from 0 to k − 1 do
7:
8:

10:
11:
12:
13:
14:
15:
16:

. Sample r ∈ Rqk from Bη

r[i] := CBDη (PRF(r, N ))N := N + 1
end forfor i from 0 to k − 1 do

. Sample e1 ∈ Rqk from Bη

e1 [i] := CBDη (PRF(r, N ))N := N + 1
end fore2 := CBDη (PRF(r, N ))r̂ := NTT(r)−1
19: u := NTT(ÂT ◦ r̂) + e1
−1 T
20: v := NTT(t̂ ◦ r̂) + e2 + Decompressq (Decode1 (m), 1)
21: c1 := Encoded (Compress (u, du ))qu
22: c2 := Encoded (Compress (v, dv ))qv
23: return c = (c1 kc2 ). Sample e2 ∈ Rq from Bη

17:

18:

. u := AT r + e1
. v := t r + e2 + Decompressq (m, 1)T. c := (Compressq (u, du ), Compressq (v, dv ))Algorithm 6 Kyber.CPAPKE.Dec(sk , c): decryption
Input: Secret key sk ∈ B 12·k·n/8
Input: Ciphertext c ∈ B du ·k·n/8+dv ·n/8
Output: Message m ∈ B 32

u := Decompressq (Decodedu (c), du )v := Decompressq (Decodedv (c + du · k · n/8), dv )3: ŝ := Decode12 (sk )−1 T
4: m := Encode1 (Compress (v − NTT(ŝ ◦ NTT(u)), 1))q
5: return m

1:

2:

10

. m := Compressq (v − sT u, 1))1.3

Specication of

Kyber.CCAKEM

CCAKEM IND-CCA2-secure KEM from the IND-CPA-secure public-key encryption

We construct the Kyber.

scheme described in the previous subsection via a slightly tweaked FujisakiOkamoto transform [40].

CCAKEM.

In

Algorithms 7, 8, and 9 we dene key generation, encapsulation, and decapsulation of Kyber.

Algorithm 7 Kyber.CCAKEM.KeyGen()
Output: Public key pk ∈ B 12·k·n/8+32
Output: Secret key sk ∈ B 24·k·n/8+96

z ← B 320
2: (pk , sk ) := Kyber.CPAPKE.KeyGen()0
3: sk := (sk kpk kH(pk )kz)
4: return (pk , sk )1:

Algorithm 8 Kyber.CCAKEM.Enc(pk )Input: Public key pk ∈ B 12·k·n/8+32
Output: Ciphertext c ∈ B du ·k·n/8+dv ·n/8
Output: Shared key K ∈ B ∗m ← B 32
2: m ← H(m)3: (K̄, r) := G(mkH(pk ))4: c := Kyber.CPAPKE.Enc(pk , m, r)
5: K := KDF(K̄kH(c))
6: return (c, K)
1:. Do not send output of system RNG

Algorithm 9 Kyber.CCAKEM.Dec(c, sk )Input: Ciphertext c ∈ B du ·k·n/8+dv ·n/8
Input: Secret key sk ∈ B 24·k·n/8+96
Output: Shared key K ∈ B ∗pk := sk + 12 · k · n/8
h := sk + 24 · k · n/8 + 32 ∈ B 32
3: z := sk + 24 · k · n/8 + 64
0
4: m := Kyber.CPAPKE.Dec(s, (u, v))
0 0
0
5: (K̄ , r ) := G(m kh)
0 :=
6: c
Kyber.CPAPKE.Enc(pk , m0 , r 0 )0
7: if c = c then8:
return K := KDF(K̄ 0 kH(c))
1:

2:

else
return K := KDF(zkH(c))
11: end if
12: return K
9:

10:

1.4

Kyber parameter sets

We dene three parameter sets for Kyber, which we call Kyber512, Kyber768, and Kyber1024.
parameters are listed in Table 1.

Note that the table also lists the derived parameterTheδ , which is the

CCAKEM ciphertext fails. The parameters were obtained

probability that decapsulation of a valid Kyber.
via the following approach:11

Table 1: Parameter sets for Kyber

n
Kyber512kq

η (du , dv )256 2 3329 2
256 3 3329 2
256 4 3329 2

Kyber768
Kyber1024(10, 3)(10, 4)(11, 5)

δ
−178

2
2−164
2−174

• n is set to 256 because the goal is to encapsulate keys with 256 bits of entropy (i.e., use a plaintext
size of 256 bits in Kyber.CPAPKE.Enc). Smaller values of n would require to encode multiple key bits
into one polynomial coecient, which requires lower noise levels and therefore lowers security. Larger
values of n would reduce the capability to easily scale security via parameter k .

• We choose q as a small prime satisfying n | (q − 1); this is required to enable the fast NTT-based
multiplication. There are two smaller primes for this property holds, namely 257 and 769. However,for those primes we would not be able to achieve negligible failure probability required for CCA security,
so we chose the next largest, i.e., q = 3329.

• k is selected to x the lattice dimension as a multiple of n; changing k is the main mechanism in Kyber
to scale security (and as a consequence, eciency) to dierent levels.

• The remaining parameters η , du and dv were chosen to balance between security (see Section 4),
ciphertext size, and failure probability. Note that all three parameter sets achieve a failure probability−128

of < 2

with some margin. We discuss this in more detail in Subsections 1.5 and 5.3. Also notethat η = 2 is xed for all variants, which simplies implementations.
The failure probability δ is computed with the help of the Kyber.py Python script which is available

online at https://github.com/pq-crystals/security-estimates. For the theoretical background of that
script see [22, Theorem 1].

Instantiating PRF, XOF, H, G, and KDF. What is still missing to complete the specication of Kyberis the instantiation of the symmetric primitives. We instantiate all of those primitives with functions fromthe FIPS-202 standard [68] as follows:• We instantiate XOF with SHAKE-128;• we instantiate H with SHA3-256;• we instantiate G with SHA3-512;• we instantiate PRF(s, b) with SHAKE-256(s||b); and• we instantiate KDF with SHAKE-256.
90s variant of Kyber In the 90s variant of Kyber• we instantiate XOF(ρ, i, j) with AES-256 in CTR mode, where ρ is used as the key and ikj is zeropadded to a 12-byte nonce. The counter of CTR mode is initialized to zero.
• we instantiate H with SHA-256;• we instantiate G with SHA-512;• we instantiate PRF(s, b) with AES-256 in CTR mode, where s is used as the key and b is zero-padded
to a 12-byte nonce. The counter of CTR mode is initialized to zero.
• we instantiate KDF with SHAKE-256.

12

1.5

Design rationale

The design of Kyber is based on the module version [57] of the Ring-LWE LPR encryption scheme [61]with bit-dropping [71, 77]. It is also enhanced by many of the improvements of preceding implementations oflattice-based encryption schemes such as NewHope [7]. In NewHope (and all other Ring-LWE schemes),
operations were of the form As+e where all the variables were polynomials in some ring. The main dierencein Kyber is that A is now a matrix (with a small dimension like 3) over a constant-size polynomial ringand s, e are vectors over the same ring. We refer to this as a scheme over module lattices.

The use of Module-LWE. Previous proposals of LWE-based cryptosystems either used the very structured
Ring-LWE problem (as, for example, NewHope [7]) or standard LWE (as, for example, Frodo [21]). The
main advantage of structured LWE variants based on polynomial rings is eciency in terms of both speed
and key and ciphertext sizes.

The disadvantages are concerns that the additional structure might enable

more ecient attacks and that tradeos between eciency and security can be scaled only rather coarsely.
The advantages of standard LWE is the lack of structure and easy scalability, but those come at the cost ofsignicantly decreasing eciency. Module-LWE oers a trade-o between these two extremes. In the speciccase of the Module-LWE parameters used in Kyber, we obtain somewhat reduced structure compared to
Ring-LWE, much better scalability, andwhen encrypting messages of a xed size of 256 bitsperformancevery similar to Ring-LWE-based schemes.

Active security. In [23], Bos, Costello, Naehrig, and Stebila used a passively secure KEM to migrate TLS
to transitional post-quantum security (i.e., post-quantum condentiality, but only pre-quantum authentication). Subsequent work, like NewHope [7] or Frodo [21] followed up and proposed more ecient and moreconservative instantiations of the underlying passively secure KEM. One advantage of passively secure KEMs
is that they can accept a higher failure probability (which allows to either increase security by increasing
noise or decreasing public-key and ciphertext size). The other advantage is that they do not require a CCA
transform, and therefore come with faster decapsulation. Despite these advantages, Kyber is dened as an
IND-CCA2 secure KEM only. For many applications like public-key encryption (via a KEM-DEM construction) or in authenticated key exchange active security is mandatory. However, also in use cases (like key
exchange in TLS) that do not strictly speaking require active security, using an actively secure KEM has
advantages. Most notably, it allows (intentional or accidental) caching of ephemeral keys. Furthermore, the
CCA transform of Kyber protects against certain bugs in implementations. Specically, passively secureschemes will not notice if the communication partner uses wrong noise, for example, all-zero noise. Such a
bug in the encapsulation of Kyber will immediately be caught by the re-encryption step during decapsulation. As a conclusion, we believe that the overhead of providing CCA security is not large enough to justify
saving it and making the scheme less robust.

The role of the NTT. Multiplication in Rq based on the number-theoretic transform (NTT) has multiple
advantages: it is extremely fast, does not require additional memory (like, for example, Karatsuba or Toom
multiplication) and can be done in very little code space. Consequently, it has become common practice tochoose parameters of lattice-based crypto to support this very fast multiplication algorithm. Some schemes
go further and make the NTT part of the denition of the scheme. A prominent example is again NewHope,
which samples the public value a in NTT domain and also sends public keys and ciphertexts in NTT domain
to save 2 NTTs. NewHope was not the rst scheme to do this; for earlier examples see [59, 77, 83].
In Kyber we also decided to make the NTT part of the denition of the scheme, but only in the samplingof A and the public key, not for the format of the ciphertext. A consequence of this decision is that the
NTT appears in the specication of Kyber.CPAPKE. Note that multiplications by A have to use the NTT,1

simply because Â is sampled in NTT domain . Similarly, multiplications by the public-key t̂ have to use
the NTT, because the public key is transmitted in NTT domain. As a consequence, implementations will
also want to use the NTT for all other multiplications, so we make those invocations of

NTT and NTT−1

also explicit in Alg. 4, Alg. 5, and Alg. 6. Note that also the secret key sk is stored in NTT domain.
We could have chosen to not make the NTT part of the denition of Kyber, which would have increased
simplicity of the description.

The cost for this increased simplicity would have been k

2additional NTT

operations in both key generation and encapsulation, which would result in a signicant slowdown.

We

could also have chosen to not encode the public key in NTT domain; however, this would come at the cost

1 An alternative would be to apply

NTT−1

to

Â but that would counteract the whole point of sampling A in NTT domain.

13

of additional NTTs. Finally, we could have chosen to also send the ciphertext in NTT domain; however, thiswould be incompatible with ciphertext compression via the Compressq function.

Against all authority. For the generation of the public uniformly random matrix A, we decided to adopt
the against-all-authority approach of NewHope. This means that the matrix is not a system parameterbut instead generated freshly as part of every public key. There are two advantages to this approach: First,
this avoids discussions about how exactly a uniformly random system parameter was generated. Second, it
protects against the all-for-the-price-of-one attack scenario of an attacker using a serious amount of computation to nd a short basis of the lattice spanned by A once and then using this short basis to attack allusers. The cost for this decision is the expansion of the matrix A from a random seed during key generationand encapsulation; we discuss this cost more in Subsection 2.1.

Binomial noise. Theoretic treatments of LWE-based encryption typically consider LWE with Gaussian
noise, either rounded Gaussian [81] or discrete Gaussian [25]. As a result, many early implementations also
sampled noise from a discrete Gaussian distribution, which turns out to be either fairly inecient (see, forexample, [23]) or vulnerable to timing attacks (see, for example, [26, 76, 38]). The performance of the best
known attacks against LWE-based encryption does not depend on the exact distribution of noise, but rather
on the standard deviation (and potentially the entropy). This motivates the use of noise distributions that
we can easily, eciently, and securely sample from. One example is the centered binomial distribution usedin [7].

Another example is the use of learning-with-rounding (LWR), which adds deterministic uniform

noise by dropping bits as in Kyber's

Compressq function.

In the design of Kyber we decided to use

centered binomial noise and thus rely on LWE instead of LWR as the underlying problem. The compressionof ciphertexts via Compressq introduces additional noise (making the scheme more secure), but we do notconsider this noise in our security analysis (this choice is motivated by the absence of a Ring/Module variantof a hardness reduction for LWR [13]).

Allowing decapsulation failures. Another interesting design decision is whether to allow decapsulation

CPAPKE) or choose parameters that not only have a negligible, but

failures (i.e., decryption failures in Kyber.

a zero chance of failure. The advantages of zero failure probability are obvious: CCA transforms and security
proofs become easier and we could have avoided a whole discussion of attacks exploiting decapsulation failuresin Subsection 5.3. The disadvantage of designing LWE-based encryption with zero failures is that it means
either decreasing security against attacks targeting the underlying lattice problem (by signicantly decreasing
the noise) or decreasing performance (by compensating for the loss in security via an increase of the latticedimension). The decision to allow failure probabilities of < 2−160

in all parameter sets of Kyber reects

the intuition that• decapsulation failures are a problem if they appear with non-negligible probability; but• attacks attempting to exploit failures that occur with extremely low probability as in Kyber are amuch smaller threat than, for example, improvements to hybrid attacks [49] targeting schemes withvery low noise.

Additional Hashes. In the CCA transform we hash the (hash of the) public key pk into the pre-key K̄
and into the random coins r (see line 3 of Alg. 8), and we hash the (hash of the) ciphertext into the nal key
K . These hashes would not be necessary for the security reduction (see Section 4), but they add robustness.

CCAKEM depends on the full view of exchanged messages

Specically, the nal shared key output by Kyber.

(public key and ciphertext), which means that the KEM is contributory and safe to use in authenticated key
exchanges without additional hashing of context. Hashing pk also into the random coins r adds protection
against a certain class of multi-target attacks that attempt to make use of protocol failures. This is discussed
in more detail in Subsection 5.3.

Choice of symmetric primitives. In the design of Kyber we need an extendable output function (XOF),
two hash functions, a pseudorandom function, and a KDF. We decided to rely on only one underlying
primitive for all those functions. This helps to reduce code size in embedded platforms and (for a conservative
choice) reduces concerns that Kyber could be attacked by exploiting weaknesses in one out of several
symmetric primitives. There are only relatively few extendable output functions described in the literature.
The best known ones, which also coined the term XOF, are the SHAKE functions based on Keccak [19] and14

standardized in FIPS-202 [68].

This standard conveniently also describes hash functions with the output

lengths we need; furthermore, SHAKE is designed to also work as a PRF. These properties of the FIPS-202
function family made the choice easy, but there are still two decisions that may need explanation:• We could have chosen to instantiate all symmetric primitives with only one function (e.g., SHAKE256) from the FIPS-202 standard. The choice of SHAKE-128 as instantiation of the XOF is actuallyimportant for performance; also we do not need any of the traditional security properties of hashfunctions from SHAKE-128, but rather that the output looks uniformly random. In an earlier versionof Kyber we instantiated H, G, and PRF all with SHAKE-256. We decided to change this to dierent
functions from the FIPS-202 family to avoid any domain-separation discussion. Note that this decision
increases code-size at most marginally: all 4 functions can be obtained by a call to a Keccak function
with appropriate arguments (see, for example, [18]).

• We could have decided to use KMAC from NIST Special Publication 800-185 to instantiate the PRF.
We decided against this, because it would increase the numbers of Keccak permutations required in
the generation of the noise polynomials and thus noticeably and unnecessarily decrease performance.
As a modication in round-2, we derive the nal key using SHAKE-256 instead of SHA3-256. This is anadvantage for protocols that need keys of more than 256 bits. Instead of rst requesting a 256-bit key from

Kyber and then expanding it, they can pass an additional key-length parameter to Kyber and obtain a
key of the desired length. This feature is not supported by the NIST API, so in our implementations we set
the keylength to a xed length of 32 bytes in api.h.

Choice of symmetric primitives in the 90s variant The 90s variant of Kyber uses symmetricprimitives that are standardized by NIST and accelerated in hardware on a large variety of platforms. These
two criteria narrow the choice to AES and SHA-256, which are, for example, implemented in hardware on
recent Intel, AMD, and ARM processors. A natural choice for the hash function G with 512-bit output isSHA-512 from the same SHA-2 family of hash functions as SHA-256.

Supporting non-incremental hash APIs. In line 3 of Alg. 8 we feed H(pk ) (instead of pk ) into G andin line 5 we feed H(c) (instead of c) into H.

Using H(pk ) in the call to G enables a small speedup for

decapsulation as described in Subsection 2.1. However, there is another reason why we rst hash pk and c,
namely that it simplies implementing Kyber with a non-incremental hash API. If Kyber is implemented
in an environment which already oers a library for hashing, but only oers calls of the form h = H(m), thenproducing a hash of the form h = H(m1 km2 ) would rst require copying m1 and m2 into one consecutive
area of memory. This would require unnecessary copies and, more importantly, additional stack space. Such
non-incremental hash APIs are not uncommon: one example is the API of NaCl [17].

Return value for decapsulation failure. Traditionally the FO transform returns ⊥ (i.e., a special failure
symbol) when decapsulation fails. We use a variant that instead sets the resulting shared key to a pseudorandom value computed as the hash of a secret z and the ciphertext c. This variant of the FO transformwas proven secure in [48]. In practice it has the advantage that implementations of Kyber's decapsulation
are safe to use even if higher level protocols fail to check the return value. As a consequence of this implicit

rejection approach, our implementations of decapsulation always return 0.

2 Performance analysis
In this section we consider implementational aspects of Kyber and report performance results of two implementations: the ANSI C reference implementation requested by NIST and an implementation optimized using

AVX2 vector instructions. included in the submission package under Additional_Implementations/avx2/.
We remark that the optimized implementation in ANSI C in subdirectory Optimized_Implementation/, asrequested by the Call for Proposals, is a copy of the reference implementation.

The big picture of Kyber performance. Thanks to the extremely ecient NTT-based multiplication andsampling of A in NTT domain, the performance of Kyber is largely determined by the performance of thesymmetric primitives. This is illustrated, for example, by the fact that the AVX2-optimized implementationof the 90s variant of Kyber is almost a factor fo 2 faster than Kyber with symmetric primitives based on

15

Keccak.

This dierence is going to be even larger on systems with hardware-accelerated SHA-256.

It isalso illustrated by the fact that for optimized implementations decapsulation is faster than encapsulation,although it contains a re-encapsulation from the FO transform. The reason is that decapsulation can save,for example, computing H(pk ) and sampling the 32 bytes of randomness.

2.1

Implementation considerations and tradeos

Implementing the NTT. Many dierent tradeos are possible when implementing the number-theoretictransform. The most important ones are between code size (which becomes mainly relevant on embedded
processors) and speed.

The two implementations of Kyber included in the submission package have a

dedicated forward NTT (from normal to bitreversed order) and inverse NTT (from bitreversed to normal
order). Also, both implementations use precomputed tables of powers of ζ . What is particularly interesting
about using the NTT on embedded platforms is that the multiplication of two elements of

Rq can becomputed without any additional temporary storage. What is particularly interesting about using the NTT
on large processors is that it is extremely eciently vectorizable. Since 2013, the most ecient approach tocompute the NTT on 64-bit Intel processors was to represent coecients as double-precision oating-pointvalues [44, 7].

In our AVX2-optimized implementation of Kyber, we show that carefully optimizing the

NTT using AVX2 integer instructions results in much better performance.

Specically, on Intel HaswellCPUs one forward NTT in Kyber takes only about 320 cycles; an inverse NTT takes only about 290 cycles.

Keccak. The second speed-critical component inside Kyber are the symmetric primitives, i.e., SHA3-256,
SHA3-512, SHAKE-128, and SHAKE-256, all based on the Keccak permutation. SHA3 has the reputation to
not be the fastest hash function in software (see, for example, [56]). To some extent this is compensated by thefact that most calls to Keccak are parallel and thus very eciently vectorizable. Our AVX2 implementation
makes use of this fact. Also, ARM recently announced that future ARMv8 processors will have hardware
support for SHA3 [43], so there is a good chance that at least on some architectures, software performanceof SHA3 will not be an issue in the future.

AES and SHA-2. To illustrate what performance Kyber can achieve with hardware accelerated symmetricprimitives we include the 90s variant using AES, SHA256 and SHA512 instead of symmetric primitives basedon Keccak. This variant is interesting only if at least AES is accelerated in hardware as constant-time software
implementations (required for the use of AES as a PRF) are not faster than parallel Keccak.

Hardware-RNGs for key generation. During key generation, the generation of s and e is performed
using SHAKE-256 (and AES in the 90s variant). However, this is not required. The choice of RNG during
key generation is a local decision that any user and platform can make independently.

In particular on

platforms with fast hardware AES one can adapt the AES-based PRF from the 90s variant also for theotherwise Keccak-based Kyber.

We considered using this in our AVX2 implementation, but using thisoptimization means that testvectors would not match between our two implementations. This is not an issue
in actual deployments, where randombytes is not deterministic.

Caching of ephemeral keys. Applications that are even more conscious of key-generation time can decideto cache ephemeral keys for some time. This is enabled by the fact that Kyber is IND-CCA2 secure.

Tradeos between secret-key size and speed. It is possible to use dierent tradeos between secretkey size and decapsulation speed.

If secret-key size is critical, it is of course possible to not store H(pk)and also to not store the public key as part of the secret key but instead recompute it during decapsulation.
Furthermore, not keeping the secret key in

NTT domain makes it possible to compress each coecient to only

5 bits, resulting in a total size of only 320 bytes for the three polynomials. This has the additional advantagethat it makes key recovery via cold-boot attacks [45] somewhat harder [3].

Finally, as all randomness in

key generation is generated from two 32-byte seeds, it is also possible to only store these seeds and re-run
key generation during decapsulation. When opting for such 32-byte secret keys, the re-encapsulation step of
decapsulation can save the expansion of the matrix A, is it is already expanded (in transposed form) in key
generation.
In the other direction, if secret-key size does not matter very much and decapsulation speed is critical,
one might decide to store the expanded matrix A as part of the secret key and avoid recomputation fromthe seed ρ during the re-encapsulation part of decapsulation.

16

Both implementations included in the submission package use the secret-key format described in Algorithm 7, i.e., with polynomials in

NTT domain, including the public key and H(pk), but not including thematrix A.

Local storage format of static public keys. A user who is frequently encapsulating messages to thesame public key can speed up encapsulation by locally storing an expanded public key containing the matrix

A and H(pk ). This saves the cost of expanding the matrix A from the seed ρ and the cost of hashing pk inevery encapsulation.

2.2

Performance of reference and AVX2 implementations

Table 2 reports performance results of the reference implementation and of our implementation optimized
using AVX2 vector instructions, also including performance results for the 90s variant of Kyber. All benchmarks were obtained on one core of an Intel Core i7-4770K (Haswell) processor clocked at 3500.000 MHz (asreported by /proc/cpuinfo) with TurboBoost and hyperthreading disabled. The benchmarking machine has
32 GB of RAM and is running Debian GNU/Linux with Linux kernel version 4.9.0. Both implementations
were compiled with gcc version 6.3.0. We used compiler ags -O3-fomit-frame-pointer -march=native-fPIC. to compile both implementations. All cycle counts reported are the median of the cycle counts of
10 000 executions of the respective function. The implementations are not optimized for memory usage, but
generally Kyber has only very modest memory requirements. This means that in particular our implementations do not need to allocate any memory on the heap.

3 Known Answer Test values
All KAT values are included in subdirectories of the directory KAT of the submission package. Specically, theKAT values of Kyber512 are in the subdirectory KAT/kyber512; the KAT values of the Kyber512-90s arein the subdirectory KAT/kyber512-90s; the KAT values of Kyber768 are in the subdirectory KAT/kyber768;
the KAT values of the Kyber768-90s are in the subdirectory KAT/kyber768-90s; the KAT values of Ky-

ber1024 are in the subdirectory KAT/kyber1024; and the KAT values of the Kyber1024-90s are in thesubdirectory KAT/kyber1024-90s. Each of those directories contains the KAT values as generated by the

PQCgenKAT_kem program provided by NIST. Specically, those les are:
• KAT/kyber512/PQCkemKAT_1632.req,• KAT/kyber512/PQCkemKAT_1632.rsp,• KAT/kyber512-90s/PQCkemKAT_1632.req,• KAT/kyber512-90s/PQCkemKAT_1632.rsp,• KAT/kyber768/PQCkemKAT_2400.req,• KAT/kyber768/PQCkemKAT_2400.rsp,• KAT/kyber768-90s/PQCkemKAT_2400.req,• KAT/kyber768-90s/PQCkemKAT_2400.rsp,• KAT/kyber1024/PQCkemKAT_3168.req,• KAT/kyber1024/PQCkemKAT_3168.rsp,• KAT/kyber1024-90s/PQCkemKAT_3168.req, and• KAT/kyber1024-90s/PQCkemKAT_3168.rsp,

17

Table 2:

Key and ciphertext sizes and cycle counts for all paramter sets of Kyber.

Cycle counts wereobtained on one core of an Intel Core i7-4770K (Haswell); ref  refers to the C reference implementation,
AVX2 to the implementation using AVX2 vector instructions; sk stands for secret key, pk for public key,and ct for ciphertext. In parenthesis are approximate values when including key generation in decapsulation
to avoid having to store expanded secret keys. In this scenario, we only store the initial seed d in line 1 ofAlgorithm 4. The approximate cycle counts for this scenario are computed as the sum of cycle counts forstandard decapsulation and key generation minus the number of cycles require to generate the matrix A fromthe public seed ρ. Note that this is a very conservative estimate; actual implementations of the approach canalso save, for example, sampling the 32 bytes of randomness. See also the discussion on tradeos between
secret-key size and speed in Subsection 2.1.

Kyber512

Sizes (in Bytes)

Haswell Cycles (ref )Haswell Cycles (AVX2)

sk:

gen:

gen:

pk:
ct:

1632 (or 32)
800
736

enc:
dec:

118044161440190206 (or ≈ 279150)

enc:
dec:

33428
49184
40564 (or ≈ 62292)

Kyber512-90s

Sizes (in Bytes)

Haswell Cycles (ref )Haswell Cycles (AVX2)

sk:

gen:

gen:

pk:
ct:

1632 (or 32)
800
736

enc:
dec:

232368285336313452 (or ≈ 436088)

enc:
dec:

20004
30384
24604 (or ≈ 40304)

Kyber768

Sizes (in Bytes)

Haswell Cycles (ref )Haswell Cycles (AVX2)

sk:

gen:

gen:

pk:
ct:

2400 (or 32)
1184
1088

enc:
dec:

217728272254315976 (or ≈ 469008)

62396
enc:
83748
dec: 70304 (or ≈ 102652)

Kyber768-90s

Sizes (in Bytes)

Haswell Cycles (ref )Haswell Cycles (AVX2)

sk:

gen:

gen:

pk:
ct:

2400 (or 32)
1184
1088

enc:
dec:

451018514088556972 (or ≈ 758934)

enc:
dec:

30884
45892
37844 (or ≈ 58668)

Kyber1024

Sizes (in Bytes)

Haswell Cycles (ref )Haswell Cycles (AVX2)

sk:

gen:

gen:

pk:
ct:

3168 (or 32)
1568
1568

enc:
dec:

331418396928451096 (or ≈ 667596)

88568
enc:
115952
dec: 99764 (or ≈ 139552)

Kyber1024-90s

Sizes (in Bytes)

Haswell Cycles (ref )Haswell Cycles (AVX2)

sk:

gen:

gen:

pk:
ct:

3168 (or 32)
1568
1568

735382
enc:
810398dec: 860272 (or ≈ 1148394)

18

enc:
dec:

44040
64352
54448 (or ≈ 82444)

4 Expected security strength
4.1

Security denition

CCAKEM (or short, Kyber) is an IND-CCA2-secure key encapsulation mechanism, i.e., it fullls

Kyber.

the security denition stated in Section 4.A.2 of the Call for Proposals.

4.2

Rationale of our security estimates

Our estimates of the security strength for the three dierent parameter sets of Kyberand consequently
the classication into security levels as dened in Section 4.A.5 of the Call for Proposalsare based on thecost estimates of attacks against the underlying module-learning-with-errors (MLWE) problem as detailedin Subsection 5.1.
To justify this rationale, we will in the following give two reductions from MLWE: a tight reduction in
the random-oracle model (ROM) in Theorem 2 and a non-tight reduction in the quantum-random-oracle
model (QROM) in Theorem 3.

With those reductions at hand, there remain two avenues of attack thatwould break Kyber without solving the underlying MLWE problem, namely
1. breaking one of the assumptions of the reductions, in particular attacking the symmetric primitives
used in Kyber; or
2. exploiting the non-tightness of the QROM reduction.
We briey discuss 1.)

in Subsection 5.2.

The discussion of 2.)

requires considering two separate issues,

namely• a (quadratic) non-tightness in the decryption-failure probability of Kyber.CPAPKE, and• a (quadratic) non-tightness between the advantage of the MLWE attacker and the quantum attacker
against Kyber.
In Subsection 5.3 we discuss quantum attacks exploiting decryption failures and in the presentation of the
non-tight QROM reduction we explain why the non-tightness between quantum attacks against MLWE
and quantum attacks against Kyber is unlikely to matter in practice. More specically, we show how to

CPAPKEeliminate this non-tightness if we allow the reasonable, but non-standard, assumption that Kyber.

ciphertexts are pseudorandom, even if all randomness is generated pseudorandomly from a hash of theencrypted message.

4.3

Security Assumption

The hard problem underlying the security of our schemes is Module-LWE [24, 57]. It consists in distinguishing(ai , bi ) ← Rqk × Rq from samples (ai , bi ) ∈ Rqk × Rq where ai ← Rqk is uniform andbi = aTi s + ei with s ← Bηk common to all samples and ei ← Bη fresh for every sample. More precisely, formlwe
an algorithm A, we dene Advm,k,η (A) =uniform samples


Pr b0 = 1 :4.3.1

A ← Rqm×k ; (s, e) ← βηk × βηm ;b = As + e; b0 ← A(A, b)− Pr b0 = 1 :A ← Rqm×k ; b ← Rqm ; b0 ← A(A, b).

Tight reduction from MLWE in the ROM

CPAPKE is tightly IND-CPA secure under the Module-LWE hardness assumption.

We rst note that Kyber.

Theorem 1. Suppose XOF and G are random oracles. For any adversary A, there exist adversaries B andmlwe
C with roughly the same running time as that of A such that Advcpa
Kyber.CPAPKE (A) ≤ 2 · Advk+1,k,η (B) +prf
AdvPRF (C).

19

The proof of this theorem is easily obtained by noting that, under the MLWE assumption, public-key
and ciphertext are pseudo-random.

CCAKEM is obtained via a slightly tweaked Fujisaki-Okamoto transform [48, 40] applied to
CPAPKE. The following concrete security statement proves Kyber.CCAKEM's IND-CCA2-security

Kyber.
Kyber.

when the hash functions G and H are modeled as random oracles. It is obtained by combining the genericbounds from [48] with Theorem 1 (and optimizing the constants appearing in the bound).

Theorem 2. Suppose XOF, H, and G are random oracles. For any classical adversary A that makes at mostqRO many queries to random oracles XOF, H and G, there exist adversaries B and C of roughly the samerunning time as that of A such thatprf
mlwe
AdvccaKyber.CCAKEM (A) ≤ 2Advk+1,k,η (B) + AdvPRF (C) + 4qRO δ.
Note that the security bound is tight. The negligible additive term 4qRO δ stems from Kyber.CPAPKE's
decryption-failure probability δ .

4.3.2

Non-tight reduction from MLWE in the QROM

As for security in the quantum random oracle model (QROM), [48, 84] proved that Kyber.CCAKEM is INDCCA2 secure in the QROM, provided that Kyber.CPAPKE is IND-CPA secure. A slightly tighter reduction
can be obtained by requiring the base scheme Kyber.CPAPKE to be pseudo-random. Pseudo-randomness[84] requires that, for every message m, a (randomly generated) ciphertext (c1 , c2 ) ← Kyber.CPAPKE.Enc(pk , m)is computationally indistinguishable from a random ciphertext of the form (Compressq (u, du ), Compressq (v, dv )),for uniform (u, v). (We also require the property of statistical disjointness [84] which is trivially fullled for

Kyber.CPAPKE.) The proof of Kyber.CPAPKE's IND-CPA security indeed shows that Kyber.CPAPKE istightly pseudo-random under the Module-LWE hardness assumption.

Theorem 3. Suppose XOF, H, and G are random oracles. For any quantum adversary A that makes atmost qRO many queries to quantum random oracles XOF, H and G, there exist quantum adversaries B and

C of roughly the same running time as that of A such thatqprf
2
Advmlwe(A)≤
4q·
AdvccaRO
k+1,k,η (B) + AdvPRF (C) + 8qRO δ.
Kyber.CCAKEM
Unfortunately, the above security bound is non-tight and therefore can only serve as an asymptotic
indication of Kyber.CCAKEM's CCA-security in the quantum random oracle model.

Tight reduction under non-standard assumption. We can use [48, 84] to derive a tight security
bound in the QROM from a non-standard security assumption, namely that a deterministic version of

CPAPKE, is pseudo-random in the QROM. Deterministic Kyber.CPAPKE

Kyber.CPAPKE, called DKyber.

is dened as Kyber.CPAPKE, but the random coinsfrom the message m as r:= G(m).

r used in encryption are derived deterministicallyPseudo-randomness for deterministic encryption states that an en-

cryption (c1 , c2 ) of a randomly chosen message is computationally indistinguishable from a random ciphertext (Compressq (u, du ), Compressq (v, dv )), for uniform (u, v). In the classical ROM, pseudo-randomness of

DKyber.CPAPKE is tightly equivalent to MLWE but in the QROM the reduction is non-tight (and is thereason for the term qRO ·qAdvmlwe
k+1,k,η (B) in Theorem 3). Concretely, we obtain the following bound:

pr
prf
mlwe
2
AdvccaKyber.CCAKEM (A) ≤ 2Advk+1,k,η (B) + AdvDKyber.CPAPKE (C) + AdvPRF (D) + 8qRO δ.
We remark that we are not aware of any quantum attack on deterministic Kyber.CPAPKE that performs
better than breaking the MLWE problem.

4.4

Estimated security strength

Table 3 lists the security levels according to the denition in Section 4.A.5 of the Call for Proposals for thedierent parameter sets of Kyber. Our claims are based on the cost estimates of the best known attacks

20

Table 3:Classical and quantum core-SVP hardness of the dierent proposed parameter sets of Kyber

together with the claimed security level as dened in Section 4.A.5 of the Call for Proposals. Complexities
are given in terms of the base-2 logarithm of the number of operations.
core-SVP (classical)

core-SVP (quantum)

Claimed security level

Kyber512

111

100

1 (AES-128)

Kyber768

181

164

3 (AES-192)

Kyber1024

254

230

5 (AES-256)

against the MLWE problem underlying Kyber as detailed in Subsection 5.1. Specically we list the classicaland the quantum core-SVP hardness and use those to derive security levels.

The impact of MAXDEPTH. The best known quantum speedups for the sieving algorithm, which we
consider in our cost analysis (see Subsection 5.1.1), are only mildly aected by limiting the depth of aquantum circuit, because it uses Grover search on sets of small size (compared to searching through thewhole keyspace of AES). For the core-SVP-hardness operation estimates to match the quantum gate costof breaking AES at the respective security levels, a quantum computer would need to support a maximum
depth of 7080. When limiting the maximum depth to smaller values, or when considering classical attacks,
the core-SVP-hardness estimates are smaller than the gate counts for attacks against AES. We discuss thisdierence in the following.

Gates to break AES vs. core-SVP hardness. The classical core-SVP hardness of the MLWE problem
underlying Kyber diers by a factor of ≈ 2

30from the gate count to classically break the corresponding

AES instances. The core-SVP hardness is a very conservative lower bound on the cost of an actual attack
against the MLWE problem (for details, see Subsection 5.1). Specically, the core-SVP-hardness ignores• the (polynomial) number of calls to the SVP oracle that are required to solve the MLWE problem;• the gate count required for one operation;• additional cost of sieving with asymptotically subexponential complexity;• the cost of access into exponentially large memory; and• the additional rounding noise (the LWR problem, see [13, 8]), i.e. the deterministic, uniformly distributed noise introduced in ciphertexts via the Compressq function.
The state of research into SVP-solving algorithms is way too premature to assign meaningful cost estimates to each of those items.

However, it seems clear that in any actual implementation of an attack

30

algorithm the product of the cost of those items will exceed 2. See also the paragraph How conservativeis this analysis? in Subsection 5.1.4.

4.5

Additional security properties

4.5.1

Forward secrecy.

Kyber has a very ecient key-generation procedure (see also Section 2) and is therefore particularly well
suited for applications that use frequent key generations to achieve forward secrecy.

4.5.2

Side-channel attacks.

Timing attacks. Neither straight-forward reference implementations nor optimized implementations ofKyber use any secret-dependent branches or table lookups2 .This means that typical implementations ofKyber are free from the two most notorious sources of timing leakage. Another possible source of timing
2 Note that the rejection sampling in generating the matrix A does not involve any secret data.

21

leakage are non-constant-time multipliers like the UMULL instruction on ARM Cortex-M3 processors, which
multiplies two 32-bit integers to obtain a 64-bit result. However, multiplications in Kyber have only 16-bit
inputs, and most non-constant-time multipliers show timing variation only for larger inputs. For example, on
ARM Cortex-M3 processors the obvious way to implement multiplications in Kyber is through the constant-time MUL instruction, which multiplies two 32-bit integers, but returns only the bottom 32-bits of the result.
What remains as a source of timing leakage are modular reductions, which are sometimes implemented via
conditional statements. However, timing leakage in modular reductions is easily avoided by using (faster)Montgomery [67] and Barrett reductions [14] as illustrated in our reference and AVX2 implementations.
We note that the 90s variant is only really attractive to use if AES hardware support is available.

If

hardware support is not available, then table-based implementations of AES are notorious for leaking secrets
trough cache timing. In our C reference implementation of the 90s variant we use a constant-time bitsliced
implementation of AES, which is based on code from BearSSL [78].

Dierential attacks. We expect that any implementation of Kyber without dedicated protection againstdierential power or electromagnetic radiation (EM) attacks will be vulnerable to such attacks. This is truefor essentially any implementation of a cryptographic scheme that uses long-term (non-ephemeral) keys.
Deployment scenarios of Kyber in which an attacker is assumed to have the power to mount such an attack
require specially protectedtypically maskedimplementations. In [70], Oder, Schneider, Pöppelmann, andGüneysu present such a masked implementation of Ring-LWE decryption with a CCA transform very similar
to the one used in Kyber. The implementation targets Cortex-M4F microcontrollers; the conclusion of thework is that protecting the decryption (decapsulation) step against rst-order DPA incurs an overhead of
about about a factor of 5.5. The techniques presented in that paper also apply to Kyber and we expectthat the overhead for protecting Kyber against dierential attacks is in the same ballpark.

Template attacks. Protections against dierential attacks do not help if an attacker is able to recover even
ephemeral secrets from a single power or EM trace. At CHES 2017, Primas, Pessl, and Mangard presented
such a single-trace attack against an implementation of Ring-LWE on a Cortex-M4F microcontroller [79].
The attacker model in this attack is rather strong: it is the typical setting of template attacks, which assumes
an attacker who is able to generate template traces on known inputs on a device with leakage very similar
to the actual target device. In [79], the authors used the same device for generating target traces and in theattack. The attack was facilitated (maybe even enabled) by the fact that the implementation under attack
used variable-time modular reductions. Consequently, the paper states that One of the rst measures tostrengthen an implementation against SPA attacks is to ensure a constant runtime and control ow . This is
the case for all implementations of Kyber. The attack from [79] would thus certainly not straight-forwardly
apply to implementations of Kyber, but more research is required to investigate whether also constant-time
implementations of Kyber (and other lattice-based schemes) succumb to template attacks, and what thecost of suitable countermeasures is.

4.5.3

Multi-target attacks

Our security analysis makes no formal claims about security bounds in the multi-target setting. However,in the design of Kyber we made two decisions that aim at improving security against attackers targeting
multiple users:• We adopt the against-all-authority approach of re-generating the matrix A for each public key from
NewHope [7]. This protects against an attacker attempting to break many keys at the cost of breaking
one key.

• In the CCA transform (see Alg. 8) we hash the public key into the pre-key K̄ and the coins r. Making
the coins r dependent of the public key protects against precomputation attacks that attempt to break
one out of many keys. For details, see Subsection 5.3.

4.5.4

Misuse resilience

The rst, and most important, line of defense against misuse is the decision to make IND-CCA2 security
non-optional. As discussed in Subsection 1.5, it would have been possible to achieve slightly shorter public

22

keys and ciphertexts, and faster decapsulation, in a CPA-secure variant of Kyber. Using IND-CCA2 security
by default makes it safe to use Kyber with static keys and as a consequence also to re-use ephemeral keys
for some time. What is not safe, is to reuse the same randomness in encapsulation, but that randomness isalso not exposed to the outside by the API. The CCA transform has a second eect in terms of robustness:
it protects against a broken implementation of the noise sampling. A rather peculiar aspect of LWE-based
cryptography is that it will pass typical functional tests even if one communication partner does not add any
noise (or by accident samples all-zero noise). The deterministic generation of noise via SHAKE-256 during
encapsulation and the re-encryption step during decapsulation will reveal such an implementation mistake
immediately.
An additional line of defense against misuse is to hash the public-key into the pre-key

K̄ and thus

make sure that the KEM is contributory. Only few protocols require a KEM to be contributory and those
protocols can always turn a non-contributory KEM into a contributory one by hashing the public key into
the nal key. Making this hash part of the KEM design in Kyber ensures that nothing will go wrong on
the protocol level if implementers omit the hash there.
A similar statement holds for additionally hashing the ciphertext into the nal key. Several protocols
need to ensure that the key depends on the complete view of exchanged protocol messages.

This is thecase, for example, for the authenticated-key-exchange protocols described in the Kyber paper [22, Sec. 5].
Hashing the full protocol view (public key and ciphertext) into the nal key already as part of the KEM
makes it unnecessary (although of course still safe) to take care of these hashes on the higher protocol layer.

5 Analysis with respect to known attacks
5.1

Attacks against the underlying MLWE problem

MLWE as LWE. The best known attacks against the underlying MLWE problem in Kyber do not makeuse of the structure in the lattice. We therefore analyze the hardness of the MLWE problem as an LWE
problem. We briey discuss the current state of the art in algebraic attacks, i.e., attacks that exploit thestructure of module lattices (or ideal lattices) at the end of this subsection.

5.1.1

Attacks against LWE.

Many algorithms exist for solving LWE (for a survey see [5]), but many of those are irrelevant for ourparameter set. In particular, because there are only m = (k + 1)n LWE samples available to the attacker,
we can rule out BKW types of attacks [51] and linearization attacks [11]. This essentially leaves us with two
BKZ [85, 29] attacks, usually referred to as primal and dual attacks that we will recall in Subsections 5.1.2
and 5.1.3.
The algorithm BKZ proceeds by reducing a lattice basis using an SVP oracle in a smaller dimension b.
It is known [46] that the number of calls to that oracle remains polynomial, yet concretely evaluating thenumber of calls is rather painful, and this is subject to new heuristic ideas [29, 28, 9]. We choose to ignore
this polynomial factor, and rather evaluate only the core SVP hardness, that is the cost of one call to an
SVP oracle in dimension b, which is clearly a pessimistic estimation (from the defender's point of view).
This approach to deriving a conservative cost estimate for attacks against LWE-based cryptosystems wasintroduced in [7, Sec. 6].

Enumeration vs. sieving. There are two algorithmic approaches for the SVP oracle in BKZ: enumerationand sieving algorithms. These two classes of algorithms have very dierent performance characteristics and,in particular for sieving, it is hard to predict how practical performance scales from lattice dimensions thathave been successfully tackled to larger dimensions that are relevant in attacks against cryptosystems like

Kyber. The starting point of such an analysis is the fact that enumeration algorithms have super-exponential
running time, while sieving algorithms have only exponential running time.

Experimental evidence fromtypical implementations of BKZ [42, 29, 33] shows that enumeration algorithms are more ecient in small
dimensions, so one question is at what dimension sieving becomes more ecient. So far it seems that sieving
is slower in practice for accessible dimensions of up to b ≈ 130. However, a recent work [35] showed (in the23classical setting) that sieving techniques can be sped up in practice for exact-SVP, being now less than anorder of magnitude slower than enumeration already in dimension 60 to 80.
The analysis is complicated by the fact that sieving algorithms are much more memory intensive than
enumeration algorithms. Specically, sieving algorithms have exponential complexity not only in time, butalso in memory, while enumeration algorithms require only small amounts of memory.

In practice, thecost of access to memory increases with the size of memory, which typically only becomes noticeable oncethe memory requirement exceeds fast local memory (RAM). There is no study, yet, that investigates thealgorithmic optimization and practical performance of sieving using slow background storage.
We follow the approach of [7, Sec. 6] to obtain a conservative lower bound on the performance of bothsieving and enumeration for the dimensions that are relevant for the cryptanalysis of Kyber. This approachworks in the RAM model, i.e., it assumes that access into even exponentially large memory is free. Under thisassumption sieving becomes more ecient than even sophisticated enumeration, with serious optimization
as described in [29] and with quantum speedups, for dimensions larger than 250, quite possibly alreadyearlier. The smallest dimension that we are interested in for the cryptanalysis of Kyber is 390, so that theperformance of sieving in the RAM model serves as a conservative lower bound for the performance of bothenumeration and sieving.
A lot of recent work has pushed the eciency of the original lattice sieve algorithms [69, 66], improving
the heuristic complexity from (4/3)

b+o(b)≈ 20.415b down topb+o(b)≈ 20.292b using Locality Sensitive

3/2

Hashing (LSH) techniques [54, 16]. The hidden sub-exponential factor is known to be much greater than
one in practice. Again, we ignore this factor to arrive at a security estimate with a conservative margin.
Most of the sieving algorithms have been shown [55, 53] to benet from Grover's quantum search algorithm,
bringing the complexity down to 2

0.265b. We will use 2

0.292b0.265bas the classical and 2

and the quantum

cost estimate of both the primal and dual attacks with block size (dimension) b. We recall those two attacks
in the following.

5.1.2

Primal attack.

The primal attack consists of constructing a unique-SVP instance from the LWE problem and solving it using
BKZ. We examine how large the block dimension b is required to be for BKZ to nd the unique solution. Givenm+kn+1the matrix LWE instance (A, b = As+e) one builds the lattice Λ = {x ∈ Zof dimension d = m+kn+1, volume qm: (A|Im |−b)x =√0 mod q}
kn + m.

, and with a unique-SVP solution v = (s, e, 1) of norm λ ≈ ςNote that the number of used samples m may be chosen between 0 and (k+1)n in our case and we numerically
optimize this choice.

Success condition. We model the behavior of BKZ using the geometric series assumption (which is known
to be optimistic from the attacker's point of view), that nds a basis whose Gram-Schmidt norms are given?

· Vol(Λ)1/d , where δ = ((πb)1/b · b/2πe)1/2(b−1) [28, 5]. The unique short vector v will be
detected if the projection of v onto the vector space spanned by the last b Gram-Schmidt vectors is shorter√?
than bd−b . Its projected norm is expected to be ς b, that is the attack is successful if and only if

by kbi k = δ

d−2i−1√ς b ≤ δ 2b−d−1 · q m/d .

(5)

We note that this analysis introduced in [7] diers and is more conservative than prior works, which weretypically based on the hardness of unique-SVP estimates of [41]. The validity of the new analysis has beenconrmed by further analysis and experiments in [4].

5.1.3

Dual attack0= {(x, y) ∈ Zm × Zkn : At x =y mod q}. Assume we have found a vector (x, y) of length ` and compute z = vt · b = vt As + vt e =wt s + vt e mod q , which is distributed as a Gaussian of standard deviation `ς if (A, b) is indeed an LWE
sample (otherwise it is uniform mod q ). Those two distributions have maximal variation distance bounded2 2by  = 4 exp(−2π τ ), where τ = `ς/q , that is, given such a vector of length ` one has an advantage  against
The dual attack consists of nding a short vector in the dual lattice w ∈ Λdecision-LWE.

24

Table 4:Classical and quantum core-SVP hardness of the MLWE problem (treated as LWE problem)

underlying Kyber for dierent proposed parameter sets. The value b denotes the block dimension of BKZ(i.e., the dimension of the SVP considered in the core-SVP-hardness estimates), and m the number of usedsamples. Cost is given in log2 of operations and is the smallest cost for all possible choices of m and b.

bm

Primal attack:

385

Dual attack:380

Primal attack:625

Dual attack:620

Primal attack:880

Dual attack:870

Core-SVP (classical)

Core-SVP (quantum)

410

112

102

455

111

100

655

182

165

650

181

164

795

257

233

795

254

230

Kyber512

Kyber768

Kyber1024

0

The length ` of a vector given by the BKZ algorithm is given by ` = kb0 k. Knowing that Λ has dimension

d = m + kn and volume qkn

we get ` = δ

d−1 kn/dq. Therefore, obtaining an -distinguisher requires running

BKZ with block dimension b, where− 2π 2 τ 2 ≥ ln(/4).

(6)

Note that small advantages  are not relevant since the agreed key is hashed: an attacker needs an advantage
of at least 1/2 to signicantly decrease the search space of the agreed key. He must therefore amplify his
success probability by building about 1/0.2075b2

2

many such short vectors. Because the sieve algorithms provides

vectors, the attack must be repeated at least R times whereR = max(1, 1/(20.2075b 2 )).
This makes the conservative assumption that all the vectors provided by the Sieve algorithm are as short as
the shortest one.

5.1.4

Core-SVP hardness of Kyber

In Table 4 we list the classical and quantum core-SVP-hardness of the three parameter sets of Kyber. The
lower bounds of the cost of the primal and dual attack were computed following the approach outlined above

using the analysis script Kyber.py that is available online at https://github.com/pq-crystals/kyber/tree/master/scripts/.

How conservative is this analysis? The core-SVP-hardness estimates give a lower bound on the costof actual attacks rather than attempting to assign costs to various building blocks that require further
study. To give an idea of how far this lower bound is from recent estimates that attempt to nd a tighter
bound, consider the example of the BCNS key exchange [23].

In [7, Table 6], the NewHope paper

computes the classical core-SVP hardness for the parameters used in [23] as 2
security level for those parameters in [23] is 2

128

86

.

The claimed classical. Note that [7] does not contradict this claim, the factor of

2128 /286 = 242 rather indicates how conservative the core-SVP hardness estimate is. As a second example,
consider another commonly used tool for estimating (classical) security of LWE-based cryptosystems, namely
the lwe-estimator script by Albrecht [1].

140

security of 2

for Kyber512, 2

211

Applied to the Kyber parameter sets it estimates a classical285

for Kyber768, and 2

for Kyber1024. Note that also these estimatescount number of operations rather than gates, and are in the RAM model, i.e., ignore the cost of memory
access for sieving.

25

5.1.5

Algebraic attacks.

While the best known attacks against the MLWE instance underlying Kyber do not make use of thestructure in the lattice, we still discuss the current state of the art of such attacks. Most noticeably, several
recent works propose new quantum algorithms against Ideal-SVP [37, 27, 20, 31, 32], i.e., solving the shortest
vector problem in ideal lattices. The work of [32] mentions obstacles towards a quantum attack on Ring-LWE
from their new techniques, but nevertheless suggests using Module-LWE, as it plausibly creates even moreobstacles. In [2], Albrecht and Deo establish a reduction from MLWE to RLWE, whose implication is thata polynomial-time algorithm against RLWE with certain parameters would translate to a polynomial-timealgorithm against MLWE. In practical terms, however, this attack has a signicant slow-down (and this is
not just due to the proof ) as the dimension of the module increases. This does suggest that increasing thedimension of the module may make the scheme more secure in concrete terms. In particular, going throughthis reduction to attack Kyber768 would lead to an RLWE problem with quite large modulus and error(q0= q 3 , ς 0 > q 2 ς ), and therefore require the attacker to consider more than 1 sample: the underlying lattice

remains a module with a rank strictly larger than 2.

5.2

Attacks against symmetric primitives

All symmetric building blocks of Kyber are instantiated with functions derived from Keccak [19]. In thedeterministic expansion of A from ρ we essentially need SHAKE-128 to produce output that looks uniformly
random and does not create any backdoors in the underlying lattice problem. In the noise generation we
require that concatenating a secret and a public input and feeding this concatenation to SHAKE-256 as
input results in a secure pseudorandom function. Breaking any of these properties of SHAKE would be amajor breakthrough in the cryptanalysis of SHAKE, which would require replacing SHAKE inside Kyber
by another XOF.
The security proofs model SHAKE-128, SHA3-256, and SHA3-512 as random oracles, i.e., they are subject
to the standard limitations of proofs in the (quantum-)random-oracle model. Turning these limitations into
an attack exploiting the instantiation of XOF, H, or G with SHAKE and SHA3 would again constitute amajor breakthrough in the understanding of either Keccak or random-oracle proofs in general.

5.3

Attacks exploiting decryption failures−160

All parameter sets of Kyber have a decapsulation-failure probability δ of somewhat below 2
examples in the remainder of this subsection we assume the failure probability of 2

−164

; for theof Kyber768. In

Theorems 2 and 3 we see that this failure probability plays a role in the attacker's advantage: in the classical2

context in the term 4qRO δ and in the quantum context in the term 8qRO δ , where qRO is the number ofqueries to the (classical or quantum) random oracle.

Attacks exploiting failures. This term in the attacker's advantage is not merely a proof artifact, it canbe explained by the following attack: An attacker searches through many dierent values of m (see line 1 ofAlg. 8) until he nds one that produces random coins r (line 3 of Alg. 8) that lead to a decapsulation failure,
which will give the attacker information about the secret key. In the quantum setting the search through2

dierent values of m is accelerated by Grover's algorithm, which explains the square in the term qRO . With
this attack in mind note that with 2chance of 2

−100

64

ciphertexts (cmp. Section 4.A.2 of the Call for Proposals), there is aof a decapsulation failure without any particular eort by the attacker.

The eect on Kyber. The attack sketched in the previous paragraph is based on two assumptions that
do not hold for Kyber: First it requires the capability to determine oine (e.g., as part of the Grover
oracle) if a certain value of r produces a decapsulation failure. Second it assumes that one decapsulation
failure seriously threatens the secrecy of the private key. Concerning the rst assumption, an attacker cannot
determine oine whether a given value of r , or more specically, the derived values r (line 9 of Alg. 5) ande1 (line 13 of Alg. 5), produce a decapsulation failure. The reason is that the probability of decapsulation
TT
failures largely depends on the products s e1 and e r and the attacker does not now the values of s ande. A quantum attacker can try to use Grover search to precompute values of m that have a slightly higher
chance to produce a failure; as the attacker does not know the signs of the coecients of e1 and s, the best
strategy is probably to search for values of m that produce e1 and r with above-average norm. The gain26

achieved through such an approach is limited due to the fact that the distribution of a high-dimensional
Gaussian is tightly concentrated around its expected value, while that of a 1-dimensional Gaussian is not astightly concentrated around its mean.

1536

The polynomial pair (e1 , r) can be seen as a vector in Z

distributed as a discrete Gaussian withp
η/2 = 1. By standard tail bounds on discrete Gaussians [12], we know that an
standard deviation σ =m-dimensional vector v drawn from a discrete Gaussian of standard deviation σ will satisfy√
2m
Pr[kvk > κσ m] < κm · e 2 (1−κ ) ,(7)

for any κ > 1.
So for example, the probability of nding a vector which is of length 1.33 · σ√

1536 is already as small as
2−220 . Even if Grover's algorithm reduces the search space and increases the probability to 2−110 , nding
such a vector merely increases the chances of getting a decryption error; and the probability increase is

3 For any vector v, if z is chosen according to agoverned by the tail-bounds for 1-dimensional Gaussians.
Gaussian with standard deviation σ , then for any κ,

2Pr[hz, vi| > κσkvk] ≤ 2e−κ /2 .

(8)

−160

If originally, the above probability is set so that decryption errors occur with probability ≈ 2, thenκ ≈ 15.4 If the adversary is then able to increase kvk by a factor of 1.33 (by being able to nd larger (e , r)),1

then we can decrease κ by a factor of 1.33 to ≈ 11.25 in (8), which would still give us a probability of a−90

decryption error of less than 2.

110

However, nding such a large v would take at least 2

200

would make the whole attack cost at least 2

time, which.

Of course one can try to nd a slightly smaller v in the rst step so that the entire attack takes less time.
If Grover's algorithm really saves a square-root factor, then the optimal value is ≈ 1.05 for κ in (7), which
would allow us to lower κ by a factor of 1.05 in (8) to 15/1.05 ≈ 14.28, and would still give a total time tond one decryption error ≈ 2−150. This makes the attack completely impractical.

Furthermore, a single decapsulation failure in Kyber does not allow an attacker to recover much information about the secret key s. To get an intuition for the amount of information obtained from failures, consider
the attack described in [39]. This is the standard attack that exploits failures in RLWE key encapsulation
schemes that reuse keys without the CCA transform.

In this scenario the attacker can adaptively choose

arbitrary noise, i.e., set failure probabilities to arbitrary values and maximize the information obtained fromeach failure or non-failure. The paper concludes that attacking RLWE key exchange in lattice dimension

1024 in this setting can be done with perhaps 4, 000 queries .

It seems extremely unlikely that even 10

decapsulation failures in Kyber would allow an attacker to recover any meaningful information about thesecret key s. Note that the probability of f decapsulation failures in 2

−e

2

64

−(e−64)f

ciphertexts is about 2

whereis the largest probability of failure an attacker can achieve for one ciphertext. We have established that110

even with a Grover search making 2

calls to the hash function, an attacker can only get e > 90. This

very loose analysis shows that an attacker can't reasonably hope to produce more than two or three failures128

in less than 2time. We therefore conclude that the decryption failures do not introduce any weaknesses

into Kyber.

Multitarget attacks using failures. Despite the limited gain, an attacker could consider using Grover's
algorithm to precompute values of m that produce r and e1 with large norm and then use this precomputed
set of values of m against many users. This multi-target attack is prevented by hashing the public key pk
into the random coins r and thereby into r and e1 (line 3 of Alg. 8).

3 The decryption noise is generated as an inner product of two vectors, and the distribution of this inner product closely
resembles the Gaussian distribution.

4 The above formula only roughly approximates how the decryption error is calculated where z corresponds to the secret key(s, e). We should also point out that a part of the decryption error inKyber

is caused by the rounding function Compress,

which the adversary has no control over. Therefore this attack will be even less practical than what we describe.

27

6 Advantages and limitations
6.1

Advantages

In addition to the very competitive speeds, small parameters, and being based on a well-studied problem,the unique advantages of Kyber are:Ease of implementation: Optimized implementations only have to focus on a fast dimension-256 NTT
and a fast Keccak permutation. This will give very competitive performance for all parameter sets ofKyber.

Scalability: Switching from one Kyber parameter set to another only requires changing the matrix
dimension (i.e., a #define in most C implementations) and the noise sampling.

We will now give a brief comparison of Kyber to other types of post-quantum schemes (that we areaware of ) and, more importantly, to other manners in which lattice-based schemes could be instantiated.

6.2

Comparison to SIDH

An interesting alternative to lattice-based KEMs is supersingular-isogeny Die-Hellman (SIDH) [50]. The
obvious advantage of SIDH is the sizes of public keys and ciphertexts thatwith suitable compression [30]
are about a factor of 3 smaller than Kyber's public keys and ciphertexts. The downside of SIDH is that it
is more than 2 orders of magnitude slower than Kyber. The scheme is also rather new, which makes it hard
to make denitive comparisons. In the coming years, both implementation speeds and (quantum) attacks
against SIDH can improve which may result in faster schemes and/or larger parameters.

6.3

Comparison to code-based KEMs

When considering code-based KEMs, one needs to distinguish the classical McEliece and Niederreiterschemes based on binary Goppa codes, and schemes with a less conservative (but more ecient) choiceof code.

A KEM based on binary Goppa codes can reasonably claim to be a very conservative choice of

post-quantum primitive; however, its deployment will, in many scenarios, be hampered by massive publickey size and key-generation time. Less conservative choices, like quasi-cyclic medium-density parity-check(QC-MDPC) codes, are a closer competition in terms of performance but suer from the fact that forecient parameters at high security levels they do not achieve (provably) negligible failure probability,
which precludes their use in CCA-secure KEMs.

6.4

Comparison to other lattice-based schemes

There are certain design choices that one can make when designing lattice-based schemes, some of which canhave signicant eects on the eciency of the resulting scheme and on the underlying security assumption.
Below we list the most important ones and explain the advantages / disadvantages of them versus what wechose for Kyber.

6.4.1

Schemes that build a KEM directly

The Kyber KEM is constructed by encrypting a random message using the LPR encryption [61] (withbit-dropping).

Another approach one could take is directly building a KEM using the slightly dierent

ideas described in [34, 73]. The advantage of the constructions in [34, 73] over our approach is that if one
were to construct a CPA-secure KEM transmitting a b-bit key, then the ciphertext would be b bits shorter,
which is about a 3% saving for typical parameters [58]. If, however, one wishes to construct a CCA-secure
KEM like Kyber, then this advantage disappears since transformations from CPA-secure KEMs to CCAsecure ones implicitly go through a CPA-secure encryption scheme, which will result in adding b bits to theKEM. This is why, in Kyber, we simply use the LPR encryption scheme (instead of the CPA-secure key

CPAPKE, and then use this as a building block to construct the IND-CCA2CCAKEM. Since there is virtually no dierence between the two approaches, we will not

encapsulation) to dene Kyber.
secure KEM Kyber.

draw a distinction between schemes constructed in either manner throughout the rest of this section.

28

6.4.2

LWE based schemes

If one does not want to use any algebraic structure in the LWE problem (i.e. if one takes the MLWE problem
over the ring Z), then there are two possibilities for constructing encryption or key-exchange schemes. The
rst approach makes the public key and the secret key very large (on the order of Megabytes), while keeping
the ciphertext at essentially the same size as in Kyber. This type of scheme is the [75] version of the original
Regev scheme from [81]. Because of the very large public-key size, this scheme would be extremely inecient
as a key exchange. A scheme more amenable to key exchange is [21], whose public key and ciphertext sizes
are both approximately 11 KB each, which is approximately 10 times larger than in Kyber. The running
time of each party is also larger by a factor of at least 10. In short, LWE-based schemes do not have any ring
structure but are an order of magnitude slower and larger than Kyber. They are good back-up schemes incase algebraic structure in lattice schemes could somehow be devastatingly exploited by attackers.

6.4.3

Ring-LWE based schemes

The other extreme in the LWE design space are Ring-LWE (RLWE) schemes based on [61] (e.g., [7]). RLWE
is a special case of the MLWE problem where the width of the matrix A over the ring R is always 1 (andtypically, its height would be 2 for a PKE or KEM scheme).

Varying the hardness of an RLWE scheme

therefore requires to change the dimension of the ring, whereas in Kyber, the ring is always the same andthe dimension of the module is being varied. As we mentioned above, one advantage of the approach we
chose for Kyber is that we only need to have one good implementation for operations over the ring; varying
the dimension of the module simply involves doing more (or fewer) of the same ring operations. Changing
the ring, on the other hand, would require completely re-implementing all the operations.
Another advantage of working with a constant-degree small ring is that it enables more ne-grained
tradeos between performance and security. The simplest and most ecient way of implementing RLWE is
to work over rings Z[X]/(Xn+ 1) where n is a power of 2. Since n is the only parameter that determines

the eciency and security of RLWE schemes, limiting it to powers of 2 may require overshooting the needed
security bound. For example, the dimension of Kyber768 is not reachable. One could of course work directly
modulo a polynomial of any desired degree (with the main restriction being that it has to be irreducible
over Z), but then the security would decrease slightly due the geometry of non-power-of-2 number elds(see [64, 65]).
The one advantage of RLWE over Kyber is that if A is a k × k matrix, then extracting it from a seedrequires k times more XOF output than for a 1 × 1 matrix.

6.4.4

NTRU

When compared to Kyber, NTRU [47] has all the advantages and disadvantages of RLWE, but in addition
has two further negative points against it.

First NTRU key generation is considerably more expensive

than in RLWE when the ring does not support NTT. The reason is that NTRU key generation requires
polynomial division, whereas RLWE key generation requires only multiplication (if the ring supports NTT,
then division is not much slower than multiplication). The second possible downside of NTRU is that thegeometry of its underlying lattice leads to attacks that do not exist against RLWE or MLWE schemes [52].
While this property does not seem to aid in attacks against the small parameters that are used for dening
NTRU cryptosystems, it may point to a possible weakness that could be further exploited. The one possible
advantage of using NTRU is a small performance advantage during encryption (encapsulation), but given the
disadvantages we do not consider this a good tradeo. Furthermore, it is not possible to dene an ecientversion of Module-NTRU that would allow for the advantages of Kyber described above in Section 6.1.

6.4.5

Dierent Polynomial Rings

One could consider using Kyber with a ring that is not Z[X]/(Xn+ 1). An argument that could be madefor using dierent rings is that the rings currently used in Kyber have algebraic properties (e.g., subrings,
large Galois groups, etc.) which may be exploited in attacks. We choose to work with Z[X]/(Xthe following reasons:29n+ 1) for• From a performance perspective there is no serious competition; the NTT-based multiplication supported by the parameters we chose for Kyber is at the same time very memory ecient and fasterthan any other algorithm for multiplication in polynomial rings.

• Lattice-based schemes using the ring Z[X]/(X n + 1) have been studied since at least [59]. When thenoise vectors are chosen as specied in [61], there have been no improved attacks against RLWE (or
MLWE) that use the underlying algebraic structure [74].

Furthermore, being based on MLWE, thealgebraic structure of Kyber is very dierent from that which was exploited in the attacks against ideal

5  we emphasize that the lattice problems underlying the hardness of Kyber

lattices in [20, 31, 32]
are not ideal lattices.

• Some of the additional algebraic structure of Z[X]/(X n + 1) is actually helpful against certain possiblenattack vectors. As a simple example, it can be proved that when X + 1 (almost) fully splits modulo
q , there do not exist polynomials in the ring that have small norm and many zeros in the NTT
representationthe existence of such polynomials for any q would weaken the security of MLWE.
• Finally, Z[X]/(X n + 1) is one of the most widely studied, and best understood, rings (along with othercyclotomic rings) in algebraic number theory. The fact that no attacks have been found against its use
for cryptosystems like Kyber makes it a much more conservative choice than some ring that is harderto analyze and may show weaknesses only after many more years of study.

6.4.6

Deterministic Noise.

Instead of adding noise e, e1 , and e2 , one can add deterministic noise by simply dropping bits. This is thebasis behind the Learning with Rounding (LWR) problem [13], which for certain parameters is as hard as
the LWE problem. We believe that asymptotically this is a sound approach but the number of bits that canbe dropped before signicant decryption error is introduced is not very large (≈ 2) in certain places in thescheme. This may allow for a possibility of slightly improved attacks against the scheme. Since generating
noise is not a particularly costly operation, we did not choose to potentially weaken the scheme to save alittle time.

7 Brief discussion of relevant results since Nov. 2017
In this section we briey reference and comment on results relevant to Kyber that were published after theoriginal NIST PQC submission deadline in November 2017.

small Kyber. The idea of decreasing the modulus q from q = 7681 to q = 3329 for Kyber was alreadypresent in [86]; the paper refers to the resulting parameter set as small-Kyber. Other parameters chosen
in small-Kyber are dierent than what we describe in this round-2 update; in particular, small-Kyber does
not eliminate the public-key compression. More importantly, the polynomial multiplication using the NTT
algorithm is dierent in small-Kyber. Our multiplication algorithm uses the NTT algorithm to computethe decomposition of polynomials ai ∈ Zq [X]/(X256+ 1) as(ai mod X 2 − r1 , . . . , ai mod X 2 − r128 ),and multiplication is performed using pointwise products modulo X

2−rj . The algorithm in [86], on the other

hand, divides the ai into two polynomials of degree 128 and performs a full-splitting NTT (i.e. modulo

X − ri0 ) on each of them. This method, which computes two (smaller) NTTs and some additional steps toreassemble the polynomials, has slightly worse performance than the original Kyber and considerably worse
than Kyber with our round-2 tweaks; though we believe that applying our new tweaks would speed up thealgorithm in [86] as well.

Fault attacks. In [80], Ravi, Roy, Bhasin, Chattopadhyay, and Mukhopadhyay describe a fault attack
against implementations of NewHope, Kyber, Frodo, and Dilithium on an ARM Cortex-M4. Specically,
these attacks target the instructions loading the nonce in the PRF; skipping this load through a clock glitch

5 Also, like the attacks against NTRU, these do not apply for the small parameters used public key encryption schemes.

30reuses the same nonce multiple times, which leads to eciently breakable instances of the schemes.

We

could have decided to modify the specication of Kyber to generate randomness in a dierent way. Indeed,
generating all randomness at once through one call to the PRF would thwart this specic attack and maybe
aid future fault-attack protected implementations. However, such a change to the specication would reduceparallelism and thus cost performance on many platforms. More importantly however, the benets of sucha change are still completely unclear. It is not at all surprising that an implementation without any faultattack countermeasures, such as the one targeted in [80], succumbs to some fault attack.

It is not clear

if the attack described in [80] is the most powerful attack and it is also unclear what serious fault-attack
countermeasures for any of the targeted schemes have to look like to thwart any realistic attack.

Attacks exploiting decapsulation failures. In [36], D'Anvers, Vercauteren, and Verbauwhede present
a detailed analysis of attacks exploiting decapsulation failures. The paper essentially conrms the analysis
we give in Section 5.3, namely that failures that occur with negligibly small probability are no concern for
security. For example, the best attack the paper presents against Kyber768 collects 42 decapsulation failures131

from 2142

decapsulation queries and takes time 2. Note that these numbers are for Kyber without theround-2 tweaks; the parameters we propose for round-2 have even lower failure probability.
In [15], Bauer, Gilbert, Renault, and Rossi revisit CCA attacks against schemes that only oer CPA security (more specically, against NewHope-CPAKEM). The attacks presented show once more how important
CCA security is when not using purely ephemeral secrets.

References[1] Martin Albrecht. Security estimates for the learning with errors problem, 2017. Version 2017-09-27,

https://bitbucket.org/malb/lwe-estimator. 25[2] Martin Albrecht and Amit Deo. Large modulus Ring-LWE ≥ Module-LWE, 2017. To appear. https://eprint.iacr.org/2017/612. 26[3] Martin R. Albrecht, Amit Deo, and Kenneth G. Paterson. Cold boot attacks on ring and module LWE
keys under the NTT.

Transactions on Cryptographic Hardware and Embedded Systems, (3):173213,

2018. https://doi.org/10.13154/tches.v2018.i3.173-213. 16[4] Martin R Albrecht, Florian Göpfert, Fernando Virdia, and Thomas Wunderer. Revisiting the expected
cost of solving uSVP and applications to LWE. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advancesin Cryptology  ASIACRYPT 2017, volume 10211 of LNCS, pages 65102. Springer, 2017.

//eprint.iacr.org/2017/815. 24

https:[5] Martin R. Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of learning with errors.

J. Mathematical Cryptology, 9(3):169203, 2015. https://eprint.iacr.org/2015/046. 23, 24[6] Michael Alekhnovich. More on average case vs approximation complexity. In 44th Symposium on Foun-dations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings,
pages 298307, 2003. 8[7] Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe.
 a new hope.

Post-quantum key exchange

In Proceedings of the 25th USENIX Security Symposium, pages 327343. USENIX

Association, 2016. http://cryptojedi.org/papers/#newhope. 9, 13, 14, 16, 22, 23, 24, 25, 29[8] Joël Alwen, Stephan Krenn, Krzysztof Pietrzak, and Daniel Wichs. Learning with rounding, revisited.
In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology  CRYPTO 2013, volume 8042 of

LNCS, pages 5774. Springer, 2013. https://eprint.iacr.org/2013/098. 21[9] Yoshinori Aono, Yuntao Wang, Takuya Hayashi, and Tsuyoshi Takagi.

Improved progressive BKZ

algorithms and their precise cost estimation by sharp simulator. In Marc Fischlin and Jean-SébastienCoron, editors, Advances in Cryptology  EUROCRYPT 2016, volume 9665 of LNCS, pages 789819.

Springer, 2016. https://eprint.iacr.org/2016/146. 23

31

[10] Benny Applebaum, David Cash, Chris Peikert, and Amit Sahai.
circular-secure encryption based on hard learning problems.

Fast cryptographic primitives and

In Advances in Cryptology - CRYPTO

2009, 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2009.
Proceedings, pages 595618, 2009. 8[11] Sanjeev Arora and Rong Ge. New algorithms for learning in presence of errors. In Luca Aceto, Monika
Henzingeri, and Ji°í Sgall, editors, Automata, Languages and Programming, volume 6755 of LNCS,
pages 403415. Springer, 2011. https://www.cs.duke.edu/~rongge/LPSN.pdf. 23[12] Wojciech Banaszczyk. New bounds in some transference theorems in the geometry of numbers. Math-ematische Annalen, 296(1):625635, 1993. 27[13] Abhishek Banerjee, Chris Peikert, and Alon Rosen.

Pseudorandom functions and lattices.

In David

Pointcheval and Thomas Johansson, editors, Advances in Cryptology  EUROCRYPT 2012, volume 7237

of LNCS, pages 719737. Springer, 2012. http://www.iacr.org/archive/eurocrypt2012/72370713/

72370713.pdf. 9, 14, 21, 30[14] Paul Barrett.

Implementing the Rivest Shamir and Adleman public key encryption algorithm on astandard digital signal processor. In Andrew M. Odlyzko, editor, Advances in Cryptology  CRYPTO'86, volume 263 of Lecture Notes in Computer Science, pages 311323. Springer-Verlag Berlin Heidelberg,
1987. https://link.springer.com/chapter/10.1007/3-540-47721-7_24. 22[15] Aurélie Bauer, Henri Gilbert, Guénaël Renault, and Mélissa Rossi. Assessment of the key-reuse resilienceof newhope.

IACR Cryptology ePrint Archive report 2019/075, 2019.

2019/075.pdf. 31[16] Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven.

https://eprint.iacr.org/

New directions in nearest neighborsearching with applications to lattice sieving. In SODA '16 Proceedings of the twenty-seventh annual

ACM-SIAM symposium on Discrete Algorithms, pages 1024. SIAM, 2016.

org/2015/1128. 24[17] Daniel J. Bernstein, Tanja Lange, and Peter Schwabe.

https://eprint.iacr.

The security impact of a new cryptographic

library. In Alejandro Hevia and Gregory Neven, editors, Progress in Cryptology  LATINCRYPT 2012,
volume 7533 of LNCS, pages 159176. Springer, 2012.

http://cryptojedi.org/papers/#coolnacl.

15[18] Daniel J. Bernstein, Peter Schwabe, and Gilles Van Assche.

Tweetable FIPS 202, 2015.

keccak.team/2015/tweetfips202.html (accessed 2017-11-29). 15

https://[19] Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. The Keccak reference. Submission

to the NIST SHA-3 competition, 2011. https://keccak.team/files/Keccak-reference-3.0.pdf. 14,
26[20] Jean-François Biasse and Fang Song.

Ecient quantum algorithms for computing class groups andsolving the principal ideal problem in arbitrary degree number elds. In SODA '16 Proceedings of thetwenty-seventh annual ACM-SIAM symposium on Discrete Algorithms, pages 893902. SIAM, 2016.

http://fangsong.info/files/pubs/BS_SODA16.pdf. 26, 30[21] Joppe Bos, Craig Costello, Léo Ducas, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Ananth
Raghunathan, and Douglas Stebila. Frodo: Take o the ring! practical, quantum-secure key exchange
from LWE. In CCS '16 Proceedings of the 2016 ACM SIGSAC Conference on Computer and Commu-

nications Security, pages 10061018. ACM, 2016. https://eprint.iacr.org/2016/659. 13, 29[22] Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter
Schwabe, and Damien Stehlé.

CRYSTALS  Kyber:a CCA-secure module-lattice-based KEM.

In

2018 IEEE European Symposium on Security and Privacy, EuroS&P 2018. IEEE, 2018. To appear.

https://eprint.iacr.org/2017/634. 5, 12, 2332

[23] Joppe W. Bos, Craig Costello, Michael Naehrig, and Douglas Stebila. Post-quantum key exchange for
the TLS protocol from the ring learning with errors problem. In 2015 IEEE Symposium on Security

and Privacy, pages 553570, 2015. https://eprint.iacr.org/2014/599. 13, 14, 25[24] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) fully homomorphic encryption
without bootstrapping. In ITCS '12 Proceedings of the 3rd Innovations in Theoretical Computer Science

Conference, pages 309325. ACM, 2012. https://eprint.iacr.org/2011/277. 19[25] Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehlé. Classical hardnessof learning with errors. In STOC '13 Proceedings of the forty-fth annual ACM symposium on Theoryof computing, pages 575584. ACM, 2013. http://arxiv.org/pdf/1306.0281. 14[26] Leon Groot Bruinderink, Andreas Hülsing, Tanja Lange, and Yuval Yarom. Flush, Gauss, and Reload a cache attack on the BLISS lattice-based signature scheme. In Benedikt Gierlichs and Axel Poschmann,editors, Cryptographic Hardware and Embedded Systems  CHES 2016, volume 9813 of LNCS, pages
323345. Springer, 2016. https://eprint.iacr.org/2016/300. 14[27] Peter Campbell, Michael Groves, and Dan Shepherd.

Soliloquy:

A cautionary tale.

In ETSI

https://docbox.etsi.org/workshop/2014/
201410_CRYPTO/S07_Systems_and_Attacks/S07_Groves_Annex.pdf. 26

2nd Quantum-Safe Crypto Workshop, pages 19, 2014.

[28] Yuanmi Chen. Lattice reduction and concrete security of fully homomorphic encryption. PhD thesis,
l'Université Paris Diderot, 2013. http://www.di.ens.fr/~ychen/research/these.pdf. 23, 24[29] Yuanmi Chen and Phong Q. Nguyen. BKZ 2.0: Better lattice security estimates. In Dong Hoon Lee
and Xiaoyun Wang, editors, Advances in Cryptology  ASIACRYPT 2011, volume 7073 of LNCS, pages
120. Springer, 2011.

http://www.iacr.org/archive/asiacrypt2011/70730001/70730001.pdf. 23,

24[30] Craig Costello, David Jao, Patrick Longa, Michael Naehrig, Joost Renes, and David Urbanik. Ecientcompression of SIDH public keys. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, Advancesin Cryptology  EUROCRYPT 2017, volume 10210 of LNCS, pages 679706. Springer, 2017.

//eprint.iacr.org/2016/963. 28

https:[31] Ronald Cramer, Léo Ducas, Chris Peikert, and Oded Regev. Recovering short generators of principal
ideals in cyclotomic rings. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology

 EUROCRYPT 2016, volume 9666 of LNCS, pages 559585. Springer, 2016. https://eprint.iacr.

org/2015/313. 26, 30[32] Ronald Cramer, Léo Ducas, and Benjamin Wesolowski.
plication to Ideal-SVP.

Short Stickelberger class relations and ap-

In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, Advances in

Cryptology  EUROCRYPT 2017, volume 10210 of LNCS, pages 324348. Springer, 2017.

//eprint.iacr.org/2016/885. 26, 30

https:[33] The FPLLL development team. fplll, a lattice reduction library. Available at https://github.com/

fplll/fplll, 2017. 23[34] Jintai Ding, Xiang Xie, and Xiaodong Lin. A simple provably secure key exchange scheme based on
the learning with errors problem.

//eprint.iacr.org/2012/688. 28

IACR Cryptology ePrint Archive report 2012/688, 2012.

https:[35] Léo Ducas. Shortest vector from lattice sieving: a few dimensions for free. IACR Cryptology ePrint
Archive report 2017/999, 2017. https://eprint.iacr.org/2017/999. 23[36] Jan-Pieter D'Anvers, Frederik Vercauteren, and Ingrid Verbauwhede.

On the impact of decryption

failures on the security of LWE/LWR based schemes. IACR Cryptology ePrint Archive report 2018/1089,
2018. https://eprint.iacr.org/2018/1089. 31

33

[37] Kirsten Eisenträger, Sean Hallgren, Alexei Kitaev, and Fang Song. A quantum algorithm for computing
the unit group of an arbitrary degree number eld. In STOC '14 Proceedings of the forty-sixth annual

ACM symposium on Theory of computing, pages 293302. ACM, 2014.

edu/kxe8/unitgroup.pdf. 26

http://www.personal.psu.

[38] Thomas Espitau, Pierre-Alain Fouque, Benoït Gérard, and Mehdi Tibouchi. Side-channel attacks on
BLISS lattice-based signatures: Exploiting branch tracing against strongswan and electromagnetic emanations in microcontrollers. In CCS '17 Proceedings of the 2017 ACM SIGSAC Conference on Computerand Communications Security, pages 18571874. ACM, 2017.

https://eprint.iacr.org/2017/505.

14[39] Scott Fluhrer. Cryptanalysis of ring-LWE based key exchange with key share reuse. IACR Cryptology
ePrint Archive report 2016/085, 2016. https://eprint.iacr.org/2016/085. 27[40] Eiichiro Fujisaki and Tatsuaki Okamoto. Secure integration of asymmetric and symmetric encryption

https://link.springer.

schemes. In Advances in Cryptology - CRYPTO '99, pages 537554, 1999.

com/chapter/10.1007/3-540-48405-1_34. 5, 11, 20[41] Nicolas Gama and Phong Nguyen.

Predicting lattice reduction.

In Nigel Smart, editor, Advancesin Cryptology  EUROCRYPT 2008, volume 4965 of LNCS, pages 3151. Springer, 2008.

//www.iacr.org/archive/eurocrypt2008/49650031/49650031.pdf. 24

https:[42] Nicolas Gama, Phong Q Nguyen, and Oded Regev. Lattice enumeration using extreme pruning. In Henri
Gilbert, editor, Advances in Cryptology  EUROCRYPT 2010, volume 6110 of LNCS, pages 257278.
Springer, 2010. http://www.iacr.org/archive/eurocrypt2010/66320257/66320257.pdf. 23[43] Matthew

Gretton-Dann.

Introducing

2017'sextensions

to

the

Arm

architecture,2017.

https://community.arm.com/processors/b/blog/posts/introducing-2017s-extensions-tothe-arm-architecture. 16[44] Tim Güneysu, Tobias Oder, Thomas Pöppelmann, and Peter Schwabe.
lattice-based signatures.

Software speed records for

In Philippe Gaborit, editor, Post-Quantum Cryptography, volume 7932 of

LNCS, pages 6782. Springer, 2013. http://cryptojedi.org/papers/#lattisigns. 16[45] J. Alex Halderman, Seth D. Schoen, Nadia Heninger, William Clarkson, William Paul, Joseph A.
Calandrino, Ariel J. Feldman, Jacob Appelbaum, and Edward W. Felten.
boot attacks on encryption keys, 2008.

papers/halderman/halderman.pdf. 16

Lest we remember: Coldhttps://www.usenix.org/legacy/event/sec08/tech/full_[46] Guillaume Hanrot, Xavier Pujol, and Damien Stehlé.

Terminating BKZ.

Archive report 2011/198, 2011. https://eprint.iacr.org/2011/198. 23

IACR Cryptology ePrint[47] Jerey Hostein, Jull Pipher, and Joseph H. Silverman. NTRU: a ring-based public key cryptosystem.
In Joe P. Buhler, editor, Algorithmic number theory, volume 1423 of LNCS, pages 267288. Springer,

1998. https://www.securityinnovation.com/uploads/Crypto/ANTS97.ps.gz. 8, 29[48] Dennis Hofheinz, Kathrin Hövelmanns, and Eike Kiltz. A modular analysis of the Fujisaki-Okamototransformation. In Yael Kalai and Leonid Reyzin, editors, Theory of Cryptography, LNCS, pages 341

371. Springer, 2017. https://eprint.iacr.org/2017/604. 15, 20[49] Nick Howgrave-Graham. A hybrid lattice-reduction and meet-in-the-middle attack against NTRU. In
Alfred Menezes, editor, Advances in Cryptology  CRYPTO 2007, volume 4622 of LNCS, pages 150169.

Springer, 2007. http://www.iacr.org/archive/crypto2007/46220150/46220150.pdf. 14[50] David Jao and Luca De Feo.

Towards quantum-resistant cryptosystems from supersingular elliptic

curve isogenies. In Bo-Yin Yang, editor, Post-Quantum Cryptography  PQCrypto 2011, volume 7071
of LNCS, pages 1934. Springer, 2011. https://eprint.iacr.org/2011/506. 28

34

[51] Paul Kirchner and Pierre-Alain Fouque. An improved BKW algorithm for LWE with applications tocryptography and lattices. In Rosario Gennaro and Matthew Robshaw, editors, Advances in Cryptology

 CRYPTO 2015, volume 9215 of LNCS, pages 4362. Springer, 2015. http://www.iacr.org/archive/

crypto2015/92160264/92160264.pdf. 23[52] Paul Kirchner and Pierre-Alain Fouque. Revisiting lattice attacks on overstretched NTRU parameters.
In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, Advances in Cryptology  EUROCRYPT

2017, volume 10210 of LNCS, pages 326. Springer, 2017. https://www.di.ens.fr/~fouque/euro17a.

pdf. 29[53] Thijs Laarhoven. Search problems in cryptography. PhD thesis, Eindhoven University of Technology,
2015. http://www.thijs.com/docs/phd-final.pdf. 24[54] Thijs Laarhoven.

Sieving for shortest vectors in lattices using angular locality-sensitive hashing.

In

Rosiario Gennaro and Matthew Robshaw, editors, Advances in Cryptology  CRYPTO 2015, volume9216 of LNCS, pages 322. Springer, 2015.

92160123.pdf. 24

http://www.iacr.org/archive/crypto2015/92160123/[55] Thijs Laarhoven, Michele Mosca, and Joop van de Pol.

Finding shortest lattice vectors faster using

quantum search. Designs, Codes and Cryptography, 77(2):375400, 2015. https://eprint.iacr.org/

2014/907. 24[56] Adam Langley. Maybe skip SHA-3. Blog post on ImperialViolet, 2017. https://www.imperialviolet.

org/2017/05/31/skipsha3.html. 16[57] Adeline Langlois and Damien Stehlé. Worst-case to average-case reductions for module lattices. Designs,

Codes and Cryptography, 75(3):565599, 2015. https://eprint.iacr.org/2012/090. 5, 13, 19[58] Vadim Lyubashevsky.

Standardizing lattice crypto and beyond.

Lyubashevsky at PQCrypto 2017, 2017.

2017_lattice.pdf. 28

Slides of the talk given by Vadim

https://2017.pqcrypto.org/conference/slides/pqc_[59] Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, and Alon Rosen. SWIFFT: A modest proposal
for FFT hashing. In Kaisa Nyberg, editor, Fast Software Encryption  FSE 2008,, volume 5086 of LNCS,
pages 5472. Springer, 2008. https://www.eecs.harvard.edu/~alon/PAPERS/lattices/swifft.pdf.
13, 30[60] Vadim Lyubashevsky, Adriana Palacio, and Gil Segev. Public-key cryptographic primitives provably as
secure as subset sum. In Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010,

Zurich, Switzerland, February 9-11, 2010. Proceedings, pages 382400, 2010. 8[61] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors overrings. In Henri Gilbert, editor, Advances in Cryptology  EUROCRYPT 2010, volume 6110 of LNCS,
pages 123. Springer, 2010.

pdf. 8, 13, 28, 29, 30

http://www.iacr.org/archive/eurocrypt2010/66320288/66320288.

[62] Vadim Lyubashevsky, Chris Peikert, and Oded Regev.
over rings.

On ideal lattices and learning with errors

Slides of the talk given by Chris Peikert at Eurocrypt 2010, 2010.

francetelecom.com/events/eurocrypt2010/talks/slides-ideal-lwe.pdf. 8[63] Vadim Lyubashevsky, Chris Peikert, and Oded Regev.
over rings. Journal of the ACM, 60(6):43:143:35, 2013.

ideal-lwe.pdf. 8

http://crypto.rd.

On ideal lattices and learning with errors

http://www.cims.nyu.edu/~regev/papers/[64] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. A toolkit for Ring-LWE cryptography. In Thomas
Johansson and Phong Q. Nguyen, editors, Advances in Cryptology  EUROCRYPT 2013, volume 7881
of LNCS, pages 3554. Springer, 2013.

78810035.pdf. 29

http://www.iacr.org/archive/eurocrypt2013/78810035/

35

[65] Vadim Lyubashevsky and Gregor Seiler. NTTRU: Truly fast NTRU using NTT. TCHES, 2019. https://eprint.iacr.org/2019/040. 2, 29[66] Daniele Micciancio and Panagiotis Voulgaris. Faster exponential time algorithms for the shortest vector
problem.

In SODA '10 Proceedings of the twenty-rst annual ACM-SIAM symposium on Discrete

Algorithms, pages 14681480. SIAM, 2010. https://cseweb.ucsd.edu/~daniele/papers/Sieve.pdf.
24[67] Peter L. Montgomery.

Modular multiplication without trial division.

Mathematics of Computa-tion, 44(170):519521, 1985. http://www.ams.org/journals/mcom/1985-44-170/S0025-5718-1985-

0777282-X/S0025-5718-1985-0777282-X.pdf. 22[68] National Institute of Standards and Technology. FIPS PUB 202  SHA-3 standard: Permutation-basedhash and extendable-output functions, 2015. http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.

202.pdf. 12, 15[69] Phong Q. Nguyen and Thomas Vidick. Sieve algorithms for the shortest vector problem are practical.

Journal of Mathematical Cryptology, 2(2):181207, 2008. ftp://ftp.di.ens.fr/pub/users/pnguyen/

JoMC08.pdf. 24[70] Tobias Oder, Tobias Schneider, Thomas Pöppelmann, and Tim Güneysu. Practical CCA2-secure andmasked Ring-LWE implementation. IACR Cryptology ePrint Archive report 2016/1109, 2016. https://eprint.iacr.org/2016/1109. 22[71] Chris Peikert.

Public-key cryptosystems from the worst-case shortest vector problem, 2009.

//web.eecs.umich.edu/~cpeikert/pubs/svpcrypto.pdf (full version of [72]). 9, 13, 36

https:[72] Chris Peikert. Public-key cryptosystems from the worst-case shortest vector problem: extended abstract.
In STOC '09 Proceedings of the forty-rst annual ACM symposium on Theory of computing, pages 333
342. ACM, 2009. See also full version [71]. 36[73] Chris Peikert. Lattice cryptography for the Internet. In Michele Mosca, editor, Post-Quantum Cryptog-

raphy, volume 8772 of LNCS, pages 197219. Springer, 2014. http://web.eecs.umich.edu/~cpeikert/

pubs/suite.pdf. 28[74] Chris Peikert. How (not) to instantiate Ring-LWE. In Vassilis Zikas and Roberto De Prisco, editors,

Security and Cryptography for Networks, volume 9841 of LNCS, pages 411430. Springer, 2016. https://web.eecs.umich.edu/~cpeikert/pubs/instantiate-rlwe.pdf. 30[75] Chris Peikert, Vinod Vaikuntanathan, and Brent Waters.

A framework for ecient and composable

oblivious transfer. In David A. Wagner, editor, Advances in Cryptology  CRYPTO 2008, volume 5157
of LNCS, pages 554571. Springer, 2008.

51570556.pdf. 29[76] Peter Pessl,

Leon Groot Bruinderink,

https://www.iacr.org/archive/crypto2008/51570556/

and Yuval Yarom.

ing strongSwan's implementation of post-quantum signatures.

To BLISS-B or not to be  attackIn CCS '17 Proceedings of the 2017

ACM SIGSAC Conference on Computer and Communications Security, pages 18431855. ACM, 2017.

https://eprint.iacr.org/2017/490. 14[77] Thomas Pöppelmann and Tim Güneysu.

Towards practical lattice-based public-key encryption onrecongurable hardware. In Tanja Lange, Kristin Lauter, and Petr Lison¥k, editors, Selected Areas in

Cryptography  SAC 2013, volume 8282 of LNCS, pages 6885. Springer, 2013. https://www.ei.rub.

de/media/sh/veroeffentlichungen/2013/08/14/lwe_encrypt.pdf. 9, 13[78] Thomas Pornin. BearSSL  a smaller SSL/TLS library, 2018. https://bearssl.org/ (accessed 201903-15). 22

36

[79] Robert Primas, Peter Pessl, and Stefan Mangard. Single-trace side-channel attacks on masked latticebased encryption.

In Wieland Fischer and Naofumi Homma, editors, Cryptographic Hardware andEmbedded Systems  CHES 2017, volume 10529 of LNCS, pages 513533. Springer, 2017.

//eprint.iacr.org/2017/594. 22[80] Prasanna

Ravi,

Debapriya

Basu

Roy,

ShivamBhasin,AnupamChattopadhyay,andhttps:

Debdeep

Mukhopadhyay. Number not used once - practical fault attack on pqm4 implementations of nist candidates. IACR Cryptology ePrint Archive report 2018/211, 2018. https://eprint.iacr.org/2018/211.
30, 31[81] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In STOC '05

Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 8493. ACM,
2005. Preliminary version of [82]. 8, 14, 29[82] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of theACM, 56(6):34, 2009. http://www.cims.nyu.edu/~regev/papers/qcrypto.pdf. 8, 37[83] Sujoy Sinha Roy, Frederik Vercauteren, Nele Mentens, Donald Donglong Chen, and Ingrid Verbauwhede.
Compact Ring-LWE cryptoprocessor. In Lejla Batina and Matthew Robshaw, editors, Cryptographic

Hardware and Embedded Systems  CHES 2014, volume 8731 of LNCS, pages 371391. Springer, 2014.

http://www.iacr.org/archive/ches2014/87310183/87310183.pdf. 13[84] Tsunekazu Saito, Keita Xagawa, and Takashi Yamakawa. Tightly-secure key-encapsulation mechanismin the quantum random oracle model. IACR Cryptology ePrint Archive report 2017/1005, 2017. https://eprint.iacr.org/2017/1005. 20[85] Claus-Peter
cal

Schnorr

algorithms

and

and
solving

MartinsubsetEuchner.
sum

Lattice

problems.

basis

reduction:

Mathematicalimproved

programming,

practi-66(1-3):181

1994.
http://www.csie.nuk.edu.tw/~cychen/Lattices/Lattice%20Basis%20Reduction_%20Improved%20Practical%20Algorithms%20and%20Solving%20Subset%20Sum%20Problems.pdf. 23
199,[86] Shuai Zhou, Haiyang Xue, Daode Zhang, Kunpeng Wang, Xianhui Lu, Bao Li, and Jingnan He.
Preprocess-then-ntt technique and its applications to KYBER and NEWHOPE.
ePrint Archive report 2018/995, 2018. https://eprint.iacr.org/2018/995. 30

37

IACR Cryptology