Koen De Boer

Léo Ducas

Alice Pellet-Mary

Benjamin Wesolowski

Random Self-reducibility of Ideal-SVP via Arakelov Random Walks

Fixing a number eld, the space of all ideal lattices, up to isometry, is naturally an abelian group, called the Arakelov class group. This fact, well known to number theorists, has so far not been explicitly used in the literature on lattice-based cryptography. Remarkably, the Arakelov class group is a combination of two groups that have already led to signicant cryptanalytic advances: the class group and the unit torus. In the present article, we show that the Arakelov class group has more to oer. We start with the development of a new versatile tool: we prove that, subject to the Riemann Hypothesis for Hecke Lfunctions, certain random walks on the Arakelov class group have a rapid mixing property. We then exploit this result to relate the average-case and the worst-case of the Shortest Vector Problem in ideal lattices. Our reduction appears particularly sharp: for Hermite-SVP in ideal lattices of certain cyclotomic number elds, it loses no more than a Õ( √ n) factor on the Hermite approximation factor. Furthermore, we suggest that this rapid-mixing theorem should nd other applications in cryptography and in algorithmic number theory.

Introduction

The task of nding short vectors in Euclidean lattices (a.k.a. the approximate Shortest Vector Problem) is a hard problem playing a central role in complexity theory. It is presumed to be hard even for quantum algorithms, and thanks to the average-case to worst-case reductions of Ajtai [START_REF] Ajtai | Generating hard instances of the short basis problem[END_REF] and Regev [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF], it has become the theoretical foundation for many kinds of cryptographic schemes. Furthermore, these problems appear to have resisted the quantum-cryptanalytic eorts so far; the overlying cryptosystems are therefore deemed quantum-safe, and for this reason are currently being considered for standardization.

Instantiations of these problems over ideal lattices have attracted particular attention, as they allow very ecient implementations. The Ring-SIS [START_REF] Micciancio | Generalized compact knapsacks, cyclic lattices, and ecient one-way functions[END_REF][START_REF] Lyubashevsky | Generalized compact knapsacks are collision resistant[END_REF][START_REF] Peikert | Ecient collision-resistant hashing from worst-case assumptions on cyclic lattices[END_REF] and Ring-LWE [START_REF] Stehlé | Ecient public key encryption based on ideal lattices[END_REF][START_REF] Lyubashevsky | On ideal lattices and learning with errors over rings[END_REF] problems were introduced, and shown to reduce to worst-case instances of Ideal-SVP (the specialization of approx-SVP to ideal lattices).

In this work, we propose to recast algebraic lattice problems in their natural mathematical abstraction. It is well known to number theorists (e.g. [START_REF] Schoof | Computing arakelov class groups[END_REF]) that the space of all ideal lattices (up to isometry) in a given number eld is naturally an abelian group, called the Arakelov class group. Yet, this notion has never appeared explicitly in the literature on lattice-based cryptography. The relevance of this perspective is already illustrated by some previous work which implicitly exploit Arakelov ideals [START_REF] Eisenträger | A quantum algorithm for computing the unit group of an arbitrary degree number eld[END_REF][START_REF] Biasse | A polynomial time quantum algorithm for computing class groups and solving the principal ideal problem in arbitrary degree number elds[END_REF] and even the Arakelov class group [START_REF] Pellet-Mary | Approx-svp in ideal lattices with pre-processing[END_REF][START_REF] Lee | An lll algorithm for module lattices[END_REF]. Beyond its direct result, our work aims at highlighting this powerful formalism for ner and more rigorous analysis of computational problems in ideal lattices.

Our result

The rst half of this work (Section 3) is dedicated to the development of a new versatile tool: we prove that, subject to the Riemann Hypothesis for Hecke L-functions, certain random walks on the Arakelov class group have a rapid mixing property. In the second half (Section 4), we exploit this result to relate the average-case This paper is the full version of [START_REF] De Boer | Random self-reducibility of ideal-SVP via Arakelov random walks[END_REF], which appeared in the proceedings of Crypto 2020. and the worst-case of Ideal-SVP, due to the interpretation of the Arakelov class group as the space of all ideal lattices. Note that this reduction does not directly impact the security of existing schemes: apart from the historical Fully Homomorphic Encryption scheme of Gentry [START_REF] Gentry | A fully homomorphic encryption scheme[END_REF], 5 there exists no scheme based on the average-case version of Ideal-SVP. The value of our result lies in the introduction of a new tool, and an illustration of the cryptanalytic insights it oers.

A second virtue of our technique resides in the strong similarities it shares with a distant branch of cryptography: cryptography based on elliptic curves [START_REF] Jao | Expander graphs based on GRH with an application to elliptic curve cryptography[END_REF], or more generally on abelian varieties [START_REF] Jetchev | On graphs of isogenies of principally polarizable abelian surfaces and the discrete logarithm problem[END_REF]. These works established that the discrete logarithm problem in a randomly chosen elliptic curve is as hard as in any other in the same isogeny class. The strategy consists in doing a random isogeny walk, to translate the discrete logarithm problem from a presumably hard curve to a uniformly random one. The core of this result is a proof that such walks are rapidly mixing within an isogeny graph (which is isomorphic to the Cayley graph of the class group of a quadratic number eld). As long as the length of the random walk is polynomial, the reduction is ecient.

We proceed in a very similar way. The set of ideal lattices (up to isometry) of a given number eld K can be identied with the elements of the Arakelov class group (also known as the degree zero part Pic 0 K of the Picard Group). There are two ways to move within this group: given an ideal, one can obtain a new one by `distorting' it, or by `sparsifying' it. In both cases, nding a short vector in the target ideal also allows to nd a short vector in the source ideal, up to a certain loss of shortness. This makes the length of the walk even more critical in our case than in the case of elliptic curves: it does not only aect the running time, but also the quality of the result.

Nevertheless, this approach leads to a surprisingly tight reduction. In the case of cyclotomic number elds of conductor m = p k , under the Riemann Hypothesis for Hecke L-functions (which we abbreviate ERH for the Extended Riemann Hypothesis), and a mild assumption on the structure of the class groups, the loss of approximation factor is as small as O( √ m). In other words:

Main Theorem (informal). Let m = p k be a prime power. If there exists a polynomial-time algorithm for solving Hermite-SVP with approximation factor γ over random ideal lattices of Q(ζ m ), then there also exists a polynomial time algorithm that solves Hermite-SVP in any ideal lattice with approximation factor

γ = γ • √ m • poly(log m).
In fact, this theorem generalizes to all number elds, but the loss in approximation factor needs to be expressed in more involved quantities. The precise statement is the object of Theorem 4.5.

Prerequisites. The authors are aware that the theory of Arakelov class groups, at the core of the present article, may not be familiar to all readers. Given space constraints, some denitions or concepts are introduced very briey. We found Chapters I and VII of Neukirch's textbook [START_REF] Neukirch | Algebraic number theory[END_REF] to be a good primer.

Overview

The Arakelov class group. Both the unit group [START_REF] Cramer | Recovering short generators of principal ideals in cyclotomic rings[END_REF] and the class group [START_REF] Cramer | Short stickelberger class relations and application to ideal-svp[END_REF] have been shown to play a key role in the cryptanalysis of ideal lattice problems. In these works, these groups are exploited independently, in ways that nevertheless share strong similarities with each other. More recently, both groups have been used in combination for cryptanalytic purposes [START_REF] Pellet-Mary | Approx-svp in ideal lattices with pre-processing[END_REF][START_REF] Lee | An lll algorithm for module lattices[END_REF]. It therefore seems natural to turn to a unifying theory.

The Arakelov class group (denoted Pic 0 K ) is a combination of the unit torus T = Log K 0 R / Log(O * K ) and of the class group Cl K . The exponent 0 here refers to elements of algebraic norm 1 (i.e., modulo renormalization), while the subscript R indicates that we are working in the topological completion of K. By `a combination' we do not exactly mean that Pic 0 K is a direct product; we mean that there is a short exact sequence

0 -→ T -→ Pic 0 K -→ Cl K -→ 0.
That is, T is (isomorphic to) a subgroup of Pic 0 K , and Cl K is (isomorphic to) the quotient Pic 0 K /T . The Arakelov class group is an abelian group which combines an uncountable (yet compact) part T and a nite part Cl K ; topologically, it should be thought of as | Cl K | many disconnected copies of the torus T .

A worst-case to average-case reduction for ideal-SVP. An important aspect of the Arakelov Class Group for the present work is that this group has a geometric interpretation: it can essentially be understood as the group of all ideal lattices up to K-linear isometries. Furthermore, being equipped with a metric, it naturally induces a notion of near-isometry. Such a notion gives a new handle to elucidate the question of the hardness of ideal-SVP: knowing a short vector in I, and a near-isometry from I to J, one can deduce a short vector of J up to a small loss induced by the distortion of the near-isometry. This suggests a strategy towards a worst-case to average-case reduction for ideal lattices, namely randomly distort a worst-case ideal to a random one.

However, there are two issues with this strategy: rst near-isometry leaves one stuck in a xed class of Cl K ; i.e., one is stuck in one of the potentially many separated copies of the torus that constitute the Arakelov class group. Second, even if | Cl K | = 1, the torus might be too large, and to reach the full torus from a given point, one may need near-isometry that are too distorted.

In the language of algebraic geometry, distortion of ideal lattices corresponds to the `innite places' of the eld K, while we can also exploit the `nite places', i.e., the prime ideals. Indeed, if a is an integral ideal of small norm and J = aI, then J is a sublattice of I and a short vector of J is also a somewhat short vector of I, an idea already used in [START_REF] Cramer | Short stickelberger class relations and application to ideal-svp[END_REF][START_REF] Pellet-Mary | Approx-svp in ideal lattices with pre-processing[END_REF].

Random walk in the Arakelov class group. The questions of whether the above strategy for the self-reducibility of ideal-SVP works out, and with how much loss in the approximation factor therefore boils down to the following question:

How fast does a random walk in the Arakelov class group converges to the uniform distribution ? More specically, this random walk has three parameters: a set P of nite places, i.e., a set of (small) prime ideals, a length N for the discrete walk on nite places, and nally a variance s for a continuous walk (e.g. a Gaussian) on innite places. The loss in approximation factor will essentially be driven by B N/n • exp(s) where B is the maximal algebraic norm of the prime ideals in P, and n the rank of the number eld.

Because the Arakelov class group is abelian and compact, such a study is carried out by resorting to Fourier analysis: uniformity is demonstrated by showing that all the Fourier coecients of the distribution resulting from the random walk tend to 0 except for the coecient associated with the trivial character. For discrete walks, one considers the Hecke operator acting on distributions by making one additional random step, and shows that all its eigenvalues are signicantly smaller than 1, except for the eigenvalue associated with the trivial character. This is merely an extension to compact groups of the spectral gap theorem applied to the Cayley graph of a nite abelian group, as done in [START_REF] Jao | Expander graphs based on GRH with an application to elliptic curve cryptography[END_REF].

Our study reveals that the eigenvalues are indeed suciently smaller than 1, but only for low-frequency characters. But this is not so surprising: these eigenvalues only account for the discrete part of the walk, using nite places, which leaves discrete distributions discrete, and therefore non-uniform over a continuous group. To reach uniformity we also need a continuous walk over the innite places, and taking a Gaussian continuous walk eectively clears out the Fourier coecients associated to high-frequency characters.

Related work

Relation to recent cryptanalytic works. The general approach to this result was triggered by a heuristic observation made in [START_REF] Ducas | On the shortness of vectors to be found by the ideal-svp quantum algorithm[END_REF], suggesting that the worst-case behavior of the quantum Ideal-SVP algorithm built out of [START_REF] Eisenträger | A quantum algorithm for computing the unit group of an arbitrary degree number eld[END_REF][START_REF] Biasse | A polynomial time quantum algorithm for computing class groups and solving the principal ideal problem in arbitrary degree number elds[END_REF][START_REF] Cramer | Recovering short generators of principal ideals in cyclotomic rings[END_REF][START_REF] Cramer | Short stickelberger class relations and application to ideal-svp[END_REF] could be made not that far of the average-case behavior they studied experimentally. More specically, we do achieve the hoped generalization of the class-group mixing theorem of [START_REF] Jao | Expander graphs based on GRH with an application to elliptic curve cryptography[END_REF][START_REF] Jetchev | On graphs of isogenies of principally polarizable abelian surfaces and the discrete logarithm problem[END_REF] to Arakelov class groups; but we furthermore show that this result aects all algorithms, and not only the one they studied.

We also remark that recent works [START_REF] Pellet-Mary | Approx-svp in ideal lattices with pre-processing[END_REF][START_REF] Lee | An lll algorithm for module lattices[END_REF] were already implicitly relying on Arakelov theory. More specifically, the lattice given in Section 3.1 of [START_REF] Pellet-Mary | Approx-svp in ideal lattices with pre-processing[END_REF] is precisely the lattice of Picard-class relations between the appropriate set of (degree 0) Arakelov Divisors. In fact, our theorem also implies upper bounds for the covering radius of the those relation lattices, at least for suciently large factor bases, and with more eort one may be able to eliminate Heuristic 4 from [START_REF] Pellet-Mary | Approx-svp in ideal lattices with pre-processing[END_REF] or Heuristic 1 of [START_REF] Lee | An lll algorithm for module lattices[END_REF].

Prior self-reduction via random walks. As already mentioned, our result shares strong similarities with a technique introduced by Jao, Miller and Venkatesan [START_REF] Jao | Expander graphs based on GRH with an application to elliptic curve cryptography[END_REF] to study the discrete logarithm problem on elliptic curves. Just as ideal lattices can be seen as elements of the Arakelov class group, elliptic curves in certain families are in bijective correspondence with elements of the class group of a quadratic imaginary number eld. In [START_REF] Jao | Expander graphs based on GRH with an application to elliptic curve cryptography[END_REF], Jao et al. studied (discrete) random walks in class groups, and showed that they have a rapid mixing property. They deduced that from any elliptic curve, one can eciently construct a random isogeny (a group homomorphism) to a uniformly random elliptic curve, allowing to transfer a worst case instance of the discrete logarithm problem to an average case instance. Instead of the nite class group, we studied random walks in the innite Arakelov class group, which led us to consequences in lattice-base cryptography, an area seemingly unrelated to elliptic curve cryptography.

Prior self-reduction for ideal lattices. Our self-reducibility result is not the rst of its kind: in 2010, Gentry already proposed a self-reduction for an ideal lattice problem [START_REF] Gentry | Toward basing fully homomorphic encryption on worst-case hardness[END_REF], as part of his eort of basing Fully-Homomorphic Encryption on worst-case problems [START_REF] Gentry | A fully homomorphic encryption scheme[END_REF]. Our result diers in several point: Our reduction does not rely on a factoring oracle, and is therefore classically ecient; this was already advertised as an open problem in [START_REF] Gentry | Toward basing fully homomorphic encryption on worst-case hardness[END_REF].

The reduction of Gentry considers the Bounded Distance Decoding problem (BDD) in ideal lattices rather than a short vector problem. Note that this distinction is not signicant with respect to quantum computers [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF].

The denition of average case distribution is signicantly dierent, and we view the one of [START_REF] Gentry | Toward basing fully homomorphic encryption on worst-case hardness[END_REF] as being somewhat ad-hoc. Given that the Arakelov class group captures exactly ideal lattices up to isometry, we consider the uniform distribution in the Arakelov class group as a much more natural and conceptually simpler choice.

The loss on the approximation factor of our reduction is much more favorable than the one of Gentry [START_REF] Gentry | Toward basing fully homomorphic encryption on worst-case hardness[END_REF].

For example, in the case of cyclotomic number elds with prime-power conductor, Gentry's reduction (on BDD) seems to loose a factor at least Θ(n 4.5 ), while our reduction (on Hermite-SVP) only loses a factor Õ( √ n) making a mild assumption on plus-part h + of the class number.

Other Applications. Finally, we wish to emphasise that our rapid mixing theorem for Arakelov class groups appears to be a versatile new tool, which has already found applications beyond hardness proofs for ideal lattices.

One such application is the object of another work in progress. Namely, we note that many algorithms [START_REF] Biasse | Subexponential class group and unit group computation in large degree number elds[END_REF][START_REF] Biasse | Computing generator in cyclotomic integer rings[END_REF][START_REF] De Boer | Calculating the power residue symbol and ibeta[END_REF] rely on nding elements a in an ideal I such that aI -1 is easy to factor (e.g. prime, near-prime, or B-smooth). Such algorithms are analyzed only heuristically, by treating aI -1 as a uniformly sampled ideal, and applying know results on the density of prime or smooth ideals. Our theorem allows to adjust this strategy and make the reasoning rigorous. First, we show that if the Arakelov class of the ideal I is uniformly random, one can rigorously analyze the probability of aI -1 being prime or smooth. Then, our random-walk theorem allows to randomize I, while not aecting the usefulness of the recovered element a. However, due to space constraints and thematic distance, we chose to develop this application in another article.

As mentioned above, another potential application of random walk theorem may be the elimination of heuristics in cryptanalysis of ideal and module lattices [START_REF] Pellet-Mary | Approx-svp in ideal lattices with pre-processing[END_REF][START_REF] Lee | An lll algorithm for module lattices[END_REF].

Preliminaries

We denote by N, Z, Q, R the natural numbers, the integers, the rationals and the real numbers respectively. All logarithms are in base e. For a rational number p/q ∈ Q with p and q coprime, we let size(p/q) refer to log |p| + log |q|. We extend this denition to vectors of rational numbers, by taking the sum of the sizes of all the coecients.

Number theory

Throughout this paper, we use a xed number eld K of rank n ≥ 3 over Q, having ring of integers O K , discriminant ∆, regulator R, class number h and group of roots of unity µ K . Minkowski's theorem [35, pp. 261264] states that there exists an absolute constant c > 0 such that log |∆| ≥ c • n. The number eld K has n eld embeddings into C, which are divided in n R real embeddings and n C conjugate pairs of complex embeddings, i.e., n = n R + 2n C . These embeddings combined yield the so-called Minkowski embedding

Ψ : K → K R ⊆ σ:K →C C, α → (σ(α)) σ , where K R = x ∈ σ:K →C C x σ = x σ .
Here, σ equals the conjugate embedding of σ whenever σ is a complex embedding and it is just σ itself whenever it is a real embedding. Note that we index the components of the vectors in K R by the embeddings of K. Embeddings up to conjugation are called innite places, denoted by ν. With any embedding σ we denote by ν σ the associated place; and for any place we choose a xed embedding σ ν .

Composing the Minkowski embedding by the component-wise logarithm of the entries' absolute values yields the logarithmic embedding, denoted by Log.

Log : K * → Log K R ⊆ σ:K →C R, α → (log |σ(α)|) σ .
The multiplicative group of integral units O * K under the logarithmic embedding forms a lattice, namely the lattice Λ K = Log(O * K ) ⊆ Log K R . This so-called logarithmic unit lattice has rank = n R + n C -1, is orthogonal to the all-one vector (1) σ , and has covolume Vol(Λ

K ) = √ n • 2 -n C /2
• R, where the 2 -n C /2 factor is due to the specic embedding we use (see Lemma A.1). We denote by H = Span(Λ K ) the hyperplane of dimension , which can also be dened as the subspace of Log K R orthogonal to the all-one vector (1) σ . We denote by T = H/Λ K the hypertorus dened by the logarithmic unit lattice Λ K .

Fractional ideals of the number eld K are denoted by a, b, . . ., but the symbol p is generally reserved for integral prime ideals of O K . The group of fractional ideals of K is denoted by I K . Principal ideals with generator α ∈ K * are usually denoted by (α). For any integral ideal a, we dene the the norm N (a) of a to be the number |O K /a|; this norm then generalizes to fractional ideals and elements as well. The class-group of O K , denoted by Cl(O K ), is the quotient of the group I K by the subgroup of principal ideals Princ K := {(α) , α ∈ K}. For any fractional ideal a, we denote the ideal class of a in

Cl(O K ) by [a].
Extra attention is paid to the cyclotomic number elds K = Q(ζ m ), for which we can prove sharper results due to their high structure. These results rely on the size of the class group

h + K = | Cl(K + )| of the maximum real subeld K + = Q(ζ m + ζm ) of K,
which is often conjectured to be rather small [START_REF] Miller | Real cyclotomic elds of prime conductor and their class numbers[END_REF][START_REF] Buhler | Heuristics for class numbers of prime-power real cyclotomic elds[END_REF]. In this paper, we make the mild assumption that h

+ K ≤ (log n) n .
Extended Riemann Hypothesis Almost all results in this paper rely heavily on the Extended Riemann Hypothesis (in the subsequent part of this paper abbreviated by ERH), which refers to the Riemann Hypothesis extended to Hecke L-functions (see [22, 5.7]). All statements that mention (ERH), such as Theorem 3. Let q ∈ P be arbitrary, and let N (q) = q j with q prime. Then, the probability of sampling q equals 1 nB , namely 1 n times the probability of sampling q. Therefore, the probability of sampling successfully (i.e., no failure) equals |P| nB ≥ 1 2n log B , since |P| ≥ B 2 log B , by Lemma A.3. The most costly part of the algorithm is the factorization of a prime p ≤ B in O K . This can be performed using the Kummer-Dedekind algorithm, which essentially amounts to factoring a degree n polynomial modulo p. Using Shoup's algorithm [START_REF] Shoup | A new polynomial factorization algorithm and its implementation[END_REF] (which has complexity O(n 2 + n log p) [45, 4.1]) yields the complexity claim.

The Arakelov class group

The Arakelov divisor group is the group

Div K = p Z × ν R
where p ranges over the set of all prime ideals of O K , and ν over the set of innite primes (embeddings into the complex numbers up to possible conjugation). We write an arbitrary element in Div K as

a = p n p • p + ν x ν • ν ,
with only nitely many non-zero n p . We will consistently use the symbols a, b, e, . . . for Arakelov divisors. Denoting ord p for the valuation at the prime p, there is a canonical homomorphism

• : K * → Div K , α -→ p ord p (α) p - ν log |σ ν (α)| • ν .
The divisors of the form α for α ∈ K * are called principal divisors. Just as the ideal class group is the group of ideals quotiented by the group of principal ideals, the Picard group is the group of Arakelov divisors quotiented by the group of principal Arakelov divisors. In other words, the Picard group Pic K is dened by the following exact sequence.

0 → K * /µ K • -→ Div K → Pic K → 0.
For any Arakelov divisor a = p n p • p + ν x ν • ν , we denote its Arakelov class by [a]; in the same fashion that [a] denotes the ideal class of the ideal a.

Despite the Arakelov divisor and Picard group being interesting groups, for our pursposes it is more useful to consider the degree-zero subgroups of these groups. The degree map is dened as follows:

deg : Div K → R, p n p • p + ν x ν • ν → p n p • log(N (p)) + ν real x ν + ν complex 2 • x ν . 0 0 0 0 O * K /µK K * /µK PrincK 0 0 H Div 0 K IK 0 0 T Pic 0 K ClK 0 0 0 0 • Log d 0
Fig. 1: A commutative diagram of exact sequences.

The degree map sends principal divisors α to zero; therefore, the degree map is properly dened on Pic K , as well. We subsequently dene the degree-zero Arakelov divisor group Div 0

K = {a ∈ Div 0 K | deg(a) = 0}
and the Arakelov class group Pic 0

K = {[a] ∈ Pic K | deg([a]) = 0}
. Note that by `forgetting' the innite part of a (degree-zero) Arakelov divisor a, one arrives at a fractional ideal. This projection Div 0

K → I K , p n p • p + ν x ν • ν -→ p p np ,
has the hyperplane H ⊆ Log K R as kernel under the inclusion H → Div 0 K , (x σ ) σ → ν x σν ν . This projection morphism Div 0 K → I K has the following section that we will use often in the subsequent part of this paper.

d 0 : I K → Div 0 K , a -→ p ord p (a) • p - log(N (a)) n ν ν
The groups and their relations, that are treated above, t nicely in the diagram of exact sequences given in Figure 1, where the middle row sequence splits with the section d 0 . It will be proven useful to show that the volume of the Arakelov class group roughly follows the square root of the eld discriminant. Lemma 2.3 (Volume of Pic 0 K ). We have Vol(Pic 0

K ) = h Vol(T ) = hR √ n2 -n C /2 , and log Vol(Pic 0 K ) ≤ n 1 2 log(|∆| 1/n ) + log log(|∆| 1/n ) + 1
Proof. The volume of the Arakelov class group follows from the above exact sequence and the volume computation of T in Lemma A.1. The bound on the logarithm is obtained by applying the class number formula [START_REF] Neukirch | Algebraic Number Theory[END_REF]VII.5,Cor 5.11] and Louboutin's bound [START_REF] Louboutin | Explicit bounds for residues of dedekind zeta functions, values of l-functions at s=1, and relative class numbers[END_REF] on the residue of the Dedekind zeta function at s = 1:

Vol(Pic 0 K ) = hR √ n2 -n C /2 = ρ |∆|ω K √ n 2 n R (2 √ 2π) n C ≤ ρ |∆| ≤ |∆| e log |∆| n n ,
where ω K = |µ K | is the number of roots of unity in K. For the bound on the logarithm, use n log(e log

|∆|/n) = n log log(|∆| 1/n ) + n. We let U(Pic 0 K ) = 1 Vol(Pic 0 K ) • 1 Pic 0 K denote
(Pic 0 K ) = {f : Pic 0 K → C | Pic 0 K |f | 2 <
∞} can be uniquely decomposed into a character 6 The measure on the Arakelov class group is unique up to scaling it is the Haar measure. By xing the volume of Pic 0 K as in Lemma 2.3, we x this scaling as well. We use then this particular scaling of the Haar measure for the integrals over the Arakelov class group.

sum f = χ∈ Pic 0 K a χ • χ,
with a χ ∈ C. In the proof of Theorem 3.3, we will make use of Parseval's identity [START_REF] Deitmar | Principles of Harmonic Analysis[END_REF]Thm. 3.4.8] in the following form.

Pic 0 K |f | 2 = f 2 2 = 1 Vol(Pic 0 K ) χ∈ Pic 0 K |a χ | 2 (1)

Lattices

A lattice Λ is a discrete subgroup of a real vector space. In the following, we assume that this real vector space has dimension m and that the lattice is full-rank, i.e., span(Λ) equals the whole real space. A lattice can be represented by a basis

(b 1 , • • • , b m ) such that Λ = { i x i b i , x i ∈ Z}.
Important notions in lattice theory are the volume Vol(Λ), which is essentially the volume of the hypertorus span(Λ)/Λ (alternatively, Vol(Λ) is the absolute determinant of any basis of Λ); the rst minimum λ 1 (Λ) = min v∈Λ\{0} v ; and the last minimum λ m (Λ), which equals the minimal radius r > 0 such that {v ∈ L | v ≤ r} is of full rank m.

We will be interested into the following algorithmic problem over lattices.

Denition 2.4 (γ-Hermite-SVP). Given as input a basis of a rank m lattice Λ, the problem γ-Hermite-SVP consists in computing a non-zero vector v in λ such that

v ≤ γ • Vol(Λ) 1/m . For a rank-m lattice Λ ⊂ R m , we let Λ * denote its dual, that is Λ * = {x ∈ R m : ∀v ∈ Λ , v, x ∈ Z}.

Divisors and ideal lattices

It will be proven useful to view both ideals and Arakelov divisors as lattices in the real vector space K R , where K R has its (Euclidean or maximum) norm inherited from the complex vector space it lives in. Explicitly, the Euclidean and maximum norm of α ∈ K are respectively dened by the rules α 2 2 = σ |σ(α)| 2 and α ∞ = max σ |σ(α)|, where σ ranges over all embeddings K → C. By default, α refers to the Euclidean norm α 2 .

For any ideal a of K, we dene the associated lattice L(a) to be the image of a ⊆ K under the Minkowski embedding Ψ, which is clearly a discrete subgroup of K R . In particular, L(O K ) is a lattice and we will always assume throughout this article that we know a basis

(b 1 , • • • , b n ) of L(O K ). For Arakelov divisors a = p n p • p + ν x ν • ν , the associated lattice is dened as follows. L(a) = (e xν σ • σ(α)) σ | α ∈ p np = diag ((e xν σ ) σ ) • L p np ⊆ K R ,
where diag denotes a diagonal matrix. Note that we have

Vol(L(a)) = |∆| N (a) and Vol(L(a)) = |∆| • σ e xν σ • N ( p p np ) = |∆| • e deg(a)
The associated lattice L(a) of a divisor is of a special shape, which we call ideal lattices, as in the following denition.

Denition 2.5 (Ideal lattices). An ideal lattice is an O K -module I ⊆ K R for which holds that there exists an invertible x ∈ K R such that xI = L(a) for some ideal a of O K . We let IdLat K denote the set of all ideal lattices.

Note that the lattices L(a) for a ∈ I K are special cases of ideal lattices, which we will call fractional ideal lattices. Since the Minkowski embedding is injective, the map L(•) provides a bijection between the set of fractional ideals and the set of fractional ideal lattices.

The set IdLat K of ideal lattices forms a group; the product of two ideal lattices I = x L(a) and J = y L(b) is dened by the rule I • J = xy L(ab). It is clear that L(O K ) is the unit ideal lattice and x -1 L(a -1 ) is the inverse ideal lattice of x L(a). The map L : Div 0 K → IdLat K , a → L(a) sends an Arakelov divisor to an ideal lattice. The image under this map is the following subgroup of IdLat K .

IdLat 0 K = {x L(a) | N (a) σ
x σ = 1 and x σ > 0 for all σ}.

Denition 2.6 (Isometry of ideal lattices). For two ideal lattices L, L ∈ IdLat 0 K , we say that L and L are K-isometric, denoted by L ∼ L , when there exists

(ξ σ ) ∈ K R with |ξ σ | = 1 such that (ξ σ ) σ • L = L .
It is evident that being K-isometric is an equivalence relation on IdLat 0 K that is compatible with the group operation. Denoting Iso K for the subgroup

{L ∈ IdLat 0 K | L ∼ L(O K )} ⊂ IdLat 0 K , we have the following result.
Lemma 2.7 (Arakelov classes are ideal lattices up to isometries). Denoting P : IdLat 0

K → Pic 0 K for the map x L(a) -→ p ord p (a)[p] + ν log(x σν )[ν]
modulo principal divisors, we have the following exact sequence.

0 → Iso K → IdLat 0 K P -→ Pic 0 K → 0.
Proof. This is a well-known fact (e.g., [START_REF] Schoof | Computing arakelov class groups[END_REF]), but we give a proof for completeness. It suces to show that P is a well-dened surjective homomorphism and its kernel is Iso K . In order to be well-dened, P must satisfy

P (x L(a)) = P (x L(a )) whenever x L(a) = x L(a ).
Assuming the latter, we obtain

x -1 x L(O K ) = L((a ) -1 a) = L(αO K ), for some α ∈ K * , as the module is a free O K -module. This implies that (x -1 x ) σ = σ(ηα) for all embeddings σ : K → C, for some unit η ∈ O * K . Therefore, we have, P (x L(a)) -P (x L(a )) = p ord p (α)[p] + ν log((x σν ) -1 x σν )[ν] = ηα ; i.e.
, their dierence is a principal divisor, meaning that their image in Pic 0 K is the same. One can check that P is a homomorphism, and its surjectivity can be proven by constructing an ideal lattice in the pre-image of a representative divisor a = p n p

[p] + ν x ν [ν] ∈ Div 0 K of an Arakelov class [a], e.g., (e xν σ ) σ • L( p p np ).
We nish the proof by showing that the kernel of P indeed equals Iso K . Suppose x L(a) ∈ ker(P ), i.e., P (x L(a)) = p ord p (a)[p] + ν log(x σν )[ν] = α is a principal divisor. This means that a = αO K and

x = (|σ(α)| -1 ) σ , i.e., x L(a) = (|σ(α)| -1 ) σ L(αO K ) = σ(α) |σ(α)| σ • L(O K ), so x L(a) ∼ L(O K ), implying
x L(a) ∈ Iso K . This shows that ker P ⊆ Iso K . The reverse inclusion starts with the observation that x L(a) ∼

L(O K ) directly implies that a = αO K is principal, by the fact that x L(a) is a free O K -module. So, (x σ σ(α)) σ • L(O K ) = x L(αO K ) = (ξ σ ) σ • L(O K ) for some (ξ σ ) σ ∈ K R with |ξ σ | = 1. Therefore, |x σ σ(ηα)| = |ξ σ | = 1, i.e., |x σ | = |σ(ηα)| -1 for some unit η ∈ O * K . From here one can directly conclude that P (x L(a)) = P ((|σ(ηα)| -1 ) σ L(αO K )) = ηα , a principal divisor.
Lemma 2.8. For any ideal lattice L in IdLat K , we have

λ n (L) ≤ √ n • λ n (L(O K )) • Vol(L) 1/n . Moreover, it holds that λ n (L(O K )) ≤ √ n • √ ∆.
Proof. Write L = x L(a) and choose a shortest element xα ∈ x L(a). That means xα = λ 1 (x L(a)). Then

x L(a) ⊃ x L(αO K ), and therefore

λ n (x L(a)) ≤ λ n (x L(αO K )) ≤ xα ∞ λ n (L(O K )) ≤ xα 2 λ n (L(O K )) ≤ λ 1 (x L(a)) • λ n (L(O K )) ≤ √ n • λ n (L(O K )) • Vol(x L(a)) 1/n
where the last inequality is Minkowski's theorem. The bound on λ n (L(O K )) is proven using Minkowski's second theorem (in the innity norm) and the fact that λ

(∞) 1 (L(O K )) ≥ 1.

The Gaussian Function and Smoothing Errors

Let n be a xed positive integer. For any parameter s > 0, we consider the n-dimensional Gaussian function

ρ (n) s : R n → C , x → e -π x 2 s 2
, (where we drop the (n) whenever it is clear from the context), which is well known to satisfy the following basic properties.

Lemma 2.9. For all s > 0, n ∈ N and x, y ∈ R n , we have

z∈R n ρ s (z)dz = s n , F R n {ρ s } = y∈R n ρ s (y)e -2πi y,• dy = s n ρ 1/s and ρ s (x) 2 = ρ s/ √ 2 (x).
The following two results (and the variations we discuss below) will play an important role and will be used several times in this paper: Banaszczyk's bound, originating from [START_REF] Banaszczyk | New bounds in some transference theorems in the geometry of numbers[END_REF], and the smoothing parameter, as introduced by Micciancio and Regev [START_REF] Micciancio | Worst-case to average-case reductions based on gaussian measures[END_REF]. They allow us to control

ρ s (X) := x∈X ρ s (x) ,
for certain discrete subsets X ⊆ R m . For ease of notation, we let

β (n) z := 2πez 2 n n/2 e -πz 2 ,
which decays super-exponentially in z (for xed n). In particular, we have β

(n) t ≤ e -t 2 for all t ≥ √ n. The following formulation of Banaszczyk's lemma is obtained from [34, Equation (1.1)].
Lemma 2.10 (Banaszczyk's Bound). Whenever r/s ≥ n 2π ,

ρ s (Λ + t) \ B r ≤ β (n) r/s • ρ s (Λ) ,
where

B r = B r (0) = {x ∈ R n x 2 < r}.
Denition 2.11 (Smoothing parameter). Given an ε > 0 and a lattice Λ, the smoothing parameter η ε (Λ) is the smallest real number s > 0 such that ρ 1/s (Λ * ) ≤ ε. Here, Λ * is the dual lattice of Λ.

Lemma 2.12 (Smoothing Error). Let Λ ∈ R n be a full rank lattice, and let s ≥ η (Λ). Then, for any

t ∈ R n , ( 1
-) s n det Λ ≤ ρ s (Λ + t) ≤ (1 + ) s n det Λ . (2)
We have the following two useful upper bounds for full-rank n-dimensional lattices Λ [32, Lemma 3.2 and

3.3]: η (Λ) ≤ log(2n(1 + 1/ )) • λ n (Λ) for all > 0 and η 1 (Λ) ≤ η 2 -n (Λ) ≤ √ n/λ 1 (Λ * ) ≤ √ n • λ n (Λ)
. The latter leads to the following corollary. Corollary 2.13. Let L be an ideal lattice in IdLat K . Let t ∈ R n be arbitrary and

s ≥ n • λ n (L(O K )) • Vol(L) 1/n . Then it holds that ρ s (L -t) • Vol(L) s n -1 ≤ 2 -n , (3)
Proof. By the assumption on s and by Lemma 2.8, we have s

≥ n • λ n (L(O K )) • Vol(L) 1/n ≥ √ n • λ n (L) ≥ η 2 -n (Λ).
The result follows then from Lemma 2.12.

Gaussian distributions and statistical distance

Statistical distance. For two random variables X and Y , we let SD(X, Y ) denote their statistical distance (or total variation distance). This distance is equal to half of the 1 -distance between the two corresponding distributions. In particular, if X and Y live in a countable set S, then

SD(X, Y ) = 1 2 • s∈S |P(X = s) -P(Y = s)|.
Continuous Gaussian distribution. For a real vector space H of dimension n, a parameter s > 0 and a center c ∈ H, we write G H,s,c the continuous Gaussian distribution over H with density function ρ s (x -c)/s n for all x ∈ H. When the center c is 0, we simplify the notation as G H,s .

Discrete Gaussian distributions. For any lattice L ⊂ R n , we dene the discrete Gaussian distribution over

L of standard deviation s > 0 and center c ∈ R n by ∀x ∈ L , G L,s,c = ρ s (x -c) ρ s (L -c) .
When the center c is 0, we simplify the notation as G L,s .

Observe that we use almost the same notation for discrete Gaussian distributions and for continuous ones. What allows us to make a distinction between them are the indexes L or H (if the index is a lattice, then the distribution is discrete whereas if the index is a real vector space, then the distribution is continuous).

The following lemma states that one can sample from a distribution statistically close to a discrete Gaussian distribution over a lattice L (provided that the standard deviation s is large enough). Proposition 2.14 (Theorem 4.1 of [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]). There exists a probabilistic polynomial time algorithm that takes as input a basis

(b 1 , • • • , b n ) of a lattice L ⊂ R n , a parameter s ≥ √ n • max i b i and a center c ∈ R n and outputs a sample from a distribution G L,s,c such that SD(G L,s,c , G L,s,c ) ≤ 2 -n .
We will refer to the algorithm mentioned in Proposition 2.14 as Klein's algorithm [START_REF] Klein | Finding the closest lattice vector when it's unusually close[END_REF]. We note that Theorem 4.1 of [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] states the result for a statistical distance negligible (i.e., of the form n -ω (1) ), but the statement and the proof can be easily adapted to other statistical distances. [START_REF] Banaszczyk | New bounds in some transference theorems in the geometry of numbers[END_REF] Random Walk Theorem for the Arakelov Class Group

In this section, we prove Theorem 3.3, on random walks in the Arakelov class group. Starting with a point in the hyperplane H ⊆ Div 0 K , sampled according to a Gaussian distribution, we prove that multiplying this point suciently often by small random prime ideals yields a random divisor that is very close to uniformly distributed in the Arakelov class group (i.e., modulo principal divisors). The proof of Theorem 3.3 requires various techniques, extensively treated in Sections 3.2 to 3.6, and summarised in the following.

Hecke operators. The most important tool for proving Theorem 3.3 is that of a Hecke operator, whose denition and properties are covered in Section 3.2. This specic kind of operator acts on the space of probability distributions on Pic 0 K , and has the virtue of having the characters of Pic 0 K as eigenfunctions.

Eigenvalues of Hecke operators. The aim of the proof is showing that applying this Hecke operator repeatedly on an appropriate initial distribution yields the uniform distribution on Pic 0 K . The impact of consecutive applications of the Hecke operator can be studied by considering its eigenvalues of the eigenfunctions (which are the characters of Pic 0 K ). Classical results from analytic number theory show that the eigenvalues of these characters are (in absolute value) suciently smaller than 1, whenever the so-called analytic conductor of the corresponding character is not too large. An exception is the unit character, which is xed under each Hecke operation. This classical result and how to apply it in our specic setting is covered in Section 3.3.

The analytic conductor. The Hecke operator thus quickly `damps out' all characters with small analytic conductor (except the unit character). In Section 3.4, we examine which quantities of a character of Pic 0 K dene the analytic conductor. It turns out that this analytic conductor is closely related to how the character acts on the hypertorus dened by the log unit lattice. The higher the frequency of this character on the hypertorus, the larger the analytic conductor. This frequency can be measured by the norm of the uniquely associated dual log unit lattice point of the character. In fact, we establish a bound on the analytic conductor of a character in terms of the norm of its associated dual lattice point.

Fourier analysis on the hypertorus. To summarize, low-frequency (non-trivial) characters on Pic 0 K (i.e., with small analytic conductor) are quickly damped out by the action of the Hecke character, whereas for highfrequency characters we do not have good guarantees on the speed at which they damp out. To resolve this issue, we choose an initial distribution whose character decomposition has only a negligible portion of highfrequency oscillatory characters. An initial distribution that nicely satises this condition is the Gaussian distribution (on the hypertorus). To examine the exact amplitudes of the occuring characters of this Gaussian distribution, we need Fourier analysis on this hypertorus, as covered in Section 3.5.

Splitting up the character decomposition. In this last part of the proof, which is covered in Section 3.6, we write the Gaussian distribution into its character decomposition, where we seperate the high-frequency characters, the low-frequency ones and the unit character. Applying the Hecke operator often enough damps out the low-frequency ones, and as the high-frequency characters were only negligibly present anyway, one is left with (almost only) the unit character. This corresponds to a uniform distribution.

Main result

Denition 3.1 (Random Walk Distribution in Div 0 K ). We denote by W Div 0 K (B, N, s) the distribution on Div 0 K that is obtained by the following random walk procedure. Sample x ∈ H ⊆ log K R according to a centered Gaussian distribution with standard deviation s. Subsequently, sample N ideals p j uniformly from the set of all prime ideals with norm bounded by B. Finally, output x + N j=1 d 0 (p j ), where x ∈ Div 0 K is understood via the injection H → Div 0 K . Denition 3.2 (Random Walk Distribution in Pic 0 K ). By W Pic 0 K (B, N, s), we denote the distribution on the Arakelov class group obtained by sampling a from W Div 0 K (B, N, s) and taking the Arekalov class

[a] ∈ Pic 0 K . Theorem 3.3 (Random Walks in the Arakelov Class Group, ERH). Let ε > 0 and s > 0 be any positive real numbers and let k ∈ N >0 be a positive integer. Putting s = min(

√ 2 • s, 1/η 1 (Λ * K )),
there exists a bound

B = O(n 2k [n 2 (log log(1/ε)) 2 + n 2 (log(1/s )) 2 + (log ∆ K ) 2 ]) such that for any N ≥ 2 •log(1/s )+ 1 2 log(Vol(Pic 0 K ))+log(1/ε)+1 k log n , the random walk distribution W Pic 0 K (B, N, s) is ε-close to uniform in L 1 (Pic 0 K ), i.e., W Pic 0 K (B, N, s) -U(Pic 0 K ) 1 ≤ ε.
Below, we instantiate Theorem 3.3 with specic choices of ε and k that are tailored to give an optimal approximation factor in Section 4. As a consequence, the value of B in Corollary 3.4 is exponential in n.

We note however that this value could be made as small as polynomial in n and log ∆, but at the cost of a slightly worse approximation factor for the reduction of Section 4.

The key dierence between those two instantiations is how we deal with the smoothing parameter of the dual log-unit lattice, η 1 (Λ * K ). In the general case, we rely on works of Dobrolowski and Kessler [START_REF] Dobrowolski | On a question of lehmer and the number of irreducible factors of a polynomial[END_REF][START_REF] Kessler | On the minimum of the unit lattice[END_REF] to lower bound the rst minimum of the primal log unit lattice. In the case of cyclotomics, we obtain a sharper bound by resorting to the analysis of dual cyclotomic unit lattice from Cramer et al. [START_REF] Cramer | Recovering short generators of principal ideals in cyclotomic rings[END_REF].

Corollary 3.4 (Application to General Number Fields, ERH).

Let s > 1/ , there exists a bound B = Õ(∆ 1/ log n ) such that for

N ≥ (n -n C )(log n) 2 log(∆) 1 + 30 log log n log n + n log n log ∆ 1 2 log(∆ 1/n ) + log log(∆ 1/n )
holds that the random walk distribution

W Pic 0 K (B, N, s) satises SD W Pic 0 K (B, N, s), U(Pic 0 K ) ≤ 2 -n .
Corollary 3.5 (Application to Prime-Power Cyclotomic Number Fields, ERH). Let K = Q(ζ p k ) be a prime-power cyclotomic number eld and assume

h + K = Cl(K + ) ≤ (log n) n . For s = 1/ log 2 (n), there exists a bound B = O(n 2+2 log n ) such that, for N ≥ n 2 log n 1/2 + 8 log(log(n)) log n
, the random walk distribution

W Pic 0 K (B, N, s) satises SD W Pic 0 K (B, N, s), U(Pic 0 K ) ≤ 2 -n .
The proof of these corollaries can be found in Appendices B.1 and B.2.

Hecke Operators

A key tool to analyse random walks on Pic 0 K are Hecke operators, which allow to transform a given distribution into a new distribution obtained by adding one random step. Denition 3.6 (The Hecke operator). Let P be a nite subset of prime ideals of the number eld K, and let Pic 0 K be the Arakelov class group. Then we dene the Hecke operator

H P : L 2 (Pic 0 K ) → L 2 (Pic 0 K
) by the following rule:

H P (f )(x) := 1 |P| p∈P f (x -[d 0 (p)])
Lemma 3.7 (Eigenfunctions of the Hecke operator). The Hecke operator

H P : L 2 (Pic 0 K ) → L 2 (Pic 0 K )
has the characters χ ∈ Pic 0 K as eigenfunctions, with eigenvalues λ χ = 1 |P| p∈P χ([d 0 (p)]), i.e.,

H P (χ) = λ χ χ.
Proof. We have

H P (χ)(x) = 1 |P| p∈P χ(x -[d 0 (p)]) = 1 |P| p∈P χ(x)χ([d 0 (p)]). So H P (χ) = λ χ χ with λ χ = 1 |P| p∈P χ([d 0 (p)]). Note that H P (1 Pic 0 K ) = 1 Pic 0 K , for the trivial character 1 Pic 0 K , so λ 1 Pic 0 K = 1.
For any other character χ it is evident from the above that |λ χ | ≤ 1.

Bounds on Eigenvalues of Hecke Operators

Using results from analytic number theory, one can prove the following proposition. Proposition 3.8 (Bound on the eigenvalues of the Hecke operator, ERH). Let P be the set of all primes of K with norm bounded by B ∈ N. Then the eigenvalue λ χ of any non-constant eigenfunction χ ∈ Pic 0 K of the Hecke operator satises

λ χ = O log(B) log(B n • ∆ • q ∞ (χ)) B 1/2 ,
where q ∞ (χ) is the innite part of the analytic conductor of the character χ, as in Denition 3.11 (cf. [22, Eq. (5.6)]).

The proof of this proposition can be found in Appendix B.3.

The Analytic Conductor

In the bounds of Section 3.3, the innite part of the analytic conductor q ∞ (χ) of a character χ : Pic 0 K → C plays a large role. In this section, we show that this innite part of the analytic conductor is closely related to the dual logaritmic unit lattice point * ∈ Λ * K that is uniquely associated with the character χ| T : T → C.

The innite part of the analytic conductor can be dened using the so-called local parameters of the character χ ∈ Pic 0 K . To dene these, we need

F 0 = {(a ν ) ν ∈ ν innite K ν | ν |a ν | ν = 1}
, the normone subgroup of the product of the completions K ν of K with respect to the innite place ν. Characters η :

F 0 → C are of the form η((a ν ) ν ) = ν a ν |a ν | uν e ivν log |aν |ν , (4)
where v ν ∈ R, and u ν ∈ Z or u ν ∈ {0, 1} depending on whether ν is complex or real (see [36, 3.3, eq. 3.3.1]). In all these denitions, the absolute value

| • | ν equals | • | 2 C or | • | R
depending on whether ν is complex or real. Since there is the map ι : 4) for all χ ∈ Pic 0 K . This leads to the following denition.

F 0 → Pic 0 K , (a ν ) ν -→ ν log |a ν | ν • ν , we must have that χ • ι is of the form described in Equation (
Denition 3.9 (Local parameters of a character on Pic 0 K ). For a character χ : Pic 0 K → C, the numbers k ν (χ) = |u ν | + iv ν (for all innite places ν) are called the local parameters of χ, where u ν and v ν are the numbers appearing in the formula of χ • ι : F 0 → C in Equation ( 4).

As characters on the Arakelov class group are actually very special Hecke characters7 , the local parameters are very restricted. This is described in the following lemma. Proof. As the map ι : F 0 → Pic 0 K only depends on the absolute values of (a ν ) ν , it is clear that u ν = 0 in the decomposition of χ • ι as in Equation ( 4). It remains to prove that v ν = 2πi * σν . The units O * K ⊆ F 0 map to one under χ • ι, since any principal divisor maps to one. Here, the inclusion O * K → F 0 is dened by η → (σ ν (η)) ν , where σ ν is a xed embedding associated with the innite place ν. This means that

χ • ι(η) = ν e ivν log |σν (η)|ν = exp i σ v νσ log |σ(η)| C = 1 for all η ∈ O * K , (5)
where the last sum is over all embeddings σ : K → C, where ν σ is the place associated with the embedding σ, and where | • | C is the standard absolute value on C. Vectors of the form (v νσ ) σ satisfying Equation ( 5) are precisely the vectors (v νσ ) σ ∈ 2πΛ * K ⊆ log K R . By Denition 3.9, one directly obtains k ν (χ) = 2πi * σν .

Denition 3.11 (The innite part of the analytic conductor). Let χ ∈ Pic 0 K be a character with local parameters k ν (χ), where ν ranges over the innite places of K. Then, we dene the innite part of the analytic conductor to be

q ∞ (χ) = ν real (3 + |k ν |) ν complex (3 + |k ν |)(3 + |k ν + 1|)
Remark 3.12. Above denition of the innite part of the analytic conductor is obtained from [22, p. 95, eq.

(5.6) with s = 0], where it is described in a slightly dierent form. In [START_REF] Iwaniec | Analytic Number Theory[END_REF], the functional equation lacks the complex L-functions L C . Instead, those are replaced by L R (s)L R (s + 1) = L C (s) (see [START_REF] Neukirch | Algebraic Number Theory[END_REF]Ch. 7,Prop 4.3 (iv)]. This means that the local parameters κ σ , κ σ as in [22, p. 93, eq. (5.3)] must equal k ν , k ν + 1 for the embeddings {σ, σ} associated with the complex place ν (cf. [22, p. 125]). Lemma 3.13. Let q ∞ (χ) be the innite part of the analytic conductor of the character χ ∈ Pic 0 K , and let * ∈ Λ * K be such that χ| T = χ * , where Λ * K is the dual lattice of the log-unit lattice. Then we have

q ∞ (χ) ≤ 4 + 2π * / √ n n
Proof. Let | * | denote the vector * where all entries are replaced by their absolute value. Then, by applying subsequently the triangle inequality, the inequality between • 1 and • 2 and the arithmetic-geometric mean inequality, one obtains

4 √ n + 2π * 2 ≥ 4 + 2π| * | 2 ≥ 1 √ n 4 + 2π| * | 1 ≥ √ n σ (4 + 2π| * σ |) 1/n ≥ √ nq ∞ (χ * ) 1/n .
Dividing by √ n and raising to the power n yields the claim.

3.5 Fourier Analysis on the Hypertorus Denition 3.14. Let H ⊆ Log K R be the hyperplane where the log unit lattice T , we obtain, for all * ∈ Λ * K ,

Λ K = Log(O * K ) lives in. Recall the Gaussian function ρ s : H → R, x → e -π x 2 /s 2 . Denoting T = H/Λ K , , we put ρ s | T : T → R, x → ∈Λ K ρ s (x + ). As we have (see Lemma A.2) s -ρ s H,1 = H s -ρ s (x)dx = 1, and s -ρ s | T T,1 = T s -ρ s | T (x)dx = 1, both functions s -
a * = 1 Vol(T ) s -ρ s | T , χ * = 1 Vol(T ) x∈F ∈Λ K s -ρ s (x + )χ * (x)dx = 1 Vol(T ) x∈H s -ρ s (x)χ * (x)dx = 1 Vol(T ) F H (s -ρ s )( * ) = 1 Vol(T ) ρ 1/s ( * ).

Conclusion

Theorem 3.16 (ERH). Let P be the set of primes of K of norm at most B, and let H = H P the Hecke operator for this set of primes. Then, for all r, s > 0 with rs > 4π , we have

H N (s -n ρ s ) - 1 Vol(Pic 0 K ) 1 Pic 0 K 2 2 ≤ ρ 1 √ 2s (Λ * K ) Vol(T ) c 2N + β ( ) √ 2rs (6)
with c = O log(B) log(B n •∆•(4+2πr/ √ n) n ) B 1/2 . Proof. As s -ρ s = 1 Vol(T ) χ∈ T ρ 1/s ( * )χ * (see Lemma 3.15), Vol(Pic 0 K ) = h K Vol(T )
, and every χ ∈ T has exactly h K extensions [13, Cor. 3.6.2] to characters on Pic 0 K , we directly deduce that

s -ρ s = 1 Vol(Pic 0 K ) χ * ∈ T χ | T =χ * ρ 1/s ( * )χ ,
where χ ranges over all characters of Pic 0 K . Therefore, by the fact that the characters χ are eigenfunctions of the operator H = H P (see Lemma 3.7),

H N (s -ρ s ) = 1 Vol(Pic 0 K ) χ * ∈ T ρ 1/s ( * ) χ | T =χ * λ N χ χ
where χ ranges over all characters of Pic 0 K . By the fact that s -ρ s is a probability distribution, we obtain that the eigenvalue of the unit character 1 = 1 Pic 0 K satises λ 1 = 1. Therefore, by Parseval's theorem (see Equation ( 1)) and the fact that

ρ 2 1/s = ρ 1 √ 2s , H N (s -ρ s ) - 1 Vol(Pic 0 K ) 1 2 2 = 1 Vol(Pic 0 K ) χ * ∈ T ρ 1 √ 2s ( * ) χ | T =χ * χ =1 |λ χ | 2N ,
where χ ranges over all characters of Pic 0 K . In order to bound the quantity above, we split up the sum into a part where * > r, and a part where * ≤ r. For the former part we can namely bound the Gaussian ρ 1 √ 2s

( * ) whereas for the latter part we can bound the eigenvalues λ χ (see Proposition 3.8). For the part where * > r, we use the assumption √ 2sr > /(2π) to apply Banaszczyk's bound (see Lemma 2.10) , and the fact that

|λ χ | ≤ 1. 1 Vol(Pic 0 K ) * >r ρ 1 √ 2s ( * ) χ | T =χ * |λ χ | 2N ≤h K ≤ ρ 1 √ 2s (Λ * K \ rB) Vol(T ) ≤ β ( ) √ 2rs • ρ 1 √ 2s (Λ * K ) Vol(T ) (7)
For the part where * < r, we have, by Lemma 3.13 that q ∞ (χ) ≤ (4 + 2πr/ √ n) n , and therefore, by Proposition 3.8, we have the bound

|λ χ | ≤ c = O log(B) log(B n •∆•(4+2πr/ √ n) n ) B 1/2 . So, 1 Vol(Pic 0 K ) * ≤r ρ 1 √ 2s ( * ) χ | T =χ * |λ χ | 2N ≤h K •c 2N ≤ c 2N • ρ 1 √ 2s (Λ * K ) Vol(T ) (8)
Combining Equations ( 7) and ( 8), we obtain the result.

Proof (of Theorem 3.3). Let 1 > ε > 0, s > 0 and k ∈ N >0 be given. As

1/s = max( 1 √ 2s , η 1 (Λ * K )) ≥ η 1 (Λ * K ), the smoothing parameter of Λ * K , we have ρ 1 √ 2s (Λ * K )/ Vol(T ) ≤ ρ 1/s (Λ * K )/ Vol(T ) ≤ 2 • s-. (9)
By applying subsequently Hölder's inequality (i.e., f •1 1 ≤ f 2 1 2 ) and the inequality ρ 1/s (Λ * K )/ Vol(T ) ≤ 2s -in Equation ( 6), we obtain (for rs ≥ 4π )

H N (s -n ρ s ) -U (Pic 0 K ) 2 1 ≤ 2 Vol(Pic 0 K ) • s-(c 2N + β ( ) √ 2rs ) (10)
In the following, we will bound the two summands in Equation ( 10) seperately. Putting8

r = 1 √ 2s • max √ , 2 + log(1/s) + 2 log(1/ε) + log(Vol(Pic 0 K )) , implies 2 • Vol(Pic 0 K ) • s-• β ( ) √ 2rs ≤ ε 2 /2. Subsequently, choose 9 B = Õ n 2k • [log(∆) 2 + n 2 log(1/s) 2 + n 2 log(log(1/ε)) 2 ] , such that c ≤ 1/n k , where c = O log(B) log(B n •∆•(4+2πr/ √ n) n ) B 1/2
, as in Theorem 3.16. Finally, taking any

N ≥ /2•log(1/s)+log(1/ε)+ 1 2 log(Vol(Pic 0 K ))+1 k log n and noting that c 1 k log n ≤ 1/e, we deduce 2 Vol(Pic 0 K )•s -c 2N ≤ 1 2 ε 2 .
Combining above two bounds, we can bound the right-hand side of Equation ( 10) by ε 2 . Taking square roots gives the nal result. Worst-Case to Average-Case Reduction

In this section, we give a worst-case to average-case reduction for approx-Hermite-SVP in fractional ideal lattices. In the case of prime power cyclotomic number elds (under the assumption that h + k ≤ (log n) n ), our reduction increases the approximation factor by a factor O( √ n). In the more general case, the approximation factor increases by a factor O(n • ∆ 1/(2n) ).

Our reduction works as follows. Given as input a fractional ideal a, we randomize it using the random walk of the previous section, in order to obtain something uniform in the Arakelov class group. More formally, we multiply a by N prime ideals p i chosen uniformly among the prime ideals of norm smaller than B (where N and B are the ones of Theorem 3.3). We then multiply the resulting ideal a i p i by an element x ∈ K R sampled such that Log(x) follows a Gaussian distribution of small standard deviation. Observe that this means that the coordinates of x are somehow balanced and so multiplication by x does not change the geometry of the ideal that much. Using Theorem 3.3, the obtained ideal lattice L = xL(a • i p i ) has a uniform class in the Arakelov class group. This will essentially be our average-case distribution for ideals. 10Assume now that one can eciently nd a small vector v in the randomized ideal x • L(a • i p i ). Then x -1 • v is an element of L(a) (because L(a • i b i ) is a subset of L(a)). Since x does not distort the geometry too much, this element x -1 • v is still small compared to Vol(L(a

• i p i )) 1/n = Vol(L(a)) 1/n • N ( i p i ) 1/n .
The approximation factor we get is then roughly equal to N ( i p i ) 1/n ≤ B N/n . Using the values of N and B in Corollaries 3.4 and 3.5, we obtain the claimed upper bound on the increase of the approximation factors.

In this overview, we assumed for simplicity that the average-case distribution is the uniform distribution over ideal lattices. In reality, however, for computational reasons, we will instead use a close, `rounded', fractional version of this uniform distribution. This is because general ideal lattices (i.e., Arakelov class group elements) can't be represented eciently and uniquely on a computer. In order to make the reduction computable, we therefore resort to computing with fractional ideals only, which can be eciently represented, for instance by a basis with rational coecients. To be clear, elements of the Arakelov class group are thus only used theoretically and are never actually represented on a computer.

The rst subsection below describes the average-case distribution we consider, and gives some insight on why we have to modify slightly the simple `uniform in the Arakelov class group' distribution. In the second subsection, we show that the randomization procedure described above indeed produces an ideal of the desired average-case distribution. Finally, we prove the reduction in the last subsection.

Algorithm 1 Randomized function Extract

ς,M : IdLat 0 K → I K Require: An ideal lattice L ∈ IdLat 0 K Ensure: A fractional ideal lattice L(b) 1: Sample c = (cσ)σ uniformly in {(xσ)σ : |xσ| = M , ∀σ}. 2: Sample v ← GL,ς,c. 3: return L(b) = v -1 • L ⊂ K R .

The average-case distribution

As mentioned above, the average-case distribution we would like to use is the one obtained by sampling a uniformly distributed Arakelov class [a], and then considering the associated ideal lattice L (dened up to K-isometries, see Lemma 2.7). This distribution however, suers from the following diculty: we don't have a nice way of representing ideal lattices. First of all, these lattices involve real numbers, which cannot be represented on a computer; but even if it was possible to represent real numbers, we do not have a canonical way of representing an ideal lattice. For instance, the natural representation of the ideal lattice L = xL(a) as a pair (x, L(a)) is highly non-unique and it may leak some information on the random walk that was performed to obtain L.

We solve both problems by introducing a specic rounding procedure, that maps an ideal lattice to a fractional ideal lattice with almost the same geometry. Once we have a fractional ideal lattice, we can compute the Hermite Normal Form (HNF) of one of its bases. This provides us a unique representation of the lattice, which can be eciently represented by a matrix with rational coecients.

The ideas behind the rounding procedure are the following. First, we observe that dividing L by any element v ∈ L provides an ideal lattice v -1 • L which is fractional. Hence, to round the ideal lattice L, it is sucient to nd an element v ∈ L such that multiplication by v -1 does not distort too much the geometry of L (this idea was already exploited by [START_REF] Gentry | Toward basing fully homomorphic encryption on worst-case hardness[END_REF]). We nd such a good v by sampling it from a Gaussian distribution in L centered in (M, M, • • • , M ) for some M signicantly larger than the standard deviation. This choice of center ensures that v has all its coordinates close to M , hence v and v -1 are well balanced and so multiplication by v -1 does not distort the geometry too much. To conclude, we nally consider the ideal v -1 L, whose geometry is close to the one of L, and which is a fractional ideal.

In this subsection, our only goal is to describe the average-case distribution, from a mathematical point of view. This means that none of the functions described here needs to be eciently computable, and none of the elements involved needs to be eciently representable.

Let us start by describing a randomized function Extract ς,M (parameterized by some ς > 0 and M > 0), that extracts from an Arakelov class [a] a fractional ideal b, such that the distribution of b is independent from the representation of [a]. We rst describe the function Extract ς,M from ideal lattices of norm 1 to fractional ideals, and we will later extend it to Arakelov classes. 11Lemma 4.1. The function Extract ς,M described in Algorithm 1 outputs a fractional ideal lattice of the form L(b) for a fractional ideal b ⊂ K. More precisely, b is the inverse of an integral ideal and has an algebraic norm larger than ( √ nς + M ) -n with overwhelming probability (i.e., probability at least 1 -2 -Ω(n) ).

Proof. Let us write the ideal lattice L as L = xL(c) for some fractional ideal c. The element v is in L, so it is of the form x Ψ(w) for some w ∈ c. In particular, there exists an (integral) ideal d such that (w) = cd.

Putting everything together we obtain that v -1 L = Ψ(w) -1 L(c) = L(d -1 ). To conclude the proof, we need an upper-bound on the algebraic norm of d.

Since L in is IdLat 0 K , we know that | N (x)| • N (c) = 1.
We also know that with overwhelming probability, every coordinate of v is smaller (in absolute value) than √ nς + M , and so | N (v)| ≤ ( √ nς + M ) n . We conclude by using the fact that

| N (v)| = | N (x)| • N (c) • N (d).
Let us now show that the function Extract ς,M is constant (as a probability distribution) over K-isometric ideal lattices. Lemma 4.2. Let L and L be two ideal lattices such that L ∼ L (i.e., there exists (ξ σ ) σ ∈ K R , with |ξ σ | = 1 for all σ, such that (ξ σ ) σ • L = L ). Then the two probability distributions Extract ς,M (L) and Extract ς,M (L ) are identical.

Proof. Let ξ = (ξ σ ) ∈ K R be as in the lemma. Observe that the multiplication by ξ is an isometry. This means that for any v ∈ L and c ∈ K R , the probability that G L,ς,c outputs v is the same as the one that G L ,ς,ξc outputs ξv. In both cases, the ideal output by the Extract ς,M function will be v -1 • L = (ξv) -1 • L . Due to the random choice of c (uniform among {(x σ ) σ : |x σ | = M for all σ}), the distribution of ξc is the same as the one of c . We then conclude that both nal distributions must be identical.

Since Extract ς,M is constant over all classes of ideal lattices modulo

Iso K = {L ∈ IdLat 0 K | L ∼ L(O K )} ⊂ IdLat 0
K , we can view it as a randomized function from IdLat 0 K / Iso K to I K . But recall that we have an isomorphism between IdLat 0 K / Iso K and Pic 0 K . Using this isomorphism, we can nally dene a function Extract ς,M from Pic 0 K to I K , such that for any ideal lattice L, it holds that the distributions Extract ς,M (L) and Extract ς,M (P (L)) are identical (where P : IdLat 0 K → Pic 0 K is the map dened in Lemma 2.7). We now describe our average-case distribution, which we will refer to as D perfect ς,M (parameterized by two parameters ς, M > 0):

D perfect ς,M := Extract ς,M (U(Pic 0 K )), (11)
where U(Pic 0 K ) is the uniform distribution over Pic 0 K . Once again, this is only the mathematical denition of the distribution D perfect ς,M , and this does not provide an ecient algorithm for sampling from this distribution (in particular because we cannot sample from U(Pic 0 K )). In the next subsection, we will explain how one can sample eciently from a distribution statistically close to D perfect ς,M , when the parameter ς is large enough (this is possible since the output of D perfect ς,M are fractional ideals of bounded algebraic norm, which can be eciently represented).

Sampling from the average-case distribution

In this section, we explain how one can eciently sample from a distribution D sample ς,M that is statistically close to the distribution D perfect ς,M . Let us start by describing a tool distribution D round , which should be eciently samplable. In order to use our random walk theorem, we need to be able to sample elements x ∈ K R such that Log(x) follows a continuous Gaussian distribution of parameter s in H = Log(K * R ). This distribution however cannot be sampled eciently on a computer, as it is a continuous distribution. The objective of the distribution D round is to compute eciently a rounded version of this distribution, where the output x lies in Ψ(K) ⊂ K R . This is formalized in the lemma below. The proof is rather technical and has been postponed to Appendix C.1. Lemma 4.3. For any ε 1 , ε 2 > 0, there exists a deterministic function12 E ε1 : H → Ψ(K) such that for any y ∈ H it holds that

E ε1 (y) • (e -yσ ) σ -1 ∞ ≤ ε 1 .
Furthermore, for any s > 0, one can sample in time polynomial in n,

max i log b i , s, log(1/ε 1 ) and log(1/ε 2 ) from a distribution D round ε1,ε2,s that is ε 2 close in statistical distance to E ε1 (G H,s ). Here, (b 1 , • • • , b n ) is a known basis of L(O K ).
We can now describe the distribution D sample ς,M,a , which we will use as a samplable replacement of D perfect ), but also by a fractional ideal a ⊂ K. We will show that whatever the choice of a is, the distribution Algorithm 2 Distribution D sample ς,M,a Require: A fractional ideal a ⊂ K and two parameters ς, M > 0. Ensure: A fractional ideal lattice L(b) ⊂ Ψ(K).

1: Let s = 1/(log n) 2 and N , B be the smallest integers satisfying the conditions of Corollary 3.5 (if K is a primepower cyclotomic eld) or Corollary 3.4 (in the generic case). 2: Sample p1, • • • , pN uniformly among all prime ideals of norm ≤ B.

3: Sample

(xσ)σ ← D round ε 1 ,ε 2 ,s for ε1 = 2 -n /M and ε2 = 2 -n . 4: Dene L ∈ IdLatK to be L = (xσ)σ • L( N i=1 pi • a). 5: Sample c = (cσ)σ uniformly in {(xσ)σ : |xσ| = M , ∀σ}. 6: Let ς = N ( N i=1 pi • a) 1/n • ς and c = N ( N i=1 pi • a) 1/n • c. 7: Sample v ← G L,ς ,c . 8: return L(b) = v -1 • L ⊂ Ψ(K). D sample ς,M,a is statistically close to D perfect ς,M
. Looking forward, the distribution D sample ς,M,a will be the one obtained by randomizing the ideal a in the worst-case to average-case reduction.

Let a ⊂ K be any fractional ideal and ς, M > 0 be some parameters. Recall that G L,ς,c refers to the distribution obtained by running Klein's Gaussian sampling algorithm on lattice L with parameter ς and center c (see Proposition 2.14). The distribution D sample ς,M,a is obtained by running the following algorithm (Algorithm 2). Theorem 4.4. Let a ⊂ K be any fractional ideal and

ς ≥ 2 n+1 √ n • ∆ 1/(2n) • λ n (L(O K )). Assume we know a basis (b 1 , • • • , b n ) of L(O K )
and an LLL reduced basis of L(a), then there exists an algorithm sampling from the distribution D sample ς,M,a in time polynomial in size(N (a)), log ∆, max i log b i , log M and log ς. Furthermore, the statistical distance between the distributions D sample ς,M,a and D perfect ς,M is at most 2 -cn for some absolute constant c > 0.

The proof of this theorem is available in Appendix C.2.

The reduction

We can now prove our worst-case to average-case reduction, where the average-case distribution we consider is D perfect ς,M (for some well chosen parameters ς and M ).

Theorem 4.5. Let ς ≥ 2 n+1 √ n • ∆ 1/(2n) • λ n (L(O K )) and M ≥ 2 √ nς.
Assume we have a (randomized) algorithm A and real numbers γ ≥ 1 and p > 0 such that A solves γ-Hermite-SVP with probability at least p when given as input L(a) ← D perfect ς,M (where the probability is taken over the choice of a and over the randomness of A). Let T be an upper bound on the run time of A on any input.

Then there exists a randomized algorithm A solving γ -Hermite-SVP in any fractional ideal L(a) with probability at least p-n -ω (1) (where the probability is taken over the randomness of A ), for an approximation factor

γ = O(B N/n ) • γ ≤      O n 1/2 • γ for prime power cyclotomic elds (assuming h + K ≤ (log n) n ) O n 1-n C /n • ∆ 1/(2n)
• γ for arbitrary number elds.

The run time of A is bounded by

T + poly(log ∆, max i log b i , size N (a), log ς, log M ), where (b 1 , • • • , b n ) is a known basis of L(O K ).
Remark 4.6. Observe that from Theorem 4.4, one can sample in time polynomial in log ∆, max i log b i , log s and log M from a distribution D sample ς,M,O K whose statistical distance to D perfect

ς,M is at most 2 -Ω(n) .
This gives us the following upper bound on the product

v ∞ • v -1 ∞ : v ∞ • v -1 ∞ ≤ N ( N i=1 p i • a) 1/n • (M + √ n • ς) N ( N i=1 p i • a) 1/n • (M - √ n • ς) = 1 + √ n • ς/M 1 - √ n • ς/M ≤ 3, by choice of M ≥ 2 √ n • ς. To compute a bound on x ∞ • x -1
∞ , recall that x is sampled from a distribution that is statistically close to E ε1 (G H,s ), for ε 1 and s as in Algorithm 2. Let y = (y σ ) σ be sampled from G H,s . Recall that by Lemma 4.3, it holds that E ε1 (y)/e y -1 ∞ ≤ ε 1 ≤ 1/2. In particular, for a xed coordinate σ we have that

e yσ /2 ≤ |E ε1 (y) σ | ≤ 2e yσ , which implies E ε1 (y) ∞ • 1 E ε1 (y) ∞ ≤ 4e 2 y ∞ .
Since y is chosen from an n-dimensional continuous Gaussian distribution of parameter s, we know that y ∞ ≤ (log n) 2 • s except with probability at most 2 -Ω((log n) 2 ) = n -ω (1) . Using the fact that s • (log n) 2 ≤ 1, we conclude that, except with probability at most n -ω (1) , it holds that

x ∞ • x -1 ∞ ≤ 4e (log n) 2 •s ≤ 11.
We nally obtain that

γ = 33 • B N/n • γ.
Plugging in the values of B and N from Corollary 3.5 in the prime power cyclotomic case or the ones from Corollary 3.4 in the generic case concludes the proof.

A Number-theoretic computations

Lemma A.1. Let Log O * K ⊆ H ⊆ log K R be the logarithmic unit lattice. Then the covolume of this lattice in H equals

√ n • 2 -n C /2 • R.
Proof. In the literature, often one uses the embedding

Log O * K ⊆ H ⊆ R n R +n C
, where (Log (η)) σ equals log |σ(η)| or 2 log |σ(η)|, depending on whether σ is real or complex. The space H = {x ∈ R n R +n C | j x j = 0} is the equivalent hyperplane. It is evident that the linear map

A : R +1 → Log K R , e ν →
e σν when ν is real

1 2 (e σν + e σν ) when ν is complex maps Log O * K ⊆ H to Log O * K ⊆ H. Let U be a basis of Log O *
K , and denote U by the same basis, but the last row removed; the determinant of U is called the regulator R of the number eld K. Dene B : R → R +1 , e j → e j -e n R +n C . By the fact that for any element in Log O * K holds that the sum of the entries equals zero, we have

BU = U . As A maps Log O * K to Log O * K , we obtain that ABU is a basis of Log O * K . The covolume of this basis equals det(B T A T AB) det(U ) = det(B T A T AB)R = √ n2 -n C /2 R.
The last equality is proven by the computation of det(B T A T AB) below. Note that A T A = diag(1, . . . , 1, 1/2, . . . , 1/2), where the 1 is repeated n R times and the 1/2 is repeated n C times. Therefore,

B T A T AB = J + 1 2 1 • 1 T , where J = diag(1, . . . , 1 n R , 1/2, . . . , 1/2 n C -1
).

and 1 is the all-one vector of dimension . Using the Weinstein-Aronszajn identity, we obtain

det(B T A T AB) = det(J + 1/2 • 1 • 1 T ) = det(J)(1 + 1/2 • 1 T J -1 1) = 2 -n C +1 (1 + 1 2 (n R + 2n C -2)) = 2 -n C • n Lemma A.2. Let H ⊆ Log(K R )
be the hyper plane orthogonal to the all-one vector, and let ρ (n) s be the Gaussian function. Then

x∈H s -ρ (n) s (x)dx = 1
Proof. Use the matrices A and B from the previous lemma to apply integration by substitution, observing that

H = ABR . x∈ABR s -ρ (n) s (x)dx = det(B T A T AB) x∈R s -ρ (n) s (ABx)dx = det(D T D) x∈R s -e -πx T D T Dx/s 2 dx = x∈R s -e -πx T x/s 2 dx = 1
Where D T D = B T A T AB T is the -dimensional Cholesky decomposition, and the last equality follows then again by integration by substitution.

Lemma A.3. Assume the Extended Riemann Hypothesis, and let π K (y) the number of prime ideals in a number eld K with norm bounded by y. Let furthermore x > max((12 log ∆ + 8n + 28) 4 , 3 • 10 11 ). Then

π K (x) ≥ x 2 • log x .
Proof. By simplifying an explicit result of Grenié and Molteni [21, Cor. 1.4], we obtain

π K (x) -π K (3) - x 3 du log u ≤ √ x[6 log ∆ + 4n log x + 14].
Therefore, we have

π K (x) ≥ x 3 du log u - √ x[6 log ∆ + 4n log x + 14] ≥ x log x 1 -log(x) 2 (6 log ∆+4n+14) √ x ≥ x 2 log
x , where the rst inequality follows from omitting π K (3) and the second inequality from x 3 du ln u ≥ x ln x and from the assumption that x > 2 4 • (6 log ∆ + 4n + 14) 4 and x > 3 • 10 11 . Note that with such x, we have

ln(x) 2 / √ x < x -1/4
, so that ln(x) 2 (6 log ∆+4n+14)

√ x < 1/2.
N ≥ (n -n C )(log n) 2 log(∆) 1 + 30 log log n log n + n log n log ∆ 1 2 log(∆ 1/n ) + log log(∆ 1/n )
holds that the random walk distribution

W Pic 0 K (B, N, s) satises SD W Pic 0 K (B, N, s), U(Pic 0 K ) ≤ 2 -n .
Proof. We instantiate Theorem 3.3 with = 2 -n , k = log(∆)/(2(log n) 2 ) and s > 1/ . We assume throughout the proof that > 1. By the fact that

η 1 (Λ * K ) ≤ √ λ1(Λ K ) [ 32, Lemma 3.2]
and a general upper bound 1/λ 1 (Λ K ) ≤ 1000 √ + 1 log( ) 3 by Kessler [START_REF] Kessler | On the minimum of the unit lattice[END_REF], we obtain

1/s = max( 1 √ 2s , η 1 (Λ * K )) ≤ max( 1 √ 2s , √ /λ 1 (Λ K )) ≤ 2000 log( ) 3 .
The quantities log(log(1/ε)) and log(1/s ) occurring in B of Theorem 3.3 can (as they are in O(log n)) therefore be put in the polylogarithmic factors. We obtain B = Õ(n 2k log(∆) 2 ) = Õ(∆ 1/ log n ), using the instantiation k = log(∆)/(2(log n) 2 ).

Putting llog(x) = max(log(log x), 1), and noting that log( ) -1 ≤ 2 log(n) -1 for > 1, we have

log(1/s ) ≤ [log( ) + 3 llog( ) + log(2000)] ≤ log 1 + 22 • llog(n) log n , log(Vol(Pic 0 K )) ≤ n 2 [log ∆ 1/n +2 log(log(∆ 1/n )) + 2] and log(1/ε) ≤ n ≤ 2 .
Combining these, we obtain the sucient lower bound

N ≥ n -n C 2k 1 + 30 llog n log n + n 2k log n 1 2 log ∆ 1/n + log log ∆ 1/n .
This bound is obtained by simplifying the bound below by applying 1 ≤ llog(x) and

≤ n -n C . 2k [1 + 22 llog n log n /2•log(1/s ) + 4 + 2/ log n log(1/ε)+1 ] + n 2k log(n) [ 1 2 log ∆ 1/n + log(log(∆ 1/n ))) + 1 log(Pic 0 K )/2 ] Instantiating k = log(∆)/(2(log n) 2 ) yields the result.
B.2 Proof of Corollary 3.5

Corollary 3.5. Let K = Q(ζ p k ) be a prime-power cyclotomic number eld and assume h +

K = Cl(K + ) ≤ (log n) n . For s = 1/ log 2 (n), there exists a bound B = O(n 2+2 log n ) such that, for N ≥ n 2 log n 1/2 + 8 log(log(n)) log n , the random walk distribution W Pic 0 K (B, N, s) satises SD W Pic 0 K (B, N, s), U(Pic 0 K ) ≤ 2 -n .
Proof. The proof consists of three parts. In the rst part we prove stronger version of Theorem 3.3, specicially tailored to prime-power cyclotomic elds. In this stronger version, the part in N that depends on 1/s can be made negligible, with the caveat that h + K (the class number of the maximum real subeld of K) pops up as an extra factor in the error analysis. In the second part we prove bounds on log(1/s ), log(∆) and log(ε). In the third and last part of the proof we combine these bounds to obtain a sucient lower bound for N . Throughout the proof we assume that n ≥ 10.

Part 1. The group of units of a cyclotomic elds contains a subgroup of cyclotomic units, which are units that have a specic compact shape [START_REF] Washington | Introduction to cyclotomic elds[END_REF]Ch. 8]. One can take the Logarithmic map of these cyclotomic units, obtaining the logarithmic cyclotomic unit lattice C ⊆ Λ K , for which holds [Λ K : C] = h + K [START_REF] Washington | Introduction to cyclotomic elds[END_REF]Thm. 8.2]. For our purposes it is useful to look at the dual lattice C * ⊇ Λ * K , because we have the following sequence of bounds, due to [START_REF] Micciancio | Worst-case to average-case reductions based on gaussian measures[END_REF]Lemma 3.3] and [START_REF] Cramer | Recovering short generators of principal ideals in cyclotomic rings[END_REF]Thm. 3.1] respectively.

η 1 (C * ) ≤ log(4 )λ (C * ) ≤ O(log( ) 5/2 • -1/2 ) Therefore, whenever 1/( √ 2s) ≥ O(log( ) 5/2 • -1/2 ), we have det(Λ K )ρ 1 √ 2s (Λ * K ) ≤ h + K det(C)ρ 1 √ 2s (C * ) ≤ 2h + K ( √ 2s
) .

This means that we can apply Theorem 3.3 on cyclotomic elds with s = min( √ 2s, O( √ / log 5/2 ( ))) and

N ≥ /2•log(1/s )+ 1 2 log(Vol(Pic 0 K ))+log(1/ε)+log(h + K )+1 k log n .
Part 2. Note that we assumed that s = 1/ log(n) 2 . By Part 1 of this proof and the fact that = n/2 for cyclotomic elds, this directly implies that 2 log(1/s ) ≤ n 2 log log(n). Per denition, log(1/ε) = log(2)n and per assumption log(h + K ) ≤ n log log(n). By Lemma 2.3 and the fact that log ∆ ≤ n log(2n) for cyclotomic elds, we directly obtain (assuming n ≥ 10) + log(log(n))

log(Vol(Pic 0 K ))/2 ≤ n 2 [log(2n)/2 + log log(2n) + 1] ≤ n 2 [log(n)/2 + 3 log log(n)] (12
log h + K + log(2) log(1/ε) +1] ≤ n
λ χ = O log(B) log(B n • ∆ • q ∞ (χ)) B 1/2 ,
where q ∞ (χ) is the innite part of the analytic conductor of the character χ, as in Denition 3.11 (cf. In order to apply analytic number-theoretic results, we need to eliminate the non-split primes of the number eld from the character sums arising in the eigenvalues of the Hecke operator. This happens in the following lemma, whose proof follows exactly the outline as in [47, Cor.

Proof. Any nonzero entry χ(a)[M(a) -M(a)] arise from an ideal a that is a power of a prime ideal and that does not have prime norm. As there are at most n = [K : Q] prime ideals above each prime number, we see that the left side of Equation ( 13) must be bounded by

n p ≤B ≥2 ln(p) ≤ n p≤ √ B 2≤ ≤ ln B ln p ln(p) ≤ n p≤ √ B ln ln B ln = nπ(B 1/2 ) ln B = O(nB 1/2 ),
where π is the prime counting function and where the last bound is obtained by the prime number theorem (see Theorem 2.1).

Proof (of Proposition 3.8). Assuming the Extended Riemann Hypothesis, we have the following classical analytic result 13 [22, Thm 5.15] for any non-trivial charakter χ ∈ Pic 0 K .

N (a)<B M(a)χ(a) = O(B 1/2 log(B) log(B n ∆ • q ∞ (χ))),
where q ∞ (χ) is the innite part of the analytic conductor of χ, and where M is the von Mangoldt function for the number eld K.

According to Lemma B.2, the sums N (a)≤B χ(a) M(a) and N (a)≤B χ(a)M(a) dier at most O(nB 1/2 ), and therefore

A(B) := 2≤n≤B a n = N (a)≤B χ(a) M(a) = O(B 1/2 log(B) log(B n ∆ • q ∞ (χ)))
where a n = N (a)=n χ(a) M(n) and where M(n) = log n whenever n is prime and zero otherwise. Using the Abel partial summation formula, we deduce

N (p)≤B χ(p) = n≤B a n 1 log n = A(B) log B + B 2 A(t) dt t log 2 (t) = O(B 1/2 log(B n ∆ • q ∞ (χ))) + O B 2 log(t n ∆ • q ∞ (χ)) log(t)t 1/2 dt = O(B 1/2 log(B n ∆ • q ∞ (χ)))
where the last equality uses

B 2 log(t n A) log(t)t 1/2 dt ≤ log(B n A)/ log(2) B 2 t -1/2 dt = O(log(AB n )• √ B). As χ•[d 0 (•)] : I K → C is
λ χ = 1 |P| p∈P χ(d 0 (p)) = 1 |P| O(B 1/2 log(B n ∆ • q ∞ (χ))) = O(B -1/2 log(B) log(B n ∆ • q ∞ (χ)))
which nishes the proof.

E ε1 (y) • (e -yσ ) σ -1 ∞ ≤ ε 1 .
Furthermore, for any s > 0, one can sample in time polynomial in n, max i log b i , s, log(1/ε 1 ) and log(1/ε 2 ) from a distribution D round ε1,ε2,s that is

ε 2 close in statistical distance to E ε1 (G H,s ) (recall that (b 1 , • • • , b n ) is a known basis of L(O K )).
Proof. Algorithm 4 below describes the function E ε1 and provides an ecient way of computing it. This algorithm denes three integers N 1 , N 2 and N 3 , that represent the number of bits of precision used at dierent steps of the algorithm. They are chosen so that the function E ε1 satises the desired requirement E ε1 (y) • (e -yσ ) σ -1 ∞ ≤ ε 1 for all y ∈ H.

The last two steps of the algorithm simply consists in rounding the element x 1 ∈ K R to a close element in Ψ(K). We observe rst that the algorithm indeed output an element in Ψ(K), because x 2 ∈ Ψ(O K ). Also, one can see that if y has rational coecients (so that is can be nitely represented), then Algorithm 4 computes E ε1 (y) in time polynomial in n, y ∞ , size(y), log(1/ε 1 ) and max i log b i . The fact that E ε1 can be eciently computed when the input has bounded size will be used in the description of the distribution D round ε1,ε2,s .

Let us now x an arbitrary input y = (y σ ) σ ∈ H and compute an upper bound on E ε1 (y) • (e -yσ ) σ -1 ∞ . For a given embedding σ, we have that |y σ -y σ | ≤ 2 -N1 . Going to Step 2, we have that 14 The function Eε 1 plays the role of the exponential function, rounded to a near element of K.

|x 1,σ -e yσ | ≤ |x 1,σ -e yσ | + |e yσ -e yσ | ≤ 2 -N2 + e yσ • |e yσ-yσ -1| ≤ 2 -N2 + e yσ • 2 • | y σ -y σ | ≤ 2 -N2 + e yσ • 2 1-N1 ,

Algorithm 4 The function E ε1

Require: An element y = (yσ)σ ∈ H and a basis (b1, • • • , bn) of Ψ(OK ) in K R . Ensure: An element x ∈ Ψ(K).

1:

Dene N2 = 2 + ( (yσ)σ ∞ + log(1/ε1))/ log(2), N1 = N2 + (yσ)σ ∞/ log(2) + 1 and N3 = N2 • log( i bi ∞)/ log(2) 2: Compute y = ( 2 N 1 yσ 2 N 1
)σ (rounding of y with N1 bits of absolute precision) 3: Compute x1 ∈ K R to be (e yσ )σ where every exponential function is computed with 2 N 2 bits of absolute precision [START_REF] Bach | Algorithmic Number Theory: Ecient Algorithms[END_REF] we see that the upper bound is equal to 2 -N2 . Combining it with our previous bound x 1 -(e yσ ) σ ∞ ≤ 2 -N2+1 , we obtain that

, x-x 1 ∞ ≤ 2 -N3 • i b i ∞ . Using the equation N 3 = N 2 •log( i b i ∞ )/ log
x -(e yσ ) σ ∞ ≤ 2 -N2+2 .
This implies that for any coordinate σ, we have

x σ e yσ -1 ≤ 2 -N2+2 e yσ .
Plugging in the denition of N 2 , we nally obtain the desired bound.

Let us now describe the distribution D round ε1,ε2,s . Recall that we want this distribution to be close to the distribution E ε1 (G H,s ) and to be eciently samplable. The only thing that prevents us from sampling an element y ∈ H using the distribution G H,s and then computing E ε1 (y) is the fact that the distribution G H,s is continuous, and so one cannot eciently sample from this distribution (also, the element y would have real coecients that cannot be nitely represented). In order to circumvent this diculty, we simply sample ŷ from a distribution statistically close to a rounded Gaussial distribution over H. We will choose a rounded Gaussian distribution with N1 > N 1 bits of absolute precision so that the rounding to N 1 bit in the second step of E ε1 provides a distribution statistically close to the one we would have obtained if we had started with a continuous Gaussian distribution.

Let t > 0 be such that, if y is sampled from a continuous n-dimensional Gaussian distribution of parameter s, it holds that y ∞ ≤ t • s except with probability at most ε 2 /2. We know that there exists such a t bounded by poly(n, log(1/ε 2 )) (and it can be eciently computed). Let N1 = 3 + (2t • s + log(1/ε 1 ))/ log(2) (this choice corresponds to the denition of the integer N 1 in Algorithm 4, except that y ∞ has been replaced by t • s).

For a distribution D and an integer N , let us write D N the distribution obtained by sampling y ← D and rounding every coordinate of y with N bits of absolute precision. Let Dε2,H,s, N1 be a distribution that is ε 2 /2 statistically close to G H,s N1 . We know that there exist such distributions Dε2,H,s, N1 that can be sampled in time polynomial in log(1/ε 2 ), n, N1 and s. , G H,s ) ≤ ε 2 /2, which implies in particular that SD( G tail-cut

H,s N1 , G H,s N1 ) ≤ ε 2 /2.
Combining everything together, we nally obtain that

SD( G H,s N1 , Dtail-cut ε2,H,s, N1 N1 ) ≤ ε 2 .
The rst distribution corresponds to the distribution of y when computing E ε1 (y) for y ← G H,s , whereas the second one corresponds to the distribution of y when computing E ε1 (ŷ) for ŷ ← Dtail-cut ε2,H,s, N1

. Since the rest of the computation of E ε1 only depends on y, we conclude that the statistical distance between E ε1 (G H,s ) and E ε1 ( Dtail-cut ε2,H,s, N1

) is no more that ε 2 . We conclude by observing that the second distribution is exactly D round ε1,ε2,s .

To conclude the proof, it remains to prove that D round ε1,ε2,s can be eciently sampled. The rst step of Algorithm 5 can be performed in expected time polynomial in log(1/ε 2 ), n, N1 and s. Recall that if ŷ has rational coecient (which is the case here), then E ε1 (ŷ) can be computed in time polynomial in n, ŷ ∞ , size(ŷ), log(1/ε 1 ) and max i log b i . Plugging in the value of N1 and the upper bound on ŷ ∞ , we obtained the desired result. Proof. Run time. We show that Algorithm 2 used above to describe the distribution D sample ς,M,a also provides an ecient way of sampling it. At Step 2, we use Lemma 2.2 to sample the primes p i in time polynomial in N and log B. With our choice of N and B, this is polynomial in log ∆. In Step 3, we use the distribution D round ε1,ε2,s previously dened, which we have seen can be sampled in time polynomial in n, log(M ) and max i log b i (where we used the fact that log(1/ε 1 ) and log(1/ε 2 ) are polynomial in n, log(M ) and that s ≤ 1). In Step 4, computing a basis of the ideal lattice L can be done in time polynomial in N , log B, size(N (a)) and size(x). We know that the size of x is bounded by the time needed to compute it (in Step 3). By denition of N and B, we conclude that Step 4 is polynomial in log ∆, log(a) and max i log b i . In Step 5, sampling c can be done in time polynomial in n. Finally, Klein's algorithm can be run in time polynomial (in the size of the basis and in log ς), and computing a basis of v -1 • L is also polynomial in all the previous quantities. We conclude that Algorithm 2 runs in time polynomial in log ∆, max i log b i , size(N (a)) and log ς (using the fact that n = O(log ∆)). . We show that for i ∈ {0, • • • , 6}, the statistical distance between D i and D i+1 is at most 2 -Ω(n) , which will conclude the proof by triangle inequality. All the intermediate distributions that we introduce here are only used for the proof and so they do not need to be computable (the algorithms are used only to describe them and not to compute them). Distribution D 1 . Algorithm 6 below denes a distribution D 1 (depending on the ideal a). Let us show that Algorithm 6 Distribution D 1 Require: A fractional ideal a ⊂ K and two parameters ς, M > 0 Ensure: A fractional ideal lattice 1: Let s = 1/(log n) 2 and N , B be the smallest integers satisfying the conditions of Corollary 3.5 or 3.4.

Statistical distance. Let us now x an ideal a and a parameter

ς ≥ 2 n+1 √ n • ∆ 1/(2n) • λ n (L(O K ))

2: Sample

[a] ← W Pic 0 K (B, N, ς) 3: Dene [a ] = [a] + [d 0 (a)] 4: return Extractς,M ([a ]) SD(D 0 , D 1 ) ≤ 2 -n . Recall that D 0 = Extract ς,M (U(Pic 0 K )).
Hence, it is sucient to show that the statistical distance between the distribution of [a ] in Algorithm 6 and the uniform distribution over Pic 0 K is bounded by 2 -n . This is true by Corollary 3.4 or Corollary 3.5 (thanks to our choices of B and N ) and using the fact that U(Pic 0 Let us bound the two terms of the sum above. We will use Corollary 2.13 to bound the rst term. In to do so, we need to have an upper bound on the volume of the lattices L 3 and L 4 . The volume of L 3 satises Vol(L 3 ) = √ ∆ (since L 3 = L(a ) for some a ∈ Div 0 K ). To compute the volume of L 4 , recall that L 4 = zL 3 and hence

K ) + [d 0 (a)] = U(Pic 0 K ).
Vol(L 4 ) = σ |z σ | • Vol(L 3 ) ≤ (1 + 2 -n ) n • √ ∆ ≤ 2 • √ ∆.
We then conclude that the condition of the theorem implies ς ≥ n • λ n (L(O K )) • max(Vol(L 3 ) 1/n , Vol(L 4 ) 1/n ), and so we can apply Corollary 2.13 to the lattices L 3 and L 4 . Doing so, we obtain

log ρ ς (L 4 -c) ρ ς (L 3 -c) ≤ log 1 + 2 -Ω(n) 1 -2 -Ω(n) • Vol(L 3 ) Vol(L 4 ) ≤ log 1 + 2 -Ω(n) - σ log |z σ | ≤ 2 -Ω(n) + n • 2ε 1 = 2 -Ω(n) .
Let us now consider the second term v∈L3 Pr(G L3,ς,c = v) • π( zv-c 2 -v-c 2 )

ς 2
. For any v ∈ L 3 , is holds that

zv -c 2 -v -c 2 = ( zv -c + v -c ) • | zv -c -v -c | ≤ ( zv -zc + zc -c + v -c ) • zv -v using both triangle inequalities ≤ (( z ∞ + 1) • v -c + z -1 ∞ • c ) • z -1 ∞ • v ≤ (3 • v -c + ε 1 c ) • ε 1 • ( v -c + c ) ≤ ε 1 • (3 • v -c 2 + 4 • v -c • c + ε 1 c 2 ) ≤ ε 1 • (3 • v -c 2 + 4 √ n • M • v -c + ε 1 • n • M 2 ) ≤ 2 -Ω(n) • ( v -c 2 + v -c ) by choice of ε 1 ≤ 2 -Ω(n) • ( v -c 2 + 1)
Going back to the sum, we obtain

v∈L3 Pr(G L3,ς,c = v) • π( zv -c 2 -v -c 2 ) ς 2 ≤ 2 -Ω(n) ς 2 • v∈L3 Pr(G L3,ς,c = v) • v -c 2 + v∈L3 Pr(G L3,ς,c = v) = 2 -Ω(n) ς 2 • E v←G L 3 ,ς,c ( v -c 2 ) + 1
Using the fact that ς ≥ n log(n) • λ n (L(O K )) • ∆ 1/(2n) and Lemma 2.8, we see that s ≥ √ log n • λ n (L). Combining Lemmas 3.3 and 4.3 of [START_REF] Micciancio | Worst-case to average-case reductions based on gaussian measures[END_REF] (instantiated at = 1/2), we nally obtain

E v←G L 3 ,ς,c ( v -c 2 ) ≤ 2nς 2 .
it with the previous bound, we nally obtain

v∈L3 Pr(G L3,ς,c = v) • π( zv -c 2 -v -c 2 ) ς 2 ≤ 2 -Ω(n) ,
which conclude the bound on the KullbackLeibler divergence of G L3,ς,c and z -1 • G L4,ς,c . We nally obtain a bound on the statistical distance SD(G L3,ς,c , z -1 • G L4,ς,c ) ≤ 2 -Ω(n) using Equation ( 14), which we have seen implies SD(D 3 , D 4 ) ≤ 2 -Ω(n) . , D sample ς,M,a ) ≤ 2 -Ω(n) for any fractional ideal a. It can be checked that all the constant appearing in the Ω(n) during the proof are absolute.

2

 2

Lemma 3 . 10 .

 310 Let χ ∈ Pic 0 K and let * ∈ Λ * K such that χ| T = χ * = e 2πi * ,• . Then we have k ν (χ) = 2πi * σν , where σ ν is an embedding associated with the place ν.

2 =

 2 ρ s and s -ρ s | T can be seen as probability distributions on their respective domains R m and T .Lemma 3.15 (Fourier coecients of the periodized Gaussian). The function s-ρ s | T ∈ L 2 (T ) satises s -ρ s | T = * ∈Λ * K a * χ *where a * = 1 Vol(T ) ρ 1/s ( * ), where Λ * K is the dual lattice of the log unit lattice Λ K , and where χ * (x) = e -2πi x, * . Proof. Note that χ * 1 , χ * Vol(T ) • δ * 1 , * 2 . Identifying T and Λ * K via the map χ * → * , taking a fundamental domain F of Λ K and spelling out the denition of ρ s |

4

 4

  distribution D sample ς,M,a is parameterized by parameters ς, M > 0 (the same as for D perfect ς,M

B Proofs from Section 3 B. 1 4 Corollary 3 . 4 .

 31434 Proof of Corollary 3.Let s > 1/ , there exists a bound B = Õ(∆ 1/ log n ) such that for

) Part 3 . 1 2

 31 Combining all the bounds of Part 2 of this proof we deduce that the bound B = Õ(n 2+2k ) and the lower bound N ≥ n 2k + 8 log(log(n)) log n suce. The last bound is obtained by the following simplication n 2k log(n) [log(log(n)) log(1/s )/2 + log(n)/2 + 3 log log(n) log(Vol(Pic 0 K ))

1

 1 We denote by M : I K → N the von Mangoldt function for number elds K. The value M(a) equals log(N (p)) whenever a is a power of a prime ideal p and zero otherwise. We also dene the function M : I K → N, for which M(a) = log(N (a)) whenever N (a) is prime and zero otherwise.

  2.3.5]. Lemma B.2. For any character χ : I K → C, we have N (a)≤B χ(a)M(a) -N (a)≤B χ(a) M(a) = O(n √ B)

  a Hecke character on ideals, and |P| = Θ(B/ log(B)) (see Theorem 2.1), we have

4 :

 4 Write 2 N 3 x1 as i zibi with zi ∈ R and compute x2 = i zi bi ∈ OK (This is Babai round-o algorithm in Ψ(O K ) using the basis (bi)i with target2 N 3 x1) 5: Compute x = 2 -N 3 • x2 6: return xwhere we used the fact that for anyx ∈ [-1, 1], it holds that |e x -1| ≤ 2 • |x|. Using the fact that N 1 = N 2 + (y σ ) σ ∞ / log(2) + 1,we then have |x 1,σ -e yσ | ≤ 2 -N2+1 for all coordinates. Going to Step 3 and 4, we have, after Babai's rounding

C. 2 4 Theorem 4 . 4 .

 2444 Proof of Theorem 4.Let a ⊂ K be any fractional ideal and ς ≥ 2 n+1 √ n • ∆ 1/(2n) • λ n (L(O K )). Assume we know a basis (b 1 , • • • , b n ) of L(O K ) and an LLL reduced basis of L(a), then there exists an algorithm sampling from the distribution D sample ς,M,a in time polynomial in size(N (a)), log ∆, max i log b i , log M and log ς. Furthermore, the statistical distance between the distributions D sample ς,M,a and D perfect ς,Mis at most 2 -cn for some absolute constant c > 0.

  and prove that the distributions D sample ς,M,a and D perfect ς,M are statistically close. We do so by introducing intermediate distributions D 1 up to D 6 . Let us call D 7 := D sample ς,M,a and D 0 = D perfect ς,M

Distribution D 2 . 2 : 2 :

 222 Algorithm 7 below denes a distribution D 2 . This distribution is the same as D 1 . Indeed, Algorithm 7 Distribution D 2 Require: A fractional ideal a ⊂ K and two parameters ς, M > 0 Ensure: A fractional ideal lattice 1: Let s = 1/(log n) 2 and N , B be the smallest integers satisfying the conditions of Corollary 3.5 or 3.4. Sample a ← W Div 0 K (B, N, ς) 3: Dene a = a + d 0 (a) 4: Dene L = L(a ) 5: return Extractς,M (L) recall that for any a ∈ Div 0 K , we have P (L(a)) = [a] (where P is dened in Lemma 2.7). Hence, by denition of W Div 0 K , W Pic 0 K , it holds that P (L) in Algorithm 7 has the same distribution as [a ] in Algorithm 6. Using the fact that Extract ς,M (P (L)) = Extract ς,M (L) (as distributions), we conclude that D 1 = D 2 . Distribution D 3 . Algorithm 8 below denes a distribution D 3 . Distribution D 3 is exactly the same as Algorithm 8 Distribution D 3 Require: A fractional ideal a ⊂ K and two parameters ς, M > 0 Ensure: A fractional ideal lattice 1: Let s = 1/(log n) 2 and N , B be the smallest integers satisfying the conditions of Corollary 3.5 or 3.4. Sample p1, • • • , pN uniformly among all prime ideals of norm ≤ B. 3: Sample (yσ)σ ← GH,s 4: Dene L ∈ IdLat 0 K to be L = (e yσ / N ( N i=1 pi • a) 1/n )σ • L N i=1 pi • a . 5: return Extractς,M (L) Distribution D 2 , except that we made explicit the denitions of W Div 0 K (B, N, ς), d 0 (•) and L(•).

Algorithm 9 Distribution D 4 2 :| 2 d

 422 Require: A fractional ideal a ⊂ K and two parameters ς, M > 0 Ensure: A fractional ideal lattice 1: Let s = 1/(log n)2 and N , B be the smallest integers satisfying the conditions of Corollary 3.5 or 3.4. Sample p1, • • • , pN uniformly among all prime ideals of norm ≤ B.3: Sampley := (yσ)σ ← GH,s 4: Dene L ∈ IdLat 0 K to be L = (Eε 1 (y)/ N ( N i=1 pi • a) 1/n )σ • L N i=1 pi • a ,where ε1 = 2 -n /M . 5: return Extractς,M (L) Distribution D 4 . Algorithm 9 below denes a distribution D 4 . The only dierence between distributions D 3 and D 4 is in the denition of the lattice L. In distribution D 3 , the lattice L is obtained using (e yσ ) σ , whereas in distribution D 4 we use E ε1 ((y σ ) σ ).Let us x some idealsp 1 , • • • , p N and an element y ∈ H. Let us dene L 3 = (e yσ / N ( N i=1 p i • a) 1/n ) σ • L N i=1 p i • a as in D 3 and L 4 = (E ε1 (y)/ N ( N i=1 p i • a) 1/n ) σ • L N i=1 p i • a as in L 4 . If we show that SD(Extract ς,M (L 3 ), Extract ς,M (L 4 )) ≤ 2 -n ,then this will hold for any choices of p i and y, and we will have the desired result SD(D 3 , D 4 ) ≤ 2 -n .By denition of L 3 and L 4 , it holds that L 4 = zL 3 for z = E ε1 (y)/(e yσ ) σ . Besides, by Lemma 4.3 (and by choice ofε 1 = 2 -n /M ), we know that z -1 ∞ ≤ 2 -n /M.Let us now enfold the denition of Extract ς,M . To simplify notations, we writeC = {(x σ ) σ ∈ K R : |x σ | = M , ∀σ} SD(Extract ς,M (L 3 ), Extract ς,M (L 4 )) Pr(Extract ς,M (L 3 ) = L(a)) -Pr(Extract ς,M (L 4 ) = L(a))| )=v -1 •L3 Pr(G L3,ς,c = v) -v∈L4: L(a)=v -1 •L4 Pr(G L4,ς,c = v) dc Vol(C)Observe now that multiplication by z gives us a bijection between the sets {v ∈ L3 s.t. L(a) = v -1 • L 3 } and {v ∈ L 4 s.t. L(a) = v -1 • L 4 }. Hence, we obtain SD(Extract ς,M (L 3 ), Extract ς,M (L 4 )) =v -1 •L3 (Pr(G L3,ς,c = v) -Pr(G L4,ς,c = zv)) =v -1 •L3 |Pr(G L3,ς,c = v) -Pr(G L4,ς,c = zv)L3,ς,c = v) -Pr(G L4,ς,c = zv)| = sup c∈C SD(G L3,ς,c , z -1 • G L4,ς,c ).Let us x an arbitrary c ∈ C. In order to upper bound the statistical distance between the two distributions G L3,ς,c and z -1 • G L4,ς,c , we will bound their Kullback-Leibler divergence. The Kullback-Leibler divergence of two discrete random variables X and Y over the same set S and such that P(Y = x) > 0 for all x ∈ S is dened asd KL (X Y ) = s∈S P(X = s) • log P(X = s) P(Y = s).It satises the following relation with the statistical distanceSD(X, Y ) ≤ 1 KL (X Y ).(14)Going back to our random variables G L3,ς,c and z -1 • G L4,ς,c , we haved KL (G L3,ς,c z -1 • G L4,σ,s ) = v∈L3 Pr(G L3,ς,c = v) • log ρ ς (v -c) ρ ς (L 3 -c) • ρ ς (L 4 -c) ρ ς (zv -c) = log ρ ς (L 4 -c) ρ ς (L 3 -c) + v∈L3 Pr(G L3,ς,c = v) • π( zv -c 2 -v -c 2 ) ς 2

Distribution D 5 . 2 : 2 :

 522 Algorithm 10 below denes a distribution D 5 . The only dierence between distributions Algorithm 10 Distribution D 5 Require: A fractional ideal a ⊂ K and two parameters ς, M > 0 Ensure: A fractional ideal lattice 1: Let s = 1/(log n) 2 and N , B be the smallest integers satisfying the conditions of Corollary 3.5 or 3.4. Sample p1, • • • , pN uniformly among all prime ideals of norm ≤ B.3: Samplex := (xσ)σ ← D round ε 1 ,ε 2 ,s for ε1 = 2 -n /M and ε2 = 2 -n . 4: Dene L ∈ IdLat 0 K to be L = (x/ N ( N i=1 pi • a) 1/n )σ • L( N i=1 pi • a). 5: return Extractς,M (L) D 4 and D 5 is that x is sampled as D round ε1,ε2,s in D 5 whereas it is sampled as E ε1 (G H,s ) in D 4 . We have proved in Lemma 4.3 that the statistical distance between D round ε1,ε2,s and E ε1 (G H,s ) is bounded by ε 2 = 2 -n . Hence we conclude that SD(D 4 , D 5 ) ≤ 2 -n .Distribution D 6 . Algorithm 11 below denes a distribution D 6 . This distribution is the same as distribution D 5 except that the lattice L has been scaled by N (N i=1 p i •a) 1/n (so that L ⊂ Ψ(K)).The standard deviation and the center of the Gaussian distribution used in the Extract procedure have also been multiplied by N ( N i=1 p i • a) 1/n . Hence, the distribution is unchanged, i.e., we have D 6 = D 5 . Distribution D 7 . We now have our last distribution D 7 = D sample ς,M,a . The only dierence between distributions D 6 and D 7 is that the perfect Gaussian distribution in Extract used in D 6 is replaced by Klein's algorithm in D 7 . Recall from Proposition 2.14 that these two distributions have statistical distance at most 2 -n if the standard deviation ς satises ς ≥ √ n • max i c i for some known basis (c 1 , • • • , c n ) of L.Algorithm 11 Distribution D 6Require: A fractional ideal a ⊂ K and two parameters ς, M > 0 Ensure: A fractional ideal lattice 1: Let s = 1/(log n) 2 and N , B be the smallest integers satisfying the conditions of Corollary 3.5 or 3.4. Sample p1, • • • , pN uniformly among all prime ideals of norm ≤ B.3: Samplex := (xσ)σ ← D round ε 1 ,ε 2 ,s for ε1 = 2 -n /M and ε2 = 2 -n . 4: Dene L ∈ IdLatK to be L = (x)σ • L( N i=1 pi • a). 5: Let ς = N ( N i=1 pi • a) 1/n • ς and M = N ( N i=1 pi • a) 1/n • M . 6: return Extract ς ,M (L)In order to use Klein's algorithm in D 7 , we will use an LLL reduced basis of L, which can be computed in polynomial time. Such a basis(c 1 , • • • , c n ) satises max i c i ≤ 2 n λ n (L) ≤ 2 n √ n • λ n (L(O K )) • (2 • N ( N i=1 p i • a) • √ ∆) 1/n .We conclude that Proposition 2.14 holds as long as ς≥ 2 n+1 √ n • ∆ 1/(2n) • λ n (L(O K )). By choice of ς, we then have SD(D 6 , D 7 ) ≤ 2 -n .Conclusion.We have shown that SD(D i , D i+1 ) ≤ 2 -Ω(n) for all i ∈ {0, • • • , 6}, with D 0 = D perfect ς,M and D 7 = D sample ς,M,a . We conclude by triangle inequality that SD(D perfect ς,M

  ERH). Let π K (x) be the number of prime integral ideals of K of norm ≤ x. Then, assuming the Extended Riemann Hypothesis, there exists an absolute constant C (i.e., independent of K and x) such that Sampling of prime ideals, ERH). Let a basis of O K be known and let P = {p prime ideal of K | N (p) ≤ B} be the set of prime ideals of norm bounded by B ≥ max((12 log ∆ + 8n + 28) 4 , 3 • 10 11 ). Then one can sample uniformly from P in expected time O(n 3 log 2 B). . The sampling algorithm goes as follows. Sample an integer uniformly in [0, B] and check if it is a prime. If it is, factor the obtained prime p in O K and list the dierent prime ideal factors {p 1 , . . . , p k } that have norm bounded by B. Choose one p i uniformly as random in {p 1 , . . . , p k } and output it with probability k/n. Otherwise, output `failure'.

	Theorem 2.1 (|π K (x) -li(x)| ≤ C •	√	x (n log x + log |∆|) ,
	where li(x) = x 2	dt ln t ∼ x ln x .
	Lemma 2.2 (Proof
				3,
	assume the Extended Riemann Hypothesis.
	Prime densities In multiple parts of this paper, we need an estimate on the number of prime ideals
	with bounded norm. This is achieved in the following theorem, obtained from [2, Thm. 8.7.4].

  the uniform distribution over the Arakelov class group.

	Fourier theory over the Arakelov class group As the Arakelov class group Pic 0 K is a compact abelian group, every function in 6 L 2

  Proposition 3.8. Let P be the set of all primes of K with norm bounded by B ∈ N. Then the eigenvalue λ χ of any non-constant eigenfunction χ ∈ Pic 0 K of the Hecke operator satises

	B.3 Proof of Proposition 3.8
	2k	[1/2 +	8 log log n log n	] for n ≥ 10.
	Putting k = log(n) yields the claim.

  Lemma 4.3. For any ε 1 , ε 2 > 0, there exists a deterministic function 14 E ε1 : H → Ψ(K) such that for any y ∈ H it holds that

	C	Proofs from Section 4
	C.1 Proof of Lemma 4.3

  The distribution D round ε1,ε2,s is obtained as follows Let us prove that the distribution D round ε1,ε2,s is ε 2 close to E ε1 (G H,s ). To do so, let us introduce the two distributions Dtail-cut N1 and G H,s N1 conditioned on the output having innity norm at most t • s. Recall that SD( Dε2,H,s, N1 , G H,s N1 ) ≤ ε 2 /2. Then, by performing rejection sampling on the two distributions and rounding the output with N 1 bits of precision, we also have that SD( Dtail-cut Require: Three parameters ε1, ε2, s > 0 Ensure: An element of Ψ(K)1: Sample ŷ ← Dε 2 ,H,s, N1 until ŷ ∞ ≤ t • s (where t and N1 are as described above) 2: return Eε 1 (ŷ)Now, using the fact that N 1 ≥ N1 for an element output by the distribution G H,s

	Algorithm 5 The distribution D round ε1,ε2,s
					tail-cut N1	, one can
	see that the distribution G H,s	tail-cut N1	N1 is the same as G tail-cut H,s	N1 . By denition of t, we know that
	SD(G tail-cut H,s
	ε2,H,s, N1	and G H,s	tail-cut N1 , which corresponds to the distributions Dε2,H,s, ε2,H,s, N1 N1 , G H,s tail-cut N1 N1 ) ≤ ε 2 /2.

We here refer to the version of the scheme described in Chapters 16 to 19 of Gentry's PhD Thesis[START_REF] Gentry | A fully homomorphic encryption scheme[END_REF], whose security is based on the quantum worst case hardness of SIVP in ideal lattices, via a worst-case to average-case reduction (see for instance the discussion in Section 16.5 of[START_REF] Gentry | A fully homomorphic encryption scheme[END_REF]). This is dierent from the scheme in[START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF], which uses principal ideal lattices with a short generator, and have been broken by a later line of works[START_REF] Campbell | Soliloquy: A cautionary tale[END_REF][START_REF] Eisenträger | A quantum algorithm for computing the unit group of an arbitrary degree number eld[END_REF][START_REF] Cramer | Recovering short generators of principal ideals in cyclotomic rings[END_REF][START_REF] Biasse | A polynomial time quantum algorithm for computing class groups and solving the principal ideal problem in arbitrary degree number elds[END_REF].

Hecke characters of K are characters on the idèle class group of K. As the Arakelov class group is a specic quotient of the idèle class group [38, Ch. VI, pp. 360], the characters on the Arakelov class group are essentially Hecke characters whose kernel contains the kernel of the quotient map sending the idèle class group to the Arakelov class group.

We use the bound β ( ) α ≤ e -α 2 for α ≥ √

In this bound on B one would expect an additional log(log(Vol(Pic 0 K )). But as it is bounded by log(log(∆)) (see Lemma 2.3), it can be put in the hidden polylogarithmic factors.

One can observe that this randomization process outputs an ideal lattice instead of a fractional ideal. This will be solved by rounding the ideal lattice to a fractional lattice with close geometry.

Observe that contrary to the high level overview, the center c of the Gaussian distribution has been randomized (but it still holds that the sampled element v will be balanced). This is needed in Lemma 4.2, to show that the Extractς,M (•) distributions are identical when applied to K-isomorphic ideal lattices.

The function Eε 1 plays the role of the exponential function, rounded to a near element of K.

Any character on the Arakelov class group can be seen as a Hecke character, by projecting the idèle class group to the Arakelov class group. Since characters on the Arakelov class group are necessarily dened on any ideal class, the conductor equals one. The analytic conductor q(χ) is then equal to ∆ • N (fχ) • q∞(χ) = ∆ • q∞(χ), where ∆ is the discriminant of the number eld K and q∞(χ) is the innite part of the analytic conductor; see, for example,[22, p. 129 & Eq. (5.7)]

Acknowledgments We are grateful to René Schoof for valuable feedback on a preliminary version of this work. We also would like to thank Wessel van Woerden for his help in simplifying the proof of Lemma A.1. Part of this work was done while the authors were visiting the Simons Institute for the Theory of Computing. L.D. is supported by the European Union Horizon 2020 Research and Innovation Program Grant 780701 (PROMETHEUS), and by a Fellowship from the Simons Institute. K.d.B. was supported by the ERC Advanced Grant 740972 (ALGSTRONGCRYPTO) and by the European Union Horizon 2020 Research and Innovation Program Grant 780701 (PROMETHEUS). A.P. was supported in part by CyberSecurity Research Flanders with reference number VR20192203 and by the Research Council KU Leuven grant C14/18/067 on Cryptanalysis of post-quantum cryptography. Part of this work was done when A.P. was visiting CWI, under the CWI PhD internship program. Part of this work was done when B.W. was at the Cryptology Group, CWI, Amsterdam, The Netherlands, supported by the ERC Advanced Grant 740972 (ALGSTRONGCRYPTO).

Algorithm 3 Algorithm A

Require: A fractional ideal L(a) (given by a basis). Ensure: A vector w ∈ L(a).

1: Sample L(b) ← D sample ς,M,a using Algorithm 2 and remember the elements x = (xσ)σ and v used in the algorithm. 2: Run A(L(b)) to obtain w.

3: return

Hence, if one chooses ς and M minimal (still satisfying the conditions of Theorem 4.5) and if we are given an LLL reduced basis of L(O K ) (which can always be computed from any other basis), then the run time of Algorithm A in Theorem 4.5 is of the form T + poly (log ∆, size(N (a))).

Proof. We construct an algorithm A using A as described in Algorithm 3.

Let us rst prove the bound on the run-time of

, we can apply Theorem 4.4 and we know that one can sample from D sample ς,M,a in time polynomial in size(N (a)), log ∆, max i log b i , log M and log ς. The second step of the algorithm is bounded by T by assumption and this concludes the proof on the run time of the algorithm.

Let us now prove that the algorithm is correct. First of all, we note that by choice of ς and by Theorem 4.4, then SD(D sample ς,M,a , D perfect ς,M

) ≤ 2 -Ω(n) , which shows that with probability at least p-2 -Ω(n) , Algorithm 3 above

Let us assume in the following that this is the case, and show that w ∈ L(a) and that Let us now bound the size of w . We know that

By denition of L(b), it also holds that

Hence we obtain that w ≤ γ • Vol(L(a)) for an approximation factor

Recall that v is sampled from a distribution which is statistically close to G L,ς ,c for some ideal lattice L with ς = N (

Recall also that we have seen in the proof of Theorem 4.4 that ς ≥ n log(n) • λ n (L(O K )) • Vol(L) 1/n . Using Lemma 2.8 as well as Lemmas 3.3 and 4.4 of [START_REF] Micciancio | Worst-case to average-case reductions based on gaussian measures[END_REF] (instantiated at = 1/2), this implies that v -c ≤ √ n • ς , except with probability at most 2 -Ω(n) . Let us assume that this is indeed the case, then, for any coordinate v σ of v it holds that

from which we conclude that