Improved Quantum Cryptanalysis on Lattices

Modern public-key cryptography has been built on the assumption that certain mathematical problems
(RSA and ECC) are hard for classical computers to solve efficiently. Those assumptions are broken by
large-scale fault-tolerant quantum computers that can easily solve them using Shor’s algorithm. This
threat has led to the development of post-quantum cryptographic (PQC) schemes that are supposedly
resistant against quantum adversaries. Among those, lattice-based cryptography has emerged as a
promising candidate, and several lattice-based key encapsulation and signature schemes have already
been standardized by the National Institute of Standards and Technology in the USA (NIST).

Despite their promise, the security of lattice-based schemes against quantum adversaries is not
yet fully understood. The currently best known quantum attacks against lattice-based schemes are
Grover-type quantized versions of existing classical attacks that only offer up to quadratic speed-
up [ANS18, BCSS23]. Several audacious but unfruitful attempts [ES16, Che24] have been made to
achieve exponential speed-up on LWE which is a fundamental lattice-based hardness assumption. In
the process of doing so, new problems such as C-LWE, S-LWE and the Dihedral Coset Problem (DCP)
were introduced in order to find novel attack angles against LWE.

In addition to its post-quantum feature, lattice-based cryptography allows to construct many ad-
vanced cryptography primitives such as polynomial commitment, functional commitment, blind signa-
tures, anonymous credentials and SNARKS (succinct non-interactive arguments of knowledge). They
can be built from standard lattice assumptions (algebraic versions of LWE and SIS). However, in order
to make these constructions more efficient, people came up with new hardness assumptions that are re-
lated to previous well-studied ones but with extra hints. These hints may lead to potential weaknesses
that do not exist in the original assumptions, and they have not been well studied.

The goal of this thesis is to improve the understanding of quantum security of lattice-based crypto-
graphic schemes.

1) C-LWE, S-LWE and links with DCP: An intriguing possibility of quantum computing is the
possibility to obtain a superposition of all possible LWE samples: such states are known as C|LWE⟩ and
S|LWE⟩ [CLZ22, TLL+25]. If one is able to construct such states with suitable amplitutes efficiently,
certain PQC assumptions used in SNARKS have been shown to be vulnerable [DAFS24]. Furthermore,
there are links between the problem of constructing those states and the Dihedral Coset Problem (DCP)
[BJK+25] which is related to the LWE problem. [BJK+25] futher provided a polynomial quantum
algorithm for the DCP in a special case where the moduli is a power of 2. Starting from these papers,
our goal will be to provide new quantum algorithms for lattice-based assumptions.

2) LWE with hints With: more advanced constructions relying on many new variants of LWE with
hints, it is necessary to better understand the security of those assumptions. Our goal is to system-
atically study those assumptioms, starting with one particular assumption (the PRSIS assumption
[FMN24]) that seems structured and problematic, and establish the relationship between them (i.e.,
reductions between them) in both classical and quantum settings.

3) Improved quantum algorithms on structured lattices: Virtually all PQC schemes operate on structured lattices for efficiency reasons. Despite this fact, very few quantum algorithms have been developed that specifically target such lattices. For example, one of them shows how to solve SVP with a subexponential approximation factor in specific lattices [CDPR16]. Our goal will be to develop new quantum algorithms specifically for structured lattices, using [CDPR16] as a starting point.