Keywords: SimonŠs Algorithm

Jean-Pierre, je ne saurais te remercier assez pour ces trois ans, qui ont été, tu en conviendras probablement, particulièrement atypiques. Je nŠai que de la gratitude à exprimer pour ton aide constante, pour ta patience, mais également pour mŠavoir épargné bien des tracas à plusieurs reprises. Je suis dŠautant plus reconnaissant pour tout ce que jŠai pu apprendre grâce à toi, scientiĄquement ou non, et suis Ąer de tŠavoir eu comme directeur de thèse.

Simon, je mesure ma chance dŠavoir effectué mon stage de Ąn dŠétudes, puis dŠavoir poursuivi en doctorat, sous ton regard toujours bienveillant. Bien que mes travaux soient Ąnalement restés assez éloignés de tes domaines dŠexpertise, tu mŠas toujours apporté de précieux conseils. Travailler et discuter avec toi est un plaisir en plus dŠêtre enrichissant.

Merci à Omar Fawzi et à Damien Stehlé pour avoir endossé le rôle de rapporteur, ainsi quŠà Alex Bredariol Grilo, Mehdi Mhalla et María Naya-Plasencia pour avoir accepté de faire partie de mon jury.

Je tiens également à remercier Thomas et André, que jŠai eu la chance dŠavoir comme co-auteurs. Thomas, ton sens de la pédagogie et la passion que tu mets dans ton travail sont particulièrement admirables. André, nous avons principalement collaboré à distance, mais je peux témoigner de ton enthousiasme et de la qualité du travail que tu abats de manière terriblement efficace.

Je souhaite également exprimer ma reconnaissance envers Cyril. Vous mŠavez accordé votre conĄance pour réaliser ce doctorat, puis lŠavez renouvelée pour la suite. JŠespère être à la hauteur des tâches qui mŠattendent ! Ces trois années ont été rendues dŠautant plus agréables grâce à mes collègues à Atos dŠune part et à lŠINRIA dŠautre part. Je ne pourrais citer toutes les personnes que jŠai croisées, avec qui jŠai eu le plaisir de travailler ou de discuter au cours dŠun repas ou dŠune pause café. Évoluer dans ces deux environnements différents mais complémentaires a été à la fois instructif et plaisant.

JŠai une pensée particulière pour les professeurs qui mŠont conduit sur la route des mathématiques, puis sur un chemin de plus en plus spéciĄque pour en arriver jusquŠici. En particulier, jŠaimerais mentionner François Arnault, avec qui jŠai eu la chance de i découvrir lŠinformatique quantique lors dŠun stage entre mes deux années de Master, et Philippe Gaborit, pour avoir notamment contribué à rendre cette thèse possible.

Maxime, un grand merci pour avoir relu un des chapitres de cette thèse et mŠavoir donné de très bons conseils, mais également pour nos conversations, toujours très intéressantes et agréables.

Il nŠy a pas que des docteurs en informatique théorique que je souhaite remercier. JŠai une reconnaissance inĄnie envers Dr. Laigle-Donadey en particulier, mais également tous les autres spécialistes que jŠai été amené à rencontrer. Peut-être ai-je contribué à faire avancer la science en médecine durant ces trois ans, bien malgré moi ? Anaïs, Caroline, Koray, merci pour les moments partagés ensemble. Même sŠils se font plus rares quŠen Licence ou en Master, ils sont inestimables et me rendent souvent nostalgique de ce quŠon a pu vivre ensemble à la Roche, à Limoges ou ailleurs.

Olivier, meda akpe na wò ŋuto. Wòe nye xõnye vevito eye melé wò de nye dzi ŋu kplikplikpli. Mawu nayra wò gede. Èno anyi nam le γeyiγi nyui kple võwo me, èdo alom hede dzi ƒo nam. Akpe gede na wò, èle vevie nam ŋuto

Introduction (Français)

Problème de sous-groupe caché. Abrégé par HSP pour "Hidden Subgroup Problem", le problème de sous-groupe caché est un problème fondamental en informatique théorique consistant à trouver un sous-groupe inconnu H au sein dŠun groupe G à lŠaide uniquement dŠune fonction qui est constante et distincte sur les classes de H. Ce problème de sous-groupe caché a de nombreuses applications en cryptographie, ce qui en fait un problème important à étudier, puisque la sécurité de certains systèmes cryptographiques repose notamment sur la difficulté à résoudre ce problème. Les algorithmes quantiques interviennent alors, car il a été montré que des avantages signiĄcatifs peuvent être obtenus pour résoudre efficacement certaines instances de HSP difficiles à résoudre pour les ordinateurs classiques. Une technique bien connue se cache derrière cela, cŠest lŠéchantillonnage de Fourier quantique.

Échantillonnage de Fourier quantique. Quantum Fourier Sampling en anglais, lŠéchantillonnage de Fourier quantique est en effet une technique algorithmique quantique qui exploite la transformée de Fourier quantique (QFT, pour "Quantum Fourier Transform", qui est lŠanalogue quantique de la transformée de Fourier discrète: dŠune certaine manière, elle mesure les fréquences présentes dans lŠétat dŠentrée et les exprime dans lŠétat transformé). LŠéchantillonnage de Fourier quantique tire donc parti de cette propriété pour résoudre efficacement les problèmes qui peuvent être représentés à lŠaide dŠune fonction avec périodicité. La méthode est simple: il suffit tout dŠabord de construire une superposition dŠentrées, appliquer la fonction en question sur cette superposition, puis appliquer une QFT sur le registre contenant les images ainsi calculées et le mesurer. Nous obtenons alors une superposition dŠéléments dŠune classe de lŠorthogonal du sous-groupe caché, nous permettant par conséquent dŠobtenir de lŠinformation sur ce dernier.

Chapitre 1. LŠalgorithme de Shor est un célèbre et excellent exemple de la manière dont lŠéchantillonnage de Fourier quantique peut être appliqué à un problème de sousgroupe caché. Il utilise en effet cette technique pour trouver la période dŠune fonction modulaire, qui est un exemple concret de HSP. La factorisation de grands nombres (un problème difficile classiquement) pouvant être réduite à la recherche de la période dŠune v fonction modulaire et cette fonction modulaire pouvant être calculée efficacement de manière quantique, lŠalgorithme de Shor résout le problème de factorisation efficacement (cŠest-à-dire, en temps polynomial). En tirant parti de la puissance de lŠéchantillonnage de Fourier quantique, qui hérite lui-même des propriétés de la QFT, il a ainsi été montré quŠà lŠimage de lŠalgorithme de Shor, il est possible de résoudre des problèmes de sousgroupe caché ayant un impact important en cryptographie. Le Chapitre 1 introduit plus largement le problème de sous-groupe caché ainsi que la méthode dŠéchantillonnage de Fourier quantique, en allant de lŠalgorithme de Simon jusquŠà lŠalgorithme générique permettant de résoudre le HSP dans nŠimporte quel groupe abélien en temps polynomial, en passant par lŠalgorithme de Shor.

Chapitre 2. La cryptographie post-quantique est un domaine en pleine évolution qui cherche à développer des primitives cryptographiques sûres contre les attaques cryptanalytiques exécutées sur des ordinateurs quantiques. La sécurité de ces primitives post-quantiques est basée sur des problèmes mathématiques considérés comme difficiles pour les ordinateurs classiques et quantiques, tels que le problème du vecteur le plus court (SVP, pour "Shortest Vector Problem") et le problème de lŠapprentissage avec erreurs (LWE, pour "Learning With Errors") en cryptographie à base de réseaux, qui est une approche populaire de la cryptographie post-quantique se basant sur la métrique euclidienne. Le Chapitre 2 donne les bases et notions élémentaires de cryptographie à base de codes, une autre approche majeure en cryptographie post-quantique se basant quant à elle sur la métrique de Hamming. Les équivalents de SVP et LWE, respectivement le problème de recherche de mot de petit poids et le problème de décodage, sont notamment clairement déĄnis et leur difficulté est discutée. EnĄn, nous introduisons et discutons également de la métrique rang, qui tend à être de plus en plus étudiée et investiguée dans le cadre de la recherche de primitives post-quantiques (quelques soumissions en métrique rang, en plus de celles plus nombreuses en métrique euclidienne et de Hamming, sont à noter au programme de standardisation du NIST, voir [START_REF]Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process[END_REF][START_REF]Call for Additional Digital Signature Schemes for the Post-Quantum Cryptography Standardization Process[END_REF]).

Chapitre 3. Ce chapitre correspond à lŠarticle [START_REF] Debris-Alazard | ŞQuantum Reduction of Finding Short Code Vectors to the Decoding ProblemŤ[END_REF]. Le but de notre travail est de montrer comment calculer avec un ordinateur quantique un mot de faible poids de Hamming dans un code aléatoire à partir dŠun algorithme permettant de décoder son dual. CŠest la première fois quŠune telle réduction (classique ou quantique) pour la métrique de Hamming a été obtenue. En fait, ce travail fournit une adaptation aux codes linéaires de la réinterprétation de Stehlé-Steinfeld-Tanaka-Xagawa [START_REF] Stehlé | ŞEfficient Public Key Encryption Based on Ideal LatticesŤ[END_REF] de la réduction quantique de Regev [START_REF] Regev | ŞOn lattices, learning with errors, random linear codes, and cryptographyŤ[END_REF] de SVP approximé dans le pire cas au problème LWE. La métrique de Hamming est une métrique beaucoup plus grossière que la métrique euclidienne et cette adaptation a nécessité plusieurs nouveaux ingrédients pour fonctionner. Par exemple, pour obtenir une réduction signiĄcative, il est nécessaire, avec la métrique de Hamming, de choisir un rayon de décodage très grand: dans de nombreux vi cas, il faut aller au-delà du rayon où le décodage est unique. Une autre étape cruciale pour lŠanalyse de la réduction est le choix des erreurs pour lŠalgorithme de décodage. En réseaux, les erreurs sont généralement échantillonnées selon une distribution gaussienne. Cependant, il sŠavère que la distribution de Bernoulli (lŠanalogue de la gaussienne pour les codes) est trop étalée et ne peut pas être utilisée, en tant que telle, pour la réduction avec des codes. Nous avons traité cette difficulté pour obtenir le résultat susmentionné en considérant une distribution originale dans ce contexte, cŠest-à-dire une distribution de Bernoulli tronquée. En outre, notre travail montre également une connexion entre lŠapproche de Regev et une notion intéressante de "distance duale" qui est impliquée dans la première borne de programmation linéaire en théorie des codes [START_REF] Mceliece | ŞNew upper bounds on the rate of a code via the Delsarte-MacWilliams inequalitiesŤ[END_REF] ou celle [START_REF] Iossifovitch | ŞBounds for packings in n-dimensional Euclidean spaceŤ[END_REF][START_REF] Cohn | ŞNew Upper Bounds on Sphere Packings IŤ[END_REF] dŠempilement des sphères dans R n . Chapitre 4. Comme vu dans le premier chapitre, la méthode dŠéchantillonnage de Fourier quantique permet de résoudre le problème de sous-groupe caché dans nŠimporte quel groupe abélien en temps polynomial. Mais son intérêt ne sŠarrête pas aux seuls groupes abéliens: il a également été montré quŠelle peut être utile pour résoudre ce problème dans un groupe diédral. Cette fois-ci elle ne permet pas une accélération exponentielle comme pour les groupes abéliens mais une accélération sous-exponentielle, tout de même. Dans ce chapitre nous reprenons les principaux algorithmes qui ont échelonné lŠhistoire de la résolution du problème de classe diédrale suivant le sous-groupe caché (DCP, pour "Dihedral Coset Problem"), problème quantique qui peut sŠexprimer relativement simplement et auquel se réduit le problème de sous-groupe caché dans un groupe diédral. A celui-ci se réduit la sécurité de nombreux cryptosystèmes, quŠils soient asymétriques ou symétriques, et plus généralement de nombreux autres problèmes, notamment utilisés en cryptographie à base de réseaux ou à base dŠisogénies, faisant du DCP un problème de prime importance. Pour N ∈ N, il est déĄni comme suit.

Problème (DCP). Etant donné un oracle générant aléatoirement des nombres k tirés

uniformément dans Z N et leur état quantique associé ♣ψ k ⟩, déterminer s ∈ Z N , avec:

♣ψ k ⟩ def = 1 √ 2 ♣0⟩ + e 2iπsk N ♣1⟩  .
Il existe deux familles dŠalgorithmes pour le résoudre, toutes deux tournant en temps sous-exponentiel: la première est essentiellement composée du premier algorithme de Kuperberg [START_REF] Kuperberg | A subexponential-time quantum algorithm for the dihedral hidden subgroup problem[END_REF], qui résout le problème de manière directe et uniquement grâce à des portes CNOT et des mesures, tandis que lŠautre est notamment composée de lŠalgorithme de Regev [START_REF] Regev | A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space[END_REF] et du deuxième algorithme de Kuperberg [START_REF] Kuperberg | Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem[END_REF], qui réduisent le problème à un problème de somme de sous-ensembles (subset-sum problem). Ces trois algorithmes sont présentés dans ce chapitre et leur complexité est donnée, après que le problème de sous-groupe caché dans un groupe diédral et le DCP soient déĄnis, ainsi que vii lŠalgorithme de Ettinger et Høyer [START_REF] Ettinger | ŞOn Quantum Algorithms for Noncommutative Hidden SubgroupsŤ[END_REF], le premier algorithme résolvant ce problème, présenté.

Chapitre 5. En combinant une idée due à Regev pour résoudre le DCP dans Z N [START_REF] Regev | A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space[END_REF] et la méthode dŠéchantillonnage de Fourier quantique, nous introduisons dans ce chapitre un nouveau genre dŠalgorithme pour résoudre le problème de sous-groupe caché dans un groupe diédral. Nous réduisons en effet la résolution de ce problème à celle dŠun problème quantique de somme de sous-ensembles, ce qui offre une nouvelle alternative aux deux autres principaux modes de résolutions déjà connus et cités ci-dessus. Pour cela, nous reprenons lŠidée initiale de lŠalgorithme de Regev mais au lieu de mesurer une superposition de valeurs cibles pour un problème de somme de sous-ensembles et de résoudre le problème classiquement, nous conservons la superposition et utilisons un algorithme quantique pour résoudre le problème quantiquement. Nous obtenons alors un algorithme qui ne nécessite plus de faire quŠun nombre linéaire (cŠest-à-dire en O (log N )) de requêtes à lŠoracle, là où la version économe en requêtes de celui de Regev nécessitait un nombre quadratique (en O (log N ) 2 ). De plus, la complexité en temps est celle de lŠalgorithme quantique de somme de sous-ensembles au lieu de celui classique.

Nous obtenons ainsi le premier algorithme depuis celui de Ettinger et Høyer à effectuer un nombre linéaire de requêtes à lŠoracle, et nous en améliorons lŠexposant: là où celui de Ettinger-Høyer tourne en temps en O (N ), le notre tourne approximativement en

Introduction (English)

Hidden Subgroup Problem. Abbreviated HSP, the hidden subgroup problem is a fundamental problem in theoretical computer science consisting in Ąnding an unknown subgroup H within a group G using only a function that is constant and distinct over the cosets of H. This hidden subgroup problem has many applications in cryptography, making it an important problem to study, since the security of some cryptographic systems relies in particular on the difficulty of solving this problem. Quantum algorithms come into play here, as it has been shown that signiĄcant advantages can be gained in efficiently solving certain HSP instances that are difficult for classical computers to solve. A well-known technique behind this is quantum Fourier sampling.

Quantum Fourier sampling. Quantum Fourier Sampling is in fact a quantum algorithmic technique that exploits the quantum Fourier transform (QFT, which is the quantum analog of the discrete Fourier transform: in a way, it measures the frequencies present in the input state and expresses them in the transformed state). Quantum Fourier sampling therefore takes advantage of this property to efficiently solve problems that can be represented using a function with periodicity. The method is simple: Ąrst construct a superposition of inputs, apply the function in question to this superposition, then apply a QFT to the register containing the images thus calculated and measure it. We obtain a superposition of elements of a coset of the orthogonal of the hidden subgroup, enabling us to obtain information about the latter.

Chapter 1. ShorŠs algorithm is a famous and excellent example of how quantum Fourier sampling can be applied to a hidden subgroup problem. It uses this technique to Ąnd the period of a modular function, which is a concrete example of HSP. Since factorization of large numbers (a classically difficult problem) can be reduced to Ąnding the period of a modular function, and since this modular function can be quantumly computed efficiently, ShorŠs algorithm solves the factorization problem efficiently (i.e., in polynomial time). By taking advantage of the power of quantum Fourier sampling, which itself inherits the properties of QFT, it has thus been shown that, like ShorŠs algorithm, it is possible to solve hidden subgroup problems that have a major impact ix in cryptography. Chapter 1 provides a broader introduction to the hidden subgroup problem and the quantum Fourier sampling method, ranging from SimonŠs algorithm via ShorŠs algorithm to the generic algorithm for solving the HSP in any abelian group in polynomial time.

Chapter 2. Post-quantum cryptography is an evolving Ąeld that seeks to develop cryptographic primitives secure against cryptanalytic attacks executed on quantum computers. The security of these post-quantum primitives is based on mathematical problems considered difficult for both classical and quantum computers, such as the Shortest Vector Problem (SVP) and the Learning With Errors Problem (LWE) in latticebased cryptography, which is a popular approach to post-quantum cryptography based on the Euclidean metric. The Chapter 2 gives the basics and notions of code-based cryptography, another major approach to post-quantum cryptography based on the Hamming metric. In particular, the equivalents of SVP and LWE, respectively the short codeword search problem and the decoding problem, are deĄned and their difficulty discussed. Finally, we also introduce and discuss the rank metric, which tends to be increasingly studied and investigated in the search for post-quantum primitives (a few submissions in rank metric, in addition to the more numerous ones in Euclidean and Hamming metrics, are to be noted at the NIST standardization process, see [START_REF]Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process[END_REF][START_REF]Call for Additional Digital Signature Schemes for the Post-Quantum Cryptography Standardization Process[END_REF]).

Chapter 3. This chapter corresponds to the article [START_REF] Debris-Alazard | ŞQuantum Reduction of Finding Short Code Vectors to the Decoding ProblemŤ[END_REF]. The aim of our work is to show how to compute with a quantum computer a low-weight Hamming word in a random code from an algorithm allowing to decode its dual. This is the Ąrst time that such a reduction (classical or quantum) for the Hamming metric has been obtained. In fact, this work provides an adaptation to linear codes of Stehlé-Steinfeld-Tanaka-XagawaŠs reinterpretation [START_REF] Stehlé | ŞEfficient Public Key Encryption Based on Ideal LatticesŤ[END_REF] of RegevŠs quantum reduction [START_REF] Regev | ŞOn lattices, learning with errors, random linear codes, and cryptographyŤ[END_REF] from worst-case approximate SVP to LWE. The Hamming metric is a much coarser metric than the Euclidean one, and this adaptation required several new ingredients to work. For example, to achieve a signiĄcant reduction, it is necessary, with the Hamming metric, to choose a very large decoding radius: in many cases, we have to go beyond the radius where decoding is unique. Another crucial step in reduction analysis is the choice of errors that are passed on to the decoding algorithm. With lattices, errors are generally sampled according to a Gaussian distribution. However, it turns out that the Bernoulli distribution (the Gaussian analogue for codes) is too spread out and cannot be used, as such, for a reduction with codes. We have addressed this difficulty to obtain the above result by considering an original distribution in this context, i.e., a truncated Bernoulli distribution. In addition, our work also shows a connection between RegevŠs approach and an interesting notion of "dual distance" which is involved in the Ąrst linear x programming bound in code theory [START_REF] Mceliece | ŞNew upper bounds on the rate of a code via the Delsarte-MacWilliams inequalitiesŤ[END_REF] or that [START_REF] Iossifovitch | ŞBounds for packings in n-dimensional Euclidean spaceŤ[END_REF][START_REF] Cohn | ŞNew Upper Bounds on Sphere Packings IŤ[END_REF] of sphere stacking in R n .

Chapter 4. As seen in the Ąrst chapter, the quantum Fourier sampling method can be used to solve the hidden subgroup problem in any abelian group in polynomial time.

But the methodŠs interest is not limited to abelian groups: it has also been shown that it can be useful for solving this problem in a dihedral group. This time, it does not allow exponential acceleration as for abelian groups, but it does allow subexponential acceleration. In this chapter, we review the main algorithms that have staggered the history of the solution of the Dihedral Coset Problem (DCP), a quantum problem that can be expressed relatively simply and to which the hidden subgroup problem in a dihedral group is reduced. In turn, to this problem is reduced the security of many cryptosystems, whether asymmetric or symmetric, and more generally of many other problems, notably used in lattice-based or isogeny-based cryptography, making the DCP a problem of prime importance. For N ∈ N, it is deĄned as follows.

Problem (DCP). Given an oracle generating numbers k drawn uniformly at random

from Z N and their associated quantum state ♣ψ k ⟩, determine s ∈ Z N , where:

♣ψ k ⟩ def = 1 √ 2 ♣0⟩ + e 2iπsk N ♣1⟩  .
There are two families of algorithms for solving this problem, both running in subexponential time: the Ąrst is essentially made up of KuperbergŠs Ąrst algorithm [START_REF] Kuperberg | A subexponential-time quantum algorithm for the dihedral hidden subgroup problem[END_REF], which solves the problem directly and solely using CNOT gates and measurements, while the other is notably made up of RegevŠs algorithm [START_REF] Regev | A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space[END_REF] and KuperbergŠs second algorithm [START_REF] Kuperberg | Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem[END_REF], which reduce the problem to a classical subset-sum problem. These three algorithms are presented in this chapter and their complexity is given, after the hidden subgroup problem in a dihedral group and the DCP are deĄned, and Ettinger and HøyerŠs algorithm [START_REF] Ettinger | ŞOn Quantum Algorithms for Noncommutative Hidden SubgroupsŤ[END_REF], the historically Ąrst algorithm proposed to solve this problem, presented.

Chapter 5. Combining an idea due to Regev for solving the DCP in Z N [START_REF] Regev | A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space[END_REF] and the quantum Fourier sampling method, we introduce in this chapter a new kind of algorithm for solving the hidden subgroup problem in a dihedral group. In fact, we reduce the resolution of this problem to that of a quantum subset-sum problem, offering a new alternative to the two other main methods of resolution already known and cited above. To do this, we take up the original idea of RegevŠs algorithm, but instead of measuring a superposition of target values for a subset-sum problem and solving the problem classically, we retain the superposition and use a quantum algorithm to solve the problem quantum-wise. We then obtain an algorithm that only requires a linear xi number (i.e., in O (log N )) of queries to the oracle, whereas the low-queries version of RegevŠs algorithm required a quadratic number (in O (log N ) 2 ). The time complexity is that of the quantum subset-sum algorithm instead of the classical one. We thus obtain the Ąrst algorithm since Ettinger and HøyerŠs to perform a linear number of queries to the oracle, and we improve its exponent: where Ettinger-HøyerŠs runs in O (N ) time, ours runs in approximately O N 0.418 . Finally, we also give a very natural interpolation on the number of queries between this new algorithm and KuperbergŠs second algorithm, as well as a reĄned study of algorithms for solving the quantum subset-sum problem. This chapter corresponds to the article [START_REF] Remaud | ŞTime and Query Complexity Tradeoff for the Dihedral Coset ProblemŤ[END_REF].

Chapter 6. Finally, in our last chapter, we present several ways of solving the DCP in Z N without having to reduce it to a subset-sum problem, thus following in the footsteps of KuperbergŠs Ąrst algorithm, which nevertheless has the major drawback of requiring a subexponential space (classical and quantum) in 2 O( √ log N ) to work. Inspired by a rewriting of the latter proposed by Bonnetain and Naya-Plasencia [START_REF] Bonnetain | ŞHidden Shift Quantum Cryptanalysis and ImplicationsŤ[END_REF], we present a new algorithm for solving DCP in Z N . This beats all existing algorithms in terms of use of both classical and quantum space, since it requires at most ⌈log N ⌉ qubits and its time complexity is in O N 0.415 and is the lowest among all algorithms using linear space, but on the other hand, it requires making an exponential number of queries. Because of the way it works, it is very easy to generalize the method used to design this algorithm and adapt it to any number of qubits.

xii Preprints and Publications [START_REF] Debris-Alazard | ŞQuantum Reduction of Finding Short Code Vectors to the Decoding ProblemŤ[END_REF] Thomas Debris

Notation and Acronyms

General notation. Vectors are in row notation and they will be written with lowercase bold letters. Uppercase bold letters are used to denote matrices.

Logarithms. log (x) (or simply log x) will denote the logarithm in base 2 of x.

Set of integers.

For a and b integers with a ≤ b, we denote by a, b the set of integers ¶a, a + 1, . . . , b♢. We extend this notation when a and b are not integers to the set of integers in [a, b].

Polynomial quantity. poly(n) will denote a quantity which is an O (n a ) for some constant a.

Inner product. x • y def = n i=1 x i y i for x = (x i ) n i=1 and y = (y i ) n i=1 . Shannon entropy. h q (x) def = -(1 -x) log q (1 -x) -x log q x q-1  for x ∈ (0, 1).

Quantum Fourier Transform (QFT).

Let the prime p be the characteristic of F q , with q = p s . Let Let G be a known group and H be an unknown subgroup of G. We will refer to H as the hidden subgroup of G and Ąnding it is a problem known as the Hidden Subgroup Problem (HSP). This problem is of the greatest importance in mathematics and theoretical computer science, because it encompasses many known problems used in particular in cryptography to construct primitives. For example, we can mention the problems of period Ąnding, discrete logarithm, graph isomorphism and shortest vector as special cases of hidden subgroup problems. Among all the cryptographic primitives built relying on the hardness of Ąnding a hidden subgroup in a group, we can obviously cite the RSA cryptosystem [START_REF] Rivest | ŞA Method for Obtaining Digital Signatures and Public-Key CryptosystemsŤ[END_REF] and the Diffie-Hellman key exchange protocol [START_REF] Diffie | ŞNew directions in cryptographyŤ[END_REF], built on the period-Ąnding problem and the discrete logarithm problem respectively. More interestingly for our purpose, we can mention CSIDH [START_REF] Castryck | ŞCSIDH: An Efficient Post-Quantum Commutative Group ActionŤ[END_REF] and more generally any cryptosystem based on the isogeny problem [START_REF] Childs | ŞConstructing elliptic curve isogenies in quantum subexponential timeŤ[END_REF], any cryptosystem based on the Unique Shortest Vector Problem (uSVP) in lattice-based cryptography (such as [AD97; Reg04b]) or on any of the many problems that can be reduced to uSVP , and even symmetric primitives (Poly1305-AES [Ber05; BN18] for example).

ω p def = e 2iπ p . The QFT of ♣ψ⟩ def = x∈F n q α x ♣x⟩ is deĄned as ♣ψ⟩ def = 1 √ q n y∈F n q   x∈F n q α x ω Tr(x•y) p   ♣
But the HSP is also paramount in quantum computing because it was responsible for the Ąrst major advances in the Ąeld in the early 1990s. Indeed, SimonŠs and ShorŠs algorithms are well-known examples of quantum algorithms that solve hidden subgroup problems, and what makes them particularly interesting is the fact that they work in polynomial time, whereas no classical algorithm does.

In order to solve the HSP, we are given a function which is said to "hide" the hidden subgroup, since it has the property to be constant and distinct on the left cosets of H: Definition 1.1 (Hiding function). Let G be a group and H be a subgroup of G. We say that a function f :

G → S (where S is a Ąnite set) hides H if ∀g, g ′ ∈ G, f (g) = f (g ′ ) ⇐⇒ gH = g ′ H.
We can now properly deĄne the HSP, as follows.

Problem 1.1. Hidden Subgroup Problem (HSP). The hidden subgroup problem is defined as:

• Input: a function f : G → S that hides an unknown subgroup H of a group G, S being a finite set,

• Output: (a generating set of) H.

Note that in practice, H might be a large subset of G and Ąnding it (i.e., Ąnding all its elements) would be tedious, but Ąnding a generating set of it will be enough for our purpose.

In Table 1.1, we give examples of problems which can be casted as a HSP and the group in which this HSP has to be solved.

Problem Group

SimonŠs Z n 2 Period Finding Z N Discrete Logarithm Z N × Z N Graph Isomorphism S N Shortest Vector D N Table 1.1:
Examples of problems which can be casted as a HSP in the speciĄed group. S N is the symmetric group on N elements and D N is the dihedral group, the group of the symmetries of a polygon with N sides, which will be the subject of the next chapter. See [START_REF] Kaye | An Introduction to Quantum Computing[END_REF] for more details.

It turns out that when G is abelian, there is a well-known polynomial-time quantum algorithm solving HSP, which, roughly speaking, consists in building a superposition over the elements of G, computing f (G) in an ancillary register, applying a Quantum Fourier Transform (QFT) on the Ąrst register and Ąnally sampling it. SimonŠs and ShorŠs algorithms are speciĄc cases of this algorithm. On the other hand, when G is not abelian, there is no general algorithm for solving this problem but some results exist for particular non-abelian groups like the symmetric and the dihedral groups, to which are linked the Graph Isomorphism Problem and the Shortest Vector Problem, respectively.

In this chapter, we will focus on algorithms for solving the HSP in abelian groups. Namely, we will give an overview of SimonŠs algorithm, then of ShorŠs algorithm for the Discrete Logarithm Problem, and Ąnally of the "standard algorithm" for solving any HSP in a Ąnite abelian group in polynomial time. The HSP in a dihedral group will be the subject of Chapter 5 and Chapter 6 of this manuscript. The promise on f means that we have the following property:

∀x, y ∈ Z n 2 , f (x) = f (y) ⇐⇒ x = y ⊕ h where h ∈ H = ¶0, s♢ . (1.1)
In this problem, Ąnding H boils down to Ąnding the secret vector s.

It can be shown that any classical algorithm solving SimonŠs problem with probability at least 2/3 will have a query complexity in Ω 2 n 3



(see [START_REF] Kaye | An Introduction to Quantum Computing[END_REF], Theorem 6.5.1). On the other hand, Simon came up with a quantum algorithm which solves this same problem with a query complexity in O (n), exponentially improving over its classical counterparts (see [START_REF] Kaye | An Introduction to Quantum Computing[END_REF], Theorem 6.5.2).

Algorithm 1 provides a pseudo-code implementation of SimonŠs algorithm. It assumes that the function f that hides the subgroup is efficiently implementable in a quantum way, which will always be assumed for all algorithms presented in this chapter. Namely, we assume that we have a unitary U f for implementing f :

U f : ♣x⟩ ♣b⟩ → ♣x⟩ ♣b ⊕ f (x)⟩ .

Remarks on Simon's algorithm.

• The uniform superposition over Z n 2 is efficiently produced thanks to Hadamard gates applied to n qubits initialized to 0.

• The Ąrst measurement is not mandatory but it simpliĄes the algorithmŠs analysis.

By this measure, an image of f is chosen and the Ąrst register is projected on a

Algorithm 1 SimonŠs algorithm for SimonŠs Problem

Require: A unitary U f to quantumly compute f . Ensure: The secret vector s as deĄned in Equation 1.1.

1: Initialize a list L = ∅. 2: repeat 3:
Prepare a uniform superposition over Z n 2 and use

U f to compute f in an ancillary register 1 √ 2 n x∈Z n 2 ♣x⟩ ♣f (x)⟩ 4:
Measure the second register and discard it 1 √ 2 (♣y⟩ + ♣y + s⟩)

5:

Apply

H ⊗n 1 √ 2 n+1 x∈Z N (-1) x•y (1 + (-1) x•s ) ♣x⟩ 6:
Measure the register and place the resulting vector in L 7: until the dimension of the span of the vectors in L equals n -1. 8: Solve the linear system formed by ℓ • s = 0, ∀ℓ ∈ L and output the non-zero solution.

superposition of the preimages by f of the image that has been measured. With our notation, an image f (y) has two antecedents: y and y + s.

• If we look at the amplitude of the vector x just before the second measurement operator, we can see that it is zero if and only if x • s = 1 or conversely that it is non-zero if and only if x • s = 0. It means that we can write

1 √ 2 n+1 x∈Z N (-1) x•y (1 + (-1) x•s ) ♣x⟩ = 1 √ 2 n-1 x∈Z N : x•s=0 (-1) x•y ♣x⟩ = 1 √ 2 n-1 x∈H ⊥ (-1) x•y ♣x⟩
where we recall that

H ⊥ def = ¶x ∈ Z n 2 : x • h = 0 ∀h ∈ H♢ = ¶x ∈ Z n 2 : x • s = 0♢.
The vector that will be measured will thus be a vector orthogonal to the secret one we are looking for.

• The dimension of H being 1, the dimension of H ⊥ has to be n -1. Thus, if we have n -1 vectors orthogonal to s forming a basis of H ⊥ , we will be able to solve the linear system in polynomial time in n by Gaussian elimination in the last step of the algorithm. This linear system has exactly two solutions, 0 and s.

Shor's Algorithm

In this section, we will outline ShorŠs quantum algorithm for solving the Discrete Logarithm Problem (DLP) in polynomial time [START_REF] Shor | ŞAlgorithms for quantum computation: Discrete logarithms and factoringŤ[END_REF]. ShorŠs algorithm is surely best known for allowing to efficiently solve the factorization problem by reducing it to the period Ąnding problem that it then solves thanks to a quantum computer, but this will not be our point here. We will focus on the algorithm for DLP which is more straightforward and can easily be seen to be, in some way, on the path between SimonŠs algorithm and the standard algorithm for solving HSP for any Ąnite abelian group. We start by recalling DLP:

Problem 1.3. Discrete Logarithm Problem (DLP). Let G = ⟨g⟩ be a finite cyclic group of order N and x ∈ G. The DLP g,x,N asks to find the smallest positive integer α such that

g α = x, (1.2)
i.e., α = log g x.

With these notations, N will typically be equal to p -1 where p is a prime number and G will be Z × p . We assume that x is different from g, otherwise the problem is trivial. We also assume that we know the order N of the group since if we do not, we can simply use ShorŠs algorithm for period Ąnding to determine N .

There have actually been many classical algorithms introduced for solving the DLP in an arbitrary group. Some are deterministic, as for examples the Baby-Step/Giant-Step algorithm [START_REF] Shanks | ŞFive number-theoretic algorithmsŤ[END_REF] or Pohlig-Hellman algorithm [START_REF] Pohlig | ŞAn improved algorithm for computing logarithms overGF(p)and its cryptographic signiĄcance (Corresp.)Ť[END_REF], and some are probabilistic, such as Pollard-ρ algorithm [START_REF] Pollard | ŞMonte Carlo Methods for Index Computation (mod p)Ť[END_REF] or the distinguished points method [vW99]. In any case, all these algorithms have a query complexity which is exponential in log N . For some non-arbitrary groups, some improvements have been exhibited such as AdlemanŠs method, for the case where the group in which we intend to solve the DLP is a Ąnite Ąeld [START_REF] Adleman | ŞA subexponential algorithm for the discrete logarithm problem with applications to cryptographyŤ[END_REF]. The query complexity of all such speciĄc algorithms is not better than subexponential but in [START_REF] Barbulescu | ŞA Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small CharacteristicŤ[END_REF], a heuristic algorithm providing a quasi-polynomial complexity when N has a speciĄc form was introduced.

When Shor came up with his quantum algorithm, the impact was great because he showed that it is possible to efficiently solve the DLP with a query complexity polynomial in log N , the size of the considered group. We Ąrst show how he Ąrst reduced the DLP to a HSP in Z N × Z N and then give his algorithm for solving this latter problem right after. For more details on classical algorithms for the DLP, we refer to [START_REF] Barbulescu | ŞAlgorithms of discrete logarithm in Ąnite ĄeldsŤ[END_REF].

So indeed, the DLP can be written as a Hidden Subgroup Problem. An appropriate deĄnition of f to fall back on a HSP is the following:

f : Z N × Z N → G (α, β) → x α g β and this function f hides a subgroup H of Z N × Z N deĄned by H def = ¶(α, -α log g x) : α ∈ Z N ♢
and its cosets

(0, δ) + H = ¶(α, δ -α log g x) : α ∈ Z N ♢, δ ∈ Z N
since we have that every elements in a coset (0, δ) + H for δ ∈ Z N has the same image by f and this image is different for each coset:

∀α, δ ∈ Z N , f (α, δ -α log g x) = x α g -α log g x g δ = g δ .
ShorŠs algorithm is actually nothing more than SimonŠs algorithm adaptated from Z n 2 to Z N × Z N in the case of solving the DLP (and to Z N in the case of solving the period Ąnding problem). The Walsh-Hadamard transforms H ⊗n are simply replaced by

QFTŠs on Z N × Z N (Z N , respectively). Similarily, it assumes that the hiding function f is efficiently implementable in a quantum way, which is true since we know how to efficiently do an exponentiation with a quantum circuit (we will refer here to [START_REF] Vedral | ŞQuantum networks for elementary arithmetic operationsŤ[END_REF] but several papers improving the adder circuit which is used as a subroutine in the exponentiation algorithm have followed). Namely, we assume that we have a unitary U f for implementing f :

U f : ♣x⟩ ♣b⟩ → ♣x⟩ ♣b ⊕ f (x)⟩ .
Hereafter, Algorithm 2 provides a pseudo-code implementation of ShorŠs algorithm for the DLP.

Remarks on Shor's algorithm.

• The QFT over Z N can efficiently be approximated (e.g., [START_REF] Hales | ŞAn improved quantum Fourier transform algorithm and applicationsŤ[END_REF]) or even replaced by a QFT over Z 2 n where n def = ⌈log N ⌉, for example. Note that it can also be useful to decompose N by the fundamental theorem of arithmetic and thus uniquely write N = m i=1 p n i i where the p i Šs are distinct prime numbers and the n i Šs are integers. The QFT over Z N is then equivalent to the tensor product of the QFT over the cyclic group Z p n i i for i going from 1 to m.

• By the Ąrst measurement, an image of f is chosen, let say g δ , and the Ąrst register is projected on a superposition of the preimages (σ, τ ) by f of this g δ . Since we have g δ def = x σ g τ = g τ +σ log g x , we have τ = δσ log g x. Thus, we get a superposition of the couples (σ, δσ log g x) for σ ∈ Z N where δ is unknown.

Algorithm 2 ShorŠs algorithm for the DLP Require: A unitary U f to quantumly compute f . Ensure: The discrete logarithm log g x as deĄned in Equation 1.2.

1: Prepare a uniform superposition over Z N × Z N and use U f to compute f 1 N α,β∈Z N ♣α, β, f (α, β)⟩ = 1 N α,β∈Z N α, β, x α g β 2:
Measure the last register and discard it

1 √ N α∈Z N α, δ -α log g x 3: Apply the Fourier transform over Z N × Z N 1 N √ N α,ρ,σ∈Z N ω ρα+σ(δ-α log g x) N
♣ρ, σ⟩ 4: Measure the two registers to obtain a couple of values (σ log g x, σ) for some σ ∈ Z N 5: Compute σ -1 mod N , multiply it to σ log g x and output the result.

• If we look at the amplitude of the couple (α, β) just before the second measurement operator, we have 1

N √ N σ,α,β∈Z N ω ασ+β(δ-σ log g x) N ♣α, β⟩ = 1 N √ N α,β∈Z N ω βδ N   σ∈Z N ω σ(α-β log g x) N   ♣α, β⟩ = 1 √ N β∈Z N ω βδ N β log g x, β
where we used the following fact:

σ∈Z N ω σ(α-β log g x) N =    N if α = β log g x 0 otherwise.
So as stated in the penultimate step of the algorithm, we will obtain as a result of the measurement step a couple (β log g x, β) for some β ∈ Z N .

• The value β we obtain has an inverse modulo N with good probability, since β and N are coprime with probability ϕ(N ) N = Ω

1 log log N 
where ϕ is EulerŠs totient function, which allows us to retrieve log g x by repeating around log log N times the algorithm.

Standard Algorithm

It turns out that SimonŠs algorithm as well as ShorŠs algorithm, which respectively solve the hidden subgroup problem in Z n 2 and in Z N or Z N × Z N , can be seen as special cases of a more general algorithm. In the literature, it is often referred to as the standard algorithm and is mostly attributed to Kitaev [START_REF] Kitaev | ŞQuantum measurements and the Abelian Stabilizer ProblemŤ[END_REF]. The method behind this algorithm is called "coset sampling". It consists in the construction of a superposition of the elements of a coset of the hidden subgroup using the function that hides it, followed by the application of a quantum Fourier transform, which produces a superposition on the elements of the dual of the hidden subgroup. Thus, a measurement of this superposition will give an element of the latter, and thus of the hidden subgroup itself. This algorithm turns out to efficiently solve the hidden subgroup problem in any abelian group G. Indeed, we have the following theorem.

Theorem 1.1 (Th. 2.2 [START_REF] Ettinger | ŞOn Quantum Algorithms for Noncommutative Hidden SubgroupsŤ[END_REF]). Let f : G → S be a function that fulfills the subgroup promise with respect to a subgroup H. There exists a quantum algorithm that outputs a subset X ⊂ G such that X generates H with probability at least 1 -1/♣G♣. The algorithm uses O (log ♣G♣) evaluations of f and runs in time polynomial in log ♣G♣ and in the time required to compute f . A brief aside is made on the theory of characters (see next page), which will be useful for understanding and analyzing Algorithm 3, the algorithm in question for solving HSP, as well as others in the chapters to come. A word on character theory. Before giving some information which will be necessary to us on character theory, we must begin with representation theory. Essentially, it provides an important tool called "representation" to study abstract algebraic structures, by representing the elements of these structures by linear transformations of vector spaces. A representation is more precisely deĄned as follows.

Algorithm 3 Standard algorithm for abelian groups

Definition 1.2. Let G be a Ąnite group, V be a vector space over a Ąeld F and GL(V ) be the general linear group on V . A representation of G is a group homomorphism from

G to GL(V ).
In particular, the elements of a multiplicative group G will be represented by complex invertible matrices and thus we will be able to use linear algebra tools, which is particularly interesting. For more information on the theory of representations, we refer the reader to [START_REF] Schedler | Group representation theory[END_REF].

We now come to the character theory, which, in short, provides us with another tool called "character" that allows us to characterize the elements of a group by the trace of the matrix that represents them. The information given by the representation is not lost, it is simply compressed. Formally, a character is deĄned as follows.

Definition 1.3. Let G be a Ąnite group, V be a vector space over a Ąeld F and GL(V ) be the general linear group on V . The character of a representation ρ :

G → GL(V ) is χ ρ (g) : G → F g → Tr(ρ(g))
From this new notion, we can directly deĄne the dual group G ⊥ of G as the set of characters of G equipped with pointwise multiplication. In the same way, the dual H ⊥ of a subgroup H of G can be deĄned as follows.

H ⊥ def = χ g ∈ G ⊥ : χ g (h) = 1 ∀h ∈ H .
To Ąnish with this brief aside on characters, we give two properties that will be valuable to us later, on several occasions:

♣x⟩ QFT over G -------→ 1 ♣G♣ g∈G χ x (g) ♣g⟩ (1.3) h∈H χ g (h) =    ♣H♣ if χ g ∈ H ⊥ 0 otherwise. (1.4)
Once again we refer to [START_REF] Schedler | Group representation theory[END_REF] and to [START_REF] De | Quantum Computing: Lecture Notes[END_REF] for more details on character theory and on the link with the quantum Fourier transform, respectively.

Remarks on the standard algorithm.

• The Ąrst remark to be made concerns the QFT. How can it be implemented for any Ąnite abelian group G? One solution is to use the fundamental theorem of Ąnite abelian groups. Indeed, it says that G is isomorphic to the direct sum of cyclic subgroups of order a power of a prime number. Thus we can write that

G ≃ Z p n 1 1 × • • • × Z p nm m
where the p i Šs are distinct prime numbers and the n i Šs are integers. Therefore, the QFT over G is the tensor product of the QFT over the cyclic group Z p n i i for i going from 1 to m.

• By the Ąrst measurement, an image f (y) is chosen and the Ąrst register collapses on a superposition of the preimages of f (y), i.e. of the elements of the coset of y, y + H.

• If we look at the amplitude of an element g just before the second measurement operator, we have 1

♣G♣♣H♣ h∈H g∈G χ y+h (g) ♣g⟩ = 1 ♣G♣♣H♣ g∈G χ y (g)   h∈H χ h (g)   ♣g⟩ = 1 ♣G♣♣H♣ g∈G χ y (g)   h∈H χ g (h)   ♣g⟩ = ♣H♣ ♣G♣ g∈G : χg∈H ⊥ χ y (g) ♣g⟩ (by Equation 1.4)
So, as stated in the last step of the algorithm, we will obtain as a result of the measurement step an element g such that χ g ∈ H ⊥ .

Introduction to Code-Based Cryptography

The theory of error-detecting and error-correcting codes makes it possible to ensure the integrity of information when exchanged during a communication over a channel where errors can occur, or of data stored on a physical medium, such as a CD or a hard disk, where errors can also occur. The principle is simple: redundancy is added to the transmitted or stored information. Any alteration of this information can thus be detected and even corrected, depending on the amount of redundancy.

This step during which one takes a k bits message (which contains the information to be transmitted or stored) and one adds redundancy to it to form a n bits coded message (n being necessarily greater than k), is called encoding. Encoding corresponds in fact to the multiplication of a vector m (representing the message) by a matrix G of size k × n. The vector space given by the row space of this matrix is called a code. The recipient of the coded message mG will in fact recover a noisy version due to the alterations generated by the means of communication or storage, i.e. a vector y = mG + e of n bits where e is a vector representing the perturbations. Finding the original message m from y is then a task called decoding. This operation will be more or less complicated, depending on the vector e and on the encoding method used (whether more or less redundancy was added or whether a structure exists in the encoding method).

In the framework described so far, the objective is to make the decoding as simple as possible, preferably of polynomial complexity in n, in order to preserve the integrity of the transmitted information and especially to recover it easily. This is notably made possible by using codes with a strong structure, i.e. a structured matrix G. But errorcorrecting codes have found a second important use in cryptography, since it turns out that when G is drawn randomly, the decoding task has an exponential cost in n. It is in 1978 that McEliece proposed the Ąrst cryptosystem based on the theory of codes, opening the way to code-based cryptography. Widely studied since then, no generic algorithm with polynomial complexity is known, neither classical nor quantum, to attack cryptographic primitives built from codes, making it one of the most popular branches of post-quantum cryptography.

For an extensive introduction to error-correcting codes, we refer the reader to the well-known book by Huffman and Pless [START_REF] Huffman | Fundamentals of error-correcting codes[END_REF], which provides an extensive introduction to error correcting codes. We also mention other interesting resources for the reader interested in codes and which were good supports for writing this chapter. First, a chapter book written by Raphael Overbeck and Nicolas Sendrier [START_REF] Overbeck | ŞCode-based cryptographyŤ[END_REF] and some lecture notes by Alain Couvreur [START_REF] Couvreur | Introduction to coding theory[END_REF]

Definitions

We deĄne here some basic key terms of code theory in our context. The notation F will stand for a Ąnite Ąeld in this chapter. Recall that a Ąnite Ąeld contains q m elements, where q is a prime number and m a positive integer.

Codes and their representations

We start by formally deĄning what a code is: a code of length n is simply a subset of F n . Not convenient to use since it requires an exhaustive list of their elements, it is common to restrict ourselves to the case of linear codes (i.e., subspaces of F n ), which will be the kind of codes we will work on exclusively.

Definition 2.1 (Linear code C). Let n and k be integers with k ≤ n. A linear code of length n and dimension k over F is a k-dimensional vector space of F n and its elements are called codewords. We will refer to it as an [n, k] ♣F♣ -code and it will commonly be denoted by C.

For the sake of clarity, we will simply refer to linear codes as codes in what follows.

An important quantity to look at when considering a code is its rate. It quantiĄes the proportion of information contained in a coded message. A code is intimately linked to its dual, deĄned as follows.

Definition 2.3 (Dual code C ⊥ ). Let C be an [n, k] ♣F♣ -code. The dual code C ⊥ of C in F n is a code of dimension n -k, deĄned as C ⊥ def = ¶u ∈ F n : u • v = 0♢ .
The dual code C ⊥ of a linear code C over F can also be deĄned from the characters as follows:

C ⊥ def = ¶u ∈ F n : ∀c ∈ C, χ u (c) = 1♢
As brieĆy described in the introduction, a code can be represented by a matrix, called a generator matrix:

Definition 2.4 (Generator matrix G). Let C be an [n, k] ♣F♣ -code. A matrix G ∈ F k×n
such that the rows of G form a basis for C is a generator matrix for C.

In other words, any codeword can be expressed as a linear combination of the rows of a generator matrix of the code (note that a code can be represented by more than one generator matrix); and a linear code can be deĄned as the k-dimensional vector space C spanned by the rows of one of its generator matrices G:

C def = uG : u ∈ F k .
(2.1)

The generator matrix of the dual code C ⊥ of a code C is called a parity-check matrix of C.

Definition 2.5 (Parity-check matrix H). Let C be an [n, k] ♣F♣ -code. A matrix H ∈ F (n-k)×n such that the rows of H form a basis for C ⊥ is a parity-check matrix for C.

In other words, any vector that is orthogonal to all the codewords of C is a linear combination of the rows of a parity-check matrix of the code (note that a code can be represented by more than one parity-check matrix) and a linear code C can be deĄned as the kernel of one of its parity-check matrices H:

C def = c ∈ F n : Hc ⊺ = 0 . (2.2)
We have brieĆy mentioned that the encoding of a message m is done by computing mG where G is a generating matrix of the code. Decoding can be done in a similar way by multiplying the vector mG by the transpose of a parity check matrix, since GH ⊺ = 0 by deĄnition. Applying this decoding method to any vector of the Ąeld in which we work gives us what is called a syndrome. Definition 2.6 (Syndrome). Let H ∈ F (n-k)×n . The syndrome of a vector y ∈ F n with respect to H is deĄned as the vector yH ⊺ .

Since yH ⊺ = (c + e)H ⊺ = eH ⊺ only depends on the error in the noisy encoded message y = c + e where c ∈ C, the syndrome is a useful tool in the decoding process.

It turns out that the syndromes with respect to a code are representative of what are known as the cosets of the code.

Norm and distance

To work with error-correcting codes and to be able to specify this notion of decoding as well as that of error detection and correction, it is more than useful to equip our vector space with a norm, which we will call here a weight function and usually denote by ♣•♣. The distance induced by this norm will be denoted by d and is such that

∀x, y ∈ F n , d(x, y) = ♣x -y♣.
In what follows, the weight functions we will consider will typically be the Hamming weight for vectors and the rank weight for matrices and will be deĄned in Section 2. For the time being, we give generic deĄnitions that apply to any distance d, starting with that of ball, which is simply the set of elements whose distance to a certain point, the center, is less than or equal to a certain value, the radius. Definition 2.8 (Ball B r of radius r). Let n ∈ N, x be a vector of F n and r ≤ n be a nonnegative integer. The (closed) ball B r (x) of center x and radius r is deĄned as the subset of F n constituted of vectors at distance at most r from x, i.e.,

B r (x) def = ¶y ∈ F n : d(x, y) ≤ r♢ .
We will denote by B r a ball of radius r and B r its volume.

We similarly deĄne the notion of sphere, which is just the boundary of a ball: Definition 2.9 (Sphere S r of radius r). Let n ∈ N, x be a vector of F n and r ≤ n be a nonnegative integer. The sphere S r (x) of center x and radius r is deĄned as the subset of F n constituted of vectors at distance r from x, i.e., S r (x) def = ¶y ∈ F n : d(x, y) = r♢ .

We will denote by S r a sphere of radius r and S r its volume.

It straightforwardly follows that a ball B r is just the union of all the spheres S j with j ≤ r:

B r = r j=0 S j .
Keeping in mind the decoding objective, it is interesting to work with a code such that the balls centered on its codewords span as much as possible F n , without intersecting, since an intersection would mean that for some vectors of F n , there are several possible decodings, which is absolutely not desirable. Naturally, we must be interested in the smallest distance between two codewords in order to determine the largest radius we can take so that the balls do not overlap. Definition 2.10 (Minimum distance d min ). Let C be a code. Its minimum distance is deĄned as

d min (C) def = min c,c ′ ∈C : c̸ =c ′ d(c, c ′ ) . The relative minimum distance is δ min (C) def = d min (C) n
. When the context is clear, we will simply note d min and δ min .

Note that by linearity of the code, we can in fact prove that d min (C) = min c∈C\ ¶0♢ ¶♣c♣♢.

From there, taking r = d min -1 2 , it is straightforward that the balls B r (c) for c ∈ C are pairwise disjoint, yielding unique decoding. It is now interesting to see how the quantity d min behaves. It turns out that standard probabilistic arguments can be used to show that the minimum distance of a random linear code (i.e., a code C obtained as in Equation 2.1 by a generator matrix G chosen uniformly at random in F k×n ) is with overwhelming probability equal, up to an additive constant, to a quantity known as the Gilbert-Varshamov distance d GV (n, k) (or simply d GV if there is no ambiguity). Definition 2.11 (Gilbert-Varshamov distance d GV ). The Gilbert-Varshamov distance

d GV (n, k) of an [n, k] ♣F♣ -code is deĄned as the largest radius r for which B r ≤ ♣F♣ n-k .
This Gilbert-Varshamov distance also happens to quantify the region where we typically have unique decoding. More precisely, it turns out that the solution to the decoding problem for a random linear code is unique with probability 1 -2 -Ω(n) as long as for Ąxed positive ε,

r ≤ (1 -ε)d GV (n, k) (2.3)
when n goes to inĄnity. The Gilbert-Varshamov distance is crucial and will be very useful later on.

Computational Problems

The security of code-based cryptosystems relies on the hardness of computational problems such as the Decoding Problem and Short Codeword Problem. It is worth noting that efficient algorithms are known for solving these problems on some very speciĄc families of linear codes, but they are still difficult to solve on average, for codes uniformly drawn at random. We precisely deĄne these two problems in what follows.

• The Decoding Problem is a fundamental problem in coding theory. Given a linear code C and a noisy codeword y ∈ F n (i.e., a codeword to which an error has been added), the decoding problem (sometimes also referred as the nearest codeword problem) is to Ąnd the nearest codeword in C to y regarding the considered distance.

In the case of a random linear code C, which is the standard case, this problem can be expressed as follows:

Problem 2.1. Decoding Problem (DP). The decoding problem with parameters n, k, t ∈ N, which will be denoted by DP ♣F♣ (n, k, t), is defined as:

-Given: (G, mG + e) where G ∈ F k×n and m ∈ F k are sampled uniformly at random over their domain and e ∈ F n over the words of weight t, -Find: e.

In fact, it really corresponds to decoding the code generated by the rows of G, as in Equation 2.1.

The best algorithms for solving the decoding problem have exponential complexity in n as soon as t is linear in n and the code rate R is bounded away from 0 and 1.

The Decoding Problem can be stated in an equivalent manner, known as the Syndrome Decoding Problem. It is based on the fact that the parity-check matrix of a linear code C can be used to detect errors in a received word y by computing its syndrome. If y contains no errors, its syndrome is zero. Otherwise, the syndrome reveals information about the location and type of the errors.

• The Short Codeword Problem is another fundamental problem in coding theory. Given a linear code C and an integer w, the short codeword problem is to Ąnd a codeword c ∈ C \ ¶0♢ of weight at most w (regarding the weight induced by the considered distance). This problem is also sometimes referred to as the Low Weight Codeword Problem. In the case of a random linear code, this problem can be expressed as follows:

Problem 2.2. Short Codeword Problem (SCP). The Short Codeword Problem with parameters n, k, w ∈ N, which will be denoted by SCP ♣F♣ (n, k, w), is defined as:

-Given: H ∈ F (n-k)×n which is sampled uniformly at random, -Find: c ∈ F n such that Hc ⊺ = 0 and the weight of c belongs to (0, w].

In fact, we are looking for a non-zero codeword c of weight ≤ w in the code deĄned by the so-called parity-check matrix H, as in Equation 2.2.

The Short Codeword Problem becomes easy when the weight w is above a certain range. The reason is that the code is a vector space of dimension k: by solving a linear system, we can produce codewords with k -1 entries equal to 0, which gives good candidates for having a small weight. This strategy produces in polynomial time codewords of weight ≈ ω easy (n, k)n, where ω easy (n, k) is some important quantity that we will explicit in details in the next section. Below this quantity ω easy (n, k), the best known algorithms for solving the SCP have an exponential complexity for a Ąxed rate R and a Ąxed ratio ω = w n . Obtaining larger weights is also readily obtained by choosing only part of the k -1 entries to be equal to 0.

Weights

We will focus in this manuscript on two weights, which are also often called metrics, namely the Hamming weight and the rank weight. The former was introduced more than seventy years ago by Richard Hamming [START_REF] Hamming | ŞError detecting and error correcting codesŤ[END_REF] and is the one that was historically the Ąrst used in code-based cryptography, while the latter has been introduced in the context of matrix codes by Philippe Delsarte [START_REF] Delsarte | ŞBilinear Forms over a Finite Field, with Applications to Coding TheoryŤ[END_REF]. Other weights can be used to build error-correcting codes such as the Lee weight, due to William Lee [START_REF] William | ŞSome properties of nonbinary error-correcting codesŤ[END_REF], but it will not be studied here.

Hamming Weight

The most commonly used weight in coding theory is the Hamming weight. The Hamming weight w H of a vector is deĄned as the number of its non-zero coordinates, implying that the Hamming distance d H measures the number of positions at which two vectors of equal length differ. Formally, we have Definition 2.12 (Hamming weight w H ). Given a vector x = (x 1 , . . . , x n ) ∈ F n q , its Hamming weight is deĄned as

w H (x) = ♣ ¶i ∈ 1, n : x i ̸ = 0♢♣.

Properties for the Hamming weight

Let F q be a Ąxed Ąeld. We give a collection of properties that will be useful in Chapter 3, starting with the volume of a sphere.

S r = n r (q -1) r .
Lemma 2.2 (Bounding S r (Lemma 3.11 of [START_REF] Couvreur | Introduction to coding theory[END_REF])). Let n ∈ N and p ∈ 0, 1 -1 q such that pn ∈ N. Then S pn ≤ q nhq(p) .

The Gilbert-Varshamov distance is more precisely deĄned as follows for Hamming metric.

Lemma 2.3 (Relative Gilbert-Varshamov distance δ GV ). The relative Gilbert- Varshamov distance δ GV of a random [n, k] q -code is δ GV = h -1 q  1 - k n  + O  1 n  .
We end with a theorem giving a simple bound involving explicitly the rate of a code and the Gilbert-Varshamov bound.

Theorem 2.1 (Theorem 4.10 of [START_REF] Couvreur | Introduction to coding theory[END_REF]). There exists a sequence of linear codes (C i ) i over a fixed field F q whose lengths sequence tends to infinity, rates sequence converges to R and relative distance sequence converges to δ and such that R ≥ 1h q (δ).

Finally, we give an expression for the bound ω easy (n, k) under which it is difficult to Ąnd short codewords by solving a linear system where we aim to produce codewords with k -1 entries equal to 0.

Definition 2.13 (Short Codewords Bound). The bound ω easy (n, k) of a random [n, k] qcode is deĄned as

ω easy (n, k) def = q -1 q  1 - k n  .

Hardness of DP and SCP in the context of Hamming weight

The decoding problem for random linear codes has been studied for a long time and despite many efforts on this issue, the best algorithms are exponential in the codelength The decision version of the short codeword problem has also been proved to be NPcomplete [START_REF] Vardy | ŞThe Intractability of Computing the Minimum Distance of a CodeŤ[END_REF] and while the security of many code-based cryptosystems relies on the hardness of the decoding problem, it can also be based on Ąnding a ŞshortŤ codeword, as in [START_REF] Misoczki | MDPC-McEliece: New McEliece Variants from Moderate Density Parity-Check Codes[END_REF] or in [App+17; Bra+19; Yu+19] to build collision resistant hash functions for example.

n

Rank Weight

In recent years, there has been growing interest in developing cryptographic primitives based on the rank weight, a mathematical concept that measures the dimension of the vector space spanned by the rows of a matrix. It is thus tempting to deĄne codes embedded with this metric: these codes are named matrix codes and their codewords are matrices. The rank metric has been extensively studied in the area of network coding, where it is well-suited for the kind of errors that occur.

Definition 2.14 (Matrix code). Let M m×n (F q ) be the set of m × n matrices with coefficients in F q . An [m × n, K] q -code is a K-dimensional linear subspace of M m×n (F q ) called a matrix code.
The set of codes on F q m , which are known as F q m -linear codes, is a subset of the class of matrix codes (see [START_REF] Faugère | ŞCryptanalysis of MinrankŤ[END_REF]). Indeed, we can associate a matrix from F m×n q to any vector from F n q m by using a basis of F q m over F q and thus associate a matrix code to a F q m -linear code.

Definition 2.15 (Matrix code associated to a F q m -linear code). Let β = (β 1 , . . . , β m ) be a basis of F q m over F q and C be a F q m -linear code. To each word

x = (x 1 , . . . , x n ) ∈ C we can associate a m × n matrix M(x) = (m ij ) i∈ 1,m j∈ 1,n
with entries in F q such that for any j in 1, n :

x j = m i=1 m ij β i .
The set ¶M(x) : x ∈ C♢ is the matrix code over F q associated to C. The rank of x is then deĄned as the rank of M(x):

rank (x) def = rank (M(x)) . The rank distance d R follows from this deĄnition. For x, y ∈ F n q m , d R (x, y) = rank (x -y) .
Note that the representation of a F q m -linear code is cheaper than the one of the corresponding matrix code, making the former particularly interesting.

Remark 2.1. Let us take a [n, k] q m -code and its associated matrix code, which is a [mn, mk] q -code. We will need k(n-k)m log q bits to represent the former while mk(mnmk) log q bits are required to represent the latter. It is therefore more appropriate to work with F q m -linear codes as they offer a storage gain of a factor m over their matrix code counterpart.

Properties for the rank weight

We can now give a closed formula for the size of a sphere of radius r. It is equal to the number of matrices in F m×n q of rank r.

Lemma 2.4 (Volume S r of a sphere S r ). Let r be a positive integer. We have

S r def = ♣S r ♣ =   r-1 j=0 (q m -q j )   n r q .
Where the Gaussian coefficient n r q is deĄned by

n r q def =    r-1 j=0 q n -q j q r -q j if r ≤ n 0 otherwise (2.4)
We have some bounds on the volume of a sphere and thus on the one of a ball:

Lemma 2.5. We have q (m+n-2)r-r 2 ≤ S r ≤ q (m+n+1)r-r 2 (2.5)

q (m+n-2)r-r 2 ≤ B r ≤ q (m+n+1)r-r 2 +1 (2.6) Using the fact that ∞ i=1 (1 -q -i
) is some constant depending on q, we can prove the following asymptotic expressions for Gaussian coefficients and for the volume of a sphere:

Lemma 2.6 (Asymptotic expressions). As n → +∞, n r q = Θ q r(n-r)  (2.7) S r = Θ q r(m+n-r)  (2.8)
From Equation 2.8 we deduce that

S u+1 S u = Θ q (u+1)(m+n-u-1) q u(m+n-u) = Θ q m+n-2u-1  .
(2.9)

We can take back the DeĄnition 2.11 of the Gilbert-Varshamov distance and approximate the ball B r by its boundary S r . Injecting Equation 2.8 in the expression then yields a useful and simple relation on the Gilbert-Varshamov distance, stated in the following Lemma for any matrix code.

Lemma 2.7 (Gilbert-Varshamov distance [START_REF] Faugère | ŞCryptanalysis of MinrankŤ[END_REF]). The relative Gilbert-Varshamov

distance δ GV of an [m × n, K] q -code (with m ≥ n) satisfies the relation K ≤ (m -δ GV )(n -δ GV ).

Hardness of DP and SCP in the context of rank weight

Contrary to their counterparts in Hamming metric, the decision versions of the decoding and short codeword problems are not known to be NP-complete. However, Gaborit and Zémor proved that the decoding problem in Hamming metric, which is an NP-complete problem, can be reduced by a randomized reduction to the decoding problem in rank metric [START_REF] Gaborit | ŞOn the hardness of the decoding and the minimum distance problems for rank codesŤ[END_REF].

In addition, some cryptosystems have been proposed, based on these problems. Namely, we can cite the Ąrst one, introduced in [GPT91] and notable for the fact that it is a translation in rank metric of the McEliece cryptosystem. It suffered from several attacks, e.g., in [START_REF] Gibson | ŞThe Security of the Gabidulin Public Key CryptosystemŤ[END_REF][START_REF] Overbeck | ŞA New Structural Attack for GPT and VariantsŤ[END_REF]. It is worth noticing that two rank-based cryptosystems made it to the second round of the NIST Post-Quantum Standardization Process, namely ROLLO [START_REF] Aragon | Second round submission to the NIST post-quantum cryptography call[END_REF] and RQC [START_REF] Aguilar Melchor | Rank Quasi Cyclic (RQC). Second Round submission to NIST Post-Quantum Cryptography call[END_REF] and several rank-based signature schemes have been presented to the NIST Ąrst round of the Standardiation Process of additional signatures, such as MIRA [START_REF] Aragon | Round 1 Submission to the NIST Post-Quantum Cryptography Additional Signatures Call[END_REF], MiRitH [START_REF] Adj | Round 1 Submission to the NIST Post-Quantum Cryptography Additional Signatures Call[END_REF] or RYDE [START_REF] Aragon | RYDE. Round 1 Submission to the NIST Post-Quantum Cryptography Additional Signatures Call[END_REF] for example.

Regarding attacks on these problems, for a long time combinatorial attacks were the only ones considered useful and consist in some Information Set Decoding equivalents [CS96; GRS16; Ara+18]. However, algebraic attacks have made their way and have recently been shown to be more effective than the former [OJ02; Bar+20; Bar+20; Bar+22]. These algebraic attacks have notably impacted NISTŠs decision not to move ROLLO and RQC to the third round of the Standardization Process (as well as the signature schemes Rainbow and GeMSS, in multivariate cryptography).

Finally, it is important to note that the key sizes of rank metric cryptosystems are generally smaller than those in Hamming metric, since the complexity of rank metric attacks is higher than in Hamming metric. On the other hand, the Hamming metric has been much more widely studied than the rank metric, which is more recent.

Chapter 3 From Decoding to Finding Short Codewords

Decoding and looking for short codewords are problems that have been conjectured to be extremely close. These problems can be viewed in some sense as a code version of the LWE and SIS problems respectively in lattice-based cryptography [START_REF] Regev | ŞOn lattices, learning with errors, random linear codes, and cryptographyŤ[END_REF]. Our contribution in this chapter, based on [START_REF] Debris-Alazard | ŞQuantum Reduction of Finding Short Code Vectors to the Decoding ProblemŤ[END_REF], is precisely to give the code-based version of this reduction, namely a quantum reduction from Ąnding short codewords to decoding. This problem was open for quite some time. To simplify the statements, we will state it in the regime of parameters where the rate R is Ąxed in (0, 1), but actually it also works in the LPN setting (but needs to be adapted in several places where we use exponential bounds in n).

There is a fundamental difficulty of reducing the research of low weight codewords to decoding a linear code which is due to the fact that the nature of these two problems is very different. Decoding concentrates on a region of parameters where there is typically just one solution, whereas Ąnding low weight codewords concentrates on a region of parameters where there are solutions (and typically an exponential number of solutions). This makes these problems inherently very different. This was also the case for the reduction from SIS to LWE and the fact that we can have a reduction from one to another by looking for quantum reductions instead of classical reductions was really a breakthrough at that time.

Regev's quantum reduction strategy adapted to coding theory. In [START_REF] Regev | ŞOn lattices, learning with errors, random linear codes, and cryptographyŤ[END_REF] (see also the extended version [START_REF] Regev | ŞOn lattices, learning with errors, random linear codes, and cryptographyŤ[END_REF]) Regev showed how to transform a random oracle solving the decoding problem in a lattice into a quantum algorithm outputting a rather small vector in the dual lattice. Our aim is to show here that the natural translation of this approach in coding theory gives an algorithm that outputs a rather small vector in the dual code. Roughly speaking RegevŠs approach relies on a fundamental result about the Fourier transform. This innocent looking fact, together with the fact that the quantum Fourier transform can be performed in polylog time when the group G is Abelian, is arguably the key to several remarkable quantum algorithms solving in polynomial time the period Ąnding in a vectorial Boolean function [START_REF] Daniel | ŞOn the Power of Quantum ComputationŤ[END_REF], the factoring problem or the discrete logarithm problem [START_REF] Shor | ŞAlgorithms for quantum computation: Discrete logarithms and factoringŤ[END_REF]. All of these problems can be rephrased in terms of the hidden Abelian subgroup problem, where one is given such a function f that is constant (and distinct) on the cosets of an unknown subgroup H and one is asked to recover H. This is achieved by

(i) creating the uniform superposition 1 √ ♣G♣ x∈G ♣x⟩ ♣f (x)⟩,
(ii) measuring the second register and discarding it, yielding a quantum state of the

form 1 √ ♣H♣ h∈H ♣x + h⟩,
(iii) applying the QFT to it yielding a superposition of elements in the dual subgroup H ⊥ (and therefore gaining information on H in this way).

Proposition 3.1 is used in a similar way in RegevŠs reduction. Translating RegevŠs reduction in coding theory would use this framework by considering that the linear code C we want to decode plays the role of the aforementioned H. From now on we will assume that this code is of dimension k and length n over F q . The algorithm would basically look as follows for reducing the search of small codewords in the dual code

C ⊥ = c ⊥ ∈ F n q : c • c ⊥ = 0, ∀c ∈ C (where x • y = n i=1 x i y i is the standard inner product in F n q ) to decoding errors of weight t in C.
Step 1. Use a quantized version of the decoding algorithm to prepare the state

1 √ Z c∈C,e∈F n q π e ♣c + e⟩
where Z is a normalizing constant and (♣π e ♣ 2 ) e is a probability distribution on errors that concentrate around the weight t we are able to decode. This is done (i) by preparing Ąrst a superposition of codewords and errors,

1 √ Z c∈C e∈F n q π e ♣c⟩ ♣e⟩ ,
(ii) then adding the second register to the Ąrst one to get the entangled state

1 √ Z c∈C e∈F n q π e ♣c + e⟩ ♣e⟩
(iii) and Ąnally disentangling it thanks to a quantized version of the decoding algorithm, which from c + e recovers e and subtracts it from the second register to get the state

1 √ Z c∈C e∈F n q π e ♣c + e⟩ ♣0⟩ .
Step 2. Apply the QFT on F n q to obtain a superposition of elements c ⊥ in the dual code

c ⊥ ∈C ⊥ α c ⊥ c ⊥ .
Step 3. Measure the register to output c ⊥ of rather small norm in C ⊥ .

The second step is a direct consequence of Proposition 3.1. The last one raises the issue of whether or not the QFT concentrates the weight of the vector output by this algorithm on weights t ′ for which Ąnding a codeword in C ⊥ is not known to be easy, as it is the case for RegevŠs reduction on lattices equipped with the Euclidean metric.

On the difficulty of translating Regev's reduction to the Hamming metric.

The natural analog in the Hamming metric case of the Gaussian noise model used in RegevŠs reduction [START_REF] Regev | ŞOn lattices, learning with errors, random linear codes, and cryptographyŤ[END_REF] is the q-ary symmetric channel. Its associated quantum state is given by

π SC def = e∈F n q (1 -τ ) n-♣e♣ 2  τ q -1  ♣e♣ 2 ♣e⟩ =   √ 1 -τ ♣0⟩ + α∈F * q τ q -1 ♣α⟩   ⊗n
where ♣e♣ stands for the Hamming weight of e, n for the length of e and τ is the crossover probability of the q-ary symmetric channel. Indeed, measuring such a state yields an error distributed like a q-ary symmetric channel of crossover probability τ . In both cases (be it for the Gaussian noise or the q-ary symmetric channel), the Fourier transform yields a dual noise which is again Gaussian or q-ary symmetric respectively and the quantum state corresponding to the error is a product state which considerably simpliĄes the computation. In the case of the q-ary symmetric noisy chanel, applying the QFT on π SC yields the quantum state

e∈F n q (1 -τ ⊥ ) n-♣e♣ 2 τ ⊥ q -1 ♣e♣ 2 ♣e⟩ =   1 -τ ⊥ ♣0⟩ + α∈F * q τ ⊥ q -1 ♣α⟩   ⊗n def = ♣π SC ⟩
where (see Fact 1)

τ ⊥ def = (q -1)(1 -τ ) - √ τ  2 q .
This new quantum state represents a q-ary symmetric channel of parameter τ ⊥ . If we measure π SC we get relative weights ≈ τ whereas if we measure ♣π SC ⟩ we get relative weights around τ ⊥ .

It would thus be tempting to conclude that the ŞidealŤ version of the algorithm presented above will output dual codewords (in Step 3) of relative Hamming weight ≈ τ ⊥ < ω easy , i.e., in the regime where there is a chance that it is difficult to produce such words. However, this natural approach runs into the following problem. The parameter τ of the Bernoulli noise has to be chosen so that the typical error weight τ n is equal to or slightly below the weight t we can decode. Such a τ is therefore at most the relative Gibert-Varshamov δ GV . However, it can be proved that in this case the most likely relative weight we measure at Step 3 is typically zero if τ ⊥ < ω easy . In other words, the straightforward application of RegevŠs approach to coding theory fails to give a useful reduction.

We will give in Remark 3.1 another explanation for the failure of this approach. It can be summarized by saying that the Bernoulli noise model is not concentrated enough on its typical weight τ n.

Fact 1. Let π SC def =  √ 1 -τ ♣0⟩ + α∈F * q τ q-1 ♣α⟩  ⊗n
, where τ ∈ 0, q-1 q , then

♣π SC ⟩ =   1 -τ ⊥ ♣0⟩ + α∈F * q τ ⊥ q -1 ♣α⟩   ⊗n
, where (3.1)

τ ⊥ def = (q -1)(1 -τ ) - √ τ  2 q . (3.2) Proof. Let ♣ψ⟩ def = √ 1 -τ ♣0⟩ + α∈F * q τ q-1 ♣α⟩. Then, it is readily veriĄed that ♣π SC ⟩ = ♣ψ⟩  ⊗n where ♣ψ⟩ = 1 √ q   β 0 + y∈F * q β y ♣y⟩   with β 0 = √ 1 -τ + (q -1) τ q -1 and β y = √ 1 -τ + τ q -1 x∈F * q χ y (x).
It is easy to verify that for any y ∈ F * q we have for any

x 0 ∈ F * q : x∈Fq χ y (x) = x∈Fq χ y (x 0 • x) = χ y (x 0 ) x∈Fq χ y (x)
Since there exists x 0 ∈ F * q such that χ y (x 0 ) ̸ = 1, we deduce that x∈Fq χ y (x) = 0. Now since x∈Fq χ y (x) = 1 + x∈F * q χ y (x), we have x∈F * q χ y (x) = -1 for any y in F * q and therefore

β y √ q = 1 -τ q - τ q(q -1) = (q -1)(1 -τ ) q(q -1) - τ q(q -1) = (q-1)(1-τ ) q -τ q √ q -1 = √ τ ⊥ √ q -1 . It is then clear that β 0 √ q = √ 1 -τ ⊥ from y∈Fq ♣β y ♣ 2 = 1, concluding the proof.
Our approach. To tackle this issue, it would therefore be natural to choose the most concentrated noise model on the weight t, namely:

π unif = e : ♣e♣=t 1 √ S t ♣e⟩
where S t is the cardinality of the sphere of radius t in the Hamming metric, i.e., S t = (q -1) t n t . Understanding of which weight w is the outcome after measuring the state c ⊥ ∈C ⊥ α c ⊥ c ⊥ in Step 3 is more difficult in the constant weight error model than in the Bernoulli noise model. In particular, it involves properties of Krawtchouk polynomials. However, it can be shown that when

ω def = w n lies in a whole interval τ ⊥ , τ ⊥ + where τ ⊥ + def = √ (q-1)(1-τ )+ √ τ 2 q
, we have many points where the probability of measuring a word of weight w is actually 1 poly(n) . The ŞdualŤ weight distribution is not really concentrated on a single value but spread over a large interval. This would provide a useful reduction when we use a decoding algorithm that succeeds on a non-negligible set of inputs.

Unfortunately, to be relevant in a cryptographic context, we must consider the case where decoding succeeds only for a potentially very low probability ε, the aim being to turn our decoding algorithm into an algorithm that produces a low weight codeword from the dual with some probability poly(ε). This cannot be obtained with the uniform distribution on the sphere of radius t. Indeed, the ŞidealŤ version of the algorithm we presented before (where we assume we always succeed with our decoding algorithm) describes a state we obtain in Step 2 that is not completely orthogonal (the scalar product is bounded from below by a quantity poly(ε)) to the ŞrealŤ state after applying this approximate decoding process and the QFT. If we were to measure this state directly (starting from the uniform noise model over the sphere of radius t), we would only be sure to measure a word of some relative weight lying in the interval τ ⊥ , τ ⊥ + with probability poly(ε), since the ŞidealŤ state concentrates its relative weight distribution in all this interval. In this way, we cannot ensure the measurement of a dual codeword of smallest possible relative weight, namely τ ⊥ , it could be 1/2 ∈ τ ⊥ , τ ⊥ + . We really need here a distribution that is rather sharply concentrated around the decoding radius of our decoding algorithm, but whose Fourier transform is also sharply concentrated around a certain weight.

So far, two noise models have been considered for the reduction to work, each with an advantage and a drawback:

• the q-ary symmetric noise π SC is not concentrated enough on its typical weight τ n but its dual noise is sufficiently concentrated on τ ⊥ n,

• the uniform noise π unif on the sphere of radius τ n is sufficiently concentrated but its dual noise is spread out on the whole interval

τ ⊥ n, τ ⊥ + n  .
Interestingly, the issues with these two distributions are opposite. Fortunately, it turns out that we have a natural noise model to get a best-of-both-worlds model: truncating the q-ary symmetric noisy channel. More precisely, consider the following noise model (for some small enough constant ε > 0),

π Trunc = 1 √ N e : ♣e♣∈[(1-ε)t,(1+ε)t] (1 -τ ) n-♣e♣ 2  τ q -1  ♣e♣ 2 ♣e⟩
where N is a normalizing factor. This noise model solves our above issues with π SC and π unif because it veriĄes our two constraints for the reduction to work:

(i) its weight distribution is sufficiently concentrated around τ n, (ii) its dual noise after applying the Fourier transform is concentrated on the relative weight τ ⊥ n.

Contrary to (i), assertion (ii) may seem unclear. It relies on the following equality as we will show in Lemma 3.11

π Trunc -π SC = 2 -Ω(n)
where ∥•∥ stands for the norm of the Hilbert space in which the quantum states are embedded. Therefore, applying the Fourier transform (which is an isometry for ∥•∥) on π Trunc will yield a quantum state which is 2 -Ω(n) -close of ♣π SC ⟩.

With our approach and the truncated q-ary symmetric channel, we transform through the QFT a decoding algorithm correcting τ n errors into an algorithm outputting with non-negligible probability words of weight ≈ τ ⊥ n in the dual code. The distance τ ⊥ is clearly a decreasing function of τ and the issue is now whether or not there exists a τ < δ GV (n, k) (this is the biggest value for which we can hope that decoding is successful with probability 1o(1)) such that τ ⊥ < ω easy (n, nk) (here we want to Ąnd short codewords in the dual code C ⊥ which is of dimension nk), since this would yield a useful reduction. It turns out that in many cases we have to choose τ > δ GV (n, k)/2, meaning that we are not in the regime where decoding necessarily has at most one solution. This complicates the proof of the reduction somewhat since with a quantized version of the decoding algorithm, we will not be able to produce at Step 1 the state

1 √ Z c∈C e∈F n
q π e ♣c + e⟩ (since decoding fails for some e) but we will show that as long as τ < δ GV (n, k), we will get a state close to it. This will be enough for our purpose.

By putting all these ingredients together, we are able to prove the following result.

Theorem 3.1 (informal). The short codeword problem SCP(q, n, nk, w) reduces to the decoding problem DP(q, n, k, t) for w = τ ⊥ n + O(1) where

τ def = t n and τ ⊥ def = (q -1)(1 -τ ) - √ τ  2 q .
It will turn out that for q = 2 (see Section 2) we can Ąnd for any rate R = k n in (0, 1) a t < d GV (n, k) for which the corresponding w is below ω easy (n, nk)n (the reduction is useful in this case). It also corresponds to parameter ranges that are relevant for certain cryptographic applications (see [START_REF] Augot | ŞA family of fast syndrome based cryptographic hash functionsŤ[END_REF] whose security relies on the SCP problem in a parameter range which is covered by our reduction and [START_REF] Stern | ŞA New IdentiĄcation Scheme Based on Syndrome DecodingŤ[END_REF] which is an identiĄcation scheme whose security actually relies on the decoding problem just below the Gilbert-Varshamov distance). Unfortunately, this is not true anymore when q ≥ 5, where there is always a range for R for which w is above ω easy (n, nk)n, for any choice of t < d GV (n, k). The reduction then starts to become useless since the range in question gets larger when q grows. Roughly speaking, when q grows, the Hamming metric gets coarser (we have only n + 1 different values for the metric on F n q , whereas the size of the ambient space gets bigger) and this results in the range of values of R for which this reduction is useful becoming smaller.

Considering other metrics.

The whole approach we have followed here (properly choosing the error distribution and going beyond the unique decoding radius for decoding if necessary) can of course be adapted to other metrics. It is easy for instance to apply it to the rank metric which is becoming increasingly popular in code-based cryptography, see for instance [Ara+19; Agu+20; Bel+19; Bel+20]. This metric is even coarser than the Hamming metric: on F m×n q there are only 1 + min(m, n) different values for the rank weight (given a matrix, it is deĄned as its rank). In this case, as we will see, the reduction is always useless (i.e., reduces to weights which are always easy to produce for a random linear code). We assume here that we have a probabilistic algorithm A that solves (sometimes) the decoding problem at distance t. Its inputs are a generator matrix G ∈ F k×n q of a code

Contents

C ⊆ F n q (i.e., C = uG : u ∈ F k q
) and a noisy codeword c + e where c belongs to C. We denote by r ∈ F ℓ 2 the internal coins of A . It outputs with a certain probability ε, the ŞrightŤ e when being fed with c + e where c and e are uniformly chosen at random in C and among the errors of weight t respectively: c,e,r (A (G,c + e,r) = e) .

ε def = P G,
(3.3)

The quantum reduction starts by building the initial superposition 1 2 ℓ q k e∈F n q c∈C r∈F ℓ 2 π e ♣e⟩ ♣c⟩ ♣r⟩ where ♣π⟩ def = e∈F n q π e ♣e⟩ is some quantum superposition of errors. It then acts as follows.

Algorithm of the quantum reduction.

Initial state = 1 2 ℓ q k e∈F n q c∈C r∈F ℓ 2 π e ♣e⟩ ♣c⟩ ♣r⟩ adding e to c: → 1 2 ℓ q k e∈F n q c∈C r∈F ℓ 2 π e ♣e⟩ ♣c + e⟩ ♣r⟩ applying A : A → 1 2 ℓ q k e∈F n q c∈C r∈F ℓ 2 π e ♣e -A (G, c + e)⟩ ♣c + e⟩ ♣r⟩ def = ♣ψ A ⟩ (3.4)
QFT on 2nd reg:

→ ♣ψ A ⟩ (3.5) measuring the state: → ♣e⟩ c ⊥ ♣r⟩ (3.6)
We will now give a general theorem about an algorithm of this kind and will show that it produces a codeword of the dual code C ⊥ of some weight u with probability poly(ε) when certain conditions are met. We recall that S u denotes the volume of a sphere of radius u (see DeĄnition 2.9).

Theorem 3.2. Assume that ♣π⟩ is radial and non-negative, i.e., π e = f (♣e♣) for some nonnegative function f . Assume that ♣π⟩ = e∈F n q π e ♣e⟩ is radial too (1) and let f (w) = π e for any element e of F n q of weight w. Furthermore, assume that there exists an interval (1) In other words, we assume that the Fourier transform is radially preserving. This property depends on the characters chosen to define the Fourier transform and the metric. Recall that a radial function is a function which is constant on spheres centered around 0. This property clearly holds for functions f : F n q → C with the characters chosen here and the Hamming metric. We give this more general statement in order to apply it in other cases of interest, for instance the rank metric.

W ⊆ 0, n such that:

(Concentration of π) ⟨π♣1⟩ 2 q n-k = 2 -Ω(n) , (C1) (Exponentially many dual codewords of weight u ∈ W ) u∈W q k S u = 2 -Ω(n) , (C2) (Concentration of the dual distribution π on W ) u∈W S u f (u) 2 = 1 -2 -Ω(n) (C3)
with ♣1⟩ being the (unnormalized) superposition of errors : ♣1⟩ def = e∈F n q ♣e⟩. Suppose that there exists an algorithm A solving the decoding problem DP(q, n, k, t) with success probability ε. Then, there exists a quantum algorithm which takes as input a generator matrix G ∈ F k×n q of C and outputs a codeword of weight u ∈ W in C ⊥ with probability greater than

p 2 t ε 3 16 -O(p 4 t ε 5 ) -2 -Ω(n) -O q -min(k,n-k)
 where

p t def = e : ♣e♣=t ♣π e ♣ 2 = S t f (t) 2 .
Remark 3.1.

• We will use this theorem for Hamming and rank metrics, but it can be applied to any metric for which the Fourier transform is radially preserving.

• When π e is non-negative, Condition (C1) basically requires the probability distribution on F n q , µ def = (π 2 e ) e∈F n q , to be sufficiently concentrated. This quantity can be expressed as q k (1 -H 2 (µ, U )) 2 , where U stands for the uniform distribution over F n q and H(p, q) def = 1i √ p i q i is the Hellinger distribution between two probability distributions p and q deĄned over a same probability space.

1. It is clearly maximal for the uniform probability distribution over F n q , and 2. on the other hand, when considering the Hamming metric and ♣π⟩ = π SC , we have

π SC 1 2 q n-k = q k q n y∈F n q χ y (0)π y 2 = q k f (0) 2 = q k (1 -τ ⊥ ) n .
It can be veriĄed that there is no way to choose τ such that at the same time:

(i) τ n ≤ d GV (n, k) (otherwise there is no hope to decode correctly most of the time),

(ii) τ ⊥ ≤ ω easy (otherwise Ąnding codewords in C ⊥ of weight τ ⊥ n is easy), (iii) q k (1 -τ ⊥ ) n = o(1).
The quantity

⟨π SC ♣1⟩ 2 q n-k
is just too big, or in other words, the distribution of µ is too much spread out and not concentrated enough on its typical weight.

• Condition (C2) expresses that u lies in a subset of values for which a random [n, nk]-code has an exponential expected number of codewords. Indeed, the expected number of codewords of weight u is equal to Su q k .

• Finally, Condition (C3) expresses that the dual probability distribution

µ def = (♣ π e ♣ 2 ) e∈F n
q is almost completely supported on W up to an exponentially small vanishing term.

Outline of the proof of Theorem 3.2

Let us Ąrst give a general outline of the proof before detailing each step.

Step 1. We prove that after applying A in the reduction, ♣ψ A ⟩ is close enough to the ŞdisentangledŤ state

♣ψ ideal ⟩ def = 1 √ Z e∈F n q c∈C r∈F ℓ 2 π e ♣0 n ⟩ ♣c + e⟩ ♣r⟩ (3.7)
where Z is a normalizing constant.

Step 2. We then analyze the effect of the QFT on the Şideal stateŤ ♣ψ ideal ⟩ and a subsequent measurement of it. We namely prove that measuring it produces a codeword c ⊥ ∈ C ⊥ of weight u with probability f (u) 2 , up to a normalizing factor.

Step 3. Then we prove that the number of codewords of weight u in C ⊥ is typically very close to Su q k . With Step 2 and the assumptions of Theorem 3.2, we infer that the probability of observing a dual codeword of weight in the set W after measuring ♣ψ ideal ⟩ is exponentially close to 1.

Step 4. We upper-bound the statistical distance between the probability distribution of the states after measuring ♣ψ A ⟩ and ♣ψ ideal ⟩ respectively by using Step 1 and the properties of the trace distance given in Fact 2 below.

Let us give more details about these steps.

Step 1. For this purpose, we use the trace distance between quantum states (as in [START_REF] Stehlé | ŞEfficient Public Key Encryption Based on Ideal LatticesŤ[END_REF] where this has been used in the lattice setting). It is deĄned as follows :

D tr (♣ϕ⟩ , ♣ψ⟩) def = 1 -♣⟨ϕ♣ψ⟩♣ 2 . (3.8)
This distance meets the following properties that will prove useful in our context: Fact 2.

(I) It can never increase after a quantum evolution [NC16, §9, Th. 9.1];

(II) The pair of probability distributions (p m , q m ) of the measurement outcome m of any quantum measurement performed on the pair of states (♣ϕ⟩ , ♣ψ⟩) satisfies [NC16, §9, Th. 9.2]

D stat (p m , q m ) ≤ D tr (♣ϕ⟩ , ♣ψ⟩) (3.9)
where D stat is the statistical distance (also called the total variation distance) between two probability distributions. It is defined by:

D stat (p, q) def = 1 2 x∈X ♣p(x) -q(x)♣
where p and q are two discrete probability distributions on X .

With this notion we can prove that Proposition 3.2. With probability greater than 1

-⟨π♣1⟩ 2 q n-k -O q -min(k,n-k)
 over the choices of G we have:

D tr (♣ψ A ⟩ , ♣ψ ideal ⟩) ≤ 1 - p 2 t 2 ε 2 G ,
where ε G is the probability that A returns the right error e when the input matrix is G, i.e., (3.10)

The proof of this result follows immediately from three lemmas (whose proof is in Section 3.1). The Ąrst one bounds the trace distance in terms of ε G and Z, and the second one gives a tight upper-bound on the expected value of Z for a related probabilistic model. The latter is used to derive the third one which is fundamental and states that it is very unlikely for Z to be much greater than the ŞnaturalŤ constant 2 ℓ q k : Lemma 3.1. We have:

D tr (♣ψ A ⟩ , ♣ψ ideal ⟩) ≤ 1 - 2 ℓ q k p 2 t Z ε 2 G .
Lemma 3.2. Assume that C is chosen by uniformly drawing at random a parity-check matrix H for it. We have:

E(Z) ≤ 2 ℓ q k 1 + ⟨π♣1⟩ 2 q n-k . (3.11) Lemma 3.3. Let η > 0.
We have:

P G (Z > 2 ℓ q k (1 + η)) ≤ 1 η ⟨π♣1⟩ 2 q n-k + O q -min(k,n-k)  .
Proposition 3.2 immediately follows by using η = 1 in Lemma 3.3 and plugging this bound on Z in Lemma 3.1. The quantity 2 ℓ q k is the natural value for Z since it is what we can expect when all the c + e terms (taking all c in C and all typical e) are different. The constant Z increases precisely when there are many collisions for the c + e terms. However, in this case, we do not expect to be able to solve the decoding problem anymore.

Step 2. More precisely, we prove that Lemma 3.4. If the Fourier transform is radially preserving, meaning that it transforms a radial function into a radial function, then after measuring ♣ψ ideal ⟩ we obtain a state

♣0 n ⟩ c ⊥ ♣r⟩ with c ⊥ ∈ C ⊥ of weight u with probability 2 ℓ q 2k Z N ⊥ u f (u) 2 where f (u) def = π e
for an arbitrary e of weight u and

N ⊥ u is the number of codewords of weight u in C ⊥ .
The proof is given in Section 3.2.

Step 3. This step consists in quantifying how close to 1 the probability of observing a dual codeword of weight in the set W after measuring ♣ψ ideal ⟩ is. More speciĄcally, we have Proposition 3.3. Under the assumptions made in Theorem 3.2, the probability of

obtaining a codeword c ⊥ ∈ C ⊥ of weight u ∈ W when measuring ♣ψ ideal ⟩ is ≥ 1 -α(π)
for a proportion ≥ 1β(π) of matrices G, where:

α(π) def = u∈W q k S u 1/4 + ⟨π♣1⟩ 2 q n-k -2 -Ω(n) , β(π) def = (q -1) u∈W q k S u + ⟨π♣1⟩ 2 q n-k + O q -min(k,n-k)  .
This proposition is proved in Section 3.3.

Step 4. We Ąrst prove the following point Lemma 3.5. Call G the set of "good matrices" G ∈ F k×n q that satisfy at the same time:

(i) ε G ≥ ε/2 (where ε and ε G are defined in Equation 3.3 and Equation 3.10),

(ii) Z ≤ 2 ℓ+1 q k .
The proportion of good matrices is at least ε/2δ(π) where δ(π)

def = ⟨π♣1⟩ 2 q n-k + O q -min(k,n-k)  . Proof. By deĄnition, ε = 1 q kn G∈F k×n q ε G .
Let B be the set of matrices G that are not good, namely for which (a) ε G < ε/2 or (b)

Z > 2 ℓ+1 q k . By Lemma 3.3, the density of matrices verifying (b) is smaller than δ(π). Therefore,

ε ≤ 1 q kn G / ∈B 1 + δ(π) ε 2 ≤ 1 q kn G / ∈B 1 + δ(π) + ε 2
which concludes the proof.

We use this lemma to prove that the statistical distance between the weight distributions obtained by measuring ♣ψ A ⟩ and ♣ψ ideal ⟩ cannot be too far away:

Lemma 3.6. Let P , respectively Q, be the distribution of the weights c ⊥ of the state ♣e⟩ c ⊥ obtained by measuring the state ♣ψ A ⟩, respectively ♣ψ ideal ⟩. We have

D stat (P, Q) ≤ 1 - p 2 t ε 3 16 + O p 4 t ε 5  + δ(π).
Proof. Let, We start the proof by noticing that

P G (u)
D stat (P, Q) = 1 2 u ♣P (u) -Q(u)♣ = 1 2 u G∈F k×n q 1 q kn (P G (u) -Q G (u)) ≤ 1 q kn G∈F k×n q 1 2 u ♣P G (u) -Q G (u)♣ = 1 q kn G∈F k×n q D stat (P G , Q G ) = G∈G D stat (P G , Q G ) q kn + G / ∈G D stat (P G , Q G ) q kn ≤ G∈G D tr (♣ψ A ⟩ , ♣ψ ideal ⟩) q kn + G / ∈G 1 q kn
(by Equation 3.9)

≤ G∈G 1 - p 2 t ε 2 4 q kn + G / ∈G 1 q kn (by Proposition 3.2) ≤ 1 - p 2 t ε 2 4 (ε/2 -δ(π)) + 1 -ε/2 + δ(π) (by Lemma 3.5) ≤ (ε/2 -δ(π)) 1 - p 2 t ε 2 8 + O p 4 t ε 4  + 1 -ε/2 + δ(π) ≤ 1 - p 2 t ε 3 16 + O p 4 t ε 5  + δ(π)
which concludes the proof.

Proof of Theorem 3.2

We are now ready to prove Theorem 3.2. By Proposition 3.3 we know that u∈W

Q(u) ≥ (1 -α(π))(1 -β(π)) ≥ 1 -α(π) -β(π).
But now we have the following computation,

u∈W P (u) ≥ u∈W Q(u) -D stat (P, Q) ≥ 1 -α(π) -β(π) -1 + p 2 t ε 3 16 -O p 4 t ε 5  -δ(π) = p 2 t ε 3 16 -O p 4 t ε 5  -α(π) -β(π) -δ(π)
which concludes the proof by deĄnition of α(π), β(π) and δ(π).

Application to the Hamming metric

The assumptions of Theorem 3.2 will be satisĄed for the Hamming metric for weights u close to τ ⊥ n (where τ ⊥ is given in Equation 3.2) and we will prove that Theorem 3.3. Suppose that there exists an algorithm A solving with success probability ε the decoding problem DP(q, n, k, t) at Hamming distance

1 ≤ t def = τ n ≤ (1 -δ)d GV (n, k)
for any arbitrary δ > 0. Then, there exists a quantum algorithm which takes as input a generator matrix

G ∈ F k×n q of a code C ⊆ F n q and outputs c ⊥ ∈ C ⊥ of weight u ∈ (1 -α)τ ⊥ n, (1 + α)τ ⊥ n (where α is any arbitrary constant > 0) with probability over a uniform choice of G given by a Ω ε 3 n -2 -Ω(n)
 where:

τ ⊥ def = 1 q  (q -1)(1 -τ ) - √ τ  2 . (3.12)
The proof of this theorem relies on Theorem 3.2, for a suitable choice of quantum state ♣π⟩. This is done by choosing ♣π⟩ = π Trunc which represents a truncated q-ary symmetric channel of crossover probability τ . All its weights are in an interval (1η)t, (1 + η)t where η is some positive constant which will be chosen later on. More precisely, let us Ąrst deĄne the (untruncated) quantum state representing the q-ary symmetric channel of crossover probability τ :

π SC def =   √ 1 -τ ♣0⟩ + τ /(q -1) α∈F * q ♣α⟩   ⊗n .
Indeed, since π SC can also be written as

π SC = e∈F n q π e ♣e⟩ with π e def = (1 -τ ) n-♣e♣  τ q -1  ♣e♣
, measuring π SC mimics the error we have in a q-ary symmetric channel of crossover probability τ , i.e.,

P(measurement outputs e) = ♣π e ♣ 2 =  τ q -1  ♣e♣ (1 -τ ) n-♣e♣ .
We will be interested in the truncated version given by

π Trunc def = e∈F n q : ♣e♣∈ (1-η)t,(1+η)t π Trunc e ♣e⟩ with π Trunc e def =    πe √ N if ♣e♣ ∈ (1 -η)t, (1 + η)t 0 otherwise
where N is the normalizing constant given by

N def = e∈F n q ♣e♣∈ (1-η)t,(1+η)t ♣π e ♣ 2 .
(3.13)

It will be helpful to notice that for all η > 0, N is exponentially close to 1:

Lemma 3.7. For all η > 0, we have

N = 1 -2 -Ω(n) .
Proof. Notice that by Equation 3.13,

1 -N = e∈F n q ♣e♣̸ ∈ (1-η)t,(1+η)t ♣π e ♣ 2 = P e (♣e♣ / ∈ (1 -η)t, (1 + η)t ) = P e (♣e♣ < (1 -η)τ n) + P e (♣e♣ > (1 + η)τ n) (3.14)
where ♣e♣ is the sum of n independent (binary) Bernoulli random variables of parameter τ . Therefore, by HoeffdingŠs inequality, we have for all η > 0,

P e (♣e♣ < (1 -η)τ n) ≤ e -2η 2 τ 2 n and P e (♣e♣ > (1 + η)τ n) ≤ e -2η 2 τ 2 n
which concludes the proof by plugging this in Equation 3.14.

Theorem 3.3 is proved by showing that π Trunc satisĄes all the requirements of Theorem 3.2 when η is small enough.

Step 1: Verification of Condition (C1).

This amounts to proving the following lemma Lemma 3.8. For η > 0 small enough, we have,

π Trunc 1 2 q n-k = 2 -Ω(n) .
Before proving this result, it will be helpful to notice that:

Lemma 3.9. If u ≤ (1 -δ)d GV (n, k) for some δ > 0, then S u q n-k = 2 -Ω(n) .
Proof. Recall that the size B u of the Hamming ball of radius u is of the form

B u = q n hq(µ)(1+o(1))
where µ def = u/n. From this we obtain

S u q n-k ≤ B u B d GV (since S u ≤ B u and B d GV ≤ q n-k ) ≤ q n(hq(µ)-hq(δ GV )+o(1)) ≤ q n(hq((1-δ)δ GV )-hq(δ GV )+o(1)) .
We Ąnish the proof by noticing that h q ((1δ)δ GV )h q (δ GV ) < 0.

We are now ready to prove Lemma 3.8.

Proof of Lemma 3.8. We have the following computation,

π Trunc 1 = e∈F n q ♣e♣∈ (1-η)t,(1+η)t π Trunc e = r∈ (1-η)t,(1+η)t e∈F n q ♣e♣=r π e √ N = 1 √ N r∈ (1-η)t,(1+η)t n r (q -1) r n r (q -1) r (1 -τ ) n-r  τ q -1  r ≤ 1 √ N r∈ (1-η)t,(1+η)t n r (q -1) r (3.15)
where in the last line we used that n u (q -1)

u τ q-1  u (1 -τ ) n-u ≤ 1 for any u ∈ 0, n .
Therefore, using Equation 3.15, we have:

π Trunc 1 2 ≤ 1 N   ⌊(1+η)t⌋ r=⌈(1-η)t⌉ n r (q -1) r     ⌊(1+η)t⌋ r ′ =⌈(1-η)t⌉ n r ′ (q -1) r ′   and since ♯ (1 -η)t, (1 + η)t ≤ n + 1, π Trunc 1 2 ≤ (n + 1) 2 N max r,r ′ ∈ (1-η)t,(1+η)t n r n r ′ (q -1) r (q -1) r ′ .
The max is reached for r = r ′ = (1 + η)t, so:

π Trunc 1 2 ≤ (n + 1) 2 N n (1 + η)t (q -1) (1+η)t = (n + 1) 2 N S (1+η)t .
Using this last inequality, Lemma 3.7 and Lemma 3.9, we obtain

π Trunc 1 2 q n-k = O  (n + 1) 2 S (1+η)t q n-k  = 2 -Ω(n)
where we choose η small enough such that (1

+ η)t ≤ (1 -δ ′ )d GV (n, k) for some δ ′ > 0 (recall that by assumption t ≤ (1 -δ)d GV (n, k) for δ > 0).
Remark 3.2. As explained in the introduction and Remark 3.1, Lemma 3.8 is not satisĄed by π SC . Here truncating the error distribution is essential to verify this concentration lemma.

Step 2: Verification of Conditions (C2) and (C3).

We prove here that the Conditions (C2) and (C3) of Theorem 3.2 are met by π Trunc .

This results from a combination of arguments: (i) these two conditions are met for π SC (ii) π SC and π Trunc are very close and so are ♣π SC ⟩ and ♣π Trunc ⟩ (because they are obtained from the Ąrst pair by applying a QFT, which is unitary).

More precisely we are going to prove that Lemma 3.10.

Let t ⊥ def = ( √ (q-1)(n-t)- √ t) 2 q
and α > 0 be some constant small enough.

We let ♣π Trunc ⟩ = e∈F n q π Trunc e ♣e⟩. This state is radial and we let f Trunc (w) = π Trunc e for any element e of F n q of Hamming weight w. We have

p t = Ω  1 √ n  , ∀u ∈ t ⊥ (1 -α), t ⊥ (1 + α) , q k S u = 2 -Ω(n) and ⌊t ⊥ (1+α)⌋ u=⌈t ⊥ (1-α)⌉ S u f Trunc (u) 2 = 1-2 -Ω(n) .
As explained above, to prove this result we will rely on the following lemma Lemma 3.11. For all η > 0, we have

π Trunc -π SC = 2 -Ω(n) and π Trunc -π SC = 2 -Ω(n) (3.16)
Proof. We have the following computation,

π Trunc -π SC 2 = e∈F n q (π e -π Trunc e ) 2 = e∈F n q : ♣e♣̸ ∈ (1-η)t,(1+η)t π 2 e + e∈F n q : ♣e♣∈ (1-η)t,(1+η)t  π e - π e √ N  2 = 1 -N + (1 - √ N ) 2 N e∈F n q ♣e♣∈ (1-η)t,(1+η)t π 2 e (by Equation 3.13) = 1 -N + (1 - √ N ) 2 (by Equation 3.13) ≤ 2 -Ω(n) (by Lemma 3.7).
The second relation follows, since the QFT is an isometry with respect to ∥•∥.

With this lemma at hand, we are ready to prove Lemma 3.10.

Proof of Lemma 3.10. By deĄnition,

p t = 1 N e : ♣e♣=t (1 -τ ) n-t  τ q -1  t = n t (q -1) t q nhq(τ ) N = Ω  1 √ n 
where in the last equality we used Lemma 3.7 and StirlingŠs formula.

The equality q k Su = 2 -Ω(n) is veriĄed when u is sufficiently close to t ⊥ (α small enough), because it is readily veriĄed that there exists some constant β > 0 such that t ⊥ ≥ (1 + β)d GV (n, nk). This together with t ⊥ ≤ (q-1)n q implies that q k Su = 2 -Ω(n) for any

u in t ⊥ (1 -α), t ⊥ (1 + α) .
The untruncated distribution π SC = e π e ♣e⟩ is radial, and so is its Fourier transform ♣π SC ⟩ = e π e ♣e⟩. We let f (u) = π e where e is any e ∈ F n q of Hamming weight u. We notice that

⌊t ⊥ (1+α)⌋ u=⌈t ⊥ (1-α)⌉ S u f (u) 2 = e∈F n q : ♣e♣∈[(1-α)t ⊥ ,(1+α)t ⊥ ] ♣ π e ♣ 2 = P e ♣e♣ ∈ (1 -α)t ⊥ n, (1 + α)t ⊥ n  ,
where τ ⊥ = t ⊥ n and ♣e♣ is the sum of n independent (binary) Bernoulli random variables of parameter τ ⊥ . Therefore, by using HoeffdingŠs bound again we obtain that

u∈[(1-α)t ⊥ ,(1+α)t ⊥ ] S u f (u) 2 = 1 -2 -Ω(n) .
(3.17) meaning that f concentrates around vectors of weight t ⊥ . Consider the projection of ♣π SC ⟩ and ♣π Trunc ⟩ on the space spanned by the states ♣e⟩ for ♣e♣ ∈ (1α)t ⊥ , (1 + α)t ⊥ :

♣π SC ⟩ def = e∈F n q : ♣e♣∈[(1-α)t ⊥ ,(1+α)t ⊥ ] π e ♣e⟩ ♣π Trunc ⟩ def = e∈F n q : ♣e♣∈[(1-α)t ⊥ ,(1+α)t ⊥ ] π Trunc e ♣e⟩
Since a projection can only reduce the norm, we have

♣π SC ⟩ -♣π Trunc ⟩ ≤ ♣π SC ⟩ -♣π Trunc ⟩ = 2 -Ω(n) . (3.18)
We deduce from the triangle inequality that

♣π Trunc ⟩ ≥ ♣π SC ⟩ -♣π SC ⟩ -♣π Trunc ⟩ , (3.19)
and then from Equation 3.18 and Equation 3.17 which says

♣π SC ⟩ 2 = 1 -2 -Ω(n)  that ♣π Trunc ⟩ ≥ 1 -2 -Ω(n) . Since ♣π Trunc ⟩ ≤ ♣π Trunc ⟩ = 1 we Ąnally obtain ♣π Trunc ⟩ = 1 -2 -Ω(n) .
This directly implies u∈ (1-α)t ⊥ ,(1+α

)t ⊥ S u f Trunc (u) 2 = ♣π Trunc ⟩ 2 = 1 -2 -Ω(n) .
Proof of Theorem 3.3.

This immediately follows from Lemma 3.8 and Lemma 3.10 which show that the relevant assumptions of Theorem 3.2 are veriĄed for the choice ♣π⟩ = π Trunc for η small enough.

Application to the rank metric

The assumptions of Theorem 3.2 will also be satisĄed in the context of codes C ⊆ F m×n q embedded with the rank metric (given some matrix in F m×n q , its weight is deĄned as its rank). The Gilbert-Varshamov distance d GV (m, n, k) is deĄned in a similar way, but it depends on three parameters here and corresponds to the largest radius t of a ball in the rank metric for which

q k B t ≤ q m×n .
We will be able to prove that Theorem 3.4. Suppose that there exists an algorithm A solving with success probability ε the decoding problem at rank distance 1 ≤ t < d GV (m, n, k) where m ≥ n. Then, there exists a quantum algorithm which takes as input a generator matrix of C ⊆ F m×n q and outputs c ⊥ ∈ C ⊥ of weight u ∈ (t ⊥ηn, t ⊥ ] where t ⊥ def = nt (for any arbitrary constant η > 0) with probability over a uniform choice of the generator matrix given by a Ω ε 3 -2 -Ω(n)

 .

Remark 3.3. Our assumption that m ≥ n can be done without loss of generality. In the case where n > m we can just consider the transposed code C

⊺ def = M ⊺ : M ∈ C : taking the transpose is a linear automorphism and can be used to transform any algorithm decoding C into an algorithm decoding C

⊺ with the same complexity.

As in the Hamming case, Theorem 3.4 will be a consequence of Theorem 3.2. Therefore we Ąrst have to choose appropriately a quantum state ♣π⟩ that will model the noise distribution.

Step 1 : Choosing ♣π⟩.

Let,

♣π⟩ def = 1 √ N V ≤F n q dim V =t ♣π V ⟩ where (3.20) ♣π U ⟩ def = 1 q dim U u∈U ♣u⟩ ⊗m (3.21)
and N is a normalizing constant. ♣π U ⟩ can be viewed as a uniform superposition of matrices whose rows belong to U . These matrices have rank at most dim U and ♣π⟩ is close to a uniform distribution of all matrices of rank t. We also have the following alternative description for ♣π⟩.

Lemma 3.12. ♣π⟩ is radial, i.e., we may write ♣π⟩ as

♣π⟩ = E∈F m×n q : ♣E♣≤t π E ♣E⟩ with ♣E⟩ def = ♣E 1 ⟩ ⊗ • • • ⊗ ♣E m ⟩
where the E i 's denote the rows of E and π E = f (♣E♣) where

f (u) =      [ n-u t-u ] q √ q mt N if u ≤ t, 0 otherwise.
This lemma is proved in Section 4.1, as well as the following one, which gives estimations for N and p t in order to apply Theorem 3.2.

Lemma 3.13. We have:

N = Θ   n t q  
and p t = Θ (1) .

Step 2: Verification that ♣π⟩ is radial.

The following proposition states that ♣π⟩ has actually the same form as ♣π⟩ where t is replaced by nt:

Proposition 3.4. We have,

♣π⟩ = 1 √ N W ≤F n q dim W =n-t ♣π W ⟩ .
Proof. We apply the QFT on ♣π⟩, deĄned in Equation 3.20. It gives,

♣π⟩ = 1 √ N V ≤F n q dim V =t   1 q n+t y∈F n q v∈V χ y (v) ♣y⟩   ⊗m
By distinguishing the cases where y ∈ V ⊥ (the dual of V with the standard inner product) or not:

♣π⟩ = 1 √ N V ≤F n q dim V =t   1 q n+t y∈V ⊥ q t ♣y⟩   ⊗m = 1 √ N W ≤F n q dim W =n-t   1 q n-t y∈W ♣y⟩   ⊗m
which concludes the proof.

We can now straightforwardly apply Lemma 3.12 on ♣π⟩ and obtain Lemma 3.14. The state ♣π⟩ is radial and can be written as E∈F m×n q

: ♣E♣≤n-t π E ♣E⟩. If we let f (u) def = π E for any E ∈ F m×n q of rank u, we have f (u) =      [ n-u n-t-u ] q √ q m(n-t) N if u ≤ n -t, 0 otherwise.
Step 3: Verification of Conditions (C1), (C2) and (C3).

This is achieved in the following lemmas that are proved in Section 4.2.

Lemma 3.15. We have, S t q mn-k = q -Ω(n) and ⟨π♣1⟩ 2 q mn-k = q -Ω(n) .

Lemma 3.16. For any η > 0, we have,

∀u ∈ (1 -η)n -t, n -t , q k S u = q -Ω(n) and u∈ (1-η)n-t,n-t S u f (u) 2 = 1 -q -Ω(n) .
Proof of Theorem 3.4.

This follows from Lemma 3.12, Lemma 3.14, Lemma 3.15 and Lemma 3.16 that allow to apply Theorem 3.2, completing the proof.

2 About the usefulness of our reduction.

It is now interesting to look at the parameters for which our reduction is useful for both the Hamming and rank metrics.

Hamming case

A lower-bound on τ is obtained with the following arguments. First, if one wants to compute dual codewords (via the quantum measure) for which no poly-time algorithm is known, one has to ensure that τ ⊥ < ω easy (n, nk) = q-1 q k n . But notice that τ → τ ⊥ is a decreasing involution on 0, 1 2 . Therefore, for the reduction to be meaningful, it is necessary that

τ > ω easy (n, n -k) ⊥ = 1 q (q -1)  1 - q -1 q k n  - q -1 q k n 2 = q -1 q 2   q -(q -1) k n - k n   2 (3.22)
Furthermore, according to Theorem 3.3, the relative decoding distance τ has to verify

τ < d GV (n, k) n = h -1 q  1 - k n  + O  1 n  = δ GV (n, k) + O  1 n  .
where t ⊥ belongs to a range of values for which it is always easy to Ąnd codewords of this weight as we now show.

To verify this point, consider a linear code C ⊆ F m×n q of dimension K (with m ≥ n). It is easy to Ąnd short codewords if they are above a certain range. To produce codewords of small weight, we use the fact that the dual code is a vector space of dimension nm -K. Thus, we can just produce codewords with nm -K -1 entries equal to 0 that will be good candidates for having a small weight by solving a linear system. The entries are chosen so as to Ąll columns with zeroes. It is straightforward that this strategy produces in polynomial time codewords of weight ≈ Rn (since in our case n ≤ m) where R is the rate of C deĄned by R def = K mn . Notice now that t ⊥ is a decreasing function of the decoding distance t. The largest value for which we can hope to decode is the Gilbert-Varshamov distance d GV (m, n, K). The relative Gilbert-Varshamov distance δ GV (m, n, K)

def = d GV (m,n,K) n satisĄes the relation R = 1 -δ GV (1 + ν -δ GV )
where ν def = m n ≥ 1. However, we have (where

δ ⊥ GV is deĄned as t ⊥ /n when t/n = δ GV (m, n, K)) t ⊥ n ≥ δ ⊥ GV = 1 -δ GV = R + δ GV (ν -δ GV ) ≥ R.
In other words, we are always in a regime where Ąnding codewords of relative weight t ⊥ /n is easy.

3 Proof of Theorem 3.2

Step 1: Proof of Lemma and Lemma 3.3

Let us recall Lemma 3.1 Ąrst: Lemma 3.1. We have:

D tr (♣ψ A ⟩ , ♣ψ ideal ⟩) ≤ 1 - 2 ℓ q k p 2 t Z ε 2 G .
Proof. Let G be the set of (c, e)Šs that correspond to inputs of weight t to A that are correctly decoded:

G def = (c, e, r) ∈ C × S t × F ℓ 2 : A (G, c + e, r) = e .
Let us recall that

♣ψ A ⟩ = 1 2 ℓ q k e∈F n q c∈C r∈F ℓ 2 π e ♣e -A (G, c + e)⟩ ♣c + e⟩ ♣r⟩ and ♣ψ ideal ⟩ = 1 √ Z e∈F n q c∈C r∈F ℓ 2 π e ♣0 n ⟩ ♣c + e⟩ ♣r⟩
From this we deduce by using the non-negativity of π e that

⟨ψ A ♣ψ ideal ⟩ ≥ 1 2 ℓ q k Z (c,e,r)∈G π 2 e = 2 ℓ q k Z S t f (t) 2 ♯G 2 ℓ q k S t = 2 ℓ q k Z p t ε G .
Remark 3.4. Here we do not have as in the lattice case [START_REF] Stehlé | ŞEfficient Public Key Encryption Based on Ideal LatticesŤ[END_REF] to make the assumption that the decoder is Şstrongly solution independentŤ. In our case we can indeed have a uniform superposition over all the codewords and we can just use the way our error probability is deĄned, namely as the ratio ♯G 2 ℓ q k St . All the probabilistic results of this section are easier to prove if, instead of choosing a code C by picking uniformly at random a generator matrix G for it, we slightly change the probabilistic model by picking uniformly at random a parity-check matrix H ∈ F (n-k)×n q for it, i.e., C = x ∈ F n q : Hx ⊺ = 0 .

We



. This relationship is expressed by the following lemma.

Lemma 3.17. Let E be an ensemble of linear codes of length n in F q . We have

P G (E ) ≤ P H (E ) + O q -min(k,n-k)  .
With this new probabilistic model, the expected value of Z is given by: Lemma 3.2. Assume that C is chosen by uniformly drawing at random a parity-check matrix H for it. We have:

E(Z) ≤ 2 ℓ q k 1 + ⟨π♣1⟩ 2 q n-k . (3.11)
Proof. Computing E H (Z) with this alternate probabilistic model is straightforward. We have

Z = c∈C,e∈F n q ,r∈F ℓ 2 π e ♣0 n ⟩ ♣c + e⟩ ♣r⟩ 2 = 2 ℓ q k e∈F n q ♣π e ♣ 2 + 2 ℓ (c,e)̸ =(c ′ ,e ′ ) : c+e=c ′ +e ′ π e π e ′ = 2 ℓ q k   1 + e̸ =e ′ : H(e-e ′ ) ⊺ =0 π e π e ′  
where H is an arbitrary-parity check matrix for C. Let

X def = e̸ =e ′ : H(e-e ′ ) ⊺ =0 π e π e ′ .
The point of the probabilistic model where the parity-check matrix H is uniformly drawn at random is that for non-zero element x ∈ F n q we have

P H (x ∈ C) = P H (Hx ⊺ = 0) = 1 q n-k .
From this we deduce

E H (X) = e̸ =e ′ π e π e ′ P H ((e -e ′ ) ∈ C) = e̸ =e ′ π e π e ′ q n-k ≤ e,e ′ π e π e ′ q n-k = ⟨π♣1⟩ 2 q n-k .
From this inequality we conclude the proof.

With the help of these two lemmas, we can upper-bound the probability for Z to be bigger than 2 ℓ q k (1 + η) for any η > 0 and prove Lemma 3.3, that we recall:

Lemma 3.3. Let η > 0. We have:

P G (Z > 2 ℓ q k (1 + η)) ≤ 1 η ⟨π♣1⟩ 2 q n-k + O q -min(k,n-k)  .
Proof. We take back the notation from the proof of Lemma 3.2. We have

P G (Z > 2 ℓ q k (1 + η)) = P G (X > η) ≤ P H (X > η) + O q -min(k,n-k)



(by Lemma 3.17)

≤ 1 η E H (X) + O q -min(k,n-k)  (Markov inequality) ≤ 1 η ⟨π♣1⟩ 2 q n-k + O q -min(k,n-k)
 which concludes the proof.

3.2

Step 2: Proof of Lemma 3.4

If we apply a QFT on the second register of ♣ψ ideal ⟩ (given in Equation 3.7), we obtain:

♣ψ ideal ⟩ def = (I ⊗ QFT ⊗ I) ♣ψ ideal ⟩ = q k √ Z c ⊥ ∈C ⊥ r∈F ℓ 2 π c ⊥ ♣0 n ⟩ c ⊥ ♣r⟩ ,
where ♣π⟩ = e∈F n q π e ♣e⟩ is the QFT of ♣π⟩. We use this remark to prove Lemma 3.4, that we recall: Lemma 3.4. If the Fourier transform is radially preserving, meaning that it transforms a radial function into a radial function, then after measuring ♣ψ ideal ⟩ we obtain a state

♣0 n ⟩ c ⊥ ♣r⟩ with c ⊥ ∈ C ⊥ of weight u with probability 2 ℓ q 2k Z N ⊥ u f (u) 2 where f (u) def = π e
for an arbitrary e of weight u and N ⊥ u is the number of codewords of weight u in C ⊥ .

Proof. For e ∈ F n q , let

♣1 C+e ⟩ def = c∈C ♣c + e⟩ .
We have

♣1 C+e ⟩ = c∈C 1 √ q n y∈F n q χ y (c + e) ♣y⟩ = 1 √ q n y∈F n q χ y (e) c∈C χ y (c) ♣y⟩ = q k √ q n c ⊥ ∈C ⊥ χ c ⊥ (e) c ⊥ (since c∈C χ y (c) = 0 if y / ∈ C ⊥ and q k otherwise) Therefore e∈F n q ,c∈C π e ♣c + e⟩ = e∈F n q π e ♣1 C+e ⟩ = q k √ q n e∈F n q π e c ⊥ ∈C ⊥ χ c ⊥ (e) c ⊥ = q k c ⊥ ∈C ⊥ 1 √ q n e∈F n q π e χ c ⊥ (e) c ⊥ = q k c ⊥ ∈C ⊥ π c ⊥ c ⊥ .
It follows that

♣ψ ideal ⟩ = q k √ Z c ⊥ ∈C ⊥ r∈F ℓ 2 π c ⊥ ♣0 n ⟩ c ⊥ ♣r⟩ .
After measurement we get a state ♣0 n ⟩ c ⊥ ♣r⟩ with probability

q 2k Z f ( c ⊥ ) 2 . By
summing over all r ∈ F ℓ 2 and c ⊥ ∈ C ⊥ of weight u, we conclude the proof.

Step 3 : Proof of Proposition 3.3

We Ąrst need for this a good estimation of ♣ψ ideal ⟩Šs amplitudes. This will be a consequence of the following lemma.

Lemma 3.18. If the generator matrix G of a code C is chosen uniformly at random in F k×n q then the number N ⊥ u of codewords of weight u in C ⊥ satisfies

P G N ⊥ u - S u q k ≥  S u q k  3/4 ≤ (q -1) q k S u .
Proof. Let 1 x be the indicator function of the event Şx ∈ C ⊥ Ť. By deĄnition,

N ⊥ u = x∈Su 1 x . (3.23)
We have

E(1 x ) = P G (x ∈ C ⊥ ) = 1 q k , implying that E(N ⊥ u ) = Su q k . By using Bienaymé-
TchebychevŠs inequality, we obtain:

P  N ⊥ u - S u q k ≥ a  ≤ Var(N ⊥ u ) a 2 = 1 a 2     x∈Su Var(1 x ) + x,y∈Su x̸ =y E(1 x 1 y ) -E(1 x )E(1 y )     ≤ 1 a 2     x∈Su E(1 x ) +
x,y∈Su x̸ =y

E(1 x 1 y ) -E(1 x )E(1 y )     = 1 a 2     S u q k + x,y∈Su x̸ =y E(1 x 1 y ) -E(1 x )E(1 y )     (3.24)
where we used that Var(1

x ) ≤ E(1 2 x ) = E(1 x ).
Let us now upper-bound the second term of the inequality. It is readily veriĄed that:

E(1 x 1 y ) =    1 /q k
if x and y are colinear,

1 /q 2k otherwise.

Therefore, we deduce that:

x,y∈Su x̸ =y

E(1 x 1 y ) -E(1 x )E(1 y ) = x∈Su y∈Su\x : colinear to x 1 q k - 1 q 2k ≤ x∈Su y∈Su\x : colinear to x 1 q k ≤ (q -2)S u q k (3.25)
It gives by plugging Equation 3.25 in Equation 3.24:

P G  N ⊥ u - S u q k ≥ a  ≤ 1 a 2  S u q k + (q -2)S u q k  = (q -1)S u a 2 q k
which concludes the proof by choosing a = Su

q k  3/4 .
We are ready to prove Proposition 3.3 which we now recall:

Proposition 3.3. Under the assumptions made in Theorem 3.2, the probability of

obtaining a codeword c ⊥ ∈ C ⊥ of weight u ∈ W when measuring ♣ψ ideal ⟩ is ≥ 1 -α(π)
for a proportion ≥ 1β(π) of matrices G, where:

α(π) def = u∈W q k S u 1/4 + ⟨π♣1⟩ 2 q n-k -2 -Ω(n) , β(π) def = (q -1) u∈W q k S u + ⟨π♣1⟩ 2 q n-k + O q -min(k,n-k)  .
Proof. Let Q be the quantum algorithm starting from ♣ψ⟩ which computes (I ⊗ QFT ⊗ I) ♣ψ⟩. This algorithm succeeds when measuring a dual codeword c ⊥ ∈ C ⊥ of weight u ∈ W . When starting with ♣ψ ideal ⟩, the probability of success of Q is equal to

u∈W 2 ℓ q 2k N ⊥ u Z f (u) 2 by Lemma 3.4. Let B def =    G ∈ F k×n q : Z > 2 ℓ q k   1 + ⟨π♣1⟩ 2 q n-k      and E u def = G ∈ F k×n q : N ⊥ u - S u q k ≥  S u q k  3/4
. By Lemma 3.3 and Lemma 3.18 we have that

P   G ∈ B ∪ u∈W E u   ≤ β(π) = (q -1) u∈W q k S u + ⟨π♣1⟩ 2 q n-k + O q -min(k,n-k)  .
Therefore, for a proportion ≥ 1β(π) of codes (over matrices G):

(i) Z ≤ 2 ℓ q k 1 + ⟨π♣1⟩ 2 q n-k
and Z ≥ 2 ℓ q k (this is true for any G as π e ≥ 0 for any e),

(ii) for all u in W ,

q k N ⊥ u Su -1 ≤ q k Su  1/4 .
We deduce that for a proportion ≥ 1β(π) of codes and for all u in W :

1 -q k Su  1/4 1 + ⟨π♣1⟩ 2 q n-k ≤ q k N ⊥ u S u 2 ℓ q k Z ≤ 1 + q k S u 1/4
. This implies that for a proportion ≥ 1β(π) of codes and for all u in W we have that

1 -u∈W q k Su  1/4 1 + ⟨π♣1⟩ 2 q n-k ≤ 2 ℓ q 2k N ⊥ u S u Z ≤ 1 + u∈W q k S u 1/4
, from which we deduce that under the same conditions we also have

S u f (u) 2     1 -u∈W q k Su  1/4 1 + ⟨π♣1⟩ 2 q n-k     ≤ u∈W 2 ℓ q 2k N ⊥ u Z f (u) 2 ≤ S u f (u) 2   1 + u∈W q k S u 1/4   . (3.26) Now, 1 -u∈W q k Su  1/4 1 + ⟨π♣1⟩ 2 q n-k ≥ 1 - u∈W q k S u 1/4 - ⟨π♣1⟩ 2 q n-k
Therefore, by plugging this in Equation 3.26 we have for a proportion ≥ 1β(π) of codes:

(

1 -δ) u∈W S u f (u) 2 ≤ u∈W 2 ℓ q 2k N ⊥ u Z f (u) 2 ≤ (1 + δ) u∈W S u f (u) 2 (3.27)
where

δ def = u∈W q k Su  1/4 + ⟨π♣1⟩ 2
q n-k . We Ąnish the proof by applying Lemma 3.4: we namely know that after measuring the state obtained by Q, we obtain a dual codeword of weight u in W with probability u∈W

2 ℓ q 2k N ⊥ u Z f (u) 2 .
4 Proof of Theorem 3.4

4.1 Proofs of Lemma 3.12 and Lemma 3.13

The following lemma will be very helpful in what follows.

Lemma 3.19. [BCN89, §9.3, Lem. 9.3.2] Let V be a subspace of dimension s, then there are exactly q (t-ℓ)(s-ℓ) n-s t-ℓ q s ℓ q subspaces W of dimension t such that dim(V ∩ W ) = ℓ.

Let us now recall Lemma 3.12:

Lemma 3.12. ♣π⟩ is radial, i.e., we may write ♣π⟩ as

♣π⟩ = E∈F m×n q : ♣E♣≤t π E ♣E⟩ with ♣E⟩ def = ♣E 1 ⟩ ⊗ • • • ⊗ ♣E m ⟩
where the E i 's denote the rows of E and π E = f (♣E♣) where

f (u) =      [ n-u t-u ] q √ q mt N if u ≤ t, 0 otherwise.
Proof. Let U be the F q -space generated by the E i Šs. We denote by u the dimension of U . We have

π E = 1 q mt N ♯ V ≤ F n q : dim V = t and U ⊆ V = n-u t-u q q mt N ,
where we used Lemma 3.19 for the last equality. It concludes the proof.

Another asymptotic expression for N and an estimate for p t are given by: Lemma 3.13. We have:

N = Θ   n t q   and p t = Θ (1) .
This lemma will be a consequence of the following lemmas.

Lemma 3.20. For any V, W ≤ F n q such that V ̸ = W and dim V = dim W = t we have,

⟨π V ♣π W ⟩ = q m(dim(V ∩W )-t) .
Proof. Recall that,

♣π U ⟩ = 1 q dim U u∈U ♣u⟩ ⊗m Therefore we have, ⟨π V ♣π W ⟩ = 1 q t v∈V w∈W ⟨v♣w⟩ m =  1 q t ♯(V ∩ W )  m
which concludes the proof.

Lemma 3.21. We have,

V ≤F n q dim V =t W ≤F n q dim W =t W ̸ =V ⟨π V ♣π W ⟩ = O   n t q   .
Proof. We have

V ≤F n q dim V =t W ≤F n q dim W =t W ̸ =V ⟨π V ♣π W ⟩ = V ≤F n q dim V =t W ≤F n q dim W =t W ̸ =V q m(dim(V ∩W )-t) = V ≤F n q dim V =t t-1 ℓ=0 W ≤F n q dim W =t dim(W ∩V )=ℓ 1 q m(t-ℓ) = V ≤F n q dim V =t t-1 ℓ=0 1 q m(t-ℓ) q (t-ℓ) 2 t ℓ q n -t t -ℓ q (3.28) = n t q t-1 ℓ=0 q (t-ℓ-m)(t-ℓ) t ℓ q n -t t -ℓ q
where in Equation 3.28 we used Lemma 3.19. Now, there exists some constant c > 0 such that:

n ℓ q ≤ cq ℓ(n-ℓ) .
Then, for some constant C > 0,

V ≤F n q dim V =t W ≤F n q dim W =t W ̸ =V ⟨π V ♣π W ⟩ ≤ C n t q t-1 ℓ=0 q (t-ℓ-m)(t-ℓ)+ℓ(t-ℓ)+(t-ℓ)(n-2t+ℓ) = C n t q t-1 ℓ=0 q (t-ℓ)(t-ℓ-m+ℓ+n-2t+ℓ) = C n t q t-1 ℓ=0 q (t-ℓ)(-t+ℓ-m+n) ≤ C n t q t-1 ℓ=0 q -(t-ℓ) 2 (since n ≤ m)
which concludes the proof.

We are now ready to prove Lemma 3.13.

Proof of Lemma 3.13. By deĄnition of N we have:

N = V ≤F n q dim V =t π V 2 = V ≤F n q dim V =t ∥π V ∥ 2 + V ≤F n q dim V =t W ≤F n q dim W =t W ̸ =V ⟨π V , π W ⟩
and by deĄnition of π V :

V ≤F n q dim V =t ∥π V ∥ 2 = n t q 1 q t v∈V 1 m = n t q
This concludes the proof that N = n t q by using Lemma 3.21. Now, by deĄnition of p t , we have:

p t = S t f (t) 2 = S t n-t 0 2 q q mt N (by Lemma 3.12) = S t Θ (S t )
(by using the estimate for N and Equation 2.8) allowing us to conclude that p t = Θ (1).

Proofs of Lemma 3.15 and Lemma 3.16

Recall Lemma 3.15 Ąrst: Lemma 3.15. We have, S t q mn-k = q -Ω(n) and ⟨π♣1⟩ 2 q mn-k = q -Ω(n) .

Proof. In order to prove the Ąrst equation, note that d GV (m, n, k) is deĄned such that S d GV q mn-k ≤ 1. From this and Equation 2.9 we deduce

S d GV -1 q mn-k = S d GV -1 S d GV S d GV q mn-k ≤ Θ q -(m+n-2d GV -1)  = Θ q -Ω(n) 
where the last equality follows from the fact that (see for instance [START_REF] Loidreau | Properties of codes in rank metric[END_REF])

d GV (n, m, k) = m + n -(m -n) 2 + 4k 2 (1 + o(1)). (3.29)
Now, for the second equation, we have

⟨π♣1⟩ 2 q mn = f (0) 2 = n n-t 2 q
q m(n-t) N (by Lemma 3.14) = Θ q mt n t q q mn (By Lemma 3.13) = Θ  S t q mn  (By Equation 2.7 and Equation 2.8)

Thanks to the Ąrst equation, we complete the proof.

The second lemma we need is recalled here: Lemma 3.16. For any η > 0, we have,

∀u ∈ (1 -η)n -t, n -t , q k S u = q -Ω(n) and u∈ (1-η)n-t,n-t S u f (u) 2 = 1 -q -Ω(n) .
Proof. The Ąrst equation can be proved in the same way as Lemma 3.15. For the second identity, Ąrst notice (by Lemma 3.14) that

u∈ n-t-ηn,n-t S u f (u) 2 = 1 - u<n-t-ηn S u f (u) 2 .
Now, we have the following computation:

u<n-t-ηn S u f (u) 2 = u<n-t-ηn S u n-u n-u-t 2 q N q m(n-t) (by Lemma 3.15) = Θ   u<n-t-ηn S u n-u n-u-t 2 q n t q q m(n-t)   (by Lemma 3.13) = Θ   u<n-t-ηn
q u(m+n-u) q 2(n-t-u)t q t(n-t) q m(n-t)   (By Equation 2.7 and 2.8) = Θ q max u<n-t-ηn u(m+n-u-2t) q (t-m)(n-t)



Let g(u)

def = u(m + n -u -2t). Then, g ′ (u) = m + n -2(t + u) ≥ 0 as t + u ≤ n ≤ m.
Therefore, g is an increasing function and by setting u = ntηn, we obtain

u<n-t-ηn S u f (u) 2 ≤ n Θ q (n-t-ηn)(m-t+ηn) q (t-m)(n-t)  = n Θ q (n-t)(t-m+m-t+ηn) q -ηn(m-t+ηn)  = n Θ q -ηn(m-t+ηn-n+t)  = n Θ q -ηn(m-n+ηn)  = q -Ω(n)
as n ≤ m by assumption. It concludes the proof.

Chapter 4 Introduction to the Dihedral Hidden Subgroup Problem

The dihedral group of order 2N , which will be denoted D N , is simply deĄned as the group of symmetries (rotations and reĆections) of a regular N -gon. Formally:

D N def = u, v : u N = v 2 = (uv) 2 = 1
Here u can be thought as a rotation of the N -gon by an angle 2π/N and v as a reĆection about some Ąxed axis. A simple example is given in Figure 4.1 of the action of the dihedral group on a regular pentagon. It results from the deĄnition we gave that any group element can be written in the form u x v b where x ∈ Z N and b ∈ Z 2 . Thus we can equivalently think of the group as consisting of elements (x, b) ∈ Z N × Z 2 , where x deĄnes the angle of the rotation applied and b if we apply a reĆection or not. For more information about dihedral groups, we refer to [START_REF] Childs | Lecture notes on quantum algorithms -Kuperberg's algorithm for the dihedral HSP[END_REF][START_REF] Conrad | Expository papers, Dihedral Groups I and II[END_REF].

61

In this chapter, we look at the HSP in a dihedral group (DHSP). While the HSP in an abelian group is quantumly easy to solve, as we saw in Chapter 1, many post-quantum primitives are related to the DHSP. This is the case of cryptosystems based on the Unique Shortest Vector Problem (uSVP) in lattice-based cryptography (such as [AD97; Reg04b]) or on any problem that can be reduced to the uSVP (because of a chain of reductions between several problems [Reg02; LM09; Ste+09]). More concretely, the security of several primitives reduces to the DHSP. The most prominent example is the isogeny-based post-quantum key-exchange CSIDH [START_REF] Castryck | ŞCSIDH: An Efficient Post-Quantum Commutative Group ActionŤ[END_REF], which is similar to the Diffie-Hellman protocol [START_REF] Diffie | ŞNew directions in cryptographyŤ[END_REF] except that it does not rely on the period-Ąnding problem in an abelian group (which is solvable in quantum polynomial time), but on the difficulty to invert the group action. As it has been shown in [BS20; Pei20; Chá+22], a better understanding of the security of CSIDH comes from a careful analysis of quantum algorithms solving the DHSP. Several related constructions [START_REF] Alamati | ŞCryptographic Group Actions and ApplicationsŤ[END_REF] such as the signature schemes SeaSign [DG19; DPV19] and CSI-FiSh [BKV19] also rely on this problem. It should be noted that these isogeny-based cryptosystems are the only major contenders for which the quantum attacker enjoys more than a quadratic speedup, as opposed to the lattice-and hash-based Ąnalists of the NIST post-quantum standardization process [NIS16; Ala+22].

In Section 1, we will see how to reduce the DHSP, which is a purely classical problem, to a quantum problem, known as the Dihedral Coset Problem (DCP). The following sections will then introduce the milestone algorithms, from the Ąrst algorithm to solve the DCP in sub-exponential time to KuperbergŠs second algorithm, which is the state of the art, via RegevŠs algorithm, which was the Ąrst algorithm to solve the DCP with a polynomial number of qubits.

Contents

From Finding a Hidden Subgroup to Solving a Quantum Problem

We properly deĄne here the Dihedral Hidden Subgroup Problem and the Dihedral Coset Problem. We show how to reduce the former to the latter, by the intermediate of another problem which is the hidden subgroup problem in a dihedral group with a promise on the structure of this subgroup.

Dihedral Hidden Subgroup Problem

The Dihedral Hidden Subgroup Problem, DHSP for short, is simply the Hidden Subgroup Problem in a dihedral group D N for some integer N . We take it to be greater than 2 in what follows, since D N is non-abelian in this case. We then have here an example of a group with a relatively simple structure for which the standard algorithm solving the abelian HSP cannot be applied.

We will therefore be interested in the structure that the hidden subgroup in a dihedral group can take, i.e., the possible subgroups of a dihedral group. But Ąrst we start by proving that an exhaustive search of the hidden subgroup in D N is not possible when N is too big. The following lemma states the number of subgroups S N of the dihedral group D N : From this lemma, we can then deduce a lower bound on S N , which we Ąnd by considering that N is a prime number since it is trivially the case where S N will be the smallest. In this case, σ(N ) = N + 1 and τ (N ) = 2, since the only divisors of N are 1 and N itself. It follows that when N is exponential, so is an exhaustive search to Ąnd a hidden subgroup in D N .

We will now look at the structure of the subgroups of a dihedral group. In fact, it can be shown that its subgroups are either dihedral themselves or cyclic, as stated in the following lemma: • ⟨(x, 0), (y, 1)⟩ where x ∈ Z N is some divisor of N and 0 ≤ y < x (dihedral subgroups).

Remark 4.1. More precisely, Miller actually proved in [START_REF] Miller | The Number of Subgroups of the Dihedral Group D(n)[END_REF] that τ (N ) is the number of cyclic subgroups and σ(N ) is the number of dihedral subgroups.

It was proved by Ettinger and Høyer that it is possible to reduce the general DHSP (in which the hidden subgroup could be any of the possible ones) to a DHSP with the promise that the hidden subgroup is of a certain form.

Lemma 4.3 (Proof of Theorem 2 [EH99]

). The DHSP in D N reduces to a DHSP where the hidden subgroup is either the trivial subgroup or ⟨(y, 1)⟩ = ¶(0, 0), (y, 1)♢ for some y ∈ Z N .

Proof. Let H be a subgroup of D N . We have from Lemma 4.2 that H can be either cyclic or dihedral:

   ⟨u x ⟩ with x♣N ⟨u x , u y v⟩ with x♣N and y ∈ 0, x -1
Let us show that any of these cases reduce to the particular case where the subgroup is of the form ⟨u y v⟩, or trivial. We distinguish the case where x = N (i.e. x = 0) from the others.

• When x ̸ = N , the hidden subgroup H necessarily has a cyclic part and therefore a cyclic subgroup, namely ⟨u x ⟩. This subgroup being normal in D N , we can compute the quotient group D N /Z x ≃ D N/x . The hidden subgroup in this quotient group is then H/Z x , which does not have any cyclic subgroup, meaning that it is either the trivial subgroup or a subgroup of the form ⟨u y v⟩.

• When x = N , we are in the same case where H can be either trivial or dihedral with no cyclic subgroup.

In conclusion, it does not matter what form the subgroup H takes, it will reduce to Ąnding a subgroup of the form ⟨u y v⟩, i.e. a subgroup of the form ⟨(y, 1)⟩.

Dihedral Coset Problem

We showed in the previous subsection that if we know how to solve the DHSP with the promise that the hidden subgroup is of the form ⟨(s, 1)⟩ = ¶(0, 0), (s, 1)♢ where s ∈ Z N is unknown, then we can in fact solve the general DHSP in which the hidden subgroup could be any of the possible ones. We now have to take a closer look to the DHSP with a promise and how to solve it. We let f : D N → S be a function that fulĄlls the subgroup promise with respect to H, where H is ¶(0, 0), (s, 1)♢ for some unknown s ∈ Z N (H could actually be the trivial subgroup ¶(0, 0)♢ but as it is easy to deal with it, we will leave it on the side). Finding H is equivalent to Ąnding s, so we will in fact focus on Ąnding the unknown value s.

A standard method to solve the DHSP with a promise thanks to a quantum algorithm is by coset sampling. The beginning is the same as the algorithm we described in Chapter 1, for the abelian case: we build a superposition over the elements of G and compute f (G) in an ancillary register thanks to the hiding function f . We then measure the ancillary, which leaves us with a coset state ♣(x, 0)H⟩, a superposition over a coset of the unknown subgroup H which is promised to be ⟨(s, 1)⟩ = ⟨(0, 0), (s, 1)⟩. This method is shown in Algorithm 4.

Algorithm 4 Building coset states

Require: A unitary U f to compute f .

1: Prepare a uniform superposition over Z N × Z 2 and compute f by using

U f 1 √ 2N x∈Z N b∈Z 2 ♣x, b, f (x, b)⟩ 2:
Measure the ancillary register and discard it

1 √ 2 b∈Z 2 ♣x + bs, b⟩ = 1 √ 2 (♣x, 0⟩ + ♣x + s, 1⟩) def = ♣(x, 0)H⟩
It can be veriĄed that the value x is picked at random from Z N during the measurement. This procedure is the crucial argument used in [START_REF] Ettinger | ŞOn Quantum Algorithms for Noncommutative Hidden SubgroupsŤ[END_REF] to conclude that solving the DHSP with a promise reduces to the Dihedral Coset Problem (DCP), which is the quantum problem of Ąnding s from coset states ♣(x, 0)H⟩, deĄned as follows.

Problem 4.1. Dihedral Coset Problem (DCP). Suppose we have a collection of coset

states ♣(x, 0)H⟩ for random unknown x ∈ 0, N . The DCP asks to find s ∈ 0, N .

From coset states, two strategies are available to us. The Ąrst one consists in applying a tensor product of a QFT and a Hadamard gate on Z N × Z 2 (and thus proceed in a way analogous to what is done for abelian groups, as seen in the previous chapter) and the second one consists in applying a QFT on Z N only. LetŠs take a closer look at these two strategies.

Quantum Fourier Transform over Z N × Z 2

In their paper [EH99], Ettinger and Høyer applied F N ⊗ H on ♣(x, 0)H⟩, which gives

1 2 √ N a∈Z N b∈Z 2 ω ax N  1 + ω as+b N 2 N  ♣a⟩ ♣b⟩ . (4.1)
They then measured the two registers to obtain a pair (a, b) ∈ Z N × Z 2 that is measured with probability given in the following lemma:

Lemma 4.4 ([EH99]

). The probability for (a, b) to be the outcome of the measurement

is 1 N cos 2 π as N if b = 0 1 N sin 2 π as N if b = 1 Proof. The probability of measuring (a, b) ∈ Z N × Z 2 is 1 4N 1 + ω as+b N 2 N 2 = 1 N cos 2  π 2 b + π as N  .
Ettinger and Høyer then built an algorithm upon this method to retrieve information about s from a collection of O (log N ) results of this procedure, as stated in Theorem 4.1, but it runs in exponential classical time and it appears to be difficult to design a more efficient algorithm using this strategy.

Theorem 4.1 (Theorem 3 of [EH99]

). There exists a quantum algorithm that outputs either "trivial" or the secret value s using at most O(log N ) evaluations of the hiding function f . The output is always "trivial" if H is trivial and the algorithm outputs s with probability at least 1 -1 2N otherwise.

We will not give the proof of this theorem here. We can simply remark from Lemma 4.4 that the probability distribution we get from measuring states of the form given by Equation 4.1 is non-uniformly distributed on Z N depending on s. From such states measurements, we can thus retrieve information about s using Lemma 4.4. That is roughly speaking what Ettinger-Høyer algorithm does: it produces a linear number (in log N ) of couples (a, b) with the above procedure and then goes through all possible values for s and Ąnds which one best Ąts the measurement results using a statistical argument. The number of queries to the hiding function is thus linear (in log N ) and enough to solve the DCP, however, the algorithm has the major disadvantage of requiring an exponential classical time, since it proceeds to an enumeration on a list of N values.

Quantum Fourier Transform over Z N

We now look at the other strategy, of applying the QFT over Z N only, which yields

1 √ 2N k∈Z N ω kx N ♣k⟩ ♣0⟩ + ω sk N ♣1⟩ 
Measuring the Ąrst register collapses the superposition on

1 √ 2 ♣k⟩ ♣0⟩ + ω sk N ♣1⟩
 for a value k picked at random from Z N . In the second register, we obtain a state which will be denoted by ♣ψ k ⟩ and called a phase vector.

Definition 4.1 (Phase vector). Let k ∈ Z N . We denote by ♣ψ k ⟩ the phase vector deĄned as

♣ψ k ⟩ def = 1 √ 2 (♣0⟩ + ω sk N ♣1⟩) (4.2)
where s ∈ Z N is an unknown integer we are looking for.

These states will turn out to be useful to reveal information about the secret s in a much more efficient way than with the previous strategy. Namely, we will be able to design subexponential time quantum algorithms to solve the DCP. We will consider in what follows that we have access to an oracle outputting phase vectors as deĄned in DeĄnition 4.1, since Ąnding s ∈ 0, N from a collection of states ♣ψ k ⟩ for known and uniformly distributed random k ∈ 0, N solves the DCP and thus the DHSP in turn, as we saw previously.

Kuperberg's first algorithm

With a simple but clever way of assembling two phase vectors to obtain one with better properties, Kuperberg designed in 2003 the Ąrst algorithm to solve the DCP in subexponential time [START_REF] Kuperberg | A subexponential-time quantum algorithm for the dihedral hidden subgroup problem[END_REF]. For the sake of clarity, we will take N to be a power of 2, namely N def = 2 n , but the algorithm described here works for any integer N .

It is indeed possible to combine two phase vectors in order to construct a new one in the following way

♣ψ p , ψ q ⟩ = 1 2 ♣0, 0⟩ + ω sp N ♣1, 0⟩ + ω sq N ♣0, 1⟩ + ω s(p+q) N ♣1, 1⟩  CNOT ----→ 1 2 ♣0, 0⟩ + ω s(p+q) N ♣1, 0⟩ + ω sq N ♣0, 1⟩ + ω sp N ♣1, 1⟩  = 1 √ 2 (♣ψ p+q , 0⟩ + ω sq N ♣ψ p-q , 1⟩)
A measurement of the second qubit will leave the Ąrst one in the state ♣ψ p+q ⟩ if 0 is obtained and in the state ♣ψ p-q ⟩ if 1 is obtained. Both cases happen with probability 1/2. Having this combination method on hand, it is interesting to note that if p and q had a certain number m of least signiĄcant bits in common, then with probability 1/2 we would get ♣ψ p-q ⟩, where pq would have its m least signiĄcant bits equal to 0.

In parallel, we note that the state ψ N/2 , associated to the value N/2 whose binary development is (0, . . . , 0, 1) (i.e., all its bits are zeroes except for the most signiĄcant one), is

ψ N/2 = 1 √ 2  ♣0⟩ + ω s N 2 N ♣1⟩  = 1 √ 2 ♣0⟩ + (-1) lsb(s) ♣1⟩  = H ♣lsb(s)⟩
So we have a method that, if we iterate it, produces phase vectors with more and more least signiĄcant bits equal to zero, and a state with all its bits equal to zero except for the most signiĄcant one, which we would like to obtain because it would give us information about the secret, namely lsb(s).

Kuperberg therefore designed the sieve which is roughly represented in Figure 4.2 and described as follows. We start by generating many phase vectors, which are gathered in a list. Their most signiĄcant bit, which is represented by a darker orange column, will not be affected. The Ąrst step is to classify the states according to their value on their m least signiĄcant bits (there will typically be 2 m lists for the 2 m possible bit strings on m bits). Once this is done, we take the phase vectors in each sublist two by two, combine them by the CNOT trick, and keep the resulting state when the difference is obtained. Finally, all the states are grouped together in the same list and the process is iterated.

Algorithm

The pseudocode for KuperbergŠs algorithm is given by Algorithm 5.

Algorithm 5 KuperbergŠs Algorithm

Require: A parameter m and a list L of 2 ℓ coset states as in Equation 4.2, where each copy has k ∈ Z N chosen independently and uniformly at random. Ensure: The least signiĄcant bit of the secret s.

1: for j from 0 to m -1 do 2:

Collect the coset states into pairs (♣ψ p ⟩ , ♣ψ q ⟩) sharing at least their m lower bits, their jm trailing zeroes being excluded, or n -1jm if j = m -1. Discard the remaining states that cannot be paired.

3:

Use the combination routine to create a state ♣ψ p±q ⟩ from each pair, and discard it if the + sign occurs.

4:

if ♣ψ 2 n-1 ⟩ ∈ L then Measure it in the ♣±⟩ basis and return the result 5: return "The algorithm failed" As previously described, this algorithm solves the DCP by collecting states that share many of their last signiĄcant bits into pairs (♣ψ p ⟩ , ♣ψ q ⟩), such that ♣ψ p-q ⟩ is likely to have many of its least signiĄcant bits equal to zero. It would require an exponential It is inspired by the one for the BKW algorithm which can be found in the slides [START_REF] Theiacr | A Non-heuristic Approach to Time-space Tradeoffs and Optimizations for BKW[END_REF] corresponding to the paper [START_REF] Liu | ŞA Non-heuristic Approach to Time-Space Tradeoffs and Optimizations for BKWŤ[END_REF], the only difference being in the combination step, where instead of using a vector that we XOR to all the others, we take them two by two and combine them with a CNOT and a measure. We start with a list of phase vectors whose labelsŠ most signiĄcant bit is shown in dark orange. The classiĄcation step separates these labels according to their value on their m least signiĄcant bits (each color corresponds to a different string of m bits). The combination step then allows us to construct phase vectors whose labels have their m least signiĄcant bits equal to 0, which is shown in white.

time to zero out all but the most signiĄcant one in one shot so instead, we proceed by zeroing out the m least signiĄcant bits in successive rounds. This parameter m has to be carefully chosen as it can bring the time complexity of the algorithm down to subexponential, as we will see in what follows.

We will also look at the number of initial phase vectors, which should be chosen such as there remains at least one element at the end of the process, i.e., one state with all its n -1 least signiĄcant bits equal to zero. Indeed, when ψ N/2 is obtained, we are left with applying a Hadamard gate on it and measuring it in order to obtain lsb(s). From this point where we know the parity of s, we can determine to which subgroup D N/2 of D N it belongs and then reapply the algorithm to determine the second least signiĄcant bit of s (which is its parity bit in D N/2 ), and so on, until the whole secret is discovered.

Bonnetain and Naya-Plasencia proved in [START_REF] Bonnetain | ŞHidden Shift Quantum Cryptanalysis and ImplicationsŤ[END_REF] that it is actually possible to recover all the bits of s at once rather than working on successive least signiĄcant bits in dihedral groups with smaller and smaller cardinal. It turns out that their procedure allows a polynomial speed-up over KuperbergŠs algorithm.

They Ąrst showed that it is possible to retrieve s from a collection of phase vectors ♣ψ

k i ⟩ with k i such that 2 i ♣k i but 2 i+1 ̸ ♣k i , for each i from 0 to n -1. It is equivalent to say that there exists α i ∈ 0, 2 n-1-i -1 such that ♣ψ k i ⟩ = ψ (2α i +1)2 i .
Indeed, up to a phase correction, we can Ąnd s n-1-i from ♣ψ k i ⟩, as shown in the following computation:

ψ (2α i +1)2 i = 1 √ 2  ♣0⟩ + e iπs 2α i +1 2 n-1-i ♣1⟩  = 1 √ 2  ♣0⟩ + e iπ(s-(s mod 2 n-1-i )) 2α i +1 2 n-1-i e iπ(s mod 2 n-1-i ) 2α i +1 2 n-1-i ♣1⟩  = 1 √ 2  ♣0⟩ + e iπs n-1-i e iπ(s mod 2 n-1-i ) 2α i +1 2 n-1-i ♣1⟩  = 1 √ 2  ♣0⟩ + (-1) s n-1-i e iπ(s mod 2 n-1-i ) 2α i +1 2 n-1-i ♣1⟩ 
Starting from i = n -1, we can directly determine the least signiĄcant bit of s. For i = n -2, we then know (s mod 2 n-1-i ) = s 0 , meaning that we can apply a phase correction of angle

-πs 0 2α i + 1 2 n-1-i on ψ (2α i +1)2 n-1-i , giving the state 1 √ 2 (♣0⟩ + (-1) s n-1-i ♣1⟩
), which will give us s 1 . Iterating this process, we will be able to determine the whole secret, as shown by Algorithm 6.

Algorithm 6 Algorithm to retrieve s from n coset states

Require: ∀i ∈ 0, n -1 a phase vector ψ (2α i +1)2 i , where α i ∈ 0, 2 i -1 . Ensure: The secret s.

1: From ♣ψ 2 n-1 ⟩, retrieve s 0 by measuring the state in the ♣±⟩ basis 2: for i from n -2 to 0 do 3: Use the bits s 0 , . . . , s i-1 to apply a phase correction of angle

-π(s mod 2 n-1-i ) 2α + 1 2 n-1-i on ψ (2α i +1)2 i 4:
Measure the corrected state in the ♣±⟩ basis to retrieve s n-1-i 5: return s Tweaking a bit KuperbergŠs algorithm to keep states ♣ψ k i ⟩ (as described above) on the way to produce ψ k n-1 = ψ N/2 , Bonnetain and Naya-Plasencia then proposed Algorithm 7.

Algorithm 7 Variant of KuperbergŠs algorithm to obtain s in one pass

Require: 2 ℓ phase vectors as in Equation 4.2, where each copy has k ∈ Z N chosen independently and uniformly at random. Ensure: The secret s.

1: Separate the coset states in pools P i , where if ∀i ∈ 0, n -1 , P i ̸ = ∅ then Pick one element in each P i , apply Algorithm 6 and return s 7: return "The algorithm failed"

P i def = ¶♣ψ k ⟩ : 2 i ♣k, 2 i+1 ̸ ♣k♢
We will come back on Algorithm 7 with more details in Chapter 6, as it was the inspiration for a new algorithm for solving the DCP.

We will now dive deeper into the parameters of KuperbergŠs algorithm and its complexity.

Complexity

KuperbergŠs algorithm has subexponential query, time and space complexities, as stated by the following theorem Sketch of proof (inspired by [START_REF] Childs | Lecture notes on quantum algorithms -Kuperberg's algorithm for the dihedral HSP[END_REF]). The parameters required for the algorithm to work can be estimated as follows. The combination step takes two phase vectors and produces one. This state is of interest for our purpose with probability 1/2. It means than Step 3 of Algorithm 5 divides by 4 the size of the list of phase vectors we have in Step 2. We also notice that on average, 2 m-1 phase vectors could be discarded at Step 2, since we are working on m bits and we will typically have an odd number of phase vectors with probability 1/2 in each sublist (i.e., one unmatched state per sublist). Thus, at the end of the combination routine with j = 0, we have on average 2 ℓ-2 -2 m-1 remaining phase vectors. In turn, when j = 1, we get 2 ℓ-4 -2 m-3 -2 m-1 states, and so on. More generally, at the end of the combination routine for j going from 0 to m -2, we have

2 ℓ-2(j+1) - j i=0 2 m-1-2i = 2 ℓ-2(j+1) + 2 m-1-2j -2 m+1 3
phase vectors on average. At the beginning of the last step, i.e., for j = m -1, we have 2 ℓ-2m + 2 m-1-2(m-1) -2 m+1 3 states. It remains n -1jm bits to put to 0, meaning that on average, 2 n-2-jm phase vectors will be discarded. We end up with

2 ℓ-2m + 2 -m+1 -2 m+1 3 -2 n-2-(m-1)m
states. These states will be of the form ♣ψ 2 n-1 ⟩ or ♣ψ 0 ⟩. In order to simplify the calculations, we will ask to have 2 m-1 states at the end of the algorithm, even if we could ask for less. We Ąrst give a lower bound on the number of phase vectors we previously computed and then we will check for when it is greater than 2 m-1 .

2 ℓ-2m + 2 -m+1 -2 m+1 3 -2 n-2-(m-1)m ≥ 2 ℓ-2m -2 m-1 -2 n-2-(m-1)m
We now look for a lower bound for the polynomial n -2 -(m -1)m. We get it for

m = √ 4n-7+1 2
, which means that m ≈ √ n. We will keep this value in mind but will keep up with the notation m for the sake of simplicity. We now have

2 ℓ-2m + 2 -m+1 -2 m+1 3 -2 n-2-(m-1)m ≥ 2 ℓ-2m -2 m-1 -1
Now if we ask for this expression to be greater than 2 m-1 ,

2 ℓ-2m -2 m-1 -1 ≥ 2 m-1 2 ℓ-2m ≥ 2 m + 1 2 ℓ ≥ 2 3m + 2 2m
Thus, ℓ should be greater than 3m + 1, i.e., ℓ ≈ 3 √ n.

It is in fact possible to study the complexity of KuperbergŠs algorithm more precisely and show that its complexity in terms of queries, classical and quantum time and classical and quantum space is a Õ 2 √ 2 log (3)n



(see [START_REF] Kuperberg | A subexponential-time quantum algorithm for the dihedral hidden subgroup problem[END_REF], Theorem 5.1). Simulations have been carried out by Bonnetain and Schrottenloher to study the practical complexity of this algorithm [START_REF] Bonnetain | ŞQuantum Security Analysis of CSIDHŤ[END_REF]. They obtained a query complexity close to 12 × 2 1.8

√ n (note that √ 2 log 3 ≃ 1.78).

Regev's algorithm

KuperbergŠs Ąrst algorithm requires to store, at each time, a subexponential number of phase vectors; thus, it has subexponential quantum memory complexity. Regev [START_REF] Regev | A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space[END_REF] modiĄed the combination routine to reduce the number of qubits to polynomial, while keeping the time complexity subexponential.

The combination routine in question takes a number of, say ℓ, phase vectors that have in common that their a least signiĄcant bits are zero, and combines them to form a new one that has its a + r least signiĄcant bits set to zero (with of course r > 0). From this method, Regev constructs an algorithm that makes calls to the oracle until it has ℓ phase vectors that share the same number of least signiĄcant bits equal to zero. In this way, we can represent the process as a system of communicating vessels. The Ąrst vase, once full of elements that have no particular structure, builds one that will belong to the second vase, and so on. This idea for keeping the space usage of the resolution of the DCP low is described in Figure 4.3. Now let us focus on the combination routine. It combines ℓ phase vectors for a wellchosen ℓ (to minimize the overall complexity) in the following way. Let B be some chosen, arbitrary value. We start with ℓ phase vectors ♣ψ κ 1 ⟩ , . . . , ♣ψ κ ℓ ⟩ and we let κ def = (κ 1 , . . . , κ ℓ ). We tensor these phase vectors, giving us the superposition:

♣ψ κ ⟩ def = ℓ i=1 ♣ψ κ i ⟩ = b∈F ℓ 2 ω sb•κ N ♣b⟩ (4.3)
We then compute b • κ mod B in an ancillary register, and measure it, which gives us a value z. This projects the superposition on the vectors b such that b • κ mod B = z. We choose ℓ and the size of B such that on average two solutions b 0 and b 1 occur. The state becomes proportional to:

♣b 0 ⟩ + ω s(b 1 -b 0 )•κ N ♣b 1 ⟩
If there are more than two solutions, we choose two and project onto them (the exact process will be described later). Finally, we remap b 0 , b 1 to 0, 1 respectively. We have obtained a phase vector ♣ψ κ ⟩ with a label κ = (b 1 -b 0 ) • κ ≤ B, i.e., by deĄnition of b 0 and b 1 , κ has now its last log (B) bits equal to zero. Then, step by step (actually, thanks to the process described before and which is illustrated in Figure 4.3 with this combination routine plugged in), we can build phase vectors whose labels have more and more of their least signiĄcant bits zeroed out until we obtain the label N/2 = 2 n-1 .

Regev [START_REF] Regev | A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space[END_REF] and later Childs, Jao and Soukharev [START_REF] Childs | ŞConstructing elliptic curve isogenies in quantum subexponential timeŤ[END_REF] used this combination routine to get an algorithm with Õ 2

√ 2n log n 
queries and O (n) quantum memory. In the following sections, we give a more detailed description of the algorithm and an analysis of its complexity.

Algorithm

We provide in Algorithm 8 the pseudocode for RegevŠs combination routine.

The projective measurement in Step 5 can be done by marking the vectors of interest thanks to an unitary operator U deĄned as:

U ♣b⟩ ♣0⟩ → ♣b⟩ ♣β⟩ where β =    1 if b ∈ ¶b 0 , b 1 ♢ 0 otherwise
and second, measuring this ancillary qubit β. If 1 is measured, we succeeded to project the superposition of t elements on the two we targeted and we can go to Step 6 of the algorithm. On the other hand, if 0 is measured, then we obtained a superposition of all the solutions except the two we wanted to project on. Thus, we pick two other solutions and restart the projection process with these two vectors. This process has some small probability to fail if t is odd that we can upperbound by 1/3.

The Ąnal relabeling step is quite simple and can be achieved in the following way:

(ω sb 0 •κ N ♣b 0 ⟩ + ω sb 1 •κ N ♣b 1 ⟩) ♣0⟩ U -→ ω sb 0 •κ N ♣b 0 ⟩ ♣0⟩ + ω sb 1 •κ N ♣b 1 ⟩ ♣1⟩ V -→ ♣0⟩ (ω sb 0 •κ N ♣0⟩ + ω sb 1 •κ N ♣1⟩)
. . .

ω sb•κ N ♣b⟩ ♣z⟩ 4: Compute b ∈ F ℓ 2 : b • κ mod 2 a+r = z , of size t.
Denote by b i the elements of this set. The state can be rewritten as

t-1 i=0 ω sb i •κ N ♣b i ⟩ ♣z⟩ 5: A projective measurement on a couple of solutions (♣b 0 ⟩ , ♣b 1 ⟩) gives 1 √ 2 ω sb 0 •κ N ♣b 0 ⟩ + ω sb 1 •κ N ♣b 1 ⟩  6: return The relabeled state 1 √ 2 ♣0⟩ + ω s(b 1 -b 0 )•κ N ♣1⟩ 
where the operators U and V are deĄned as follows:

U ♣b b ⟩ ♣0⟩ → ♣b b ⟩ ♣b⟩ and V ♣b b ⟩ ♣b⟩ → ♣0⟩ ♣b⟩ for b ∈ ¶0, 1♢.
Recall that the implementation of the operator V is possible because b 0 and b 1 are classicaly known.

Complexity

RegevŠs algorithm has subexponential query and time complexities but only needs a polynomial space, as stated by the following theorem. [START_REF] Regev | A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space[END_REF]). Since each routine in the process sets O √ n log n new bits to zero, we will need O  n log n  routines in the pipeline, described in Figure 4.3. We wonŠt prove it here but it can be shown that the combination routine is successful with constant probability (see for example [START_REF] Regev | A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space[END_REF][START_REF] Bonnetain | ŞHidden Structures and Quantum CryptanalysisŤ[END_REF]). Then, inputting a total of ℓ n log n phase vectors suffices for the algorithm to output a solution with very high probability. This quantity is of the same order as 2 O( √ n log n) , hence the query complexity estimate. Finally, the time complexity is of the same order since we can bound the time taken by the routine combination by 2 O(ℓ) .

Sketch of proof (given by

RegevŠs study of the complexity of his own algorithm, which was fairly superĄcial, was taken up in detail by Childs, Jao and Soukharev. They proved the following result. There are a number of possible tradeoffs, which can be achieved by adjusting the value of ℓ. This was the subject of a study by Bonnetain, and we refer to his paper on the subject [START_REF] Bonnetain | Improved low-qubit hidden shift algorithms[END_REF] as well as his PhD thesis [START_REF] Bonnetain | ŞHidden Structures and Quantum CryptanalysisŤ[END_REF].

Low Queries Variant RegevŠs combination method, described by Algorithm 8, is used in a communicating vessel system. The more successive rounds there are in this system, the fewer vectors are required as input to the combination method. And vice versa.

When we want to optimize the algorithm in terms of time, we obtain Theorem 4.3, with what is usually called RegevŠs algorithm, which uses a polynomial space and 2 O(

√ n log n)
queries and time. But if we take our system of communicating vessels to have only one round, we obtain an algorithm that takes ℓ = n vectors and directly produces the one of interest (i.e., the one with k = N/2) at the cost of solving a subset-sum problem on n-bit numbers. The result is an algorithm with exponential complexity in classical time, but which uses only O (n) queries to Ąnd a bit of the secret, hence a quadratic number (in n) of queries to Ąnd the whole secret. This limiting case of RegevŠs algorithm was described and studied by Bonnetain and Schrottenloher in [START_REF] Bonnetain | ŞQuantum Security Analysis of CSIDHŤ[END_REF]. It will be our starting point to design a new algorithm which reduces the DCP to an instance of quantum subset-sum instead of a classical one in Chapter 5.

Kuperberg's second algorithm

Like the two previous algorithms, KuperbergŠs collimation sieve [START_REF] Kuperberg | Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem[END_REF] is a hybrid quantum/classical procedure starting from the initial phase vectors, where we need to perform both quantum computations which create new vectors, and classical computations which give their description. It improves on the time complexity of RegevŠs algorithm and his own Ąrst algorithm, while retaining its use in quantum space polynomial. It is inspired by RegevŠs algorithm and works in the same way with tensored phase vectors. However, in order to control these new phase vectors, we need to know the list of all their labels. These lists will become of subexponential size, although the vector itself requires only a polynomial amount of qubits. This is why the algorithm combines a polynomial quantum memory with a subexponential classical memory, while RegevŠs algorithm needed polynomial classical and quantum space.

Algorithm

To introduce KuperbergŠs second algorithm, we begin by rewriting RegevŠs algorithm in a slightly different way. SpeciĄcally, instead of indexing the phase vector with a vector κ of size ℓ and writing the algorithm with all the scalar products κ • b for b ∈ F ℓ 2 , we list all the scalar products directly as a vector k = (k 1 , • • • , k L ) with in this case L = 2 ℓ , and then directly work with the values k i in this version of the algorithm. Namely, we can give a more general deĄnition of phase vectors, as the superposition:

♣ψ k ⟩ def = i∈ 1,L ω sk i N ♣i⟩ (4.4)
We can now present KuperbergŠs second algorithm combination routine, which uses this more general deĄnition to generalize in some sense RegevŠs algorithm. The Ąrst main difference is that the former does not necessarily reduce the list of labels down to 2 in the end, contrary to the latter. In other words, where Regev uses a vector of length L to produce one of length 2, Kuperberg uses two of length L and L ′ to produce one of length L " (where in practice L ≃ L ′ ≃ L "), as shown in Algorithm 9. The second main difference is that while Regev uses a vector of size L = 2 ℓ for some ℓ, Kuperberg uses (and produces) vectors of size L which can be any number, not necessarily a power of 2.

Starting from a certain set of phase vectors, we can identify them with the classical lists of their labels. The combination step operates on these lists like a purely classical list-merging algorithm, in which new lists of labels are formed from the pairs of labels satisfying a certain condition. This algorithm can be represented as a merging tree in which all nodes are lists of labels (resp. phase vectors). On the classical side, KuperbergŠs algorithm is thus similar to WagnerŠs generalized birthday algorithm [START_REF] Wagner | ŞA generalized birthday problemŤ[END_REF], which is a Algorithm 9 Combination routine in the collimation sieve.

Require: a parameter r and 2 phase vectors ♣ψ k ⟩ and ♣ψ k ′ ⟩ of respective length L and L ′ , such that for some a, ∀i ∈ 1, L , 2 a ♣k i and ∀j ∈ 1, L ′ , 2 a ♣k ′ j Ensure: a phase vector ♣ψ v ⟩ of length L ", such that ∀i ∈ 1, L " ,

2 a+r ♣v i 1: Tensor ♣ψ k ⟩ and ♣ψ k ′ ⟩ ♣ψ k ⟩ ⊗ ♣ψ k ′ ⟩ = i∈ 1,L j∈ 1,L ′ ω s(k i +k ′ j ) N ♣i⟩ ♣j⟩ 2: Compute the function (i, j) → k i + k ′ j mod 2 a+r into an ancillary register i∈ 1,L j∈ 1,L ′ ω s(k i +k ′ j ) N ♣i⟩ ♣j⟩ k i + k ′ j mod 2 a+r
3: Measure the ancillary register. The state collapses to:

i∈ 1,L ,j∈ 1,L ′ k i +k ′ j mod 2 a+r =z ω s(k i +k ′ j ) N ♣i⟩ ♣j⟩ ♣z⟩ 4: Compute (i, j) ∈ 1, L × 1, L ′ : k i + k ′
j mod 2 a+r = z , of size L ". 5: Apply to the state a transformation that maps the pairs (i, j) to 1, L " . 6: Return the state and the vector of corresponding labels

k i + k ′ j .
binary merging tree of depth √ n. In WagnerŠs algorithm, the goal is to impose stronger conditions at each level which culminate in a full-zero sum. Here, the same conditions are imposed on the labels in the phase vectors. A success in the list-merging routine is equivalent to a success in the collimation routine (we obtain a phase vector with the wanted label). The query, time and memory complexities depend on the shape of the tree. Even though the conditions are actually chosen at random at the measurement step in Algorithm 9, we can consider them chosen at random before the combination to analyze the algorithm. The merging tree will typically have the shape pictured in Figure 4.4.

Complexity

In the following lemma, we give the complexity of KuperbergŠs second algorithm. Proof. The optimal time complexity is obtained with a tree (as described in We start from the leaves of the tree, which correspond to phase vectors of length L = 2, towards the root, where the solution vector will be found. At the i-th level of the tree, we form pairs of phase vectors of length (approximately) 2 i , which we combine two by two, to form new ones of length (approximately) 2 i+1 that will belong to the (i + 1)-th level. If we were to process this tree level by level, we would not only have to store 2 d+1 classical indices of the phase vectors, where d is the depth of the tree, but also all the phase vectors themselves. A better strategy exists, and it is a kind of reverse depth-Ąrst search. This method allows us to store at most a reasonable number of phase vectors at any time, i.e., use poly(n) qubits.

as follows. It starts with lists of size 2, i.e., two-labeled phase vectors. At level i starting from the leaves, the lists have (expected) size 2 i , and they are merged pairwise into a list of size 2 i+1 . This means that when combining phase vectors of the i-th level of the tree, we can eliminate 2i -(i + 1) = i -1 bits. So the depth d of the tree should be such that:

d-1 i=1 (i -1) = n
i.e., d should be close to √ 2n. We directly deduce that there are in total 2 √ 2n leaves (hence queries to do). The (classical) cost of merging, over the whole tree, is equal to the sum of all list sizes. It is also the (quantum) cost of the relabeling operations:

d i=1 2 √ 2n-i × 2 i = O √ 2n2 √ 2n



To compute the memory complexity, one must note that it is not required to store whole levels of the merging tree. Instead, we compute the lists (resp. the phase vectors) depth-Ąrst, and store only one node of each level at most, i.e., d nodes in total, as we can prove by induction. Indeed, if d = 2, we will have to store the two initial phase vectors to produce a Ąnal one, so we will store at most d phase vectors. Assume this is true for a tree of i levels. It is then also true for a tree of i + 1 levels, since we will store the root of one subtree of i levels while we have to go through the whole other subtree, i.e. store at most i additional nodes, until we arrive to its root and combine the result with the root of the former subtree. In the end this means that we will have to store at most around √ 2n phase vectors at any time. For the same reason, the classical memory complexity is O 2

√ 2n  .
Up to this point, the analysis was only performed on average, and in practice, there is a signiĄcant variance in the list sizes in the tree. More precise analyses were performed in [START_REF] Peikert | ŞHe Gives C-Sieves on the CSIDHŤ[END_REF][START_REF] Chávez-Saab | ŞThe SQALE of CSIDH: sublinear Vélu quantum-resistant isogeny action with low exponentsŤ[END_REF]. It follows from them that the list size after merging should be considered smaller than the expected one by an Şadjusting factorŤ 3/(2π). Furthermore, the combination may create lists that are too large, which must be discarded. The empirical analysis of Peikert [START_REF] Peikert | ŞHe Gives C-Sieves on the CSIDHŤ[END_REF] gives a factor (1δ) of loss at each level, with δ = 0.02. The smaller factor in list sizes simply means that at level i, we will not exactly eliminate i -1 bits, but ic where c = log 2 1 + 3 2π  ≃ 0.76. (We can control the interval size in Algorithm 9 very precisely.) Thus d is in fact solution to:

d i=1 (i -c) = n =⇒ d 2 2 -ch = n =⇒ d ≃ c + 2n + 4c 2 .
Finally, the loss at each level induces a global multiplicative factor (1δ) -d = 2 -log 2 (1-δ)d ≃ 2 0.029d on the complexity. Therefore, accounting for the adjusting factor and discards, the query complexity of the sieve is close to:

2 1.029(0.76+ √ 2n+2.30) (4.5)
and the quantum time complexity multiplies this by a factor 0.76 + √ 2n + 2.30. The difference with the exact 2 √ 2n is not negligible, but not large either. At n = 4608, the two exponents are respectively 99.6 and 96.

This analysis applies if we want to obtain a speciĄc label, e.g., the label 1. Afterwards, the algorithm can be repeated n times. For a generic N (not a power of 2), one typically produces all labels which are powers of 2 and uses a QFT to directly recover the secret. This is done for example in [START_REF] Bonnetain | ŞQuantum Security Analysis of CSIDHŤ[END_REF] but Peikert [START_REF] Peikert | ŞHe Gives C-Sieves on the CSIDHŤ[END_REF] proposed a more advanced method to recover multiple bits of the secret with each phase vector. Lemma 4.5 gives the complexity of Ąnding one bit of the secret. We give an important formula for computing the complexities for Ąnding the whole secret from this lemma. Lemma 4.6. Let α > 0 and n be a positive integer. We have

n i=1 2 α √ i = O √ n2 α √ n  .
Proof. When i is a perfect square, let say i = j 2 , we have that 2 α √ i = 2 αj . Now for any i between the two perfect squares (j -1) 2 and j 2 , we have the upper bound 2 α √ i < 2 αj . In order to use this, we rewrite the sum:

n i=1 2 α √ i ≤ ⌈ √ n⌉-1 j=0 (j+1) 2 k=j 2 +1 2 α √ k ≤ ⌈ √ n⌉-1 j=0 (j+1) 2 k=j 2 +1 2 α(j+1) = ⌈ √ n⌉-1 j=0 (2j + 1)2 α(j+1)
Using the formula for geometric series, we obtain:

n i=1 2 α √ i ≤ 2 α+1 (2 α -1) ⌈ √ n⌉ 2 α⌈ √ n⌉ -2 α (2 α⌈ √ n⌉ -1) (2 α -1) 2 + 2 α 2 α⌈ √ n⌉ -1 2 α -1 = 2 α 2 α -1 (2 √ n + 1)2 α⌈ √ n⌉ - 2 α+1 2 α -1 (2 α⌈ √ n⌉ -1) -1 ≤ 2 α 2 α -1 (2 √ n + 1)2 α⌈ √ n⌉ .
which allows us to conclude the proof, α being Ąxed.

In Chapter 5, we will consider the task of obtaining labels which, instead of reaching a prescribed k, match k on a certain number of bits only (we can say that the phase vectors are partially collimated), let say i: this complexity is of order 2 √ 2i . By Lemma 4.6, we can obtain a sequence of i phase vectors collimated on 1, . . . , i bits with a query complexity (by Lemma 4.6):

i j=1 2 √ 2j = O √ i2 √ 2i  Chapter 5 A Query Interpolation Algorithm Let n def = ⌈log N ⌉.
In this chapter, based on [START_REF] Remaud | ŞTime and Query Complexity Tradeoff for the Dihedral Coset ProblemŤ[END_REF], we Ąrst propose a new algorithm for solving the DCP using a linear number of queries. It is somewhat analogous to RegevŠs algorithm where instead of reducing the DCP to a classical subset-sum problem, it reduces the DCP to a quantum subset-sum problem. In the Ąrst case, the algorithm makes O (n) queries to Ąnd one bit of the secret, meaning it has to be iterated O (n) times. With this new algorithm, which is inspired by [Reg02; Ste+09], we only need O (1) quantum subset-sum instances, i.e., O (n) queries, to Ąnd the whole secret. Second, we present a simple and natural method of interpolation between KuperbergŠs second algorithm (which is the state of the art) and the new algorithm we mentioned above. It consists in using KuperbergŠs algorithm to more or less preprocess the states given as input to our algorithm. The difficulty of solving the inherent quantum subsetsum problem instance will depend on the preprocessing step.

Finally, as a building block of our algorithms, we study quantum subset-sum algorithms when the problem to solve is partially in superposition. We show here that we can still improve over GroverŠs search even under the constraint of a polynomial quantum memory, using an exponential classical memory, with or without quantum access. SpeciĄcally, we show that the QRACM-based algorithm of [START_REF] Bonnetain | ŞImproved Classical and Quantum Algorithms for Subset-SumŤ[END_REF] adapts to this case and reaches a complexity Õ 2 0.2356n . Without QRACM, we reach a quantum time Õ 2 0.4165n using O 2 0.2334n bits of classical memory, improving over a previous algorithm by Helm and May [START_REF] Helm | ŞThe Power of Few Qubits and Collisions -Subset Sum Below GroverŠs BoundŤ[END_REF]. In both cases, we also give non-asymptotic estimates of their complexity.

All together, we can summarize the complexity exponents of the different algorithms for solving the DCP in Table 5.1, including the new one we propose. Note that this is a corrected version of the same table appearing in the paper [START_REF] Remaud | ŞTime and Query Complexity Tradeoff for the Dihedral Coset ProblemŤ[END_REF] (same for the table that will follow in the next paragraph where some evaluations are given). In this table and in this chapter in general, RegevŠs algorithm refers to the low-queries variant described in Section 3.2, and 0.283 is the best asymptotic exponent that we can obtain for classical subset-sum algorithms known at the moment [START_REF] Bonnetain | ŞImproved Classical and Quantum Algorithms for Subset-SumŤ[END_REF], if there are no constraints on the memory. We propose two versions of our algorithm, one with QRACM and one without, both using polynomial quantum space. Note that our algorithm with QRACM outperforms other algorithms using a linear number of queries when we look at the complexity in classical time + quantum time.

Impact on CSIDH.

Although KuperbergŠs second algorithm is the one with the best time complexity for solving the DCP, it is still interesting to look at algorithms that only use a linear number of queries, since for example, CSIDH cryptanalysis via the resolution of the DCP involves the use of a very expensive oracle.

We give in Table 5.2 a few examples of complexity exponents for parameters of CSIDH. Organization. In Section 1, we give some preliminaries on subset-sum algorithms that we will use as black boxes afterwards. In Section 2, we recall the reduction from the DCP to the subset-sum problem, and introduce our new idea of using a quantum subset-sum solver. Our interpolation between the sieving and subset-sum approaches is detailed in Section 3. Finally, our contributions on quantum subset-sum algorithms and the details of the black boxes that we used in the chapter are provided in Section 4.

The Subset-Sum Problem. As we saw in Chapter 4, the DCP can be reduced to the Subset-sum problem; this leads to the most query-efficient algorithms, and depending on the cost of queries, to the best optimization for some instances. We recall here the deĄnition of this problem Problem 5.1 (Subset-sum). A subset-sum instance is given by

(v, k), v ∈ Z N , k ∈ Z m N
for some modulus N and integer m. The problem is to find a vector (or all vectors

) b ∈ ¶0, 1♢ m such that b • k = v mod N .
When m ≃ n = ⌈log N ⌉, there is one solution on average. The instance is said to be of density one. Heuristic classical and quantum algorithms based on the representation technique [HJ10; BCJ11] allow to solve it in exponential time in n. In the following, we will use these algorithms as black boxes. We Ąrst need a classical subset-sum solver.

Fact 3. We have a classical algorithm S C which, on input a subset-sum instance (v, k) of density one, finds all solutions. It has a time complexity in Õ (2 c cSS n ) where c cSS < 1.

Here, the parameter c cSS is the best asymptotic exponent that we can obtain for classical subset-sum algorithms. If there are no constraints on the memory, we can take c cSS = 0.283 which is the best value known at the moment [START_REF] Bonnetain | ŞImproved Classical and Quantum Algorithms for Subset-SumŤ[END_REF].

In this paper, we will also need (quantum) algorithms solving a more difficult problem, in which k is Ąxed, but the target v is in superposition. We will call this type of algorithm a quantum subset-sum solver.

Fact 4. We have a quantum algorithm S Q which has a complexity cost in Õ (2 c qSS n ) (where c qSS < 1), which, given an error bound ε, given a known (classical) k ∈ Z m N and on input a quantum v, maps:

♣v⟩ ♣b⟩ → ♣v⟩ b ⊕ S Q (v)
where, for a proportion at least 1ε of all v admitting a solution, S Q (v) is selected uniformly at random from the solutions to the subset-sum problem, i.e., from the set

¶b : b • k = v♢.
Notice that in the way we implement the solver, we can only guarantee that it succeeds on a large proportion of inputs (there remains some probability of error). However, it depends on some precomputations that we can redo, to obtain a heuristically independent solver which allows to reduce ε and / or to ensure that we get more solutions.

Though we could implement the function S Q by running an available classical (or quantum) subset-sum algorithm, it would then require exponential amounts of qubits. Using only poly(n) qubits, we know for sure that c qSS ≤ 0.5, because we can use GroverŠs algorithm to exhaustively search for a solution b. This search uses poly(n) qubits only. In Section 4, we will show that we can reach smaller values for c qSS , which differ depending on whether we allow QRACM or not.

Reducing the DCP to a Subset-sum Problem

Recall that we note n = ⌈log N ⌉, where N is not necessarily a power of 2. We will focus in this section on two algorithms to solve the DCP: the Ąrst one (from Regev [START_REF] Regev | A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space[END_REF]) uses a classical subset-sum solver and the other (ours) uses a quantum one.

Using a Classical Subset-sum Solver

By reducing RegevŠs algorithm to a single level as described in Section 3.2, we can directly produce lsb(s) from n phase vectors. The pseudocode of the corresponding algorithm is given in Algorithm 10.

It can be proven that in Step 4, the number of solutions is quite small but generally enough for our purpose. In Step 5, the solution vectors we want to project our superposition on are marked in an ancillary register which is then measured. Either we will get what we want, or we will end up with a superposition of the solution vectors that were not marked, in which case we start the process again with two other solution vectors. For more details, we refer to the extensive study of RegevŠs algorithm by Childs, Jao and Soukharev [START_REF] Childs | ŞConstructing elliptic curve isogenies in quantum subexponential timeŤ[END_REF].

The following lemma gives us the complexity of Algorithm 10, derived from RegevŠs algorithm.

Lemma 5.1 (Subsection 3.3 [BS20]

). There exists an algorithm which finds lsb(s) with O (n) queries and quantum time and space. It has the same usage in classical time and space as the subset-sum solver S C .

Algorithm 10 Ąnds one bit of the secret. In order to retrieve the whole secret, we will have to repeat this procedure n times. Thus, we get an algorithm using a quadratic number of calls to the oracle, exponential classical time and space because of the subset-sum solver, linear quantum space and quadratic quantum time.

It turns out that we could solve the classical subset-sum problem on the side with a quantum computer, leading to some tradeoffs described in [START_REF] Bonnetain | Improved low-qubit hidden shift algorithms[END_REF]. But we show hereafter that we can also build an algorithm which directly uses a quantum subset-sum solver instead of having to measure the ancillary register to get a classical instance of a subset-sum problem.

Algorithm 10 Finding lsb(s) using a classical subset-sum solver S C Require:

♣ψ k 1 ⟩, . . . , ♣ψ kn ⟩ with k def = (k 1 . . . k n ) ∈ Z n N . Ensure: lsb(s).
1: Tensor the phase vectors and append a register on

F n-1 2 n i=1 ♣ψ k i ⟩ = 1 √ 2 n b∈F n 2 ω sb•k N ♣b⟩ 2:
Compute the inner product of b and k in the ancillary register

1 √ 2 n b∈F n 2 ω sb•k N ♣b⟩ b • k mod 2 n-1 3: Measure the ancillary register ▷ Z is a normalizing constant 1 √ Z b∈F n 2 : b•k=z mod 2 n-1 ω sb•k N ♣b⟩ ♣z⟩ 4: Search for vectors b i such that b i • k = z mod 2 n-1 using S C 5: Project the superposition onto a pair of solutions, e.g., (b 1 , b 2 ) 1 √ 2 ω sb 1 •k N ♣b 1 ⟩ + ω sb 2 •k N ♣b 2 ⟩  6:
Relabel the basis states to (♣0⟩ , ♣1⟩), resulting in

ω sb 1 •k N √ 2 ♣0⟩ + ω s(b 2 -b 1 )•k N ♣1⟩  7:
Apply a Hadamard gate on the qubit, measure it and output the result.

Using a Quantum Subset-sum Solver

The main observation that led to the design of the algorithm we introduce hereafter is that on one hand, we would like to build the superposition

1 √ N j∈Z N ω sj N ♣j⟩ (5.1)
since applying the inverse QFT on Z N on it would directly give the secret s, and on the other hand, we know that it would be possible, thanks to a quantum subset-sum solver, to prepare the state

1 Z(k) b∈F m 2 ω sb•k N ♣b • k mod N ⟩ (5.2)
where Z(k) is a normalizing constant depending on k. Indeed, preparing this state is done by using RegevŠs trick (see [START_REF] Regev | ŞQuantum computation and lattice problemsŤ[END_REF][START_REF] Stehlé | ŞEfficient Public Key Encryption Based on Ideal LatticesŤ[END_REF]), i.e., (i) by tensoring m phase vectors

1 √ M b∈F m 2 ω sb•k N ♣b⟩ ♣0 n ⟩ ,
(ii) then computing the subset-sum in the second register to get the entangled state

1 √ M b∈F m 2 ω sb•k N ♣b⟩ ♣b • k mod N ⟩ ,
(iii) and Ąnally disentangle it thanks to a quantum subset-sum algorithm which from b • k mod N and k (which is classical) recovers b and subtracts it from the Ąrst register to get the state we want.

As one can see, if we could take m = n and have an isomorphism between the vectors b and the knapsack sums b • k mod N , the prepared state (5.2) would be exactly the superposition (5.1).

However, there would be many cases in which multiple solutions to the subset-sum problem exist. Thus we take m < n and deĄne M def = 2 m < N . This is different from Algorithm 10, where such collisions are needed. We obtain Algorithm 11, which uses RegevŠs trick with a quantum subset-sum solver in Step 3.

Despite M being smaller than N , some cases still yield multiple solutions, and furthermore the subset-sum solver (as given by Fact 4) fails on some instances. This is why we distinguish between Algorithm 11 in which we consider the quantum subset-sum solver to be ideal (i.e., it Ąnds back b from b • k and k with certainty), and the algorithm that we actually build in practice: Algorithm 12.

The analysis of

G (k) def = ¶b ∈ F m 2 : S Q (b • k) = b♢ and let G(k) be the size of the set G (k).
We apply in Step 4 a measurement in order to disentangle the superposition we have, so we can apply an inverse QFT in the same natural way as in the ideal algorithm. We show that the probability of success of the measurement (i.e., of measuring 0) is good enough for our purpose when taking m close to n. We also prove under the same

Algorithm 11 Ideal algorithm

Require: A parameter m < n and phase vectors ♣ψ k i ⟩ for i ∈ 1, m . Ensure: An element j ∈ Z N .

1: Tensor the m phase vectors and append a register on

Z N m i=1 ♣ψ k i ⟩ ♣0 n ⟩ = 1 √ M b∈F m 2 ω sb•k N ♣b⟩ ♣0 n ⟩ 2:
Compute the inner product of b and k in the ancillary register

1 √ M b∈F m 2 ω sb•k N ♣b⟩ ♣b • k mod N ⟩ 3: Uncompute b thanks to k and ♣b • k mod N ⟩ 1 Z(k) b∈F m 2 ω sb•k N ♣0 m ⟩ ♣b • k mod N ⟩ 4:
Apply the inverse QFT on Z N on the second register

1 √ N j∈Z N   1 Z(k) b∈F m 2 ω (s-j)b•k N   ♣0 m ⟩ ♣j⟩ 5:
Measure the state and output the resulting j.

assumption that the algorithm outputs the secret with good probability. All in all, these two properties lead to our main result.

Theorem 5.1. There exists an algorithm which finds s using O (n) queries and the same usage in time and space as the subset-sum solver S Q .

In order to analyze Algorithm 12 and prove Theorem 5.1, we will proceed in two steps.

Step 1.

The Ąrst step is to give a lower bound on E k [G(k)]. This lower bound is given by estimating the number of vectors which admit more than one possible solution.

To arrive here, we Ąrst take a look at the normalization constant Z(k) and we compute E k [Z(k)] (the average over all choices of k). This can be done by simply looking at the measurement step in Algorithm 11.

Lemma 5.2. We have

E k [Z(k)] = M  1 + M -1 N  .
Algorithm 12 Finding s using a quantum subset-sum solver S Q Require: A parameter m < n and phase vectors ♣ψ k i ⟩ for i ∈ 1, m . Ensure: An element j ∈ Z N .

1: Tensor the phase vectors and append a register on

Z N m i=1 ♣ψ k i ⟩ ♣0 n ⟩ = 1 √ M b∈F m 2 ω sb•k N ♣b⟩ ♣0 n ⟩ 2:
Compute the inner product of b and k in the ancillary register

1 √ M b∈F m 2 ω sb•k N ♣b⟩ ♣b • k mod N ⟩ 3: Apply S Q to uncompute b 1 √ M b∈F m 2 ω sb•k N b ⊕ S Q (b • k) ♣b • k mod N ⟩ 4:
Measure the Ąrst register. If the result is not 0 m , abort and restart with new coset states. Otherwise, we obtain

1 G(k) b∈G ω sb•k N ♣0 m ⟩ ♣b • k mod N ⟩ 5:
Apply the inverse QFT on Z N on the second register

1 √ N j∈Z N   1 G(k) b∈G ω (s-j)b•k N   ♣0 m ⟩ ♣j⟩ 6:
Measure the state and output the resulting j.

Proof. Fix k = (k 1 , • • • , k m )
. For all j ∈ Z N , the measurement in Algorithm 11 returns j with probability:

P ideal [j♣k] = 1 N Z(k) b∈F m 2 ω (s-j)b•k N 2 = 1 N Z(k) m i=1 1 + ω (s-j)k i N  2 = 1 N Z(k) m i=1 1 + ω (s-j)k i N 2 = 1 N Z(k) m i=1 4 cos 2  πk i s -j N  = M 2 N Z(k) m i=1 cos 2  πk i s -j N  .
Furthermore, we have j∈Z N P ideal [j♣k] = 1, so we can write:

Z(k) = M 2 N j∈Z N m i=1 cos 2  πk i s -j N  (5.3) It follows that E k [Z(k)] = M 2 N j∈Z N E m i=1 cos 2  πk i s -j N 
and since the k i are i.i.d., we have

E k [Z(k)] = M 2 N   1 + j∈Z N \ ¶s♢ m i=1 E  cos 2  πk i s -j N    = M 2 N 1 + (N -1) m i=1 1 2 = M N (N + M -1) .
Next, we give a relation between G(k) and Z(k).

Lemma 5.3. For any k:

G(k) ≥ (1 -ε) (2M -Z(k)) .
Proof. Fix k. Let B(j) be the set of vectors whose knapsack sum is j:

B(j) def = ¶b ∈ F m 2 : b • k = j mod N ♢
and let C i be the set of vectors b that have i collisions:

C i def = ¶b ∈ F m 2 : #B(b • k) = i♢ .
We denote by C i the size of the set C i .

If we take a closer look at Z(k), we have that

Z(k) = j∈Z N b∈B(j) ω sb•k N 2 = j∈Z N ω sj N 2 b∈B(j) 1 2 = j∈Z N b∈B(j) b ′ ∈B(j) 1 = j∈Z N b∈B(j) b ′ ∈B(b•k) 1 = j∈Z N b∈B(j) #B(b • k) = b∈F m 2 #B(b • k) = i≥1 b∈F m 2 : #B(b•k)=i i = i≥1 iC i
Letting C >1 be the number of vectors b with at least one collision (i.e., for which there exists b ′ ̸ = b such that they have the same knapsack sum), we have

C >1 = i>1 C i . From Z(k) = i≥1 iC i = C 1 + 2 i≥2 C i + i≥3 (i -2)C i ,
it follows that we have the lower bound:

Z(k) ≥ C 1 + 2C >1 .
Injecting twice the equation C 1 = M -C >1 in this inequality and using the trivial bound

G(k) ≥ (1 -ε)C 1 , we conclude the proof.
From Lemma 5.2 and Lemma 5.3, we immediately deduce:

Lemma 5.4. E k [G(k)] ≥ (1 -ε)M  1 - M -1 N  .
Step 2.

The second step in our proof computes the probability of success of the ŞrealŤ algorithm by relating it to E k [G(k)].

Lemma 5.5. Algorithm 12 outputs the secret s with probability

≥ (1 -ε) M (N -M +1) N 2 .
Proof. We compute the probability of measuring j ∈ Z N at the end of Algorithm 12. In particular, we have for s

P real [s♣k] = 1 N G(k) b∈G ω 0 N 2 = G(k) N We have by Lemma 5.4 that E [G(k)] ≥ (1 -ε)M 1 -M -1 N 
. We Ąnish the proof by

observing that P real [s] = E [P real [s♣k]] ≥ (1 -ε) M (N -M +1) N 2
.

Finally, we can prove Theorem 5.1.

Proof.

Step 4 of Algorithm 12 succeeds with average probability

E[G(k)]
M which is greater than (1ε) N -M +1 N (by Lemma 5.4). The Ąnal measurement of the algorithm outputs the secret with probability

≥ (1 -ε) M (N -M +1) N 2
(by Lemma 5.5). We will thus have to repeat the algorithm an expected number smaller than N 3

(1-ε) 2 M (N -M +1) 2 times. By letting m be equal to n -1, we obtain that the algorithm will have to be repeated less than 8/(1ε) 2 times. Thus, we can conclude that our algorithm needs O (n) queries and has complexity costs identical to the ones of the subset-sum solver, since the subset-sum resolution is the only exponential step of the algorithm.

Interpolation algorithm

If we take a look at the ideal algorithm and consider that there is no collision, we can see that we would like 2 m to be as close to N as possible in order for the sum

1 √ M b∈F m 2 ω (s-j)b•k N
to contain as many as possible elements of the sum

1 √ N b∈F n 2 ω (s-j)b•k N .
In the mean time, it is clear that the closest M gets to N , the more likely collisions

b 1 • k = b 2 • k for b 1 ̸ = b 2 become.
We thus have to Ąnd a compromise on the value m or more interestingly play with the values k i used in the algorithm, to avoid collisions and to simplify the resolution of the subset-sum problem.

In fact, we can reduce the size of the subset-sum problem we have to solve by preprocessing the states to get values of k i that will allow us to solve the subset-sum problem on some bits by Gaussian elimination. Constructing these k i Šs can be achieved by KuperbergŠs second algorithm (or any improvement). Given a threshold parameter t ∈ 1, m , we can consider the following conĄguration for the k i to use as inputs in Algorithm 12 (dots represent unknown bits and the i-th bit of the j-th row is the j-th bit of the binary expansion of k i ):

               1 2 • • • m -t m -t + 1 • • • n k 1 1 • • • • • • • • • • k 2 0 1 . . . • • • • • • . . . . . . . . . . . . . . . . . . • • • • k m-t 0 0 • • • 1 • • • • • k m-t+1 0 0 • • • 0 • • • • • . . . . . . . . . . . . . . . • • • • k m 0 0 • • • 0 • • • • •               
(5.4)

In Algorithm 12, it turns out that we can keep a good probability of Ąnding the secret s by letting m be equal to n -1 so that is what we will assume afterwards.

To build phase vectors that satisfy the conĄguration in Equation 5.4, we will approximately have to query the oracle

n-t i=1 2 √ c DCP i + t2 √ c DCP (n-t)



(by Lemma 4.6), where c DCP is the constant of the algorithm used to construct the states (c DCP = 2 for KuperbergŠs second algorithm). For the subset-sum problem, solving it on the Ąrst nt bits is easy (thanks to a Gaussian elimination), the difficulty comes from the last t bits, leading to a complexity in O 2 c qSS t time, where c qSS is the complexity exponent of the quantum subset-sum solver. This parameter t can be used in a natural way to obtain an interpolation algorithm, since it allows to obtain a tradeoff between the preparation of the states and the resolution of the problem (which amounts to solving a quantum subset-sum problem).

We can now give an interpolation algorithm derived from Algorithm 12. We note that letting q be the query complexity exponent, it is possible to determine t from n and the value q we can afford. Using KuperbergŠs second algorithm (or any improvement) to compute suitable phase vectors as described before and then giving them as inputs to Algorithm 12, we can retrieve the secret s as described by Algorithm 13 with the complexities given by Theorem 5.2.

Algorithm 13 Interpolation algorithm (using a quantum SS solver)

Require: q such that 2 q is the number of queries we are allowed to do. Ensure: The secret s.

1: Use KuperbergŠs second algorithm (or any improvement) to create states ♣ψ k i ⟩ for i ∈ 1, m satisfying the conĄguration represented by Matrix (5.4), where t ≈ q c SS . 2: Apply Algorithm 12 on these m states to obtain a value j ∈ Z N . 3: Check if j is the secret. If not, return to Step 1. Otherwise, output j.

Theorem 5.2. Let t ∈ 1, m . Algorithm 13 finds s with O ( √ n -t + t)2 √ c DCP (n-t)  queries in O ( √ n -t + t)2 √ c DCP (n-t) + 2 c qSS t  quantum time, classical space O 2 √ c DCP (n-t) + 2 c qSS t 
and O (poly(n)) quantum space.

We notice that when t = m, the k i are kept random and we have to solve the Şfull rankŤ subset-sum, matching with Algorithm 12. On the other side, when t = 1, we fall back on KuperbergŠs second algorithm since we have in this case to construct a collection of states divisible by all the successive powers of 2. Finally, when 1 < t < m, we have new algorithms working for any number of queries between O (n) and Õ 2

√ c DCP n  .

Quantum Subset-sum Algorithms

In this section, we consider quantum algorithms solving the quantum subset-sum problem introduced in Section 1. We give both asymptotic complexities and numerical estimates.

Recall that we consider a subset-sum instance (v, k), k ∈ Z m N , where v is in superposition, and k will remain Ąxed. The problem is to Ąnd b such that b • k = v mod N for a given (Ąxed) modulus N . For a given v, if there are many solutions, we want to Ąnd one selected uniformly at random (under heuristics). If we want all solutions, then we can run multiple instances of the solver (we will have to redo the pre-computations that we deĄne below). A given solver, deĄned for a speciĄc k, is expected to work only for some (large) proportion 1ε of v. We can check whether the output is a solution or not and measure the obtained bit to collapse on the cases of success.

Algorithms Based on Representations

The best algorithms to solve the subset-sum problem with density one are list-merging algorithms using the representation technique [START_REF] Howgrave | ŞNew generic algorithms for hard knapsacksŤ[END_REF][START_REF] Becker | ŞImproved Generic Algorithms for Hard KnapsacksŤ[END_REF]. The best asymptotic complexities (both classical and quantum) are given in [START_REF] Bonnetain | ŞImproved Classical and Quantum Algorithms for Subset-SumŤ[END_REF]. We detail the representation framework following the depiction given in [START_REF] Bonnetain | ŞImproved Classical and Quantum Algorithms for Subset-SumŤ[END_REF]. To ease the description, we start with the case v = 0, i.e., the homogeneous case, and we will show below how to extend it easily to v ̸ = 0. Guessed Weight. We assume that the solution b is of weight ⌈m/2⌉. This is true only with probability: p m := 2 -m m ⌈m/2⌉ = 1/poly(m). If not, we re-randomize the subset-sum instance by multiplying b by a random invertible matrix. Thus if we manage to solve an instance of weight ⌈m/2⌉, the total complexity to solve any instance will introduce a multiplicative factor 1 pm that we will have to estimate.

Distributions. We consider distributions of vectors having certain relative weights:

D m [α] ⊆ ¶0,
1 ∈ D m [α 1 ], b 2 ∈ D m [α 2 ] and α 1 + α 2 = 1 2 .
In this paper, we consider only representations with coefficients 0 or 1. Extended representations can be considered, using more coefficients (which have to cancel out each other). However, the advantage of using extended representations becomes quickly insigniĄcant in practice. It is also harder to compute the number of representations, or the Ąltering probabilities that we deĄne below.

Merging Tree. A subset-sum algorithm is deĄned by a merging tree. A node in this tree is a list L[ℓ, α, c], which represents a set of vectors drawn from ¶0, 1♢ m under several conditions: 1. the size of the list is 2 mℓ ; 2. the vectors are sampled u.a.r. from a prescribed distribution D m [α]; 3. the vectors satisfy a modular condition of cm bits. With v = 0, the following condition can be used: e • k mod N ∈ [-N/2 cm ; N/2 cm ] for some number c. More generally, the modular conditions can be chosen arbitrarily, as long as they remain compatible with the target v.

Once the tree structure is chosen, its parameters are optimized under several constraints. First, the lists have a certain maximal size. A distribution D m [α] has size m αm , which is asymptotically estimated as ≃ 2 h(α)m . This creates the constraint ℓ ≤ h(α)c. Second, we expect the root list to contain the solution of the problem, i.e., ℓ = 0 (one element), α = 1 2 and c = 1. Finally, each non-leaf list L has its parameters determined by its two children L 1 , L 2 . Indeed, it is obtained via the merging-filtering operation which selects, among all pairs of vectors (e 1 , e 2 ) ∈ L 1 × L 2 , the pairs such that: e 1 + e 2 satisĄes the modular condition (merging) and satisĄes the weight condition (Ąltering). The parameters are:

   α = α 1 + α 2 (increasing weights) ℓ = ℓ 1 + ℓ 2 -(c -min(c 1 , c 2 )) -pf(α 1 , α 2 ) (5.5)
Here, pf is the probability that two vectors chosen u.a.r. in their respective distributions will not have colliding 1s.

Lemma 5.6 (Lemma 1 in [START_REF] Bonnetain | ŞImproved Classical and Quantum Algorithms for Subset-SumŤ[END_REF]). Let e 1 , e 2 be drawn u.a.r. from

D m [α 1 ], D m [α 2 ] with α 1 + α 2 ≤ 1. The probability that e 1 + e 2 ∈ D m [α 1 + α 2 ] is equal to: PF(α 1 , α 2 , m) := m -α 1 m α 2 m / m α 2 m ≃ 2 mpf(α 1 ,α 2 )
where pf(α 1 , α 2

) := h 1-α 2 α 1  α 1 -h(α 1 ) .
Classical Computation of the Tree. To any correctly parameterized merging tree corresponds a classical subset-sum algorithm that runs as follows: it creates the leaf lists by sampling their distributions at random. It then builds the parent lists by merging-filtering steps. The merging operation is efficient, since elements can be ordered according to the modular condition to be satisĄed.

Lemma 5.7 (Lemma 2 in [START_REF] Bonnetain | ŞImproved Classical and Quantum Algorithms for Subset-SumŤ[END_REF]). Let L 1 , L 2 be two sorted lists stored in classical memory with random access. In log 2 , relatively to m, the parent list L can be built in time: max(min(ℓ 1 , ℓ 2 ), ℓ 1 + ℓ 2 -(cmin(c 1 , c 2 ))) and in memory max(ℓ 1 , ℓ 2 , ℓ).

Quantum Computation of the Tree. While the more advanced quantum subsetsum algorithms use quantum walks [Ber+13; HM18; Bon+20], we want to focus here on algorithms using few qubits, which at the moment, rely only on quantum merging with Grover search. They replace the classical merging operation by the following.

Lemma 5.8 (Lemma 4 in [START_REF] Bonnetain | ŞImproved Classical and Quantum Algorithms for Subset-SumŤ[END_REF]). Let L 2 be a sorted list stored in QRACM. Assume given a unitary U that produces, in time t L 1 , a uniform superposition of elements of L 1 . Then there exists a unitary U ′ that produces a uniform superposition of elements of L,

in time O  t L 1 √ pf(α 1 ,α 2 ) max( 2 cm /♣L 2 ♣, 1)  .
Since the goal is only to sample u.a.r. from the root list, only half of the lists in the tree need actually to be stored in QRACM. The others are sampled using the unitary operators given by Lemma 5.8. In short, the obtained subset-sum algorithm is a sequence of Grover searches which use existing lists stored in memory to sample elements in new lists with more constraints.

Heuristics. The standard subset-sum heuristic assumes that the elements of all lists in the tree (not only the leaf lists) behave as if they were uniformly sampled from the set of vectors of right weight, satisfying the modular condition. This heuristic ensures that the list sizes are very close to their average: for each L obtained by merging and

Ąltering L 1 [ℓ 1 , α 1 , c 1 ] and L 2 [ℓ 2 , α 2 , c 2 ],
we have:

♣L♣ ≃ ♣L 1 ♣♣L 2 ♣ 2 m(c-min(c 1 ,c 2 )) PF(α 1 , α 2 , m) ,
where the approximation is exact down to a factor 2. This is true with overwhelming probability for all lists of large expected size via Chernoff-Hoeffding bounds, and even if the root list is of expected size 1, the probability that it actually ends up empty is smaller than e -0.5 ≃ 0.61.

From Asymptotic to Exact Optimizations

As the time and memory complexities of a subset-sum algorithm are determined by its merging tree, we seek to select a tree which minimizes these parameters. Given a certain subset-sum problem, we Ąrst select a tree shape. As an example, the best subset-sum algorithm with low qubits (using QRACM) is the Şquantum HGJŤ algorithm of [START_REF] Bonnetain | ŞImproved Classical and Quantum Algorithms for Subset-SumŤ[END_REF], whose structure is reproduced in Figure 5.1. At level 3, it splits the vectors into two halves, and merges without Ąltering. While all lists are obtained via quantum merging/Ąltering, the main computation is performed after obtaining L 3 1 , L 2 1 , L 1 1 , where the main branch is explored using GroverŠs algorithm: we search through the lists L 3 0 , L 2 0 L 1 0 without representing them in memory. The quadratic speedup of Grover search makes the tree unbalanced, which is reĆected on the naming of its parameters in Figure 5.1.

The asymptotic time complexity of the algorithms has the form Õ 2 βm  , and is the result of summing together the costs of all merging steps. Through the approximation of binomial coefficients, the list sizes are approximated in log 2 and relatively to m. The In this paper, we also perform non-asymptotic optimizations for a given m. Since we use only ¶0, 1♢-representations, the Ąltering probability is well known and has a simple expression (Lemma 5.6). Since the binomial coefficients can be extended as functions of R 2 , we can perform an exact numerical optimization of list sizes for a given m. Afterwards, the numbers obtained are rounded, in particular the weights of representations, and we take the point which gives us the best results: smallest complexity and biggest average size for L 0 .

Example. Let us take n = log 2 N = 256, m = n -1 = 255, and the structure of Figure 5.1. We adapt the optimization code of [START_REF] Bonnetain | ŞImproved Classical and Quantum Algorithms for Subset-SumŤ[END_REF] by taking the exact exponents (not relative to n) and optimize numerically under the constraint L 0 = 2 2 (to ensure that there are solutions). The asymptotic formula would give 2 0.2356n ≃ 2 60.31 . Numerical optimization gives us a time 2 63.81 , but this admits non-integer parameters and it is only the maximum between all steps. By rounding the parameters well, we obtain Figure 5.2.

To compute the quantum time complexity, we consider the list sizes to be exact and use the formula of Lemma 5.8 without the O. The subtrees on the right can be computed in 2 65.71 operations; the slight increase is due to the fact that we take a sum of their respective terms and not a maximum. In the left branch, we sample from L 0 in 2 63.48 operations.

The actual time complexity is slightly bigger, due to the variation in list sizes, and the constant complexity overhead (π/2) of Grover search. More importantly, these operations require: • to recompute a sum, using m (controlled) additions modulo N ;

• to test membership in some distribution; • to sample from input distributions D n . 2 53.31 and a memory 2 26.82 < 2 128×0.2324 = 2 29.75 . On top of this, we must also take p m into account.

After running optimizations for n = 128 to 1024, we obtained a count of about 2 0.418m+12.851 blocks of m arithmetic operations (m 2 quantum gates). The point at which the algorithm starts improving over Grover search lies around n = 157.

Chapter

A Space Interpolation Algorithm

To brieĆy review the main historical stages in solving the DHSP, the Ąrst major milestone was KuperbergŠs Ąrst algorithm, proposed in 2003. It solves the DHSP directly, using only CNOT gates and measurements, in sub-exponential time, but also with sub-exponential space. Less than a year later, Regev proposed an algorithm that is also sub-exponential in time, but with two notable differences: it reduces the DHSP to a subset-sum problem and requires only a polynomial (classical and quantum) space. Subsequent efforts have then focused on this idea of reducing the DHSP to a subset-sum problem, leading to the state-of-the-art, KuperbergŠs second algorithm, and several tradeoffs. On the other hand, only minor improvements have been made on KuperbergŠs Ąrst algorithm (of the order of polynomial factors, see Chapter 4), and the basic idea of the algorithm does not seem to have been exploited beyond that.

In this chapter, we look at just that and give some hints as to what could be done to obtain new algorithms for solving the DHSP using only CNOT gates and measurements, with the aim of building (both classical and quantum) space-efficient algorithms. The work presented here is still in progress, which is why conjectures about the complexity of the algorithms introduced hereafter are given and attempts to prove them are presented. In addition, experimental results are given, reinforcing in particular a conjecture about the complexity of one of the algorithms presented. This algorithm would solve the DCP in Z N where N = 2 n using at most n qubits (and likewise a classical space of the order of n 2 bits) in (classical and quantum) time Θ 2 0.415n with an equivalent number of queries. This algorithm would therefore be the fastest among all the previously known algorithms that use a linear number of qubits to solve the DCP (namely, Ettinger-Høyer algorithm and the algorithm presented in Chapter 5). The work presented in this chapter is the object of a preprint to come soon [START_REF] Remaud | ŞLinear Space Algorithm for the Dihedral Coset ProblemŤ[END_REF]

A Space-Efficient Algorithm

We recall that phase vectors are deĄned as states

♣ψ k ⟩ def = 1 √ 2 (♣0⟩ + ω sk N ♣1⟩) (6.1)
where s ∈ Z N is an unknown integer we are looking for. We will assume for the sake of simplicity that N = 2 n .

In what follows, we assume we have an oracle O outputting at each call an integer k drawn uniformly at random from Z N and the corresponding phase vector ♣ψ k ⟩ as deĄned in Equation (6.1). When such a couple is obtained, we will put it in a pool denoted by

P i if 2 i-1
is the greatest power of 2 that divides k, more precisely:

P i ←-(k, ♣ψ k ⟩) if k ∈ D i where ∀i ∈ 1, n , D i def = (2α -1)2 i-1 , α ∈ 1, 2 n-i .
Thanks to this deĄnition, Bonnetain and Naya-Plasencia [START_REF] Bonnetain | ŞHidden Shift Quantum Cryptanalysis and ImplicationsŤ[END_REF] proposed to write KuperbergŠs Ąrst algorithm in a more opportunistic way, for which we recall in Algorithm 14 a pseudo-code implementation.

Algorithm 14 Opportunistic variant of KuperbergŠs Ąrst algorithm

Require: A set of phase vectors. Ensure: ψ N/2 .

1: Classify the phase vectors in the pools P i 2: for i = 1 to n -1 do 3:

while ♣P i ♣ ≥ 2 do 4:
Pick ♣ψ a ⟩ and ♣ψ b ⟩ from P i such that a ± b has the highest possible divisibility by 2 (and is not 0)

5:

Combine ♣ψ a ⟩ and ♣ψ b ⟩ and insert the result in the appropriate pool 6: if P n ̸ = ∅ then return ψ N/2 7: return "The algorithm failed".

It is claimed in [START_REF] Bonnetain | ŞHidden Shift Quantum Cryptanalysis and ImplicationsŤ[END_REF] that Algorithm 14 has the same complexity as KuperbergŠs Ąrst algorithm and this is the algorithm that inspired us to build a new one that uses at most n qubits and n 2 bits to solve the DCP, making it the most space-efficient algorithm to date. Its pseudocode is provided in Algorithm 15. while for all i, ♣P i ♣ < 2 do 3:

Call O and insert the result in the appropriate pool.

4:

Let i be such that ♣P i ♣ = 2.

5:

Pick ♣ψ a ⟩ and ♣ψ b ⟩ from P i .

6:

Combine ♣ψ a ⟩ and ♣ψ b ⟩ and insert the result in the appropriate pool 7: until there is a state in the pool P n 8: return ψ N/2 . Note that when the state ♣ψ 0 ⟩ is produced, we just drop it off, since it is basically the state ♣+⟩ and does not carry any information about the secret.

From this algorithm we cannot say much other than to study the probability distributions corresponding, on one hand, to what the oracle produces and, on the other, to what is obtained by combining two elements from the same pool.

Probability Distributions. The probability distribution of elements picked uniformly at random from the oracle is given by the following lemma. Lemma 6.1 (Initial distribution). Let i ∈ 1, n . The probability that the oracle O yields a phase vector belonging to the pool P i , denoted by P O [i], is

P O [i] = 2 -i .
Proof. This is straightforward since

P O [i] = ♣D i ♣ ♣Z N ♣ = 2 n-i 2 n .
The probability distribution of elements obtained from combining two phase vectors of a same pool is given by the following lemma.

Lemma 6.2 (Combination distribution). Let i ∈ 1, n -1 and j ∈ 1, n . The probability that combining two phase vectors from P i yields a phase vector from P j , denoted by P i [j], is

P i [j] =    2 i-j if j > i 0 otherwise. Proof. Let P + i [j] (resp. P - i [j]
) be the probability for two phase vectors from P i to produce one from P j when combined and their sum (resp. difference) is obtained. Let k ∈ D i . There exists α ∈ 1, 2 n-i such that k = (2α -1)2 i-1 . We Ąrst look for the proportion P + i [j] of ℓ ∈ D i , which we can write as ℓ = (2β -1)2 i-1 for some β ∈ 1, 2 n-i , such that k + ℓ = (α + β -1)2 i ∈ P j , i.e.,

P + i [j] = 1 ♣D i ♣ # β ∈ 1, 2 n-i (α + β -1)2 i ∈ P j
Looking closely at the condition, it is equivalent to say that there must exist γ ∈ 1, 2 n-j such that

(α + β -1)2 i = (2γ -1)2 j-1
We can see that if j ≤ i, no value for γ exists such that this equation holds. We assume from now on that j > i. The condition becomes

α + β -1 = 2 j-(i+1) mod 2 j-i
It follows that

P + i [j] = 1 ♣D i ♣ 2 n-i 2 j-i = 2 i-j
We use the same reasoning for the difference, P

- i [j] being the proportion of ℓ ∈ P i such that ♣k -ℓ♣ = ♣α -β♣2 i ∈ P j , i.e., P - i [j] = 1 ♣D i ♣ # β ∈ 1, 2 n-i ♣α -β♣2 i ∈ P j
It is equivalent to say that there must exist γ ∈ 1, 2 n-j such that

♣α -β♣2 i = (2γ -1)2 j-1
Once again if j ≤ i, no value for γ exists such that this equation holds. We assume from now on that j > i. The condition is equivalent to

♣α -β♣ = 2 j-(i+1) mod 2 j-i
It follows that

P - i [j] = 1 ♣D i ♣ 2 n-i 2 j-i = 2 i-j
By deĄnition, the overall probability P i [j] is

P i [j] = 1 2 P + i [j] + P - i [j]  = 2 i-j .
These probability distributions would actually be useful for studying the mean hitting time of the Markov chain corresponding to the process followed in the algorithm, which would thus give us the average time complexity of the algorithm. The problem is that there is an exponential number of states in this Markov chain.

On the Markov chain of Algorithm 15. Indeed, these states are vectors of length the number of qubits we are using (namely, n). They contain in their i-th entry the number at time t of phase vectors contained in the i-th pool. The transitions between different vectors are made according to the probability distribution of the combination if we start from a vector that contains a 2 (since in this case we have two phase vectors in the same subpool that we have to combine) or according to the probability distribution given by the oracle in the other case (since if there are no elements to combine, we draw a new one from the oracle). All in all, the Markov chain has an exponential number of states, which makes it difficult to study. Indeed, we have:

• the conĄgurations were a solution have been found, i.e., there is 1 element in P n , coming either from the oracle (which means before calling the oracle, there was no pool with 2 elements) or either from a combination (meaning that 2 elements from a pool were used to produce the solution, leaving no pool with 2 elements) are 2 n-1 of them,

• the conĄgurations for which no solution has been found, corresponding either to a situation where a query must be made (i.e., no pool contains 2 elements), or to a situation where a combination must be made (i.e., there is a pool which contains 2 elements). There are therefore 2 n-1 + n-1 1 2 n-2 = (n + 1)2 n-2 of these conĄgurations.

In total, the Markov chain corresponding to our algorithm therefore has (n + 3)2 n-2 states. Studying the mean hitting time starting from the conĄguration where we do not have any phase vector in any of the pools would give us the exact average-time complexity of our algorithm, but unfortunately we could not manage to deal with this exponential amount of states and their intricate structure.

Our analysis. In order to avoid this exponential number of states to consider, we looked at a different algorithm which is based on the same idea but where we assume that all the calls to the oracle have been made from the outset. All that remains is to combine the phase vectors (which are taken at random, unlike in Algorithm 14). Its pseudocode is given in Algorithm 16. In order to determine the query and time complexity of this algorithm, we barely have to Ąnd what quantity of phase vectors we should give it as input. We conjecture that the number of calls to the oracle made by this algorithm is of the same order as that of Algorithm 15, which is what we are observing experimentally (experimental results are given at the end of the section).

Algorithm 16 The algorithm we study (sequential version)

Require: A set of 2 ℓ phase vectors. Ensure: ψ N/2 . 1: Classify the phase vectors in the pools P i 2: for i = 1 to n -1 do 3:

while ♣P i ♣ ≥ 2 do 4:
Pick ♣ψ a ⟩ and ♣ψ b ⟩ from P i .

5:

Combine ♣ψ a ⟩ and ♣ψ b ⟩ and insert the result in the appropriate pool 6: if P n ̸ = ∅ then return ψ N/2 7: return "The algorithm failed".

Algorithm 15 is essentially a version that makes calls to the oracle as it goes along and so recycles the qubits it uses, whereas Algorithm 16 stores all the states it needs as input. The latter then processes the phase vectors sequentially. It Ąrst sorts them according to the pool to which they belong, then runs through these pools in order, since combining elements from the i-th pool produces elements that belong exclusively to pools i + 1 to n, as shown in Lemma 6.2. In this way, the algorithm gradually concentrates the phase vectors in the last pools. Indeed, on the i-th iteration of the For loop, at most one element (which could not have been matched) remains in pools P 1 through P i , while the pool P i+1 will contain a quantity of phase vectors denoted Q i+1 . This must be greater than or equal to 2 in order to form at least one pair of phase vectors, which can be combined to obtain a more interesting pair. Finally, for the algorithm to succeed, we must have Q n equal to at least 1 at the end.

We can also write this algorithm in parallel mode, which will be even more easier to study: instead of acting sequentially by processing the pools one after the other, we can process all the pools P i at once and place the results in a separate pool, then classify these new states in the pools P i again and iterate the process. This is the method used in Algorithm 17.

Algorithm 17 The algorithm we study (parallel version)

Require: A pool P of 2 ℓ phase vectors. Ensure: ψ N/2 .

1: for t = 1 to n -1 do 2:
Take the phase vectors from P and classify them in the pools P i 3:

for i = 1 to n -1 do 4: while ♣P i ♣ ≥ 2 do 5:
Pick ♣ψ a ⟩ and ♣ψ b ⟩ from P i .

6:

Combine ♣ψ a ⟩ and ♣ψ b ⟩ and insert the result in P 7: if P n ̸ = ∅ then return ψ N/2 8: return "The algorithm failed".

In order to study the average-case complexity of Algorithm 17, we construct a vector b corresponding to the initial distribution of phase vectors, i.e., whose i-th entry is equal to the expected number of phase vectors that will belong to P i at the beginning of the algorithm. We thus have from Lemma 6.1:

b i def = 2 ℓ P O [i] = 2 ℓ-i .
We also deĄne the transition matrix A corresponding to the action on the vector b of one iteration of the main For loop, from the distribution given in Lemma 6.2. Namely, combining two elements of P i will produce one element of P j with probability P j [i], so we let:

A i,j def =    P j [i] if i = n 1 2 P j [i]
otherwise. The halving factor comes from the fact that we take two elements to produce one, except when we are already in the pool of solutions. It turns out that the matrix A has a particular form, speciĄed in the following lemma. Lemma 6.3. A is a square matrix of order n such that

A = N 0 T u 1 (6.2)
where 0 = (0, . . . , 0) is a vector of size n -1, u is a positive vector of size n -1 and N is a nilpotent matrix of order and index n -1 (the smallest power of N yielding the zero matrix) whose elements under the diagonal are nonnegative and zero over the diagonal.

Proof. This directly follows from the deĄnition of A and Lemma 6.2.

Analyzing the average-case complexity of Algorithm 17 then boils down to studying the powers of A, since one iteration of the main For loop corresponds to applying the matrix A on b, two iterations to applying A 2 , and so on. It will thus be crucial to have a closed-form expression for powers of the matrix A, which is provided in the following lemma.

Lemma 6.4. Let p be any positive integer, then

A p = N p 0 T u p-1 ℓ=0 N ℓ  1
Proof. This is trivially true for p = 1. Assume it holds for some Ąxed p. Then we have

A p A = N p 0 T u p-1 ℓ=0 N ℓ  1 N 0 T u 1 = N p+1 0 T u + u p ℓ=1 N ℓ  1
concluding the proof by induction.

Recall that our goal is to determine the quantities Q i . Since solutions can accumulate in the last pool P n , all we have to do is look at the number of elements in P n at the end of the algorithm to obtain Q n . However, for any other pool P i , it is necessary to accumulate the number of elements that go through P i over the iterations of the main For loop in order to Ąnd back the value of Q i .

Actually, if we denote

Q the vector (Q 1 , . . . , Q n ) with Q i def = E [Q i ], and if we let Q def = n-2
p=0 N p , we have the following lemma.

Lemma 6.5. We have

Q def = Qb T where Q = Q 0 T uQ 1
Now, in order to analyze the average-case complexity of Algorithm 17, it remains to determine Q and make sure to choose a value for ℓ such that Q i is greater or equal to 2 for every i ∈ 1, n -1 and greater or equal to 1 when i = n.

Thanks to Lemma 6.5, we can easily Ąnd the average-case complexity of Algorithm 17 and thus prove the following theorem. # i f t h e t a r g e t has been produced , r e t u r n i t break # e l s e , q u e r y t h e o r a c l e k = r a n d i n t ( 0 ,N-1) n _ q u e r i e s += 1 while k == 0 : k = r a n d i n t ( 0 ,N-1) n _ q u e r i e s += 1 pool_idx

= int ( l o g 2 ( k & -k ) ) p o o l s [ pool_idx ] . append ( k )
return n _ q u e r i e s choosing uniformly at random between the sum and the difference when combining two phase vectors. The code is given hereafter.

We then ran this implementation a thousand times on small values of n (from 5 up to 35) and computed the mean query complexity. The results are given in Table 6.1. They are indeed of the order of 2 (2-log 3)n , and more precisely they appear to be very close to 2 (2-log 3)n+1 . Note that the time complexity is necessarily of the same order as the query complexity. There cannot be more than n combination steps before calling the oracle a new time, so in the worst case the time complexity is n times the query complexity.

A Space-Interpolation Algorithm

We have just described an algorithm using at most n qubits, which we have matched to pools of size 2 i , for i ranging from 0 to n -1. A very simple observation is that if we have more qubits, we can subdivide these pools. We will do this uniformly, in order to keep the size of the subpools equal to a power of 2, and at least 2, so we can have two different elements to combine when falling in such a subpool. We introduce a parameter m such that each pool will have 2 m subpools, with the exception of those that are too small which will be divided in subpools of 2 elements.

Formally, for any i ∈ 1, n -1 , we will divide P i in 2 min (n-i-1,m) subpools, where m will be chosen such that the total number of subpools will be as close to the number X of qubits we have at our disposal as possible, i.e., m is the greatest integer such that

X ≥ 1 + n-1 i=1 φ(i) = 1 + n-m-2 i=1 2 m + n-1 i=n-m-1 2 n-i-1 = 1 + (n -m -2)2 m + 2 m+1 -1 = (n -m)2 m
We will assume that m > 0 since the case m = 0 corresponds to the algorithm without subpools, i.e., the algorithm described in the previous section. We will place a couple (k, ♣ψ k ⟩) in a subpool denoted by P (i,v i ) , where i ∈ 1, n and v i ∈ 0, φ(i) -1 , in the following manner: while for all (i, v i ), P (i,v i ) < 2 do 3:

P (i,v i ) ←-(k, ♣ψ k ⟩) if k ∈ D (i,v i ) where D (i,v i ) def = (2(φ(i)α + v i ) + 1)2 i , α ∈ 0, 2 n-i φ(i) -1 and φ(i) def = 2 min (n-i-1,m)
Call O and insert the result in the appropriate pool.

4:

Let (i, v i ) be such that P (i,v i ) = 2.

5:

Pick ♣ψ a ⟩ and ♣ψ b ⟩ from P (i,v i ) .

6:

Combine ♣ψ a ⟩ and ♣ψ b ⟩ and insert the result in the appropriate pool 7: until there is a state in the bin P (n,0)

8: return ψ N/2 .
As for the previous section, we give the probability distributions corresponding to the oracle outputs and the combination process.

Probability distributions. The probability distribution of elements picked uniformly at random from the oracle is given by the following lemma. Lemma 6.9 (Initial distribution). Let i ∈ 1, n and v i ∈ 0, φ(i) -1 . The probability that the oracle O yields a phase vector belonging to the subpool P (i,v i ) , denoted by

P O [(i, v i )], is P O [(i, v i )] def = 1 φ(i)2 i
Proof. This is straightforward since

P O [(i, v i )] = ♣D (i,v i ) ♣ ♣Z N ♣ = 2 n-i φ(i) 2 n .
The probability distribution of elements obtained from combining two phase vectors of a same subpool is given by the following lemma.

Lemma 6.10 (Combination distribution (subpools)). Let i ∈ 1, n -1 and v i ∈ 0, φ(i) -1 . Let j ∈ i + 1, n and w j ∈ 0, φ(j) -1 . The probability that combining two phase vectors from P (i,v i ) yields a phase vector from P (j,w j ) , denoted by P (i,v i ) [(j, w j )], is

• when i = n -1:

P (i,v i ) [(n, 0)] = 1 2
• when n -(m + 1) ≤ i < n -1:

P (i,v i ) [(j, w j )] =    1 4
if (j, w j ) = (n, 0)

1 2 if (j, w j ) = (i + 1, v i mod φ(i + 1))

• when i < n -(m + 1):

P (i,v i ) [(j, w j )] =          1 4
if (j, w j ) = (i + 1, v i mod φ(i + 1))

1 4
if (j, w j ) = (i + 1, (v i + 2 m-1 ) mod φ(i + 1))

2 m+i-j-1 φ(j)
for w j ∈ 0, φ(j) -1 for j ∈ i + m + 1, n .

When j ∈ 1, i , the probability is always zero.

Please note that v i depends on i and w j depends on j, but also on i and v i . For the sake of clarity, we dropped the latter from the index of w.

Proof. Let P + (i,v i ) [(j, w j )] (resp. P - (i,v i ) [(j, w j )]) be the probability for two phase vectors from P (i,v i ) to produce one from P (j,w j ) when combined and their sum (resp. difference) is obtained. Let k ∈ D (i,v i ) . There exists α ∈ 0, 2 n-i φ(i) -1 such that k = (2(φ(i)α + v i ) + 1)2 i .

We Ąrst look for the proportion P + (i,v i ) [(j, w j )] of ℓ ∈ D (i,v i ) , which we can write for some β ∈ 0, 2 n-i φ(i) -1 as ℓ = (2(φ(i)β + v i ) + 1)2 i , such that k + ℓ = (φ(i)(α + β) + 2v i + 1)2 i+1 ∈ D (j,w j ) , i.e., there must exist γ ∈ 0, 2 n-j φ(j) -1 such that (φ(i)(α + β) + 2v i + 1)2 i+1 = (2(φ(j)γ + w j ) + 1)2 j . (6.3) Necessarily, j ≥ i+1. We have three cases to consider. Recall that φ(i) def = 2 min (n-(i+1),m) .

• When i < n -(m + 1), we have φ(i) = 2 m . Equation 6.3 becomes 2 m (α + β) + 2v i + 1 = (2w j + 1)2 j-(i+1) mod φ(j)2 j-i

Necessarily, 2 j-(i+1) has to be odd, so j = i + 1. The condition can then be simpliĄed to 2 m-1 (α + β) + v i = w j mod φ(j)2 j-i .

We deduce that P + (i,v i ) [(j, v i mod φ(i + 1))] = 1 2 and P + (i,v i ) (j, v i + 2 m-1 mod φ(i + 1)) = 1 2 .

• When n -(m + 1) ≤ i < n -1, we have φ(i) = 2 n-(i+1) and φ(j) = 2 n-(j+1) . Equation 6.3 becomes (α + β)2 n + v i 2 i+2 + 2 i+1 = γ2 n + w j 2 j+1 + 2 j

Necessarily j = i + 1 and it follows that

P + (i,v i ) [(i + 1, v i )] = 1.
• When i = n-1, j can only be equal to n and we have φ(i) = φ(j) = 1. Equation 6.3 becomes α + β + 2v i + 1 = 2γ + 2w j + 1 implying that α + β = 0 mod 2. It follows that P + (n-1,0) [(n, 0)] = 1 2 .

We use the same reasoning for the difference, P - (i,v i ) [(j, w j )] being the proportion of ℓ ∈ D (i,v i ) such that ♣kℓ♣ = ♣αβ♣φ(i)2 i+1 ∈ D (j,w j ) , i.e., there must exist γ ∈ 0, 2 n-j φ(j) -1 such that ♣αβ♣φ(i)2 i+1 = (2(φ(j)γ + w j ) + 1)2 j . (6.4) Necessarily, j ≥ i + 1. Now we have three cases to consider.

• When i < n -(m + 1), we have φ(i) = 2 m . Equation 6.4 becomes ♣αβ♣2 m = (2w j + 1)2 j-(i+1) + γφ(j)2 j-i Necessarily, j ≥ i + m + 1. We can rewrite the condition as ♣αβ♣ = (2w j + 1)2 j-m-(i+1) mod φ(j)2 j-m-i

It follows that P - (i,v i ) [(j, w j )] = 2 m+i-j φ(j)

• When n -(m + 1) ≤ i < n -1, we have φ(i) = 2 n-(i+1) and φ(j) = 2 n-(j+1) . Equation 6.4 becomes ♣αβ♣2 n = (2w j + 1)2 j + γ2 n implying that j = n. It follows that

P - (i,v i ) [(n, 0)] = 1 2 .
The case i = n -1 is similar and leads to the same result.

• When i = n-1, j can only be equal to n and we have φ(i) = φ(j) = 1. Equation 6.4 becomes ♣αβ♣ = 2γ + 2w j + 1 implying that α + β = 1 mod 2. It follows that

P - (n-1,0) [(n, 0)] = 1 2 .
By deĄnition, the overall probability P (i,v i ) [(j, w j )] is

P (i,v i ) [(j, w j )] = 1 2 P + (i,v i ) [(j, w j )] + P - (i,v i ) [(j, w j )]
 which allows us to conclude the proof.

On the Markov chain of Algorithm 18. As we said in the previous section, the right way to study this algorithm would also be to analyse the corresponding Markov chain. Once again, this chain has an exponential number of states, which makes it difficult to study. Indeed, we have:

• the conĄgurations were a solution have been found, i.e., there is 1 element in P (n,0) , coming either from the oracle (which means before calling the oracle, there was no subpool with 2 elements) or either from a combination (meaning that 2 elements from a subpool were used to produce the solution, leaving no subpool with 2 elements) are 2 (n-m)2 m -1 of them,

• the conĄgurations for which no solution has been found, corresponding either to a situation where a query must be made (i.e., no subpool contains 2 elements), or to a situation where a combination must be made (i.e., there is a subpool which contains 2 elements). There are therefore 2 (n-m)2 m -1 + (n-m)2 m -1 1 2 (n-m)2 m -2 = ((nm)2 m + 1) 2 (n-m)2 m -2 of these conĄgurations.

In total, the Markov chain corresponding to our algorithm has ((nm)2 m + 3) 2 (n-m)2 m -2 states. This is a prohibitive quantity, even though studying the mean hitting time of this Markov chain would give us the exact average complexity of our algorithm.

Our analysis. The algorithm we will actually study, in the same way as we did in the previous section, is Algorithm 19.

Algorithm 19

The algorithm we study (parallel version)

Require: A pool P of 2 ℓ phase vectors. Ensure: ψ N/2 .

1: for t = 1 to n -1 do 2:

Take the phase vectors from P and classify them in the subpools P (i,v i )

3:

for i = 1 to n -1 do 4:

while P (i,v i ) ≥ 2 do 5:

Pick ♣ψ a ⟩ and ♣ψ b ⟩ from P (i,v i ) .

6:

Combine ♣ψ a ⟩ and ♣ψ b ⟩ and insert the result in P 7: if P (n,0) ̸ = ∅ then return ψ N/2 8: return "The algorithm failed".

We construct a vector b corresponding to the initial distribution of phase vectors, i.e., whose (i, v i )-th entry is equal to the expected number of phase vectors that will belong to P (i,v i ) at the beginning of the algorithm. We thus have from Lemma 6.9:

b(i,v) = 2 ℓ P O [(i, * )] = 2 ℓ-i φ(i)
We also deĄne the transition matrix à corresponding to the action on average on the vector b of one iteration of the main For loop, from the distribution given in Lemma 6.10. Namely, combining two elements of P (i,v i ) will produce one element of P (j,w j ) with probability P (j,w j ) [(i, v i )], so we let: Ã(i,v i ),(j,w j ) =    P (j,w j ) [(i, v i )] if i = n 1 2 P (j,w j ) [(i, v i )] otherwise.

The halving factor comes from the fact that we take two elements to produce one, except when we are already in the pool of solutions.

We can actually simplify a great deal this analysis by considering the combination distribution from pool to pool rather than from subpool to subpool. Lemma 6.11. Let t ∈ 0, n -1 . We have for any i ∈ 1, n and v i , v ′ i ∈ 0, φ(i) -1 :

( Ãt b T ) (i,v i ) = ( Ãt b T ) (i,v ′ i ) .
Proof. This is true by deĄnition of b for t = 0 (since b (i,v i ) does not depend on v i ). Now assume this is true for some t ∈ 0, n -2 . Using Lemma 6.10 and its notation, we want to prove that for any j ∈ 1, n and w j , w ′ j ∈ 0, φ(j) -1 :

( Ãt+1 b T ) (j,w j ) = ( Ãt+1 b T ) (j,w ′ j ) . We take back the different conĄgurations of Lemma 6.10 for i:

• If i = n -1, we have only one subpool since j = n (i.e., w j = w ′ j = 0), so the property trivially holds.

• If n -(m + 1) ≤ i < n -1, the case j = n is once again trivial. For the other case, we Ąrst note that φ(i) = 2 n-i-1 and φ(i + 1) = 2 n-i-2 . Thus, any subpool indexed by (j, w j ) with j = i + 1 and w j ∈ 0, φ(i + 1) -1 has exactly two preimages by Ã: those are (i, w j ) and (i, w j + 2 n-i-2 ), and the probability to go from one of the two to the considered image is constant. Therefore, the property holds.

• If i < n -(m + 1), we have φ(i) = φ(i + 1) = 2 m . Any subpool indexed by (j, w j ) with j = i + 1 and w j ∈ 0, φ(i + 1) -1 has once again exactly two preimages by Ã: those are (i, w j ) and (i, w j + 2 m-1 mod 2 m ), and the probability to go from one of the two to the considered image is once again constant. For the remaining case, we can see that every subpool (i, v i ) has for images every subpool indexed by (j, w j ) for w j ∈ 0, φ(j) -1 , for j ∈ i + m + 1, n with a probability that does not depend on v i nor w j , meaning that every subpool of a same pool will be attained with the same probability, i.e., the property holds.

It follows from this important lemma that we can in some sense merge in our analysis the subpools of each pool. This allows us to once again work with a transition matrix between the n pools, instead of working with a transition matrix between the (nm)2 m subpools. Namely, we give in the following lemma the transition probabilities between pools.

Corollary 6.1 (Combination distribution (pools)). Let i ∈ 1, n -1 and j ∈ i + 1, n .

The probability that combining two phase vectors from P (i, * ) yields a phase vector from P (j, * ) (where the asterisk means that it can be any of the subdivisions of the considered pool), denoted by P i [j], is

• when i = n -1:

P i [n] = 1 2
• when n -(m + 1) ≤ i < n -1:

P i [j] =    1 4 if j = n 1 2 if j = i + 1

A Space-Interpolation Algorithm

123

• when i < n -(m + 1):

P i [j] =    1 2 if j = i + 1
2 m+i-j-1 for j ∈ i + m + 1, n .

When j ∈ 1, i , the probability is always zero.

Proof. We simply take back the probability distribution of Lemma 6.10 and forget about the subpools indexes. When i < n -(m + 1), we merge the 1/4 probabilities of falling into P (i+1,v mod φ(i+1)) and into P (i+1,(v+2 m-1 ) mod φ(i+1)) : we simply have a 1/2 probability of falling into P (i, * ) . The same applies when j ∈ i + m + 1, n : we sum every probability to fall into P (j, * ) , i.e., we sum φ(j) times 2 m+i-j-1 φ(j)

, leading to a probability of 2 m+i-j-1 to go from P (i, * ) to P (j, * ) .

We can then take back our method of analysis and deĄne a new transition matrix from the combination distribution we just gave in Corollary 6.1. Namely, we let, as we did in the previous section, for i, j ∈ 1, n :

A i,j def =    P j [i] if i = n 1 2 P j [i] otherwise.
In the exact same way, we deĄne from the probabilities of getting an element in P (i, * ) when calling the oracle a vector b as follows:

b i def = 2 ℓ φ(i)P O [(i, * )] = 2 ℓ-i
It turns out that the matrix A has the same form as in Lemma 6.3. We can thus analyze Algorithm 19 as we did for Algorithm 17. Using the same notation, we want to determine Q (as deĄned in Lemma 6.5 and make sure to choose a value for ℓ such that Q i is greater or equal to 2 for every i ∈ 1, n -1 and greater or equal to 1 when i = n.

In the end, we will be able to give a loose estimate of the average-case complexity of Algorithm 19, which is stated in the following conjecture.  time with the same amount of queries and qubits.

The O 2 log 3 n m+1 +2m  for the time complexity seems actually to be a very rough upper bound on the actual complexity of the algorithm, as we will see in the last subsection, where we will give experimental results. For now on, we proceed in the same way as for the analysis of the n-qubits algorithm: we take a closer look at Q and uQ. and prove that this bound holds for α + 1. We have 2 n-α(m+1)-i-3 σ j ≥ 2 -α(m+1)-3 + α a=1 j∈Ia

2 n-α(m+1)-j-3 σ n-a(m+1)

≥ 2 -α(m+1)-3 + α a=1 j∈Ia

2 n-α(m+1)-j-4 3 a = 2 -α(m+1)-3 + 2 m+1 -1 2 m+4 α a=1 2 (a-α)(m+1) 3 a = 2 -α(m+1)-3 + 2 m+1 -1 2 m+1 -3 2 m+1 -3 α 2 -(α-1)(m+1) 3 α 2 m+4 ≥ 2 -α(m+1)-3 + 1 8 × 3 α -2 -α(m+1)-3 = 1 8 × 3 α

We obtain

σ n-(α+1)(m+1) ≥ 1 2 × 3 α+1 .
We conclude the proof by induction, the upper bound being provable in the exact same way.

From this lemma, we can now give an asymptotic expression for Q n . Lemma 6.14. We asymptotically have

Q n = Θ 3 -⌈ n m+1 ⌉  .
leading us to assert that this formula is a very rough upper bound of the actual query complexity of our algorithm.

Having the entire vector Q would allow us to reĄne the value of ℓ and obtain one sufficient for Algorithm 18 to succeed in producing a solution. It seems likely that we would obtain an expression of the form cst 1 n m+1 + cst 2 m for ℓ (where cst 1 and cst 2 are constants to determine). We could then, by equating the two terms, determine the optimal value for m leading to an algorithm with the lowest complexity in time and queries (observed as the minimum in Figure 6.2). Finally, we could of course compare our algorithm with those of Kuperberg.

Conclusion

As we have just seen, there is still room for precise analysis of the proposed algorithm. The method used here might not be the most suitable, and even if we were to carry out the calculations to the end, we might not obtain a result corresponding to what we observe experimentally. In fact, the right way to study our algorithm would be to analyse the corresponding Markov chain and its mean hitting time.

We also propose a variant of our algorithm that is a priori more efficient. The only difference is in the way the pools are deĄned. Although it seems more promising than the one presented above, according to the practical experiments we have carried out, it would also involve the study of the underlying Markov chain, or the same kind of process as the one we have used here, only more complicated (in particular, the involved matrix A does not contain a nilpotent matrix, which made things easier for us in our study). The idea is to put phase vectors whose associated values are close in Z N into the same pool instead of doing it according to their least signiĄcant bits. More precisely, we deĄne the pools as follows: a couple (k, ♣ψ k ⟩) generated by the oracle will be placed in the i-th pool, denoted by P i if k is in between 2 i and 2 i+1 , more precisely:

P i ←-(k, ♣ψ k ⟩) if k ∈ D i where ∀i ∈ 0, n -1 , D i def = [ 2 i , 2 i+1 ) .
In the same way as we did previously in this chapter, these pools might actually be subdivised in smaller subpools depending on the value m derived from the number of qubits X we have at our disposition. Namely, we will place a couple (k, ♣ψ k ⟩) in a subpool denoted by P (i,v i ) , where i ∈ 0, n -1 and v i ∈ 0, 2 min (i-1,m) -1 , in the following manner:

P (i,v i ) ←-(k, ♣ψ k ⟩) if k ∈ D (i,v i )
where

D (i,v i ) def
= [ 2 i + v i 2 i-min (i-1,m) , 2 i + (v i + 1)2 i-min (i-1,m) ) .

Note that with this approach, the solution state that we wish to construct is ♣ψ 1 ⟩ instead of ψ N/2 and that it will therefore be found in P 0 . Note also that we can save a few qubits compared with the previous approach in the following way: when the oracle generates a state with k ∈ N/2, N -1 , we can bring it back into 0, N/2 -1 at a lower cost, by combining ♣ψ k ⟩ with ♣ψ N ⟩ (which is equal to ♣+⟩). One time out of two, this will give back ♣ψ k ⟩, in which case you will have to repeat the process until you obtain ♣ψ N -k ⟩. Finally, this trick allows us to deal with any value of N very easily, not only powers of 2.

Conclusion and Perspectives

Conclusion In this thesis, we have seen two new concrete applications of the Quantum Fourier Sampling technique, Ąrstly in complexity theory and secondly in algorithms.

In both cases, the implications for cryptography are direct, reminding us of the major importance of studying this method in cryptanalysis, well beyond the famous Shor algorithm. In this respect, we recalled in Chapter 1 the application of Quantum Fourier Sampling in the more general context of solving the HSP in any abelian group.

These fundamental reminders, together with the elementary but no less necessary reminders of code-based cryptography given in Chapter 2, enabled us to give in Chapter 3 a quantum reduction of the problem of Ąnding a low-weight codeword in a code to the problem of decoding in its dual code. This result is an important advance in complexity theory, since no reduction in this direction existed between these problems, whether classical or quantum, and it gives us a better understanding of the links between these problems.

Quantum Fourier Sampling has also been shown to be of interest in the context of dihedral groups and not just abelian groups, as we saw in Chapter 4. We reviewed there the main algorithms that have been milestones for solving the DCP, to which the security of many cryptosystems, whether asymmetric or symmetric, can be reduced, and more generally to which many other problems, whether used in lattice-based or isogeny-based cryptography, can be reduced.

By combining the Quantum Fourier Sampling method with an idea due to Regev for solving the DCP, we have then introduced in the Chapter 5 a new kind of algorithm for solving the HSP in a dihedral group. Namely, we reduced the resolution of the DCP to that of a quantum subset-sum problem, which offers a new alternative to the two other main methods of resolution already known (direct resolution or reduction to a classical subset-sum problem). We thus obtained the Ąrst algorithm to improve over Ettinger-Hoyer algorithm in the regime of algorithms using a linear number of queries to the oracle. Finally, we also give a very natural interpolation on the number of queries between this new algorithm and KuperbergŠs second algorithm.

Finally, in Chapter 6, we give new ways of solving the HSP in a dihedral group without 133 reducing it to a subset-sum problem. In particular, we present a new algorithm that beats all previously known algorithms in terms of quantum space usage and whose time complexity is the lowest among all algorithms using a linear space. We also give an interpolation between this algorithm and, most probably, KuperbergŠs Ąrst algorithm.

Giving the complexity of this interpolation explicitly is unfortunately a difficult task and requires further work.

Perspectives

We have shown that our quantum reduction of the short codeword problem to the decoding problem is interesting when we consider the Hamming metric, but that on the contrary, with the rank metric, it operates in an area where the Ąrst problem is already easy. This is because the rank metric is much coarser than the Hamming metric. That said, there is the Lee metric, which is less coarse than the Hamming metric and is making its way into post-quantum cryptography, for which it would be interesting to investigate this reduction. Finally, although this reduction was originally studied and presented with the Euclidean metric, its full potential had not been exploited. As we saw in the Hamming metric, we had to consider going beyond d GV /2 for the decoding problem, where in the lattice setting, [START_REF] Stehlé | ŞEfficient Public Key Encryption Based on Ideal LatticesŤ[END_REF] stopped before. It would therefore be interesting to investigate this further for the Euclidean metric.

As we discussed in the last chapter, there are still a number of things to be done with our space-interpolation algorithm and one major idea to be explored. First of all, we need to reĄne the study of our algorithm so that we can obtain its complexity more precisely, and thus be able to compare it with KuperbergŠs algorithms in particular. Analysing the Markov chain corresponding to the algorithm would be optimal but appears to be a complicated task. Secondly, the idea of changing the way in which subpools are deĄned seems promising and worth looking into, but it also seems all the more difficult to study. It is, however, more intuitive and represents a genuinely new approach compared with KuperbergŠs Ąrst algorithm.

1:♣H♣ h∈H ♣y + h⟩ 3 :

 3 Prepare the uniform superposition over G × S and compute f 1 ♣G♣ x∈G ♣x⟩ ♣f (x)⟩ 2: Measure the second register and discard it 1 Apply the Fourier transform over G 1 ♣G♣♣H♣ h∈H g∈G χ y+h (g) ♣g⟩ 4: Measure the register to get a random element from H ⊥ .

Definition 2. 2 (

 2 Code rate R). Let C be an [n, k] ♣F♣ -code. The quantity R def = kn is referred to as the rate of a code.

Definition 2. 7 (

 7 Coset). Let C be an [n, k] ♣F♣ -code. The coset of a vector y ∈ F n with respect to C is deĄned as the set y + C def = ¶y + c : c ∈ C♢ .

Chapter 2 .

 2 Introduction to CBC Lemma 2.1 (Volume S r of a sphere S r ). Let n ∈ N and r be a positive integer. The volume of S r is

Proposition 3. 1 .

 1 Consider an Abelian group G and a function f : G → C that is constant on the cosets of a subgroup H of G. Then the Fourier transform f is constant on the dual subgroup H ⊥ .

  ε G def = P c,e,r (A (G, c + e, r) = e) .

def=

  P c,e measuring c ⊥ of weight u in the 2nd register of ♣ψ A ⟩ for a code choice G  Q G (u) def = P c,e measuring c ⊥ of weight u in the 2nd register of ♣ψ ideal ⟩ for a code choice G 

  will denote P G and P H respectively the probabilities in the initial model and the probabilities in the new model. The two probability distributions are closely related: the Ąrst model always produces linear codes of dimension ≤ k and codes of dimension = k with probability 1 -O q -(n-k)  whereas the second model always produces linear codes of dimension ≥ k and codes of dimension = k with probability 1 -O q -k

Figure 4 . 1 :

 41 Figure 4.1: Action of the dihedral group D 5 of order 10 on a regular pentagon. The Ąrst row shows the effect of the rotation u, the second one shows the effect of a vertical reĆection v applied to the Ąrst row. We denote by 1 the identity.

Lemma 4. 1

 1 [START_REF] Miller | The Number of Subgroups of the Dihedral Group D(n)[END_REF]). The number S N of subgroups of D N is equal to σ(N ) + τ (N ) where σ(N ) is the sum of the divisors of N and τ (N ) is the number of divisors of N :

Lemma 4. 2 (

 2 Theorem 3.1[START_REF] Conrad | Expository papers, Dihedral Groups I and II[END_REF]). The possible subgroups of D N are of the form • ⟨(x, 0)⟩ where x ∈ Z N is some divisor of N (cyclic subgroups, normal in D N ),

Figure 4 . 2 :

 42 Figure 4.2: Diagram representing the process of the Kuperberg algorithm.It is inspired by the one for the BKW algorithm which can be found in the slides[START_REF] Theiacr | A Non-heuristic Approach to Time-space Tradeoffs and Optimizations for BKW[END_REF] corresponding to the paper[START_REF] Liu | ŞA Non-heuristic Approach to Time-Space Tradeoffs and Optimizations for BKWŤ[END_REF], the only difference being in the combination step, where instead of using a vector that we XOR to all the others, we take them two by two and combine them with a CNOT and a measure. We start with a list of phase vectors whose labelsŠ most signiĄcant bit is shown in dark orange. The classiĄcation step separates these labels according to their value on their m least signiĄcant bits (each color corresponds to a different string of m bits). The combination step then allows us to construct phase vectors whose labels have their m least signiĄcant bits equal to 0, which is shown in white.

2:

  for i from 0 to n -2 do 3:while ♣P i ♣ ≥ 3 do 4:Pop ♣ψ a ⟩ and ♣ψ b ⟩ of P i such that a + b or ab has the highest possible divisibility by 2 (and is not 0)5:Combine ♣ψ a ⟩ and ♣ψ b ⟩ and insert the resulting state in the appropriate pool 6:

Theorem 4. 2 (

 2 Theorem 3.1 of[START_REF] Kuperberg | A subexponential-time quantum algorithm for the dihedral hidden subgroup problem[END_REF]). Letting m = ⌈ √ n⌉, Algorithm 5 then requires

Figure 4 . 3 :Algorithm 8

 438 Figure 4.3: Diagram showing the system of communicating vessels that enabled Regevto design a polynomial-space algorithm to solve the DCP. The dotted boxes have a capacity of ℓ phase vectors and must be Ąlled so that their contents can be used to construct a new phase vector that will (most likely) belong to the next box. The arrows represent the combination process in question. Calls are made to the oracle until our vase system has Ąlled the penultimate vase, allowing us to construct a solution state.

Theorem 4. 3 (

 3 See [Reg04a]). Letting ℓ = r + 4 = O √ n log n , Regev's algorithm then requires 2 O( √ n log n) queries and time, and polynomial (in n) space.

n

  log n classical time, and polynomial (in n) space.

Lemma 4. 5 .

 5 Kuperberg's second algorithm requires on average O √ 2n2queries and classical memory, and poly(n) qubits.

Figure

Figure

  Figure 4.4:We start from the leaves of the tree, which correspond to phase vectors of length L = 2, towards the root, where the solution vector will be found. At the i-th level of the tree, we form pairs of phase vectors of length (approximately) 2 i , which we combine two by two, to form new ones of length (approximately) 2 i+1 that will belong to the (i + 1)-th level. If we were to process this tree level by level, we would not only have to store 2 d+1 classical indices of the phase vectors, where d is the depth of the tree, but also all the phase vectors themselves. A better strategy exists, and it is a kind of reverse depth-Ąrst search. This method allows us to store at most a reasonable number of phase vectors at any time, i.e., use poly(n) qubits.

  Algorithm 12 is related to the set of b on which the quantum subset-sum solver succeeds: S Q (b • k) = b for a Ąxed k. Notation 1. Let us denote by G (k) the set of b's that are correctly found back by S Q for a given k:

  1♢ m is the set of vectors having weight αm. The basic idea of representations is to write the solution b as a sum of vectors of smaller relative weights, e.g., b = b 1 + b 2 where b

Figure 5 . 1 :

 51 Figure 5.1: Quantum HGJ algorithm. Dotted lists are search spaces (they are not stored). Bold lists are stored in QRACM. The Ąrst level uses a left-right split of vectors, without Ąltering.

Algorithm 15

 15 Our algorithmRequire: An oracle O outputting uniformly at random ♣ψ k ⟩ with k ∈ Z N . Ensure: ψ N/2 .

Listing 6. 1 :

 1 Python code for Algorithm 15 from math import l o g 2 from random import r a n d i n t def a l g o ( n ) : N = 2 * * n p o o l s = [ [ ] fo r _ in range ( n ) ] n _ q u e r i e s = 0 pool_idx = 0 while True : while len ( p o o l s [ pool_idx ] ) == 2 : # i f a p o o l has s i z e 2 , combine t h e e l e m e n t s b = ( 1 -2 * r a n d i n t ( 0 , 1 ) ) k = ( p o o l s [ pool_idx ] . pop ( ) + b * p o o l s [ pool_idx ] . pop ( ) ) % N i f k != 0 : pool_idx = int ( l o g 2 ( k & -k ) ) p o o l s [ pool_idx ] . append ( k ) i f N/2 in p o o l s [ n -1 ] :

Conjecture 6. 2 .

 2 Algorithm 19 runs in O 2 log 3 n m+1 +2m

  (α+1)(m+1) ≥ 2 -α(m+1)-3 σ n + α a=1 j∈Ia

  -Alazard, Maxime Remaud, and Jean-Pierre Tillich. ŞQuantum Reduction of Finding Short Code Vectors to the Decoding ProblemŤ.

In: IEEE transactions on Information Theory (2023) (cit. on pp. vi, x, 23). [RST23] Maxime Remaud, André Schrottenloher, and Jean-Pierre Tillich. ŞTime and Query Complexity Tradeoff for the Dihedral Coset ProblemŤ. In: PQCrypto 2023. LNCS. Springer, 2023 (cit. on pp. viii, xii, 83). [RT23] Maxime Remaud and Jean-Pierre Tillich. ŞLinear Space Algorithm for the Dihedral Coset ProblemŤ. In: (2023). Preprint (cit. on p. 103). xiii

  In the early 1990s, Simon was one of the Ąrst to present a quantum algorithm that could solve a certain problem using a polynomial number of queries where a classical algorithm would use an exponential number[START_REF] Daniel | ŞOn the Power of Quantum ComputationŤ[END_REF]. The problem in question, which is simply called "SimonŠs problem", was designed speciĄcally to show that there is a quantum advantage over classical algorithms, but it later turned out that it has practial applications in symmetric cryptography (see for example [Bon+19; CLS22]), making SimonŠs work all the more interesting. More precisely, SimonŠs problem is deĄned as follows.

2 ShorŠs Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3 Standard Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1 Simon's Algorithm Problem 1.2. Simon's problem. Let f : Z n 2 → S (where S is a finite set) be a function that hides H = ¶0, s♢ ⊆ Z n 2 . Simon's problem asks to find s given f .

  in the regime where t and k are linear in n. LPN context, no reduction is known in the other direction. These problems can be viewed in some sense as a code version of the LWE and SIS problems respectively in lattice-based cryptography[START_REF] Regev | ŞOn lattices, learning with errors, random linear codes, and cryptographyŤ[END_REF].

	improved up to the point that it beats Information Set Decoding algorithms when F = F 2
	and the rate of the code is smaller than 0.3 in [Car+23].
	Nonetheless, the decision version of this problem is NP-complete [BMT78]. In 1978,
	Robert McEliece [McE78] proposed the Ąrst public key encryption scheme based on
	coding theory and relying on the difficulty of decoding a random linear code. Many
	other public key encryption schemes [Ale03; Mis+12] and schemes such as authentication
	protocols [Ste93] or pseudorandom generators [FS96] followed, built relying on the
	hardness of this task.
	Decoding and looking for short codewords are problems that have been conjectured to be
	extremely close. They have been studied for a long time [Pra62; Ste88; Dum89; MMT11;
	Bec+12; MO15; BM18; Car+23], and for instance in the regime of parameters where the
	rate R = k n is Ąxed in (0, 1), the best algorithms for solving them are the same (namely Information Set Decoding). A reduction from decoding to the problem of Ąnding short
	codewords is known but in an LPN context [App+17; Bra+19; Yu+19; DR22]. However,
	even in an
	They almost all use the same technique,
	known as Information Set Decoding, which was introduced in 1962 by Eugene Prange
	[Pra62] in the case F = F 2 . Many improvements have later on been proposed [LB88;
	Leo88; Ste88; FS09; BLP11; MMT11; Bec+12; MO15; BM17]. On the other hand, a
	technique known as Statistical Decoding and introduced in [Jab01] was very recently

Quantum Reduction from Sampling Short Code- words to Decoding 1.1 A general result

	1	Quantum Reduction from Sampling Short Codewords to Decoding .	30
		1.1	A general result . . . . . . . . . . . . . . . . . . . . . . . . .	30
		1.2	Outline of the proof of Theorem 3.2 . . . . . . . . . . . . .	33
		1.3	Proof of Theorem 3.2 . . . . . . . . . . . . . . . . . . . . . .	37
		1.4	Application to the Hamming metric . . . . . . . . . . . . .	38
		1.5	Application to the rank metric . . . . . . . . . . . . . . . .	43
	2	About the usefulness of our reduction. . . . . . . . . . . . . . . . . .	46
		2.1	Hamming case .

. . . . . . . . . . . . . . . . . . . . . . . . 46 2.2 Rank Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3 Proof of Theorem 3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.1 Step 1: Proof of Lemma 3.1 and Lemma 3.3 . . . . . . . . . 48 3.2 Step 2: Proof of Lemma 3.4 . . . . . . . . . . . . . . . . . . 51 3.3 Step 3 : Proof of Proposition 3.3 . . . . . . . . . . . . . . . 52 4 Proof of Theorem 3.4 . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.1 Proofs of Lemma 3.12 and Lemma 3.13 . . . . . . . . . . . 55 4.2 Proofs of Lemma 3.15 and Lemma 3.16 . . . . . . . . . . . 58 1

Table 5 . 1 :

 51 Complexity exponents of algorithms for Ąnding the whole secret s.

	Algorithm Kuperberg II Regev	√	Queries 2n + 1 2 log n + 3 2 log n + 3	Classical Time √ 2n + 1 2 log n + 3 0.283n + 3	Quantum Time √ 2n + 1 2 log n + 3 2 log n + 3	Classical Space √ 2n 0.283n
	Ettinger-Hoyer		log n + 6.5	n	log n + 6.5	log n
	Alg. 12 w/ QRACM Alg. 12 w/o QRACM		log n + 3 log n + 3	0.238n + 12 < 0.232n	0.238n + 3 2 log n + 12 0.418n + 3 2 log n + 15.5	0.238n < 0.232n

Table 5 . 2 :

 52 Complexity exponents for some parameters of CSIDH, computed from the expressions given in Table5.1. The quantum space is polynomial in n.

		Algorithm	Queries	Classical Time	Quantum Time	Classical Space
	CSIDH-512 (n = 256)	Regev Alg. 12 w/ QRACM	19 11	76 73	19 85	73 61
	CSIDH-1024 (n = 512)	Regev Alg. 12 w/ QRACM	21 12	148 134	21 148	145 122
	CSIDH-1792 (n = 896)	Regev Alg. 12 w/ QRACM	23 13	257 226	23 240	254 214
	CSIDH-3072 (n = 1536)	Regev Alg. 12 w/ QRACM	25 14	438 378	25 394	435 366
	CSIDH-4096 (n = 2048)	Regev Alg. 12 w/ QRACM	25 14	583 500	25 516	580 488

  .

	Contents
	1	A Space-Efficient Algorithm . . . . . . . . . . . . . . . . . . . . . . 104
		1.1	Proof of Theorem 6.1 . . . . . . . . . . . . . . . . . . . . . . 111
		1.2	Experimental Results . . . . . . . . . . . . . . . . . . . . . . 113
	2	A Space-Interpolation Algorithm . . . . . . . . . . . . . . . . . . . . 115
		2.1	Clues for Conjecture 6.2 . . . . . . . . . . . . . . . . . . . . 124
		2.2	Experimental Results . . . . . . . . . . . . . . . . . . . . . . 129
	3	Conclusion . .
			103

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

  Note that we do not subdivide P n , since D n contains only one element, but we will refer to it as P (n,0) for notation consistency. Note also that φ(i) is deĄned such that subpools will correspond to sets of elements of size at least 2, because we want to combine different phase vectors, even in the smallest subpools.We now present our generalized algorithm for Ąnding one bit of the secret s, from phase vectors produced by an oracle O. The pseudocode for this algorithm is given by Algorithm 18. An oracle O outputting uniformly at random ♣ψ k ⟩ with k ∈ Z N .

		n Query exponent 0.415n + 1 Abs. difference
		5	2.91	3.07	0.16
		6	3.37	3.49	0.12
		7	3.75	3.9	0.15
		8	4.22	4.32	0.1
	9 Algorithm 18 Our generalized algorithm 4.68	4.73	0.05
	Require: Ensure: ψ N/2 .	10 11 12	5.08 5.5 5.94	5.15 5.56 5.98	0.07 0.06 0.04
		13	6.35	6.39	0.04
		14	6.74	6.81	0.07
		15	7.18	7.22	0.05
		16	7.61	7.64	0.03
		17	8.06	8.05	0.01
		18	8.5	8.47	0.03
		19	8.89	8.88	0.0
		20	9.26	9.3	0.04
		21	9.68	9.71	0.03
		22	10.1	10.13	0.03
		23	10.55	10.54	0.01
		24	10.94	10.96	0.02
		25	11.29	11.38	0.08
		26	11.79	11.79	0.0
		27	12.17	12.21	0.03
		28	12.63	12.62	0.01
		29	13.04	13.04	0.0
		30	13.38	13.45	0.07
		31	13.82	13.87	0.05
		32	14.25	14.28	0.03
		33	14.68	14.69	0.02
		34	15.1	15.11	0.01
		35	15.52	15.52	0.01
	Table 6.1: The mean query complexity exponent of Algorithm 15 (1000 shots) is given
	and compared to 0.415n + 1. The rounded absolute difference between both values
	(taken before rounding) is given in the last column.

1: repeat 2:

Remerciements

• quantum memory (i.e., qubits): some DCP algorithms (e.g., KuperbergŠs Ąrst algorithm [START_REF] Kuperberg | A subexponential-time quantum algorithm for the dihedral hidden subgroup problem[END_REF]) need to store many coset states, which creates a subexponential quantum memory requirement;

• classical memory with quantum random-access (QRACM): the QRACM (or qRAM, QROM in some papers) is a specialized hardware which stores classical data and accesses this data in quantum superposition. That is, we assume that given a classical memory of M bits y 0 , . . . , y M -1 , the following unitary operation:

. QRACM is a very common assumption in quantum computing, and it appears in several works on the DCP [Kup13; Pei20] but also on collision-Ąnding [START_REF] Brassard | ŞQuantum Cryptanalysis of Hash and Claw-Free FunctionsŤ[END_REF] and subset-sum algorithms [START_REF] Bonnetain | ŞImproved Classical and Quantum Algorithms for Subset-SumŤ[END_REF].

• classical memory without quantum random-access: the Access operation can be implemented in M arithmetic operations using a sequential circuit. This removes the QRACM assumption, and we fall back on the basic quantum circuit model. Some algorithms using QRACM can be re-optimized in a non-trivial way when memory access is costly, and this is the case of subset-sum [START_REF] Helm | ŞThe Power of Few Qubits and Collisions -Subset Sum Below GroverŠs BoundŤ[END_REF].

Theorem 6.1. Algorithm 17 runs in Θ 2 0.415n average-time with a similar amount of queries and qubits.

It directly follows that Ąnding the whole secret s with Algorithm 17 would all the same require Θ 2 0.415n time, space and queries.

1.1 Proof of Theorem 6.1

We start our analysis by giving an expression for the entries of a power of the nilpotent matrix N we are working with.

Lemma 6.6. Let p be a positive integer. We have for all i ∈ 1, n -1 and j ∈ 1, i -1 :

Proof. We have for any square matrix M of order n -1 and integer p greater than 1:

with k 0 = i and k p = j. When taking M = N, where N is a nilpotent matrix whose elements under the diagonal are nonnegative and zero over the diagonal, we obtain:

From Lemma 6.2, we have

so the product simpliĄes to

Thus we have

We can now give an expression for the entries of the matrix Q.

Lemma 6.7. We have for i, j ∈ 1, n :

Proof. Let i, j ∈ 1, n -1 . We have by deĄnition and Lemma 6.6:

Now, let j ∈ 1, n -1 . We have

Together with the deĄnition of Q in Lemma 6.5, we conclude the proof.

Now that we have a closed-form expression for the entries of Q and since we know b, we can look at Q. Lemma 6.8. Let i ∈ 1, n . We have

Proof. For any i ∈ 1, n , we have by Lemma 6.5:

2 j by Lemma 6.7

Concluding the proof.

Proof of Theorem 6.1. We want at least 2 phase vectors in each pool except in the last one, where we can have just one phase vector, i.e., one solution. In other words, we want:

)n satisĄes all these inequations, meaning that we should have an input set of approximately 2 0.415n phase vectors in order for Algorithm 17 to output the state ψ N/2 on expectation.

Experimental Results

From the study of Algorithm 17 in this section, we conjecture that the complexity of our algorithm is of the same order. SpeciĄcally, Conjecture 6.1. Using Algorithm 15, one can solve the DCP in Θ 2 0.415n time and queries, with at most n qubits.

We implemented the classical part of Algorithm 15 in Python, picking uniformly at random numbers in Z N (instead of generating them with the quantum oracle) and

Clues for Conjecture 6.2

We are soon faced with a problem in carrying out our study: looking at the powers of the nilpotent matrix N is much less straightforward than in the case where m = 0. However, determining Q, the sum of the powers of N, is essential if we want to obtain Q. We manage hereafter to obtain the Ąrst Q i values for i ranging from 1 to m + 1 and also to give a good estimate for Q n . Unfortunately, all the other Q i values remain unknown. In the end, we are therefore forced to give a very large estimate for ℓ based on the values we know, but which should be much lower when our study is complete and the Q vector is fully known.

Estimate of Q n . We will use the fact that (uQ) j = A n-1 n,j to estimate the value of Q n . We Ąrst show that the values (uQ) j are recursively deĄned and let σ j def = (uQ) j . Lemma 6.12. We have:

Proof. We have

Taking p to be greater than n, we get p > p -1 ≥ n -1. Since n -1 is the index of the nilpotent matrix N, it follows that

Now, the matrix N being a lower triangular matrix whose diagonal is zero, we have

Plugging the probability distributions given by Corollary 6.1 in this equation, we conclude the proof.

From this lemma, it is then possible to give a closed-form expression for some of the entries (uQ) j , namely, when j ∈ nm -1, n -1 .

Corollary 6.2. Let j ∈ nm -1, n -1 . We have:

Proof. The case j = n -1 is readily veriĄed. Now for j ∈ nm -1, n -2 , we have from Lemma 6.12:

Unfortunately, giving a closed-form expression for the entries σ j becomes increasingly difficult as j decreases. As can be seen in Lemma 6.12, when j < nm -2, σ j depends on the σ i Šs with i ≥ j + m + 1. It follows that we can theoretically give a closed-form expression in packets of m + 1 consecutive σ j , but it is simpler to give lower and upper bounds for these. We now give a tight interval in which σ j can be found for any j. Lemma 6.13. Let α ∈ 0, n m . For j ∈ nα(m + 1), nα(m + 1) + m def = I α , we have:

Proof. Only j = n belongs to I 0 and since σ n = 1, the bound is veriĄed for α = 0. By Corollary 6.2, we have for j ∈ I 1 = n -(m + 1), n -1 :

so the bound is also veriĄed for α = 1.

From Lemma 6.12, we note that σ j < σ j+1 . Thus, for α ∈ 2, n m , we actually have for all j ∈ I α that σ j ≥ σ n-α(m+1) .

(6.5)

We now assume that

We now use the upper bound of Lemma 6.13 to obtain:

For n and m big enough, we have

Using the lower bound of Lemma 6.13 instead of the upper bound, we can also show that

Now that we have an estimate for (uQ♣1) • b, i.e. for Q n , we look at the case where i < n.

Value of Q i for i ∈ 1, m + 1 . It turns out that we can easily give an expression for Q i = (Q i ♣0) • b for i ∈ 1, m + 1 (where Q i denotes the i-th row of the matrix Q), from the probability distribution of the subpools. In this aim, we assume that m < n-1 2 (when m is greater, the algorithm uses in any case an exponential amount of qubits, which is not really appealing), meaning that m < n -(m + 1). It follows that for i ∈ 1, m + 1 , φ(i) = 2 m . We then have a closed-form expression for Q i . Lemma 6.15. Let i ∈ 1, m + 1 . We have

Proof. We take back the probability distributions of Lemma 6.9 and Lemma 6.10. In any subpool of the Ąrst pool, we have a proportion of 1 2φ(1) = 1 2 m+1 phase vectors, so the equality is veriĄed for i = 1. Now we assume that it holds for a given value i ∈ 1, m + 1 . Then, for the i + 1-th pool, we initially have a proportion of 1 2 i+1 φ(i+1) phase vectors and we have to add a quarter of the proportion of phase vectors we had in the i-th pool, i.e.,

concluding the proof by induction.

The equality given in Lemma 6.15 does not hold anymore for i greater than m + 1, since we have to take into consideration the probability to come from the i -(m + 1)-th pool to the i-th one (see Lemma 6.10).

Conclusion.

We do not currently have an expression for Q i for i from m + 2 to n -1.

We just use the ones we do have to conclude. So we want at least 2 phase vectors in each subpool except in the last one, where we can have just one phase vector, i.e., one solution. In other words, we want from Lemma 6.14 and Lemma 6.15:

Taking ℓ = log (3) n m+1 + 2m largely satisĄes all these inequations. Once again, some inequations are missing, for i ∈ m + 2, n -1 . We will see in the next subsection that a much smaller value for ℓ should be enough, but we do not have for the moment any more precise value.