André Chailloux
email: andre.chailloux@inria.fr∥johanna.loyer@gmail.com

Johanna Loyer

Classical and Quantum 3 and 4-Sieves to Solve SVP with Low Memory

Keywords: Shortest Vector Problem (SVP), Lattice sieving, Locality-sensitive filtering (LSF), Configuration problem. ×

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The Shortest Vector Problem (SVP) is a central problem in lattice-based cryptography. For a given d-dimensional lattice, SVP asks to find a shortest non-zero vector in the lattice. This problem admits a variety of derived problems such as SIS, LWE and their modular or ring versions, on which several of the (believed to be) quantum-resistant cryptographic protocols rely, such as Dilithium [START_REF] Ducas | CRYSTALS-Dilithium, Algorithm Specifications and Supporting Documentation[END_REF] and Kyber [START_REF] Bos | CRYSTALS -Kyber: a CCAsecure module-lattice-based KEM[END_REF] both winners of the NIST standardization process. It is therefore crucial to estimate the hardness of these constructions both in classical and quantum models.

There are two main families of algorithms for SVP: those based on enumeration [FP85; [START_REF] Kannan | Improved algorithms for integer programming and related lattice problems[END_REF][START_REF] Michael | On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications[END_REF] and those based on sieving [START_REF] Nguyen | Sieve algorithms for the shortest vector problem are practical[END_REF][START_REF] Micciancio | Faster exponential time algorithms for the shortest vector problem[END_REF]. The former does not have good asymptotic running but requires a small amount of memory and has good performances in practice. The latter has much better asymptotic running time -especially with heuristics that improve the analysis of these algorithms -but requires a very large amount of memory, sometimes as much as the running time. Despite these strong memory requirements, the current best algorithms for SVP in practice are based on sieving methods1 .

The rough idea of sieving algorithms is the following: we start from a list of lattice points of large norm and sum them in order to find shorter lattice points, and repeat until we find a short vector. However, the number of points we have to start with is very large, which explains the large memory requirements. For example, in 2-sieve algorithms, where we start from a list of N points and build shorter points by summing pairs, we need to take N = 2 0.2075d+o (d) in order to be able to build enough shorter lattice points.

Reducing this memory requirement makes the attack more materially practical, and a way to do it is by the k-sieve introduced in [START_REF] Shi Bai | Tuple lattice sieving[END_REF] and then improved by [START_REF] Herold | Improved algorithms for the approximate k-list problem in Euclidean norm[END_REF][START_REF] Herold | Speedups and time-memory trade-offs for tuple lattice sieving[END_REF][START_REF] Kirshanova | Quantum Algorithms for the Approximate k-List Problem and their Application to Lattice Sieving[END_REF]. The idea is to sum k lattice points instead of pairs at each sieving step in order to find shorter ones. This decreases the number N of lattice points that we need at each step to find the same number N of shorter lattice points. However, this will drastically increase the time to perform the sieving step. For instance, a naive exhaustive search of each k-tuple takes time O(N k ), and the fact that N is smaller does not outweigh this increased exponent, see Table 1. Table 1: N is the number of points needed for k-sieving. N k is the running time of a naive exhaustive search for k-sieving.

There are two main ideas that significantly improve the complexity of k-sieving algorithms:

-For 2-sieving, perform locality-sensitive filtering (LSF). The idea is to regroup lattice points into filters for which pairs are more likely to be reducible than random pairs. The most efficient known way to perform LSF for 2-sieve is to construct a code that behaves as a random code but which is efficiently decodable. In [START_REF] Becker | New directions in nearest neighbor searching with applications to lattice sieving[END_REF], the authors use a random product code to achieve this. Then, filters will correspond to all lattice points which will be close to a given code point. -For k > 2, one can replace the reducibility constraint ∥⃗

x 1 + • • • + ⃗ x k ∥ ≤ R
(starting from vectors of norm R) with constraints of the form ⟨⃗ x i |⃗ x j ⟩ ≤ C i,j for some well-chosen C i,j . This is known as the configuration problem. The main advantage is that we now only have constraints on pairs of points instead of k-tuples and we can use much more efficient algorithms, including the LSF idea presented above.

Fig. 1:

A 1 + A 2 + A 3 = ⃗ 0 with ⟨A i |A j ⟩ = -1 2 for i ̸ = j.
In this work, we add an extra idea that gives better time-memory trade-offs for 3-sieve and 4-sieve algorithms, both in the classical and quantum regimes, and introduce the notion of LSF tailored for k-sieving. In previous algorithms, we first start from a configuration problem and then use LSF only on pairs of points. Here, we first use LSF in a way to construct many lists of lattice points L 1 , . . . , L k such that k-tuples (⃗ x 1 , . . . , ⃗ x k ) ∈ L 1 × • • • × L k are more likely to reduce than random k-tuples.

We illustrate briefly this idea with an example: in 3-sieve algorithms, we look for triplets of lattice points (⃗ x 1 , ⃗ x 2 , ⃗ x 3 ) each of norm R such that ∥⃗ x 1 +⃗ x 2 +⃗ x 3 ∥ ≤ R. Instead of directly translating this condition into a configuration problem, we first perform a filtering step as follows: consider a list-decodable code that contains many triples of words A 1 , A 2 , A 3 such that A 1 + A 2 + A 3 = ⃗ 0 (see Figure 1). If we consider lists of lattice points L 1 , L 2 , L 3 such that each L i contains lattice points close to A i , then triplets of points (⃗ x 1 , ⃗ x 2 , ⃗ x 3 ) ∈ L 1 × L 2 × L 3 of norm R are more likely to satisfy ∥⃗ x 1 + ⃗ x 2 + ⃗ x 3 ∥ ≤ R than random triplets. We then use known algorithms on configuration search on these triplets of lists to find reducible triplets.

We summarize our contributions below.

-We show how to extend the construction of random product codes of [START_REF] Becker | New directions in nearest neighbor searching with applications to lattice sieving[END_REF] as a means of performing LSF tailored for k-sieving. Our code will also be efficiently decodable and the set of codewords can be partitioned into sets

{A 1 , . . . , A k } each of size k such that A 1 + • • • + A k = ⃗ 0.
-We analyze classical and quantum algorithms for 3 and 4-sieving using this k-sieve tailored filtering, and get improved time-memory trade-offs for these algorithms.

We first analyze our results for classical algorithms (see Figure 2). For the 3sieve, our algorithm performs better in the minimal memory regime. In the main text, we also present other time-memory trade-offs. However, when we do not restrict memory, we obtain the same running time 2 0.3041d+o (d) as in [START_REF] Herold | Speedups and time-memory trade-offs for tuple lattice sieving[END_REF] and our method does not give improvements here. For 4-sieve algorithms, the situation is a little different. We use a different algorithm than the ones studied in previous work. We essentially combine sequentially two 2-sieve algorithms. However, we first perform our tailored LSF on 4-tuples of points to speed up this process. As Figure 2 shows, this algorithm does not perform well in the minimal memory regime (M = 2 0.1723d+o(d) ) but then works much better for slightly larger memories, outperforming our 3-sieve algorithm and also the best previously known running time for 4-sieve, which used more memory.

We must notice however that it is hard to make direct comparisons with previous work in the classical setting as those are mainly done for Gauss-sieve and we present results for NV-sieve which has better time-memory trade-offs asymptotically. However, our results do show that tailored LSF significantly improves the algorithms we study, and we leave it as future work to extend this idea to the Gauss sieve. In the quantum setting (see Figure 3), we use the same algorithms as in [START_REF] Kirshanova | Quantum Algorithms for the Approximate k-List Problem and their Application to Lattice Sieving[END_REF] so the comparison can be made more directly. Our algorithm uses our tailored filtering and then applies Algorithm 4.1 of [START_REF] Kirshanova | Quantum Algorithms for the Approximate k-List Problem and their Application to Lattice Sieving[END_REF], which is not the best algorithm for the configuration problem for low values of k. What we show is that this algorithm benefits from this prefiltering. The results should be compared with the state-of-the-art Algorithm B.2 of [START_REF] Kirshanova | Quantum Algorithms for the Approximate k-List Problem and their Application to Lattice Sieving[END_REF]. However, only the extremities of the trade-offs of their algorithm were given, represented by triangles on the graphs of Figure 3. For k = 3 in the minimal memory regime M = 2 0.1887d+o(d) , we achieve time T = 2 0.3098d+o(d) improving the time T = 2 0.3266d+o(d) of Algorithm B.2 in [START_REF] Kirshanova | Quantum Algorithms for the Approximate k-List Problem and their Application to Lattice Sieving[END_REF]. For k = 4, our algorithm does not work well for the lowest memory regime but gives a new interesting time-memory trade-off.

Notice that as in previous algorithms cited here, our quantum algorithms require quantumly accessible classical memory (QRACM) and poly(d) qubits.

Outline of the article. Section 2 introduces the helpful preliminaries on quantum computing and lattice sieving. Section 3 presents the new code structure for the filtering step tailored for k-sieving. Then, we present a framework to solve SVP by sieving in Section 4, and describe some instances within this framework in the classical model in Section 5 and in the quantum model in Section 6.

Preliminaries

Notations. We designate the elements of R d as vectors as well as points. The norm considered in this work is Euclidean and is denoted by ∥ • ∥. We denote by S d-1 = {⃗ x ∈ R d : ∥⃗ x∥ = 1} the d-dimensional unit sphere. For two vectors ⃗ x 1 , ⃗ x 2 ∈ R d , ⟨⃗ x 1 |⃗ x 2 ⟩ denotes their scalar product and θ(⃗ x 1 , ⃗ x 2 ) = arccos( ⟨⃗ x1|⃗ x2⟩ ∥⃗ x1∥∥⃗ x2∥ ) denotes their angle. We use the notation O to denote running times T = O 2 cd , which ignores sub-exponential factors in d.

Quantum computing

QRAM model. The Quantum Random Access Memory (QRAM) is an operation added to the quantum circuit model. We consider here only quantum-accessible classical memory (sometimes denoted as QRACM in the literature). Consider N classical registers x 1 , ..., x N ∈ {0, 1} d stored in memory. A QRAM operation consists of applying the following unitary

U QRAM : |i⟩ |y⟩ → |i⟩ |x i ⊕ y⟩ .
This work relies on the QRAM model, meaning that the above unitary can be constructed efficiently. In particular, we assume that given list L there exists an efficient quantum circuit for 1

√ |L| i |i⟩ |0⟩ → 1 √ |L| i |i⟩ |L[i]⟩.
With a QRAM access to L, this can be done by applying Hadamard gates to state |0⟩ to create a superposition over all indices, and then by querying L[i] for each i in the superposition.

Proposition 1 (Grover's algorithm [START_REF] Grover | A fast quantum mechanical algorithm for database search[END_REF]). We are given QRAM access to a list L = {x 1 , ...x ℓ }. We consider a function f : L → {0, 1}, associated to its unitary O f : |x⟩ |y⟩ → |x⟩ |y ⊕ f (x)⟩, such that there are t elements x i ∈ L said "marked" verifying f (x i ) = 1. The value t is not necessarily known. There exists a quantum algorithm, called Grover's algorithm, that returns a marked element with probability greater than 1/2 using O( |L|/t) calls to O f . Classically, this problem cannot be solved with a better average complexity than Θ(|L|/t) queries in the black box model.

Proposition 2 (Quantum Amplitude amplification [START_REF] Brassard | Quantum amplitude amplification and estimation[END_REF]). Let A be an algorithm without measurements that finds a solution x ∈ L such that f (x) = 1 with a success probability p. Quantum amplitude amplification returns a solution with probability 1/2 using O(1/ √ p) calls to O f .

Moreover, one can make the success probability of these algorithms go exponentially close to 1 by repeating them k times: Proposition 3. Grover's algorithm (resp. Quantum Amplitude Amplification) described above can have a success of 1 - Definition 2 (Shortest Vector Problem). Given a basis B, the Shortest Vector Problem (SVP) asks to find a shortest non-zero vector of L(B). By Minkowski's theorem, the Euclidean norm of a shortest vector of L(B) is upperbounded by

2 -η with O(η |L|/t) (resp. O(η/ √ p)) calls to O f .
√ d • det(B) 1/d .
Sieving algorithms. The sieving algorithms, introduced by [START_REF] Nguyen | Sieve algorithms for the shortest vector problem are practical[END_REF], are a class of heuristic algorithms that solves SVP. Given a list of lattice vectors of norm at most R and a reducing factor γ < 1, a sieving step will return a list of lattice vectors of norm at most γ. To obtain these reduced vectors, it computes all the differences between pairs of vectors of the input list and fills the output list with those which are of norm at most γ. Then, it iteratively builds lists of shorter lattice vectors by applying this sieve step. The first list of lattice vectors can be sampled with Klein's algorithm [START_REF] Klein | Finding the closest lattice vector when it's unusually close[END_REF] for example. Because the norms of the list vectors reduce with a factor by γ < 1 at each sieve step, the output list will hopefully contain a non-zero shortest lattice vector after a polynomial number of iterations.

We present here two simplifications of notation. First, we will only consider the case R = 1. Indeed, all the algorithms we consider will be independent of R. Also, in practice, we have γ ≈ 1 (typically γ = 1 -1 poly(d) notations, we will fix γ = 1 which doesn't change the overall analysis of these algorithms.

There is also another family of sieving algorithms called Gauss-sieve. These have worse asymptotic time-memory trade-offs so we don't analyze them in this work since we are interested in the best asymptotic time-memory trade-offs. However, they are usually faster in practice and it is an interesting follow-up to look at how our new ideas for sieving apply in this setting.

The sieving algorithms stand under the following heuristic.

Heuristic 1. Lattice points behave like uniform points.

Notice that uniform vectors of norm at most 1 are with a high probability of norm close to 1. So we will consider that the lattice vectors are lying on the sphere S d-1 . The relevance of this heuristic has been studied in [START_REF] Nguyen | Sieve algorithms for the shortest vector problem are practical[END_REF]. It becomes invalid when the vectors become short, but in this case, we can assume we have solved SVP. In practice, the faster algorithms to solve SVP rely on this heuristic.

Tuple-sieve and k-List algorithms. The NV-sieve described above can be generalized to the k-sieve.

Definition 3 (Approximate k-Lists problem). Given k lists L 1 ..., L k of equal exponential (in d) size N and whose elements are i.i.d. uniformly cho- sen vectors from S d-1 , the approximate k-List problem is to find N k-tuples (⃗ x 1 , . . . , ⃗ x k ) ∈ L 1 × • • • × L k satisfying ∥⃗ x 1 + • • • + ⃗ x k ∥ ≤ 1.
Volume of spherical cap / Hypercone filter. We define the spherical cap of center ⃗ s and angle α as follows:

H ⃗ s,α := {⃗ x ∈ S d-1 | θ(⃗ x,⃗ s) ≤ α}.
In order to compute the complexity of sieving algorithms, we will need the following value.

Proposition 4. ([Bec+16], Lemma 2.1) For an angle α ∈ [0, π/2] and a vector ⃗ v ∈ S d-1 , the ratio of the volume of a spherical cap H ⃗ v,α to the volume of the sphere

S d-1 is V(α) := poly(d) • sin d (α).

Configurations

In the approximate k-Lists problem, we have the condition

∥⃗ x 1 + • • • + ⃗ x k ∥ ≤ 1.
Notice that we can rewrite

∥⃗ x 1 + • • • + ⃗ x k ∥ 2 = k i=1 ∥⃗ x i ∥ 2 + 2 k i,j̸ =i ⟨⃗ x i |⃗ x j ⟩.
This means that the condition on ∥⃗ x 1 +• • •+⃗ x k ∥ can be verified if some constraints on the ⟨⃗ x i |⃗ x j ⟩ are verified. This motivates the following definition:

Definition 4 (Configuration). The configuration C of k points ⃗ x 1 , . . . , ⃗ x k ∈ S d-1 is the Gram matrix of the ⃗ x i 's, i.e. C i,j = ⟨⃗ x i |⃗ x j ⟩.
A configuration is said balanced when for i ̸ = j, C i,j = -1/k and C i,i = 1. In this case, the tuple points will form together the summits of a regular polyhedron inscribed in the sphere.

For

k-tuple (⃗ x 1 , . . . , ⃗ x k ) with ⃗ x i ∈ L i such that ⟨⃗ x i |⃗ x j ⟩ ≤ C i,
j for all i, j.

[HK17] showed that the approximate k-Lists problem (Definition 3) can be reduced to the configuration problem.

Proposition 5 ([HK17]

). The probability that a k-tuple of i.i.d. uniformly random points on

S d-1 satisfies a given configuration C ∈ R k×k is det(C) d/2 .
After a sieving step on a list L, we want to get |L| k • det(C) d/2 k-tuples satisfying the chosen configuration C, so that they are reducing k-tuples. We need this number of solutions to be equal to |L|. So we can deduce the required size of L, in function of the target configuration:

|L| = O 1 det(C) d 2(k-1)
.

(1)

For a fixed k, the minimum value of |L| is reached when the configuration C is balanced. In particular, for a balanced configuration with k = 2 we require (4/3) d/2 = 2 0.2075d+o(d) points ; for k = 3, (27/16) d/4 = 2 0.1887d+o(d) points and for k = 4, (256/125) d/6 = 2 0.1724d+o(d) points. See Table 1 for the other values of k. We see that this value decreases with k, and that is the main interest of the k-sieve: to reduce the minimum memory we require to solve SVP. Considering non-balanced configurations leads to not reaching the lower bound for memory, but it can allow decreasing time by adding a little memory. This is useful to get better time-memory trade-offs.

Proposition 6 (Size of the filtered lists L i (x j ) given C i,j [START_REF] Kirshanova | Quantum Algorithms for the Approximate k-List Problem and their Application to Lattice Sieving[END_REF]). We are given a configuration C ∈ R k×k and lists

L 1 , . . . L k ⊂ S d-1 each of size |L j |. For ⃗ x 1 , . . . , ⃗ x i ∈ S d-1 , we denote L j (⃗ x 1 , . . . , ⃗ x i ) := {⃗ x j ∈ L j : ⟨⃗ x 1 |⃗ x j ⟩ ≤ C 1,j , . . . , ⟨⃗ x i |⃗ x j ⟩ ≤ C i,j }. Then, for a i-tuple ⃗ x 1 , . . . , ⃗ x i satisfying the configuration C[1 . . . i], the ex- pected size of L j (⃗ x 1 , . . . , ⃗ x j ) is E(|L j (⃗ x 1 , . . . , ⃗ x i )|) = |L j | • det(C[1, . . . , i, j]) det(C[1, . . . , i]) d/2
.

And in particular,

E(|L j (⃗ x i )|) = |L j | • 1 -C 2 i,j d/2 .
3 Code structure and filtering

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 , so that codewords are points of the sphere S d-1 . We can have a full description of C by storing mB points corresponding to the codewords of C 1 , . . . , C m and by storing the rotation Q. When the context is clear, C will correspond to the description of the code or to the set of codewords. The code points of C behave like random points of the sphere S d-1 . This was argued in [START_REF] Becker | New directions in nearest neighbor searching with applications to lattice sieving[END_REF], see for instance Lemma 5.1 and Appendix C therein. Random product codes can be easily decoded in some parameter range, as the following proposition shows.

Proposition 7 ([Bec+16]

). Let C be a random product code of parameters (d, m, B) with m = log(d) and B m = N O(1) . For any ⃗ x ∈ S d-1 and angle α,

one can compute H ⃗ x,α ∩ C in time N o(1) • |H ⃗ x,α ∩ C|, where H ⃗ x,α is defined in Proposition 4.
Definition 6 (Hypercone filter). Given a center A j i ∈ S d-1 and an angle α, the filter f A j i ,α is the set of all points in S d-1 of angle at most α with A j i .

Random Product Codes are useful tools to search reducing pairs of lattice vectors in a sieving step (Algorithm 1). Indeed, given a list of lattice vectors on S d-1 and a Random Product Code C, we can efficiently compute for a given vector all its nearest codewords. In this way, we construct lists that contain vectors from the input list close to the codewords. Each codeword is considered the center of a filter. Then, we can search in the same filter two vectors ⃗ x 1 , ⃗ x 2 such that ⃗ x 1 -⃗ x 2 is reduced. By adding Locality Sensitive Filtering using Random Product Codes [Bec+16; Laa16] in a sieving step, this provides the actual best algorithms to solve SVP. The sieve with LSF reaches time 2 0.292d+o(d) in the classical model [START_REF] Becker | New directions in nearest neighbor searching with applications to lattice sieving[END_REF], in time 2 0.257d+o(d) in the quantum model [CL21; Hei21; Bon+22].

However, a k-sieve structure for k > 2 searches k-tuples such that ⃗ x 1 +• • •+⃗ x k is reduced. Then, searching within one unique filter does not permit to quickly find a solution without having to check a lot of non-reducing elements. So we will slightly modify the construction of the random product code in order to take into account a configuration. k-Random Product Code In order to describe our k-Random Product Code construction, we start with the case k = 3. Instead of constructing fully random codes C 1 , . . . , C m , we will construct random codes C i which have the following property:

∀A 1 ∈ C i , ∃A 2 , A 3 ∈ C i st. A 1 + A 2 + A 3 = ⃗ 0.
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 each constructed as follows:

1. Sample B/3 random vectors A 1 1 , . . . , A B/3 1 sampled uniformly at random over the sphere 1/m • S b-1 . 2. For each i ∈ [B/3], pick a random vector A j 2 sampled uniformly at random over the sphere 1/m • S b-1 with the condition that ⟨A j 1 |A j 2 ⟩ = -1 2m .

3. For each i ∈ [B/3], let A j 3 be the unique point on the sphere 1/m • S b-1 st.

A j 1 + A j 2 + A j 3 = ⃗ 0. The code C is then the set of points {A 1 1 , A 1 2 , A 1 3 , . . . , A B/3 1 , A B/3 2 , A B/3 3 }. Notice that A j 3 = -(A j 1 + A j 2 ) is of the correct norm 1 √ m . Indeed, ∥A j 3 ∥ 2 = ∥ -(A j 1 + A j 2 )∥ 2 = ∥A j 1 ∥ 2 + ∥A j 2 ∥ 2 + 2⟨A j 2 |A j 1 ⟩ = 2 m - 2 2m = 1 m .
We can generalize this construction for any constant k to get a k-RPC of codewords

{A j i } i∈[k],j∈[B/3] such that ∀A 1 ∈ C i , ∃A 2 , . . . A k ∈ C i st. k i=1 A i = ⃗ 0. 1. Sample B/k random vectors A 1 1 , . . . , A B/k 1
sampled uniformly at random over the sphere 1/m • S b-1 . 2. For each j ∈ [B/k], pick a random vector A j 2 sampled uniformly at random over the sphere 1/m • S b-1 with the condition that

⟨A j 1 |A j 2 ⟩ = -1 (k-1)m . Then, for i ∈ [|2, k -1|], pick random vectors A j i such that for each previous i ′ ∈ [i], ⟨A j i |A j i ′ ⟩ = -1 (k-1)m . 3. For each j ∈ [B/k], let A j k be the unique point on the sphere 1/m • S b-1 such that k i=1 A j i = ⃗ 0. The code C is then the set of points {A j i } i∈[k],j∈[B/3] .
As before, we can check that

A j k = - k-1 j=1 A j i is of the correct norm 1 √ m : ∥A j k ∥ 2 = k-1 j=1 ∥A j i ∥ 2 + k-1 i=1 k-1 i ′ =1 i ′ ̸ =i ⟨A j i |A j i ′ ⟩ = k -1 m + (k -1)(k -2) • -1 (k -1)m = k -1 m - k -2 m = 1 m .
For each j ∈ [B/k], we actually take ⟨A j i |A j i ′ ⟩ = -1/(k-1) for i ̸ = i ′ , because this balanced configuration optimizes the number of k-tuples whose vectors are respectively close to the centers A j i (See Proposition 5). Proposition 8. Let C be a random product code with triangles of parameters [d, m, B] with m = log(d) and B m = N O(1) . For any ⃗ x ∈ S d-1 and angle α, one can compute

H ⃗ x,α ∩ C in time N o(1) • |H ⃗ x,α ∩ C|.
Proof. The decoding algorithm of Proposition 7 presented in [START_REF] Becker | New directions in nearest neighbor searching with applications to lattice sieving[END_REF] uses only the product structure of the code and not how the codes C 1 , . . . , C m are constructed. The same algorithm will therefore also efficiently decode random product codes with triangles.

Definition 7 (Tuple-filter). Let C be a k-RPC with codewords

(A j i ) for i ∈ [k] and j ∈ [|C| /k] such that ∀j ∈ [|C|/k], k i=1 A j i = ⃗ 0. Given angle α, we call a tuple-filter (f α,A j 1 , . . . , f α,A j k
), with f α,A j i filters (see Definition 6).

Residual vectors in filter.

Proposition 9 ([HKL18], Lemma 3). We are given vectors i.i.d. uniformly random over S d-1 and a filter of center A and angle α. Then the vectors of angle at most α with A are i.i.d. uniformly random over the border of the filter. Their residual vectors are i.i.d. uniformly random over the (d-1)-dimensional sphere {⃗ y ∈ R d : ∥⃗ y∥ = 1, θ(⃗ y, A i ) = α}.

Then for a random ⃗ x ∈ S d-1 of angle α with a center of filter A, we can write for some ⃗ y ⊥ A, ⃗ x = cos(α)A + sin(α)⃗ y.

We call ⃗ y the residual vector of ⃗ x on the filter of center A and angle α.

We are given a list L of lattice vectors assumed to be i.i.d. uniformly random over S d-1 . We choose an angle α and sample a k-RPC C having 1/V(α) codewords. Going through the ⃗ x's in the list L, we decode ⃗ x to its nearest unique codeword A ∈ C. This step, called prefiltering, separates L into disjoint sublists, each one of size N • V(α). We focus on only one chosen tuple of filters of centers A 1 , . . . , A k respectively associated to the lists L 1 , . . . , L k . By Proposition 9, with high probability the angle between any ⃗ x ∈ L i and A i is α.

While filling the list L i with the ⃗ x, we fill in parallel a list R i with their residual vectors ⃗ y in the filter of center A i . Note that the points in L i are i.i.d. uniformly random over the (d-1)-dimensional sphere {⃗ y ∈ R d : ∥⃗ y∥ = 1, θ(⃗ y, A i ) = α}. See Figure 4 for illustration.

× A1 • A2 • A3 • × × × ⃗ x1 ⃗ y 1 ⃗ x2 ⃗ y 2 ⃗ x3 ⃗ y 3 Fig. 4: List vectors ⃗ x i ∈ L i in their filters of centers A i and their respective residual vectors ⃗ y i ∈ R i , where for i ̸ = j, ⟨A i |A j ⟩ = -1 2 .
Proposition 10. Using the above notations for the lists L i 's and

R i 's, a k- tuple ⃗ x 1 , . . . , ⃗ x k ∈ L 1 × • • • × L k is reducing iff. their residual vectors ⃗ y 1 , . . . , ⃗ y k ∈ R 1 × • • • × R k satisfy 1⩽i<j⩽k ⟨⃗ y i |⃗ y j ⟩ ⩽ 1 -k cos 2 (α) 2 sin 2 (α) := I k (α). (2)
Proof. By Proposition 9, we can consider that for i ̸ = j, ⟨A i |⃗ y j ⟩ = 0. And for i ̸ = j, ⃗ x i ∈ L i and ⃗ x j ∈ L j , we obtain:

⟨⃗ x i |⃗ x j ⟩ = cos 2 (α)⟨A i |A j ⟩ + sin 2 (α)⟨⃗ y i |⃗ y j ⟩.
Then we have

k i=1 ⃗ x i 2 = k i=1 sin(α)⃗ y i 2 = k sin 2 (α) + 2 sin 2 (α)   1⩽i<j⩽k ⟨⃗ y i |⃗ y j ⟩   . (3)
In the case the tuple (⃗ x 1 , . . . , ⃗ x k ) is reducing, we have

k i=1 ⃗ x i 2
⩽ 1, hence the wanted result. Notice also that we can translate the norm condition

k i=1 ⃗ x i 2 ⩽ 1 directly into a norm condition of the residual vectors k i=1 ⃗ y i 2 ⩽ 1 sin 2 (α) .
Lemma 1. Let be a configuration C ∈ R k×k and an angle α. If a k-tuple ⃗ x 1 , . . . , ⃗ x k satisfies C then their residual vectors ⃗ y 1 , . . . , ⃗ y k on a filter of angle α satisfies the configuration C ′ (α) with for i ̸ = j,

C ′ i,j (α) = - 1 sin 2 (α) C i,j + cos 2 (α) k -1
Proof. As written in the previous proof, for i ̸ = j we have ⟨⃗

x i |⃗ x j ⟩ = cos 2 (α)⟨A i |A j ⟩+ sin 2 (α)⟨⃗ y i |⃗ y j ⟩.
The configuration C gives constraints over the ⃗ x i 's, and C ′ (α) over the ⃗ y i 's ; and ⟨A i |A j ⟩ is fixed at -1/(k -1).

If we consider a balanced configuration C for the ⃗ x i 's, then we have for i ̸ = j, C i,j = -1/k all equal. For residual vectors on a filter of angle α, this also implies C ′ i,j (α) all equal for i ̸ = j. There are C ′ i,j at number

k-1 i=1 i = k • (k -1)/2. Thus for i ̸ = j we will have C ′ i,j (α) = 2 k•(k-1) • I k (α)
, with I k (α) as defined in Proposition 10.

Framework

The idea behind the framework of our sieving algorithms is the following:

1. Prefilter the list vectors, 2. Search all reduced tuples within each filter, 3. Repeat steps 1. and 2. until all the reduced points are found.

Parameters. The algorithm takes into its input an angle α, and a configuration C ∈ R k×k that defines constraints over the lattice vectors. We will discuss later how to choose them optimally. From α and C, we can compute the configuration C ′ (α) over the residual vectors on filters of angle α using Lemma 1. From C, we also know the number of vectors we require to achieve the sieve step, which gives by Proposition 5 the minimum memory requirement |L| = O(det(C) -d 2(k-1) ).

Algorithm 3 Framework for our new k-sieves

Require: List L of lattice vectors of norm at most R ; reducing factor γ < 1. Parameters: k ∈ N ; angle α ∈ (0, π/2] ; target configuration C. Ensure: List Lout of lattice vectors of norm at most γR.

Lout = ∅ while |Lout| < |L| do ▷ NbRep α,C repeats Sample a k-RPC code C having k • 1/V(α) codewords L j i = ∅ for i ∈ [k], j ∈ [|C|/k] for each ⃗ x ∈ L do A j i ← Decode(⃗ x, C) ▷ Algorithm from Proposition 7. ⃗ y ← 1/ sin(α) • ⃗ x -cos(α)A j i ▷ Residual vector of ⃗ x in the filter of center A j i L j i ← L j i ∪ {⃗ x} ; R j i ← R j i ∪ {⃗ y} for each tuple-filter numbered j ∈ [|C|/k] do Sol ⃗ y ← FindAllSolutionsWithinFilter (R j i )i, C ′ (α) ▷ Find all (⃗ y i )i ∈ R j 1 × • • • × R j k satisfying C ′ (α) Sol Σ⃗ x ← k i=1 ⃗ xi : (⃗ y i )i ∈ Sol ⃗ y ▷ ⃗ xi ∈ L j i and ⃗ y i ∈ R j i share

the same index in their respective lists

Lout ← Lout ∪ Sol Σ⃗ x return Lout 1. Prefiltering. We start by sampling a k-RPC C (Defined in Part 3.1) of size k • 1/V(α). Its codewords are denoted (A j i ) i,j for i ∈ [k] and j ∈ [|C|/k] (we suppose these values are integers by simplicity). For a fixed j ∈ [|C|/k] and for

i 1 ̸ = i 2 ∈ [k] we have ⟨A j i1 |A j i2 ⟩ = -1 k-1 , that implies k i=1 A j i = ⃗ 0.
Once the code is sampled, we can start the so-called prefiltering step. For each vector ⃗ x ∈ L, we efficiently compute its nearest codeword in C using the algorithm from Proposition 8. If it returns center A j i , then we add ⃗ x to its associated list L j i . We also compute ⃗ x's residual vector ⃗ y = 1/ sin(α) • ⃗ xcos(α)A j i (by Proposition 9) and we add it to list R j i . Given a residual vector in R j i , we will be able to recover its corresponding vector in L j i by just looking at the same index.

There are tuple-filters (

A j i ) i∈[k] at number NbFilters := |C|/k = O 1 V(α) . ( 4
)
As we compute the nearest filter in amortized time O(1) for each vector in L, the prefiltering step takes times |L|.

2. Find all solutions within a tuple-filter. We started with a list L and we wanted to solve a configuration problem, and after the prefiltering step, we can consider easier instances of the configuration problem on the sublists of L. The subroutine FindAllSolutionsWithinFilter solves one of these instances at a time, and we run it over each of the 1/V(α) tuple-filters.

Let's fix some j ∈ [|C|/k] and consider the instance of configuration problem on the k lists (R j i ) i with configuration C ′ (α). The subroutine then has to find all the k-tuples within R j 1 × • • • × R j k that satisfies the configuration C ′ (α). As we focus on only one filter at a time, in the following we will no longer write the j in exponent to lighten the notations.

The number of solutions the subroutine has to return is given by the following lemma.

Lemma 2. With the same notations as before and for fixed j ∈ [|C|/k], the expected number of tuples in the tuple-filter associated with the lists

R 1 ו • •×R k satisfying configuration C ′ (α) is on average |Sol f | = O |R 1 | k • det(C ′ (α)) d/2 = O |L| k V(α) k • det (C ′ (α)) d/2 .
Proof. There are Any subroutine with these inputs and outputs may suit the framework. For example, in the case k = 2, [CL21] describes a 2-sieve under this framework, where the subroutine uses quantum random walks to find the reducing pairs of vectors. We denote the time complexity of the subroutine FindAllSolution-sWithinFilter with parameters α and C by T (FAS C ′ (α) ).

|R 1 | k tuples in R 1 × ... ×

Number of repeats.

After searching all the solutions within every tuple-filters, we expect to find the following number of solutions:

|Sol all | = |L| k • det(C) d/2 .
(5)

To complete the sieve step, we require to find |L| reduced lattice vectors. Thus steps 1. and 2. have to be repeated until enough solutions have been found. The missed solutions are the ones such that a part of the solution is in one tuple-filter and the rest is in another. By doing a new prefiltering, it changes the partitions of the sphere, and this allows to find some of these missing solutions.

Lemma 3. The number of repetitions in the while loop is

N bRep α,C = O max 1, |Sol all | |Sol f | • N bF ilters = O   max    1, |L 1 | k det(C) d/2 |L 1 | k V k (α) det (C ′ (α)) d/2 • 1 V(α)      = O max 1, det(C) d/2 V k-1 (α) det (C ′ (α)) d/2
.

The overall time complexity of an algorithm based on this framework is given in the following theorem.

Theorem 2. Let α ∈ (0, π/2] be an angle and a configuration C ∈ R k×k , and C ′ (α) the configuration on the residual vectors (See Lemma 1). Given an algorithm that solves the configuration problem C ′ (α) for k lists in time T (FAS C ′ (α) ), Algorithm 3 solves SVP in time

T (k-sieve) := NbRep α,C • |L| + NbFilters α • T (FAS C ′ (α) )
where NbRep α,C is given by Lemma 3 and

NbFilters α = O( 1 V(α)
) by Equation 4.

The above theorem is the main technical contribution of our work. The main novelty is the angle α which can be freely chosen. Taking an angle α = π/2 means that we do not perform any tailored LSF.

Optimization of the parameters. So the C i,j 's are parameters to optimize to get the minimal overall time of the k-sieve, and they obey to the constraints on memory and reduceness of the tuples. We also require that the inner algorithm for solving the configuration problem with C ′ (α) uses at most memory M . There is as well the prefiltering angle α ∈ (0, π/2] that has to be optimized. In the next sections, we will present algorithms that fit in the framework 3 and for each one we will specify the optimal values for C and α we have obtained by numerical optimization. The code is available on https://github.com/johanna-loyer/ 3-4-sieve.

Classical sieving

We present here our 3-sieve and 4-sieve classical algorithms. In both cases, we use Theorem 2 so the only thing to explicit is the inner algorithm running in time T (FAS C ′ (α) ) as well as the parameters C and α. Actually, in both cases, the inner algorithm will use a classical 2-sieve algorithm so we first give formulas for the configuration problem with k = 2.

Classical 2-sieve

We present here the best-known algorithm for classical 2-sieve. While these are known results, we will need this analysis for our 3-sieve and 4-sieve algorithms. We can actually derive the best-known algorithms (in terms of asymptotic time and memory) from our framework.

Proposition 11. Take k = 2, lists L 1 , L 2 of random points of norm 1 with

|L 1 | = |L 2 |, a target configuration C = 1 C 12 C 12 1 . Let α st. V(α) = 1 |L1| . 1. Construct L 12 = {(⃗ x 1 , ⃗ x 2 ) ∈ L 1 × L 2 : ⟨⃗ x 1 |⃗ x 2 ⟩ ≤ C 12 } and L 13 = {(⃗ x 1 , ⃗ x 3 ) ∈ L 1 × L 3 : ⟨⃗ x 1 |⃗ x 3 ⟩ ≤ C 23 }. 2. For each ⃗ x 1 ∈ L 1 , let L 12 (⃗ x 1 ) = {⃗ x 2 ∈ L 2 : (⃗ x 1 , ⃗ x 2 ) ∈ L 12 } and L 13 (⃗ x 1 ) = {⃗ x 3 ∈ L 3 : (⃗ x 1 , ⃗ x 3 ) ∈ L 13 }. 3. For each ⃗ x 1 ∈ L 1 , compute L 123 (⃗ x 1 ) = {(⃗ x 2 , ⃗ x 3 ) ∈ L 12 (⃗ x 1 ) × L 13 (⃗ x 1 ) : ⟨⃗ x 2 |⃗ x 3 ⟩ ≤ C 23 }. For each ⃗ x 1 ∈ L 1 , triples (⃗ x 1 , ⃗ x 2 , ⃗ x 3 ) are solution when (⃗ x 2 , ⃗ x 3 ) ∈ L 123 (⃗ x 1 ).
Now that we defined all intermediate lists, we can write the algorithm we use for solving the inner configuration problem with k = 3. Construction of the lists L 12 and L 13 . As a direct consequence of Proposition 11, we have: Lemma 4. Let T 12 (resp. T 13 ) be the time to compute L 12 (resp. L 13 ). Let α such that |L 1 | = 1/V(α). We have

T 12 = O |L 1 | 2 1 -C 2 12 d/2 (1 -C ′ 12 (α) 2 ) d/2 T 13 = O |L 1 | 2 1 -C 2 13 d/2 (1 -C ′ 13 (α) 2 ) d/2
Construction of the lists L 23 (⃗ x 1 ). For a fixed ⃗ x 1 , notice that the lists L 2 (⃗ x 1 ) and L 3 (⃗ x 1 ) do not contain points uniformly distributed on the sphere since they have an inner-product constraint with ⃗ x 1 so we cannot apply Proposition 11 directly. Fix ⃗ x 1 ∈ L 1 and let ⃗ x 2 ∈ L 2 and ⃗ x 3 ∈ L 3 . For simplicity of calculations, we consider the case where ⟨⃗

x 1 |⃗ x 2 ⟩ = C 12 , ⟨⃗ x 1 |⃗ x 3 ⟩ = C 13 and ⟨⃗ x 2 |⃗ x 3 ⟩ = C 23 .
This approximation is justified from Heuristic 1. So we write

⃗ x 2 = C 12 ⃗ x 1 + 1 -C 2 12 ⃗ y 2 ; ⃗ x 3 = C 13 ⃗ x 1 + 1 -C 2 13 ⃗ y 3 (7)
where ⃗ y 2 , ⃗ y 3 are orthogonal to ⃗ x 1 . Also, if ⃗ x 2 (resp. ⃗ x 3 ) is a random vector satisfying ⟨⃗

x 1 |⃗ x 2 ⟩ = C 12 (resp. ⟨⃗ x 1 |⃗ x 3 ⟩ = C 13 ) then ⃗ y 2 (resp. ⃗ y 3 ) is a random unit vectors. Let Y 23 := ⟨⃗ y 2 |⃗ y 3 ⟩. We have ⟨⃗ x 2 |⃗ x 3 ⟩ = C 12 C 13 + 1 -C 2 12 1 -C 2 13 Y 23
which implies

Y 23 = C 23 -C 12 C 13 1 -C 2 12 1 -C 2 13 .
We can now use Proposition 11 to give the running time of computing R 23 (⃗ x 1 ), which gives the running time

T 23 (⃗ x 1 ) of computing L 23 (⃗ x 3 ). Let Y = 1 Y 23 Y 23 1 and let α" st. V(α ′ ) = 1 |L2(⃗ x1)| . We have T 23 (⃗ x 1 ) = O (N bRep α ′ ,Y • |L 2 (⃗ x 1 )|) .
Now, let T 23 be the running of computing all the lists L 23 (⃗ x 1 ) since the number of ⃗ x 1 is |L 1 |, we have

T 23 = |L 1 |T 23 (⃗ x 1 ) = O (|L 1 |N bRep α ′ ,Y • |L 2 (⃗ x 1 )|) (8) = |L 1 ||L 2 (⃗ x 1 )| 2 1 -Y 2 23 d/2 (1 -Y ′ 23 (α ′ ) 2 ) d/2 (9)
with Y ′ 23 (α) = 1 sin 2 (α) Y 23 + cos 2 (α ′ ) . Putting everything together, we have the following Proposition 12. Let |L 1 | a list size and C a 3 × 3 configuration matrix with negative non-diagonal entries.

Let |L 2 (⃗ x 1 )| = |L 1 |(1-C 2 12 ) d/2 . Let α ′ st. V(α ′ ) = 1 |L2(⃗ x1)| . Algorithm 4 solves FAS c 3 (|L 1 |, C) in time T 12 + T 13 + T 23 with T 12 = T 23 = O |L 1 | 2 (1 -C 2 12 ) d/2 T 123 = |L 1 ||L 2 (⃗ x 1 )| 2 1 -Y 2 23 d/2 (1 -Y ′ 23 (α ′ ) 2 ) d/2
where

Y 23 = 1 1 -C 2 12 1 -C 2 13 • (C 23 + C 12 C 13 ) Y ′ 23 (α) = 1 sin 2 (α) Y 23 + cos 2 (α ′ ) . Let |L 12 | = |L 1 | 2 1 -C 2 12 d/2 . This algorithm uses memory M = max{|L 1 |, |L 12 |}.
Complexity of the classical 3-sieve. The above was the analysis of the classical 3-sieve after the first filtering. We now apply Theorem 2 with k = 3 in order to obtain the running of our classical 3-sieve algorithm within our framework.

Theorem 3. There is a classical algorithm with parameter α that solves the 3-sieve problem for a configuration C and lists of size |L| that runs in time T and that uses memory M with

T = O NbRep α,C • |L| + 1 V(α) • T (FAS c 3 (|L 1 |, C ′ (α))) ,
and

M = max{|L|, |L 1 |, |L 12 |, |L 123 |}.
where Proposition 13. There exists a classical algorithm for SV P using 3-sieve that runs in time 2 0.338d+o(d) and uses memory 2 0.1887d+o(d) .

|L 1 | = |L|•V(α),
Proof. Take the above proposition with a configuration matrix C st.

C 12 = C 13 = C 23 = -1 3 , α = 1.2954rad and |L| = 2 0.1887d . We apply Proposition 3; We write C ′ 12 (α) = C ′ 13 (α) = C ′ 23 (α) ≈ -0.32 and |L 1 | = |L| • V(α) = 2 0.133d . We have, (omitting o(d) factors in the exponent) N bRep α,C = 2 0.070d ; 1 V(α) = 2 0.055d ; T (FAS c 3 (|L 1 |, C ′ )) = 2 0.213d
Putting everything together, we indeed have a running time of 2 0.070d • 2 0.055d • 2 0.213d = 2 0.338d . The memory

M = max{|L|, |L out |, |L int |} where L int is the intermediate list used in FAS c 3 (|L 1 |, C ′ (α)).
We have

|L int | = |L 1 | 2 1 -C ′ 12 (α) 2 d/2 = 2 0.1887d .
This implies that the memory used is M = 2 0.1887d .

Space-time trade-off. We also extend this algorithm where we fix the available memory to something more than the minimal memory 2 0.1887d . We present here a list of points that we obtain, showing the general behaviour of our algorithm: Table 2: Time complexity of our classical 3-sieving algorithm for a fixed memory constraint. α is the optimal angle used in the first prefiltering. Also see Figure 2a for a plot corresponding to this algorithm.

Classical 4-sieve

We now consider the case k = 4. For our inner algorithms, we start with 4 lists L 1 , L 2 , L 3 , L 4 . There are actually several strategies of merging the lists. Here we choose to perform the following merges:

1. Construct L 12 = {(⃗ x 1 , ⃗ x 2 ) ∈ L 1 × L 2 : ⟨⃗ x 1 |⃗ x 2 ⟩ ≤ C 12 } and L 34 = {(⃗ x 3 , ⃗ x 4 ) ∈ L 3 × L 4 : ⟨⃗ x 3 |⃗ x 4 ⟩ ≤ C 34 }. 2. Construct L 1234 = {((⃗ x 1 , ⃗ x 2 ), (⃗ x 3 , ⃗ x 4 )) ∈ L 12 ×L 34 : (⃗ x 1 , ⃗ x 2 , ⃗ x 3 , ⃗ x 4 ) satisfies configuration C}.
Using these lists, we consider the following algorithm: We then use the above algorithm as the FindAllSolutionsWithinFilter subroutine in Algorithm 3 to describe our entire algorithm for 4-sieve. The algorithm presented here is usually inefficient in memory because the lists L 12 and L 13 are large. However, thanks to our initial α-filtering, we start from smaller lists L 1 , L 2 , L 3 , L 4 so the intermediate lists will be small as well.

Complexity of Algorithm 5. Lemma 5. Let T 12 be the time to compute L 12 (which is also the time to compute L 34 by symmetry). Let α st. V(α) = 1 |L1| . Then

T 12 = O |L 1 | 2 1 -C 2 12 d/2 (1 -C ′ 12 (α) 2 ) d/2
This comes directly from the analysis of our simplified 2-sieve algorithm. The size of the intermediate lists L 12 and L 34 is then

|L 12 | = |L 1 | 2 • 1 -C 2 12 d/2 (10)
We now look at the time to compute L 1234 . Elements of L 12 are of squared norm R 2 = 2 + 2C 12 , using ∥⃗

x 1 + ⃗ x 2 ∥ 2 = ∥⃗ x 1 ∥ 2 + ∥⃗ x 2 ∥ 2 + 2⟨⃗ x 1 |⃗ x 2 ⟩. We write

Quantum sieving

We now study how our framework impacts quantum algorithms. In the quantum setting, Theorem 2 also applied and once again, we only need to describe the running time and amount of memory used for the inner configuration problem.

The input lists L i are stored classically and are assumed to be quantumly accessible, i.e. for any given list L, we can efficiently construct the uniform superposition over all its elements |ψ L

⟩ := 1 √ |L| ℓ |ℓ⟩ |L[ℓ]⟩.
In the following, we will not necessarily write the first register for simplicity2 .

Quantum 3-sieve

For the FindAllSolutionsWithinFilter quantum subroutine in case k = 3, we start with classical lists L 1 , L 2 , L 3 that are quantumly accessible. The algorithm outputs a list containing all triples in L 1 × L 2 × L 3 satisfying a given target configuration C.

To find one solution, our algorithm constructs a uniform quantum superposition over all triples, and then applies two Grover's algorithms in order to get a "filtered" quantum superposition. This whole process is then repeated inside an amplitude amplification to get a superposition over the solutions, that we measure, and we repeat this whole process until we have found all the solutions.

As a reminder (See Proposition 6), given a configuration C, we use the following notation: for i, j ∈ [k], i ̸ = j and ⃗ y j ∈ L j , L i (⃗ y j ) := {⃗ y i ∈ L i : ⟨⃗ y i |⃗ y j ⟩ ≤ C i,j }.

⟩ ψ L 2 (⃗ y 1 ) ψ L 3 (⃗ y 1 )
Apply Amplitude Amplification to get state |ψ Sol ⟩, the uniform superposition of all solutions Take a measurement and get some (⃗ y 1 , ⃗ y 2 , ⃗ y 3 ) if (⃗ y 1 , ⃗ y 2 , ⃗ y 3 ) satisfies configuration C then add it to Lout return Lout Complexity of Algorithm 6. We first analyse the complexity to find one solution during one single iteration from the while-loop.

Initialization. We assume that lists L 1 , L 2 and L 3 of i.i.d. random points are classically stored and quantumly accessible. So the state |ψ L1 ⟩ |ψ L2 ⟩ |ψ L3 ⟩ can be constructed efficiently.

Grover on the second register. The algorithm then applies Grover's algorithm on the second register such that the two first registers become

|ψ L1 ⟩ ψ L2(⃗ y 1 ) = 1 |L 1 | 1 |L 2 (⃗ y 1 )| ⃗ y 1 ∈L1 ⃗ y 2 ∈L2(⃗ y 1 ) |⃗ y 1 ⟩ |⃗ y 2 ⟩ .
It only keeps in the quantum superposition the elements ⃗ y 2 ∈ L 2 such that ⟨⃗ y 1 |⃗ y 2 ⟩ ≤ C 12 for each superposed ⃗ y 1 from the first register. So the state ends up with a quantum superposition of all pairs in L 1 × L 2 eligible to form the beginning of a triple-solution. This application of Grover's algorithm takes time

T 2 = |L2| |L2(⃗ y 1 )| = (1 -C 12 ) -d/4
by Proposition 6.

Grover on the third register. Similarly, we also apply Grover's algorithm on the third register to get the state

|ψ L1 ⟩ ψ L2(⃗ y 1 ) ψ L3(⃗ y 1 ) equal to 1 |L 1 | 1 |L 2 (⃗ y 1 )| 1 |L 3 (⃗ y 1 )| ⃗ y 1 ∈L1 ⃗ y 2 ∈L2(⃗ y 1 ) ⃗ y 3 ∈L3(⃗ y 1 ) |⃗ y 1 ⟩ |⃗ y 2 ⟩ |⃗ y 3 ⟩ in time T 3 = |L3| |L3(⃗ y 1 )| = (1 -C 13 ) -d/4
. The sizes |L 2 (⃗ y 1 )| and |L 3 (⃗ y 1 )| do not depend on the choice of ⃗ y 1 , that is why we can write their corresponding normalizing factors before the sum over the ⃗ y 1 's. Amplitude amplification. The goal is now to construct a uniform quantum superposition over all elements of the set of solutions Sol := {(⃗ y 1 , ⃗ y 2 , ⃗ y 3 ) ∈ L 1 × L 2 × L 3 satisfying C}, by applying a quantum amplitude amplification. Let A be unitary that maps |0⟩ |0⟩ |0⟩ to the state |ψ L1 ⟩ ψ L2(⃗ y 1 ) ψ L3(⃗ y 1 ) constructed so far.

Lemma 8. The operation

A : |0⟩ |0⟩ |0⟩ → |ψ L1 ⟩ ψ L2(⃗ y 1 ) ψ L3(⃗ y 1
) is repeated T AA times inside the amplitude amplification to construct state |ψ Sol ⟩ (with probability 1 -o(1)), where

T AA = O |L 1 |/|Sol| • |L 2 (⃗ y 1 )| |L 3 (⃗ y 1 )| = O |L 3 i |/|Sol| • (1 -C 12 ) d/4 (1 -C 13 ) d/4 .
Proof. Performing a measurement of state |ψ L1 ⟩ ψ L2(⃗ y 1 ) ψ L3(⃗ y 1 ) gives a triplet solution (⃗ y 1 , ⃗ y 2 , ⃗ y 3 ) with some probability p, we are going to specify. There are |L 1 | possible ⃗ y 1 and |Sol| "good" ones belonging to a solution, so the probability of measuring a good ⃗ y 1 is |Sol|/|L 1 |. Then given a ⃗ y 1 , a pair (⃗ y 2 , ⃗ y 3 ) ∈ L 2 (⃗ y 1 ) × L 3 (⃗ y 1 ) forms the solution together with ⃗ y 1 with probability

1 |L2(⃗ y 1 )| 1 |L3(⃗ y 1 )| .
Finally, the probability to measure a solution is thus p

= |Sol|/|L 1 |• 1 L2(⃗ y 1 ) 1 L3(⃗ y 1 )
. By Theorem 3, the number of iterations of amplitude amplification is O 1/ √ p , hence the top line. The bottom line is obtained by expressing the sizes of L 2 (⃗ y 1 ) and L 3 (⃗ y 1 ) using Proposition 6.

Subroutine complexity.

Proposition 14 (FindAllSolutionsWithinFilter quantum 3-sieve). Let |L 1 | a list size and C a 3 × 3 configuration matrix with negative non-diagonal entries. Algorithm 6 solves FAS q

3 (|L 1 |, C) in time |Sol| • (T 2 + T 3 ) • T AA where |Sol| = |L 1 | 3 • det(C) d/2 T 2 = (1 -C 12 ) -d/4 ; T 3 = (1 -C 13 ) -d/4 T AA = O |L 3 i |/|Sol| • (1 -C 12 ) d/4 (1 -C 13 ) d/4
After simplification, the time complexity of Algorithm 6 can be written

T (FAS q 3 (|L 1 |, C)) = |L i | 3 • |Sol| • (1 -C 2 12 ) d/2 + (1 -C 2 13 ) d/2 .
This algorithm uses classical memory |L 1 | and quantum memory poly(d) qubits.

Complexity of the quantum 3-sieve. The above was the analysis of the algorithm we use as the subroutine FindAllSolutionsWithinFilter in Algorithm 3 for quantum 3-sieve. The lists given in input of Algorithm 6 are then the lists of residual vectors R 1 , R 2 , R 3 , which are of size

|R 1 | = |L 1 | = |L| • V(α)
; and it return residual vectors that satisfy the target configuration C ′ (α). Using Theorem 2 in the case k = 3, we recover the overall time complexity of our quantum 3-sieve algorithm.

Theorem 5. There is a quantum algorithm with parameter α that solves the 3-sieve problem for a configuration C ∈ R 3×3 and lists of size |L|, that runs in time

T = O NbRep α,C |L| + 1 V(α) • T (FAS q 3 (|L 1 |, C ′ (α)))
where

|L 1 | = |L| • V(α) and T (FAS q 3 (|L 1 |, C ′ (α)))
given by Proposition 14. This algorithm uses quantum-accessible classical memory M = |L| and quantum memory poly(d).

Minimal memory parameters.

Proposition 15. There is a quantum algorithm that solves SVP in dimension d using 3-sieve that runs in time T = 2 0.3098d+o(d) , quantum-accessible classical memory M = 2 0.1887d+o(d) and poly(d) quantum memory. Putting everything together, we indeed have a running time of 2 0.1055d • 2 0.0832d • 2 0.1210d = 2 0.3098d . Space-time trade-offs. We also extend this algorithm where we fix the available memory to something more than the minimal memory 2 0.1887d . Table 4: Time complexity of our quantum 3-sieving algorithm for a fixed memory constraint. α is the optimal angle used in the prefiltering. Also see Figure 3a for a plot corresponding to this algorithm.

Quantum 4-sieve

This algorithm and its analysis are very similar to Algorithm 6. As previously, we first analyse the complexity to find one solution during one single iteration from the while-loop.

Complexity of Algorithm 7.

Initialization. Lists L i for i = 1, 2, 3, 4 are assumed stored classically and quantumly accessible, so we can construct the state |ψ L1 ⟩ |ψ L2 ⟩ |ψ L3 ⟩ |ψ L4 ⟩.

Grover over the second register. The algorithm applies Grover's algorithm over the second register such that the two first registers become Measurement gives a 4-tuple (⃗ y 1 , ⃗ y 2 , ⃗ y 3 , ⃗ y 4 ) solution to the configuration problem. We need to repeat this whole process until we find all the solutions at number |Sol|.

|ψ L1 ⟩ ψ L2(⃗ y 1 ) = 1 |L 1 | 1 |L 2 (⃗ y 1 )| ⃗ y 1 ∈L1 ⃗ y 2 ∈L2(⃗ y 1 ) |⃗ y 1 ⟩ |⃗ y 2 ⟩ ,
Notice that the same operations are performed over L 3 and over L 4 , which implies that an optimal configuration will necessarily respect the symmetry C 13 = C 14 and C 23 = C 24 .

In the end, this subroutine FindAllSolutionsWithinFilter runs in time

T (FAS q 4 ) = |Sol| • (T 2 + T 3 + T 4 ) • T AA ,
and this leads to the following theorem. .

  (a) Classical 3-sieve (Theorem 3). (b) Classical 4-sieve (Theorem 4).

Fig. 2 :

 2 Fig. 2: Time T = 2 td+o(d) for classical algorithms as a function of available memory 2 md+o(d) = 2 M .

  (a) Quantum 3-sieve (Theorem 5). (b) Quantum 4-sieve (Theorem 6).

Fig. 3 :

 3 Fig. 3: Time T = 2 td+o(d) for quantum 3 and 4-sieves algorithms as a function of available memory 2 md+o(d) = 2 M .

2. 2

 2 Lattice sieving Definition 1 (Lattice). Given a basis B = ( ⃗ b 1 , ... ⃗ b m ) ∈ R d of linearly independent vectors, the lattice generated by B is defined as L(B) = m i=1 z i ⃗ b i , z i ∈ Z . For simplicity, we work with lattices of full rank, i.e. d = m.

  I ⊂ [k], we denote by C[I] the |I| × |I| submatrix of C obtained by restricting C to the rows and columned whose indexes are in I. Definition 5 (Configuration problem). Let k ∈ N and ϵ > 0. Suppose we are given a target configuration C ∈ R k×k . Given lists L 1 , . . . , L k all of exponential (in d) size |L| whose elements are i.i.d. uniform from S d-1 , the configuration problem consists of finding a 1 -o(1) fraction of all solutions, where a solution is a

3. 1

 1 Locality Sensitive Filtering Random Product Code (RPC). We assume d = m • b, for m = O(polylog(d)) and a block size b. The vectors in R d will be identified with tuples of m vectors in R b . A random product code C of parameters [d, m, B] on subsets of R d and of size B m is defined as a code of the form

  More formally, we assume d = m • b, for m = O(polylog(d)) and a block size b. The vectors in R d will be identified with tuples of m vectors in R b . A random product code with triangles C of parameters [d, m, B] on subsets of R d and of size B m is defined as a code of the form

Algorithm 4

 4 FindAllSolutionsWithinFilter classical 3-sieve Require: lists L1, L2, L3 of vectors i.i.d. in S d-1 with |L1| = |L2| = |L3| ; target configuration C ∈ R 3×3 . Ensure: list Lout of all 3-tuples in L1 × L2 × L3 satisfying configuration C. Lout := ∅. construct L12 and L13 using a 2-sieve algorithm with angle parameter α ′ , from which you can recover lists L12(⃗ x1) and L13(⃗ x1) for each ⃗ x1 ∈ L1: compute L123(⃗ x1) using a 2-sieve algorithm with angle parameter α ′′ for each (⃗ x2, ⃗ x3) ∈ L123(⃗ x1), do Lout := Lout ∪ {(⃗ x1, ⃗ x2, ⃗ x3)}. return Lout Complexity of Algorithm 4.

  |L 12 |, |L 123 | can be taken from Proposition 6 and FAS c 3 (|L 1 |, C) = T 12 + T 13 + T 123 where each T 12 , T 13 , T 123 can be taken from Proposition 12.

Algorithm 5

 5 FindAllSolutionsWithinFilter classical 4-sieveRequire: lists L1, L2, L3, L4 of vectors i.i.d. in S d-1 with |L1| = |L2| = |L3| = |L4| ; target configuration C ∈ R 4×4 with C12 = C34 and C13 = C14 = C23 = C24. Ensure: list Lout of all 4-tuples (⃗ x1, ⃗ x2, ⃗ x3, ⃗ x4) ∈ L1 × L2 × L3 × L4 satisfying configuration C.Construct L12 and L34 using our classical 2-sieve algorithm.Start from L12 and L34 and use our classical 2-sieve algorithm to compute L1234. return L1234.

Proof.

  We take a balanced configuration C with C 12 = C 13 = C 23 = -1/3, α = 1.2343rad and |L| = 2 0.1887d = M . We apply Proposition 5: We writeC ′ 12 (α) = C ′ 13 (α) = C ′ 23 (α) ≈ -0.31 and |L 1 | = |L| • V(α) = 2 0.1055d . We have NbRep α,C = 2 0.1055d ; 1 V(α) = 2 0.0832d ; T (FAS q 3 (|L 1 |, C ′ )) = 2 0.1210d .

log 2 (

 2 Memory)/d 0.1887 0.189 0.190 0.1907 log 2 (Time)/d 0.3098 0.3073 0.3056 0.3053 α (rad) 1.2346 1.2341 1.2336 1.2331

  y 1 )| = (1 -C 2 12 ) -d/4 . Amplitude amplification. We then want to construct a uniform quantum superposition over all elements of the set of solutions Sol := {(⃗ y 1 , ⃗ y 2 , ⃗ y 3 , ⃗ y 4 ) ∈ L 1 × L 2 × L 3 × L 4 satisfying C}, by applying a quantum amplitude amplification.Lemma 9. The operation |0⟩ |0⟩ |0⟩ |0⟩ → |ψ L1 ⟩ ψ L2(⃗ y 1 ) ψ L3(⃗ y 1 ,⃗ y 2 ) ψ L4(⃗ y 1 ,⃗ y 2 )is repeated T AA times inside the amplitude amplification to construct state |ψ Sol ⟩ (with probability 1 -o(1)), whereT AA = |L 1 | |Sol| |L 2 (⃗ y 1 )| |L 3 (⃗ y 1 , ⃗ y 2 )| |L 4 (⃗ y 1 , ⃗ y 2 notation C[I]with a set of indexes I was introduced in Definition 4.Proof. The reasoning is the same as for the proof of Lemma 8. Performing a measurement of state |ψ L1 ⟩ ψ L2(⃗ y 1 ) ψ L3(⃗ y 1 ,⃗ y 2 ) ψ L4(⃗ y 1 ,⃗ y 2 ) gives a 4-tuple solution (⃗ y 1 , ⃗ y 2 , ⃗ y 3 , ⃗ y 4 ) with some probability p, we are going to specify. The probability of measuring a good ⃗ y 1 is |Sol|/|L 1 |. Then given a ⃗ y 1 , a triple (⃗ y 2 , ⃗ y 3 , ⃗ y 4 ) forms the solution together with ⃗ y 1 with probability 1/(|L2 (⃗ y 1 )|• |L 3 (⃗ y 1 , ⃗ y 2 )|• |L 4 (⃗ y 1 , ⃗ y 2 )|).Finally, the probability of success to measure a solution is thus p= |Sol| |L1| • 1/ (|L 2 (⃗ y 1 )| • |L 3 (⃗ y 1 , ⃗ y 2 )| • |L 4 (⃗ y 1 , ⃗ y 2 )|). By Theorem 3, the number of iterations of amplitude amplification is O 1/ √ p , hence the top line. The bottom line is obtained by expressing the sizes of L 2 (⃗ y 1 ), L 3 (⃗ y 1 , ⃗ y 2 ) and L 4 (⃗ y 1 , ⃗ y 2 ) using Proposition 6.

Proposition 16 .

 16 Given lists L 1 , L 2 , L 3 , L 4 ⊂ S d-1 of same size |L i | with i.i.d.uniformly random vectors, and a configuration C ∈ R 4×4 with C 13 = C 14 and C 23 = C 24 , there exists an algorithm that finds all the |Sol| 4-tuples inL 1 × L 2 × L 3 × L 4 satisfying configuration C in time T (FAS q 4 ) = |L i | 2

  Algorithm 6 FindAllSolutionsWithinFilter quantum 3-sieve Require: lists L1, L2, L3 of vectors i.i.d. in S d-1 with |L1| = |L2| = |L3| ; a target configuration C ∈ R 3×3 . Ensure: list Lout containing all 3-triples in L1 × L2 × L3 satisfying configuration C. Lout := ∅ while |Lout| < |Sol| do Construct state |ψL 1 ⟩ |ψL 2 ⟩ |ψL 3 ⟩ Apply Grover on the second register to get state |ψL 1 ⟩ ψ L 2 (⃗ y 1 ) |ψL 3 ⟩ Apply Grover on the third register to get state |ψL 1

See https://www.latticechallenge.org/svp-challenge/

This simplification was already done in[START_REF] Kirshanova | Quantum Algorithms for the Approximate k-List Problem and their Application to Lattice Sieving[END_REF]. At no point do we use the fact that we do not have the first register, this is just for simplicity of notations.

Algorithm 3 with parameter α constructs a list L out of pairs of points (⃗ x 1 , ⃗ x 2 ) with (⃗ x 1 , ⃗ x 2 ) ∈ L 1 × L 2 st. ⟨⃗ x 1 |⃗ x 2 ⟩ ≤ C 12 , in time T using memory M st.

det (C ′ (α))

where recall that C ′ 12 (α) = 1 sin 2 (α) • C 12 + cos 2 (α) . Notice that |L out | corresponds asymptotically to all the pairs (⃗ x 1 , ⃗ x 2 ) ∈ L 1 × L 2 st. ⟨⃗ x 1 |⃗ x 2 ⟩ ≤ C 12 so we find here asymptotically all solutions.

Proof. We use Theorem 2 with k = 2 and some parameter α to get

Recall that here, FAS C ′ 12 (α) computes the running time of finding all solution pairs with inner product smaller than C ′ 12 (α) when starting with lists of size

We perform an exhaustive search on the pairs of points to find all solutions so

We take α st.

which allows us to conclude that

.

As a special case, we can take

which is the best-known algorithm asymptotically.

Classical 3-sieve

So we now consider the case of k = 3. Our inner algorithms will construct the following intermediate lists:

Proof. We write

|L12| . We have

, with Y ′ (α ′ ) = 1 sin 2 (α) T + cos 2 (α ′ ) . By combining the above 2 propositions, we have Theorem 4. Algorithm 5 runs in time T = 2T 12 + T 1234 where T 12 and T 1234 can be taken respectively from Lemma 5 and Lemma 7.

To conclude, we can plug this theorem again in Theorem 2 to get our results. Recall that we work with 4-tuples of residual vectors after an initial αfiltering so we look for 4-tuples of residual points (⃗ 3). This means we take r 0 = 1 sin(α) . Regarding memory requirements, we have that the memory M of our algorithm satisfies

This algorithm gives smooth time-memory trade-off to the points where the memory is 2 0.0275d and the time is 2 0.292d , corresponding precisely to the complexity of the 2-sieve algorithm (and indeed corresponds to the case where our 4-sieve algorithm performs independently two 2-sieve algorithms). When looking at the minimal memory setting, so M = 2 0.1724d , this algorithm performs poorly, as the time is 2 0.418d . However, when looking at intermediate memory requirements, there are some ranges when the algorithm performs quite well. For example, when taking M = 2 0.1887d , this algorithm performs better than the 3-sieve classical algorithm we presented before. We put below a list of values of interest. As in the previous case, the less memory we are allowed, the more it is interesting to perform a tailored prefiltering step. We put below a list of values and the corresponding angle α used in the prefiltering step.

Apply Amplitude Amplification to get state |ψ Sol ⟩, the uniform superposition of all solutions Take a measurement and get some (⃗ y 1 , ⃗ y 2 , ⃗ y 3 , ⃗ y 4 ) if (⃗ y 1 , ⃗ y 2 , ⃗ y 3 , ⃗ y 4 ) satisfies configuration C then add it to Lout return Lout Grover over the third register. Another Grover's algorithm is then performed over the third register |ψ L3 ⟩ such that it becomes the quantum superposition over all elements of L 3 (⃗ y 1 , ⃗ y 2 ), for ⃗ y 1 ∈ L 1 and ⃗ y 2 ∈ L 2 (⃗ y 1 ) being elements in quantum superposition in the two first registers.

The three first registers then become the state

Performing this Grover's algorithm takes time

. Note that these notations for partial configurations are given in Definition 4. So we can rewrite

. Grover over the fourth register. Analogously to what was done over the third register, we perform Grover's algorithm over the fourth one |ψ L4 ⟩.

.

Complexity of the quantum 4-sieve. The above was the analysis of the quantum 4-sieve after the prefiltering. We use this algorithm as the subroutine in our framework for k = 4. Using Theorem 2 in this case, we recover the overall time complexity of our quantum 4-sieve algorithm.

Theorem 6. There is a quantum algorithm with parameter α that solves the 3-sieve problem for a configuration C and lists of size |L| that runs in time T with

and uses quantum-accessible classical memory M = |L| and quantum memory poly(d), and where

given by Proposition 16.

Minimal memory parameters.

Proposition 17. There is a quantum algorithm that solves SVP in dimension d using 4-sieve that runs in time T = 2 0.3276d+o(d) using quantum-accessible classical memory M = 2 0.1724d+o(d) and quantum memory poly(d).

Proof. We take a balanced configuration C with C i,j = -1/4 for i ̸ = j, α ≈ 1.3131rad and |L| = 2 0.1724d = M . We apply Theorem 6: We write C ′ i,j ≈ -0.244

Putting everything together, we indeed have a running time of 2 0.1069d • 2 0.0484d • 2 0.1722d = 2 0.3276d .

Time-optimizing parameters.

Proposition 18. There exists an algorithm that solves SVP in dimension d in time T = 2 0.3120d+o(d) using quantum-accessible classical memory M = 2 0.1813d+o(d) and quantum memory poly(d).

Proof. We take a configuration C with C 12 ≈ -0. Putting everything together, we indeed have a running time of 2 0.1254d • 2 0.0554d • 2 0.1312d = 2 0.3120d . log 2 (Memory)/d 0.1724 0.175 0.180 0.1813 log 2 (Time)/d 0.3276 0.3153 0.3127 0.3120

Table 5: Time complexity of our quantum 4-sieving algorithm for a fixed memory constraint. For the prefiltering, we have an optimal α ≈ 1.3131rad. Also see Figure 3b for a plot corresponding to this algorithm.

Code used for our results. All our results have been obtained using SageMath and the code is available on https://github.com/johanna-loyer/3-4-sieve.