Johanna Loyer Master

André Chailloux

Quantum cryptanalysis on euclidean lattices

i Je tiens aussi à remercier les professeurs du Master Cryptis de l'Université de Limoges, qui m'ont fourni les connaissances et les méthodes, ainsi que le fait de pousser à la curiosité, qui ont été nécessaires à la réussite de mes études.

Merci à ma famille d'avoir transformé ce confinement en une période agréable mais productive. Et merci à ma famille de coeur pour leur présence quoi qu'il arrive.

Je remercie tous mes amis de la promo Math Cryptis qui ont fait de ces deux ans les deux meilleures années de ma vie, aussi bien intellectuellement que relationnellement. Cela va me manquer ces rendez-vous jeux de société, ces soirées à la colloc et ces week-ends de révisions/projets sur fond de musiques des années 2000.

Je remercie Jérôme d'avoir supporté que je lui parle d'hypercones et de quantique à longueur de journée. Remarque, il me l'a bien rendu avec son passage à l'échelle des VE et autres calculs d'efficacité de recharge par bornes.

Je souhaite enfin remercier M. Biondi, ancien professeur de SI, qui m'a encouragée à ne pas baisser les bras en prépa et à continuer à croire en mes rêves de travailler dans la recherche. (Certes, avec des mots bien à lui.) C'est chose faite, et c'est en partie grâce à son discours.

iii

Notations

The following notations are used in this paper.

• If not precised, v i stands for the i-th coordinate of the vector v.

• We will several times amalgamate the sets Z 2 n ≈ {0, 1} n .

• We denote |0 = 1 0 and |1 = 0 1 .

• We will several times amalgamate the notions of vectors in R d and points in R d .

• We use O(n) := O(polylog(n)) = O(log(n) k ) for some k, with O the Landau notation.

• For a vector v, we call the associated normalized vector: v/ v .

Introduction

With the possible emergence of quantum computers in the near future, developing cryptography that is resistant to it is one of the challenges that will have to be addressed. In 2015 the National Institute of Standards and Technology (NIST) launched an international competition in the purpose of standardizing quantum resistant protocols of encryption, signature and key exchange. The security of the candidate cryptosystems are based on problems on error decoding codes, multivariate, hashing functions, and lattices. Several finalists [DKL + 19, CDH + 19, FHK + 19] announced on the 23th July 2020 are lattice-based protocols. Therefore it is necessary to deeply study their problems to verify if their difficulty is sufficient against both classical and quantum computers.

From March to July 2020, I did my final internship under the supervision of André Chailloux, researcher in quantum cryptography. It took place at the Inria, a public research institute in computer science and applied mathematics. The project-team I worked with was COSMIQ (ex-SECRET), the acronym standing for COde-based, SyMmetric cryptology, and Quantum Information. Their research work concerns the design and analysis of cryptographic algorithms, classically and quantumly. It mixes fundamental and practical aspects of information protection: cryptanalysis, design of algorithms and implementation.

My internship mostly consisted in acquiring a solid basis of knowledge in quantum computing. The purpose was to start my doctorate with an already constituted bibliography in solving-SVP sieving algorithms, and be able to apply to them quantum speed-ups. Towards the end of my internship, I started to follow a lead to improve the complexity of an algorithm solving the shortest-vector problem on lattices. It has not yet succeeded, so I will pursue this idea during my Ph.D. This report will present the knowledge I have acquired during these five months. The first part is about Quantum Computing. I will expose the fundamental principles, the quantum model, an attack on actual main cryptosystems (RSA, ECC, Diffie-Hellman), and finally present the most important algorithm for us : Grover's algorithm. In the second part, Sieve Attack Algorithms on Lattices, I will present some cryptographic problems, and algorithms which solve one of them in particular (SVP) by the sieve method, and then present several improvement of its complexities.

Quantum Computing

Classical computing consists in storing and processing information coded in form of states of electronic components. In the same way, we speak about quantum computing when data are coded by states of quantum particles. In this case, classical physics no longer stands and the quantum physics theory takes over. That allows us to exploit the particular properties of these particles to do things that were proven impossible for a classical algorithm.

Fundamental principles

We are going to begin with a comparison with classical physics to understand the important differences between the two physics models. In classical computing, a bit have the value 0 or 1, but only one of these two states at the same time. It can change from one to another, but its state is always unique at an instant t. For quantum particles, the elementary piece of information is called qubit and its state can be a superposition of 0 and 1 at the same time. When we perform a measurement of the particle, there are probabilities of finding the states 0 or 1, but is it impossible to predict in advance which result we will find. Once it is measured, the particle loses its quantum behavior and stays in the state we have measured.

However, probabilities alone are not sufficient to completely explain some physical behaviors of a quantum particle, for example the interference effect. Thus, we use amplitudes to characterize its state. Physically this notion is related to the wave function of the particle, and it is translated by a probability when we measure. For a qubit at a state denoted |ψ , we can fully describe this state by its amplitudes α, β ∈ C:

|ψ = α|0 + β|1 = α β
Here, the value |α| 2 (resp. |β| 2 ) is the probability of finding 0 (resp. 1) when we perform a measurement. For this, we must have |α| 2 + |β| 2 = 1.

If we manipulate n qubits, we can rename for simplicity the states |0 , |1 , ...|2 n -1 instead of |0...00 , |0...01 , ..., |1...11 , these last ones are the binary writing of the first. A register of n qubits can be in any superposition in this form:

α 0 |0 + α 1 |1 + • • • + α 2 n -1 |2 n -1 with 2 n -1 j=0 |α j | 2 = 1.
Another important property of quantum particle is the entanglement. When two particles are said entangled, it means that if we measure one of them, the state of the other acts as if we also measured it. That implies that we can act on one particle and cause immediate consequence on the other.

For example, let's consider the 2-qubit register 1

√ 2 |00 + 1 √ 2 |11
. If we perform a measurement of any of the two qubits, we obtain with the same probability 0 or 1. But if we then measure the second, one will necessarily get the same result as the first one.

With that basic knowledge about quantum physics, it is sufficient to understand and create quantum algorithms. It is not uncommon for researchers to work on quantum computing without knowing much more about all the subtleties of quantum mechanics.

Quantum circuit model

A quantum circuit generalizes the idea of classical circuits. The AND, OR and NOT gates are replaced by elementary quantum gates. A model well defined allows us to know which tools we can use to then construct more complex algorithms.

Measurement

First we are going to formalize the measurement operation for amplitudes in R. For a qubit at state |ψ , we can measure it by taking an orthogonal unitary basis (|x , |y ). Denote θ the angle between |x and |ψ seen as vectors. The probability of having as result |x by performing a measurement of |ψ is cos 2 (θ), and for a result |y is sin 2 (θ). In particular, we set the Hadamard basis (figure above) with

|+ = 1 √ 2 (|0 + |1 ) and |-= 1 √ 2 (|0 -|1
), which will have several applications further.

When we do not precise an other basis for performing a measurement, it will be by default (|0 , |1 ).

Quantum gates

As qubits have a vector form, we can apply to them functions represented in form of unitary matrices. Note that for one qubit (a vector of 2 complex elements), the dimension of a matrix is 2 × 2.

Definition 2.1 (Pauli matrices).

I = 1 0 0 1 Identity matrix X = 0 1 1 0 Bitflip: exchanges the amplitudes of |0 and |1 (equivalent to NOT gate) Y = 0 -i i 0 Z = 1 0 0 -1 Phaseflip: changes the sign before |1
From these 2 × 2 single-qubit matrices, we want to construct matrices which act on several qubits. To do this operation, we first need to define the Kronecker product, i.e. the tensor product of matrices. Definition 2.2 (Kronecker product). If A an m×n matrix and B a p×q matrix, then the Kronecker product A ⊗ B is the pm × qn matrix: For U a matrix and n ∈ N, we will denote

A ⊗ B =    a 11 B • • • a 1n B . . . . . . a m1 B • • • a mn B   
U ⊗n = U ⊗ • • • ⊗ U n .
The n-qubits Pauli matrices are obtained by the tensor product of n of the 2 × 2 Pauli matrices. Since we have 4 possibilities for each of the n tensor factors, we count 4 n n-qubits Pauli matrices of dimension 2 n × 2 n . Theorem 2.3. [dW19] Every complex 2×2 matrix A can be written as a linear combination of Pauli matrices:

A = λ 0 I + λ 1 X + λ 2 Y + λ 3 Z,
where λ i ∈ C. Every 2 n × 2 n matrix A can be written uniquely as a linear combination of the 4 n n-qubits Pauli matrices of dimension 2 n × 2 n .

We now define other matrices convenient to use. This conducts to:

R θ |0 = |0 , R θ |1 = e iθ |1 . H = 1 √ 2 1 1 1 -1 Hadamard transform
If we apply H to a state |0 and then measure, we have equal probability of observing |0 or |1 . Idem for |1 . However, if we apply H to 1

√ 2 |0 + 1 √ 2 |1
, we obtain |0 . Mathematically, it can be easily be verified by calculus (H = H -1 ), and physically it is due to the interference effect.

CN OT =     1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0     Controlled NOT
If the first qubit (control) values 1, the second (target) is opposed. The sub-matrix X = 0 1 1 0 (N OT operation) can be generalised by any 2 × 2 unitary matrix.

Theorem 2.4. [dW19] With H, CN OT and T = R π/4 , we can construct an approximation of any possible quantum circuit.

Example We can construct a circuit to turn two input qubits into an entangled state with only two gates: H and CN OT .

Queries to oracles

Definition 2.5. Let |x = |x 0 , ..., x n-1 be a register of n qubits. For i ∈ [0, n -1] and b ∈ {0, 1}, we call a query oracle:

O x : |i, b → |i, b ⊕ x i
In simpler terms, we dispose in one hand the register |x containing data. In the other we have two qubits. We set the first at the value i for which we are interested to know x i , and the other bit b we will write onto. After applying O x seen as a black-box, the second qubit is now at the state x i .

In particular, for |b = |-from the Hadamard basis, we have

O x : |i, -→ (-1) xi |i, -.
For a function f that we suppose we know how to compute, we can generalize to any oracle:

O f : |a |0 n → |a |f (a)
Note that O f entangles the two qubits. Indeed, if we measured the second and obtain the state |f (a) and by measuring the first then we get |a , and reciprocally.

Quantum Fourier Transform

Definition 2.6 (Quantum Fourier Transform -QFT). Let be N = 2 n and |k a register of n qubits. We define the quantum Fourier transform:

F N |k = 1 √ N N -1 j=0 (e 2iπ/N ) jk |j
In its matrix form, denoting ω := e 2iπ/N :

F N = 1 √ N        1 1 • • • 1 1 ω • • • ω N -1 1 ω 2 • • • ω 2(N -1) . . . . . . . . . 1 ω N -1 • • • ω (N -1)(N -1)       
Note that F 2 = H. And we also note that

F N |0 n = H ⊗n |0 n .
Theorem 2.7. [START_REF] Shor | Algorithms for quantum computation: Discrete logarithm and factoring[END_REF] The QFT is feasible in O(n • log(n)) gates H and controlled-R 2π/2 m for 1 m n.

Elementary bricks to construct algorithms

According to the quantum circuit model, we have these tools at our disposal:

• any normalized linear combination or tensor product of I, X, Y, Z and H, R θ , CN OT ,

• query oracles for obtaining information about a qubit in a register,

• the Quantum Fourier Transform to put the register in a superposed state,

• measurements.

For computing the complexity of an algorithm, depending on the case we can count the number of gates we need or focus on the number of queries to an oracle.

Attack on RSA, ECC and Diffie-Hellman

Shor's Algorithm

This algorithm is not directly in the domain of research I will work in, but it is a historically important one. Published in 1994, Shor's algorithm [START_REF] Shor | Algorithms for quantum computation: Discrete logarithm and factoring[END_REF] can factor a number N in a polynomial time: O(log(N ) 2 ), and therefore breaks the RSA cryptosystem. For comparison, the actual best classical factoring algorithm is about O(2

√ log(N ) ).
Definition 2.8 (Period finding problem). Let be a function f

: N → {0, ..., N -1} with r ∈ {0, ..., N -1} such that f (a) = f (b) mod r ⇔ a = b mod r. Find r the period of f .
Theorem 2.9. The factorisation problem Fact is reduced to the period finding problem.

Proof. Let be N an non prime odd integer and x ∈ {2, ..., N -1} chosen randomly. If gcd(x, N ) > 1, the proof is done: we have found a non trivial factor of N . Else, x and N are co-primes, that we will suppose from now. Let be the sequence (in Z * N ) : 1, x, x 2 , ... This sequence admit a period r ∈ [|0, N -1|], such that x r = 1. r can also be called the order of the element x.

With a probability greater than 1/2, r is even and neither (x r/2 + 1) nor (x r/2 -1) are multiples of N . Else, we change of x until it is the case. We have:

x r ≡ 1 mod N ⇒ x r/2 -1 ≡ 0 mod N ⇒ (x r/2 + 1)(x r/2 -1) ≡ 0 mod N ⇒ (x r/2 + 1)(x r/2 -1) = kN for k > 0
In short, (x r/2 + 1) and (x r/2 -1) have good chances to have a non-trivial common factor with N . If it does not work, we change x again until we find. Thus, if we know how to find a period in an efficient way, we also know how to factorize in an efficient way.

Main idea. The algorithm put a first register in an uniform state over all its qubits by applying a QFT. Then it queries to an oracle to get in the second register the images by the function for which we are looking for its period. Each image is entangled with its antecedent. By applying the QFT on the first register again and then perform a measurement of the first register, we get a value that allow to recover the period.

Let q = 2 . Again, for simplicity we will confuse the sets {0, ..., q -1} and {0, 1} , the elements of the second set are seen as the binary writing of an element of the first. We dispose of two gates to construct the associated quantum circuit:

• the Quantum Fourier transform F q : |a → 1 √ q q-1 b=0 (e 2iπ/q ) ab |b • and a black-box O f : |a |0 n → |a |f (a) .

Algorithm 1 Shor

Require: two registers: |0 |0 n . Ensure: the period r of f 1. Apply F q to the first register.

We get an uniform superposition :

1 √ q q-1 a=0 |a |0 n 2.
Apply O f on all the qubits. We get the state :

1 √ q q-1 a=0 |a |f (a)
. Note that all the qubits of the first register are now entangled with the second (i.e. measuring the value of ones can force the state of the others).

3. Measure the qubits of the second register.

The value of f (s) is obtained for a s to be determined. Let m be the number of a's such that f (a) = f (s), that is to say a = s mod r. We can write a = jr+s with 0 j m. After this measurement, so we get the state:

1 √ m m-1 j=0 |jr + s |f (s) .
We can ignore the second register from there, because it is frozen in the state |f (s) . 4. Apply again F q to the first register.

We get (it is sufficient to write the calculations):

1 √ qm q-1 b=0 e 2iπ sb q m-1 j=0 e 2iπ jrb q |b
5. Measure the first register giving |b .

Recover r from b

See the reasoning below.

We denote the result of the measure: |b , from which we will find r. What are the |b that have the highest probability of being measured? There are two cases to consider: Simple case. r | q Thus 0 r < q and m = q/r. We have e 2iπrb/q = 1 iff rb/q ∈ N iff b is a multiple of q/r. The amplitude (i.e. the coefficient before a state in the sum above) of a such b so is:

1 √ qm e 2iπ sb q m-1 j=0 e 2iπ jrb q = 1 √ qm 1 • m-1 j=0 1 = m √ qm = m q
By squaring its module, we get the probability that the result of the measurement is the state |b , which is m/q = 1/r. As we know that the register is in an uniform state (each |b has the same probability to be measured), we deduce that the number of such b is r. By measuring the first register, so we find randomly one of these b multiples of q/r. We denote b = cq/r with 0 c < r. So we have:

b/q = c/r
We know b (measured) and q (in the problem statement). If c and r are co-primes, we find them easily by simplifying the fraction b/q to make it irreducible, and the proof is over.

If they have a common factor, we restart the algorithm until finding c co-prime with r. According to a theorem ([HW79] theorem 328), there are O r log(log(r)) numbers smaller than r which are co-primes with r, hence the probability of finding such a c which is in O 1 log(log(r)) . And thus we start again the algorithm O(log(log(N ))) times before finding the wanted result.

Difficult case. r q

It is the case that happens most often because q = 2 . We will not detail here. In summary, if q is chosen sufficiently high, the gap between b/q and c/r is low ( 1/2q). With calculations of continuous fractions, we can find c and r.

Hidden Subgroup Problem

As we will see soon, the Hidden Subgroup Problem (HSP) is a generalization of the period-finding problem. Even if classical HSP-solving algorithms run in exponential complexities, quantum ones are very efficient.

Definition 2.10 (Coset). Let G be a group and H G. The cosets are the gH for a g ∈ G.

Definition 2.11 (Hidden Subgroup Problem -HSP). Let be G a group, a finite set S, and a function f : G → S. Find H G such that:

1. f constant in each coset gH, and 2. f distinct on two different cosets :

f (g) = f (g ) ⇔ gH = g H.
Remark 2.12. The period finding and discrete logarithm problems are HSP instances.

Indeed, for the period finding problem, we consider G = Z φ(N ) (with φ(N ) the Euler's phi function) and H = r . For f a function of period r, f is constant on r + H and distinct on different cosets. Thus finding H = r leads to know r.

For the discrete logarithm, given γ a generator of a set S (N = |S|) and A ∈ S, the problem is to find the unique a ∈ N such that γ a = A. We consider G = Z N × Z N and H = (a, 1) . We have f : G → S with f (x, y)γ x A -y that we can show it is constant on H and distinct on different cosets. Finding H = (a, 1) leads to know a. Therefore, constructing an algorithm which solves efficiently HSP breaks RSA, ECC and Diffie-Hellman.

Grover's Algorithm

Definition 2.13 (Grover's search problem). For N = 2 n , we are given an arbitrary x = (x 1 , ..., x N ) ∈ {0, 1} N . The goal is to find an i such that x i = 1, and to output "no solution" if there are no such i. We assume that we know the number t of such i, or at least an approximation of t.

This problem has first been presented as a search in a un-ordered database. In the original article [Gro96], Grover fixed t = 1, which is generalized here. Classically, it is not possible to get a better complexity than Θ(N ) queries, by examining each x i one by one until we find one which values 1. Grover's algorithm solves the search problem in O( √ N ) queries, and with O( √ N log(N )) other gates.

Main idea. The algorithm separates "good" (x i = 1) and "bad" (x i = 0) indices i and increases step by step the amplitudes of the "good" state. The action of the algorithm can be understood thanks to geometric arguments which we will present.

First, we set:

θ := Arcsin t N = Arccos( N -t N |G := 1 √ t i:xi=1 |i and |B := 1 √ N -t i:xi=0 |i |U := 1 √ N N -1 i=0 |i = N -t t |B + t N |G
|U is the uniform state over all indices. |G and |B stand respectively for the "good" and "bad" states, following the values of the x i 's. We consider the 2-dimensional space induced by |G and |B . It will be the basis in which we will take measurements. The normalization coefficients allows to represent this on a circle of radius 1.

Geometrically, we see that θ represents the angle between the states |B and |U . Indeed, t N is the probability of finding a good solution at the beginning of the algorithm, i.e. getting |G by a measurement. So t/N is the amplitude of |G at the beginning. After a measure, we have the relation Pr(|G ) = sin(θ), so the associate angle has indeed the expression θ = Arcsin( t/N ). So, by a basic rule of trigonometry, we can write the following relation:

cos(θ)|B + sin(θ)|G = |U = 1 √ N N -1 i=0 |i
To run the algorithm, we have these gates at our disposal:

• H the Hadamard gate, with H ⊗n that acts like F N over |0 n ,

• the query oracle O x,± |i = (-1) xi |i , Then,

• R|i = -|i if |i = |0 n |0 n else. ,
H ⊗n RH ⊗n = H ⊗n 2|0 n 0 n | -I H ⊗n = 2|U U | -I which is a reflection through |U . A Grover step is G = H ⊗n RH ⊗n O x,± .
The algorithm starts with |U and at each iteration of the loop, we move forward of the angle 2θ. We note that each application of G performs only one query to the oracle O x,± .

Algorithm 3 Grover

Require: a register |0 N , the number of solutions t (or its approximation) Ensure: an index i such that x i = 1, or "no solution"

Apply H ⊗n on the entire register.

We get

H ⊗n |0 n = |U for k π 4θ -1 2 iterations do Apply O x,± Reflection through |B Apply H ⊗n RH ⊗n
Reflection through |U Measure the first register and verify if the resulting i is a solution. If we choose k too low or even too high, we see that the probability is not optimal. To maximize this probability, we want (2k + 1)θ = π 2 , so we set k

π 4θ -1 2 .
Here is a generalization of Grover's algorithm described in [vM10].

Definition 2.15 (Amplitude amplification). Given a function f : Z n → {0, 1}, we want to solve f (z) = 1 with a probability of error < 1/2.

We dispose of:

• H the Hadamard gate,

• O f |z = (-1) f (z) |z ,
• A an algorithm which has a probability p of finding a solution.

The principle of Grover's algorithm is repeated, by taking θ = Arcsin( √ p) and |U = A|0 .

Algorithm 4 Amplitude amplification

Require: a register |0 N , the probability p of success of A.

Ensure: z such that f (z) = 1, or "no solution" Apply H ⊗n on the entire register we get

H ⊗n |0 n = |U for O(1/ √ p) iterations do Apply O f Reflection through |B Apply ARA -1
Reflection through |U Measure the first register If the resulting z is a solution, return z. Else, return "no solution". This algorithm has a complexity in O(1/ √ p) queries of f .

For Grover for example, we have taken O f = O x,± , A = H ⊗n , and p = t/N .

Sieve Attack Algorithms on Lattices

In this part, we will present algorithms that attack lattice-based cryptosystems by solving the cryptographic problem of the shortest-vector (SVP). Currently, the two main practical methods to solve SVP are enumeration and sieving according to the recent records for the lattice-challenge [START_REF] Schneider | Lattice challenge[END_REF].

For a dimension d, enumeration has a low space complexity, but a time complexity super-exponential in the dimension d. Sieving runs with a space complexity of 2 θ(d) and in single exponential time 2 θ(d) but the hidden constants in the exponents are relatively big. We will only focus on sieving algorithms here.

Lattice-based cryptographic problems

In this part, we will introduce some definitions about lattices and several cryptographic problems based on them.

Definition 3.1 (Lattice). The lattice L ⊂ R m generated by a basis B = (b 1 , ..., b n ) of linearly independants b i ∈ R m is: L = n i=1 i b i , i ∈ Z L is said full rank iff n = m.
By default, we will consider the lattices full rank in the following. Definition 3.2 (Successive minima λ i ). Let Ball(r, n) be the ball of dimension n and radius r. For 1 i m,

λ i (L) := inf r > 0 | dim L ∩ Ball(r, n) i
So we have λ 1 (L) λ 2 (L) ... λ m (L), and in particular λ 1 = inf y∈L\{0} y which is the length of the shortest vector of L.

Any secure cryptosystem has to rely on NP-hard problems. We will here define several lattice-based cryptographic problems, and then show why the first one, SVP, interest us particularly.

Definition 3.3 (SVP). Find some v ∈ L such that v = λ 1 (L).
α-SVP (approximate SVP): find some non-zero v ∈ L such that v αλ 1 (L).

Definition 3.4 (CVP). Given a target vector t ∈ Span(B). Find some v ∈ L such that vt is minimized, i.e. vt = d(L, t) = min u∈L d(u, t). α-CVP (Relative): find some v ∈ L such that vt α.d(L, t) (when α increases, the hardness decreases.) r-AbsCVP (Absolute): find some v ∈ L such that vt r Definition 3.5 (BDD -Bounded Distance Decoding). Given t ∈ Span(B). Let r λ 1 (L)/2 and α 1/2. α-BDD (relative): promised d(L, t) αλ 1 . Find v ∈ L (unique) such that vt α.λ 1 . r-AbsBDD (absolute): promised d(L, t) r. Find v ∈ L (unique) such that vt r.

The previous problem can be seen as a decoding problem. That illustrates the strong link between lattice-based and code-based cryptography.

Definition 3.6 (Subset Sum Problem). Given a set of integers, find a non-empty subset whose sum is zero. Definition 3.7 (SIS -Short Integer Solution). Given a matrix A ∈ Z n×m q , find a non-zero vector v ∈ Z m such that Av = 0 and v β.

Definition 3.8 (LWE). Given some couples (a i , a i .s + e i ) with a i ∈ Z n q and a small error e i ∈ Z, find the vector s ∈ Z n q .

Among the NIST competition finalists, Dilithium [DKL + 19] is based on modular variants of SIS and LWE, namely: MSIS, SelfTargetSIS and MLWE. The two other lattice-based finalists, Falcon [FHK + 19] and NTRU [CDH + 19], are based on the NTRU problem [START_REF] Hoffstein | NTRU: a ring-based public key cryptosystem[END_REF]. All these problems are proven reduced to the Shortest Vector Problem. Their hardness depends on SVP, so that is why we mainly focus on this problem in particular.

Sieving algorithms

The Nguyen-Vidick Sieve

Main idea. The NV-sieve [START_REF] Nguyen | Sieve algorithms for the shortest vector problem are practical[END_REF] starts with a list L of long lattice vectors and iteratively builds lists of shorter lattice vectors L by applying a sieve to L. After poly(d) applications of the sieve, we hope to get a list containing a non-zero shortest lattice vector.

The input L can be obtained by Klein's algorithm [START_REF] Klein | Finding the closest lattice vector when it's unusually close[END_REF]. It samples vectors from a discrete Gaussian over the lattice with a large variance, i.e. a relatively high probability of sampling long vectors. It is important to notice that for all the algorithms we will present, there are no proven complexities but only results based on heuristics. It is thus primordial to choose well the heuristic we use and experimentally check them.

Setting of N the number of vectors

We follow the reasoning of [START_REF] Nguyen | Sieve algorithms for the shortest vector problem are practical[END_REF], using the heuristic Assumption 3.9 in the case γ → 1. We want to know how many vectors in L we need at average to cover the d-dimensional ball of center 0 d and radius 1 (normalized for any radius R). We take a list vector of length R, represented by a point on this sphere and Complexity. The time complexity is dominated by comparing almost every pair of vectors in L in each sieving step. This leads to a time complexity in O(n 2 ) for each sieve step, which is applied poly(d) times. Therefore the NV-sieve heuristically solves SVP in time O(n 2 ) ≈ 2 0.415d+o (d) and in space O(n) ≈ 2 0.208d+o(d) .

The GaussSieve

Main idea. The GaussSieve [START_REF] Micciancio | Faster exponential time algorithms for the shortest vector problem[END_REF] starts with a short list of vectors, and iteratively builds a longer and longer list of lattice vectors, occasionally reducing the lengths of list vectors in the process, until at some point this list L contains a shortest vector.

Reduce v with w : if v ± w < v then v := v ± w.

Algorithm 6 GaussSieve

Require: a lattice L Ensure: a list L containing a shortest vector L := empty list S := empty stack while v is not a shortest vector do get a vector v from the stack S (or sample new one) for each w ∈ L do reduce v with w reduce w with v if w has changed then remove w from the list L add w to the stack S (unless w = 0) if v has changed then add v to the stack S (unless v = 0) else add v to the list L return L Complexity. According to [START_REF] Micciancio | Faster exponential time algorithms for the shortest vector problem[END_REF], there is no known upper bound of the time complexity, but the experiments showed a time complexity in time 2 0.415d+o(d) and space 2 0.208d+o (d) .

The GaussSieve seems to be more efficient than the NV-sieve in practice.

Leveled sieving

The 1-level sieve

A lattice L of dimension d such that L ⊆ L is called an overlattice of L.
The main idea of this other algorithm is to use a tower of k overlattices L i , where L = L 0 ⊆ ... ⊆ L k . In this tower, the lattice L k is chosen at the bottom of the tower in a way that ensures that we can efficiently compute a sufficiently large set of short vectors in L k . Starting from this set of short vectors, we move from each lattice of a tower to the one above using summation of vectors while controlling the growth of norms.

Locality-sensitive hashing (LSH)

Main idea. We use locality-sensitive hash functions, which have more probability to have equal output hashes when the inputs are close vectors. Instead of reading all the list vectors to reduce a vector v, we now partition the space and only consider those who have the same hash as v, i.e. their difference has a high probability to have a lower length.

Note that these hash functions have completely the opposite properties that we are usually looking for when we use hash functions. Figure 3.2: In this example, each of the t hash functions separates the space in four areas of different hashes. We compute the hash value of the target v through the hash function and then we look in their associated hash tables to see which vectors have the same hash. Those are candidates to be the closest point of v: w 6 , w 7 , w 8 , w 9 and w 10 . (Illustration from [START_REF] Laarhoven | Search problems in cryptography, From fingerprinting to lattice sieving[END_REF])

Definition 3.11. A family H = {h : R d → U ⊆ N} is called (r 1 , r 2 , p 1 , p 2 )-sensitive for a similarity measure D if for any v, w ∈ R d , • if D(v, w) < r 1 , then Pr h∈H [h(v) = h(w)] p 1 and • if D(v, w) > r 2 , then Pr h∈H [h(v) = h(w)] p 2 . Ideally, r 1 ≈ r 2 and p 1 ≈ 1 p 2 ≈ 0. We can choose D(v, w) := θ(v, w) = Arccos v T w v • w .
Definition 3.12 (Combined hash function). For j ∈ [|1, t|], we will denote the combined hash function h j := (h 1,j , ..., h k,j ). That means that two vectors have the same hash through h j if and only if they have the same hash through h i,j for all i.

Lemma 3.14. Suppose there exists a (r 1 , r 2 , p 1 , p 2 )-sensitive hash family H. Let :

ρ = log p 1 log p 2 , k = log n log(1/p 2 ) , t = O(n ρ )
Then, assuming the heuristic 3.13, for any v ∈ R d , with high probability we can find an element w * ∈ L with D(v, w * ) r 1 or correctly conclude that no element w * ∈ L with D(v, w * ) r 2 exists, with the following costs :

1. Time for preprocessing the list: O(n 1+ρ log 1/p 2 (n) ) 2. Space complexity of the preprocessed data: n vectors in t = O(n ρ ) hash tables: O(n 1+ρ )

Time for answering a query v: O(n ρ )

Hash evaluations of the query vector v: t = O(n ρ ) Candidates to compare to the query vector v: O(n ρ )

Since we need to perform these searches O(n) times, and we need to repeat the whole sieving procedure poly(d) times, the time complexity is in the order O(n 1+ρ ).

Proof. We have t combined hash functions h j = (h 1,j , ..., h t,j ).

If

D(v, w) r 1 , Pr[h j (v) = h j (w)] p k 1 = 1
t , because we want to have on average at least one vector w which collide with v.

And if

D(v, w) r 1 , Pr[h j (v) = h j (w)] p k 2 = 1
n , because we want that it happens only on average at most one time on n vectors. We obtain :

k. log(p 2 ) = -log(n) so k = - log(n) log(p 2 ) = log(n) log(1/p 2 ) and 1/t = p k 1 = p - log(n) log(p 2 ) 1 so t = n log(p1)/ log(p2) := n ρ
The goal is thus to design the LSH family H so that ρ = log(p1) log(p2) is as small as possible. In practice, the calculated complexity is below the true because the assumption 3.13 is too far from the reality, especially in moderate dimensions. To know the real optimal parameters and complexities for a chosen LSH family, it is necessary to calculate the probabilities of finding good and bad vectors in function of the definition of the LSH family. Without using the Assumption 3.13, we say this about the bounds for the complexities: Theorem 3.15. The NV-sieve with LSH runs with complexities at most:

1. Time (hashing): O(n • t) 2. Space: O(n • t) 3. Time (query): O(n 2 • p 2 )
The next part shows examples of hash function families to run the two previous algorithms.

Hyperplane LSH

Definition 3.16 (Charikar hash family). [START_REF] Charikar | Similarity estimation techniques from rounding algorithms[END_REF] For a random vector a from a Gaussian distribution, we denote H := {h a : a ∈ R d , a = 1} and h a (v) := 1 if a T v 0 0 if a T v < 0. The vector a defines a hyperplane (for which a is a normal vector), and h a maps the two half-spaces separated by this hyperplane respectively to the bits 0 and 1. For another illustration, in the Figure 3.2 the LSH family was a hyperplane LSH with a combination (Definition 3.12) of k = 2 hash functions together.

v w • • • a h a (v) = 1 h a (w) = 0
Complexity. According to [START_REF] Laarhoven | Search problems in cryptography, From fingerprinting to lattice sieving[END_REF], the NV-sieve with hyperplane LSH heuristically solves SVP in time 2 0.3366d+o(d) and space 2 0.2075d+o(d) .

Polytope LSH

As a reminder: for a vector v ∈ R n , v 1 = n i=1 |v i |. In 1 , spheres are squares. Definition 3.17 (Cross-polytope LSH). [START_REF] Terasawa | Spherical lsh for approximate nearest neighbor search on unit hypersphere[END_REF] Let be e i for i = 1, ..., d the ith unit vector in R d . The d-dimensional cross-polytope is defined as the 1 -unit sphere in R d with as vertices ±e 1 , ..., ±e d .

The hash function associated to the cross-polytope maps a vector v to the nearest vertex to v. Complexity. According to the analysis from [START_REF] Laarhoven | Search problems in cryptography, From fingerprinting to lattice sieving[END_REF], the NV-sieve with cross-polytope LSH heuristically solves SVP in time 2 0.2972d+o(d) and space 2 0.2075d+o(d) .

Hypercone LSH

Definition 3.18 (Spherical LSH). [START_REF] Andoni | Beyond locality-sensitive hashing[END_REF] We assume that all points in a data set L lie on the unit sphere d) vectors s 1 , ..., s u ∈ R d from a d-dimensional Gaussian distribution with average norm of the s i 's being 1. To each s i from i = 1 to u = 2 Θ(d) , we then associate a hash region :

S d-1 = {x ∈ R d : x = 1}. First, we sample u = 2 Θ( √
H i := x ∈ S d-1 : x, s i α i-1 j=1 H j
where α ∈ (0, 1). For instance, [START_REF] Laarhoven | Search problems in cryptography, From fingerprinting to lattice sieving[END_REF] set α = d -1/4 .

s i • v • w • 0 θ θ α 1 -α Figure 3
.4: The red area represents H i . For h i ∈ H the function corresponding to s i , we have for instance here h i (v) = 1 and h i (w) = 0. This indicates how to partition the unit sphere in regions. We now extend this method to all R d . As spherical hash regions correspond to spherical caps, the normalization of the vectors extends these hash regions to hypercones. Definition 3.19 (Hypercone LSH). Given a vector v ∈ R d , the hypercone hash of a vector v ∈ R d is defined as the spherical hash of the normalized vector v/ v ∈ S d-1 . In other words, denoting the spherical hash family by H and the hypercone hash family by H, we have h

(v) = h (v/ v ) for h ∈ H, h ∈ H and v ∈ R d .
Complexity. The NV-Sieve with hypercone LSH heuristically solves SVP in both time and space 2 0.2972d+o (d) .

Proof. The complete proof of this complexity is in the appendix.

Hypercone Locality-sensitive filter (LSF)

A LSF family is a LSH family where a very small number of vectors goes in each hash-bucket. Having a small ρ (ρ < 1 2c 2 -1 ) gives access to a decoding oracle. (See Lemma 3.14 for a reminder of the definition of the parameter ρ.) We will call "filters" the hash functions from a such LSH family.

In this part, we will focus on LSF families based on the same principle of the hypercone LSH seen just above in the section 3.4.3. We will take a larger α, which has effect to reduce the number of vectors surviving one filter. Definition 3.20 (Hypercone locality-sensitive filters). A hypercone filter f is characterised by a unit vector s chosen randomly and a value α ∈ (0, 1). A normalized vector w survives f , i.e. f (w) = 1 iff w, s α. In this case, we will say w survives f . Let µ be the canonical Lebesgue measure over R d . We denote the unit sphere by S d-1 := {x ∈ R d : x = 1} and the half-spaces by H v,α := {x ∈ R d : v, x α}. For v, w ∈ S d-1 such that v, w = cos(θ) and α, β ∈ (0, 1) we denote spherical caps and wedges (Figure 3.5) by:

C v,α := S d-1 ∩ H v,α W v,α,w,β := S d-1 ∩ H v,α ∩ H w,β
Lemma 3.21. [START_REF] Becker | New directions in nearest neighbor searching with applications to lattice sieving[END_REF] Given v, w ∈ S d-1 with v, w = cos(θ), the volume of spherical caps and wedges for a given large d is:

C(α) := µ(C v,α ) µ(S d-1 ) = poly(d) • (1 -α 2 ) d/2 W(α, β, θ) := µ(W v,α,w,β ) µ(S d-1 ) = poly(d) • (1 -γ 2 ) d/2 with γ = α 2 + β 2 -2αβ cos(θ) sin 2 (θ)
Main idea. The purpose is to speed up the algorithms 8 and 9 (NV-and Gauss-sieves with LSH) by selecting the filters that are relevant for the input vectors, instead of sampling them totally randomly. The method proposed by [START_REF] Becker | New directions in nearest neighbor searching with applications to lattice sieving[END_REF] is to sample a code C that admit a fast decoding algorithm, which gives the list of candidate vectors for the reducing.

C = Q • (C 1 × C 2 × • • • C m ),
where Q is a uniformly random rotation over R d and the subcodes C 1 , ..., C m are sets of B vectors, sampled uniformly and independently random over the sphere 1/m • S b-1 . To be useful in our case, the code C has to be efficiently decodable and to behave as a real random code over the sphere, considering the probability of collision between two vectors. Theorem 3.23. [START_REF] Becker | New directions in nearest neighbor searching with applications to lattice sieving[END_REF] There exists an algorithm that, given the description Q, C 1 , ..., C m of a random product code C of parameters [d, m, B] and a target vector t, returns the set S = C ∩ C t,α in average time

T (M, α) = O d • B + m • B log(B) + m • M • C d (α)

Conclusion

Here is a recap of the complexities obtained for the heuristic algorithms heuristically solving SVP by sieving we presented in this report. Remember that these results are only under heuristic assumptions. We see that the hypercone filtering is the actual most promising method, in both classical and quantum models. For the further researches, we can pursue several leads to try improving the complexity of solving SVP by sieving.

The first lead is to modify the NV-sieve with hypercone LSH (Algorithm 8) by cutting the dimension d in half. Concretely, for x = (x 1 , ..., x d ) a lattice vector, we define x L = (x 1 , ..., x d/2 , 0, ..., 0) and x R = (0, ..., 0, x d/2+1 , ..., x d ). In the algorithm, instead of testing vw γR, we test if v L -w L γR/ √ 2 and v G -w G γR/ √ 2. (The 1/ √ 2 are normalization factors.) This method has the advantage to create a saturation of candidate vectors. That allows to recoverer the nearest and it works well with an application of Grover's algorithm.

Then, we could also analyse the NV-sieve with hypercone LSF (Algorithm 11) with this modification.

Secondly, we could take a larger the size of the input list of any NV-sieve based algorithm. The goal is again to get a saturation and find more quickly a reducing vector. There is rapidly a problem of exploding space complexity with a naive application of this method, but it could be overcome it if we do not save all the vectors at time, but only those which are in a delimited part of the sphere.

Thirdly, more generally, we can study other LSH families and see if they are more efficient. Indeed, the hypercone LSH family has good theoretical results but computing angles between vectors in high dimension is not the most practical. We also can focus on families specifically designed for quantum sieves.

Appendix: Proof of the Complexity of the NV-sieve with hypercone LSH

We want to compute the complexity of the NV-sieve (Algorithm 8) with a hypercone LSH family H (Definition 3.19). This proof follows the one developed in [START_REF] Laarhoven | Search problems in cryptography, From fingerprinting to lattice sieving[END_REF]. First we have to check if two nearby vectors collide with a constant probability 1 -, then that a distant vector collide happens with a exponentially small probability, and finally we balance the parameters to get an optimal complexity.

The Lemma 3.1 from [AINR14] stated the following result: Lemma 6.2. The probability that a reducing vector w is a candidate vector for v with θ = θ(v, w) is

p * (θ) := 1 -(1 -p(θ) k ) t .
Proof. It suffices to explain the different probabilities. The probability that at least one vector at angle θ have k hashes equal to v's is p(θ) k . So the probability that there is no vector at angle θ with k same hashes is 1 -p(θ) k . So the probability that there is no vector at angle θ with k same hashes for t hash tables is (1 -p(θ) * ) t . The fact that at least one vector at angle θ has k same hashes than v for t hash tables is equivalent to say that at least one vector at angle θ which reduces v is selected to be a candidate, and its probability is 1 -(1 -p(θ) k ) t .

Nearby vectors collide with constant probability Lemma 6.3. Let > 0 and let k = 6.(ln(t)-ln(ln(1/ )) √ d

. Then the probability that nearby vectors collide in at least one of the hash tables is at least 1 -.

Proof. The probability that a reducing vector w is a candidate vector, given the angle θ = θ(v, w) ∈ (0, π/3) is p * 1 = E θ∈(0,π/3) [p * (θ)]. Since p * (θ) is strictly decreasing in θ, we can obtain a lower bound by substituting θ = π 3 .

p * 1 p * π 3 = 1 -1 -p π 3 k t
We replace by its expression p( π 3 ) = exp - is a constant which does not depend on d. This achieves the proof.

Distant vectors collide with low probability

As a reminder, Assumption 3.9. The angle θ(v, w) between two list vectors v, w ∈ L follows the same distribution as the distribution of angles θ(v, w) between vectors v, w ∈ S d-1 drawn at random from the unit sphere.

Lemma 6.4. [START_REF] Laarhoven | Search problems in cryptography, From fingerprinting to lattice sieving[END_REF] If Assumption 3.9 holds, then the probability density function f (θ) of angles between non-reducing vectors satisfies

f (θ) = 2d π (sin θ) d-2
Since Lemma 6.3 expresses k depending on t, this means that only t remains to be chosen. We write: n = 2 cn.d , t = 2 ct.d , and γ 1 = log 2 ( 4/3) ≈ 0.2075. Lemma 6.5. Let c n γ 1 . Then, if Assumption 3.9 holds, for large d the probability of collisions between distant vectors is bounded by: where α ∈ (0, 1) is defined as

α = - 1 c n max θ∈( π 3 , π 2 )
log 2 sin(θ) -c t 3 tan 2 θ 2 -1 Remark 6.6. The condition c n γ 1 is easily satisfiable with no additional cost caused by a too large n. Indeed, we have seen in Section 3.2 the explanation of the setting of c n .

Proof. Two "bad" vectors has an angle θ ∈ ( π 3 , π 2 ). Letting f (θ) denote the density of angles θ ∈ ( π 3 , π 2 ), we have:

p * 2 = E θ∈( π 3 , π 2 ) [p * (θ)] =
)) ) t dθ we omit the normalizing constant (negligible) for f (θ), and k given by Lemma 6.3.

  Any basis (|x , |y ). The Hadamard basis: (|+ , |-).

For example: for A = a 11 a 12 a 21 a 22 and B = b 11 b 12 b 21 b 22 ,a

 22 11 b 11 a 11 b 12 a 12 b 11 a 12 b 12 a 11 b 21 a 11 b 22 a 12 b 21 a 12 b 22 a 21 b 11 a 21 b 12 a 22 b 11 a 22 b 12 a 21 b 21 a 21 b 22 a 22 b 21 a 22 b 22

  Phase gate: R θ rotates the phase of |1 by an angle θ.

Figure 2 . 2 :

 22 Figure 2.2: Entanglement circuit. (Illustration from [dW19])

Figure 2

 2 Figure 2.3: Shor's algorithm circuit. (Illustration from [dW19])

Figure 2

 2 Figure 2.4: Geometrical representation of the state of the N -qubit register.

  Ox,±, reflection through |B . H ⊗n RH ⊗n , reflection through |U .

Figure 2 . 6 :

 26 Figure 2.6: Circuit of the algorithm with k Grover iterations. (Illustration from [dW19])

Algorithm 5

 5 The Nguyen-Vidick sieve Require: a list L of n vectors of norm R ; a sieve factor γ such that 2/3 < γ < 1 Ensure: the list L of n vectors of norm γR L := empty list sample C ⊂ L ∩ {x ∈ R d : x γR} of poly(d) • n for each v ∈ L\C do if v γR then add v to the list L else for each w ∈ C do if vw γR then add vw to the list L continue the loop for over "v ∈ L\C" return L Assumption 3.9. (validated by experiments [NV08]) The angle θ(v, w) between two list vectors v, w ∈ L follows the same distribution as the distribution of angles θ(v, w) between vectors v, w ∈ S d-1 drawn at random from the unit sphere.

Figure 3

 3 Figure 3.1: For v and w of length R in L, if vw has a length of γR or less we add it to L .

Figure 3 . 3 :

 33 Figure 3.3: Example of a hyperplane hash function.

  More formally: h(v) := sign(v i * )e i * with i * = max i∈[|1,d|] |v i |.

Figure 3

 3 Figure 3.5: Representation on the unit sphere of caps, wedges, and parameters α and β.

  Definition 3.22 (Random product codes). A random product code C of parameters [d, m, B] on subsets of R d and of size M = B m is defined as a code of the form

Figure 4 . 1 :

 41 Figure 4.1: The space/time trade-offs curves of the sieving algorithms (Illustration from [Laa15]).

Lemma 6. 1 .

 1 Let v, w ∈ R d and let θ denote the angle between v and w. Then for large d, the hypercone hash family H satisfies:p(θ) := Pr h∈H [h(v) = h(w)] = exp -

  and we choose k = 6.(ln(t)-ln(ln(1/ )) 1 -exp(-ln(t) + ln ln(1/ ))t = 1 -1 -ln(1/ ) t t 1 -because ∀x, 1 -x e -x, with here x = ln(1/ ) t .

  collide | θ(v, w) > π 3 n -α+o(1)

  o(1)) ) t dθ by Lemma 6.4 for f (θ) and Lemma 6.1 for p * (θ) ) d 1 -(1 -exp -3 ln(t) tan 2 ( θ

  Algorithm 2 Solving HSP if G is abelian Require: Two registers |O |G| |0 |S| Ensure: the hidden subgroup g

	Apply the QFT	we get an uniform superposition |g |0
	Apply O f	we get the state |g |f (g)
	Measure the second register	we obtain f (s)
	Apply the QFT on the first register
	Measure the first register	we obtain g

Complexity. This algorithm runs in time O( √ N ) with N the number of the subgroups of G.

  which is realizable in O(n) elementary gates. Proposition 2.14. O x,± acts as a reflection through |B , and H ⊗n RH ⊗n acts as a reflection through |U . Proof. O x,± |i = (-1) xi |i does not change the state |B if applied on, because we have in this case x i = 0. And for all other states |i , it changes its sign. So it is by definition a reflection through |B .

Remerciements

Je voudrais tout d'abord adresser toute ma gratitude à mon tuteur de stage, André Chailloux, pour l'encadrement et la pédagogie dont il a fait preuve, et ce malgré les conditions très particulières dans lesquelles se sont déroulées ce stage. Je le remercie également pour la confiance qu'il m'a accordée en acceptant que je poursuive en thèse avec lui. J'ai hâte de travailler sur ces fameuses pistes cyclables quantiques.

Je tiens à remercier mes collègues de l'équipe-projet COSMIQ pour leur accueil et les échanges passionnants que nous avons eus. Merci aussi de m'avoir fait réaliser grâce à leur engagement qu'il y a aussi des aspects humains et même politiques qui entourent la cryptologie.

We choose these parameters such that γ 2 < 1 < γ 1 < √ 2γ 2 . γ 1 is chosen larger than in the 1-level sieve, each of the vectors in C 1 will now cover a larger part of the space.

Algorithm 7 The 2-level sieve Require: a list L of (4/3) d/2+o(d) vectors of norm R Ensure: the list L of (4/3) d/2+o(d) vectors of norm γ 2 • R L := empty list |. [START_REF] Wang | Improved nguyen-vidick heuristic sieve algorithm for shortest vector problem[END_REF] showed that these values only depend of γ 1 , γ 2 and d. The number of centers stored is n 1 n 2 , so it is the space complexity. And for each of these vectors, we need to perform over C 1 and (potentially) another search over a list C (w1) 2

. Thus the time complexity is n 1 n 2 (n 1 + n 2 ). Since, we can look for which values γ 1 and γ 2 minimize the complexities. The optimal γ 2 is 1, and the optimal γ 1 can be calculated at x ≈ 1.093 a root in (1, √ 2) of the polynome x 6 -4x 4 + 4. From this, the 2-level sieve solves SVP in time 2 0.3836d+o(d) and space 2 0.2557d+o (d) .

High-level sieving

Complexity. The k-level sieve has the same structure than the 2-level sieve, with centers sets

According to [START_REF] Laarhoven | Search problems in cryptography, From fingerprinting to lattice sieving[END_REF], for k 3, the optimal parameters are (γ 1 , ..., γ k ) = (x k-1 , ..., x, 1) where x ∈ [1, 2 1/(2k-2) ] is a root of x 4k-2 -4x 2k + 4. Which this choice, time and space complexities are 2 ctimen+o(n) and 2 cspacen+o(n) where c time = (k + 1) log 2 (x) and c space = k • log 2 (x).

So these coefficients are lower and lower until 4 : c time = 0.3774 and c space = 0.2925. However, for k > 4, the exponents increase again.

Remark 3.10. It appears that for a same k the trade-off curves (space/time complexities) are exactly the same for the k-level sieve and the sieve based on overlattices [START_REF] Becker | A sieve algorithm based on overlattices[END_REF] with a tower of k overlattices.

The parameters of the algorithms are:

• t the number of hash tables,

• k the number of hash functions combined together to construct each h j .

If we do not precise other notations, we consider in all this part 1 i k and 1 j t. The following lemma (inspired from [START_REF] Indyk | Approximate nearest neighbors: To-wards removing the curse of dimensionality[END_REF]) gives an approximation for the values of parameters and the corresponding complexities of the sieve algorithms with LSH. Assumption 3.13. For all v, w ∈ L, if vw > γR then v and w are orthogonal.

For a given i ∈ [|1, m|], c i,j with j ∈ [|1, B|] are the elements of C i after the sort. We denote d i,j := c i,j , t i , with t i the vector with all-zero except the ith position which is equal to t i .

Algorithm 10 List decoding

Require: The description Q, C 1 , ..., C m of the code C, a target vector t ∈ R d and α ∈ (0, 1). Ensure: L = C ∩ C t,α containing all α-close words to t.

L := empty list Sort each C i by decreasing

Proof. This algorithm has an overall running time which is the sum of the following three terms:

Thus, we can consider we have an oracle that allows us to compute efficiently relevant filters to the input list of vectors.

The algorithm has the following parameters:

• t ∈ N: number of hash tables.

• α ∈ (0, 1): the query parameter for finding the relevant vectors of a given target vector. Increasing α decreases the number of queries to filters to find nearby vectors.

• β ∈ (0, 1): the insertion parameter for finding all filters that a vector is inserted in. Increasing β decreases the number of vectors we store in buckets.

The parameter k is set at 1. So we do not longer combine hash functions together.

Theorem 3.24 (Costs of one query). Given n points uniformly distributed on the sphere, and t spherical filters with parameters α, β, the time to answer a query is:

First, to answer a query, we compute the O(t • C(α)) relevant filters using list decodable random product codes.

We assume the vectors in L are uniformly distributed on the sphere, and all filters cover an equal portion of the sphere (Assumpion 3.9). So, each filter bucket will roughly have the same size.

In total each list vector has been inserted in O(t • C(β)) filters, leading to O(n • t • C(β)) total entries in the filter database, and O(n • C(β)) vectors per filter.

We have the cost of computing relevant filters O(t•C(α)) summed with the cost of comparing the vector to all other vectors in these filters O(t•C(α)•n•C(β)). In total, we get that a query costs

Setting of t the number of filters

We want to make sure that we do not miss nearby vectors at angle π 3 , which are potential reducing vectors. The probability that two vectors at angle π 3 are found through a collision is

)), that we want to be close to 1. Thus:

Choice of the query and insertion parameters α and β

We keep n = (3/4) d/2+o(d) , for the reason explained in section 3.2.

Time complexity. T = T preprocessing + T queries . For the preprocessing, for each of the n input vectors we have compute the t • C(β) relevant filters.

Space complexity. We store n vectors and t.n.C(β) filters, represented also by vectors in R d .

Complexity. The NV-sieve with hypercone LSF solves SVP in • time and space T = S = (3/2) d/2+o(d) 2 0.292d+o(d) for α = β = 1 2 ,

• time T = (5/3 d/2+o(d) ) 2 0.292d+o(d) and space S = (4/3) d/2+o(d) 2 0.368d+o(d) for α = 1 4 and β = 1 2 .

By setting β = 1 2 and varying α between these two values, we can get the optimal time complexity for a given space complexity.

Quantum speed-ups

In this part, we are going to look at the complexities we can hope in the quantum model. To do that, we apply Grover's algorithm (Amplitude amplification, Algorithm 4 in section 2.4) on the search phase for the candidate vectors.

As a reminder, Grover's algorithm returns x such that f (x) = 1 with a complexity of O( √ n) instead of O(n) in classical. However, this quadratic gain only concerns a search phase, not the whole sieves.

The Nguyen-Vidick and Gauss Sieves.

Given two lattice vectors v and w, we define f v (w) := 1 if vw γR 0 else.

Algorithm 12

The Quantum NV-sieve Require: a list L of n vectors of norm R ; a sieve factor γ such that 2/3 < γ < 1 Ensure: the list L of n vectors of norm γR

We get a w such that vw γR (or "no solution"). add vw to the list L return L Complexity. [START_REF] Laarhoven | Solving the shortest vector problem in lattices faster using quantum search[END_REF] For a given v, the complexity of finding a reducing w (if it exists) is O( √ N ). This leads to complexities in time (4/3) 3d/2+o(d) 2

2 0.311d+o (d) and in space (4/3) d/2+o(d) 2 0.208d+o(d) . Classical time complexity was 2 0.415d+o(d) for the same space complexity. So the quantum NV-sieve is 25% faster than the classical one.

The GaussSieve obtains exactly the same speed-up.

Leveled and Overlattice Sieves.

These two methods give complexities not better than the quantum NV-sieve. In short, the reason is that they operates with many search subroutines which cannot be speeded up by simply applying Grover.

LSH and LSF.

Given two lattice vectors v, w and a set of vectors C, we define f v,C (w) := 1 if w ∈ C and vw γR 0 else.

Algorithm 13 Quantum NV-sieve with LSH Require: a list of n vectors of norm R n = (4/3) d/2+o(d) Ensure: the list L of n vectors of norm γ.R L := empty list sample C with poly(d) • n elements of L ∩ {x ∈ R d : x γ.R} T 1 , ..., T t := empty hash tables and sample k.t random hash functions h i,j ∈ H for each w ∈ C do add w to the bucket

We get a w ∈ C such that vw γR (or "no solution"). add vw to the list L The classical time complexity of a search in the candidates list is n 1-α . By applying Grover for this search, the time complexity is reduced to √ n 1-α . So the total number of comparisons is O(n (3-α)/2 ) and the number of hashing remains at O(n • t). The parameters k and t have then to be computed for each LSH family to get the optimal complexities of the algorithm in its quantum version.

Hyperplane LSH According to [START_REF] Laarhoven | Search problems in cryptography, From fingerprinting to lattice sieving[END_REF], it solves SVP in time 2 0.286d+o(d) and space 2 0.208d+o (d) , which is a speed-up of about 15%.

Cross-polytope LSH According to [START_REF] Becker | Efficient (ideal) lattice sieving using cross-polytope lsh[END_REF], it solves SVP in time 2 0.268d+o(d) and space 2 0.208d+o (d) , which is a speed-up of about 10%.

Hypercone LSH According to [START_REF] Laarhoven | Solving the shortest vector problem in lattices faster using quantum search[END_REF], it solves SVP in time 2 0.268d+o(d) and space 2 0.208d+o (d) , which is a speed-up of about 10%.

Note that cross-polytope and hypercone LSH has the same complexities in both classical and quantum.

Hypercone LSF According to [START_REF] Laarhoven | Search problems in cryptography, From fingerprinting to lattice sieving[END_REF], it solves SVP in time 2 0.2975d+o(d) and space 2 0.208d+o (d) , which is a speed-up of about 9%.

For more practicity, let write w(θ) = [-3 ln(t) tan 2 (θ/2)](1 + o(1)).

Note that for θ ∈ ( π 3 , π 2 ) far from π/3, we have w(θ) << w(π/3) = -ln(t), so 1 -exp(w(θ))

t ≈ 1 -t. exp(w(θ)). However, the integration range include π/3. So we split the integration interval at π/3 + δ where δ = Θ(1/ √ d). Bounding I 1 . f is croissant in θ, thus for π/3 θ π/3+δ, we have f (θ) f ( π 3 +δ). And with p * (θ) 1, we obtain

by the Taylor expansion of sin(x) for x ≈ π/3 which gives: sin

Bounding I 2 . The choice of δ = Θ(1/ √ d) allows to consider that the o(1)-term in w(θ) can be neglected.

Thus we obtain log 2 (I 2 ) max

Combining previous bounds, with the assumption that c n γ 1 :

By setting:

Indeed, we have c n α by assumption we did and α < 1 by definition. So we also have -γ 1 -αc n +o(1). Thus p * 2 n -α , that achieves the proof.

Balancing the parameters and overall complexity Theorem 6.7. The NV-sieve with hypercone LSH heuristically solves SVP in time and space 2 0.2972d+o(d) using the parameters k = 0.3727 √ d + o(d) and t = 2 0.0896d+o(d) .

Proof. By the two previous lemmas, we have 1. The average probability that a reducing vector w collides with v in at least one of the t hash tables is at least constant in d: p * 1 = Pr hi,j ∈H v, w collide |θ(v, w) π 3 1 -2. The average probability that a non-reducing vector w collides with v in at least one of the t hash tables is exponentially small:

3. The number of hash tables grows as t = n 0.4319+o(1)

The complexities of the algorithm are given by:

• time (hashing): O(n.t) = 2 (cn+ct)d+o(d)

• time (searching): O(n 2 .p * 2 ) = 2 cn+(1-α)cn.d+o(d)

• time (overall): 2 (cn+max{ct,(1-α)cn})d+o(d)

• space: O(n.t) = 2 (cn+ct)d+o (d) We write the time and space complexities as 2 ctimed+o(d) and 2 cspaced+o(d) . We have:

We search to minimize the overall time complexity, thus we balance the hashing and searching complexities, i.e. we solve (1 -α)γ 1 = c t numerically for c t .

We obtain c t ≈ 0.0896. We denote θ * the angle in the expression of α. This leads to:

θ * ≈ 0.425, α ≈ 0.568, c time ≈ 0.297, c space ≈ 0.297.

With parameters t = 2 0.0896 and k = 6. ln(t) √ d , both time and space complexities are thus balanced at 2 0.297d+o (d) .