Basic Lattice Cryptography

The concepts behind Kyber (ML-KEM) and Dilithium (ML-DSA)

Vadim Lyubashevsky
IBM Research Europe, Zurich
vad@[Link]

(Last updated: February 14, 2025)

Contents
1 Prelude 2

2 Encryption 5
2.1 Some Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 A Motivating Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 The LWE Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4 Public Key and Ciphertext Size Trade-offs . . . . . . . . . . . . . . . . . . 10
2.5 Some Variations and Optimizations . . . . . . . . . . . . . . . . . . . . . . 11
2.6 Non-Interactive Key Exchange (NIKE) . . . . . . . . . . . . . . . . . . . . 17

3 Hardness of LWE and Other Lattice Problems 19

3.1 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Finding Short Vectors in Random Lattices (the SIS Problem) . . . . . . . 21
3.3 The LWE Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.4 Practical Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4 Encryption Over Polynomial Rings 26

4.1 Polynomial Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2 The Generalized-LWE and SIS Problems . . . . . . . . . . . . . . . . . . . 28
4.3 Generalized-LWE Encryption . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.4 NTRU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.5 Exploiting the Algebraic Structure ... for Attacks . . . . . . . . . . . . . . 32
4.6 Exploiting the Algebraic Structure ... for Efficiency (The Number Theoretic
Transform) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.7 The Encryption Scheme CRYSTALS-Kyber (ML-KEM) . . . . . . . . . . 36
4.8 From CPA Encryption to a CCA-KEM . . . . . . . . . . . . . . . . . . . 39

5 Digital Signatures from Σ-Protocols 41

5.1 The Statements and Witnesses . . . . . . . . . . . . . . . . . . . . . . . . 41
5.2 The Basic Σ-Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.3 Analogies to Discrete Logarithm Schemes:
Schnorr, Okamoto, and Katz-Wang. . . . . . . . . . . . . . . . . . . . . . 46
5.4 Reducing the Proof Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.5 Reducing the Public Key Size . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.6 Digital Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.7 The Signature Scheme CRYSTALS-Dilithium (ML-DSA) . . . . . . . . . . 56
2 Basic Lattice Cryptography

1 Prelude
The road to the NIST standards. The beginning of modern lattice-based cryptography
traces back to two works from the mid 1990’s. The first was Ajtai’s result [Ajt96] that
showed that being able to solve a random instance of the Small Integer Solution (SIS)
problem was as hard as solving some believed-to-be-difficult problem for every lattice.
The second was NTRU [HPS98], an efficient public key cryptosystem based on a new,
potentially-hard, lattice problem over polynomial rings. The work of [Ajt96], which
also inspired an encryption scheme [AD97] with a similarly strong security guarantee,
unfortunately had completely impractical instantiations. The NTRU cryptosystem, on
the other hand, was very practical but lacked a theoretical underpinning. Indeed, there
were various constructions [GGH97, Sil01, HPS01, HHGP+ 03] building on the NTRU
approach, or using other tricks to improve efficiency, that were later shown to be weakened
or completely insecure [Ngu99, Gen01, GS02, NR06].
The theoretical and practical threads of lattice cryptography research were woven
together during the next decade. The works of [Mic02, PR06, LM06] distilled out the
algebraic structure which allowed lattice-based primitives to have the efficiency of NTRU,1
while also enjoying the same type of theoretical guarantees as Ajtai’s original construction.2
At the same time, Regev introduced the very versatile Learning with Errors (LWE)
problem [Reg05] which greatly expanded the universe of possible lattice-based primitives.
In that work, Regev also proved that solving random instances of LWE is as hard as
(quantumly3 ) solving the same worst-case lattice problems as in [Ajt96]. Together with
a better understanding of the concrete hardness of lattice problems [GN08], researchers
were able to create efficient (at least in an asymptotic sense) encryption, signature, and
identity-based encryption schemes which were based on solid theoretical foundations
[Reg05, LM08, GPV08, Lyu09, SSTX09, LPR10].
Lattice-based cryptography gained further momentum in the early 2010’s due to the
first realization, from any assumption, of a fully-homomorphic encryption scheme [Gen09]
and the rapid increase in research aimed towards building a quantum computer that
would be able to break all cryptography based on factoring and discrete log [Sho97].
During the middle part of the 2010’s, refinements and enhancements (e.g. [GLP12, BG14,
DLP14, LS15, DP16, ADPS16]) allowed lattice constructions to go from being merely
asymptotically-efficient to having truly practical instantiations. By the time the NIST
post-quantum cryptography standardization process started in 2017 [NIS17], lattice-based
schemes were among the fastest and most compact quantum-resistant primitives, and even
surpassed their number-theoretic counterparts in terms of raw performance.

The scope of this tutorial. This tutorial focuses on describing the fundamental mathe-
matical concepts and design decisions used in the two “main” lattice schemes standardized
by NIST and included in the CNSA 2.0 algorithmic suite [Age24]. They are the KEM /
encryption scheme CRYSTALS-Kyber (ML-KEM) [BDK+ 18, NIS24b] and the signature
1 Or even better efficiency, by utilizing polynomial rings that allow for the Number Theoretic Transform
k
[LMPR08] (see Section 4.6) – specifically the ring Zq [X]/(X 2 + 1), which is now ubiquitous throughout
practical lattice constructions including the three NIST lattice standards. An interesting side note is that
one early suggestion for speeding up NTRU was to use a polynomial ring that supported the Number
Theoretic Transform (NTT). But after an attack that exploited the structure of the proposed ring [Gen01],
the suggestion was to not use rings that allow for the NTT [Sil01], because the necessary structure appears
similar to the one exploited in [Gen01]. The theoretical results of [PR06, LM06], however, precise exactly
what properties one needs from the algebraic rings to have a connection to worst-case lattice problems
(the rings that were attacked by [Gen01] did not have the necessary property), and does not preclude one
from using rings that support the NTT. We can view this episode as a good example where theoretical
work enhances the efficiency of practical schemes.
2 In particular, it was shown that solving random instances of the SIS problem over polynomial rings

was as hard as worst-case lattice problems in lattices having some related algebraic structure.
3 The quantum requirement was later removed in [Pei09].
Vadim Lyubashevsky 3

scheme CRYSTALS-Dilithium (ML-DSA) [DKL+ 18, NIS24a]. In addition, we will also

give the main ideas behind other lattice-based KEMs like Frodo [BCD+ 16] and NTRU
[HPS98].
The target audience for this manuscript are persons who are already familiar with basic
public-key cryptography and ideas from proving security of cryptographic schemes using
reduction arguments. It’s therefore assumed that concepts such as indistinguishability,
the hybrid argument, CPA-secure encryption, random oracles, the Fiat-Shamir transform,
etc. are not too foreign. Those familiar with these concepts most likely first saw them
when studying public key cryptographic primitives based on the hardness of the discrete
log or RSA problems. Keeping the discrete logarithm constructions, such as ElGamal
encryption and Schnorr signatures, in mind will actually be very useful for understanding
the high-level ideas of the lattice constructions.
A difference that many people observe between classical cryptography based on factoring
or discrete logarithm and lattice cryptography is that lattice cryptography is “messy”.
Instead of there being one parameter from which security is derived, there are several
which affect the security in various ways. There are also many optimization tricks which
involve techniques such as dropping some low-order bits, rounding, etc. which make the
schemes seemingly more convoluted. On a positive note, many lattice constructions require
very few “deep” mathematical concepts – understanding and implementing Kyber and
Dilithium from scratch requires less mathematical background than a lot of elliptic curve
constructions.4 It takes a little practice and patience to get used to the issues that lattice
constructions present and so the reader is encouraged to go through this manuscript with
some pencil and paper to work out the details and get comfortable with the mess. Do
not worry if after working out the messy details, they almost immediately leave you. The
important thing is to understand the high-level concepts; then knowing that you were able
to work out the messy details once means that you should be able to repeat it if necessary.
There is a lot about lattices that this manuscript does not cover. For example, it does
not say anything about more “advanced” constructions beyond encryption or signatures –
a good overview of some of those may be found in [Pei16]. It also doesn’t say much about
precise cryptanalysis or the geometric aspects of lattice cryptography which are crucial to
understanding some more advanced constructions. A good reference for the geometrical
foundations of lattices is [MG02] and the lecture notes [Mic19]. Some recent papers
related to algorithms and cryptanalysis of the problems upon which the lattice-based NIST
standardization candidates are based include [ACD+ 18, AM18, ADH+ 19, DP23]. Notably
missing is also the other lattice-based signature scheme chosen to be standardized by NIST –
FALCON [PFH+ 17], understanding which would require a deeper dive into the geometry of
lattices, which can be started by studying the seminal works of [GPV08, Pei10, MP12] which
explain how to create lattice-based trapdoor sampling algorithms which are ubiquitous in
many lattice constructions, and then understand how these techniques are optimized for
the concrete instantiation of FALCON [DLP14, DP16, PP19].
While the main reason for the interest in lattice-based encryption and signatures is
their presumed resistance to quantum attacks, we do not broach this topic. The random
oracle model (ROM) where, in the security proof, a concrete cryptographic hash function
is replaced with a perfect random function to which the adversary only has oracle access,
has an analogue in the quantum setting (QROM) where the adversary is allowed to also
make quantum queries (i.e. querying the oracle on a superposition of inputs) to such
a function. While security proofs in the ROM do not immediately carry over to the
QROM setting, there have been many recent works bridging the two closer together (e.g.
4 This is not to say that there is no math in lattice cryptography. Cryptanalysis requires fairly deep
concepts from the geometry of numbers and algebraic number theory, and even understanding constructions
involving trapdoor sampling, such as the FALCON [PFH+ 17] digital signature scheme, requires some
fairly non-trivial number theory. But none of these are needed in this tutorial which only focuses on the
math needed for Kyber and Dilithium.
4 Basic Lattice Cryptography

[HHK17, SXY18, KLS18, DFMS19, LZ19, JMW24]) with the only remaining difference
being the tightness of, or the concrete parameters used in, the security reduction. At
the time of this writing, if one just replaces all the cryptographic functions with their
counterparts that have the requisite quantum security, then there aren’t any known
improved attacks on real-world schemes proven secure in the ROM if the adversary is given
the extra quantum power of querying the random oracle on a superposition of inputs.

Outline. This manuscript does not take the shortest path towards presenting Kyber and
Dilithium; but rather makes some detours in order to hit upon related topics that are
used throughout a lot of lattice cryptography. In Section 2, we present the framework for
lattice-based encryption over the ring Zq based on the hardness of the LWE problem that
stems from the original work of Regev [Reg09], with some variations and optimizations
from the works of [PVW08, ACPS09, LPS10, LPR10, LP11]. We also discuss many small,
but crucial, tricks for compressing the ciphertext. Some of these tricks are fairly general
and will also come in handy in the constructions presented in the later sections. In Section
3, we introduce lattices as geometric objects and describe the connection between the LWE
and SIS problems and the difficulty of solving lattice problems. In Section 4, we review
polynomial rings and instantiate the analogous version of the encryption scheme from
Section 2, which results in the Kyber (ML-KEM) encryption scheme. In that section we
also describe the Number Theory Transform algorithm which speeds up the operations
over some particular polynomial rings. Finally in Section 5, we present all the needed
techniques for constructing an optimized lattice-based analogue of the Schnorr signature
scheme, which Dilithium (ML-DSA) [DKL+ 18] is an example of. The scheme is built
by applying the Fiat-Shamir transform to a lattice-based Σ-protocol. The latter also
serves as a gateway to understanding more advanced lattice-based constructions such as
zero-knowledge proofs.

Acknowledgments. I thank Katharina Boudgoust, Katrine Laursen, Antonio Merino-

Gallardo, Haotian Lin, Daniele Micciancio, Laz Panard, and Christopher Patton for finding
typos and errors in previous versions of this manuscript. I am sure that I have managed
to sneak a few more past them, and I’ll try to periodically make updates as these are
unearthed. Should you find any such errors or typos, I would very much appreciate it
if you sent me a quick email! This work is supported by the EU H2020 ERC Project
101002845 PLAZA.
Vadim Lyubashevsky 5

2 Encryption
We begin our study of lattice-based cryptography by constructing a CPA-secure (i.e.
Chosen Plaintext Attack Secure) public key encryption scheme. Recall that CPA-secure
encryption scheme consists of three algorithms: key generation, encryption, and decryption.
The key generation algorithm outputs a public key/secret key pair. The encryption
algorithm takes as input the public key and a message, and produces a ciphertext. The
decryption algorithm, in turn, takes a ciphertext and the secret key and outputs the
message. The scheme is said to be CPA-secure if for any two messages of the adversary’s
choosing, the encryptions of the two messages are computationally indistinguishable.
We only discuss CPA-secure encryption in this section, as there are generic transfor-
mations (e.g. Fujisaki-Okamoto [FO99]) that convert CPA-secure encryption schemes to
CCA-secure ones (in which the adversary also has access to a decryption oracle) as well as
to key exchange protocols secure against active attackers (Section 4.8).
We point out that the schemes in this chapter, unlike their discrete log and factoring
analogues, are most efficiently instantiated in a way that gives rise to decryption errors.
That is, even if the key generation and encryption algorithms are run correctly, the
produced ciphertext may, with a very small probability, not decrypt to the message that
was encrypted. In general, having a small-enough decryption error (say, around 2−150 )
doesn’t appear to hurt the practical security of schemes; one just has to account for these
in the proofs of the transformations (e.g. [HHK17, SXY18]).5

2.1 Some Notation

All operations in this section will be performed in the ring (Zq , +, ×) with the usual
addition and multiplication of integers modulo q. For a set S, we write a ← S to mean
that a is chosen uniformly at random from the set S. For any positive integer β, we will
define the set
[β] = {−β, . . . − 1, 0, 1, . . . , β}. (1)
This notation naturally extends to vectors (and matrices) by writing, for example, [β]n×m
to denote an n × m matrix with coefficients in [β]. By default, all our vectors will be
column vectors. One can also indicate that a vector v is in [β]m by writing ∥v∥∞ ≤ β.
For an integer x, we write ⌈x⌋ to denote the closest integer to x, with ties being broken
upwards.
d−1
ai X i ∈ Z[X],
P
When, in later sections, we work with fixed-degree polynomials a =
i=0
we write a ← [β] to mean that all integer coefficients ai are chosen uniformly from [β].
Similarly, for a vector a ∈ Z[X]m , we write a ← [β]m to be the distribution in which
every polynomial ai in the vector a is chosen as ai ← [β]. Sometimes instead of uniformly
sampling from the set [β], we will want to sample from some distribution ψ. In that case
we similarly write a ← ψ or a ← ψ m , where a is either an integer or polynomial, and a is
a vector of integers or polynomials.

2.2 A Motivating Example

Let’s pretend for a second that for positive integers q, n ≥ m, and β ≪ q, the following
two distributions are computationally indistinguishable (in the security parameter related
to m):
5 If
handled “properly”, decryption errors do not cause any security issues. On the other hand, if
their presence is ignored, then schemes that are CPA-secure become trivially not secure in the CCA
security model. In some scenarios, like fully-homomorphic encryption schemes (FHE), where schemes are
only CPA-secure, one needs to be cognizant of the security implications that they cause in practice (c.f.
[LM21].)
6 Basic Lattice Cryptography

1. (A, As), where A ← Zn×m

q and s ← [β]m

2. (A, u), where A ← Zn×m

q and u ← Znq .

That is, we’re assuming that there exists no efficient algorithm which can tell whether the
sample he is given comes from the first or the second distribution. This indistinguishability
assumption is clearly false because one can use Gaussian elimination to invert A (or an
m × m sub-matrix of A) and check whether there is indeed an s ∈ [β]m satisfying As = u.
Please bear with this example, because a slightly modified version of this assumption forms
the foundation of most lattice cryptography. We will now use this assumption to construct
a simple CPA-secure public key encryption scheme that very much resembles the discrete
logarithm based ElGamal encryption scheme. The secret and public keys of the scheme are

sk : s ← [β]m , pk : (A ← Zm×m
q , t = As). (2)

To encrypt a message µ ∈ Zq , the encryptor picks a random vector r ← [β]m and outputs
the ciphertext (u, v) ∈ Zm
q × Zq where

(uT = rT A, v = rT t + µ). (3)

To decrypt, one simply computes

µ = v − uT s. (4)
Correctness of the scheme follows because

v − uT s = rT t + µ − rT As = rT As + µ − rT As = µ.6 (5)

The security of the scheme follows by our assumption and the hybrid argument. By the
assumption, the public key (A, t) in (2) is indistinguishable from uniform. The public key
m×(m+1)
matrix A′ = [A | t] ∈ Zq is therefore indistinguishable from uniform, and using our
assumption once more, we obtain that the distribution (A′ , rT A′ ) is also indistinguishable
from uniform based on the same assumption (except with n and m switched). It therefore
follows that the distribution of (A, t, u, v) is indistinguishable from uniform, and therefore
the scheme is CPA-secure.
Notice that we used our indistinguishability assumption twice – once for arguing that
the public key looks random, and the other time to argue that the ciphertext does. Instead
of choosing A ← Zm×mq , we could have chosen it randomly from Zn×m q for m ̸= n. If we
set m ≫ n, then one can show7 that the public key (A, t) is actually statistically-close to
being uniform. But then forming the ciphertext would still require us to use the absurd
indistinguishability assumption. So using the assumption at least once is inescapable.

2.3 The LWE Problem

We will now make a “small” adjustment to the assumption from the previous section which
will make it plausibly valid and still allow us to construct a cryptosystem following the
same outline. We now define a simple version of the Learning with Errors Problem (LWE)
[Reg09] upon which a lot of lattice cryptography rests.

Definition 1. For positive integers m, n, q, and β < q, the LWEn,m,q,β problem asks to
distinguish between the following two distributions:
6 Compare this with the ElGamal encryption scheme! There, the secret key is s and the public key is
A, t = As . The ciphertext is u = Ar , v = tr · µ, and decryption is v/us = Asr · µ/Ars = µ. The principle
for why decryption works is exactly the same, except in our example, we do not have commutativity and
so are multiplying by the vector rT on the left side and by s on the right.
7 Using a simple application of the Leftover Hash Lemma [IZ89, IN96]
Vadim Lyubashevsky 7

1. (A, As + e), where A ← Zn×m

q , s ← [β]m , e ← [β]n
2. (A, u), where A ← Zn×m
q and u ← Znq .
The crucial part that makes LWEn,m,q,β hard is the presence of the additional “error”
vector e which makes the Gaussian elimination attack inapplicable. The exact hardness of
the problem depends on the parameters n, m, q, and β, and we discuss this in some more
detail in Section 3. For now, it’s enough to know just that the problem becomes harder as
m and β/q grow. The parameter n is not known to have a large impact on the hardness of
the problem except in extreme cases where n is as large as approximately m2β+1 , in which
case one can build a distinguisher in time approximately m2β by linearization techniques
[AG11]. In the constructions that we will present throughout this chapter, n will never
need to be so large. Since the parameter n will not be particularly important, we will
sometimes omit it when stating the hardness assumption and just write LWEm,q,β .
We also mention that there is nothing too special about using the uniform distribution
for our secret and error terms – it just makes the presentation simpler and so we choose
to use this distribution for illustrative purposes. In the original definition of LWE, the
error distribution was chosen as a rounded Gaussian distribution – that is, one generates a
continuous random 0-centered Gaussian with some standard deviation and rounds it to
the nearest integer. This distribution was necessary for the average-case to worst-case
reduction proofs [Reg09, Pei09] showing that LWE is at least as hard as some worst-case
lattice problems. This restriction has since been shown to not be strictly necessary,
and one can use, for example, the uniform distribution [DM13, MP13]. Some practical
implementations, notably Kyber, use the binomial distribution to generate the errors (see
Section 4.7) because in practice it is sometimes faster to generate a string of bits and add
them up instead of generating a uniform element in [β].
To account for different distributions that one could use, we can define the LWE
problem relative to the distribution of the secrets ψ as:
Definition 2. For positive integers m, n, q, and a distribution ψ, the LWEn,m,q,ψ problem
asks to distinguish between the following two distributions:
1. (A, As + e), where A ← Zn×m
q , s ← ψm , e ← ψn
2. (A, u), where A ← Zn×m
q and u ← Znq .
For concreteness, we will mostly use the LWE from Definition 1, but once one accounts
for the specific properties of ψ (specifically the expected norm of the secrets generated by
this distribution), everything we say equally applies to the problem in Definition 2 as well.
Something to note is that in the definition of LWE, we are not setting any conditions
on the relative sizes of m, n and q. It’s therefore possible that some choices will lead to
trivially hard LWE instances. For example, if n < m and β is large-enough, then the
distribution (A, As + e) could indeed be statistically-close to (A, u). And then one clearly
should not be able to build an encryption scheme based on just this assumption, since
we would have an unconditionally-secure public key encryption scheme. The reason why
things will indeed not work out will become clear when we consider correctness of the
decryption. It is of course also possible to set parameters so that LWE is not a hard
problem. For example, if m = 1, then it is not difficult to figure out whether As + e is close
to a multiple of the vector A. We will discuss the hardness of the LWE problem in Section
3. Another note is that it is also possible to define LWE where the secret s is chosen to be
uniform in Zm q (being careful to then take n large enough so that the LWE problem does
not become trivially hard); and this is indeed how LWE was originally defined in [Reg09].
In [ACPS09], it was shown that taking s to be from the same distribution as e results in
an essentially equally-hard problem. For applications, it is usually more efficient to take s
to be smaller, and so we will only consider this version of the LWE problem.
8 Basic Lattice Cryptography

As was already explicit in the previous section, distinguishing (A, sT A + eT ) from the
uniform distribution is also the LWE problem, except with n and m interchanged – i.e. the
LWEm,n,q,ψ problem. Similarly, via the hybrid argument, distinguishing between

(A, As1 + e1 , . . . , Ast + et , s′T ′T ′T ′T

1 A + e1 , . . . , st′ A + et′ )

and uniform is as hard (with the distinguishing advantage increasing by a factor of at most
(t + t′ )) as the easier of either LWEn,m,q,ψ or LWEm,n,q,ψ .

2.3.1 An LWE-Based Encryption Scheme

In the rest of this section, we will present cryptosystems which stem from the original work
in [Reg09] and have been improved and generalized via a series of observations in various
follow-up works (c.f. [ACPS09, Pei09, LPS10, LP11, BCD+ 16]). We can view the scheme
in this section as a modification of the encryption scheme from Section 2.2, but based on
the hardness of LWEm,q,β instead of the clearly false assumption made there. Our first
modification will be the message µ – rather than being an arbitrary element in Zq , it will
now come from the set {0, 1}. The key generation from (2) is modified to:

sk : s ← [β]m , pk : (A ← Zm×m
q , t = As + e1 ), where e1 ← [β]m . (6)

To encrypt a message µ ∈ {0, 1}, the encryptor chooses r, e2 ← [β]m and e3 ← [β], and
outputs  lqk 
uT = rT A + eT2 , v = rT t + e3 + µ . (7)
2
Let’s first discuss a little notation. We are working in Zq , but the above equation has a
strange-looking term ⌈q/2⌋. What we mean by this is an element in Zq that’s closest to the
rational number q/2 (e.g. if q = 13, then ⌈q/2⌋ = 7). So the division operation is not in Zq
– i.e. we are not multiplying by q or the inverse of 2. (If we will ever want to do division in
Zq , we will instead write it as multiplication by an inverse). For presentation-purposes, we
will often omit the ⌈·⌋ symbol as simply write q/2 because the meaning should be clear.
Before discussing decryption, let’s go through the security argument to see why the
scheme is based on the hardness of LWEm,q,β . The argument is the same as in Section
2.2. The indistinguishability of the public key (A, t) from the uniform distribution over
m×(m+1)
Zq stems directly from the LWEm,q,β assumption. Rewriting the public key (A, t)
as a matrix A′ = [A | t], we see that the LWEm,q,β assumption again implies that the
 T !
e
distribution A′ , rT A′ + 2 is also indistinguishable from uniform. Thus (A, T, u, v)
e3
is indistinguishable from uniform for any µ ∈ {0, 1} based on LWEm,q,β . Note that we
used the LWEm,q,β assumption twice and the parameter m came into play as the number
of columns of A in the argument showing that the public key looks random, and then
as the number of rows in A in the argument that the ciphertext looks random. This is
intuitively the reason why it makes sense to set the number of rows and columns in A to
be equal when trying to minimize the combined size of the public key and ciphertext in
public key encryption. We discuss this topic further in Section 2.4, and in Section 2.5.5
also discuss some applications, and a sightly-modified cryptosystem, in which one may not
want to have the number of rows equal to the number of columns.
To decrypt, one computes v − uT s. But rather than this cleanly giving us the message
µ as in (4), we instead obtain
q
v − uT s = rT (As + e1 ) + e3 + µ − rT A + eT2 s


(8)
2
T q T
= r e1 + e3 + µ − e2 s (9)
2
Vadim Lyubashevsky 9

As in (5), the rT As terms in the above equation cancel out; we are however left
with some combinations of “error” terms. Luckily, all these error terms have coefficients
bounded by ±β, and so the vector products rT e1 and eT2 s in (9) each consist of m terms of
magnitude at most β 2 each. Therefore one can rewrite (9) as e + 2q µ where e ∈ [2mβ 2 + β],
and so if the parameters are set such that 2mβ 2 + β < q/4 the decryptor can determine µ
from looking at v − uT s by checking whether the preceding value is closer to 0 or to q/2.

2.3.2 Bounding the Total Error, Exactly

The value 2mβ 2 + β that we computed above is the upper bound on the error magnitude.
Because the coefficients of r, s, e1 , and e2 are chosen randomly in the range [β], which is
centered around 0, it is however quite unlikely√that the error will actually be so large. Due
to cancellations, it will in fact be closer to O( mβ 2 ). In general, we would be fine getting
a bound on the error such that with very high probability (say 1 − 2−150 ) the error will be
below q/4. This would imply that the probability of a decryption error is at most 2−150 .
Such small errors can be tolerated in applications and when using this CPA-encryption
scheme as a component of other constructions (e.g. CCA-secure encryption).
There are asymptotic ways to approximately compute such bounds, but when dealing
with concrete parameters and having β not too large, it is possible (using simple scripts)
to get the exact value for

Pr [rT e1 + e3 − eT2 s ∈ [α]] (10)

s,r,e1 ,e2 ←[β]m ,e3 ←[β]

using the fact that probability distributions of sums of random variables can be modeled
as products of polynomials. Suppose that A and B are random variables (possibly with
different distributions) over the finite set [γ]. For all i ∈ [γ], let Ai (resp. Bi ) be the
probability that A (resp. B) is equal to i. Now define the polynomials
γ
X γ
X
A(X) = Ai X i , B(X) = Bi X i .
i=−γ i=−γ

Let
2γ
X
C(X) = A(X) · B(X) = Ci X i
i=−2γ

be the product of A(X) and B(X). One can now make a direct connection between the
coefficients Ci and the probability that A + B = i. In particular,

Pr[A + B = i] = Ci . (11)

This implies that

α
X
Pr[A + B ∈ [α]] = Cα . (12)
i=−α

This directly carries over to computing the probability in (10) by noticing that rT e1 −eT2 s
is distributed as a sum of 2m independent random variables A, where

Ai = Pr[A = i] = Pr [xy = i],

x,y←[β]

and e3 is just a uniformly distributed random variable over [β]. So, for example, if β = 2,
then
2 4 2 9
A−4 = A4 = , A−2 = A2 = , A−1 = A1 = , A0 = ,
25 25 25 25
10 Basic Lattice Cryptography

and all the other Ai are 0. If we then write

 2m
2 −4 4 −2 2 −1 9 2 4 2 2 4
C(X) = X + X + X + + X+ X + X
25 25 25 25 25 25 25
 
1 −2 1 −1 1 1 1
· X + X + + X + X2 ,
5 5 5 5 5
α
P
then the probability in (10) is exactly Ci , where Ci are again the coefficients associated
i=−α
to X i in C(X). By setting α = q/4 − 1, we will obtain the probability that the decryption
algorithm in Section 2.3.1 will correctly decrypt.

2.4 Public Key and Ciphertext Size Trade-offs

We now know how to set the parameters m, q, β relative to one another so that the
encryption scheme in Section 2.3.1 correctly decrypts with overwhelming probability. We
haven’t yet discussed how one should set the parameters in order for it to be secure, and
we will defer this to a bit later. But we can still compute the sizes of the public key and
the ciphertext in terms of the parameters q, m, β.
The public key (see (6)) consists of a random matrix A ∈ Zm×m q and a vector t ∈ Zm
q .
Since A is completely random, there is no need to store it – if one creates A by choosing a
256-bit seed ρ and then defining A as the expansion of ρ using some cryptographic PRF
(e.g. SHAKE based on the SHA-3 function), then one only needs to store the 256 bits ρ
instead of the m2 log q bits of A. One will need to expand A from ρ when encrypting and
decrypting, but it’s often a worthwhile trade-off to do so in lieu of storing the A – and in
particular when the scheme is used as a KEM, one would much rather transmit ρ than the
entire A. The other part of the public key, t, depends on the secret key and so cannot
be compressed in a similar way, and thus the total public key size is 256 + m log q bits.
The ciphertext (u, v) ∈ Zm q × Zq can be represented using (m + 1) log q bits. Concrete
secure parameter settings will require taking m ≈ 700 and q ≈ 213 , and so it is somewhat
inefficient to have the encryption of just one plaintext bit be so large. We will now give a
generalization of the LWE encryption scheme that allows for various trade-offs between
the public key and ciphertext size.
The reason that our current LWE-based encryption scheme has such a large ciphertext
expansion is that u consists of m log q bits. To reduce the ciphertext expansion, we will
give a variant of the scheme that amortizes the ciphertext part u [PVW08] among the
encryption of many messages [MR09, BCD+ 16]. The trade-off is that the public key will
be larger. Suppose that we would like to encrypt N = kℓ bits, which we arrange into a
matrix M ∈ {0, 1}k×ℓ . The key generation procedure will now be

sk : S ← [β]m×ℓ , pk : A ← Zm×m , T = AS + E1 , where E1 ← [β]m×ℓ .

q (13)

Observe that, compared to (6), the public key size is now increased to 256 + ℓm log q bits.
The encryption algorithm proceeds analogously where the encryptor chooses R, E2 ←
[β]k×m and E3 ← [β]k×ℓ , and outputs the ciphertext
 q 
U = RA + E2 , V = RT + E3 + M . (14)
2
which is comprised of km log q + kℓ log q bits. To obtain a trade-off between the public
key and ciphertext sizes, one can vary the parameters k and ℓ, while keeping its product
(the total number of bits N ) fixed. To obtain
√ the minimum combined public key and
ciphertext√ size, one should set k ≈ ℓ ≈ N . In this way, encrypting N bits √ requires
≈ 256 + 2 N m log q + N log q bits, which in practice will be dominated by the 2 N m log q
Vadim Lyubashevsky 11

term because one generally never needs to use public key encryption to encrypt more than
N = 256 bits before switching to symmetric encryption.
The security of this cryptosystem is again directly based on LWEm,q,β . Notice that the
public key (A, AS + E1 ) can be rewritten as (A, As1 + e1 , . . . , Asℓ + eℓ ) where si and ei
are, respectively, the ith columns of S and E1 . The indistinguishability of (A, T) from
uniform then directly follows from LWEm,q,β using the usual hybrid argument with a loss
of log ℓ bits of security.8
Writing A′ = [A | T], we again use the LWEm,q,β assumption (and the hybrid argument)
to note that the distribution (A′ , RA′ + [E2 | E3 ]) is indistinguishable from the uniform
distribution, and therefore
 q 
(A, T, U, V) = A′ , RA′ + [E2 | E3 + M] (15)
2
is indistinguishable from uniform for any fixed message M.
Decryption is done exactly the same way as we’ve been doing it for all the other schemes
in this section. Given the ciphertext (U, V), the decryptor computes
q
V − US = R(AS + E1 ) + E3 + M − (RA + E2 )S (16)
2
q
= RE1 + E3 + M − E2 S. (17)
2

From above, observe that the (i, j)th coefficient of V − US is equal to

q
rT e1 + e3 + µ − eT2 s,
2

where rT and eT2 are the ith rows of R and E2 , e1 and s are the j th columns of E1 and S,
and e3 and µ are the (i, j)th positions of E3 and M. Since all the vectors are in Zm q and
all their coefficients were uniformly chosen from [β], we are in the exact same situation as
in (9) and so one can set the parameters m, q, β in the exact same way as before to have a
small decryption error.9

2.5 Some Variations and Optimizations

The scheme presented in the previous section is more of a general framework of what one
would do in practice. When instantiating such a scheme with concrete parameters, there
are several possible optimizations that one might consider, which we will describe next.
We should mention that it’s not easy to figure out exactly which optimizations one can
use and to exactly set the parameters optimally without actually trying some possibilities
and seeing what security / output size one gets.

2.5.1 Reducing the Ciphertext Size by Removing the Low-Order Part

The ciphertext part V contributes N log q bits to the total ciphertext size. Suppose that
instead of the encryptor publishing all log q bits of each coefficient of V as part of the
ciphertext, he wanted to transmit only κ bits per coefficient. This is possible, but will add
a further error to the decryption equation. Visualizing the additive group Zq as points
on a circle (c.f. Figure 1), we want to pick a set S ⊂ Zq of size 2κ so that the maximum
distance between neighboring points in S (measured in the number of Zq points between
8 As with many applications of the hybrid argument, it’s not clear in this case whether there is a real

security loss or it’s just an artifact of the proof.

9 Note that now the decryption error probability will be per coefficient of M (and the probabilities are

not independent), so one should use the union bound to bound the total decryption error.
12 Basic Lattice Cryptography

0
12 1

2
11

3
10

4
9
5
8
7 6

Figure 1: A representation of Z13 as points on a circle. If we define the set S = {⌈i · 13/4⌋ :
0 ≤ i < 4}, then it consists of the four points 0, 3, 7, 10. S can thus be represented by 2
bits and every point in Z13 is within a distance of ⌈13/8⌉ = 2 of one of the elements of S.

them) is as small as possible. Note that q/2κ is the smallest we can hope for, so we would
like to get as close as possible to this number. One could define such a set as
S = {⌈i · q/2κ ⌋ : 0 ≤ i < 2κ }. (18)
If 2κ | q, then the distance between all the neighboring points is the same. Otherwise all
distances are within 1 of each other, which is as good as one can hope for.
The crucial feature of the set S is that every v ∈ Zq is within a distance of ⌈q/2κ+1 ⌉
of some element of S. Let us define HIGHS (v) to be the element in S closest to v and
LOWS (v) to be v − HIGHS (v). Then instead of transmitting V ∈ Zk×ℓ q as part of the
ciphertext, one could transmit a V′ ∈ S k×ℓ = HIGHS (V). Note that there exists an
k×ℓ
E′ ∈ ⌈q/2κ+1 ⌉ = LOWS (V) such that V = V′ + E′ .


If the ciphertext (U, V′ ) is created in this fashion, then the decryption V′ − US will
produce
q
V′ − US = RE1 + E3 − E′ + M − E2 S, (19)
2
where the only difference with the decryption in (17) is the presence of the E′ term. Notice
that E′ has limited effect on the decryption error because the other error terms are involved
in an inner product which produce much larger coefficients in (19). In practice, one can
usually set κ to be a small constant like 3 or 4 without the decryption error increasing
too much. This implies that instead of contributing N log q bits to the ciphertext, V
contributes just κN bits. Assuming that V is uniformly distributed, we can obtain the
exact distribution of E′ and then compute the decryption error probability using the exact
same techniques as in Section 2.3.2.
In some cases it may also make sense to use a similar bit reduction procedure on the
ciphertext part U. Here, though, one cannot remove bits without noticeably increasing
the decryption error because any error added to U will get multiplied by S, and so we
would get an additional E′′ S term in (19), where E′′ is defined analogously to E′ . But
because U is the dominant source of ciphertext size, reducing the number of bits in U
even by a little bit, could make a noticeable difference as well. The trick is then to balance
the decryption error and the ciphertext size using trial-and-error.

2.5.2 Modulus Switching / Compression / Decompression

We now make the discussion about compression from the previous section more concrete.
We first define an operation that takes an element from one set into another. When the
target set is smaller, then this can be seen as rounding, or compression. When the target
set is larger, this can be seen as lifting or decompression.
Vadim Lyubashevsky 13

Definition 3. For an element x ∈ Zq and some positive integer p, we define a mapping

from Zq to Zp as  
x·p
⌈x⌋q→p = ∈ Zp .
q
One should observe that the resulting element of Zp is independent of the exact
l x in kZq –l that is, kall elements
representative element l k in the set x + qZ produce the same
(x+qZ)p xp xp
result in Zp (since q = q + pZ = q + pZ); and thus the above definition is
well-formed. We now prove the core Lemma about how one could use the above function
to meaningfully compress and decompress data. In particular, it states that if one first
compresses an element in Zq to one in Zp (where p < q) and then decompresses back to
Zq , the result will not be too far away from the original element.

Lemma 1. For integers p < q and x ∈ Zq , it holds that

l k
⌈x⌋q→p = x + η ∈ Zq ,
p→q

q
for some η ∈ Z satisfying |η| ≤ 2p + 21 .

Proof. By definition of rounding, there exists a δ ∈ Q, |δ| ≤ 12 , such that for x ∈ Zq ,

 
xp xp
⌈x⌋q→p = = + δ ∈ Zp .
q q

Therefore,
  
xp
+ δ · q  
q
 = x + δq = x + δq + δ ′ ∈ Zq ,
l k 
⌈x⌋q→p =
p→q

 p p p

δq q
for some |δ ′ | ≤ 21 , which is a result of the rounding, and p ≤ 2p .

To relate the modulus switching operation from Definition 3 to the example in Section
2.5.1, we relate the definitions of S, κ, HIGHS , LOWS from the previous section to the notions
introduced here.

1. 2κ = p
n o
2. S = ⌈x⌋p→q , for x ∈ Zp
l k
3. HIGHS (x) = ⌈x⌋q→p
p→q

4. LOWS (x) = x − HIGHS (x)

And Lemma 1 proves that LOWS (x) ∈ [⌈q/2p⌉]. In implementations of compression, we

would of course not send the element HIGHS (x) ∈ Zq , but rather ⌈x⌋q→p ∈ Zp , because
the latter can be more compactly represented. One should think of HIGHS (x) ∈ Zq as the
decompression of the compression of x.
We also point out that recovering the message m from the noisy decryption output
as in (9) can also be done using the compression function. In particular, for an element
x ∈ Zq , ⌈x⌋q→2 will map to 0 if x is closer to 0 than to q/2, and to 1 otherwise. Thus one
can rewrite the decryption procedure (e.g. (8)) as

v − uT s q→2 .
 
(20)
14 Basic Lattice Cryptography

Another point worth mentioning is that, in terms of minimizing the distance between
all points HIGHS when S is fixed to be a certain size, the definition of S as in item (2) is
optimal for all p, q. For some particular values of p, q, we could, however, define the set S
differently, while still achieving the same optimality. The reason we may want to do this is
to avoid performing the ⌈x⌋q→p operation which requires division by (usually a prime) q.
For example, if we have p = 4 and q = 33, then we could define the set S = {0, 8, 16, 24}.
Notice that to compute HIGHS (x) for this set will only require modular reductions and
divisions modulo 8, which is usually a very efficient operation in CPUs since just register
shifts are required.
In the Kyber encryption scheme (Section 4.7), because the modulus q is small, we
are not able to find a prime that satisfies a condition we need for optimal multiplication
efficiency (see Section 4.6) and to have a set S such that rounding to it involves only the
nice operations above. Thus we use the generic definition of S as in item (2). In the
Dilithium signature scheme (Section 5.7), the modulus q is larger and so we are able to set
it so that we have a nice S and still have fast multiplication.

2.5.3 Learning with Rounding

By the LWE assumption, the distribution (A, t = As + e) ∈ Zn×m q × Znq looks indis-
tinguishable from uniform when the coefficients of s and e come from [β]. If we round
each coefficient of t to the nearest point in some subset S ⊆ Zq , as in Section 2.5.1, then
the distribution of (A, HIGHS (t)) is still indistinguishable from (A, HIGHS (u)), where u
is uniformly random. Let’s now examine t = As + e. Since e has coefficients in a small
subset [β], it may turn out that it doesn’t have any effect on the value of HIGHS (As + e).
In particular, when S is defined as in (18), then the probability  (over the
 randomness
n
β|S|
of A, s, e) that HIGHS (As + e) = HIGHS (As) is approximately 1 − 2q . To see this,
notice that if some coefficient of As is not within β/2 of the midpoint between two points
in S, then adding an error in [β] will not change the point in S to which it gets rounded.
So whenever q is large with respect to β and |S|, adding e doesn’t make a difference,
and so there is no reason to add it in the first place! Distinguishing the distribution
(A, HIGHS (As + e)) from uniform is called the Learning with Rounding (LWR) problem,
and it is at least as hard as LWE whenever adding e doesn’t affect the rounded output
[BPR12, AKPW13, BGM+ 16]. Sometimes this assumption is used in constructions of
encryption schemes even when the parameters do not permit a reduction from LWE (i.e.
q is not large enough). In this case, it’s a separate assumption and its relationship with
LWE is unclear.
The advantage of making the LWR assumption is that it permits smaller parameters
due to the fact that it does not add the error e. As an illustration, let’s take a look at (19).
The error E3 that was added in (14) is a term needed for the LWE assumption, whereas
the error E′ naturally occurred due to the rounding. Since we already have E′ , the E3
might be unnecessary. Thus under the LWR assumption, the rounding is performing two
functions – it adds a uniform-like error vector and it reduces the ciphertext size. Similarly,
instead of adding an error to the ciphertext U, we can simply round it to some (different)
set S which has the effect of adding deterministic error to U – thus making the E2 term
in (14) possibly redundant and unnecessary.

2.5.4 Encrypting More Bits per Slot

Our encryption scheme packed the N -bit message into a matrix M ∈ {0, 1}k×ℓ . We could
have instead, for example, packed it into a matrix
√ √
M ∈ {0, 1, . . . , 2b − 1}(k/ b)×(ℓ/ b)
.
Vadim Lyubashevsky 15

For decryption to work, we would need to make two small changes to the encryption and
decryption algorithms, while also adjusting the parameters. We will replace the 2q M term
in the encryption algorithm with 2qb M. The part of the decryption algorithm computing
V − US will then result in the 2q term being similarly replaced with 2qb in (17). This means
that in order for decryption to produce the correct result, one would need to have the
remaining error terms (i.e. the terms in (17) not involving M) be in [q/2b+1 ] rather than
[q/4] as before.
The trivial modification of the parameters in order for decryption to again work would
involve simply increasing q by a factor of approximately 2b−1 . Note that this could have a
positive effect of the size of the ciphertext and public key. The size of the public key in
(13) is 256 + ℓm log q bits. If we, for example, increase q by a factor of 2b−1 , but decrease ℓ
by a factor of 2, then the size will become 256 + ℓm2 (log q + b − 1) bits. This will be smaller
if b − 1 < log q. But increasing q while keeping everything else constant has the effect of
decreasing security (as mentioned in the beginning of Section 2.3, the problem becomes
harder as the ratio β/q grows), so we will need to either increase β or increase m. The
way to achieve the optimal parameters is to try a few possible options, or better yet, write
a script that does this for you.

2.5.5 LWE Encryption with a “Non-Square” Public Key

In all the versions of public key encryption that we presented thus far, the security proof
used the LWE assumption to argue that the public key is computationally indistinguishable
from uniform, and then used the uniformity of the public key and the LWE assumption
one more time to argue that the ciphertext is computationally indistinguishable from
uniform. It is sometimes, however, useful to have the public key be truly uniform. Or,
similarly, have the ciphertext be truly uniform under the (computational) assumption that
the public key was. In other words, for some applications we may want to apply the LWE
assumption only once. We’ll now explain how to construct such a cryptosystem and also
give some intuition for when something like this may actually be useful in practice.
To make the public key or the ciphertext uniform, we will need to use the leftover
hash lemma. This lemma applied to our scenario roughly states that if A ← Zn×m q (where
q is a prime) and s ← [β]m , where (2β + 1)m ≫ q n , then the distribution of (A, As) is
statistically-close to the distribution of (A, u), where u ← Znq . In other words, if s is
chosen uniformly from some set, then the size of this set should be larger than the size of
the range of the function As. With the leftover hash lemma in hand, it’s fairly easy to see
how one would modify either the key generation (13) or the encryption (14) procedure to
ensure that either the public key or the ciphertext are random.
If we would like the public key to be uniformly random, we replace (13) with

sk : S ← [β ′ ]m×ℓ , pk : A ← Zn×m , T = AS , where (2β ′ + 1)m > q n .

q (21)

Note that since we’re not using the LWE assumption twice, there is no longer a reason to
have β in the key generation be the same as in encryption – and so we give them different
names. The encryption and decryption equation can remain exactly as in (14) and (17).
When setting the parameters to make sure that decryption returns the correct answer, one
should pay attention to the fact that the term E2 S in (17) is larger due to the fact that
m and/or β ′ are larger than before, and also to the fact that the term RE1 in (17) is 0
because E1 does not exist in the key generation procedure.
The necessary modifications for the scenario where we would like to have the ciphertext
be uniformly-random (after applying the LWE assumption to conclude that the public key
in (13) is indistinguishable from random) uses the exact same principle. In particular, the
dimension of A and the distribution of R should be such that ([A | T], R[A | T]) where
[A | T] ← Zn×mq are indistinguishable from ([A | T], [U | V]), where U, V are uniform.
16 Basic Lattice Cryptography

Without going into much detail, we will now touch upon why one would want to have
either the public key or the ciphertext be truly uniform. The two examples we provide
are by no means exhaustive, but give a flavor about where and why sacrificing some
efficiency may be required. The main application of a uniform public key is in the lattice
construction of identity-based encryption [GPV08]. In this scenario, the public key of
a user with identity x ∈ {0, 1}∗ is (A, tx ), where tx = H(x) for a cryptographic hash
function H (modeled as a random oracle) that maps {0, 1}∗ to Znq . In other words, A is
common to all users, while tx is unique to every user and is uniformly-random. In an
IBE scheme, the public key of user x should be computable by anyone. It is therefore not
possible to generate it from some secret information (e.g. like the secret key) as in (6). On
the other hand, there needs to exist a way to associate a secret key with the public key.
The solution to this problem is for the master authority to possess a “trap-door” to A,
which allows him to create a low-norm vector sx satisfying Asx = tx . This sx is then the
secret decryption key of user x. Interestingly, note that the key generation is not done as
in (21) – in particular, the secret key is created after the public key. This is only possible
because the master authority created A together with a trapdoor. Despite this difference
in the order of key creation, the main result of [GPV08] provides algorithms such that the
distribution of A, s, t will be the same whether one chooses s before computing t or the
other way around.
An application where one would want the ciphertext to be uniformly random comes
up when there is a chance that something about the ciphertext randomness r is leaked.
It was observed in [AGV09] that one could leak something about r, and by the leftover
hash lemma, the ciphertext would still remain uniformly random because there is enough
entropy left in r.

2.5.6 Using Different Distributions for the Secret and the Error
Another possible optimization to the public key encryption scheme is to choose the
coefficients of the secret polynomials s, e1 , e2 , r from distinct distributions [ZYF+ 20]. In
particular, it may be beneficial to choose r, s ← ψ1 and e1 , e2 ← ψ2 where ψ1 ̸= ψ2 .
The intuition for splitting things up in this manner is as follows. Based on the currently
best known algorithms, the hardness of distinguishing (A, As + e1 ) from the uniform
distribution depends on the norm of the vector (s, e1 ) (see Section 3.3). We therefore may
want to strategically distribute the total fixed norm of (s, e1 ) between s and e1 . Note
that this is no longer the LWE problem as defined in this section, but it is perhaps also a
reasonable assumption.
To see why we may want to make the norms of s and e1 different comes from looking
at the error obtained during the decryption procedure in (9). To decrypt correctly, we
would like
rT e1 + eT2 s (22)
to be small – the smaller this value is, the smaller we can set the modulus q, which will
both make the LWE problem harder and reduce the public key size. To illustrate the
intuition, we will assume that all the vectors are chosen from Nσ – the zero-centered
normal distribution with standard deviation σ.10 If an n-dimensional√vector v is chosen
from Nσ , then it is known that ∥v∥ is tightly concentrated around σ · n. Furthermore, it
is also known that the inner product of a vector s ← Nσn and a vector v ∈ Rn is distributed
according to the distribution Nσ·∥v∥ . Using the above two facts, we can conclude that
if s, r ← Nσ1 and e1 , e2 ← Nσ2 , then (22) is distributed (roughly) according to the
distribution Nσ1 σ2 ·√2n . Also, the norm of the vectors (s, e1 ) and (r, e2 ) is approximately
p √
σ12 + σ22 · n.
10 Let’s ignore the fact that this distribution is continuous, rather than discrete. The same intuition

applies if we discretize the distribution in some natural way.

Vadim Lyubashevsky 17

We can now see that if in one case σ1 = σ2 = σ, then

√
∥(s, e1 )∥ = ∥(r, e2 )∥ ≈ σ · 2n, and (22) ∼ Nσ2 ·√2n . (23)
√
On the other hand, if we take σ1 = 43 σ, and σ2 = 2
3 σ, then we will have
√
∥(s, e1 )∥ = ∥(r, e2 )∥ ≈ σ · 2n, and (22) ∼ N 4√2 ·σ2 ·√2n . (24)
9

So the ℓ2 -norms of (s, e1 ) and (r, e2 ) are the same in both cases, but in the second
case the distribution of (22) has a smaller standard deviation, which means the error in
̸ σ2 . Whether one should indeed try and set σ1 =
(22) is smaller for the case where σ1 = ̸ σ2
depends on one’s belief that the hardness of the two LWE problems (one as in Definition 2
and one where s, e have different distributions) is equivalent.

2.6 Non-Interactive Key Exchange (NIKE)

The encryption schemes described in this section can be easily converted to a passively-
secure key transport scheme in which the two parties wish to agree on a shared symmetric
key (e.g. an AES key). The protocol would simply involve the first party creating a public
key (as in (13)) and sending it to the second party. The second party then chooses the
AES key and encrypts it as the message M and sends the ciphertext (as in (14)). The
first party then decrypts the shared key M.
While the above protocol is good enough for most purposes where classical key exchange
(e.g. Diffie-Hellman) is used, there is a critical order to the flow of the protocol. The
user sending M cannot send his message before receiving the public key. In the classical
Diffie-Hellman protocol, on the other hand, either user can send his g xi first. One can
similarly create a protocol with this property from the LWE problem, but it will be a
much less efficient way of exchanging keys where this arbitrary flow property isn’t needed.
We will describe this simple protocol for the case of agreeing on one random bit. To
agree on more bits, one would apply the same ideas as in Section 2.4. There is a public
random matrix A ∈ Zm×m q that is trusted by everyone to have been honestly generated (e.g.
it is expanded by SHAKE from the seed 0). Party i ∈ {1, 2} chooses vectors si , ei ← [β]m .
The first party sends u1T = sT1 A + eT1 , while the second sends u2 = As2 + e2 . Upon
receiving the message from the second party, the first party computes sT1 u2 and if this
value is closer to q/2 than to 0 (i.e. it’s between q/4 and 3q/4), it will set the shared bit
b1 = 1 (otherwise it will set b1 = 0). The second party computes u1T s2 and sets b2 = 0 or 1
using the same rule. In short, they end up with

sT1 u2 = sT1 As2 + sT1 e2 (25)

u1T s2 = sT1 As2 + eT1 s2 . (26)

and hope that the error terms sT1 e2 and eT1 s2 (which have maximum magnitude mβ 2 )
don’t cause b1 ̸= b2 .
Notice that the probability that b1 ̸= b2 is at most the probability that sT1 As2 falls
into the “dangerous” ranges near 3q/4 and q/4. In particular,
   hq i
3q 3q q
Pr[b1 ̸= b2 ] < Pr sT1 As2 ∈ + mβ 2 , − mβ 2 or + mβ 2 , − mβ 2 . (27)
4 4 4 4

The probability that sT1 As2 is any particular value in Zq is 1/q and so the above
probability is at most 4mβ 2 /q. In practice, one would use the techniques from Section √
2.3.2 to reduce this probability, but one would still end up with a probability of Ω(β 2 m/q)
of a mismatch between b1 and b2 . This is quite different than the situation we had with
18 Basic Lattice Cryptography

the encryption schemes where we could set parameters so that the decryption error is
exponentially small (or even 0) with respect to q. In the non-interactive key agreement,
getting a negligibly-small error will require setting q to be very large which has an adverse
effect on the communication size (see [GdKQ+ 24] where the concrete details are worked
out). There are, in fact, technical reasons for why this inefficiency may be intrinsic to
using LWE in the “natural way” for non-interactive key exchange [GKRS22].
Vadim Lyubashevsky 19

3 Hardness of LWE and Other Lattice Problems

We will now give a geometric view of the LWE problem. While this connection is not really
necessary for understanding how most cryptographic constructions work, it is crucial for
understanding their security.

3.1 Lattices
At the core of the geometric interpretation of the LWE problem are objects known as
lattices. An m-dimensional integer lattice Λ is simply a subgroup of the group (Zm , +).
Such a group can be described via a generating set called a basis. In particular, a lattice Λ
defined by a (full-rank) basis B ∈ Zm×m is
Λ = L(B) = {v ∈ Zm : ∃z ∈ Zm s.t. Bz = v}. (28)
In this chapter, we will just restrict ourselves to special types of lattices called q-ary
integer lattices, as these are the ones that are used in cryptographic constructions. They
also have the nice theoretical property that, asymptotically, solving some problem over
random instances of these lattices is as hard as solving some problem for any lattice. This
is the celebrated worst-case to average-case reduction line of research [Ajt96, Reg09] that
formed the foundation, and spearheaded the development, of lattice-based cryptography.
For a matrix A ∈ Zn×mq , the q-ary lattice Λ defined by A is

Λ = L⊥
q (A) = {v ∈ Z
m
: Av ≡ 0 (mod q)} (29)
It’s not hard to see that under the usual vector addition operation, the above set is a
group. For reader’s familiar with linear codes, the above two definitions of lattices are akin
to describing a code using a generating matrix (28) or a parity-check matrix (29). Even
more specifically, the lattices that we will be dealing with are
Λ = L⊥
q ([A | In ]), (30)
where In is the n × n identity matrix. This is not much of a restriction because if the
A in (29) contains n columns that are linearly independent over Zq (without loss of
generality, suppose that A = [A1 | A2 ] where A2 ∈ Zn×n q is invertible), then we can write
A−1
2 A = [A −1
2 A 1 | I] and L⊥
q (A) = L ⊥
q (A −1
2 A), where the latter is in the form of (30).
For lattices in the form of (30), it is also easy to switch between the “generator” matrix
representation in (28) and the “parity check” matrix representation in (29). It’s easy to
check that  
⊥ −Im 0
Lq ([A | In ]) = L . (31)
A qIn
In particular, if Av1 +v2 ≡ 0 mod q, then there exists some vector r such that Av1 +v2 = qr.
Then      
−Im 0 −v1 v
· = 1 . (32)
A qIn r v2
 
⊥ −Im 0
The above shows that all vectors in Lq ([A | In ]) are also in L and vice
A qIn
versa.

3.1.1 The Quotient Group and Determinant

The determinant of a full-rank lattice Λ ⊆ Zm , written as det(Λ), is the inverse of the
density of Λ in the space Zm . That is, if we define the set Sr = {z ∈ Zm : ∥z∥ < r}, then
|Sr |
det(Λ) = lim .
r→∞ |Λ ∩ Sr |
20 Basic Lattice Cryptography

If Λ = L(B) for a full-rank matrix B ∈ Zm×m , then det(Λ) = | det(B)|, where the
right-hand side is the usual matrix determinant of B. For example, the determinant of
the (n + m)-dimensional lattice in (31) is det(Λ) = | det(B)| = q n . Another equivalent
definition of the determinant of a full-rank m-dimensional lattice Λ is the size of the
quotient group Zm /Λ.
The parity-check representation of a lattice, Λ = L⊥ q (A), is convenient for checking
whether two vectors in Zm are in the same coset of Zm /Λ. In particular, z1 and z2 are
in the same coset if and only if Az1 ≡ Az2 (mod q). With this observation it’s easy to
see that when Λ = L⊥ n
q ([A | In ]), there are exactly q cosets; which is consistent with our
previous observation that the determinant of the lattice in (31) is q n .

3.1.2 Distance to the Lattice

For an m-dimensional lattice Λ and any vector r ∈ Zm (not necessarily in Λ), the ℓp -norm
distance from r to the lattice is defined as
∆p (r, Λ) = min ∥v − r∥p . (33)
v∈Λ

Observe that for any two elements r1 and r2 belonging to the same coset of Zm /Λ,
∆p (r1 , Λ) = ∆p (r2 , Λ), and so distances are well-defined notions for cosets as well. Therefore
if Λ = L⊥ q (A) and t ≡ Az (mod q) defines a coset z + Λ, then we write

∆C
p (t, Λ) = ∆p (z, Λ).

For clarity, we write ∆C instead of ∆ to denote that t is the image of the coset under
A, rather than some coset representative.
We will now prove some statements about the (non)-existence of short vectors in
random lattices. For simplicity, we will only prove them for the case that q is prime, but
with more care, one can prove similar statements for all q. Lemmas 2 and 3 show that
random cosets are far from random q-ary lattices and that q-ary lattices don’t have very
short vectors. Lemma 4 proves a partial converse, giving a lower bound on the length of
the shortest vector in any q-ary lattice.
Lemma 2. For any prime q and any t ∈ Znq \ {0},
Pr [∃z ∈ [β]n+m s.t. [A | In ]z ≡ t (mod q)] ≤ (2β + 1)n+m /q n
A←Zn×m
q

Proof. Since t is non-zero, some coefficient of z must also be non-zero. Without loss of
generality, assume that it’s the first one. Then we have that for a fixed z,
   
′ z1
Pr [[A | In ]z ≡ t (mod q) = Pr [a | A | In ] ′ ≡ t (mod q)
A←Zn×m
q
n×(m−1)
a←Zn ,A′ ←Zq z
q

= Pr n [az1 ≡ t − [A′ | In ]z′ (mod q)]

a←Zq

= Pr n [a ≡ z1−1 (t − [A′ | In ]z′ ) (mod q)] = q −n ,

a←Zq

where z −1 (mod q) exists because we assumed that gcd(z1 , q) = 1. Since there are
(2β + 1)n+m possible vectors in [β]n+m , the statement in the lemma follows by the union
bound.
Corollary 1.
∗
Pr [∆C n
∞ (t, Λ) ≤ β] ≤ (1 − |Zq |/q) + (2β + 1)
n+m n
/q ,
A←Zn×m
q ,t←Zn
q

where Λ = L⊥
q ([A | In ]).
Vadim Lyubashevsky 21

Some “popular” settings for q in lattice cryptography are prime q and q that are powers
of 2. In both of these cases, the first term in the probability bound is negligible in n
((1/q)n and 2−n , respectively). And so, whenever β 1+m/n ≪ q, random cosets will be
more than distance β away from Λ.
The next lemma states that the probability, over the choice of A ← Zn×m q , that the
⊥
lattice Lq ([A | In ]) has a short non-zero vector is small. We only prove this lemma for
a prime q, as it’s somewhat more messy for other choices. The proof of the lemma is
virtually identical to that of Lemma 2.
Lemma 3. For any prime q,

Pr [∃z ∈ [β]n+m \ {0} s.t. [A | In ]z ≡ 0 (mod q)] ≤ (2β + 1)n+m /q n .

A←Zn×m
q

The next Lemma is a converse of the one above; it gives a lower bound on the length
of an existing non-zero vector.
Lemma 4. For any q and any A ∈ Zn×m
q ,
h in+m
∃z ∈ q n/(n+m) \ {0} s.t. [A | In ]z ≡ 0 (mod q)

Proof. The proof is by the pigeonhole principle. There are more than (q n/(n+m) )n+m = q n
vectors in Zn+m whose coefficients are between 0 and q n/(n+m) . Since there are only q n
possibilities for the value of Az mod q, there must exist two distinct z1 , z2 with coefficients
 n+m
in the aforementioned range such that Az1 ≡ Az2 (mod q). Thus z1 −z2 ∈ q n/(n+m)
and A(z1 − z2 ) ≡ 0 (mod q).
Looking at the statements of Lemmas 3 and 4, we see that the boundary between there
existing a vector in Λ = L⊥q ([A | In ]) with coefficients in [β] and there not being one with
high probability is pretty sharp. Lemma 4 states that when β = q n/(n+m) , such a vector
always exists. On the other hand, if we set β < 14 q n/(n+m) , then the probability of there
being a vector in Λ with coefficients in [β] is less than 2−(n+m) .

3.2 Finding Short Vectors in Random Lattices (the SIS Problem)

A fundamental computational question one can ask about a lattice is to find a “short” (non-
zero) vector in it. When specifically tailored to the lattices we’ve been dealing with above,
the question simply becomes to find a non-zero z ∈ [β]n+m such that [A | In ]z ≡ 0 (mod q).
Lemma 4 states that when β = q n/(n+m) , such a vector surely exists, but the proof does
not give us any way of finding it. As of today, all known (quantum) algorithms for finding
such vectors (for uniformly random A) take 2Ω(m+n) time (c.f. [AKS01, ADRS15, AS18]).
The problem does get easier as β increases. Clearly if β = q/2, then the problem is
trivially solved by just setting the coefficients of z that are being multiplied by In to
the target coefficients. For smaller value of β, one would run an algorithm that finds
a vector in the lattice that is some factor larger than the smallest vector. All modern
efficient (i.e. polynomial-time) algorithms for finding such short vectors are descendants of
the famous LLL algorithm [LLL82] which guarantees to find a vector of length at most
2O(n+m) times larger than that of the shortest vector in the lattice. Lemma 4 then implies
 n+m
that for a random A, the LLL algorithm will find a vector z ∈ 2Ω(n+m) · q n/(n+m)
in L⊥ q ([A | In ]).
While the length of the vector the LLL algorithm is guaranteed to find is exponentially
larger (in the dimension of the lattice) than the length of the shortest vector, in practice,
22 Basic Lattice Cryptography

this exponent is not too large. Until experiments were run with lattices of sufficiently high
dimension (at least 100), it wasn’t even clear whether the real approximation factor of
LLL for random lattices was exponential or just linear. As it turns out, the approximation
factor is indeed exponential in the dimension, but the base of the exponent is rather small.
Experiments in [GN08, MR09] showed that one can find non-trivial vectors (i.e. those
that are not multiples of q) in random lattices Λ of the form (30) (of dimension m + n) of
length approximately

det(Λ)1/(n+m) · δ n+m = q n/(n+m) · δ n+m (34)

where δ depends on how much time the algorithm takes. Deducing a good approximation
to the running time of an LLL-type algorithm for a particular value of δ is fairly involved
(c.f. [ACD+ 18, ADH+ 19]) and is out of scope of this manuscript. As a very rough rule of
thumb, δ = 1.01 is considered within reach, whereas δ = 1.005 may never be achieved for
lattices of high-enough dimension (e.g. more than 500).
Note that if the dimension of the lattice L⊥
q ([A | In ]) is very large, one can just remove
arbitrarily many columns from A and run LLL on the resulting lattice. In particular, it is
optimal to have the dimension of the lattice be
p
n log q/ log δ, (35)

(see [MR09, Chapter 3]) which results in the ℓ2 -norm of the non-trivial found vector being
√
22 n log q log δ .11 (36)

The problem of finding a short vector in a random lattice as in (30) is called the
SIS (Short Integer Solution) problem. It is known that solving random instances of this
problem is at least as hard as solving some related problem in all lattices [Ajt96, MR07].
We will write SISn,m,q,β to be the problem of finding a vector with coefficients in [β] when
given a random lattice as in (30).
Definition 4. For positive integers m, n, q, and β < q, the SISn,m,q,β problem asks to
find, for a randomly-chosen matrix A ← Zn×m
q , vectors s1 ∈ [β]m and s2 ∈ [β]n such that
As1 + s2 = 0 (mod q).
Notice that by Lemma 3, the SISn,m,q,β problem is vacuously hard when β ≪ 12 q n/(n+m)
and (36) statespthat the problem gets easier as β grows. Also note from (36) that once m
is larger than n log q/ log δ, then it has no impact on the hardness of the problem since
it does not figure in the formula for the size of the found vector. This is quite similar to
the situation in the LWEn,m,q,β problem, where the parameter n does not matter much.
And as in that case, we will just write SISn,q,β .
We defined the SISn,m,q,β problem in Definition 4 in the ℓ∞ norm, whereas the hardness
of finding a vector in (36) is in the ℓ2 norm. The reason we define the problem in the
ℓ∞ norm is because in the Dilithium signature scheme, which was designed to avoid
complicated operations,12 the hard problem is naturally in the ℓ∞ norm. A way that one
could use (36) to conclude something about the hardness of the problem in the ℓ∞ norm
is to note that finding a vector of ℓ∞ norm β requires to at least find a lattice of ℓ2 norm
in (36) multiplied by the square root of the dimension.
11 [MR09] only state this bound to be valid whenever the ℓ -norm of the found vector is less than q
2
and do not claim anything for when q is exceeded. Asymptotically, though, it appears that this bound is
still rather accurate when one, for example, is attempting to find short vectors with a bounded ℓ∞ -norm
≪ q/2. Then one could still use this bound with the corresponding ℓ2 -norm of the vector. There are some
small known optimizations (see e.g. [DKL+ 18]), but as a rough guide, this bound is still fairly good.
12 All sampling in the Dilithium signature scheme is done from the uniform distribution. More efficient

versions of the signature scheme are possible if one samples from somewhat more computationally involved
distributions (e.g. [Lyu12, DFPS22]).
Vadim Lyubashevsky 23

Figure 2: The hardness of LWEn,m,q,β and SISn,m,q,β for fixed n, m, q, and varying β. The
lines are not meant to describe the concrete hardness of these problems, but rather to
illustrate the dependence of the hardness of these problems on β. The intersection point is
approximately at β = q n/(n+m) .

3.3 The LWE Lattices

Let us now rephrase the LWEn,m,q,β problem from Section 2.3 in the language of lattices.
If we choose a random A ← Zn×m q and random s ← [β]m , e ← [β]n , and output (A, t =
As + e), then this is the same as outputting a lattice Λ = L⊥ q ([A | In ]) for a random A
and a coset t in Zmq /Λ such that ∆ C
∞ (t, Λ) ≤ β. On the other hand, outputting (A, u) for
a random u ← Znq is akin to outputting the lattice Λ and a random coset of Zm /Λ. The
LWEn,m,q,β problem can therefore be restated as trying to distinguish between cosets that
are close to the lattice and random cosets.
√
Our encryption scheme had m = n and for correctness we needed β 2 = O(q/ m),
√
and therefore β ≪ q. From Corollary 1, this implies that random cosets will be further
away than β from the lattice. Thus the LWEn,m,q,β problem for parameters that make the
encryption scheme work can be seen as distinguishing between cosets that are close to the
lattice with those that are far away.
We can now show how to use an algorithm that solves SIS to solve LWE. If we’re given
an LWEn,m,q,β instance (A, t = As + e), then the idea for distinguishing this from random
is to find short vectors r1 , r2 such that

rT1 · A + rT2 = 0. (37)

Once we find such vectors, we compute rT1 · t. If t is uniformly random, then this will be a
random element in Zq . On the other hand, if t = As + e, then

rT1 · t = rT1 · A · s + rT1 · e = −rT2 · s + rT1 · e. (38)

Since s, e have small norms, and we assumed that we also found short r1 , r2 , the above
implies that rT1 · t will also have a small norm, and this will allow us to distinguish an
LWE instance from a random one, and thus solve the LWE problem.
Finding r1 , r2 in (37) is equivalent to finding a short vector in the lattice L⊥ ([ AT | Im ]).
√ q
We know from (36) that we can find a vector in this lattice of norm 22 m log q log δ (note
T
√ because we used A , the n in (36) becomes an m), which implies that ∥(r1 , r2 )∥ ≤
that
22 m log q log δ . If s, e have coefficients chosen uniformly at random from [β], then the
24 Basic Lattice Cryptography

Table 1: Approximate values of δ-hardness of the LWEm,q,β problem for some parameters
that resemble those used in the Kyber encryption (ML-KEM) scheme

LWEm,q,β Parameters
m β q δ
512 2 212 1.0043
768 2 212 1.0029
1024 2 212 1.0022

Table 2: Approximate values of δ-hardness of the LWEm,q,β and SISn,q,β problems for
some parameters that resemble those used in the Dilithium (ML-DSA) signature scheme.

LWEm,q,β Parameters SISn,q,β Parameters

m β q δ n β q δ
1024 2 223 1.004 1024 218 223 1.0041
1280 4 223 1.003 1536 220 223 1.0032
1792 2 223 1.0023 2048 220 223 1.0025

variance of each of each coordinate is

β β
1 X
2 2 X 2 2 β · (β + 1) · (2β + 1) β · (β + 1)
i = i = · = , (39)
2β + 1 2β + 1 i=1 2β + 1 6 3
i=−β
q
and so the standard deviation is β·(β+1)
3 .
If we assume that
q each coefficient is, instead of uniformly, normally-distributed with
β·(β+1)
standard deviation 3 (this can be justified asymptotically by the central limit
theorem, but it is already a very good approximation for parameters used in lattice
cryptography), then we know that the distribution of −rT2 ·s+rT1 ·e is a normal distribution
with standard deviation
√
r r
β · (β + 1) 2 m log q log δ β · (β + 1)
∥(r1 , r2 )∥ · ≈2 · (40)
3 3
It is known (see [MR07]) that if√we have a normally-distributed random variable with
standard deviation greater than 3 · q and we reduce it modulo q, then the result is
statistically-close
√ (within ≈ 2−80 ) to the uniform distribution. Therefore if (40) is greater
than 3 · q, then the algorithm will not work. In other words, LWEn,m,q,β will be secure
(at least against this attack, which seems to be as good as any other known approach)
whenever p √
β · (β + 1) > 3 · q · 2−2 m log q log δ . (41)

3.4 Practical Parameters

We saw in Section 2.3.1 a construction of an encryption scheme based on the LWE problem.
In Table 1, we list some sample parameters similar to those that are used in concrete
practical instantiations – in particular as in the Kyber (ML-KEM) scheme that will be
described in Section 4.7. When building our signature scheme in Section 5, the security of
the scheme depends both on the hardness of the SIS problem and on LWE. In Table 2, we
give sample parameters that are used in the instantiation of that scheme.
Something worth pointing out is that the parameters in these tables are set based
on the best currently-known lattice-reduction algorithm (c.f. the well-supported online
Vadim Lyubashevsky 25

Lattice Estimator project [APS15]). For example, looking at the hardness graph of LWE
in Figure 2, we see a monotonic increase, without any sudden jumps, in the hardness of the
problem as the noise β increases. In particular, if q/β = 2m/k , where m is the dimension
of the lattice and 1 ≤ k ≤ m, then the best-known algorithm solves the LWE problem in
time (ignoring polynomial factors) approximately 2k .
But it is not out of the realm of possibilities that for all “small” values β, the problem
is easy and there is a sudden jump at some point. This is in fact exactly what happens
for the problem of finding short vectors in lattices that correspond√ to an ideal of some
algebraic ring [CGS14, BS16, CDPR16, CDW17]. √ When q/β > 2 m (i.e. when the k
from the above paragraph is smaller than m), the problem can be solved in quantum
polynomial
√ time (rather than 2k ), but as soon as the ratio q/β becomes smaller – i.e.
k > m, the hardness of the problem jumps back up to being 2k . It is therefore not
outside the realm of possibilities that some not-yet-invented (quantum) algorithm may
perform much better on a particular range of ratios q/β and yet yield no improvement
elsewhere. It may therefore be prudent, for security purposes, to build cryptography based
on the hardness of the LWEn,m,q,β problem where q/β is as small as possible.
26 Basic Lattice Cryptography

4 Encryption Over Polynomial Rings

The main inefficiency with the LWE-based encryption scheme in Section 2.3 was that it
required a fairly large ciphertext for encrypting one bit – in particular, the ciphertext
expansion was linear in the security parameter. This inefficiency was somewhat mitigated
by the scheme in Section 2.4 by making the ciphertext expansion only square root in the
security parameter at the expense of blowing up the public key by the same factor. In this
section, we will show how to get rid of this square root blow-up by considering the LWE
problem not over Zq , but over higher degree polynomial rings.

4.1 Polynomial Rings

The polynomial ring (Z[X], +, ×), with an indeterminate X, consists of elements of the
∞
ai X i , for ai ∈ Z, with the usual polynomial addition and multiplication
P
form a(X) =
i=0
operations. For convenience, we will often omit the indeterminate X, and simply write
a instead of a(X). The degree of a, denoted deg(a), is the largest i for which ai ̸= 0. A
polynomial a is monic if adeg(a) = 1 and it is irreducible if it cannot be written as a = bc
where b, c ∈ Z[X] and deg(b), deg(c) < deg(a).
The encryption schemes that we saw in Section 2 involved operations over the ring
(Z, +, ×). A generalization of this ring, with which we will be working with for the
remainder of the chapter, is the ring (Rf , +, ×), where f ∈ Z[X] is a monic polynomial of
d−1
degree d.13 The elements of Rf are the polynomials a = ai X i , where ai ∈ Z. The sum
P
i=0
of two elements in Rf simply involves summing the corresponding coefficients in Z. That
is,

d−1
X
a+b= (ai + bi )X i .
i=0

So the addition of polynomials in Rf can be seen as addition of vectors over Zd .

Multiplication of a polynomial by an element in Z therefore also has the same interpretation
as multiplying a vector by a constant.
Multiplication of two polynomials in Rf involves performing a normal polynomial
multiplication followed by a reduction modulo f . Reduction modulo f means (just like for
integers), the remainder after a division by f is performed. In particular, any polynomial
a ∈ Rf can be uniquely written as a = bf + r for b, r ∈ Rf where deg(r) < d. And so
a mod f = r.
To see that any a can indeed be decomposed in this fashion, we use induction. If
deg(a) < d, then a = r (and b = 0) and we’re done. Now suppose that all a of degree at
most k − 1 can be written as a = bf + r and let a′ have degree k. Then a′ − a′k f X k−d has
degree at most k − 1 and by the inductive hypothesis can be written as bf + r for some b
and r. We can therefore write a′ = a′k X k−d + b f + r.

To prove that the above decomposition of a is unique, assume for contradiction

that there are distinct (b, r) ̸= (b′ , r′ ) such that bf + r = b′ f + r′ . This implies that
(b − b′ )f + (r − r′ ) = 0. Since deg(r − r′ ) < d, it must be that r = r′ . Then we know that
if (b − b′ ) ̸= 0, then deg((b − b′ )f ) = deg(b − b′ ) + deg(f ) ̸= 0. And so b = b′ and we have
a contradiction.
Note that the above proof of existence of b and r gives rise to a very simple algorithm
for computing a mod f – multiply f by an appropriate monomial αX i and subtract it away
from a to create a polynomial of a smaller degree and continue until getting a polynomial
13 In the lattice literature, this ring is often written as Z[X]/(f (X)).
Vadim Lyubashevsky 27

of degree less than d. For example if we would like to reduce 2X 3 + 8X 2 + 5X + 1 modulo

f = X 2 − 2X + 1, we write
2X 3 + 8X 2 + 5X + 1 ≡ 2(2X 2 − X) + 8X 2 + 5X + 1 ≡ 12X 2 + 3X + 1 (mod f )
≡ 12(2X − 1) + 3X + 1 ≡ 27X − 11 (mod f ).
As a simple observation, note that the usual ring (Z, +, ×) is a special instantiation of
the ring (Rf , +, ×) in which the polynomial f is defined to be f = X (in fact f = X − α,
for any α ∈ Z is also fine).

4.1.1 Polynomials and Linear Algebra

A useful observation is that polynomial multiplication modulo f can be written as a
multiplication of a matrix in Zd×d with a vector in Zd . Observe that the product ab mod f
can be written as:
d−1
! d−1
X X
i
ab mod f = a · bi X mod f = (aX i mod f )bi . (42)
i=0 i=0
i
Since each aX mod f is a polynomial of degree less than d, it can be thought of as a vector
in Zd . The multiplication ab can therefore be seen as a linear combination (with weights
bi ) of these d vectors, and thus can be represented as a matrix-vector multiplication. For
example, the product
(2X 2 − 1)(X 2 − X + 2) mod X 3 − X + 1 = 5X 2 − 3X
can be written as
     
−1 −2 0 2 0
0 1 −2 · −1 = −3 . (43)
2 0 1 1 5
d−1
ai X i ∈ Rf as vectors and matrices, it will be
P
When treating polynomials a =
i=0
convenient to use the notation Va ∈ Z and Ma ∈ Zd×d , where
d
 
a0
 a1  d
  d×d
 . . .  ∈ Z , and Ma = Va VaX mod f . . . VaX d−1 mod f ∈ Z
Va =  (44)


ad−1
We did not include f as part of the notation for Va and Ma , but the f should always
be evident from context.
Using this notation, we can rewrite (43) as
M2X 2 −1 · VX 2 −X+2 = V5X 2 −3X .
We
 can  also extend the above  notation to matrices
 of polynomials. For a vector
a1 a1,1 . . . a1,m
a = . . . ∈ Rnf and matrix A =  . . . . . . . . .  ∈ Rn×m
f , we define Va and MA as
an an,1 . . . an,m
   
Va1 Ma1,1 . . . Ma1,m
Va =  . . .  ∈ Zdn , and MA =  . . . ... . . .  ∈ Zdn×dm . (45)
Van Man,1 . . . Man,m
From the above definitions, one can check that for any A ∈ Rn×m
f and b ∈ Rm
f , we
have
MA · Vb = VAb ∈ Zdn (46)
28 Basic Lattice Cryptography

4.1.2 Coefficient Growth

When a and b are integers, the magnitude of their product is trivial to compute – it’s
just the absolute value of ab. For a, b ∈ Rf , bounding the magnitude of the product is a
bit more involved and is heavily dependent on the polynomial f . Because multiplication
ab ∈ Rf can be written as Ma Vb , a simple bound on the maximum coefficient of the
product is d∥Ma ∥∞ · ∥Vb ∥∞ , where ∥ · ∥∞ is the absolute value of the largest coefficient.
One could obtain better bounds (in the ℓ2 norm) by computing the maximum singular
value of Ma . But either way, the effect of f on the size of the coefficients in Ma is crucial
to bounding the product.
The best we could hope for, in terms of keeping Ma small, is that ∥Ma ∥∞ = ∥Va ∥∞ .
The only two polynomials f for which this holds are X d ± 1. For polynomials of the form
d
X d ± X d/2 + 1 and X i , we have ∥Ma ∥∞ ≤ 2∥Va ∥∞ . Here are some example matrices
P
i=0
Ma for a polynomial a = a0 + a1 X + a2 X 2 + a3 X 3 for several f ’s of degree 4.
 
a0 a3 a2 a1
a1 a0 a3 a2 
f = X 4 − 1 −→ Ma =  a2 a1 a0 a3 
 (47)
a3 a2 a1 a0
 
a0 −a3 −a2 −a1
a1 a0 −a3 −a2 
f = X 4 + 1 −→ Ma =   (48)
a2 a1 a0 −a3 
a3 a2 a1 a0
 
a0 −a3 −a2 −a1 − a3
a1 a0 −a3 −a2 
f = X 4 − X 2 + 1 −→ Ma =  a2 a1 + a3 a0 + a2 −a3 + a1 
 (49)
a3 a2 a1 + a3 a0 + a2
 
a0 −a3 −a2 + a3 −a1 + a2
a1 a0 − a3 −a2 −a1 + a3 
f = X 4 + X 3 + X 2 + X + 1 −→ Ma =  a2 a1 − a3 a0 − a2
 (50)
−a1 
a3 a2 − a3 a1 − a2 a0 − a1

There are also polynomials f for which ∥Ma ∥∞ ≫ ∥Va ∥∞ . Unsurprisingly, if f itself
has large coefficients, then ∥Ma ∥ will as well. But there are also f with small coefficients
that produce Ma ’s with exponentially larger coefficients than a – one such example is
f = X d + 2X d−1 + 1. Polynomials f that result in matrices Ma having much larger
coefficients than a are not useful for cryptographic purposes. In general, we prefer to use
polynomials that result in the ratio between ∥Ma ∥∞ and ∥Va ∥∞ to be 1 or 2.

4.2 The Generalized-LWE and SIS Problems

We now present a version of the LWE problem that is defined over general rings Rf , rather
than just over Z as in Definition 1. Analogously, we will be working over the ring Rq,f ,
which is like the ring Rf except that the polynomial coefficients are in Zq rather than in
Z. The ring Rq,f is often written in the lattice literature as Zq [X]/(f (X)).

Definition 5. For positive integers m, n, q, β < q, and ring Rq,f , the Rq,f -LWEn,m,β
problem asks to distinguish between the following two distributions:

1. (A, As + e), where A ← Rn×m m

q,f , s ← [β] , e ← [β]
n

2. (A, u), where A ← Rn×m

q,f and u ← Rnq,f .
Vadim Lyubashevsky 29

As before, the parameter n does not have any known effect on the hardness of the
problem, unless it is large, and so we will usually just write Rq,f -LWEm,β . The preceding
definition of the generalized LWE problem and the following cryptosystem follows the line
of work (which related its security to worst-case instances of certain lattice problems) of
[LPR10, BV11, LPR13b, LS15].
We can analogously generalize [PR06, LM06, LS15] the SIS problem from Definition 4
as follows:
Definition 6. For positive integers m, n, q, and β < q, and ring Rq,f , the Rq,f -SISn,m,β
problem asks to find, for a randomly-chosen matrix A ← Rn×m q,f , vectors s1 ∈ [β]
m
and
n
s2 ∈ [β] (not both being 0) such that As1 + s2 = 0 (mod q).
In the literature, the Generalized-LWE / Generalized-SIS problems are often referred to
as Ring-LWE / Ring-SIS or Module-LWE / Module-SIS. In the names chosen by NIST for
the lattice standards, ML-KEM and ML-DSA, the “ML” part stands for “Module Lattice”.

4.3 Generalized-LWE Encryption

The description of the encryption scheme is virtually identical to that in Section 2.3.1 with
the ring Z being replaced with Rf . The main advantage of the scheme will be that the
message µ, being in Rf , allows us to pack d bits into it.

sk : s ← [β]m , pk : (A ← Rm×m
q,f , t = As + e1 ), where e1 ← [β]m . (51)
To encrypt a message µ ∈ Rf whose coefficients are in {0, 1}, the encryptor samples
r, e2 ← [β]m and e3 ← [β], and outputs
 q 
uT = rT A + eT2 , v = rT t + e3 + µ . (52)
2
The security argument based on Rq,f -LWEm,β is identical to the proof based on
LWEm,q,β in Section 2.3.1.
To decrypt, one computes
q
v − uT s = rT (As + e1 ) + e3 + µ − rT A + eT2 s


(53)
2
T q T
= r e1 + e3 + µ − e2 s (54)
2
To compute the decryption error, we can rewrite the above equation (excluding 2q µ) as

MrT Ve1 + Ve3 − MeT2 Vs (55)

and then apply the techniques in Section 2.3.2 to compute the probability that none of
the d coefficients has magnitude greater than q/4. When f = X d ± 1, then for each of the
d coefficients, computing this probability is the same as when we worked over the integers
because the coefficients in every row of MrT and MeT2 are independent (see (47) and (48)).
One then applies the union bound to bound the probability that all d decryption errors
are small. For rings over other polynomials, one can still apply the techniques in Section
2.3.2 if one can rewrite the matrix-vector multiplication as a sum of independent random
variables.

4.3.1 Optimizations and Efficiency

The main advantage of the Generalized-LWE scheme is that one does not need to increase
the size of the public key, as in Section 2.4, in order to be able to encrypt a larger message.
When f has degree d, the ring naturally supports the encryption of d bits. So as long as
30 Basic Lattice Cryptography

we set d ≥ 256, which is the length of an AES (or any symmetric cipher) key that one
would encrypt using public key encryption, we are able to use an optimally-small public
key. Similarly, there is no need for packing more than one message bit per coefficient as in
Section 2.5.4. The optimization in Section 2.5.1 is still very useful and is applied in exactly
the same manner as before. The Learning with Rounding problem and cryptosystem
(Section 2.5.3), as well as the non-interactive key exchange (Section 2.6), are also defined
analogously for the ring Rf .

4.3.2 Security and Connection to Integer Lattices

The connection between polynomial operations in Rf and linear algebra over Z in (46)
allows us to make useful connections between the lattices we saw in Section 3.1 and (short)
solutions to polynomial equations involved in the Rq,f -LWEn,m,β definition in the previous
section. The hardness of the LWE-based encryption scheme relied on the hardness of
distinguishing (A, t = As + e) from uniformly random (A, u), for random A ∈ Zn×m q and
integer vectors s ∈ Zm n
q , e ∈ Zq with small coefficients. We saw in Section 3.3 that finding
a short vector in the lattice
L⊥ T
q ([A | Im ]) (56)

allowed us to build such a distinguisher and we based the concrete security of the LWE
encryption scheme on the hardness of this latter problem.
The security of the more efficient encryption scheme in this section is analogously based
on the hardness of of distinguishing (A, t = As + e) from uniformly random (A, u), for
random A ∈ Rn×m q,f and polynomial vectors s ∈ Rm n
q,f , e ∈ Rq,f with small coefficients. By
(46), this is equivalent to distinguishing (MA , Vt = MA Vs + Ve ) from uniformly random
(MA , Vu ). Since this distinguishing problem is now over Zq , we can transform it into a
problem about finding short vectors in integer lattices – that is, finding a vector with short
coefficients in the lattice L⊥ T
q ([MA | Idm ]) as above.
Because MTA is an dm × dn integer matrix, the dimension of the lattice

L⊥ T
q ([MA | Idm ])

is d(m + n). If the algebraic structure of Rf does not exhibit any weaknesses (see
Section 4.5 below), then the hardness of finding a short vector in this lattice is the same
as in the LWEn′ ,m′ ,q,β lattice in (56) with n′ = dn and m′ = dm. For the Rq,f -LWEn,m,β
problem, therefore, the important value is dm – the product of the degree of f in Rf
and the number of columns of A ∈ Rn×m f . Similarly, for the Rq,f -SISn,m,β problem, the
important value is dn – the product of the degree of f and the number of rows in A.

4.4 NTRU
The NTRU cryptosystem [HPS98] was the first truly efficient lattice-based encryption
scheme, and was also the first to propose using polynomial rings – specifically Rq,X d −1
– in lattice-based cryptography. The scheme was originally proposed as a trapdoor one-
way function, which can be seen as a OW-CPA cryptosystem.14 There is also a simple
modification that allows us to construct a CPA-secure encryption scheme [SS11]. In most
use cases, however, the trapdoor one-way function is sufficient since there is a black-box
transformation from such primitives to CCA-secure encryption schemes (c.f. [Den02]).

14 An encryption scheme is OW-CPA secure if an attacker, in possession of the public key, cannot recover

the message from a ciphertext of a randomly-chosen message.

Vadim Lyubashevsky 31

4.4.1 The NTRU Trapdoor 1-way Function

In the previous sections, we worked with the decision version of the Generalized-LWE
problem, but it is also very natural to define a search version of it. This problem could be
stated as finding the e when being given (a, as + e) for a ← Rq,f and s, e ← [β]. Notice
that if a is invertible in Rq,f , then finding e immediately also implies finding s.
The NTRU problem is very similar to the above, except that the polynomial a is not
chosen at random from Rq,f , but is rather the product of the integer p = (2β + 1) and
polynomials g1 and g2−1 where gi ← [β] (conditioned on g2 being invertible) and p being
relatively prime to q (e.g. β = 1 is a popular choice). The hardness behind NTRU relies
on the assumption that the search Rq,f -LWEn,m,β problem (with n = m = 1) is still hard
whenever a is not uniformly random, but is instead the product pg1 g2−1 .
The NTRU problem is formally defined as follows:
Definition 7. Let p = 2β + 1. Given (a, as + e), where a = pg1 g2−1 for g1 , g2 , s, e ← [β]
and g2 being invertible in Rq,f and Rp,f , find e.
Based on the presumed hardness of the above problem, we can construct a trapdoor
one-way function family as follows: to generate a random element from the family, we
choose secret invertible polynomials g1 , g2 ← [β] with g2 being invertible in Rq,f and Rp,f ,
and set the public key to be
a = pg1 g2−1 . (57)
The secret key is g2 .
The one-way function mapping s, e ← [β] to Rq,f computes

b = as + e ∈ Rq,f . (58)

Observe that in order to recover e and s from b, it is enough to recover these modulo p
since there is a 1-1 correspondence between elements in [β] and residues modulo p = 2β + 1.
To recover s, e modulo p using the secret key, one first computes

g2 b mod p = pg1 s + g2 e mod p = g2 e mod p. (59)

The equality g2 b = pg1 s + g2 e over the ring Rq,f simply follows from the definition of a
and b. Because the coefficients of gi , s, e, and p are small enough relative to q, the equality
g2 b = pg1 s + g2 e holds true not only in Rq,f , but also over Rf . Therefore it also holds
when both sides are reduced modulo p, and so only g2 e is left. If (59) holds, then we also
have
(g2 b mod p)g2−1 mod p = e, (60)
where we multiplied by the inverse of g2 in Rp,f . Once we have e (mod p), which is the
same as e ∈ [β], we can also compute

(b − e)a−1 = s. (61)

I would urge the reader for whom this is the first time seeing NTRU, to look at it again
and appreciate its subtleties. In particular, (59) holds despite the fact that one is doing
modular arithmetic using two relatively prime moduli, which is very rarely an idea that
leads to any meaningful results!

4.4.2 Security
If we don’t presume any special structure of the polynomial a, then recovering s, e in (58)
is identical to the attack on the public key of the Generalized-LWE instance in which we
try to find a short vector in the lattice

L⊥
q ([Ma | Vb | Id ]). (62)
32 Basic Lattice Cryptography

We can also try to recover the secret key g1 , g2 (or some other short polynomials related
to it) from a = pg1 g2−1 by looking for a short vector in the lattice

L⊥
q ([Mp−1 a | Id ]). (63)

The lattices in (62) and (63) look very similar, with the only relevant difference being
the presence of one extra vector Vb in (62). It was therefore somewhat surprising that in
certain scenarios, where q is significantly larger than β (but not so large as to be in the
space where generic lattice reduction algorithms clearly work), it was significantly easier to
find short vectors in the lattice in (63) than in (62) [ABD16, CJL16, KF17]. While these
attacks don’t translate to attacks against NTRU paramters, they do prevent the NTRU
assumption from being used in advanced primitives (e.g. FHE) that require large moduli
and small noise. For this reason, schemes based on Generalized-LWE (whose security relies
on essentially (62)) are used in such scenarios.

4.5 Exploiting the Algebraic Structure ... for Attacks

Suppose that we are working over the ring Rq,f with f = X d − 1. Because X − 1 is a
factor of X d − 1, there is a ring homomorphism from Rq,f to Rq,X−1 which maps elements
d−1 d−1
ai X i ∈ Rq,f to a′ =
P P
a= ai ∈ Rq,X−1 . Because the ring Rq,X−1 is exactly the
i=0 i=0
ring Zq with the usual addition and multiplication modulo q, we actually have a ring
homomorphism from Rq,f to Zq . What’s particularly special about this homomorphism
is that if the coefficients of a are small, then the image of a under the homomorphism
is small as well (i.e. can only be a factor of d larger). This implies the following simple
attack on the Rq,f -LWEm,β problem where we’re given A ∈ Rn×m n
q,f , t ∈ Rq,f and are asked
to decide whether there exist s, e with coefficients in [β] satisfying As + e = t (this attack
was first given against the Rq,f -SISn,m,β problem in [PR06, LM06], and we adapt it to an
attack against Rq,f -LWEn,m,β here):

Let A′ ∈ Zn×m
q , t′ ∈ Znq be images of A, t under the homomorphism. If there really
existed s ∈ [β] ⊂ Rm
m n n
f and e ∈ [β] ⊂ Rf satisfying As + e = t, then there exist
s ∈ [dβ] ⊂ Z , e ∈ [dβ] ⊂ Z satisfying A′ s′ + e′ = t′ . Because m and n are fairly
′ m m ′ n n

small, we are left with solving a small-dimensional LWE problem, which can be done as in
Section 3.3.
The most crucial element enabling the above attack on Rq,f -LWEm,β was that there
existed a homomorphism into a ring of a smaller degree which did not increase the coefficient
size by much. If f had a factor of, for example, X −2, then the above attack would not work
d−1 d−1
ai X i ∈ Rq,f to a′ = ai 2i ∈
P P
because the homomorphism would map an element a =
i=0 i=0
Zq , and so a′ would be in a range that is exponentially dependent on d. Interestingly, the
worst-case to average-case reductions showing that solving Rq,f -LWEm,β and Rq,f -SISn,m,β
implies finding short vectors in ideal / module lattices [PR06, LM06, LPR13a, LS15, PRS17]
only require that f be irreducible (or at least have a large-degree irreducible factor in
the case of Rq,f -SISn,m,β ) over the ring Z[X] and not Zq [X]. As we will see in the next
section, it is actually quite advantageous, in terms of implementation efficiency, to work
over a ring Rq,f where the polynomial f has many low-degree factors in Zq [X].

4.6 Exploiting the Algebraic Structure ... for Efficiency (The Number
Theoretic Transform)
The most computationally-involved algebraic operation in the Rq,f -LWEn,m,β encryption
scheme is multiplication of polynomials in Rq,f . The basic “school-book” polynomial
Vadim Lyubashevsky 33

multiplication of two polynomials of degree d requires O(d2 ) operations. There are better
methods like Karatsuba and Toom-Cook which take approximately O(d1.5 ) time. The
most efficient way to perform polynomial multiplication in Rq,f , which requires as few as
O(d log d) operations over Zq , is via the NTT (Number Theoretic Transform), which is a
special case of the FFT performed over the field Z∗q rather than over the complex numbers.
The idea of using special rings that support NTT for speeding up lattice-based primitives
was first used in the SWIFFT collision-resistant hash function [LMPR08], and is now
widely used in practical instantiations of other primitives such as encryption schemes (e.g.
[ADPS16, BDK+ 18]) and digital signatures (e.g. [DKL+ 18, PFH+ 17]).
We will now explain the NTT algorithm over the polynomial ring Zq [X]/(X d + α) for
α ∈ Z and d is a power of 2. Suppose that −α has a square root r in Zq , and we can therefore
write X d + α ≡ (X d/2 − r)(X d/2 + r) (mod q). Then computing ab ∈ Zq [X]/(X d + α)
can be done via the Chinese Remainder Theorem. That is, we can first compute

(a mod X d/2 − r, a mod X d/2 + r), (64)

d/2 d/2
(b mod X − r, b mod X + r), (65)

then component-wise multiply to obtain

(ab mod X d/2 − r, ab mod X d/2 + r), (66)

and then the above can be used to reconstruct ab mod X d + α.

In Lemma 5, we show that the decomposition (64), (65) requires d additions and d/2
multiplications over Zq , and the reconstruction of ab mod X d + α from (66) requires the
same amount of operations. Thus computing the product ab would require 2d additions, d
multiplications, and two multiplications over the ring Zq [X]/(X d/2 ± r). Since multiplica-
tions over the latter ring are still O(n2 ) time, it’s not clear that we made progress – but if
the polynomial X d/2 − r can be further factored as (X d/4 − s)(X d/4 + s) (and similarly
X d/2 + r = (X d/4 − t)(X d/4 + t)), then we can compute (66) recursively!
In particular, we can now compute the runtime of the entire algorithm using a recurrence
relation, where T (d) is the time to multiply two polynomials in Zq [X]/(X d + α), and A
and M is the time required to compute one integer addition and multiplication in Zq ,
respectively. From the above discussion, this recurrence relation is

T (d) = 2 · T (d/2) + 2d · A + d · M. (67)

If d is a power of 2 and −1 and −α have dth roots in Zq , then we can continue the recursion
until X d + α splits into linear factors and thus the above recurrence is well-defined for
d, d/2, d/4, . . . , 2.15 The solution to this recurrence is thus

T (d) = d · T (1) + 2d log d · A + d log d · M, (68)

where T (1) = M . So computing a product in the ring Zq [X]/(X d + α) could require as

few as 2d log d integer additions and d(log d + 1) multiplications over Zq .
When α = 1, the above gives us an efficient multiplication algorithm in the ring
Rq,X d +1 = Zq [X]/(X d + 1). In order to be able to split the polynomial X d + 1 all the
way down to linear terms, one needs that −1 has a dth root, or in other words, that the
15 To see why, let r, s ∈ Z∗ be such that r d = −α and sd = −1. We will prove the claim by induction. At
q
every level of the recursion, the invariant is that all factors will be of the form X k ± sl rk where 2 ≤ k ≤ d
is a power of 2 and k|l. This invariant is satisfied by the base case: X d + α = X d + sd rd . We now move
on to the inductive step: because k|l, if k/2 is an integer, then so is l/2, and so the terms of the form
X k − sl r√k factor into (X k/2 + sl/2 r k/2 )(X k/2 − sl/2 r k/2 ), while those of the form X k + sl r k factor as
√ √
(X k/2 + −1sl/2 rk/2 )(X k/2 − −1sl/2 rk/2 ). Replacing −1 = sd/2 , the preceding two factors are of
the form (X k/2 ± sl/2+d/2 rk/2 ). Since k|l and k|d, we have k2 | 2l + d2 , and the invariant at the next level
is satisfied. The recursion stops when k = 1.
34 Basic Lattice Cryptography

multiplicative group Z∗q has a 2dth root of unity.16 Such a root of unity exists whenever the
modulus q is a prime satisfying q ≡ 1 (mod 2d) (see Lemma 7). It should be noted that
even if q does not satisfy the latter, the NTT algorithm can still be performed; it’s just
that we will not be able to recurse all the way down to linear polynomials. For example,
if q ≡ 1 (mod d), then the polynomial X d + 1 can be split into a product of quadratic
terms. This means that at the bottom level the component-wise multiplication will be in
rings Zq [X]/(X 2 − ri ) for some ri ∈ Z∗q . This base multiplication, while requiring more
than just 1 multiplication over Zq , can still be performed with a small constant number of
multiplications and additions (i.e. 5 multiplications and 2 additions over Zq ). And because
we do one decomposition level less, the total number of operations is virtually identical.17
One also doesn’t necessarily need the polynomial f to be X d +1 to benefit from the NTT.
There are other (cyclotomic) polynomials that have a factorization tree very similar to
X d + 1. For example, for certain d = 2k · 3 and primes q, the polynomial f = X d − X d/2 + 1
factors into (X d/2 − r1 )(X d/2 − r2 ) modulo q and then one can apply the NTT recursion
algorithm to multiply over the rings Zq [X]/(X d/2 − ri ) – the main difference is that since
d is not a power of 2, we will not be able to factor X d/2 ± ri into degree 1 polynomials,
but rather into degree 3 ones. But overall, multiplication can be performed over such rings
(c.f. [LS19]) almost as efficiently as over Rq,X d +1 . One can also utilize NTT multiplication
over rings Rq,f for arbitrary f by multiplying over Zq [X] and then reducing modulo f .
Multiplication over Zq [X] can be performed by doing multiplication over Rq,X d +1 where
the degree d is chosen to be high enough so that reduction modulo X d + 1 never occurs
(i.e. d is set to an integer larger than 2 · (deg(f ) − 1)) – this algorithm very often is still
the most efficient way to multiply two elements over polynomial rings (c.f. [CHK+ 21]).
We now prove the lemma that we alluded to above which shows that the number of
operations needed in computing (64) and (65), and also in reconstructing the element in
the ring from its CRT representation in (66) requires d additions and d/2 multiplications.
Lemma 5. Suppose that a polynomial g(X) = X n + α can be written as

X n + α ≡ (X n/2 − r)(X n/2 + r) (mod q),

and define the function ϕ,

ϕ : Zq [X]/(X n + α) → Zq [X]/(X n/2 − r) × Zq [X]/(X n/2 + r)

 
ϕ(a) = a mod X n/2 − r, a mod X n/2 + r .

If r (mod q) and r−1 (mod q) are pre-computed, then ϕ and 2 · ϕ−1 can each be computed
using n additions/subtractions and n/2 multiplications over Zq .
Proof. If we write
n−1
X
a= ai X i ,
i=0
n/2−1
X
a mod X n/2 − r = bi X i ,
i=0
n/2−1
X
a mod X n/2 + r = ci X i ,
i=0

16 Recall that an element r is a k th root of unity if r k = 1 and r j ̸= 1 for all 0 < j < k. If r is a k th root

of unity, then it must be that rk/2 = −1.

17 One can easily solve the recurrence in (67) for the case when we are not able to go all the way down

to linear factors.
Vadim Lyubashevsky 35

then we can see that for all 0 ≤ i < n/2,

bi = ai + r · ai+n/2 ,
ci = ai − r · ai+n/2 .

Thus computing ϕ requires n/2 multiplications by r and n additions (or subtractions) to

compute ai ± r · ai+n/2 . For the reverse direction, we can reconstruct 2 · a by observing
from above that for all 0 ≤ i < n/2,

2 · ai = bi + ci ,
2 · ai+n/2 = r−1 · (bi − ci ).

The above two operations similarly require 2n additions (or subtractions) and n/2 multi-
plications.

Something a little peculiar to note in the statement of the above lemma is that we’re
not computing the inverse ϕ−1 , but rather 2 · ϕ−1 . The reason that we do this is that it
saves multiplications. In the recursive algorithm, the procedure in the lemma is run for
several (say log d) iterations, and the doubling of the inverse will keep accumulating so
that the final result is 2log d = d times larger than the correct answer. Then we simply
multiply only this last level by d−1 . So instead of performing extra multiplications by 2−1
at each of the log d levels, we perform it only at the final one.

4.6.1 Useful Algebraic Properties of the Ring Rq,X d +1

In the previous section, we saw a very efficient algorithm for multiplication over the ring
Rq,X d +1 , and we also saw that for security, it would be good to have the polynomial X d + 1
be irreducible over Z[X]. In this section, we state and prove some useful properties of the
ring Rq,X d +1 . The first lemma states that the polynomial X d + 1 is irreducible over the
integers exactly when d is a power of 2.

Lemma 6. The polynomial X d + 1 is irreducible over Z[X] if and only if d is a power of

2.

Proof. Let Φk (X) be the k th cyclotomic polynomial, and recall that for any n
Y
Xn − 1 = Φk (X).
k|n

Thus (X d + 1)(X d − 1) = X 2d − 1, and therefore

Q
X 2d − 1 k|2d Φk (X)
Y
d
X +1= d
= Q = Φk (X).
X −1 k|d Φk (X) k : k|2d , k∤d

If d = 2ℓ for some non-negative integer ℓ, then it follows from the above that X d + 1 =
Φ2d (X) and is thus irreducible (since all cyclotomic polynomials are irreducible). On the
other hand, if d = 2ℓ · d′ where d′ > 1 is odd, then both 2d and 2d/d′ = 2ℓ+1 divide 2d,
but do not divide d. So, Φ2d (X) and Φ2d/d′ (X) are distinct factors of X d + 1.

The next lemma is useful for picking the modulus q such that the polynomial X d + 1
factorizes into low-degree polynomials.
36 Basic Lattice Cryptography

Table 3: Parameters for the three instantiations of Kyber. The security of the three schemes
are approximately equivalent to that of AES-128, AES-192, and AES-256, respectively.

k η1 η2 du dv decryption error pk size ciphertext size

Kyber-512 2 3 2 10 4 2−139 800 B 768 B
Kyber-768 3 2 2 10 4 2−164 1184 B 1088 B
Kyber-1024 4 2 2 11 5 2−174 1568 B 1568 B

Lemma 7. Let d ≥ k ≥ 1 where k | d and q ≡ 1 (mod 2k) be a prime. Then there exist k
distinct ri ∈ Z∗q satisfying rik ≡ −1 (mod q) such that

k
Y
Xd + 1 ≡ (X d/k − ri ) (mod q). (69)
i=1

Proof. Because the prime q is such that q ≡ 1 (mod 2k), we have 2k | q − 1, and so there
exists an element r ∈ Z∗q of order 2k, and thus rk ≡ −1 (mod q). Furthermore, for all odd
i ∈ {0, . . . , k −1}, all r2i+1 are distinct modulo q and satisfy (r2i+1 )k ≡ −1 (mod q). The k
k−1
elements r2i+1 are thus the roots of X k + 1 and we therefore have X k + 1 ≡ (X − r2i+1 )
Q
i=0
(mod q). The lemma follows by substituting X with X d/k in the preceding equality.

The final lemma is not used anywhere in this manuscript, but we state it here for
completeness as it is useful to keep in mind for some advanced applications. It states that
for all primes q, the polynomial X d + 1 is never irreducible; so Rq,X d +1 is (unfortunately)
never a field. If one wants an “almost-field”, one could set ring parameters (see [LS18]) so
that the polynomial X d + 1 factors into two irreducible polynomials of the form X d/2 ± r.

Lemma 8. Let q be an odd prime and d be a multiple of 4. Then the polynomial X d + 1

factors into at least 2 polynomials over Zq [X].

Proof. If q ≡ 1 (mod 4), then the factors of X d + 1 modulo q are as in Lemma 7 when
setting k = 2.
If q ≡ 3 (mod 4), then for all x ∈ Z∗q exactly one of x or −x is a quadratic residue
modulo q.18 Set b = 1 if 2 is a quadratic residue modulo q, and b = −1 if −2 is. Finally
let r be such that r2 ≡ 2 · b (mod q). Then

Xd + 1 ≡ X d + (2b − r2 ) · X d/2 + 1 (mod q)

≡ (X d/2 + b)2 − r2 · X d/2 (mod q)
≡ (X d/2 + b + rX d/4 ) · (X d/2 + b − rX d/4 ) (mod q),

as claimed.

4.7 The Encryption Scheme CRYSTALS-Kyber (ML-KEM)

In this section, we will put everything together by giving a full description of the NIST
standardized CRYSTALS-Kyber (named ML-KEM by NIST) scheme, which is based on the
hardness of the generalized LWE problem. The scheme works over the ring R3329,X 256 +1
18 Tosee this, assume that they’re both quadratic non-residues or quadratic residues, and therefore their
product must be a quadratic residue, and so there is an r such that −x2 ≡ r2 (mod q). There is an integer
k such that q = 3 + 4k, and we raise both sides of the preceding congruence to the power 2k + 1 obtaining
−x4k+2 ≡ r4k+2 (mod q). Since 4k + 2 = q − 1, Fermat’s little theorem implies that x4k+2 and r4k+2
are congruent to 1 and we have the contradiction −1 ≡ 1 (mod q).
Vadim Lyubashevsky 37

Public parameters: k, η1 , η2 , du , dv ∈ Z+

CPA-KeyGen CPA-Encrypt(pk, m) CPA-Decrypt(sk, ciphertext)

A ← Rk×k3329,X 256 +1 (r, e1 , e2 ) ← ψηk1 × ψηk2 × ψη2 u′ := ⌈u⌋2du →q

v ′ := ⌈v⌋2dv →q
 
(s, e) ← ψηk1 × ψηk1 uT := rT A + eT1 q→2du
v := r t + e2 + q−1 m′ := v ′ − u′T s q→2
 T   
t := As + e 2 m q→2dv
pk = (A, t), sk = s ciphertext = (u, v)

Figure 3: The CRYSTALS-Kyber CPA-secure encryption scheme

and the distribution of the secrets is drawn from the binomial distribution, rather from
the uniform one that we have been working with so far. The main reason for using the
binomial distribution (which we will denote as ψη for a positive integer η) is simply because
it is easier to sample.
Definition 8. For an integer η, an element from the binomial distribution P ψη isPgenerated
as follows: generate random a1 , . . . aη , b1 , . . . , bη ← {0, 1} and output ai − bi . This
definition is naturally extended to polynomials, where for a ∈ Rf we would write a ← ψη
to denote that every integer coefficient of a is sampled independently according to ψη .
And similarly, for a vector (of polynomials) of dimension k, we write a ← ψηk to denote
that every element gets sampled according to ψk .
At the heart of the CRYSTALS-Kyber CCA-secure KEM is a CPA-secure encryption
scheme. The transformation from the latter to a CCA-secure KEM is generic and we
briefly describe it in Section 4.8. For the rest of the Section, though, we focus exclusively
on the CPA-secure encryption.
The CPA-secure encryption scheme Kyber is presented in Figure 3. The security
parameters for Kyber are k, η1 , η2 , where k is the main parameter that is being varied
between the security levels. The parameters du and dv specify the (log of) the size of set
S (c.f. Figure 1, (18)) to which the different parts of the ciphertext get rounded to. These
values determine the ciphertext size and the decryption error.
The key generation procedure is exactly as in (51) except the secret vectors s, e ∈
RkX 256 +1 are generated according to the binomial distribution instead of uniform. To
encrypt a binary polynomial m ∈ RX 256 +1 , the encryption procedure generates vectors
r, e1 ∈ RkX 256 +1 and a ring element e2 ∈ RX 256 +1 from the binomial distribution ψη
(with possibly different values of η – we will explain the intuition for this a bit later)
and computes the uncompressed ciphertext as in (52). We then apply the compression
function to the ciphertext (see Sections 2.5.1 and 2.5.2) to reduce the ciphertext size. The
decryption function is as in (54) with the compression function being used to recover the
0/1 coefficients as in (20).

Correctness and Decryption Error. To compute the decryption error, we look at the
term
 ′ l k
v − u′T s q→2 = ⌈v⌋2dv →q − uT 2du →q s
  
q→2
& % 
  
T q − 1 l
T T
 k 
=  r t + e2 +
 m − r A + e1 q→2du s
 2 q→2dv 2dv →q
d
2 →q
u

q→2
 
q − 1
= rT t + e2 + m + e′ − rT A + eT1 + e′′T s


2 q→2
38 Basic Lattice Cryptography

for e′ ∈ RX 256 +1 , e′′ ∈ RkX 256 +1 whose coefficients correspond to the η in Lemma 1.
Replacing t with As + e, we obtain
 
 ′ q−1 T
v − u′T s q→2 = rT e + e2 + m + e′ − (e1 + e′′ ) s

. (70)
2 q→2

The result of the above will be m if all the coefficients of

T
rT e + e2 + e′ − (e1 + e′′ ) s (71)

are less than q/4 in magnitude. Computing this probability is done as in Section 2.3.2.
We already discussed in Section 4.3 (see (55)) how one would adapt those techniques to
the ring setting. The only difference between (55) and (71) is that the latter also includes
the terms e′ and e′′ which resulted from the compression and decompression operations.
By assuming that the terms being compressed are uniformly-random, one can compute
the exact probability
l distribution
k of each coefficient of e′ and e′′ – i.e. the probability
distribution of ⌈x⌋q→2dv for random x ← Zq (resp. with du instead of dv ). Once
2dv →q
we compute the exact probability of error for one coefficient, we can apply the union bound
(i.e. multiply by 256) to obtain an upper bound on the error probability. The values of
these are given in Table 3.

Security. The security of Kyber is based on the hardness of the R3329,X 256 +1 -LWEk,ψ2
problem. The security proof works exactly as in the proof of the scheme in Sections 2.3.1
and 4.3. One thing to notice is that in Kyber-512, the value of η1 was set to 3, while
η2 = 2. This means that distinguishing the public key (A, t) from a uniformly-random one
is based on the hardness of the R3329,X 256 +1 -LWEk,ψ3 , while the hardness of distinguishing
the ciphertext from uniform is based on a “hybrid” distribution where the coefficients of
r are chosen from ψ3 , while those of e1 and e2 are from ψ2 . This is at least as hard as
T T
 T R3329,X
the
T
256 +1 -LWEk,ψ2 problem, but note that we don’t output r A + e1 , but rather
r A + e1 q→2du . This means that some extra error is being added like in the Learning
with Rounding Problem (see Section 2.5.3). The total combined error of coefficients
from ψ2 and the error created by compressing from 3329 to a set of size 2du = 1024 is
actually somewhat larger than ψ3 . So while, technically, the hardness of distinguishing
the ciphertext from a uniform string is based on the hardness of R3329,X 256 +1 -LWEk,ψ2 ,
in practice, we get a few extra bits of heuristic security and the problem should be as
hard as R3329,X 256 +1 -LWEk,ψ3 . The price we pay for having the coefficients of s, e, r being
sampled from ψ3 instead of ψ2 , and thus achieving this extra heuristic security, is that the
decryption error grows.

Computational Efficiency. There are several tricks that one can do to noticeably optimize
the efficiency of the scheme in Figure 3. Firstly, one need not store the public key part A
because it is generated uniformly at random. One can thus simply store a 256-bit seed ρ
and create A as H(ρ) where H is some cryptographic hash function (e.g. SHAKE) that
can expand a seed into an arbitrary-length random-looking string. The public key would
therefore consist of just (ρ, t).
As discussed in Section 4.6, the NTT algorithm allows for very efficient multiplication in
rings of the form Rq,X d +1 whenever q is of the form (Lemma 7) that allows for factorization
of X d + 1 into low-degree polynomials. The modulus in Kyber (i.e. 3329) is congruent
to 1 modulo 256, and therefore the polynomial X 256 + 1 splits into a product of degree 2
polynomials of the form (X 2 − ri ).19 . As notation, for a polynomial a ∈ RX 256 +1 , let us
19 The reason that the prime 3329 was chosen for Kyber is that there is no prime of similar size that splits

the polynomial X 256 + 1 into linear factors (i.e. there is no prime congruent to 1 (mod 512)). While it is
Vadim Lyubashevsky 39

denote by â its NTT representation:

â = (a mod X 2 − r1 , . . . , a mod X 2 − r128 ). (72)

Converting a into â (and â into a) takes O(d log d) operations. While this is quite fast,
the existence of the NTT representation allows us even further optimizations.
Notice that the polynomials comprising the matrix A are sampled at random. And in
order to efficiently do the multiplication As, we need to first convert the polynomials A
to their NTT representation as in (72). The simple observation is that because there is
a 1-1 correspondence between polynomials and their NTT representations, we can just
sample A randomly in its NTT representation already! Furthermore, the public key t can
be stored in its NTT representation and so there is no need to do an inverse NTT after
the multiplication. And since t in its NTT representation will be needed anyway for the
computation of rT t in the encryption algorithm, this is a double-win.
On the other hand, note that we cannot sample s, e, r, e1 , and e directly in their
NTT representation because their distribution is not uniformly random. We also cannot
perform the compression operations ⌈·⌋q→p when the element is in its NTT representation.
Therefore some NTT computations will be necessary. Nevertheless, because the matrix A
consists of k polynomials, by sampling it in NTT form already, we avoid doing k 2 NTT
computations – which is a very substantial saving.

4.8 From CPA Encryption to a CCA-KEM

A Key Encapsulation Mechanism (KEM) allows two parties to exchange a random message
(shared key). It consists of three algorithms – KEM-KeyGen, KEM-Encaps, and KEM-
Decaps. The key generation algorithm outputs a secret key and a public key. The
encapsulation algorithm takes the public key as input and outputs a shared key and a
ciphertext. The decapsulation algorithm, in turn, takes the ciphertext and the secret key as
inputs and produces the same shared key as output. A CPA-secure KEM is one in which an
adversary cannot distinguish the shared key from uniform when given the public key and
ciphertext. Such a KEM can be constructed from any CPA-secure public key encryption
scheme by simply encrypting a random message and setting it as the shared key.20 To be
considered CCA-secure, the indistinguishability of the shared key from random should be
preserved even when the adversary has access to a decapsulation oracle which it may use
on anything other than the given ciphertext.
The conversion from a CPA-secure public key encryption scheme to a CCA-Secure
KEM follows the Fujisaki-Okamoto (FO) transform. The intuition behind the Fujisaki-
Okamoto transform is to make the decapsulation oracle “useless” to the adversary so that
the only time it produces a non-⊥ output is when it is given a ciphertext for which the
adversary already knows the message. The way the latter is accomplished is by making the
randomness used in constructing the ciphertext dependent on the message 21 and having
the decapsulation algorithm first decrypt the ciphertext to obtain the message, and then
re-encrypt it, and output ⊥ if the ciphertexts don’t match. This generic conversion is
presented in Figure 4.

somewhat messier to implement an NTT multiplication in a ring that does not fully split, as mentioned in
Section 4.6, there is virtually no computational difference between having X 256 + 1 split into linear or
quadratic terms.
20 To achieve slightly more “advanced” security notions, which we do not discuss here, one would not just

output a message as the shared key, but rather a hash of it with the public key, as in Figure 4. It is also
good cryptographic practice in most protocols to put all the public parameters as input to a cryptographic
hash function.
21 This makes the encryption scheme deterministic, but this does not pose problems because we’re always

encrypting random messages.

40 Basic Lattice Cryptography

Public parameters: The public parameters of the CPA-Encryption scheme from Figure 3

KEM-KeyGen KEM-Encaps(pk) KEM-Decaps(sk, c, h, z)

(pk, sk) ← CPA-KeyGen m ← {0, 1}256 ∈ RX 256 +1 m′ := CPA-Decrypt(sk, c)

pk := (A, t), sk := s (K, ρ) := H(m, pk) ∈ {0, 1}512 (K ′ , ρ′ ) := H(m′ , pk)
c := CPA-Encrypt(pk, m, ρ) c′ := CPA-Encrypt(pk, m′ , ρ′ )
Shared Key := K, ctxt := c if c ̸= c′ , then K ′ := ⊥
Shared Key := K ′

Figure 4: CCA-secure Key Encapsulation Scheme constructed using the Fujisaki-Okamoto

transform. The functions H and G are modeled as random oracles. The CPA-KeyGen,
CPA-Encrypt, and CPA-Decrypt algorithms are as in Figure 3 (though the construction is
rather generic), with the value ρ ∈ {0, 1}256 added to the CPA-Encrypt input represents
the random coins used in the procedure which is used in the generation of (r, e1 , e2 ).

Some Small Modifications Specifically for Lattice Encryption. There are a few modifi-
cations to Figure 4 that are present in the standardized ML-KEM (i.e. Kyber) owing to
the particulars of lattice-based encryption. Unlike in discrete logarithm schemes, the size of
the public key in lattice-based scheme is rather large (≈ 1KB) and the algebraic operations
that use the NTT are very fast compared to the much slower exponentiation or elliptic
curve multiplication operations in classical cryptography. Thus hashing the public key in
the encapsulation and decapsulation functions is actually a very computationally-noticeable
operation which could be somewhere between 30 and 50 percent of the running time when
the scheme is implemented using AVX-2 instructions. Because in many practical scenarios,
the decapsulation algorithm is run more often than key generation (e.g. the public key of
a party could be fixed), we can pre-hash the public key as h = G(pk) in the KEM-KeyGen
algorithm and store it, and then use G(pk) in the KEM-Encaps algorithm as input to H
(nothing is saved here) and use h in the KEM-Decaps algorithm instead of pk. In the
latter algorithm, the savings entail hashing only 32 bytes instead of ≈ 1KB.
Another change in the Kyber KEM is that ⊥ is never output, but rather in the case
that the ciphertexts do not match, a random key is output which is a hash of the input
ciphertext and some random secret value created during the key generation. The reasoning
for this is somewhat technical, and it is not really clear whether this adds any security in
practice.
Vadim Lyubashevsky 41

5 Digital Signatures from Σ-Protocols

In this section, we will strive towards a construction of a lattice-based digital signature
scheme whose high-level structure is similar to the classic discrete-log based Schnorr
signature scheme [Sch89]. In a Schnorr digital signature scheme, the public key consists of
two elements g, h in a finite field and the signature is a non-interactive Zero-Knowledge
Proof of Knowledge (ZKPoK) of an exponent x such that g x = h. The non-interactive
proof is obtained in two steps. First, we construct a 3-move interactive Σ-protocol that’s
an honest-verifier ZKPoK of an x satisfying g x = h. And secondly, we transform the
interactive proof into a non-interactive one using the Fiat-Shamir transform.

5.1 The Statements and Witnesses

We would like to now follow a similar road-map for constructing a signature scheme
from the Rq,f -LWEn,m,β and Rq,f -SISn,m,β problems. We can start with a Rq,f -LWEn,m,β
instance (A, t = As1 + s2 ), where A ← Rn×m m n
q,f , s1 ← [β] , s2 ← [β] , make A, t the public
key and hope to be able to create a zero-knowledge proof that proves knowledge of s1 , s2
in the appropriate range.22 Creating such a proof turns out to be less straight-forward
and significantly less efficient than in the discrete logarithm setting. The reason is that in
addition to proving the algebraic relation that the si satisfy As1 + s2 = t, we also need to
prove that the coefficients of si fall into a particular range (ideally [β], but [β̄] for some β̄
a little larger than β is also OK).
The most efficient signatures that stem from Σ-protocols go around the need for proving
knowledge of small s1 , s2 satisfying

As1 + s2 = t, (73)

and instead prove knowledge of a “relaxed” solution to the equation. In particular, we will
be giving protocols that allow a prover in possession of s1 ∈ [β]m , s2 ∈ [β]n satisfying the
above equation to prove knowledge of s̄1 , s̄2 with coefficients in a somewhat larger interval
than [β], and another element c̄ with small coefficients, satisfying

As̄1 + s̄2 = c̄t. (74)

A simple proof below shows that proving knowledge of (74) still proves something
meaningful. In particular, it will allow us to conclude that being able to produce such
s̄1 , s̄2 , and c̄ means that one can either solve Ring-LWE or Ring-SIS related to the matrix
A.

Lemma 9. Suppose that there is an algorithm, that when given A ← Rn×m q,f , t = As1 + s2
for s1 ← [β]m , s2 ← [β]n , is able to come up with s̄1 ∈ [β̄]m , s̄2 ∈ [β̄]n and c̄ ∈ [2] such that
As̄1 + s̄2 = c̄t. Then there is another algorithm, running in the same time, and having the
same probability of success, that solves either the Rq,f -LWEn,m,β or the Rq,f -SISn,m+1,β̄
problem.
n×(m+1)
Proof. Given a uniformly-random matrix Ā = [A | t] ∈ Rq,f , which is an instance of
the Rq,f -SISn,m+1,β̄ problem, the reduction sets (A, t) as the public key to the protocol in
Figure 5. By the Rq,f -LWEn,m,β assumption, this is computationally-indistinguishable from
the real key distribution. If there is an algorithm which can produce s̄1 , s̄2 , c̄ with coefficients
at most β̄ satisfying As̄1 +s̄2 = c̄t, then we have a solution to the Rq,f -SISn,m+1,β̄ instance
Ā.
22 Recall the notation from Section 4.2: for a polynomial s, s ← [β] means that all the coefficients of s

are chosen uniformly at random from the set [β] = {−β, . . . , 0, . . . , β} and s ← [β]n means that all the n
polynomials in the polynomial vector s have their coefficients chosen uniformly from the set [β].
42 Basic Lattice Cryptography

Note that in the above reduction, the Ring-SIS problem has dimension m + 1 (rather
than m) and completely ignores the fact that c̄ ∈ [2] rather than in [β̄]. Thus the Ring-SIS
problem from which it reduces is slightly easier than what is actually needed for a forgery.
A different argument allows us to obtain a reduction in which the dimension of the Ring-SIS
instance is not increased, and we present it below for completeness.
Lemma 10. Suppose that there is an algorithm, that when given A ← Rn×m q,f , t = As1 + s2
for s1 ← [β]m , s2 ← [β]n , is able to come up with s̄1 ∈ [β̄]m , s̄2 ∈ [β̄]n and c̄ with ∥c̄∥1 = η̄
such that As̄1 + s̄2 = c̄t; and this algorithm succeeds with probability ϵ. Set β ′ such that
(2β ′ + 1)n+m > q n · 2128/d . Then there exists another algorithm which can solve (at least
one of) Rq,f -LWEn,m,β , Rq,f -LWEn,m,β ′ or Rq,f -SISn,m,β̄+β ′ ·η̄ , which runs in the same
time and succeeds with probability ϵ − 2−128 .23
Proof. Let A be such an algorithm and suppose that we are given a matrix (A, t). We
pick random s′1 ← [β ′ ]m , s′2 ← [β ′ ]n and construct t′ = As′1 + s′2 . By the Rq,f -LWEn,m,β
and Rq,f -LWEn,m,β ′ assumptions, the distributions (A, t) and (A, t′ ) are computationally
indistinguishable and so A should produce s̄1 ∈ [β̄]m , s̄2 ∈ [β̄], and c̄ ∈ Rq,f with ∥c̄∥1 ≤ η̄
satisfying As̄1 + s̄2 = c̄t′ . This implies that
A(s̄1 − c̄s′1 ) + (s̄2 − c̄s′2 ) = 0. (75)
Since all the coefficients of s̄i − c̄s′i are in [β̄ +β ′ · η̄], we have a solution to Rq,f -SISn,m,β̄+β ′ ·η̄
– as long as at least one of s̄i − c̄s′i is non-zero. We will now show that this bad case can
happen with probability at most 2−128 . There are (2β ′ + 1)(n+m)·d possible values for s′1 , s′2 ,
while there are only q nd possible values for t′ . It is thus information-theoretically impossible
to guess the pre-image (s′1 , s′2 ) from t′ except with probability q nd /(2β ′ + 1)(n+m)d .24 By
our choice of β ′ , this probability is at most 2−128 .

5.1.1 The Challenge Space.

The size of the coefficients in c̄ (as well as s̄1 and s̄2 ) will be dependent on the challenge
space of the ZKPoK. Since we would like these to be small, we want to define our challenge
space so that it consists of polynomials with small norms.
If we’re working over the ring Rf where the degree of f is d, then define η to be the
smallest integer such that 2η · ηd > 2256 (we assume that d is large enough for such an η

to exist). Then we define the challenge set C ⊂ Rf as

C = {c ∈ [1], ∥c∥1 = η}, (76)
and the set of all (non-zero) differences as
C¯ = {c̄ = c1 − c2 , for c1 ̸= c2 ∈ C}. (77)
So C consists of all polynomials in Rf with exactly η non-zero coefficients taken from the
set {−1, 1}. By the definition of η, the size of C is exactly 2η · ηd . Note that we could

have defined C to also include polynomials with fewer than η non-zero coefficients, but this
would increase the complexity of sampling a random element in C while not increasing its
size by much.25
23 Because β ′ is approximately q n/(n+m) , the Rq,f -LWEn,m,β ′ problem is at the apex of its hardness
(see Figure 2), and so the reliance on this extra assumption presents no additional constraint in practice.
The main constraints will be the security of Rq,f -LWEn,m,β and Rq,f -SISn,m,β̄+β ′ ·η̄ .
24 To see this, observe that the optimal strategy for guessing the pre-image (s′ , s′ ) when seeing some
1 2
value t′ , is to deterministically guess the most likely pre-image. So the optimal guesser will output at
most q nd ′
possible pre-images. Since there are (2β + 1) (n+m)d total pre-images, each equally-likely to be
picked, only a q nd /(2β ′ + 1)(n+m)d fraction of them is ever output by the optimal guesser.
25 Sampling a random vector of length d with η ±1’s can be done by initializing a d-dimensional vector

with η 1’s, then performing a shuffle (e.g. Fisher-Yates) to obtain a random permutation of this vector,
and then randomly negating (or not) each of the 1’s.
Vadim Lyubashevsky 43

5.2 The Basic Σ-Protocol

We now describe the basic scheme, given in Figure 5, which was presented in [Lyu09]. An
unusual feature of this protocol is that it does not have perfect completeness. In order to
keep the coefficients of the output small, a rejection sampling step in the last round of the
Σ-protocol is performed in order to make sure that the distribution is independent of the
secret. In all the protocols in this manuscript, the rejection sampling step will be quite
simple – just checking whether all the coefficients are in a certain range. One can perform
slightly more complicated rejection sampling steps, which require sampling and rejecting
according to a discrete Gaussian distribution, which results in slightly smaller outputs
[Lyu12, DDLL13]. The main downside of these latter algorithms is that the rejection
sampling step is more complex and a slightly incorrect implementation may end up leaking
the secret key – it may also be more complicated to defend against side-channel attacks.
A simpler algorithm for such a widely-used primitive, like a digital signature, may thus be
preferable in practice.
The main consequence of the rejection sampling step is that the running time of the
signing algorithm will be a random variable (but independent of s1 , s2 ), rather than fixed.
Other than this, a reader familiar with Schnorr-type proofs will find a lot of similarities in
this protocol. The first stage of the protocol consists of creating the masking variables y1
and y2 , the second step is the challenge, and the last step consists of adding the mask to the
product of the challenge and the secret. A rejection sampling step is then performed, and
if the prover sends ⊥, he aborts and will need to restart the protocol. The transformation
of this protocol to a signature scheme will use the usual Fiat-Shamir transform, in which
the challenge is created as a hash of the message and the first message of the prover.
A common trick for keeping the size of the communication compact in an interactive
scheme is to send a hash of the first message instead of the message itself. Because the
unhashed first message can be recovered from those sent in the next rounds, the verifier is
able to compute the hash of this message during verification. In the lattice setting where
we use rejection sampling, this trick has an additional advantage in that it will allow us to
simulate transcripts in which a rejection occurs. This hashing is, however, unnecessary for
proving the security of the signature scheme because the signer does not see the aborted
signing attempts. For this reason, we will present the interactive scheme without the
hashing and only prove zero-knowledge in the case that no aborts (i.e. ⊥ is not sent) occur.

5.2.1 Honest Verifier Zero-Knowledge

We will now prove that the protocol in Figure 5 is HVZK. That is, we will show how to
create valid transcripts without knowledge of the secret s1 , s2 . The key to the proof is the
below lemma which shows that for all s1 , s2 with bounded coefficients, the probability of
⊥ is the same and that the distribution of z1 , z2 is independent of s1 , s2 .

Lemma 11. If γ ∈ Z+ is such that for all polynomials s ∈ [β], c ∈ C, we have cs ∈ [γ],
then for all si , c as in the protocol in Figure 5
 d(m+n)
2β̄ + 1
Pr [(z1 , z2 ) ̸= ⊥] = (78)
y1 ,y2 2(β̄ + γ) + 1
and
 d(m+n)
1
∀z′1 ∈ [β]m , z′2 ∈ [β]n , Pr [(z1 , z2 ) = (z′1 , z′2 ) | (z1 , z2 ) ̸= ⊥] = (79)
y1 ,y2 2β̄ + 1
     
z cs1 y
Proof. Consider 1 = + 1 as a sum of integer vectors, which written in notation
z2 cs2 y2
44 Basic Lattice Cryptography

Private information: s1 ∈ [β]m , s2 ∈ [β]n

Public information: A ∈ Rn×m n
q,f , t = As1 + s2 ∈ Rq,f

Prover Verifier

y1 ← [γ + β̄]m
y2 ← [γ + β̄]n ,
w := Ay1 + y2
w -
c←C
 c
z1 := cs1 + y1
z2 := cs2 + y2
/ [β̄]m or z2 ∈
if z1 ∈ / [β̄]n
then (z1 , z2 ) := ⊥
(z1 , z2 -
)
Accept iff z1 ∈ [β̄]m and z2 ∈ [β̄]n
and Az1 + z2 − ct = w

Figure 5: The basic Zero-Knowledge Proof System in which the prover knows s1 ∈
[β]m , s2 ∈ [β]n satisfying (73) and gives a ZKPoK of knowledge of s̄1 ∈ [2β̄]m , s̄2 ∈ [2β̄]n ,
and a c̄ ∈ C¯ satisfying (74). The value γ is defined in Lemma 11, and the value of β̄ affects
the completeness of the protocol (i.e. the probability that ⊥ is not sent) as specified in
Lemma 11.

from 4.1.1, is      
Vz1 V V
z= = cs1 + y1 ∈ Zd(n+m) .
Vz2 Vcs2 Vy2
The probability that the ith coefficient (for any i) of z is a particular coefficientνz ∈[β̄]
V
1
is exactly 2β̄+1 . The reason is the following: suppose that the ith coefficient in cs1 is
  Vcs2
V
νs , then the ith coefficient νy of the vector y1 will need to be exactly νz − νs . Notice
Vy2
that νz ∈ [β̄] and νs ∈ [γ] implies that νz − νs ∈ [β̄ + γ], which is exactly the range that
the coefficient νy gets selected from. Therefore the probability that νy will be this value is
1
exactly 2(β̄+γ)+1 . Thus
 d(m+n)
1
∀z′1 ∈ [β̄]m , z′2 ∈ [β̄]n , Pr [(z1 , z2 ) = (z′1 , z′2 )] = . (80)
y1 ,y2 2(β̄ + γ) + 1
And since there are (2β̄ + 1)d(m+n) possible valid (z′1 , z′2 ) ∈ [β̄]m × [β̄]n that could be sent,
we obtain the claim in the first part of the lemma (i.e. (78)).
To obtain the second part of the lemma, we observe that (79) = (80)/(78).
The probability of the prover not sending ⊥ is
 d(m+n)  d(m+n)  −d(m+n)
2β̄ + 1 β̄ γ
> = 1+ ≈ e−γd(m+n)/β̄ , (81)
2(β̄ + γ) + 1 β̄ + γ β̄
and so setting β̄ = γd(m + n) would result in the protocol requiring an expected number
of e repetitions before a non-⊥ value is sent. One could of course set β̄ to be smaller at
the cost of a higher number of expected repetitions.
Vadim Lyubashevsky 45

Public information: A ∈ Rn×m n

q,f , t ∈ Rq,f

Prover Extractor

w -
c, c′ ← C
′
 c  c
(z1 , z2 -
) (z′1 , z′2 -
)
z1 , z′1 ∈ [β̄]m and z2 , z′2 ∈ [β̄]n
Az1 + z2 − ct = w
Az′1 + z′2 − c′ t = w

Figure 6: Extraction procedure for (74).

We now use Lemma 11 to show how to simulate a non-aborting transcript with

the correct probability, which will show that the protocol in Figure 5 is honest-verifier
zero-knowledge in the case that ⊥ is not sent.
The simulator chooses random z1 ← [β̄]m , z2 ← [β̄]n , c ← C, sets w := Az1 + z2 − ct
and outputs (w, c, z1 , z2 ). This distribution perfectly simulates the non-aborting transcript
because c is uniform, and by Lemma 11, the values of z1 , z2 are uniformly random (for
any c); and w is uniquely determined by the other variables. This completes the proof
that the protocol in Figure 5 is HVZK when ⊥ is not sent.
Before continuing, we would like to remark that the probability with which the honest
prover will send ⊥ (and thus will have to repeat the protocol) is independent of the secret
s1 , s2 (Lemma 11). This is important in real-world applications where any dependence of
the running time on the secret would lead to side-channel attacks where the adversary
attempts to deduce some information about the secret by observing the running time of
the prover. The protocol in Figure 5 is therefore immune to this particular attack.

5.2.2 Proof of Knowledge

To show that the protocol is a PoK, we use the usual rewinding argument (see Figure
6) in which the prover sends ω and then successfully replies to two challenges c, c′ with
(z1 , z2 ) and (z′1 , z′2 ). If we can extract two such transcripts (w, c, z1 , z2 ) and (w, c′ , z′1 , z′2 )
satisfying the verification equation, then we have Az1 + z2 − ct = Az′1 + z′2 − c′ t. The
preceding simplifies to
A(z1 − z′1 ) + (z2 − z′2 ) = (c − c′ )t (82)
which is exactly the statement in (74) with s̄1 ∈ [2β̄]m , s̄2 ∈ [2β̄]n , c̄ ∈ [2].

5.2.3 Putting it All Together.

The Honest Verifier Zero-Knowledge property implies that an adversary gains no infor-
mation from seeing non-aborted transcripts. The Proof of Knowledge property implies
that an adversary who is able to impersonate a prover can produce a solution as in (74),
which implies by Lemma 9, that he can solve the Ring-LWE or the Ring-SIS problem.
The two properties together imply that (assuming Ring-SIS and Ring-LWE are hard) an
adversary cannot impersonate the prover in the protocol in Figure 5 even if he observes
previous non-aborting valid interactions. This allows us, using the Fiat-Shamir transform,
to construct a digital signature scheme secure, in the random oracle model, based on the
hardness of Ring-SIS and Ring-LWE..
46 Basic Lattice Cryptography

5.2.4 Setting the Parameters.

The proof of knowledge argument at the beginning of this section (see (82)) implies that
one can extract s̄1 , s̄2 with coefficients in [2β̄] and c̄ such that ∥c̄∥1 ≤ 2η which satisfy (74).
Lemma 9 then states that if Rq,f -LWEn,m,β is hard, then the above extraction implies
solving Rq,f -SISn,m+1,β̄ (or Rq,f -SISn,m,2(β̄+β ′ η) by Lemma 10). The optimal parameter
setting is therefore when these two problems are equally hard – i.e. the problems are on
the same vertical position in Figure 2. Choosing the parameter β̄ is dictated by Lemma 11.
As pointed out in (81), β̄ should be set to around γd(m + n), where γ is such that cs ∈ [γ]
for all s ∈ [β]. So if c is chosen such that ∥c∥1 ≤ η, then γ can be set to η · β. Thus β̄ is
approximately a factor ηd(m + n) larger than β.

5.3 Analogies to Discrete Logarithm Schemes:

Schnorr, Okamoto, and Katz-Wang.
In this section, we will dig deeper into the analogy between the lattice-based protocol
in Figure 5 and discrete log based protocols.26 As previously mentioned, the lattice
protocol and its Fiat-Shamir transformed signature scheme are very analogous to the
Schnorr identification and signature schemes [Sch89]. We will see in the following that
by simply changing the parameter β (and β̄ which is derived from it), one can obtain
schemes which have slightly different security characteristics which are analogous to other
discrete logarithm based schemes in the literature. At the end, it will turn out that the
Schnorr instantiation, where one is free to set β without any constraints, is the most
efficient variant; but we still we believe that it is instructive to see the other variants
to get more intuition for how lattice-based protocols are constructed and instantiated.
Indeed, understanding how parameters affect the nature of lattice schemes is an important
component of designing lattice cryptography protocols.

Schnorr. The public key in the Schnorr protocol consists of a random g and h = g x ,
where x is the secret key. In the first move, the prover picks a random masking variable y,
computes w = g y , and sends w to the verifier. The verifier sends a random challenge c, to
which the prover replies with z = y + xc, and the verifier checks that g z = tc · w.
To show that impersonation (in the honest verifier setting) implies breaking discrete log,
upon receiving the discrete log challenge (g, h), we set this to be the public key. Without
knowing the x such that g x = h, one can simulate honestly-generated transcripts (w, c, z)
by first picking random z, c, and then setting w = g z /tc . After this, it can be shown that
if the adversary is able to impersonate, then the usual rewinding argument obtains two
′ ′
transcripts (w, c, z) and (w, c′ , z ′ ) such that g z = tc · w and g z = tc · w. From this, we
obtain z̄ = z − z ′ and c̄ = c − c′ satisfying g z̄ = tc̄ . And from the latter, one can obtain a
valid discrete log solution z̄/c̄.

The lattice-based analogue in Figure 5 sets the public key as (A, t = As1 + s2 ) with
the secret key being s1 , s2 . In the lattice case, we extract the s̄i , c̄ satisfying (74), and
then use Lemma 9 to show that this implies a solution to Ring-SIS for the instance [A | t].
A minor difference is that in the case of Schnorr signatures, the public key (g, g x ) was
random, whereas in the lattice case, we needed the Ring-LWE assumption to argue that
the public key looks random in Lemma 9.

One should observe that algebraically, the lattice-based and the discrete-log based
schemes are quite similar. In both cases, there is some homomorphic one-way function
family F, and the public key consists of f, f (x), where f is a randomly-chosen member of
26 This section is not needed for the sequel and can be skipped if one only wishes to get to the final

construction of the lattice-based signature scheme.

Vadim Lyubashevsky 47

this family, and x is a randomly-chosen secret key. The first move consists of choosing
a random mask y and sending w = f (y). And on challenge c, the prover responds with
z = y + xc. Different properties of discrete log protocols are achieved by varying the
relationship between the size of the domain and range of f – and the lattice analogues are
obtained using the same blueprint, as we will now see.

Okamoto. The Okamoto protocol [Oka92] is similar in spirit to the Schnorr one with its
main differentiating characteristic being that one can prove the Okamoto identification
scheme secure against active adversaries – that is it can be proven secure even if the
verifier adversarially chooses the challenges c.27 . Since the Fiat-Shamir transformation
only requires HVZK, this stronger property of the Okamoto signature is not really needed
in practice for constructing digital signature schemes.
The public key in the Okamoto Scheme consists of random (g1 , g2 ) and h = g1x1 · g2x2 . In
the first move, the prover chooses random y1 , y2 and outputs w = g1y1 · g2y2 . Upon receiving
the challenge c, the prover outputs zi = yi + csi for i ∈ {1, 2}. The verifier checks that
g1z1 · g2z2 = hc · w. To prove the security of the Schnorr scheme, we needed to simulate
the transcript by first picking a random z, c and from these deriving w. In the Okamoto
scheme, one does not need to simulate – all one needs to do is honestly run the scheme.
The reduction from the discrete logarithm problem proceeds as follows: given a discrete
log instance (g1 , g2 ), where g2 = g1x for some unknown x, the extractor chooses a valid
secret key x1 , x2 and sets the public key to h = g1x1 · g2x2 . He can thus honestly answer all
of the adversary’s queries by honestly running the protocol. If the adversary afterwards
succeeds in impersonating the prover, then the usual rewinding argument leads to two
transcripts (w, c, z1 , z2 ) ̸= (w, c′ , z1′ , z2′ ) such that

w · hc = g1z1 · g2z2
′ z′ z′
w · hc = g11 · g22 ,

which can be re-written as

hc̄ = g1z̄1 · g2z̄2 , (83)
where c̄ = c − c′ and z̄i = zi − zi′ . By further rewriting h as g1x1 · g2x2 , one obtains

1 = g1z̄1 −x1 c̄ · g2z̄2 −x2 c̄ . (84)

Now observe that as long as z̄i − xi c̄ are not both 0, we can obtain a solution to the discrete
logarithm problem – that is find an x such that g1x = g2 .
Showing that with very high probability z̄i − xi c̄ will not equal to 0, we note that given
x′ x′
g1 , g2 , h = g1x1 · g2x2 , there are many possible x′1 , x′2 such that g1 1 · g2 2 = h – indeed, if
g1x = g2 , then any x′1 , x′2 satisfying x′1 + x · x′2 = x1 + x · x2 are valid. And any one of these
pairs is equally likely to have been chosen as the original secret key. We then need to prove
that the distribution of the transcripts in the Okamoto protocol (i.e. the w, c, z1 , z2 ) is
identical regardless of which of the valid secret keys was chosen (even when the adversary
has control of the c).28 Once this is established, one sees that if the algorithm impersonating
the prover can send z̄1 , z̄2 such that z̄i − xi c̄ = 0, then he knows the values xi = z̄i /c̄. But
these are information-theoretically hidden, and so there is not an overwhelming probability
that an (even all-powerful) impersonator can output such z̄i . Thus an impersonator can
be used to solve discrete log. Notice that the reason the same proof does not work in the
27While there is no reduction from the standard discrete log or DDH problems to the actively-secure
Schnorr signature scheme, one could prove the scheme secure based on certain “knowledge assumptions”
[BP02]
28 This follows from the fact that the z are uniform because the y are uniform, and then w is a
i i
deterministic function of the zi and c.
48 Basic Lattice Cryptography

Schnorr protocol is that the public key is (g, h = g x ), and there is only one possible secret
key x.
In the lattice setting, all one needs to do to move between Schnorr-like and Okamoto-like
schemes is to set the secret key s1 , s2 such that the public key (A, t = As1 + s2 ) does not,
with high probability, uniquely determine the secret key. This simply requires us to choose
a larger β. In particular, if we choose β such that (2β + 1)n+m > q n · 2128/d , then there is
only a 2−128 probability that any (all-powerful) algorithm can recover the exact (s1 , s2 ).29
And the fact that the transcripts do not leak any information about the si is proved in
Lemma 11.
But just like the Okamoto signature scheme being less efficient than the Schnorr one,
the added requirement on β will make this lattice-based instantiation less optimal. We
will discuss this in more detail after presenting the next Schnorr variant.

Katz-Wang. Another Schnorr-like protocol with slightly different security properties is

the Katz-Wang protocol [KW03, Section 3]. The differentiating feature of this scheme
is that it is based entirely on the DDH problem and its security proof does not require
rewinding. The advantage of not doing rewinding is that the security reduction is tighter.30
Thus, in theory, the [KW03] scheme has a tighter connection to a discrete-log type problem.
In the lattice setting, if one wanted to prove the security of the scheme in the Quantum
Random Oracle Model (QROM), where the adversary is assumed to be quantum and
cannot be straightforwardly rewound (because quantum states cannot be copied), then
having rewinding makes the security reduction even less tight. Both in the classical and
lattice settings, however, the tightness of the reduction from a discrete log or lattice
problem does not seem to affect the security of the signature schemes and so the Okamoto
and Katz-Wang schemes, as well as their lattice versions, remain mostly of only theoretical
interest.
The public key in the Katz-Wang scheme consists of random (g1 , g2 ) and (h1 = g1x , h2 =
x
g2 ) for a random secret x. To sign, one first creates a random mask y, then computes
(w1 = g1y , w2 = g2y ), and sends the wi to the verifier. Upon receiving a challenge c, the
prover computes z = y + cx. The verifier then checks whether giz = hci · wi .
The security reduction is from the DDH problem. Given a DDH instance (g1 , g2 , h1 , h2 ),
we are tasked with determining whether these elements are all random or whether there
is an x such that hi = gix .31 Given this (g1 , g2 , h1 , h2 ), we simply publish it as the
public key. One can then create transcripts of the interaction in the usual way by first
selecting z, then c, and then deriving the values for wi . When it’s the adversary’s turn to
impersonate, we observe that if (g1 , g2 , h1 , h2 ) is random, then, information-theoretically,
he only has a negligible chance of succeeding in outputting a valid z. In particular, if we
write h1 = g1x1 , h2 = g2x2 for x1 ̸= x2 , and w1 = g1r1 , w2 = g2r2 , for some ri , then
Pr[∃z s.t. g1z = hc1 · w1 ∧ g2z = hc2 · w2 ] = Pr[∃z s.t. z = x1 c + r1 ∧ z = x2 c + r2 ]
c c
= Pr[c = (r2 − r1 )/(x1 − x2 )]
c
= 1/|C|,
where C is the domain of the challenge space from which c is chosen. Thus seeing whether
the adversary can impersonate immediately gives us a solution to the DDH problem.
29 To see this, observe that the optimal strategy for guessing the pre-image (s , s ) when seeing some
1 2
value t, is to deterministically guess the most likely pre-image. Because the domain size of t is q nd , the
optimal guesser will output at most q nd possible pre-images. And since there are (2β + 1)(n+m)d total
pre-images, each equally-likely to be picked, only a q nd /(2β + 1)(n+m)d fraction of them is ever output by
the optimal guesser.
30 In the reduction that uses rewinding, there is a loss of a multiplicative factor of the number of random

oracle queries.
31 This formulation of the DDH problem is equivalent to the more common formulation where one is

asked to distinguish (g, g a , g b , g ab ) from uniform (simply define g2 = g a ).

Vadim Lyubashevsky 49

Figure 7: Sketching the intuition for optimal parameter selection of the Schnorr, Okamoto,
and Katz-Wang analogues of the lattice protocol from Figure 5. The constraints imposed
by the Okamoto and Katz-Wang variants result in less hard instances of the Ring-SIS /
Ring-LWE problems, which will require increasing the parameters (like n and m) in order
to increase the security of the scheme.

In the case of the lattice scheme from the protocol in Figure 5, the analogy to the
Katz-Wang scheme is obtained by setting the parameters so that β̄ is small-enough so
that, information-theoretically, there will not exist a valid response z1 , z2 when the public
key is uniformly-random (A, t). Note that in this case, seeing whether the adversary can
succeed, will allow us distinguish uniformly-random (A, t) from (A, t = As1 + s2 ), which is
exactly the Ring-LWE problem. In order to send z1 , z2 that will make the verifier accept,
we need them to have coefficients in [β̄] and satisfy Az1 + z2 = tc + w. What we would
like to show is that for all w, if the public key is chosen at random, then there is only one
possible challenge c for which there will exist such valid zi .
For contradiction, assume that there are two c, c′ ∈ C for which there exist z1 , z2 , z′1 , z′2
such that

Az1 + z2 = tc + w,
Az′1 + z′2 = tc′ + w.

Combining the two equations, we get

Az̄1 + z̄2 = tc̄, (85)

where z̄i = zi − z′i and c̄ = c − c′ . We can now use an argument similar to that in Lemma
2 to conclude that with high probability, for a random (A, t) such z̄i with coefficients in
[2β̄] do not exist.32
In order to set the parameter β̄ such that a solution to (85) doesn’t exist, with high
probability, we need β̄ to be somewhat less than q n/(n+m) (as in Lemma 2), and so β
would have to be even smaller, where the relationship between the two variables is still
dictated by Lemma 11. This, as in the case of the Katz-Wang scheme, results in a less
efficient instantiation than the Schnorr analogue.

Comparing the Efficiency/Security. The Okamoto and Katz-Wang analogues of the

lattice-based protocol introduce some constraints on the parameters β and β̄ that result in
a less efficient instantiation than if one were freely allowed to choose these values (subject to
the relationship between them established in Lemma 11). In Figure 2, we sketched how the
32 To use the analogy of that lemma over R
q,f instead of Zq , we need to make sure that the polynomials
z ∈ [2β̄] are invertible. One can ensure this by appropriately setting the parameters of the ring Rq,f (c.f.
[LS18, Corollary 1.2]).
50 Basic Lattice Cryptography

Private information: s1 ∈ [β]m , s2 ∈ [β]n

Public information: A ∈ Rn×m n
q,f , t = As1 + s2 ∈ Rq,f

Prover Verifier

y ← [γ + β̄]m
w := HIGHS (Ay)
w-
c←C
c
z := cs1 + y
/ [β̄]m or LOWS (Ay − cs2 ) ∈
if z ∈ / [δS − γ]n
then z := ⊥
z-
Accept iff z ∈ [β̄]m
and HIGHS (Az − ct) = w

Figure 8: Basic Zero-Knowledge Proof System with a smaller output. The set S ∈ Zq
has size 2κ and the function HIGHS , LOWS , and the constant δS are defined as in the text
of Section 5.4. The prover, who knows s1 ∈ [β]m , s2 ∈ [β]n satisfying (73), produces a
ZKPoK of s̄1 ∈ [2β̄]m , s̄2 ∈ [q/2κ ]n , and a c̄ ∈ C¯ satisfying (74). The value γ is defined in
Lemma 11, and the value of β̄ affects the completeness of the protocol (i.e. the probability
that ⊥ is not sent) as specified in (90).

security of the LWE and SIS problems evolve based on the parameter β. The intersection
point where LWEn,m,q,β and SISn,m,q,β problems (and their polynomial versions) meet
in hardness is at approximately q n/(n+m) . The optimal setting of the parameters for
the signature scheme from Figure 5 will be where β and β̄ are on different sides of this
intersection. In the Okamoto-like scheme, however, we need to set β > q n/(n+m) in order
for the public key to not uniquely determine the secret key, which puts β and β̄ on the same
side. In the Katz-Wang-like scheme, we need to have β̄ < q n/(n+m) in order to use the
information-theoretic argument, which again puts β and β̄ on the same side. We pictorially
demonstrate this in Figure 7, which should give the intuition for why the unconstrained
Schnorr-like variant of the scheme leads to the most efficient parameters.

5.4 Reducing the Proof Size

In this section we will show how to reduce the size of the proof of the protocol in Figure
5 by essentially removing the need to send z2 . The intuition is that to prove knowledge
of (74), it’s enough to output a proof corresponding to the s̄1 such that As̄1 ≈ c̄t. Thus
one does not, in principle, need to send the value corresponding to z2 . One needs to be
careful, though, to change the protocol so that it still remains zero-knowledge. The idea
for not sending z2 appeared in [GLP12, BG14], and the protocol we present in Figure 8 is
due to [BG14].
The idea, and execution, of not sending z2 is somewhat similar in spirit to the bit-
dropping idea for shortening the ciphertext in Section 2.5.1. As in that section, suppose
that we pick a set S ⊂ Zq of size 2κ so that the distance between any two elements in this
set is ≈ q/2κ (see (18)). Let us also recall the notation from that section with which we
can uniquely represent any w ∈ Zq as w = HIGHS (w) + LOWS (w), where HIGHs (w) ∈ S and
LOWS (w) = w − HIGHS (w) ∈ [q/2κ+1 ]. This notation can be naturally extended to vectors
Vadim Lyubashevsky 51

over Rq,f by applying this decomposition to each integer coefficient of each polynomial.
Also, define δS to be the largest integer such that for all 2κ elements si ∈ S, the sets
si + [δS ] are all disjoint. If we pick the points in S such that they are equidistant from
each other (with distances varying by at most 1 since q may not be divisible by 2κ ) on the
circle representing Zq , then δS will be approximately q/2κ+1 , which is also (again, within
1) the maximum value, over all w ∈ Zq , of LOWS (w). For the rest of the section, we will
assume that S is picked in such a manner. An important simple observation is that for all
positive γ < δS ,

LOWS (w) ∈ [δS − γ] and s ∈ [γ] =⇒ HIGHS (w) = HIGHS (w + s) (86)

With the above notation, consider the protocol in Figure 8. We will show that it is a
proof of knowledge of s̄1 ∈ [2β̄]m , s̄2 ∈ [q/2κ ]n , c̄ ∈ C¯ satisfying (74).

5.4.1 Correctness
For correctness (in the case that z ̸= ⊥), we need to show that HIGHS (Ay) = HIGHS (Az−ct).
If we write
Az − ct = A(cs1 + y) − c(As1 + s2 ) = Ay − cs2 , (87)
we know by one of the Prover’s conditions for not sending ⊥ that LOWS (Ay−cs2 ) ∈ [δS −γ]n .
The latter implies, by the observation in (86), that HIGHS (Ay) = HIGHS (Ay − cs2 ), and
therefore w = HIGHS (Az − ct).

5.4.2 Zero-Knowledge
As before, we will only show how to simulate transcripts in which ⊥ is not sent. From
Lemma 11, we know that conditioned on z ∈ [β̄]n , it is uniformly random. Thus our
simulation chooses a z uniformly random in [β̄]n and c ∈ C. He then checks whether
LOWS (Az − ct) ∈ [δS − γ]n . If it is not, then it resamples z and c and tries again. Once he is
successful, he sets w := HIGHS (Az − ct) and outputs the view (w, c, z). Because z has the
correct distribution after the first check passes and the second check is exactly the same
in the real proof and the simulation, the simulation perfectly simulates the non-aborting
transcripts.
In the above simulation, it is crucial that the simulator is able to perfectly simulate
the real prover’s check that

LOWS (Ay − cs2 ) ∈ [δS − γ]n . (88)

This is why this check, rather than a different and possibly less restrictive one, is performed
in the real proof. One does not need (88) to hold in order for the verification equation
to be satisfied. The scheme would still be complete if the prover directly checks that the
verifier will accept – i.e. simply check that w = HIGHS (Az − ct). But the simulator cannot
perform this check because he does not know w (w is set in the simulation after setting z
and checking (88)) and so the scheme would lose its ZK property. The check in (88) is
thus necessary in order to simultaneously ensure correctness and simulatability (and thus
security).

5.4.3 Computing the probability of ⊥

   2β̄+1 dm
Similarly to the calculation in Lemma 11, we know that Pry z ∈ [β̄]m = 2(β̄+γ)+1 ≈
e−γdm/β̄ (see (81)). To compute the probability that LOWS (Ay − cs2 ) ∈ [δS − γ]n , we make
the heuristic assumption that the distribution of Ay − cs2 is uniform in Rnq,f , and thus
52 Basic Lattice Cryptography

LOWS (Ay − cs2 ) is uniformly distributed in [δS ]n . Therefore the probability that a random
element in [δS ]n is inside [δS − γ]n is
 dn  dn
2(δS − γ) + 1 γ
> 1− ≈ e−γdn/δS . (89)
2δS + 1 δS

Combining the two probabilities, we obtain that

Pr [z ̸= ⊥] ≈ e−γd(m/β̄+n/δS ) . (90)
y

Note that a larger β̄ and a larger δS increase the correctness probability of the protocol.
But as we will see below, the larger these values are, the larger the coefficients in the
extracted s̄1 , s̄2 satisfying (74) will be.
We point out that even though we make the heuristic assumption to calculate the
probability that LOWS (Ay − cs2 ) ∈ [δS − γ]n , we do not need to use any heuristics to argue
that the probability of outputting ⊥ is independent of the secret key (which is needed
to prevent side-channel attacks). This is because the distribution of z is independent of
the secret key (Lemma 11), and LOWS (Ay − cs2 ) = LOWS (Az − ct), and thus this is also
independent of the secret key.

5.4.4 Proof of Knowledge

Via rewinding, the extractor can obtain two transcripts (w, c, z) and (w, c′ , z′ ) that satisfy
the verification equations, and thus HIGHS (Az − ct) = HIGHS (Az′ − c′ t). By definition,
we have

Az − ct = HIGHS (Az − ct) + LOWS (Az − ct)

Az′ − c′ t = HIGHS (Az′ − c′ t) + LOWS (Az′ − c′ t)

where LOWS (Az − ct), LOWS (Az − ct) ∈ [q/2κ+1 ]n ≈ [δS ]n . Subtracting the two above
equations, we obtain

A(z − z′ ) − (c − c′ )t = LOWS (Az − ct) − LOWS (Az′ − c′ t) ∈ [q/2κ ]n ≈ [2δS ]n , (91)

which is equivalent to (74) when we set s̄2 to LOWS (Az − ct) − LOWS (Az′ − c′ t).

5.5 Reducing the Public Key Size

We now continue improving the efficiency of the signature scheme by showing how to
decrease the size of the public key. Similarly to the intuition for removing the need to
transmit z2 from the protocol in Figure 5 in the previous section due to the fact that
Az1 ≈ ct, we also notice that if we write t = HIGHT (t) + LOWT (t) (where T ⊂ Zq ), then
Az1 ≈ c · (HIGHT (t) + LOWT (t)) ≈ c · HIGHT (t). In other words, the verifier does not need
to know the low-order bits of t in order to approximately verify the verification equation.
By not making LOWT (t) a part of the public key, we again run into a similar problem
as in the previous section in that without some adjustments to the protocol, the verifier
will want to compute HIGHS (Az − ct) because now he doesn’t even know t, but only
HIGHT (t). We will now describe the techniques needed to make the proof work and present
the protocol, from [DKL+ 18], in Figure 9.
Similarly to the way in which we defined the set S ⊂ Zq in the previous section, we
define a set T ⊂ Zq that consists of 2ℓ elements each a distance of approximately q/2ℓ
apart. Instead of outputting the entire vector t ∈ Rnq,f as part of the public key, we will
decompose it as t = t1 + t0 , where t1 = HIGHT (t) and t0 = LOWT (t). The public key
Vadim Lyubashevsky 53

Private information: s1 ∈ [β]m , s2 ∈ [β]n

Public information: A ∈ Rn×m
q,f , t = As1 + s2 (not used by the verifier), t1 = HIGHT (t)

Prover Verifier

y ← [γ + β̄]m
w := HIGHS (Ay)
w-
c←C
c
z := cs1 + y
/ [β̄]m or LOWS (Ay − cs2 ) ∈
if z ∈ / [δS − γ]n
then (z, h) := ⊥
if ct0 ∈/ [δS ]n
then (z, h) := ⊥
if (z, h) ̸= ⊥
then h := HINT(Az − ct1 , ct0 )
(z, h)
-
Accept iff z ∈ [β̄]m
and USEHINT(Az − ct1 , h) = w

Figure 9: The Zero-Knowledge Proof System with a smaller proof and a smaller public key.
The set S ∈ Zq has size 2κ and the function HIGHS , LOWS , and the constant δS ≈ q/2κ+1
are defined as in the text of Section 5.4. The set T has size 2ℓ and we require that
with high probability (over the choice of c and t), c · LOWT (t) ∈ [δS ]n . The functions
HINT and USEHINT are defined as in the text of Section 5.5. The prover, who knows
s1 ∈ [β]m , s2 ∈ [β]n satisfying (73), produces a ZKPoK of s̄1 ∈ [2β̄]m , s̄2 ∈ [q/2κ−1 ]n , and
a c̄ ∈ C¯ satisfying (94). The value γ is defined in Lemma 11, and the value of β̄ affects the
completeness of the protocol (i.e. the probability that ⊥ is not sent) as specified in (90).

will only consist of t1 , which requires ndℓ bits to represent instead of nd log q required to
represent the entire t.
The place where the verifier used t in the protocol in Figure 8 was in the computation
of Az − ct. If the verifier only has t1 , then he can compute Az − ct1 = Az − ct + ct0 . In
order for verification to work out, we would need

HIGHS (Az − ct) = HIGHS (Az − ct1 ),

or in other words,

HIGHS (Az − ct) = HIGHS (Az − ct + ct0 ). (92)

At this point, the natural question is why not resolve this issue by applying the same
technique as in the previous section? That is, we can make sure that ct0 < γ ′ for some
γ ′ and then use the observation in (86) to force the above equation to always hold. The
problem with this approach is that it’s wasteful and unlikely to result in a useful reduction
in size. The reason we upper-bounded the coefficients of cs2 (over all possible secrets s2 )
by γ was that we needed to keep s2 a secret. On the other hand, we do not need to keep
t0 a secret – we simply want it to be unnecessary for verification. So it’s perfectly fine if
the verifier is able to compute something that depends on t0 – i.e. Az − ct + ct0 . Our
54 Basic Lattice Cryptography

only goal here is to make sure that a verifier who knows HIGHS (Az − ct + ct0 ) is able to
derive HIGHS (Az − ct).
The main observation is that if ct0 ∈ [δS ]n , then a verifier who can compute HIGHS (Az−
ct + ct0 ) would only require one bit of extra information (per coefficient) to determine
HIGHS (Az − ct). In particular, if some integer point v is between points si and si+1 in
the set S on the circle representing Zq , and we add to it an integer point v ′ ∈ [δS ], then
the closest point to v + v ′ in S can only be si or si+1 (i.e. HIGHS (v + v ′ ) = si or si+1 ).
The prover, who knows, v and v ′ can provide this one bit of information to the verifier. In
other words, he can tell the verifier whether HIGHS (Az − ct) = HIGHS (Az − ct + ct0 ) or
not. Either way, the verifier can now determine HIGHS (Az − ct). Using this technique,
one can significantly reduce the size of the public key at the cost of adding an extra dn
“hint” bits to the signature.
As notation, we will write HINT(Az − ct1 , ct0 ) = h ∈ {0, 1}dn to be the vector of hints
necessary to recover HIGHS (Az − ct) from Az − ct1 . We’ll write USEHINT(Az − ct1 , h) to
be this recovery procedure. In particular, USEHINT(Az − ct1 , h) computes v = Az − ct1
and then for each integer coefficient of v (which lies between si and si+1 in S), it uses the
corresponding bit of h to either output the closer si (if the hint bit is 0) or the one that is
further away (if the hint bit is 1). In practice, it’ll usually turn out that the majority of
the time the hint bit will be 0, and so the hint vector can be more efficiently represented
by just enumerating the positions where the hint bit is 1.33
With this notation, the algorithm with compressed signatures and public keys is
presented in Figure 9. It will be important for the security proof to note that for any
vector v ∈ Rnq,f and hint vector h ∈ {0, 1}dn , we have

v − USEHINT(v, h) ∈ [q/2κ ]n ≈ [2δS ]n . (93)

The above is directly implied by the USEHINT procedure and the fact that the distance
between two neighboring points in S is q/2κ .
The statement that is proved by the protocol in Figure 9 is the knowledge of s̄1 ∈ [2β̄]m ,
s̄2 ∈ [q/2κ−1 ]n , and c̄ ∈ C¯ satisfying

As̄1 + s̄2 = c̄t1 . (94)

If we would like to relate this to the original t and satisfy (74), we can substitute
t1 = t − t0 and rewrite the above equation as As̄1 + (s̄2 + c̄t0 ) = c̄t and so the length of
the vector s̄2 gets increased by the maximum possible value (over all c̄ ∈ C) ¯ of c̄t0 .

5.5.1 Correctness and Zero-Knowledge

An important point that is worth repeating is that while the verifier does not need the value
of t0 = LOWT (t) for verification, one should not consider the value t0 to be secret because
outputting h leaks some information about t0 . The way to think about t for the proofs is
that the verifier knows the entire t, but only uses t1 in verification. The zero-knowledge
property of the scheme immediately follows from the zero-knowledge property of the scheme
in Figure 8, which we already established in Section 5.4.2, because the only difference in
the prover’s output is the construction of the hint h, which can be done knowing z and t.
The correctness of the scheme follows whenever ct0 ∈ [δS ]n . Note that it doesn’t affect
the security of the scheme if t0 is chosen such that ct0 is sometimes not in [δS ]n – though
this will require additional restarts on the part of the prover.
33 For a slightly more efficient way of computing the hint which reduces the public key size and the

probability of sending ⊥, see [BDL24].

Vadim Lyubashevsky 55

Private information: s1 ← [β]m , s2 ← [β]n

Public information: A ∈ Rn×m
q,f , t = As1 + s2 (not used by the verifier), t1 = HIGHT (t)

Signer Verifier

y ← [γ + β̄]m
c := H(HIGHS (Ay), µ, A, t) ∈ C
z := cs1 + y
/ [β̄]m or LOWS (Ay − cs2 ) ∈
if z ∈ / [δS − γ]n
then RESTART
/ [δS ]n , then RESTART
if ct0 ∈
h := HINT(Az − ct1 , ct0 )
(z, h)
-
Accept iff z ∈ [β̄]m
and H(USEHINT(Az − ct1 , h), µ, A, t) = c

Figure 10: Digital Signature Scheme obtained as a result of applying the Fiat-Shamir
transform to the protocol in Figure 9 that signs a message (digest) µ. Note that as good
cryptographic practice, we put the public key as an input to the hash function H. This
prevents some malleability attacks where seeing a signature for one public key allows one
to create a signature for another, closely-related public key.

5.5.2 Proof of Knowledge

Via rewinding, one obtains the transcripts (w, c, (z, h)) and (w, c′ , (z′ , h′ )), and we thus
have
USEHINT(Az − ct1 , h) = USEHINT(Az′ − c′ t1 , h′ ). (95)
From (93), we know that

Az − ct1 − USEHINT(Az − ct1 , h) ∈ [q/2κ ]n

Az′ − c′ t1 − USEHINT(Az′ − c′ t1 , h) ∈ [q/2κ ]n ,

which together with (95) implies that

A(z − z′ ) − (c − c′ )t1 ∈ [q/2κ−1 ]n ≈ [4δS ]n , (96)

which in turn directly implies knowledge of s̄1 , s̄2 , and c̄ as in (94).

5.6 Digital Signatures

The signing procedure in Figure 10 is the Fiat-Shamir transform of the protocol in Figure 9,
where the secret keys s1 , s2 are chosen uniformly at random from their respective domains.
An important point, which we previously mentioned, is that because the protocol is no
longer interactive, there is never a need for the prover to send ⊥ – he can simply keep
restarting the protocol until the rejection sampling step is successful. This is the reason
that we only needed to prove the zero-knowledge property only in the case that ⊥ is not
output.
The correctness and the simulatability / zero-knowledge properties of the protocol
follow directly from these respective properties of the interactive protocol in Figure 9 and
the Random Oracle heuristic. Via the generic properties of the Fiat-Shamir transform, we
know that one can extract from a successful signer the same thing as from a successful
56 Basic Lattice Cryptography

Table 4: Sample parameters for a digital signature scheme very similar to the NIST Level
3 parameter set (i.e. one that should be as hard as AES-192) CRYSTALS-Dilithium
[DKL+ 18].

q 223 − 213 + 1
f (X) X 256 + 1
β 4
(n, m) (6, 5)
C c ∈ [1] with 49 ±1′ s and 207 0′ s
γ 49 ∗ 4 = 196
β̄ 219 − γ − 1
S {i · (q − 1)/16 | 0 ≤ i ≤ 15}
δS (q − 1)/32 − 1
T {i · 213 | 0 ≤ i ≤ (q − 1)/213 }

prover in Section 5.5.2 – s̄1 , s̄2 , and c̄ satisfying (94). Applying Lemma 9 then implies that
extracting these values is as hard as Ring-LWE or Ring-SIS.

5.7 The Signature Scheme CRYSTALS-Dilithium (ML-DSA)

We now give a sample instantiation for a digital signature scheme very much resembling
[DKL+ 18], which is (conservatively) estimated to have 192 bits of security.
We will be working over the ring Rq,f for f = X 256 + 1 and q = 223 − 213 + 1. This
choice of prime q allows for efficient NTT, since q ≡ 1 (mod 512), as described in Section
4.6. The challenge set C consists of polynomials with 0, ±1 coefficients with exactly 207
0′ s (and thus 49 non-zeros) and the secrets s1 , s2 have coefficients randomly chosen from
[β] for β = 4.
The set S and T are then defined as in Table 4. The definition of set S implies that
every point in Zq is at most (q − 1)/32 + 1 away from any element in S. Similarly, the
definition of T implies that all the coefficients of t0 are in [212 ]. One can now check that
ct0 has coefficients in [δS ] with high probability and so the scheme will be correct (with
high probability). To make the scheme always correct, the prover should additionally
check that ct0 ∈ [δS ]6 , and we set the parameters so that it happens with a very small
probability (< 1%)34 .
The probability that a restart does not occur is computed from (90) as approximately
19
e−196·256·(5/2 +6·32/(q−1))
≈ 0.2,

which means that one needs, on average, about 5 signing attempts before a signature is
produced. This makes the signing procedure noticeably slower than verification. Still,
optimized implementations of the signing procedure runs in well under a millisecond on a
standard personal computer.
The public key consists of a 256-bit seed ρ that is used in the expansion of the public
matrix A and the vector t1 = HIGHT (As1 + s2 ). Since the set S can be described with 10
bits, and there are 6 · 256 integer elements in t1 , the description of t1 requires 6 · 256 · 10
bits. Thus the public key consists of 1952 bytes.
The signature consists of the vector z1 , the challenge c, and the hint vector h. Since
the coefficients of z1 are in [β], its representation requires 20 bits per coefficients for a
total of 256 · 5 · 20 bits. The challenge c consists of approximately 256 bits, while the hint
34 In fact, it never happens for the parameter set given in Table 4 because ∥t ∥ 12 and ∥c∥ = 49,
0 ∞ ≤2 1
and so ∥ct0 ∥∞ ≤ 49 · 212 < δS .
Vadim Lyubashevsky 57

vector h is a binary vector of dimension 256 · 6, and so requires at most that many bits to
represent. Thus the total signature size is around 3424 bytes.

Some Optimizations. We now discuss some small optimizations to the protocol in Figure
10 that are used in the ML-DSA (Dilithium) NIST standard. If the message µ is very long,
then the computation H(HIGHS (Ay), µ, A, t) done after every restart will be needlessly
inefficient. For this reason, it makes sense to first hash the real message µ′ using SHA-512
to obtain a 512-bit digest µ, together with the public key, and only use this digest in the
signing process.
In order to make the sampling of y as efficient as possible (since it also gets sampled
once with every restart), one can make the range in which each coefficient is sampled a
power of 2, so exactly 20 bits. So instead of sampling from [γ + β̄] = [219 − 1], where each
coefficient comes
 from a domain of size 220 − 1, we would instead sample each coefficient
from the set −(2 − 1), . . . , 219 − 1, 219 .
19

Another optimization mentioned above is to send a compact representation of the

hint vector h. With high probability, for the parameters in Table 4, the vector h will
have at most 55 ones, and thus 256 · 6 − 55 zeros. Instead of sending a 256 · 6-bit string,
one can instead specify the positions of the 0’s within the polynomial (which takes 8
bits per non-zero coefficient, so 8 · 55 bits) and also specify the boundaries between the
polynomials, which requires 5 · 6 = 30 bits, for a total of 470 bits instead of the naive
256 · 8 = 1536, which reduces the signature size to about 3290 bytes. This will require the
signer to perform a restart in case the number of non-zero entries in h is greater than 55,
but experimentally, this occurs with a very small probability and does not meaningfully
affect the run-time.

Security. As previously mentioned (see Section 5.5, Lemma 9, and (94)), the security
of the signature scheme relies on the hardness of Rq,f -LWEn,m,β and Rq,f -SISn,m+1,2β̄
problems. The Rq,f -LWEn,m,β assumption is used to prove that the public key (A, t) is
indistinguishable from uniform, and the Rq,f -SISn,m+1,2β̄ assumption is used to show that
an adversary cannot forge a signature and thus find a solution for the Rq,f -SISn,m+1,2β̄
problem in (94) where s̄1 has coefficients in [2β̄] and s̄2 has coefficients in [4δS ] (see (96)),
where both sets are approximately [220 ] for the parameters in Table 4. This therefore
corresponds to the middle row of the parameter set in Table 2 and one can see that
the value of δ, which controls the hardness of the problems, is roughly similar for both
Rq,f -LWEn,m,β and Rq,f -SISn,m+1,2β̄ .
58 Basic Lattice Cryptography

References
[ABD16] Martin R. Albrecht, Shi Bai, and Léo Ducas. A subfield lattice attack on
overstretched NTRU assumptions - cryptanalysis of some FHE and graded
encoding schemes. In CRYPTO (1), volume 9814 of Lecture Notes in Computer
Science, pages 153–178. Springer, 2016.
[ACD+ 18] Martin R. Albrecht, Benjamin R. Curtis, Amit Deo, Alex Davidson, Rachel
Player, Eamonn W. Postlethwaite, Fernando Virdia, and Thomas Wunderer.
Estimate all the {LWE, NTRU} schemes! In SCN, volume 11035 of Lecture
Notes in Computer Science, pages 351–367. Springer, 2018.
[ACPS09] Benny Applebaum, David Cash, Chris Peikert, and Amit Sahai. Fast cryp-
tographic primitives and circular-secure encryption based on hard learning
problems. In CRYPTO, pages 595–618, 2009.
[AD97] Miklós Ajtai and Cynthia Dwork. A public-key cryptosystem with worst-
case/average-case equivalence. In STOC, pages 284–293, 1997.
[ADH+ 19] Martin R. Albrecht, Léo Ducas, Gottfried Herold, Elena Kirshanova, Ea-
monn W. Postlethwaite, and Marc Stevens. The general sieve kernel and new
records in lattice reduction. In EUROCRYPT (2), volume 11477 of Lecture
Notes in Computer Science, pages 717–746. Springer, 2019.
[ADPS16] Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. Post-
quantum key exchange - A new hope. In USENIX Security Symposium, pages
327–343. USENIX Association, 2016.
[ADRS15] Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens-
Davidowitz. Solving the shortest vector problem in 2n time using discrete
gaussian sampling: Extended abstract. In STOC, pages 733–742. ACM, 2015.
[AG11] Sanjeev Arora and Rong Ge. New algorithms for learning in presence of
errors. In ICALP (1), pages 403–415, 2011.
[Age24] National Security Agency. The commercial national security algo-
rithm suite 2.0 and quantum computing faq. Technical report,
2024. [Link]
CSI_CNSA_2.0_FAQ_.PDF.
[AGV09] Adi Akavia, Shafi Goldwasser, and Vinod Vaikuntanathan. Simultaneous
hardcore bits and cryptography against memory attacks. In TCC, volume
5444 of Lecture Notes in Computer Science, pages 474–495. Springer, 2009.
[Ajt96] Miklós Ajtai. Generating hard instances of lattice problems (extended ab-
stract). In STOC, pages 99–108, 1996.
[AKPW13] Joël Alwen, Stephan Krenn, Krzysztof Pietrzak, and Daniel Wichs. Learning
with rounding, revisited - new reduction, properties and applications. In
CRYPTO (1), volume 8042 of Lecture Notes in Computer Science, pages
57–74. Springer, 2013.
[AKS01] Miklós Ajtai, Ravi Kumar, and D. Sivakumar. A sieve algorithm for the
shortest lattice vector problem. In STOC, pages 601–610. ACM, 2001.
[AM18] Divesh Aggarwal and Priyanka Mukhopadhyay. Improved algorithms for
the shortest vector problem and the closest vector problem in the infinity
norm. In ISAAC, volume 123 of LIPIcs, pages 35:1–35:13. Schloss Dagstuhl -
Leibniz-Zentrum fuer Informatik, 2018.
Vadim Lyubashevsky 59

[APS15] Martin R. Albrecht, Rachel Player, and Sam Scott. On the concrete hardness
of learning with errors. J. Math. Cryptol., 9(3):169–203, 2015. https:
//[Link]/malb/lattice-estimator.
[AS18] Divesh Aggarwal and Noah Stephens-Davidowitz. Just take the average!
an embarrassingly simple 2ˆn-time algorithm for SVP (and CVP). In
SOSA@SODA, volume 61 of OASICS, pages 12:1–12:19. Schloss Dagstuhl -
Leibniz-Zentrum fuer Informatik, 2018.
[BCD+ 16] Joppe W. Bos, Craig Costello, Léo Ducas, Ilya Mironov, Michael Naehrig,
Valeria Nikolaenko, Ananth Raghunathan, and Douglas Stebila. Frodo: Take
off the ring! practical, quantum-secure key exchange from LWE. In ACM
Conference on Computer and Communications Security, pages 1006–1018.
ACM, 2016.
[BDK+ 18] Joppe W. Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyuba-
shevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé.
CRYSTALS - kyber: A cca-secure module-lattice-based KEM. In 2018 IEEE
European Symposium on Security and Privacy, EuroS&P, pages 353–367,
2018.
[BDL24] Amit Berman, Ariel Doubchak, and Noam Livne. A note on the hint in
the dilithium digital signature scheme. Cryptology ePrint Archive, Paper
2024/1660, 2024.
[BG14] Shi Bai and Steven D. Galbraith. An improved compression technique for
signatures based on learning with errors. In CT-RSA, pages 28–47, 2014.
[BGM+ 16] Andrej Bogdanov, Siyao Guo, Daniel Masny, Silas Richelson, and Alon Rosen.
On the hardness of learning with rounding over small modulus. In TCC (A1),
volume 9562 of Lecture Notes in Computer Science, pages 209–224. Springer,
2016.
[BP02] Mihir Bellare and Adriana Palacio. GQ and schnorr identification schemes:
Proofs of security against impersonation under active and concurrent attacks.
In CRYPTO, volume 2442 of Lecture Notes in Computer Science, pages
162–177. Springer, 2002.
[BPR12] Abhishek Banerjee, Chris Peikert, and Alon Rosen. Pseudorandom functions
and lattices. In EUROCRYPT, volume 7237 of Lecture Notes in Computer
Science, pages 719–737. Springer, 2012.
[BS16] Jean-François Biasse and Fang Song. Efficient quantum algorithms for com-
puting class groups and solving the principal ideal problem in arbitrary degree
number fields. In SODA, pages 893–902. SIAM, 2016.
[BV11] Zvika Brakerski and Vinod Vaikuntanathan. Fully homomorphic encryption
from ring-lwe and security for key dependent messages. In CRYPTO, pages
505–524, 2011.
[CDPR16] Ronald Cramer, Léo Ducas, Chris Peikert, and Oded Regev. Recovering
short generators of principal ideals in cyclotomic rings. In EUROCRYPT (2),
volume 9666 of Lecture Notes in Computer Science, pages 559–585. Springer,
2016.
[CDW17] Ronald Cramer, Léo Ducas, and Benjamin Wesolowski. Short Stickelberger
class relations and application to ideal-SVP. In EUROCRYPT (1), volume
10210 of Lecture Notes in Computer Science, pages 324–348, 2017.
60 Basic Lattice Cryptography

[CGS14] Peter Campbell, Michael Groves, and Dan Shepherd. Soliloquy: A cau-
tionary tale. Technical report, ETSI 2nd Quantum-Safe Crypto Work-
shop, 2014. [Link]
S07_Systems_and_Attacks/S07_Groves_Annex.pdf.

[CHK+ 21] Chi-Ming Marvin Chung, Vincent Hwang, Matthias J. Kannwischer, Gregor
Seiler, Cheng-Jhih Shih, and Bo-Yin Yang. NTT multiplication for ntt-
unfriendly rings new speed records for saber and NTRU on cortex-m4 and
AVX2. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2021(2):159–188, 2021.

[CJL16] Jung Hee Cheon, Jinhyuck Jeong, and Changmin Lee. An algorithm for
ntru problems and cryptanalysis of the ggh multilinear map without a low-
level encoding of zero. LMS Journal of Computation and Mathematics,
19(A):255–266, 2016.

[DDLL13] Léo Ducas, Alain Durmus, Tancrède Lepoint, and Vadim Lyubashevsky.
Lattice signatures and bimodal gaussians. In CRYPTO (1), pages 40–56,
2013.

[Den02] Alexander W. Dent. A designer’s guide to kems. IACR Cryptology ePrint

Archive, 2002. [Link]

[DFMS19] Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner. Security
of the fiat-shamir transformation in the quantum random-oracle model. In
CRYPTO (2), volume 11693 of Lecture Notes in Computer Science, pages
356–383. Springer, 2019.

[DFPS22] Julien Devevey, Omar Fawzi, Alain Passelègue, and Damien Stehlé. On
rejection sampling in lyubashevsky’s signature scheme. In ASIACRYPT (4),
volume 13794 of Lecture Notes in Computer Science, pages 34–64. Springer,
2022.

[DKL+ 18] Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter
Schwabe, Gregor Seiler, and Damien Stehlé. Crystals-dilithium: A lattice-
based digital signature scheme. IACR Trans. Cryptogr. Hardw. Embed. Syst.,
2018(1):238–268, 2018.

[DLP14] Léo Ducas, Vadim Lyubashevsky, and Thomas Prest. Efficient identity-based
encryption over NTRU lattices. In ASIACRYPT, pages 22–41, 2014.

[DM13] Nico Döttling and Jörn Müller-Quade. Lossy codes and a new variant of
the learning-with-errors problem. In EUROCRYPT, volume 7881 of Lecture
Notes in Computer Science, pages 18–34. Springer, 2013.

[DP16] Léo Ducas and Thomas Prest. Fast fourier orthogonalization. In ISSAC,
pages 191–198, 2016.

[DP23] Léo Ducas and Ludo N. Pulles. Does the dual-sieve attack on learning with
errors even work? In CRYPTO (3), volume 14083 of Lecture Notes in
Computer Science, pages 37–69. Springer, 2023.

[FO99] Eiichiro Fujisaki and Tatsuaki Okamoto. Secure integration of asymmetric

and symmetric encryption schemes. In CRYPTO, pages 537–554, 1999.

[GdKQ+ 24] Phillip Gajland, Bor de Kock, Miguel Quaresma, Giulio Malavolta, and Peter
Schwabe. SWOOSH: efficient lattice-based non-interactive key exchange. In
USENIX Security Symposium. USENIX Association, 2024.
Vadim Lyubashevsky 61

[Gen01] Craig Gentry. Key recovery and message attacks on ntru-composite. In

EUROCRYPT, volume 2045 of Lecture Notes in Computer Science, pages
182–194. Springer, 2001.
[Gen09] Craig Gentry. Fully homomorphic encryption using ideal lattices. In STOC,
pages 169–178, 2009.
[GGH97] Oded Goldreich, Shafi Goldwasser, and Shai Halevi. Public-key cryptosystems
from lattice reduction problems. In CRYPTO, pages 112–131, 1997.
[GKRS22] Siyao Guo, Pritish Kamath, Alon Rosen, and Katerina Sotiraki. Limits on
the efficiency of (ring) lwe-based non-interactive key exchange. J. Cryptol.,
35(1):1, 2022.
[GLP12] Tim Güneysu, Vadim Lyubashevsky, and Thomas Pöppelmann. Practical
lattice-based cryptography: A signature scheme for embedded systems. In
CHES, pages 530–547, 2012.
[GN08] Nicolas Gama and Phong Q. Nguyen. Predicting lattice reduction. In
EUROCRYPT, pages 31–51, 2008.
[GPV08] Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard
lattices and new cryptographic constructions. In STOC, pages 197–206, 2008.
[GS02] Craig Gentry and Michael Szydlo. Cryptanalysis of the revised ntru signature
scheme. In EUROCRYPT, pages 299–320, 2002.
[HHGP+ 03] Jeffrey Hoffstein, Nick Howgrave-Graham, Jill Pipher, Joseph H. Silverman,
and William Whyte. Ntrusign: Digital signatures using the ntru lattice. In
CT-RSA, pages 122–140, 2003.
[HHK17] Dennis Hofheinz, Kathrin Hövelmanns, and Eike Kiltz. A modular analysis
of the fujisaki-okamoto transformation. In TCC, pages 341–371, 2017.
[HPS98] Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. NTRU: A ring-based
public key cryptosystem. In ANTS, pages 267–288, 1998.
[HPS01] Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. NSS: An NTRU
lattice-based signature scheme. In EUROCRYPT, pages 211–228, 2001.
[IN96] Russell Impagliazzo and Moni Naor. Efficient cryptographic schemes provably
as secure as subset sum. J. Cryptology, 9(4):199–216, 1996.
[IZ89] Russell Impagliazzo and David Zuckerman. How to recycle random bits. In
FOCS, pages 248–253. IEEE Computer Society, 1989.
[JMW24] Kelsey A. Jackson, Carl A. Miller, and Daochen Wang. Evaluating the security
of crystals-dilithium in the quantum random oracle model. In EUROCRYPT
(6), volume 14656 of Lecture Notes in Computer Science, pages 418–446.
Springer, 2024.
[KF17] Paul Kirchner and Pierre-Alain Fouque. Revisiting lattice attacks on over-
stretched NTRU parameters. In EUROCRYPT (1), volume 10210 of Lecture
Notes in Computer Science, pages 3–26, 2017.
[KLS18] Eike Kiltz, Vadim Lyubashevsky, and Christian Schaffner. A concrete treat-
ment of fiat-shamir signatures in the quantum random-oracle model. In
EUROCRYPT (3), volume 10822 of Lecture Notes in Computer Science,
pages 552–586. Springer, 2018.
62 Basic Lattice Cryptography

[KW03] Jonathan Katz and Nan Wang. Efficiency improvements for signature schemes
with tight security reductions. In CCS, pages 155–164. ACM, 2003.

[LLL82] Arjen Lenstra, Hendrik Lenstra Jr., and Laszlo Lovasz. Factoring polynomials
with rational coefficients. Mathematische Annalen, (261):513–534, 1982.

[LM06] Vadim Lyubashevsky and Daniele Micciancio. Generalized compact knapsacks

are collision resistant. In ICALP (2), pages 144–155, 2006.

[LM08] Vadim Lyubashevsky and Daniele Micciancio. Asymptotically efficient lattice-

based digital signatures. In TCC, pages 37–54, 2008. Journal version in
[LM18].

[LM18] Vadim Lyubashevsky and Daniele Micciancio. Asymptotically efficient lattice-

based digital signatures. J. Cryptol., 31(3):774–797, 2018.

[LM21] Baiyu Li and Daniele Micciancio. On the security of homomorphic encryption

on approximate numbers. In EUROCRYPT (1), volume 12696 of Lecture
Notes in Computer Science, pages 648–677. Springer, 2021.

[LMPR08] Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, and Alon Rosen.
SWIFFT: A modest proposal for FFT hashing. In FSE, pages 54–72, 2008.

[LP11] Richard Lindner and Chris Peikert. Better key sizes (and attacks) for lwe-
based encryption. In CT-RSA, pages 319–339, 2011.

[LPR10] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and
learning with errors over rings. In EUROCRYPT, pages 1–23, 2010. Journal
version in [LPR13a].

[LPR13a] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and
learning with errors over rings. J. ACM, 60(6):43, 2013. Preliminary version
appeared in [LPR10].

[LPR13b] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. A toolkit for ring-lwe
cryptography. In EUROCRYPT, pages 35–54, 2013.

[LPS10] Vadim Lyubashevsky, Adriana Palacio, and Gil Segev. Public-key crypto-
graphic primitives provably as secure as subset sum. In TCC, pages 382–400,
2010.

[LS15] Adeline Langlois and Damien Stehlé. Worst-case to average-case reductions

for module lattices. Des. Codes Cryptography, 75(3):565–599, 2015.

[LS18] Vadim Lyubashevsky and Gregor Seiler. Short, invertible elements in partially
splitting cyclotomic rings and applications to lattice-based zero-knowledge
proofs. In EUROCRYPT (1), volume 10820 of Lecture Notes in Computer
Science, pages 204–224. Springer, 2018.

[LS19] Vadim Lyubashevsky and Gregor Seiler. NTTRU: truly fast NTRU using
NTT. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2019(3):180–201, 2019.

[Lyu09] Vadim Lyubashevsky. Fiat-Shamir with aborts: Applications to lattice and

factoring-based signatures. In ASIACRYPT, pages 598–616, 2009.

[Lyu12] Vadim Lyubashevsky. Lattice signatures without trapdoors. In EUROCRYPT,

pages 738–755, 2012.
Vadim Lyubashevsky 63

[LZ19] Qipeng Liu and Mark Zhandry. Revisiting post-quantum fiat-shamir. In

CRYPTO (2), volume 11693 of Lecture Notes in Computer Science, pages
326–355. Springer, 2019.

[MG02] Daniele Micciancio and Shafi Goldwasser. Complexity of lattice problems - a

cryptograhic perspective, volume 671 of The Kluwer international series in
engineering and computer science. Springer, 2002.

[Mic02] Daniele Micciancio. Generalized compact knapsacks, cyclic lattices, and

efficient one-way functions from worst-case complexity assumptions. In FOCS,
pages 356–365. IEEE Computer Society, 2002. Journal version in [Mic07].

[Mic07] Daniele Micciancio. Generalized compact knapsacks, cyclic lattices, and

efficient one-way functions. Computational Complexity, 16(4):365–411, 2007.

[Mic19] Daniele Micciancio. Lattices: Algorithms and applications, 2019.

[Link]

[MP12] Daniele Micciancio and Chris Peikert. Trapdoors for lattices: Simpler, tighter,
faster, smaller. In EUROCRYPT, pages 700–718, 2012.

[MP13] Daniele Micciancio and Chris Peikert. Hardness of sis and lwe with small
parameters. In CRYPTO (1), pages 21–39, 2013.

[MR07] Daniele Micciancio and Oded Regev. Worst-case to average-case reductions

based on gaussian measures. SIAM J. Comput., 37(1):267–302, 2007.

[MR09] Daniele Micciancio and Oded Regev. Lattice-based cryptography. In Daniel J.

Bernstein, Johannes Buchmann, and Erik Dahmen, editors, Chapter in Post-
quantum Cryptography, pages 147–191. Springer, 2009.

[Ngu99] Phong Q. Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi cryp-

tosystem from Crypto ’97. In CRYPTO, pages 288–304, 1999.

[NIS17] NIST. Post-quantum cryptography. Technical report, 2017. [Link]

[Link]/projects/post-quantum-cryptography.

[NIS24a] NIST. Module-lattice-based digital signature standard. Technical report,

2024. [Link]

[NIS24b] NIST. Module-lattice-based key-encapsulation mechanism standard. Technical

report, 2024. [Link]

[NR06] Phong Q. Nguyen and Oded Regev. Learning a parallelepiped: Cryptanalysis

of GGH and NTRU signatures. In EUROCRYPT, volume 4004 of Lecture
Notes in Computer Science, pages 271–288. Springer, 2006. Journal version
in [NR09].

[NR09] Phong Q. Nguyen and Oded Regev. Learning a parallelepiped: Cryptanalysis

of GGH and NTRU signatures. J. Cryptology, 22(2):139–160, 2009.

[Oka92] Tatsuaki Okamoto. Provably secure and practical identification schemes and
corresponding signature schemes. In CRYPTO, volume 740 of Lecture Notes
in Computer Science, pages 31–53. Springer, 1992.

[Pei09] Chris Peikert. Public-key cryptosystems from the worst-case shortest vector
problem: extended abstract. In STOC, pages 333–342, 2009.
64 Basic Lattice Cryptography

[Pei10] Chris Peikert. An efficient and parallel gaussian sampler for lattices. In
CRYPTO, pages 80–97, 2010.
[Pei16] Chris Peikert. A decade of lattice cryptography. Foundations and Trends in
Theoretical Computer Science, 10(4):283–424, 2016.
[PFH+ 17] Thomas Prest, Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim
Lyubashevsky, Thomas Pornin, Thomas Ricosset, Gregor Seiler, William
Whyte, , and Zhenfei Zhang. FALCON. Technical report, National Insti-
tute of Standards and Technology, 2017. [Link]
quantum-cryptography/ round-1-submissions.
[PP19] Thomas Pornin and Thomas Prest. More efficient algorithms for the NTRU
key generation using the field norm. In Public Key Cryptography (2), volume
11443 of Lecture Notes in Computer Science, pages 504–533. Springer, 2019.
[PR06] Chris Peikert and Alon Rosen. Efficient collision-resistant hashing from
worst-case assumptions on cyclic lattices. In TCC, pages 145–166, 2006.
[PRS17] Chris Peikert, Oded Regev, and Noah Stephens-Davidowitz. Pseudorandom-
ness of ring-lwe for any ring and modulus. In STOC, pages 461–473. ACM,
2017.
[PVW08] Chris Peikert, Vinod Vaikuntanathan, and Brent Waters. A framework for
efficient and composable oblivious transfer. In CRYPTO, volume 5157 of
Lecture Notes in Computer Science, pages 554–571. Springer, 2008.
[Reg05] Oded Regev. On lattices, learning with errors, random linear codes, and
cryptography. In STOC, pages 84–93. ACM, 2005. Journal version in [Reg09].
[Reg09] Oded Regev. On lattices, learning with errors, random linear codes, and
cryptography. J. ACM, 56(6), 2009.
[Sch89] Claus-Peter Schnorr. Efficient identification and signatures for smart cards.
In CRYPTO, pages 239–252, 1989.
[Sho97] Peter W. Shor. Polynomial-time algorithms for prime factorization and
discrete logarithms on a quantum computer. SIAM J. Comput., 26(5):1484–
1509, 1997.
[Sil01] Joseph Silverman. Wraps, gaps, and lattice constants. Technical report,
NTRU Cryptosystems, 2001. [Link] Earlier
version, 1999.
[SS11] Damien Stehlé and Ron Steinfeld. Making NTRU as secure as worst-case
problems over ideal lattices. In EUROCRYPT, pages 27–47, 2011.
[SSTX09] Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, and Keita Xagawa. Efficient
public key encryption based on ideal lattices. In ASIACRYPT, pages 617–635,
2009.
[SXY18] Tsunekazu Saito, Keita Xagawa, and Takashi Yamakawa. Tightly-secure
key-encapsulation mechanism in the quantum random oracle model. In
EUROCRYPT (3), volume 10822 of Lecture Notes in Computer Science,
pages 520–551. Springer, 2018.
[ZYF+ 20] Jiang Zhang, Yu Yu, Shuqin Fan, Zhenfeng Zhang, and Kang Yang. Tweak-
ing the asymmetry of asymmetric-key cryptography on lattices: Kems and
signatures of smaller sizes. In Public Key Cryptography (2), volume 12111 of
Lecture Notes in Computer Science, pages 37–65. Springer, 2020.