Philippe Aram Claude

Tobias Fritz

Belén Sainz

Marc Kaplan

María Naya-Plasencia

Gaëtan Leurent

Pierre Tillich

Gilles Zémor

Nicolas Delfosse

Benjamin Audoux

Anthony Leverrier

Philippe Grangier

• Procédé de distribution quantique de clés à † variables continues

In the spirit of this document, let me be brief and to the point. Let me first thank Toni Acín, Renato Renner for giving me the opportunity to spend very fruitful years as a postdoc in their respective group, and Anne Canteaut for hosting me and my research at Inria for the last 5 years (and hopefully for many more years to come). Let

Introduction 1

1 Continuous-variable quantum cryptography 5

2 Quantum non-locality and cryptography 3 Towards quantum fault-tolerance

Conclusion

iii 1. la distribution quantique de clés à variables continues était déjà le sujet de ma thèse. Au cours de cette dernière, j'avais proposé de nouvelles solutions pour améliorer les performances de tels protocoles, mais j'avais malheureusement laissé en suspens la question essentielle à mon avis : celle de la sécurité de ces protocoles contre des attaques arbitraires. J'ai finalement récemment résolu cette question en introduisant une nouvelle classe d'états cohérents généralisés et en établissant une version gaussienne du théorème de de Finetti quantique.

2. l'étude des corrélations quantiques et leur application à la cryptographie. J'ai commencé à étudier ce qu'on appelle "corrélations quantiques" lors de mon séjour postdoctoral à Barcelone dans le groupe d'Antonio Acín, et j'ai poursuivi cette activité plus récemment en encadrant un étudiant de thèse, Kaushik Chakraborty, qui a travaillé sur certaines applications cryptographiques, notamment la géolocalisation et la mise en gage, en collaboration avec André Chailloux.

3. le calcul quantique. Depuis mon arrivée chez Inria, j'ai initié de nouvelles recherches plus éloignées de la cryptographie, qui se tournent davantage vers les codes correcteurs d'erreur nécessaires au calcul quantique. En particulier, j'encadre actuellement deux étudiants en thèse, Antoine Grospellier et Vivien Londe sur ce sujet.

Un point commun de ces thèmes est la volonté de protéger l'information quantique, que ce soit vis-à-vis d'un adversaire dans le contexte cryptographique ou de l'environnement quand on s'intéresse aux mécanismes de correction d'erreur nécessaires à la construction d'un ordinateur quantique universel.

Distribution quantique de clés à variables continues

La distribution quantique de clé (QKD en anglais) vise à distribuer une clé secrète à deux parties distantes qui ont accès à un canal de communication classique authentifié et à un canal quantique sur lequel on ne fait aucune hypothèse. Les protocoles les plus standards sont fondés sur l'échange d'états quantiques encodés sur des photons uniques et nécessitent d'utiliser des détecteurs de photons uniques. Une approche technologique xiii xiv CONTENTS intéressante consiste plutôt à encoder l'information sur des degrés de liberté continus correspondant aux quadratures du champ électromagnétique quantifié. Dans ce cas, les détecteurs de photons uniques peuvent être remplacés par une détection cohérente, qui peut être mise en oeuvre avec des équipements relativement standard en telecom. La simplicité de cette technologie a toutefois un prix, à savoir une analyse de sécurité nettement plus difficile pour ces protocoles à variables continues. Plus précisément, un protocole de QKD à variables continues est formellement décrit par un canal quantique agissant sur un espace de Fock. Le fait qu'un espace de Fock soit espace de Hilbert de dimension infinie est à l'origine de nombreuses complications mathématiques qui ne peuvent pas être adressées avec les outils développés pour étudier les protocoles en dimension finie.

Dans le premier chapitre de ce manuscrit, je décris un tel protocole de QKD à variables continues, précise les définitions de sécurité pour les protocoles de QKD et présente les principaux outils que j'ai développés pour établir la sécurité de ce protocole particulier. En particulier, j'explique comment exploiter les symétries spécifiques du protocole dans l'espace des phases afin de procéder à la tomographie des états quantiques pertinents en dimension infinie [START_REF] Leverrier | Composable security proof for continuous-variable quantum key distribution with coherent states[END_REF]. Puis je démontre une version gaussienne du théorème de de Finetti quantique, qui permet, en le combinant à un test d'énergie initialement introduit dans [START_REF] Leverrier | Security of continuous-variable quantum key distribution against general attacks[END_REF], de réduire l'étude de la sécurité du protocole contre des attaques générales à sa sécurité contre une famille restreinte d'attaques appélées "attaques collectives gaussiennes" [START_REF] Leverrier | Security of continuous-variable quantum key distribution via a gaussian de finetti reduction[END_REF]. De telles attaques peuvent finalement être analysées grâce à la technique d'estimation de matrice de covariance développée dans [START_REF] Leverrier | Composable security proof for continuous-variable quantum key distribution with coherent states[END_REF].

La série de papiers [START_REF] Leverrier | Composable security proof for continuous-variable quantum key distribution with coherent states[END_REF], [START_REF] Leverrier | q) coherent states and gaussian de finetti theorems[END_REF], [START_REF] Leverrier | Security of continuous-variable quantum key distribution via a gaussian de finetti reduction[END_REF] permet ainsi d'obtenir la première preuve de sécurité d'un protocole de distribution quantique de clés à variables continues basées sur l'échange d'états cohérents.

Corrélations quantiques et leur application à la cryptographie

Le deuxième chapitre de ce manuscrit porte sur l'étude des corrélations quantique et leur application potentielle à des fins cryptographiques.

Je discute d'abord une approche combinatoire permettant d'appréhender les propriétés de telles corrélations et qui fut introduite dans un travail commun avec Tobias Fritz, Antonio Acín et Ana-Belén Sainz [START_REF] Acín | A combinatorial approach to nonlocality and contextuality[END_REF]. Cette approche a été initialement développée afin d'étudier le "principe d'orthogonalité locale", dont l'espoir était qu'il permette de retrouver les corrélations quantiques à partie d'un principe simple de théorie de l'information.

Je considère ensuite la primitive cryptographique de géolocaliation. Alors qu'il est établi que cette primitive ne peut pas être prouvée sûre au sens de la théorie de l'information, les meilleures attaques génériques connues à ce jour nécessitent des ressources en intrication totalement irréalistes. Dans un travail avec Kaushik Chakraborty, nous avons proposé une famille d'attaques efficaces fonctionnant contre une importante classe de protocoles [START_REF] Chakraborty | Practical position-based quantum cryptography[END_REF].

Une observation récente dans le domaine de la cryptographie basée sur des principes physiques est qu'il est possible d'exploiter le fait que l'information ne puisse se propager CONTENTS xv plus vite que la vitesse de la lumière pour imposer des contraintes sévères sur les actions qu'une coalition d'agents peuvent effectuer. En particulier, ce principe est suffisant pour obtenir une sécurité au sens de la théorie de l'information pour des primitives qui ne peuvent pas être montrées sûres en exploitant seulement les limitations imposées par la mécanique quantique. Dans deux papiers avec André Chailloux et Kaushik Chakraborty, nous avons étudié plus précisément une forme faible de mise en gage, ou un bit peut être mis en gage pour un temps arbitrairement long [START_REF] Chakraborty | Arbitrarily long relativistic bit commitment[END_REF], [START_REF] Chakraborty | Robust relativistic bit commitment[END_REF]. Une aplication de ce travail a été de montrer comment obtenir des preuves à divulgation nulle de connaissance pour NP qui soient sûres contre des attaques quantiques [START_REF] Chailloux | Relativistic (or 2-prover 1-round) zero-knowledge protocol for N P secure against quantum adversaries[END_REF].

Calcul quantique

Le troisième chapitre s'éloigne de la cryptographie quantique et adresse des questions de plus long terme liées à l'apparition d'ordinateurs quantiques universels. Ce chapitre est divisé en trois parties.

Je considère d'abord le "Boson Sampling", un modèle de calcul quantique non-universel, qui a attiré un intérêt considérable ces dernières années en tant qu'approche possible pour démontrer la supériorité du traitement quantique de l'information par rapport à un traitement purement classique. Mon travail effectué sur ce domaine en collaboration avec Raúl García-Patrón consiste en une analyse de l'effet des imperfections dans des circuits quantiques de Boson Sampling : plus précisément, comprendre comment des erreurs locales dans les portes optiques du circuit affectent le résultat final du calcul. L'analyse est rendue non triviale car elle fait intervenir le permanent (le cousin du déterminant, notoirement plus difficile à manipuler !) d'une grande matrice, et qu'il faut donc étudier comment les petites perturbations liées au bruit local impactent ce permanent [START_REF] Leverrier | Analysis of circuit imperfections in bosonsampling[END_REF]. La motivation de ce travail était de comprendre à quel point l'absence de mécanisme de tolérance aux fautes était préjudiciable pour le Boson Sampling.

Ensuite, je discute d'une famille de codes quantiques appelés "codes expanseurs quantiques" que nous avons introduite avec Jean-Pierre Tillich and Gilles Zémor, qui est basée sur leur construction de produit d'hypergraphes [START_REF] Tillich | Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength[END_REF], et pour laquelle nous avons analysé un algorithme de décodage efficace qui permet de corriger des erreurs adversariales dont le poids est en racine carrée de la longueur du code [START_REF] Leverrier | Quantum expander codes[END_REF]. Ces codes sont les meilleurs codes LDPC quantiques connus en termes de distance minimale et notre algorithme est optimale puisqu'il n'y a pas moyen de décoder des erreurs adversariales de poids plus élevé que la distance minimale. De tels codes LDPC avec un algorithme de décodage efficace sont un pré-requis incontournable dans l'optique de construire des ordinateurs quantiques universels de taille importante.

Je temine en mentionnant des travaux récents effectués en collaboration avec Marc Kaplan, Gaëtan Leurent et María Naya-Plasencia sur la cryptanalyse quantique de systèmes de chiffrement symétrique [START_REF] Kaplan | Breaking symmetric cryptosystems using quantum period finding[END_REF], [START_REF] Kaplan | Quantum differential and linear cryptanalysis[END_REF]. Le but de ce travail est de comprendre comment la sécurité de la cryptographie symétrique (à clé secrète) serait affectée par l'apparition d'ordinateurs quantiques universel, et de voir si la contre-mesure habituelle consistant à doubler la taille de la clé est suffisante pour parer les attaques

Introduction

This manuscript summarizes my research activity of the past 5 years, which revolves around three main themes:

1. quantum key distribution with continuous variables, 2. quantum correlations and their use for cryptography, 3. quantum computation.

Quantum key distribution with continuous variables

Quantum key distribution (QKD) aims at distributing secret keys to two distant parties who have access to an authenticated classical channel, and an untrusted quantum channel. The standard protocols are based on the exchange of single-photon states between the two parties, and require the receiver to use single-photon counters. A technologically appealing alternative is encode the information on the continuous degrees of freedom corresponding to the quadratures of the quantized electromagnetic field. In that case, single-photon detectors can be replaced by coherent detection, relying on standard telecommunication equipment. This technological simplicity comes at a price however, namely that of of more mathematically involved security analysis of the QKD protocol. More precisely, a continuous-variable (CV) QKD protocol corresponds to a quantum channel acting on a Fock space, which is an infinite-dimensional Hilbert space. This infinite dimensionality is at the heart of many technical complications as many of the tools that have been developed to deal with qubit-based protocols break down when the dimension of the quantum systems becomes too large.

In the first chapter of this manuscript, we will describe such a CV QKD protocol, explain the security definitions for QKD protocols and present the main new tools that we have developed in order to address this question. In particular, we will start by explaining how to exploit specific symmetries of the protocol in phase-space in order to perform the tomography of the relevant infinite-dimensional quantum states [START_REF] Leverrier | Composable security proof for continuous-variable quantum key distribution with coherent states[END_REF]. Then we will derive a so-called "Gaussian de Finetti" theorem [START_REF] Leverrier | q) coherent states and gaussian de finetti theorems[END_REF], which allows us, when combined with an appropriate energy test initially introduced in [LGPRC13], to reduce the problem of proving that the protocol is secure to establishing its security against a restricted class of attacks, called Gaussian collective attacks [START_REF] Leverrier | Security of continuous-variable quantum key distribution via a gaussian de finetti reduction[END_REF]. Such 1 attacks can finally be addressed thanks to the technique for covariance matrix estimation developed in [START_REF] Leverrier | Composable security proof for continuous-variable quantum key distribution with coherent states[END_REF].

It should be noted that the series of papers [START_REF] Leverrier | Composable security proof for continuous-variable quantum key distribution with coherent states[END_REF], [START_REF] Leverrier | q) coherent states and gaussian de finetti theorems[END_REF], [START_REF] Leverrier | Security of continuous-variable quantum key distribution via a gaussian de finetti reduction[END_REF] lead to the first full security proof of CV QKD based on the exchange of coherent states.

Quantum correlations and their use for cryptography

The second chapter is concerned with the study of quantum correlations and their potential application for cryptographic purposes.

We first discuss a combinatorial approach to discuss the properties of such correlations that was introduced in a work with Tobias Fritz, Antonio Acín and Ana-Belén Sainz [START_REF] Acín | A combinatorial approach to nonlocality and contextuality[END_REF]. This approach was initially developed in order to study the "local orthogonality" principle, which was a candidate to recover quantum correlations from a simple information-based physical principle.

I will then consider the cryptographic task of position verification. While it is known that information-theoretic security cannot be achieved for this task, the current attacks require an exponential amount of resources (entanglement, for quantum protocols) which means that the protocols are hardly broken. In a work with Kaushik Chakraborty, we proposed a family of efficient attacks that apply against a large class of protocols [START_REF] Chakraborty | Practical position-based quantum cryptography[END_REF].

A recent observation in the field of physical-based cryptography is that the fact that information cannot travel faster than the speed of light puts severe constraints on the tasks that a coalition of agents can perform. In particular, this principle is sufficient to obtain information-theoretic security for cryptographic tasks that cannot be achieved with the help of quantum theory alone. In a series of papers with André Chailloux and Kaushik Chakraborty, we studied more particularly a weak form of bit commitment, where a bit can be committed for an arbitrarily long time [START_REF] Chakraborty | Arbitrarily long relativistic bit commitment[END_REF], [START_REF] Chakraborty | Robust relativistic bit commitment[END_REF]. As an application, we showed how to obtain zero-knowledge proofs for NP secure against quantum attacks [START_REF] Chailloux | Relativistic (or 2-prover 1-round) zero-knowledge protocol for N P secure against quantum adversaries[END_REF].

Quantum computation

The third chapter moves away from quantum cryptography and addresses more long term questions related to the appearance of quantum computers. The chapter is divided along three axes.

First, I will consider Boson Sampling, a non-universal model for quantum computing, which has attracted considerable interest in the past few years as a proposal to experimentally demonstrate the superiority of quantum information processing over classical processing. My work together with Raúl García-Patrón in this area consists in an analysis of the effects of imperfections in quantum circuits for Boson Sampling: more precisely, understanding how local errors in the optical gates of the circuit translate into a global error for the overall sampling task. This analysis is made nontrivial because the sampling procedure involves the permanent of a large matrix, and that the error analysis involves the study of how the permanent is modified by the small perturbation corresponding to the local noise [START_REF] Leverrier | Analysis of circuit imperfections in bosonsampling[END_REF]. The motivation behind this work was to understand whether the absence of fault-tolerance mechanisms for Boson Sampling would kill the whole approach, and the answer is apparently not.

In a second part, I will discuss a class of quantum codes named "quantum expander codes" that we introduced with Jean-Pierre Tillich and Gilles Zémor following their hypergraph-product construction [START_REF] Tillich | Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength[END_REF], and for which we proposed and analyzed an efficient decoding algorithm that can correct adversarial errors with a weight scaling like the square-root of the code length [START_REF] Leverrier | Quantum expander codes[END_REF]. These codes are the best known quantum LDPC codes in terms of minimum distance, and our algorithm is optimal since there is no hope of decoding adversarial errors beyond the minimum distance. Such quantum LDPC codes with an efficient decoding algorithm are certainly a prerequisite to building large scale quantum computers.

Finally, I will mention some recent work on the quantum cryptanalysis of symmetric cryptosystems in collaboration with Marc Kaplan, Gaëtan Leurent and María Naya-Plasencia [START_REF] Kaplan | Breaking symmetric cryptosystems using quantum period finding[END_REF], [START_REF] Kaplan | Quantum differential and linear cryptanalysis[END_REF]. The goal of this work is to understand how the security of symmetric cryptography is affected by the advent of quantum computation, and see whether the standard countermeasure consisting in doubling the key size is indeed sufficient. In our work, we make use of the main quantum algorithms and exploit variations of Grover's algorithms (quantum walks) and Shor's algorithm (for period finding) in order to develop attacks against symmetric cryptography, demonstrating that the common wisdom is a bit too simplistic and that further study of the problem is definitely called for.

Chapter 1

Theoretical tools for continuous-variable quantum cryptography

This chapter is devoted to the analysis of quantum key distribution (QKD) with continuous variables. We first introduce the concept of QKD in Section 1.1 and present the "canonical" continuous-variable QKD protocol is Section 1.2. The following three sections are devoted to the main tools we developed to address the security of this protocol: more specifically, Section 1.3 explains how to perform the tomography of the covariance matrix of an arbitrary quantum state, Section 1.4 shows how an energy test allows one to efficiently bound the dimension of the relevant Hilbert space and Section 1.5 introduces the Gaussian de Finetti reduction needed to reduce the full security proof to the analysis of Gaussian collective attacks.

Quantum key distribution: principle and security

The most advanced application of the field of quantum information is without a doubt quantum cryptography, and more precisely quantum key distribution. The goal of this cryptographic primitive is to allow two distant users who have access to an authenticated classical channel and an untrusted quantum channel to distill a secret key that can be later used to encrypt communication [START_REF] Bennett | Quantum cryptography: Public key distribution and coin tossing[END_REF], [START_REF] Ekert | Quantum cryptography based on bell's theorem[END_REF].

More formally, an Entanglement-Based (EB) QKD protocol E between Alice and Bob is a Completely-Positive Trace-Preserving (CPTP) map acting on an arbitrary input state

ρ AB where A = A 1 ⊗ • • • ⊗ A n (resp. B = B 1 ⊗ • • • ⊗ B n ) consists of
n quantum systems held by Alice (resp. by Bob) and outputs two keys K A for Alice and K B for Bob as well as some transcript classical C. The protocol is allowed to abort, in which case the keys have length 0.

Let us immediately note that for many protocols, the quantum systems A i , B i are assumed to be finite-dimensional, for instance 2-dimensional for the BB84 protocol. In con-trast, the protocols we will focus on in this chapter encode their information in the phasespace of bosonic quantum systems, meaning that A i (or B i ) is an infinite-dimensional quantum system, described by a Fock space with orthonormal basis {|k A i : k ∈ N} where the Fock state |k A i corresponds to a state with k photons in the mode A i .

Two properties are considered when assessing the security of a QKD protocol: it should be correct, meaning that both keys should be identical, and should output secret keys, appearing as uniformly random from the point of view of any adversary, possibly in possession of a quantum system E correlated with ρ AB . In practice, these features cannot be obtained exactly, and one says that the protocol E is ε-secure if it is ε-close to an ideal protocol F satisfying both properties:

1 2 E -F ≤ ε, (1.1)
where the diamond norm (also known as the completely bounded trace norm) quantifies how well one can distinguish the CPTP maps E and F. It is defined as:

∆ := sup ρ 1 =1 ∆ ⊗ id E (ρ ABE ) 1 , (1.2)
where the supremum is taken over states ρ on systems A, B and E and σ 1 := tr √ σ † σ is the trace norm. Here, the system E is arbitrary but the supremum is always attained for E ∼ = AB. The reader is referred to the monograph [START_REF] Watrous | Theory of quantum information[END_REF] for further details on these norms.

Evaluating the diamond distance

E -F = sup ρ ABE E AB ⊗ id E (ρ) ABE -F AB ⊗ id E (ρ) ABE 1 is
very challenging in general and one can use a result by Portmann and Renner [START_REF] Portmann | Cryptographic security of quantum key distribution[END_REF] to split this norm into two terms corresponding to correctness and secrecy: a protocol that is ε corr -correct and ε secr -secret is ε-secure provided that ε corr + ε secr ≤ ε where we say that the protocol is ε corr -correct if for all state ρ ABE

Pr[K A = K B ] ω ≤ ε corr and that the protocol is ε secr -secret if for all state ρ ABE Pr[K A , K B = ∅] ω • 1 2 ω K A EC -χ K A ⊗ ω EC 1 ≤ ε secr where ω K A K B EC := E AB ⊗ id E (ρ ABE )
is the output of the protocol and χ K A is the maximally mixed state over strings x with the same length as K A . The system E assumed to be in the hands of an eavesdropper can without loss of generality be assumed to purify the state ρ AB . Proving the correctness of a protocol is straightforward: it is sufficient for Alice and Bob to compute a small hash of their keys and compare them publicly to make sure that their keys coincide with high probability. The real challenge lies in establishing the secrecy of the keys. This is achieved thanks to the leftover hashing lemma [Ren08], [START_REF] Tomamichel | Leftover hashing against quantum side information[END_REF], which holds if K A is obtained by applying a random universal 2 hash function of length to the raw key X, where should be slightly smaller than the smooth minentropy of X conditioned on EC. The smooth min-entropy, H ε min (X|EC), introduced in

Ref. [START_REF] Renner | Security of quantum key distribution[END_REF], characterizes the average probability that Eve guesses X correctly using her optimal strategy with access to the correlations stored in her quantum memory E and the classical transcript C [KRS09], [START_REF] Tomamichel | A fully quantum asymptotic equipartition property[END_REF]. Applying the privacy amplification procedure to the string X yields a key of size which is ε sec -secret provided that [START_REF] Tomamichel | Tight finite-key analysis for quantum cryptography[END_REF], [START_REF] Tomamichel | Leftover hashing against quantum side information[END_REF],

[BFS11]

ε sec = min ε 1 2 2 l-H ε min (X|EC) + 2ε . (1.3)
We refer the reader to [START_REF] Renner | Security of quantum key distribution[END_REF], [START_REF] Portmann | Cryptographic security of quantum key distribution[END_REF] for a more in-depth discussion of the security of QKD.

One notes that with the formalism described so far, a QKD protocol takes as an input a (large) bipartite quantum state ρ AB , which means that the distribution of the quantum state is not considered to be part of the QKD protocol. The standard picture is that Alice and Bob have access to some untrusted quantum channel N : A → B. Alice therefore starts by preparing some entangled state Φ AA and sends the content of register A to Bob through N . One then defines ρ AB := (id A ⊗ N A→B )(Φ AA ).

A general QKD protocol will be characterized by the choice of:

• an initial state Φ AA prepared by Alice: for BB84, it is the tensor product of n Bell pairs; for continuous-variable protocols, it is the tensor product of n two-mode squeezed vacuum states |λ := 1 -|λ| 2 ∞ k=0 λ k |k, k for some fixed value λ of the squeezing satisfying |λ| < 1;

• an encoding, or equivalently a measurement map for Alice and Bob: for BB84, both Alice and Bob measure each of their n qubits randomly in the computational or Hadamard basis; for the CV protocol we will investigate, they measure their n modes with heterodyne detection (corresponding to a projection onto coherent states);

• a specific classical postprocessing procedure that helps them turn their measurement results into two secret keys K A and K B .

A crucial observation is that provided that Alice's equipment is trusted and well calibrated, the classical-quantum (cq) state that she shares with Bob after she measured register A and before Bob measures B could have been alternatively obtained by preparing an initial cq state and sending the quantum part through the quantum channel. Such a protocol is called Prepare-and-Measure (PM) and typically corresponds to what is done in practical implementations since it is much easier to prepare a cq state than an entangled state. That the security is identical in both versions is well-known and was proven in the case of Gaussian CV protocols in Ref.

[GCW + 03].
For a protocol to be interesting, security is not enough since a protocol that always aborts is secure according to the definition we gave above. One also wants a protocol that is robust, i.e., that produces large keys for passive adversaries described by a quantum channel N modeling the typical behaviour of an optical fiber for instance. One is then interested in the rate r = n where is the expected length of K A , as a function of the channel parameters such as loss and noise. In the context of finite-size analysis, it is also important to understand how fast r converges to its asymptotic value (limit n → ∞), and in particular what is the minimum block size n that gives a nonzero key length.

Before turning to the protocol itself, let us say a few words about security proofs (more detailed references are [SBPC + 09] for general protocols and [START_REF] Diamanti | Distributing secret keys with quantum continuous variables: Principle, security and implementations[END_REF] for CV protocols). As already pointed out, establishing the security of a QKD protocol against general attacks in the sense of Eq. 1.1 is nontrivial and a first step is often to prove its security against collective attacks: this means proving that the protocol is secure when restricting input states to independent and identically distributed (i.i.d.) states of the form ρ AB = σ ⊗n for some state σ on A 1 B 1 . This is usually a much simpler task. Then, one uses de Finettitype reductions [START_REF] Renner | Symmetry of large physical systems implies independence of subsystems[END_REF], [START_REF] Christandl | Postselection Technique for Quantum Channels with Applications to Quantum Cryptography[END_REF] in order to show that ε-security against collective attacks implies ε -security against general attacks with ε = ε × poly(n). Since ε can be made exponentially small in n by reducing the key size by an arbitrarily small fraction compared to the asymptotic rate, the polynomial overhead is negligible and one obtains a full security proof. For some protocols (such as BB84 and some specific CV protocols), a more direct approach is possible through the use of entropic uncertainty relations [START_REF] Tomamichel | Tight finite-key analysis for quantum cryptography[END_REF], [START_REF] Tomamichel | A rigorous and complete proof of finite key security of quantum key distribution[END_REF], [FFB + 12].

A CV QKD protocol with heterodyne detection

QKD protocols with continuous variables were introduced by Ralph [Ral99] but initially tried to copy the ideas from BB84 by using 4 different squeezed states to play the role of the 4 BB84 states. An important breakthrough in the field was the realization that secure protocols could be obtained with a Gaussian modulation of coherent states [START_REF] Grosshans | Continuous Variable Quantum Cryptography Using Coherent States[END_REF], which are both much more practical and exploiting efficiently the phase space by allowing for continuous modulations.

In this document, we will focus on what is arguably the most natural CV protocol, in the sense that it displays the most symmetries making its analysis somewhat more tractable (but not easy!): in its EB version, Alice prepares two-mode squeezed states |λ , distribute one half of each state to Bob and both parties measure their systems with heterodyne detection; in its PM version (described in Table 1.1 below), Alice prepares coherent states with a Gaussian modulation. This protocol was first investigated in [WLB + 04]. We note that the protocol uses reverse reconcilation [START_REF] Grosshans | Reverse reconciliation protocols for quantum cryptography with continuous variables[END_REF] meaning that Bob's measurement results will be used as the raw key since it is known to increase the robustness of the protocol.

The description of the protocol in Table 1.1 makes some simplifying assumptions. In practice, the measurement results x and y should be discretized but we ignore this in the following. We also assume that the measurement devices of Alice and Bob are trusted and behave according to their theoretical model: in particular, the heterodyne measurement admits the coherent states as POVM elements (recall that the coherent states resolve the identity: 1 π |α α|dα = 1). In other words, for a single-mode state ρ, the probability density function of measurement outcome is p Symmetrization: Alice and Bob pick a random unitary from the Haar measure on U (n) and apply it to their respective vectors x and y, seen as n-dimensional complex vectors, obtaining two new vectors u, v ∈ R 2n .

(α) = 1 π α|ρ|α with |α := e -|α| 2 /2 ∞ i=0 α i √ i! |i .
Error Correction: Bob sends some side-information of size leak EC to Alice who outputs a guess v for the string of Bob. Bob computes a hash of v of length log 2 (1/ε cor ) and sends it to Alice who compares it with her own hash. If both hashes differ, the protocol aborts.

Parameter Estimation: Bob sends n PE = O(log(1/ε PE )) bits of information to Alice that allow her to compute x 2 = u 2 , y 2 = v 2 and x, y = u, v . Depending on these three values, the protocol either continues or aborts (see Ref. [START_REF] Leverrier | Composable security proof for continuous-variable quantum key distribution with coherent states[END_REF] for details).

Privacy Amplification: They compute keys K A = H pa (v) and K B = H pa (v) of length for some hash function H pa . Finally, let us note that the protocol above has a symmetrization step, which is rather unpractical since it involves drawing a unitary from the Haar measure on U (n). This has complexity O(n 2 ). We choose to add this extra-step explicitly in order to argue that the protocol is invariant under the action of the unitary group U (n), as we will see in Section 1.5. For discrete-variable protocols such as BB84, one instead assumes that the protocols are invariant under the action of the symmetric group S n and one can enforce this symmetry by applying a random permutation. It has been claimed in the literature that this active symmetrization is in fact not needed [START_REF] Renner | Symmetry of large physical systems implies independence of subsystems[END_REF] and indeed some security proofs do not require this symmetrization step [START_REF] Tomamichel | Tight finite-key analysis for quantum cryptography[END_REF]. There are therefore reasons to be believe that the symmetrization step is not required either for the CV protocol outlined in Table 1.1. In particular, the crucial part of the postprocessing is the estimation of the correlations x 2 , y 2 , x, y and these quantities are clearly invariant under the group U (n).

In the EB version of the protocol, Alice would start by preparing n two-mode squeezed vacuum states, measure the A [n] systems with heterodyne detection and store the (properly rescaled) results in the string x. Details can be found for instance in Ref. [START_REF] Leverrier | Composable security proof for continuous-variable quantum key distribution with coherent states[END_REF].

We conclude this section by mentioning some difficulties that arise when analyzing CV QKD protocols such as the one above:

• roughly speaking, a QKD protocol is essentially a tomography procedure that aims at deciding whether the state shared by Alice and Bob is sufficiently correlated to allow them to distill a secret key. This is done via the crucial step of parameter estimation. For protocols such as BB84, the goal is to estimate the quantum bit error rate, a value between 0 and 1. In CV protocols on the other hand, the right measure of correlations is the covariance matrix of the bipartite state shared by Alice and Bob. Here the complication lies in the fact that this matrix is not a priori bounded and providing confidence regions for unbounded random variables turns out to be very challenging. We solve this problem by symmetrizing the protocol under the action of the unitary group [START_REF] Leverrier | Composable security proof for continuous-variable quantum key distribution with coherent states[END_REF].

• another challenge results from the infinite dimension of the Fock space Hilbert space, rendering most techniques developed for qubit protocols ineffective. Fortunately, the CV protocols we consider involve states with bounded energy in practice.

The goal here consists in designing the right tests of energy that will allow us to truncate the Fock space in order to obtain a finite-dimensional Hilbert space.

• finally, such a truncation still gives a very large local Hilbert space (of order log n) if performed naively. In that case, de Finetti reductions are too weak to guarantee security for practical values of n. We solve this challenge by establishing a new Gaussian version of the de Finetti theorem.

We have been able to address each of these difficulties in a series of papers [START_REF] Leverrier | Security of continuous-variable quantum key distribution against general attacks[END_REF], [START_REF] Leverrier | Composable security proof for continuous-variable quantum key distribution with coherent states[END_REF], [START_REF] Leverrier | q) coherent states and gaussian de finetti theorems[END_REF], [START_REF] Leverrier | Security of continuous-variable quantum key distribution via a gaussian de finetti reduction[END_REF] and we will describe the techniques we developed in the next sections.

The general outline of the security proof is as follows. Let us denote by E 0 the protocol of Table 1.1. Let us further design an energy test T that takes as input a spate in some larger space

A 1 • • • A n+k B 1 • • • B n+k with k
n that either passes and return a state of

A 1 • • • A n B 1 • • • B n
or aborts the protocol. In other words, both Alice and Bob start with an (n + k)-mode state, measure k of these modes, and are left with an n-mode state. The overall protocol that we consider is E := R • E 0 • T , where R is an additional privacy amplification procedure. The security proof involves several steps:

• showing that E 0 is secure against collective attacks (Section 1.3),

• showing that the test T allows us to restrict our attention to states in a certain finite-dimensional Hilbert space (Section 1.4),

• showing that the reduction from general to collective attacks is efficient, thanks to a Gaussian de Finetti theorem (Section 1.5).

Tomography of large continuous-variable systems

In this section, we focus on the problem of bounding the covariance matrix of an unknown quantum state. Recall that for a QKD protocol to be secure, it should output a secret key (possibly of length 0) for any possible input state. The parameter estimation step of the protocol is a test where Alice and Bob check whether their measurement outcomes are sufficiently correlated and can be exploited to distill a secret key of length > 0. If the test fails, then the protocol aborts. This task is reminiscent of quantum state tomography, but differs in two crucial ways: (i) in QKD, we are only interested in estimating a specific measure of correlations, not the whole density matrix; (ii) in QKD, the procedure should work for arbitrary state, while quantum state tomography is designed to work well on the specific states that are prepared in a given experiment, without any success guarantee for arbitrary states. For discrete-variable protocols such as BB84, the appropriate measure of correlations is the so-called quantum bit error rate (qber) which takes values between 0 and 1, corresponding to the fraction of bits for which Alice and Bob's results differ. The test then takes the following form: fix some threshold δ ∈ (0, 1) and and integers k, m such that k + m = n. Alice and Bob publicly reveal a random subset of k of their measurement outputs and check whether the average fraction of errors is below δ. In that case, the test passes and the protocol continues, otherwise it aborts. In order to make a security statement, one then needs to show that the probability that the test passes and that the quantum bit error rate on the rest on the measurement results is much larger than δ, is negligible.

For instance, the following theorem was established in [START_REF] Tomamichel | Tight finite-key analysis for quantum cryptography[END_REF].

Theorem 1. Consider a set of binary random variables Z = (Z 1 , Z 2 , . . . , Z n ) with Z i taking values in {0, 1} and n = m + k. Let Π be a uniformly distributed random subset of [n] of size k. Then,

Pr i∈Π Z i ≤ kδ ∧ i∈ Π Z i ≥ m(δ + ν) ≤ exp -2ν 2 nk 2 (m + k)(k + 1)
.

(1.4)

Remarkably this bound is valid without any assumption on the distribution of Z.

In the case of CV QKD, the appropriate measure of correlation for a bipartite state ρ AB is its averaged covariance matrix. If the measurement outcomes of Alice and Bob are modeled by 2 random variables X = (X 1 , . . . , X n ) and Y = (Y 1 , . . . , Y n ), we are specifically interested in their variances and covariance, namely

1 n n i=1 |X i | 2 , 1 n n i=1 |Y i | 2 and 1 n n i=1 X i , Y i .
In other words, we are not concerned anymore with estimating the average of binary variables, but rather that of real variables. The problem we face is the following: given n real-valued random variables Z = (Z 1 , . . . , Z n ), is it possible to devise a statistical test where we are allowed to look at a subset of the variables that will let us bound the average of the remaining variables, similarly as what is done in Theorem 1? To make matters worse, in the context of QKD, the protocol should always work which means that we are not allowed to make any assumption about the distribution of the Z i .

It is easy to show that the strategy of Theorem 1 will fail, in the sense that the average computed over a subset of the variables will not give us any guarantee about the average over the remaining variables. A simple counter-example is as follows: the variables Z i are distributed such as one of the n variables takes value A (which is unknown) while the remaining ones take value 0. In that case, sampling a random subset of k coordinates and computing the average will either give 0 or A/k, and in both cases, the result will incorrectly predict the average of the subset that was not observed, which is either A/m or 0. Note that if an upper bound on |A| is available, then one can still make sure that the error equal to max(A/k, A/m) is small enough by increasing k and m, but without such a bound, it is impossible to know what values of k and m to take to guarantee an arbitrary small error. The problem results from the fact that the variables Z i are not bounded a priori, and this is what makes the security statements for CV QKD more difficult to establish.

It should also be noted that restricting our attention to collective attacks, which means that the Z i can be assumed to be i.i.d. random variables, does not help. In fact, while the literature on CV QKD often makes the statement that security against collective attacks was proven in [START_REF] García-Patrón | Unconditional optimality of gaussian attacks against continuous-variable quantum key distribution[END_REF], [START_REF] Navascués | Optimality of Gaussian Attacks in Continuous-Variable Quantum Cryptography[END_REF], it is not the case, precisely for the reason described above that estimating the covariance matrix of the state is a nontrivial task which was not addressed in those papers.

Fortunately, our problem has a solution: replace the random subset of coordinates used in Theorem 1 by a random subspace. Equivalently, given a vector Z = (Z 1 , . . . , Z n ), first choose a random R chosen from the Haar measure on the orthogonal group O(n), apply it to Z to get Z = RZ and measure the first k coordinates of Z . Then, one can make a prediction about the average value of the remaining coordinates, which will be correct with high probability over the choice of random transformation R ∈ O(n). In [START_REF] Leverrier | Composable security proof for continuous-variable quantum key distribution with coherent states[END_REF], we proved this theorem in the case where Z in a complex vector instead of a real vector, but both cases work similarly.

Theorem 2. Given a vector X ∈ C 2n , consider Π the projector on a random subspace

of dimension n, then for ε ≥ 2e -n/2 , Pr 2 ΠX 2 X 2 ≥ 1 + 1.5 ln(2/ε) n ≤ ε, Pr 2 ΠX 2 X 2 ≤ 1 -2.2 ln(2ε) n ≤ ε.
While the idea of picking a random unitary or orthogonal transformation is natural to make the parameter estimation possible, it is, however, computationally costly and we would like to avoid it in a real protocol. In the protocol description given in Table 1.1, a symmetrization step is explicitly included but a future goal would be to prove that this is in fact unnecessary. For this reason, it is important to be able to perform the parameter estimation without actively symmetrizing the data. A solution for this is developed in Ref. [START_REF] Leverrier | Composable security proof for continuous-variable quantum key distribution with coherent states[END_REF]: the main idea is to perform error correction before parameter estimation, while the opposite order is usually preferred in QKD protocols. This can be done quite efficiently since a rough estimate of the signal-to-noise ratio (SNR) of the data is in general sufficient to choose an appropriate error correcting code and proceed with the reconciliation. The advantage is that once the error correction is finished, Alice knows both her and Bob's measurements results. She can therefore infer the variances and covariances for the whole set of data. She is then able to compute an upper bound on the probability of picking a unitary transformation that would lead to an incorrect prediction in the parameter estimation test.

More specifically, the CV QKD protocol of Table 1.1 admits 3 parameters Σ max a , Σ max b and Σ min c corresponding respectively to the thresholds for the variance of Alice's measurements, the variance of Bob's measurements and a lower bound on the covariance. After the error correction is completed, Alice knows the values of x 2 , y 2 and x, y and can compute γ a , γ b , γ c defined by

γ a := 1 2n 1 + 2 log(36/ε PE ) n X 2 -1, (1.5) γ b := 1 2n 1 + 2 log(36/ε PE ) n Y 2 -1 (1.6) γ c := 1 2n X, Y -5 log(8/ε PE ) n 3 ( X 2 + Y 2 ). (1.7)
Here, ε PE quantifies the probability that the energy test passes while making a wrong prediction about the conditional state of the remaining modes. The parameter estimation test is simply

: if [γ a ≤ Σ max a ] ∧ [γ b ≤ Σ max b ] ∧ [γ c ≥ Σ min c ],
then ACCEPT, otherwise REJECT. The following theorem proven in [START_REF] Leverrier | Composable security proof for continuous-variable quantum key distribution with coherent states[END_REF] gives an upper bound on the probability that the test passes and that the key produced by the protocol with parameters

Σ max a , Σ max b , Σ min c is not secret.
Theorem 3. The probability that the Parameter Estimation Test passes, that is,

[γ a ≤ Σ max a ]∧[γ b ≤ Σ max b ]∧[γ c ≥ Σ min c
] and that the Holevo information χ(v; E) between the raw key and Eve's quantum system computed for the Gaussian state with covariance matrix characterized by Σ max a , Σ max b and Σ min c is underestimated, is upper-bounded by ε PE .

Note that for the Holevo information to be well defined, it is crucial that the quantum state has an i.i.d. structure. For this reason, the theorem above and the results of [START_REF] Leverrier | Composable security proof for continuous-variable quantum key distribution with coherent states[END_REF] apply in the case of collective attacks only, and it will be the goal of the next sections to show that security against collective attacks is sufficient to imply security against general attacks (with a slightly worse security parameter).

For completeness, the Holevo information χ(v; E) mentioned in Theorem 3 can be upper bounded by f (Σ max a , Σ max b , Σ min c ) := g((ν 1 -1)/2) + g((ν 2 -1)/2) -g((ν 3 -1)/2) where ν 1 and ν 2 are the symplectic eigenvalues of the covariance matrix

Σ max a 1 2 Σ min c σz Σ min c σz Σ max b 1 2 , ν 3 = Σ max a -Σ min c 2 /(1 + Σ max b ), σ z = diag(1, -1) and g(x) := (x + 1) log 2 (x + 1) - x log 2 (x)
. This is a standard result in the study of CV QKD protocols established in [START_REF] García-Patrón | Unconditional optimality of gaussian attacks against continuous-variable quantum key distribution[END_REF] using the optimality of Gaussian states [START_REF] Michael | Extremality of Gaussian Quantum States[END_REF].

The techniques presented in this section allow one to analyze the parameter estimation test of the CV QKD protocol of Table 1.1. This is the crucial step that was missing from Refs. [START_REF] García-Patrón | Unconditional optimality of gaussian attacks against continuous-variable quantum key distribution[END_REF], [START_REF] Navascués | Optimality of Gaussian Attacks in Continuous-Variable Quantum Cryptography[END_REF] and which gives a composable security proof of the protocol against collective attacks, that is when restricting the input states to states of the form σ ⊗n AB . Extending such a proof to take care of general attacks requires some de Finetti reduction. Such an approach was first successfully carried out in a work by Renner and Cirac [START_REF] Renner | de Finetti Representation Theorem for Infinite-Dimensional Quantum Systems and Applications to Quantum Cryptography[END_REF], but gives bounds that scale poorly with n. In particular, they are too weak to prove that some secure keys can be distilled by exchanging a reasonable number of coherent states, say less than 10 9 or 10 10 . For this, a better reduction is required and we will describe such a result in Section 1.5.

To conclude this section, let us also note that there exists a different approach to proving the security of a CV QKD protocol (different from that of Table 1.1) which bypasses security proofs against collective attacks altogether. The idea is to appeal to entropic uncertainty relations for smooth-entropies that have been developed both for discrete and continuous variables [START_REF] Tomamichel | Uncertainty relation for smooth entropies[END_REF], [FFB + 12], [FBT + 14] (see [START_REF] Patrick | Entropic uncertainty relations and their applications[END_REF] for a recent review on the topic). The main advantage of this approach is that it proves that secret keys can be distilled for reasonable block length. Unfortunately, the approach has two important drawbacks: first, the protocols require Alice to prepare and send squeezed states to Bob instead of coherent states, which make these protocols less appealing from a practical point of view; second, the key rate converges to a rate strictly smaller than the one conjectured from the optimality of Gaussian attacks.

Truncating the Fock space via an energy test

In order to use the Gaussian de Finetti reduction that will be described in Section 1.5, it is necessary to "truncate" the infinite-dimensional Fock space and replace it by a finitedimensional Hilbert space. The Fock states that form an orthonormal basis of the Fock space are labelled by integers counting the number of photons present in each optical mode. In particular, Fock states with a large number of photons are highly energetic and unlikely to be observed in a CV QKD experiment. The main idea to achieve the truncation is to test a small number of modes and measure their energy. Provided that the state has been adequately symmetrized (to ensure that the energy is well spread out across the modes), the energy of the measured modes will be a good indicator of the energy of the remaining modes. In particular, if that energy is sufficiently small, it means that the remaining quantum state can be well approximated by a quantum state living in a reasonably small Hilbert space (spanned by the "lowest" Fock states). This is the idea behind our energy test.

It will be useful to introduce a notation for the various Fock spaces that will appear in the following. Let F 1,1,n represent the Fock space corresponding to a total of 2n modes, n of which being held by Alice, and the remaining modes being held by Bob. Similarly, F 1,1,n+k corresponds to a 2(n + k)-mode Fock space. The meaning of the 1s will become clearer in the next section, but we don't need it here. Finally, we define F ≤K 1,1,n to be the finite-dimensional subspace of F 1,1,n spanned by Fock states with at most K photons in total. We have:

F 1,1,n := Span |i 1 , . . . , i n ; j 1 , . . . , j n : i 1 , . . . , i n , j 1 , . . . , j n ∈ N F ≤K 1,1,n := Span |i 1 , . . . , i n ; j 1 , . . . , j n : i 1 , . . . , i n , j 1 , . . . , j n ∈ N, n k=1 i k + j k ≤ K .
Following the results of the previous section, let us suppose that our CV QKD protocol of interest, E 0 , is secure against Gaussian collective attacks. Recall that E 0 takes as input states on F 1,1,n . We will slightly modify the protocol by prepending an initial test T . More precisely, T is a CP map taking a state in the slightly larger Hilbert space F 1,1,n+k , applying a randomization of this state (corresponding to processing the modes with a random linear optical network of beamsplitters and phaseshifters), measuring the last k modes and comparing the measurement outcome to a threshold fixed in advance. The test succeeds if the measurement outcome (related to the energy) is small, meaning that the global state is compatible with a state containing only a low number of photons per mode. Such a state is well-described in a low dimensional Hilbert space, as we will discuss below. Depending on the outcome of the test, either the protocol aborts, or one applies the original protocol E 0 on the n remaining modes.

For the test to be practical, it is important that the legitimate parties do not have to physically implement the transformation corresponding to the optical network (which is parameterized by a unitary u ∈ U (n + k)). Rather, they can both measure their n + k modes with heterodyne detection, perform a random rotation of their respective classical

vector in R 2(n+k) according to u ∈ U (n + k) ∼ = O(2(n + k)) ∩ Sp(2(n + k)).
Let us denote by P(H) the set of nonnegative operators on H. We introduce the following maps:

T : P(F 1,1,n+k ) → P(F 1,1,n ) ⊗ {passes/aborts}, P : P(F 1,1,n ) → P(F ≤K 1,1,n ), R : {0, 1} × {0, 1} → {0, 1} × {0, 1} , where • the energy test T (k, d A , d B ) takes as input an arbitrary state ρ AB on F 1,1,n+k , maps it to W u ρ AB W † u
where the unitary u is chosen from the Haar measure on U (n + k) and W u is the corresponding unitary acting on F 1,1,n+k (which transforms the (n+k) creation operators of Alice's modes according to the unitary u and the (n + k) creation operators of Bob's modes according to its complex conjugate u), measures the last k modes for A and B with heterodyne detection and check whether the measurement outputs pass the test, that is whether the

k outcomes α 1 , • • • , α k of Alice and β 1 , • • • , β k of Bob satisfy k i=1 |α i | 2 ≤ kd A and k i=1 |β i | 2 ≤ kd B .
If they pass the test, the map returns the state on the first n modes (that were not measured) as well as the flag "passes". Otherwise, it returns the flag "aborts".

• P ≤K is a map projecting the input state onto the finite-dimensional subspace F ≤K 1,1,n (corresponding to states with at most K photons in the 2n modes): it maps any density matrix

ρ ∈ P(F 1,1,n ) to Π ≤K ρΠ ≤K ∈ P(F ≤K 1,1,n )
, where Π ≤K is the orthogonal projector onto F ≤K 1,1,n . This trace non-increasing map is introduced as a technical tool for the security analysis but need not be implemented in practice. It simply ensures that the states that are fed to the original QKD protocol E 0 live in a finite-dimensional subspace. In the text, we will alternatively denote this projection by P ≤K or P(n, K), depending on which parameters we wish to make explicit.

• R is a classical map that takes two -bit strings as input and returns -bit strings (for < ). It corresponds to an additional privacy amplification procedure, compared to the original protocol E 0 , needed to ensure the security of E against general attacks.

We finally define our CV QKD protocol E as

E = R • E 0 • T
and the ideal protocol as F = S • E.

The following result was obtained in [START_REF] Leverrier | Security of continuous-variable quantum key distribution via a gaussian de finetti reduction[END_REF].

Theorem 4. Let E be the protocol R • E 0 • P. Then the security of E implies the security of E:

||E -F|| ≤ ||E -F|| + 2||(1 -P) • T || , (1.8)
provided that the quantity ||(1 -P) • T || can be made arbitrarily small.

The term ||E -F|| will be addressed in Section 1.5, where we will explain how to obtain a tight upper bound by replacing the supremum of Eq. (1.2) by a supremum over a restricted class of Gaussian i.i.d. states. The second term, ||(1 -P) • T || , corresponds to the failure probability of the energy test and can be bounded using the following theorem that was proven in [START_REF] Leverrier | Security of continuous-variable quantum key distribution via a gaussian de finetti reduction[END_REF].

Theorem 5. For integers n, k ≥ 1, and

d A , d B > 0, define K = n(d A + d B ) for d A/B = d A/B g(n,
k, ε/4) for the function g defined in Eq. (1.9). Then

1 -P(n, K) • T (k, d A , d B ) ≤ ε.
Establishing Theorem 5 requires two main ingredients: the operator inequality of Lemma 6 below and concentration bounds for the χ 2 distribution which yield Lemma 7. For d > 0, let us introduce the following operators on an n-mode Fock space:

T d n := 1 π n n i=1 |α i | 2 ≥nd |α 1 α 1 | ⊗ . . . ⊗ |α n α n |dα 1 . . . α n U d n := ∞ m=nd+1 Π n m ,
where Π n m is the projector onto the finite dimensional Hilbert space spanned by Fock states containing m photons:

Π n m = m 1 +...+mn=m |m 1 , . . . , m n m 1 , . . . , m n |.
In words, T d n is the sum of the projectors onto products of coherent states such that the total squared amplitude is greater than nd and U d n is the projector onto Fock states containing more that nd photons. Intuitively, both operators should be "close" to each other. This is formalized with the following lemma that was proven in [START_REF] Leverrier | Security of continuous-variable quantum key distribution against general attacks[END_REF]. Lemma 6. For any integer n and any d ≥ 0, it holds that

U d n ≤ 2T d n .
An n-mode state is called "rotationally invariant" if it is invariant when being processed by any linear optical network consisting of beamsplitters and phase shifters. This is for instance the case of the states that are obtained after the symmetrization procedure that we described in Section 1.2 and we will study these invariant states in more detail in Section 1.5 since they are relevant in the context of de Finetti theorems. For such states, one expects that the energy is spread evenly among the different optical modes. This is formalized in the following lemma that was established in [START_REF] Leverrier | Security of continuous-variable quantum key distribution via a gaussian de finetti reduction[END_REF].

Lemma 7. Let ρ be an rotationally invariant state on H ⊗(n+k) . Then, for any d > 0,

tr (T d n ⊗ (1 -T d k ))ρ ≤ ε, for d = g(n, k, ε)d and g(n, k, ε) = 1 + 2 ln(2/ε) 2n + ln(2/ε) n 1 -2 ln(2/ε) 2k
.

(1.9)

The only missing step in the security reduction is therefore a way to obtain an upper bound on ||E -F|| . This is the object of the next section.

SU (2, 2) coherent states and Gaussian de Finetti reductions

Despite their wide range of application, there is a regime where "standard" de Finetti theorems fail, namely when the local dimension is not negligible compared to the number n of subsystems [START_REF] Christandl | One-and-a-half quantum de finetti theorems[END_REF]. In particular, these techniques do not apply directly to CV protocols where the local spaces are infinite-dimensional Fock spaces. In this work, we consider a natural symmetry displayed by some important CV QKD protocols, which are invariant under the action of beamsplitters and phase-shifts on their n modes [START_REF] Leverrier | Security of continuousvariable quantum key distribution: towards a de Finetti theorem for rotation symmetry in phase space[END_REF].

For such protocols, one legitimately expects that stronger versions of de Finetti theorems should hold. In particular, a widely held belief that it is enough to consider Gaussian i.i.d. input states instead of all i.i.d. states in order to analyze the security of the corresponding protocol.

We prove this statement rigorously here. Our main tool is a family of SU (2, 2) generalized coherent states that resolve the identity of the subspace spanned by states invariant under the action of U (n). This implies that for some applications such as QKD, it is sufficient to consider the behaviour of the protocol for these states in order to obtain guarantees that hold for arbitrary input states.

In this section, we discuss our results from Ref. [START_REF] Leverrier | q) coherent states and gaussian de finetti theorems[END_REF] and define SU (2, 2) coherent states. Such states allow us to prove a Gaussian de Finetti reduction which in turn provides an upper bound on ||E -F|| that can be computed if the protocol E 0 is secure against Gaussian collective attacks, meaning that the CV QKD protocol E 0 is secure when its input is restricted to Gaussian i.i.d. states (instead of arbitrary states on F 1,1,n ).

The symmetric subspace

F U (n) 2,2,n Let H A ∼ = H B ∼ = H A ∼ = H B ∼ = C n and define the Fock space F 2,2,n as F 2,2,n := ∞ k=0 Sym k (H A ⊗ H B ⊗ H A ⊗ H B ),
where Sym k (H) is the symmetric part of H ⊗k . Hopefully the notation F 1,1,n that we introduced in the previous section becomes a little bit clearer here. Indeed,

F 1,1,n = ∞ k=0 Sym k (H A ⊗ H B )
, and any mixed state on F 1,1,n admits a purification in F 2,2,n . Using the Segal-Bargmann representation, the Hilbert space F 2,2,n is realized as a functional space of complex holomorphic functions square-integrable with respect to the Gaussian measure,

F 2,2,n ∼ = L 2 hol (C 4n , • ), and a state ψ ∈ F 2,2,n represented by a holomorphic function ψ(z, z ) with z ∈ C 2n , z ∈ C 2n satisfying ψ 2 := ψ, ψ = 1 π 4n exp(-|z| 2 -|z | 2 )|ψ(z, z )| 2 dzdz < ∞ (1.
2 := n k=1 2 i=1 |z k,i | 2 , |z | 2 := n k=1 2 j=1 |z k,j | 2 .
A state ψ ∈ F 2,2,n therefore corresponds to a holomorphic function of 4n complex variables (z 1,1 , z n,1 ; z 1,2 , . . . , z n,2 ; z 1,1 , . . . , z n,1 ; z 1,2 , . . . , z n,2 ). For conciseness, we denote by z i and z j the vectors (z 1,i , . . . , z n,i ) and (z 1,j , . . . , z n,j ), respectively, for i, j ∈ {1, 2}. With these notations, the vector z 1 is associated to the space H A , the vector z 1 to H B , the vector z 2 to H B and the vector z 2 to H A . Formally, one can switch from the Segal-Bargmann representation to the representation in terms of annihihation and creation operators by replacing the variables z k,1 by

a † k , z k,2 by b † k , z k,1 by b † k and z k,2 by a † k . The function f (z, z ) is therefore replaced by an operator f (a † , b † , a † , b †
) and the corresponding state in the Fock basis is obtained by applying this operator to the vacuum state.

The metaplectic representation of the unitary group

U (n) ⊂ Sp(2n, R) on F 2,2,n associates to u ∈ U (n) the operator W u performing the change of variables z → uz, z → uz : U (n) → End(F 2,2,n ) (1.11) u → W u = ψ(z 1 , z 2 , z 1 , z 2 ) → ψ(uz 1 , uz 2 , uz 1 , uz 2 ) (1.12)
where u denotes the complex conjugate of the unitary matrix u. In other words, the unitary u is applied to the modes of F A ⊗ F B and its complex conjugate is applied to those of F B ⊗ F A . This representation can be extended to the Fock space F p,q,n for arbitrary integers p and q: in that case the unitary u is applied to the first p sets of n modes, while u is applied to the remaining q sets of n modes. The states that are left invariant under the action of the unitary group U (n) are relevant for instance in the context of CV QKD, and we define the symmetric subspace as the space spanned by such invariant states.

Definition 8 (Symmetric subspace). For integer n ≥ 1, the symmetric subspace F

U (n) 2,2,n
is the subspace of functions ψ ∈ F 2,2,n such that

W u ψ = ψ ∀u ∈ U (n),
where W u is defined in Eq. (1.12).

The name symmetric subspace is inspired by the name given to the subspace Sym n (C d ) of (C d ) ⊗n of states invariant under permutation of the subsystems:

Sym n (C d ) := |ψ ∈ (C d ) ⊗n : P (π)|ψ = |ψ , ∀π ∈ S n (1.13)
where π → P (π) is a representation of the permutation group S n on (C d ) ⊗n and P (π) is the operator that permutes the n factors of the state according to π ∈ S n . See for instance [START_REF] Harrow | The church of the symmetric subspace[END_REF] for a recent exposition of the symmetric subspace from a quantum information perspective.

CHAPTER 1. CONTINUOUS-VARIABLE QUANTUM CRYPTOGRAPHY

In [START_REF] Leverrier | q) coherent states and gaussian de finetti theorems[END_REF], a full characterization of the symmetric subspace F U (n) 2,2,n is given. It is helpful to introduce the four operators Z 11 , Z 12 , Z 21 , Z 22 defined by:

Z 11 = n i=1 z i,1 z i,1 ↔ n i=1 a † i b † i , Z 12 = n i=1 z i,1 z i,2 ↔ n i=1 a † i a † i , Z 21 = n i=1 z i,2 z i,1 ↔ n i=1 b † i b † i , Z 22 = n i=1 z i,2 z i,2 ↔ n i=1 a † i b † i .
For instance, the operator Z 11 can be thought of as the coherent addition of a photon in one of Alice's n modes and a photon in Bob's corresponding mode.

Definition 9. For integer n ≥ 1, let E 2,2,n be the space of analytic functions ψ of the

4 variables Z 1,1 , . . . , Z 2,2 , satisfying ψ 2 E < ∞, that is E 2,2,n = L 2 hol (C pq , • E )
, where • E is the norm induced by the norm on F 2,2,n .

In [START_REF] Leverrier | q) coherent states and gaussian de finetti theorems[END_REF], is was proven that E 2,2,n coincides with the symmetric subspace F

U (n) 2,2,n .
Theorem 10. For n ≥ 2, the symmetric subspace F

U (n) 2,2,n is isomorphic to E 2,2,n .
In other words, any state in the symmetric subspace can be written as

|ψ = f n i=1 a † i b † i , n i=1 a † i a † i , n i=1 b † i b † i , n i=1 a † i b † i |vacuum
for some holomorphic function f . Said otherwise, such a state is characterized by only 4 parameters instead of 4n for an arbitrary state in F 2,2,n ; or else, the symmetric subspace is isomorphic to a 4-mode Fock space (with "creation" operators corresponding to Z 11 , Z 12 , Z 21 , Z 22 ), instead of the ambient 4n-mode Fock space.

1.5.2 Coherent states for SU (2, 2)/SU (2) × SU (2) × U (1)
In this section, we first review a construction due to Perelomov that associates a family of generalized coherent states to general Lie groups [START_REF] Perelomov | Coherent states for arbitrary Lie group[END_REF], [START_REF] Perelomov | Generalized coherent states and their applications[END_REF] and then apply it to the pseudo-unitary group SU (2, 2). In this language, the standard Glauber coherent states are associated with the Heisenberg-Weyl group, while the atomic spin coherent states are associated with SU (2). A consequence of Theorem 10 is that symmetric subspace F

U (n) 2,2,n
is spanned by SU (2, 2) coherent states, where SU (2, 2) is the special unitary group of signature (2, 2) over C:

SU (2, 2) := A ∈ M 4 (C) : A1 2,2 A † = 1 2,2 (1.14)
where M 4 (C) is the set of 4 × 4-complex matrices and 1 2,2 = 1 2 ⊕ (-1 2 ).

In Perelomov's construction, a system of coherent states of type (T, |ψ 0 ) where T is the representation of some group G acting on some Hilbert space H |ψ 0 , is the set of states {|ψ g : |ψ g = T g |ψ 0 } where g runs over all the group G. One defines H, the stationary subgroup of |ψ 0 as

H := {g ∈ G : T g |ψ 0 = α|ψ 0 for |α| = 1 } ,
that is the group of h ∈ G such that |ψ h and |ψ 0 differ only by a phase factor. When G is a connected noncompact simple Lie group, H is the maximal compact subgroup of G. In particular, for G = SU (2, 2), one has

H = SU (2, 2) ∩ U (4) = SU (2) × SU (2) × U (1)
and the factor space G/H corresponds to a Hermitian symmetric space of classical type (see e.g. Chapter X of [START_REF] Helgason | Differential geometry, Lie groups, and symmetric spaces[END_REF]). The generalized coherent states are parameterized by points in G/H. For G/H = SU (2, 2)/SU (2) × SU (2) × U (1), the factor space is the set

D of 2 × 2 matrices Λ such that ΛΛ † < 1 p , i.e.
, the singular values of Λ are strictly less than 1.

D = Λ ∈ M 2 (C) : 1 2 -ΛΛ † > 0 ,
where A > 0 for a Hermitian matrix A means that A is positive definite.

We are now ready to define our coherent states for the noncompact Lie group SU (2, 2).

Definition 11 (SU (2, 2) coherent states). For n ≥ 1, the coherent state ψ Λ,n associated with Λ ∈ D is given by

ψ Λ,n (Z 1,1 , . . . , Z 2,2 ) = det(1 -ΛΛ † ) n/2 det exp 2 i,j=1 Λ i,j Z ij .
In the following, we will sometimes abuse notation and write ψ Λ instead of ψ Λ,n , when the parameter n is clear from context.

We note that the coherent states have a tensor product form in the sense that

ψ Λ,n = ψ ⊗n Λ,1 .
We will also write |Λ, n = |Λ, 1 ⊗n for ψ Λ,n . Such a state is called identically and independently distributed (i.i.d.) in the quantum information literature. Moreover, the SU (2, 2) generalized coherent states are Gaussian states in the sense that their Wigner function is Gaussian. This means that they are entirely characterized by their first two moments, which makes them very appealing for theoretical study [WLB + 04].

The main feature of a family of coherent states is that they resolve the identity. This is the case with the SU (2, 2) coherent states introduced above: see Ref. [START_REF] Leverrier | q) coherent states and gaussian de finetti theorems[END_REF].

Theorem 12 (Resolution of the identity). For n ≥ 4, the SU (2, 2) generalized coherent states resolve the identity over the symmetric subspace F

U (n) 2,2,n : D |Λ, n Λ, n|dµ n (Λ) = 1 F U (n) 2,2,n , (1.15)
where dµ n (Λ) is the invariant measure on D given by

dµ n (Λ) = (n -1)(n -2) 2 (n -3) π 4 det(1 2 -ΛΛ † ) 4 2 i=1 2 j=1 dR(Λ i,j )dI(Λ i,j ), (1.16)
where R(Λ i,j ) and I(Λ i,j ) refer respectively to the real and imaginary parts of Λ i,j . This operator equality is to be understood for the weak operator topology.

The main work of Ref. [START_REF] Leverrier | Security of continuous-variable quantum key distribution via a gaussian de finetti reduction[END_REF], besides the analysis of the energy test mentioned in the previous section, is to derive a finite-energy version of the resolution of the identity above.

Since the space F

U (n)
2,2,n is infinite-dimensional, the integral of Eq. (1.15) is not normalizable. In order to obtain an operator with finite norm, we consider the finite-dimensional subspace F

U (n),≤K 2,2,n of F U (n)
2,2,n spanned by states with less than K "excitations":

Span (Z 11 ) i (Z 12 ) j (Z 21 ) k (Z 22 ) |vac : i + j + k + ≤ K .
We showed in [START_REF] Leverrier | Security of continuous-variable quantum key distribution via a gaussian de finetti reduction[END_REF] that an approximate resolution of the identity still holds for this space when restricting the coherent states |Λ,

n to Λ ∈ D η for D η = Λ ∈ D : η1 2 -ΛΛ † 0 for η ∈ [0, 1[. Let us denote by Π ≤K the identity onto the subspace F U (n),≤K 2,2,n
(note that this operator differs from Π ≤K that was considered in the previous section) and introduce the relative entropy

D(x||y) = x log x y + (1 -x) log 1-x 1-y . Theorem 13. For n ≥ 5 and η ∈ [0, 1[, if K ≤ ηN 1-η for N = n -5, then the operator inequality Dη |Λ, n Λ, n|dµ n (Λ) ≥ (1 -ε)Π ≤K
(1.17)

holds with ε = 2N 4 (1 + K/N ) 7 exp -N D K K+N η .
Combining Theorem 13 together with the approach of Christandl, König and Renner [START_REF] Christandl | Postselection Technique for Quantum Channels with Applications to Quantum Cryptography[END_REF], one can finally obtain an upper bound on ||E -F|| , provided that we know how E 0 behaves for SU (2, 2) generalized coherent state inputs.

Concluding the security proof of the CV QKD protocol E

The second term in the right hand side of Eq. (1.8) is finally taken care of by the following Gaussian de Finetti reduction, which was proven in [START_REF] Leverrier | Security of continuous-variable quantum key distribution via a gaussian de finetti reduction[END_REF].

Theorem 14. With the previous notations, if E 0 is ε-secure against Gaussian collective attacks, then

||E -F|| ≤ 2T (n, η)ε where T (n, η) = (n -1)(n -2) 2 (n -3) η 4 12(1-η) 4 and E = R • E 0 • P ≤K .
Putting everything together establishes our security reduction.

Theorem 15. If the protocol E 0 is ε-secure against Gaussian collective attacks, then the protocol

E = R • E 0 • P is ε -secure against general attacks with ε ≤ K 4 50 ε
for n ≥ 38 and K ≥ n -5.

The security against collective attacks (and therefore also against Gaussian collective attacks) has been worked out in details in [START_REF] Leverrier | Composable security proof for continuous-variable quantum key distribution with coherent states[END_REF] and follows essentially from the analysis of the parameter estimation procedure discussed in Section 1.3. In particular, one can choose ε to be exponentially small in n in Theorem 15 at the price of slightly reducing the key rate compared to the asymptotic key rate computed for E 0 against Gaussian attacks. The Gaussian de Finetti reduction of Theorem 15 then implies the security of the protocol E = R • E 0 • T against arbitrary attacks.

Chapter 2

Quantum non-locality and applications to cryptography

This chapter is concerned with several topics that revolve around the concept of quantum correlations, which correspond to the conditional probability distributions that can be observed when several agents perform measurements on a multipartite quantum system. In Section 2.1, we present a general framework to describe non-locality (and more generally to contextuality) based on an original idea of Tobias Fritz and extensively developed in [START_REF] Acín | A combinatorial approach to nonlocality and contextuality[END_REF] together with Antonio Acín, Tobias Fritz and Ana-Belén Sainz. In Section 2.2, we explain how the strengthening of the non-signaling principle, namely the fact that information cannot travel faster than the speed of light, can be exploited in a cryptographic context: in particular, it allows for informationally-secure bit commitment. These results, which belong to the nascent field of "relativistic cryptography", were obtained in collaboration with André Chailloux and Kaushik Chakraborty. In Section 2.3, we consider quantum protocols for position-verification. While information-theoretic security cannot be achieved for this task, the best known attacks often require an exponential amount of entanglement. In a work with Kaushik Chakraborty, we proposed general classes of attacks that only require polynomial resources. The connection with nonlocality it that cheating strategies can be interpreted as winning strategies for a special kind of nonlocal games where the inputs are allowed to be quantum states.

A combinatorial approach to contextuality and nonlocality

We introduce a framework to describe probabilistic models in Bell experiments, and more generally in contextuality scenarios. Such a scenario is described by a hypergraph whose vertices represent elementary events and hyperedges correspond to measurements, and a probabilistic model associates to each event a probability, in such a way that events in a given measurement have a total probability equal to one. We discuss the advantages of this framework, most notably, it unifies the notions of contexuality and non-locality, 25 and give a short overview of the results presented in Ref. [START_REF] Acín | A combinatorial approach to nonlocality and contextuality[END_REF].

The main goal of physics is to understand how Nature works, and usually physicists proceed as follows: first, observe a phenomenon, then propose a model that explains it, and finally, confront the predictions of the model to experimental data. Repeat until the experimental results match the theoretical predictions. In some situations, however, it can be fruitful to limit the model to a minimum. This idea was recently investigated in the paradigm of device-independence [BCP + 13]. There, an experimenter has access to a physical device with classical commands x ∈ X and classical results a ∈ A and chooses not to model the inner workings of the device any further. This might seem futile at first sight because how can one hope to say anything meaningful when only observing conditional probabilities of the form P (a|x), corresponding to the probability of obtaining outcome a when applying command (or measurement) x? The key is to consider n physical devices accessed in a space-like separated way by n experimenters. Then, one has access to the conditional probability distribution P (a 1 , . . . , a n |x 1 , . . . , x n ) where a i and x i refer to the outcomes and measurements of the i th party, where the nosignaling principle constrains P non-trivially. Stronger restrictions can be imposed by requiring the devices to be compatible with quantum theory, or even to be classical. In this section, we describe the framework of [START_REF] Acín | A combinatorial approach to nonlocality and contextuality[END_REF] allowing to describe such Bell-type scenarios in a very general way, and that extends naturally to contextuality scenarios.

Contextuality scenarios

We define a contextuality scenario to be a hypergraph H = (V, E) whose vertices v ∈ V correspond to the events of the scenario, and the (hyper-)edges e = {v 1 , • • • , v k } ∈ E are subsets of V that should be thought of as the measurements of the scenario. We demand in addition that all the vertices belong to at least one edge, and that no edge is strictly contained in another one. Such scenarios have been studied before in quantum logic where there are known as "test spaces" [START_REF] Wilce | Test spaces. Handbook of quantum logic and quantum structures: quantum logic[END_REF]. A probabilistic model on the scenario H is then given by an assignment p : V → [0, 1] of a probability p(v) to each event v ∈ V satisfying the normalization condition:

v∈e p(v) = 1 for each measurement e ∈ E. Let us denote by G(H) ⊆ [0, 1] |V | the set of probabilistic models for the scenario H. By construction, this set is a polytope, the set of "states on test spaces" in the terminology of test spaces. Let us note that this approach was inspired by the framework developed in [START_REF] Cabello | non-) contextuality of physical theories as an axiom[END_REF] (see also [START_REF] Cabello | Graph-theoretic approach to quantum correlations[END_REF]), but that a crucial difference between the two works is that we explicitly work with normalized probability distributions, instead of subnormalized ones.

Bell-type scenarios

An important application of this framework concerns Bell-type scenarios where n parties have access to n distinct devices. For simplicity, we restrict ourselves to the scenario B n,m,k where the n devices all have m different settings and k possible outcomes. In particular, B 2,2,2 will correspond to the usual CHSH scenario. We now wish to describe the hypergraph B n,m,k . Its vertices are the (mk) n events of the form (a 1 , . . . , a n |x 1 , . . . , x n ). The trickier part is to characterize the measurements of the scenario. Usually, one would define a measurement to be the set of events of the form

(•|x 1 , • • • , x n ).
But our framework includes additional measurements: a measurement in the scenario B n,m,k corresponds to any strategy applied by the n parties, possibly coming together, where each of the parties measures their device. More specifically, a measurement of B n,m,k is given by a temporal ordering of the parties: i 1 ≤ i 2 ≤ . . . ≤ i n where party i 1 first chooses a measurement setting x i 1 and obtains an outcome a i 1 . Then, party i 2 chooses a setting x i 2 , possibly depending on x i 1 and a i 1 , and obtains an outcome a i 2 . This process is repeated until the last party performs their measurement. Note that the strategy can be adaptive, meaning that party i k can choose their measurement setting to be a function of a i 1 , x i 1 , . . . , a i k-1 , x i k-1 . The scenario obtained this way is displayed on Fig. 2.1 in the case of B 2,2,2 .

The main advantage of defining B n,m,k as above is that G(B n,m,k ) is exactly the standard no-signaling polytope N S(B n,m,k ), defined as correlations satisfying a i+1 ...an p(a 1 , . . . , a n |x 1 , . . . , x n ) = p(a 1 , . . . , a i |x 1 , . . . , x i ) for any splitting of the n parties into two groups. The proof is straightforward (see [START_REF] Acín | A combinatorial approach to nonlocality and contextuality[END_REF] for details) and we only give the intuition in the case of B 2,2,2 here. We wish to show that the normalization of the edges (i.e., the total probability of the events in a given measurement should be 1) is equivalent to the no-signaling condition. A typical no-signaling condition for CHSH reads: p(00|00)+p(01|00) = p(00|01)+p(01|01) (corresponding to the first row on Fig. 2.1). This can be derived from the normalization of the measurement "00" consisting of events of the form (•|00) and implying that p(00|00) + p(01|00) = 1 -p(10|00) -p(11|00) and of the event {(10|00), (11|00), (00|01), (01|01)} implying that p(00|01) + p(01|01) is also equal to 1 -p(10|00) -p(11|00). Hence, normalization implies no-signaling and the converse property can also be checked in the same fashion.

Classical and quantum models

There are two natural restrictions that one might want to impose on the devices: either a classical, or a quantum nature, leading respectively to the notions of classical and quantum probabilistic models. First, a deterministic model on H is a probabilistic model (hence satisfying normalization) such that p(v) ∈ {0, 1} for any event v ∈ V . Then, classical models are given by convex combinations of deterministic models: p(v) = λ q λ p λ (v), where q λ is a probability distribution, and p λ correspond to deterministic models on H. The set of classical models on H is denoted C(H). If H is a Bell-type scenario, then C(H) is the standard Bell polytope. If H is a general contextuality scenario, classical models are those that can be explained by noncontextual hidden variables [START_REF] Fine | Hidden variables, joint probability, and the bell inequalities[END_REF].

A quantum model p on H is a probabilistic model such that there exist a Hilbert space H, a normalized density matrix ρ ∈ P(H), and for each vertex v ∈ V , a projector P v such that v∈e P v = 1 H for each measurement e ∈ E that give rise to p via the Born rule: p(v) = tr (ρP v ), for each event v. The set of quantum models on H is denoted Q(H). Contrary to C(H) and G(H), the quantum set is usually not a polytope, and a recurring question in the literature is to find some "natural principle" that would limit correlations observable in Nature to be in the quantum set. Since Q(B 2,2,2 ) N S(B 2,2,2 ), it is clear that the no-signaling principle alone is not sufficient to restrict the correlations to be quantum.

The quantum set from a natural principle

Several candidate principles for recovering the set of quantum correlations have been suggested and investigated in the literature: Information Causality [PPK + 09], Macroscopic Locality [START_REF] Navascués | A glance beyond the quantum model[END_REF], the nontriviality of communication complexity [vD05], and more recently, Local Orthogonality [FSA + 13], [SFA + 14]. The latter is particularly interesting in the sense that it is a genuinely multipartite principle, a necessary condition in order to recover the quantum set [START_REF] Gallego | Quantum correlations require multipartite information principles[END_REF]. The framework introduced above turns out to be remarkably well-suited for the study of Local Orthogonality (LO). This principle defines a notion of orthogonality between events of a scenario: two events u and v are orthogonal is they belong to a common measurement, i.e., there exists a measurement e ∈ E such that {u, v} ⊆ e. Then, a set C = {v 1 , • • • , v l } ⊆ V of events is said to be orthogonal if its elements are pairwise orthogonal. The principle finally says that the sum of the individual probabilities of a set of orthogonal events is less than one, namely, v∈C p(v) ≤ 1. The set obtained this way is a polytope denoted by LO 1 (H). A natural strengthening of the principle assumes that if a given probabilistic model is "physical", then so should be an arbitrary number k of copies of this model. Then, Local Orthogonality should also be satisfied by the model corresponding to these k copies. Copies of a scenario can be defined via the k-fold Foulis-Randall product of the scenario H with itself, H ⊗k . The Foulis-Randall product [START_REF] James | Empirical logic and tensor products[END_REF] is especially relevant in the context of Bell scenarios since scenarios with many parties can be obtained by taking the product of several single-party scenarios. In particular, B n,m,k = B ⊗n 1,m,k . Now, the strengthening of LO says that the product distribution p ⊗k ∈ G(H ⊗k ) should also satisfy LO. We denote by LO k (H) the set of probabilistic models on H such that p ⊗k ∈ LO1 (H ⊗k ). In the limit of an arbitrary number of copies, this gives rise to the set LO ∞ (H), which would ideally match the set Q(H), were the LO principle sufficient to recover quantum correlations. We note that another way to naturally strengthen LO would be to allow for wirings of boxes. However, it was proved in [FSA + 13] that these leave the set LO ∞ (H) invariant. It turns out that characterizing the set LO ∞ (H) of correlations satisfying the LO principle is quite challenging. While it is reasonably easy to verify that Q(H) ⊆ LO ∞ (H) ⊆ G(H), being more precise is difficult. Our framework, however, allows for a reformulation of LO ∞ (H) in terms of graph invariants. Introduce the orthogonality graph G = Ort(H) of the contextuality scenario H to be the graph with vertex set V (H), and such that {u, v} is an edge if u and v do not belong to a common measurement e ∈ E(H). Then, one can show (see [START_REF] Acín | A combinatorial approach to nonlocality and contextuality[END_REF] for details) that a probabilistic model p belongs to LO ∞ (H) if and only if Θ(Ort(H), p) = 1 where Θ(G, p) refers to the Shannon capacity of the graph G weighted by the distribution p. This characterization can then be used to prove that LO ∞ (H) is in generally strictly larger than Q(H) 1 , and that there even exist contextuality scenarios for which LO ∞ (H) is not convex [SFA + 13].

Hierarchies

Another feature of our framework is that the various sets of correlations we mentioned can be approximated through some hierarchies of relaxations. Such hierarchies have been intensely studied in convex optimization (see Ref. [START_REF] Laurent | Sums of squares, moment matrices and optimization over polynomials[END_REF] for a recent review) and been adapted to the context of quantum correlations [START_REF] Navascués | Bounding the set of quantum correlations[END_REF]. In particular, the hierarchies we will consider may be seen as a special case of the general hierarchy for noncommutative polynomial optimization [START_REF] Doherty | The quantum moment problem and bounds on entangled multiprover games[END_REF], [START_REF] Pironio | Convergent relaxations of polynomial optimization problems with noncommuting variables[END_REF]. Let us first introduce the notion of moment matrix associated with a contextuality scenario H = (V, E). A moment matrix of order k associated with H is a symmetric matrix M k whose rows and columns are indexed by words of size at most k written in the alphabet formed by V . More explicitly, if V = {v 1 , . . . , v n }, the rows of the moment matrix will be indexed by:

∅, v 1 , . . . , v n , v 1 v 1 , v 1 v 2 , . . . , v 1 v n , . . . , v 2 n , . . . , v 3 1 , . . . , v k n ,
where v k i is the word obtained by concatenating k times the letter v. Here, ∅ refers to the empty string, and we choose the normalization M k (∅, ∅) = 1. We denote by V * the set of strings of arbitrary size on V . A matrix M k will be a certificate of order k for the probabilistic model p on H if it is positive semidefinite, M k 0, and if

M k (v, ∅) = p(v) for every v ∈ V .
The matrices M k can display additional "natural" properties that we define now: Normalization, Orthogonality and Commutativity. A moment matrix is normalized with respect to the contextuality scenario H = (V, E) if for every two strings v, w ∈ V * , and every edge e ∈ E, the following condition holds: u∈e M ( vu, w) = M ( v, w).

(Normalization)

A matrix is orthogonal with respect to H if for every e ∈ E, and v, w ∈ V * , the fact that v, w ∈ e implies that

M ( vv, ww) = 0 ∀ v, w ∈ V * . (Orthogonality)
Finally, a matrix is commutative if for any two strings v, w ∈ V * , and every permutation

π of size | v|, M (π( v), w) = M ( v, w), (Commutativity)
where π( v) is the string obtained by permuting the letters of v with the permutation π.

We are now in position to define sets of models for which there exist certificates satisfying some of these properties. These sets actually form hierarchies of sets (S k ) k≥1 , such that S k ⊆ S k-1 corresponds to the probabilistic models with a certificate of order k. The hierarchies we will introduce admit limits that we denote by S ∞ := k≤0 S k . Let us define three hierarchies of sets G k , Q k and C k as follows. A probabilistic model p on H belongs to G k (H) is there exists a certificate of order k for p satisfying Normalization; it belongs to Q k (H), if there exists a certificate of order k satisfying Normalization and Orthogonality; and it belongs to C k (H) if there exists a certificate of order k satisfying Normalization, Orthogonality and Commutativity. Our results show that these hierarchies converge to the expected sets [START_REF] Fritz | Probabilistic models on contextuality scenarios[END_REF].

Theorem 16 (Convergence of the hierarchies). For every contextuality scenario H = (V, E),

G ∞ (H) = G 1 (H) = G(H), Q ∞ (H) = Q(H), C ∞ (H) = C |V | (H) = C(H).
The hierarchies (G k ) k≥1 and (C k ) k≥1 both converge after a finite number of steps, and it is natural to ask whether the same holds for (Q k ) k≥1 . While a finite number of steps is indeed sufficient if there exists a finite-dimensional quantum model, it is an open question related to difficult problems in the theory of C * -algebras whether there exist contextuality scenarios H for which the hierarchy needs infinitely many steps to converge (see Section 8.3 of [AFLS15] for details).

Link between LO ∞ (H) and the quantum set

In the same way as LO ∞ (H) can be characterized via the Shannon capacity of the orthogonality graph Ort(H), weighted by the distribution p, the first level of the quantum hierarchy, Q 1 (H) can be characterized by the Lovasz function of Ort(H), weighted by p. More precisely, a probabilistic model p on the contextuality scenario H, belongs to Q 1 (H) if and only if ϑ(Ort(H), p) = 1.

For every graph G, and any choice of weight p for the vertices of G, it is known that Θ(G, p) ≤ ϑ(G, p), which immediately implies that for every contextuality scenario, Q 1 (H) ⊆ LO ∞ (H). This proves that the Local Orthogonality principle is not sufficient to recover the set of quantum correlations for arbitrary contextuality scenarios since

Q 1 (H) = Q(H) in general.

Bit commitment from no superluminal signaling

We now move on to possible cryptographic applications of the study of quantum correlations and nonlocality. This section discusses how security guarantees can be obtained from the no superluminal signaling (NSS) principle which states that no information carrier can travel faster than the speed of light. The whole field of quantum cryptography is based on the idea that quantum theory puts severe constraints on what an adversary can do, in particular, that there often exists a fundamental trade-off between the amount of information they can acquire and the disturbance on the physical systems this information is encoded on. This is what we saw in the previous chapter devoted to quantum key distribution. The reason we trust quantum cryptography is that we trust the quantum theory it relies on. Another pillar of modern physics is the law that no information can travel faster than the speed of light. It is sensible to ask whether this law allows one to perform cryptographic tasks with proven security. This is the theme we explore in this section. Since the NSS principle is related to special relativity, this field is referred to as "relativistic cryptography", even though no relativistic effects are exploited for this type of cryptography.

Context and history of the field

Let us first note that the NSS principe is closely related to the non-signaling principle that says that a local action performed in a laboratory cannot have an immediate influence outside of the lab. NSS is more precise since it gives an upper bound on the speed at which such an influence can propagate. The current goal of relativistic cryptography is to understand what cryptographic tasks can be achieved with information-theoretic security meaning that the schemes proposed cannot be attacked by any classical (or quantum) computers, even with infinite computing power. This is in contrast with currently deployed schemes, which most often rely on computational assumptions such as the hardness of factoring [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF]. In the future, it will perhaps make sense to consider hybrid scenarios involving both a relativistic and a more conventional (based on such hardness assumptions) components, but as we will see, it is premature to consider such scenarios today, since we are far from completely understanding what can be achieved from the NSS principle alone.

The idea of exploiting the NSS principle for cryptographic protocols originated in a pioneering work by Kent in 1999 [START_REF] Kent | Unconditionally secure bit commitment[END_REF] as a way to physically enforce a non communic-ation constraint between the different agents of one party (the idea of splitting up a party into several agents dates back to [START_REF] Ben-Or | Multiprover interactive proofs: How to remove intractability assumptions[END_REF], but without an explicit implementation proposal). The main idea is to ask questions to several agents in a synchronized fashion, to make sure that their respective answer cannot depend on the questions asked to the other agents. This is in this sense that the NSS principle puts nontrivial constraints on what a coalition of agents can achieve. The original goal of Kent was to bypass the wellknown no-go theorems for quantum bit-commitment [START_REF] Mayers | Unconditionally secure quantum bit commitment is impossible[END_REF], [START_REF] Lo | Is quantum bit commitment really possible?[END_REF]. Bit commitment is a natural two-party cryptographic primitive where one player, Alice, commits to a bit and unveils its value after some sustain time. A bit commitment protocol is deemed to be secure if it satisfies two properties: (i) it should be hiding, which means that the second player, Bob, should not be able to learn the value of the bit before Alice reveals it; and (ii) it should be binding, meaning that Alice should not be able to change her mind during the sustain time and reveal a value different from the one she committed to. It is well-known that informationally-secure bit commitment cannot be obtained in the standard (classical) model and the early success of quantum key distribution raised the hope that quantum theory could once more provide security for a protocol involving the exchange of quantum states. Some quantum bit commitments were studied in the 90s but attacks were always found, until the works of Mayers, and Lo and Chau put an end to this line of work: no quantum bit commitment protocol can be both hiding and binding [START_REF] Mayers | Unconditionally secure quantum bit commitment is impossible[END_REF], [START_REF] Lo | Is quantum bit commitment really possible?[END_REF].

With his work, Kent managed to circumvent these no-go theorems by changing the rules of the game and imposing timing constraints on the exchanges performed by the various participants [START_REF] Kent | Unconditionally secure bit commitment[END_REF]. The main novelty of this work was to split Alice and Bob into coalitions of agents who would exchange messages in a synchronized fashion. An important concept in the context of cryptography is that the NSS puts limits on the information available to the agents, but only during a very limited time, corresponding to the time that light needs to reach the agents in question. For bit commitment, it means that if Alice's agents (as well as Bob's agents) are separated by some distance d, then they all have access to full information after a time at most d/c, where c is the speed of light. This time is therefore an upper bound on the sustain time of the protocol. In order to allow for longer sustain times, multi-round protocols are required. For instance, an N -round protocol will allow for a sustain time of order N d/c. Interestingly, the original protocol of Kent was classical in the sense that all the communication only involved classical messages and allowed for several rounds which increased the lifespan of the protocol. However, the protocol required to exchange messages whose length scaled exponentially in the number of rounds (i.e., the commitment time) and a feasible implementation was not possible for a large number of rounds. A subsequent work [START_REF] Kent | Secure classical bit commitment using fixed capacity communication channels[END_REF] improved this scaling, but to our knowledge, no precise time/security tradeoff is available for this protocol. More recently, quantum relativistic bit commitment protocols were developed where the parties exchange quantum systems, with the hope that combining the no superluminal signaling principle with quantum theory will lead to more secure (but less practical) protocols [START_REF] Kent | Unconditionally secure bit commitment with flying qudits[END_REF], [START_REF] Kent | Unconditionally secure bit commitment by transmitting measurement outcomes[END_REF], [START_REF] Kaniewski | Secure bit commitment from relativistic constraints[END_REF]. In particular, the protocol [START_REF] Kent | Unconditionally secure bit commitment by transmitting measurement outcomes[END_REF] was implemented in Ref. [LKB + 13].

The original idea of [START_REF] Ben-Or | Multiprover interactive proofs: How to remove intractability assumptions[END_REF] was recently revisited by Crépeau et al. [START_REF] Crépeau | Two provers in isolation[END_REF] (see also [START_REF] Simard | Classical and quantum strategies for bit commitment schemes in the two-prover model[END_REF]). Based on this work, Lunghi et al. devised a multi-round bit commitment protocol involving only four agents, two for Alice and two for Bob [LKB + 15]. They managed to prove that this protocol, which we call the "F Q protocol" from now on, remains secure for several rounds, against classical attacks. Unfortunately, this proof was rather inefficient since the complexity of the protocol (the size of the messages the agents need to exchange at each round) scaled exponentially with the number of rounds. Recently, together with Kaushik Chakraborty and André Chailloux, we improved the security proof and showed that the complexity of the protocol in fact only scales logarithmically with the number of rounds citeCCL15 (see also the independent work of Fehr and Fillinger [START_REF] Fehr | On the composition of two-prover commitments, and applications to multi-round relativistic commitments[END_REF]), implying that the commitment time is essentially unlimited:

Theorem 17 ([CCL15], [FF15]). The F Q relativistic r-round bit commitment protocol is ε-secure with ε = O N Q 1/2 against classical adversaries.
The number of bits exchanged at each round is log 2 (Q), which can be taken equal to 2(log(1/ε) + log(N )) in order to perform the protocol over r rounds with security parameter . This security proof is based on an analysis of CHSH Q , a non-signaling game that generalizes the well-known CHSH game to the case where inputs and outputs are not restricted to being bits, but rather belong to F Q the Galois Field of order Q. We discuss it in the next subsection.

Relativistic bit commitment protocols

We will first describe the single-round protocol (with commitment time bounded by τ = d/c where d is the distance between the distant locations and c is the speed of light), before focussing on the F Q multi-round protocol.

To simplify the analysis, we consider here that all computations are performed instantaneously and that information travels at the speed of light. One could relax these assumptions by replacing τ by a smaller constant, but this would not change the various scalings of parameters and we therefore ignore this issue here.

The protocols we consider are all perfectly hiding in the sense that Bob has no information about the committed values before the reveal step. An important consequence is that the spatial configuration of the agents needs only to be checked by Bob: in particular, it is sufficient for Bob to make sure that his agents are at a distance at least d from each other. If this is the case, and if Alice's agents answer their challenges in time, then Bob can deduce that her agents are also separated by a distance d.

The single-round protocol. The single-round version of the protocol was introduced by Crépeau et al. [START_REF] Crépeau | Two provers in isolation[END_REF] (see also [START_REF] Simard | Classical and quantum strategies for bit commitment schemes in the two-prover model[END_REF]). Both players, Alice and Bob, have agents A 1 , A 2 and B 1 , B 2 present at two spatial locations, L 1 and L 2 , separated by a distance d. We consider the case where Alice makes the commitment. The protocol (followed by honest players) consists of four phases: preparation, commit, sustain and reveal. The sustain phase in the single-round protocol is trivial and simply consists in waiting for a time less than τ , which is the time needed for light to travel between the two locations.

Overall the bit commitment protocol goes as follows.

Preparation phase: A

1 , A 2 (resp. B 1 , B 2 ) share a random number a ∈ F Q (resp. b ∈ F Q ).
2. Commit phase: B 1 sends b to A 1 , who returns y = a + c * b where c ∈ F 2 is the committed bit. Here and everywhere in this paper, all operations like + and * are understood as addition and multiplications in F Q .

3. Sustain phase: A 1 and A 2 wait for some time less than τ .

Reveal phase:

A 2 reveals the values of c and a to B 2 who checks that y = a + c * b.

The F Q -protocol (multi-round). The single-round protocol above was recently extended to a multi-round commitment scheme [LKB + 15]. The main idea to increase the commitment time is to delay the reveal phase and have A 2 commit to the string a instead of revealing it. In fact, the new sustain phase will now consist of many rounds where the active agents (i.e., the agent of Alice who commits in that given round and the corresponding agent for Bob) alternate between locations L 1 and L 2 . Overall, the required number of rounds scales linearly with the commitment time one wishes to achieve. The k-round bit commitment protocol goes as follows (for k even):

1. Preparation phase: We require that round j finishes before any information about b j-1 reaches the other Alice: this is where we exploit the NSS principle (see Figure 2.2). For any j, this implies that Alice's active agent has no information about b j-1 . In particular, this means that y j is independent of b j-1 .

A 1 , A 2 (resp. B 1 , B 2 ) share k random numbers a 1 , . . . , a k (resp. b 1 , . . . , b k ) ∈ F Q .
Security of the F Q -protocol. In order to prove that the protocols above are secure, it is sufficient to prove that they are binding. This is a consequence of the fact that the CHSH Q nonlocal game cannot be won perfectly. In this game introduced by Buhrman and Massar [START_REF] Buhrman | Causality and tsirelson's bounds[END_REF], two non-communicating parties, Adeline and Bastian, each receive an input string x and y from F Q chosen uniformly at random. They respectively output strings a and b in F Q and win the game if their outputs satisfy a + b = x * y, where + ). In particular, Bavarian and Shor [START_REF] Bavarian | Information causality, szemeréditrotter and algebraic variants of chsh[END_REF] proved an upper bound on the quantum value ω * of the game, that is the maximum winning probability if both players (which correspond to Alice's agents in a cheating strategy) share an entangled state:

ω * (CHSH Q ) ≤ 1 Q + Q -1 Q 1 √ Q .
This essentially implies the security of the single-round protocol against classical or quantum adversaries.

Proving that the multi-round protocol remains binding is more involved as the two cheaters are now asked to win a multi-round game, which might be a much easier task. If one restricts the adversaries to be classical (i.e., not sharing an entangled state), it is possible to reduce the security of the protocol to the analysis of a variant of the CHSH Q game where the inputs are not uniform anymore. In [START_REF] Chakraborty | Arbitrarily long relativistic bit commitment[END_REF], we showed that the classical value ω of CHSH Q games where one of the inputs is biased with maximum probability p is

ω(CHSH Q (p)) ≤ p + 2 Q .
This result allowed us to establish Theorem 17 which proves the security of the F Q protocol against classical adversaries. The remarkable feature of this result is that the protocol turns out to be very practical, contrary to previous intuition based on the works of Kent. In particular, a convincing experiment recently demonstrated the possibility of sustaining a commitment for 24 hours [VMH + 16], consisting of 5 × 10 9 rounds.

Robust version of the F Q protocol. In a subsequent work [START_REF] Chakraborty | Robust relativistic bit commitment[END_REF], we introduced a new relativistic bit commitment protocol that addresses one of the main weaknesses of the F Q protocol, namely its fragility against network failures. Indeed, the F Q protocol aborts as soon as one agent fails to respond to a single challenge in time. We fixed this issue by modifying the F Q protocol so that each party is now represented by 3 agents in 3 distinct locations. The communication cost of this variant is relatively modest, but the gain in terms of tolerance to loss is very good: one obtains a quadratic gain for the expected number of rounds that the protocol can sustain, making it very promising for implementations in real telecom networks (instead of dedicated networks), which is crucial for a possible future deployment of this technology.

Application to zero-knowledge proofs for NP

An example of application of bit commitment is in the context of zero-knowledge proofs.

The goal here is for a prover to convince a verifier that a statement is true, without conveying any information other than the fact that the statement is indeed true. A particularly relevant class of problems is the class NP of decision problems for which instances with a yes answer admit a proof that is efficiently verifiable. Zero-knowledge proofs are interactive protocols that usually involve a bit commitment scheme. It is therefore natural to investigate whether the relativistic (single-round) bit commitment considered above is useful in this context. In Ref. [START_REF] Chailloux | Relativistic (or 2-prover 1-round) zero-knowledge protocol for N P secure against quantum adversaries[END_REF], we showed that the zero-knowledge construction for Hamiltonian Cycle remains secure against quantum adversaries in the relativistic setting. Since Hamiltonian Cycle is an NP-complete problem, our result provides zero-knowledge proofs secure against quantum adversaries for the whole class NP.

It was not a priori clear that the relativistic bit commitment would allow for such zero-knowledge proofs. Indeed, the security definition of the bit commitment protocol is rather weak and does not "compose" well in the sense that it does not imply that the security of a larger protocol using the bit commitment scheme as an elementary brick will automatically inherit the security of that scheme. In order to prove our result, we developed a new tool for studying the action of consecutive measurements on a quantum state, which in turn yields upper bound on the entangled value of some nonlocal games. In particular, we obtained the following generalization of the gentle measurement lemma [START_REF] Winter | Coding theorem and strong converse for quantum channels[END_REF] (albeit with a worse constant).

Theorem 18 ([CL16]

). Let P 1 , . . . , P n be n projectors which can be written as P k = S s=1 P s k with P s k P s k = δ s,s P s k , for all k, s, s . Let σ be an arbitrary density matrix and define V := 1 n n k=1 tr(σP k ) and E :=

1 n(n-1) k, =k S s,s tr(P s P s k σP s k P s ). Then it holds that E ≥ 1 64S V - 1 n 3 .
The quantities V and E quantify the disturbance cause by one, or 2 consecutive measurements, respectively: they are close to 1 if the state is almost not disturbed and much smaller otherwise. The case of n = 2 can be seen as a worst-case consecutive measurement theorem: how much can the first measurement disturb the measured state before the second measurement? However, for larger values of n, this shows that when we pick 2 measurements out of n, the disturbance is much smaller, as shown by the dependence of the lower bound in n. Our theorem also improves on known results since it deals with larger values of S. Interestingly, this kind of statement has already appeared previously in a paper by Unruh [START_REF] Unruh | Quantum proofs of knowledge[END_REF], who studied quantum sigma protocols and in particular quantum proofs of knowledge.

The goal of this work was to demonstrate that it is possible to plug in the F Q relativistic bit commitment protocol into the well-known zero-knowledge protocol for Hamiltonian Cycle due to Blum [Blu86]. This widens the possible applications for relativistic cryptography and raises the question of what other cryptographic tasks can benefit from the NSS principle.

Future work on relativistic cryptography

The security proof for the multi-round bit commitment protocol only holds against classical adversaries. Although the protocol is itself classical, it is quite possible that a cheating strategy becomes available if the agents of a cheating party share entanglement instead of classical randomness. And indeed, for the single-round protocol, allowing for entanglement slightly helps the cheating party since the entangled value of the CHSH Q game is a bit larger than its classical value. The main difficulty to extend the analysis to the quantum case is that the composition of the rounds is more complicated to handle because the history is not described by classical random variables anymore, but rather by quantum states. Technically, one has to analyze nonlocal games where the players are allowed to initially share an entangled state that can (weakly) depend on their input states. This is a rather uncommon scenario in the field of quantum cryptography and the tools needed to deal with it have not been developed yet.

Another important open question is to better understand what cryptographic primitives can be achieved via the NSS principle. In [START_REF] Chailloux | Relativistic (or 2-prover 1-round) zero-knowledge protocol for N P secure against quantum adversaries[END_REF], we have shown that zero-knowledge proofs could take advantage of the NSS principle. An obvious candidate is Oblivious Transfer, which cannot be informationally-secure using quantum theory alone [START_REF] Mayers | Unconditionally secure quantum bit commitment is impossible[END_REF], [START_REF] Lo | Is quantum bit commitment really possible?[END_REF]. Unfortunately, although this has not been formally proven so far, it seems unlikely that secure OT can be obtained in a relativistic setting. Other natural candidates which have not been studied so far are multipartite computation, electronic voting or password-based authentication schemes for instance.

Position-based quantum cryptography

In this third section, we turn our attention to another quantum cryptographic task: position verification. The goal of position-based cryptography is for an honest party to use her spatio-temporal position as her only credentials in a cryptographic protocol. In particular, Position Verification aims at verifying that a certain party, called the prover, holds a given position in space-time. Such a protocol typically goes as follows: a set of verifiers will coordinate and send some challenge to the prover, and it is expected that only someone sitting in the correct position can successfully pass the challenge.

Position verification protocols have been studied in the classical setting where the challenges are described by classical information, and it was shown in [CGMO09] that information-theoretic security could never be obtained in the standard model. More precisely, it is always possible for a coalition of adversaries to convince the verifiers, even if none of the adversaries sits in the spatio-temporal region where the prover is supposed to be. A possible way-out of this no-go theorem would be to consider a quantum setting.

Position-based cryptography in the quantum setting was first investigated under the name of quantum tagging by Kent around 2002, but only appeared in the literature much later in [START_REF] Kent | Quantum tagging: Authenticating location via quantum information and relativistic signaling constraints[END_REF] where attacks against possible quantum constructions are described. Malaney independently introduced a quantum position verification scheme in [START_REF] Robert | Quantum location verification in noisy channels[END_REF]. An example of a quantum protocol for position verification involves two verifiers V 0 and V 1 : V 0 sending a qubit |φ = U |x with x ∈ {0, 1} and U some unitary, and V 1 sending a classical description of the unitary U . The task for the prover is then to measure the qubit in the basis {U |0 , U |1 } and to return the classical value of x to both provers. There are many variations around this protocol, and the intuition for the possible security of such protocols is that only someone receiving both U and |φ can perform the required measurement, and return the correct value x on time. In [START_REF] Lau | Insecurity of position-based quantumcryptography protocols against entanglement attacks[END_REF], Lau and Lo extended the attack from [START_REF] Kent | Quantum tagging: Authenticating location via quantum information and relativistic signaling constraints[END_REF] to show that the above intuition is incorrect if the unitary U is a Clifford gate. In that case, a couple of cheaters, Alice lying between V 0 and the prover P , and Bob lying between V 1 and P , can always fool the verifiers provided that they share a small number of EPR pairs. This result was later generalized by Buhrman et al.

[BCF + 11] who showed that such an attack always exists provided that the coalition of cheaters share sufficiently many EPR pairs: no position-based quantum cryptographic protocol can display information-theoretic security.

Two general families of attacks against such position-verification protocols have been considered in the literature so far, both based on quantum teleportation. The first one is inspired by Vaidman's protocol for non-local computation [START_REF] Vaidman | Instantaneous measurement of nonlocal variables[END_REF] and consists in the cheaters teleporting some quantum state back and forth, with the number of exchanges depending on the success probability of the attack. If the position-based protocol involves n qubits, the resource (number of EPR pairs) required for this type of attacks to succeed typically scales double-exponentially with n [BCF + 11]. Another class of attacks uses port-based teleportation [START_REF] Ishizaka | Asymptotic teleportation scheme as a universal programmable quantum processor[END_REF] and requires only exponential entanglement to succeed [BK11]. If one could prove that such an attack was indeed optimal, one would obtain a secure position-based protocol for all practical purposes.

Establishing lower bounds for the amount of entanglement shared by the coalition in order to successfully attack the protocol is a non trivial task. Current lower bounds are linear in the security parameter of the protocol [BK11], [START_REF] Tomamichel | One-sided device-independent qkd and position-based cryptography from monogamy games[END_REF], [START_REF] Ribeiro | A tight lower bound for the bb84-states quantum-position-verification protocol[END_REF]. It was also shown by Unruh that security of some position-verification protocols could be established in the quantum random oracle model, that is if one has access to one-way functions [START_REF] Unruh | Quantum position verification in the random oracle model[END_REF].

Let us comment on some assumptions that we make in this work. Our main goal is to present some natural position verification protocols and to study general classes of attacks that can be carried out by coalitions of cheaters. While we try to be as general as possible, we think it is sensible to make some specific choices in order to simplify the analysis. For instance, we restrict our protocols to using qubit states, and more importantly, we consider one-dimensional protocols with only 2 verifiers. Most of our analysis would carry through to arbitrary qudit protocols involving many verifiers. We also decided to leave aside all the problems related to timing in order to focus on the genuinely quantum part of the procedure. This means that we consider that all communication (classical or quantum) is performed at the speed of light, and that all computation is instantaneous. These are obviously unrealistic assumptions, but dealing with more realistic ones can be done independently of the analysis we provide here (see for instance the work of Kent [START_REF] Kent | Quantum tasks in minkowski space[END_REF]). The main source of imperfection in a position verification protocol is the quantum channel between the verifiers and the prover, which can never be assumed to be perfect. In general, the channel is both lossy and noisy, which is why even an ideal prover cannot possibly pass the test perfectly. On the other hand, it makes sense to assume that the classical channels are essentially perfect (lossless and noiseless).

In this section, we investigate a family of protocols where the verifiers send respectively an n-qubit state |φ and unitary U is chosen from a family of n-qubit gates. The prover is asked to apply the unitary U , measure the resulting state U |φ in the computational basis and to send the measurement results to both verifiers. We present some new attacks against such protocols that might become particularly efficient when the position-verification protocol is practical for the honest prover, meaning that the family U is efficiently implementable.

A general family of position-verification protocols

Following the literature, we find it useful to describe the protocol in terms of distributed collaborative games, where two players, named Alice and Bob, independently receive some query from some referee, are allowed a single round of (bipartite) communication and need to output some answer. In the honest prover case, Alice and Bob hold the same spatial position and the prover has access to both their inputs. In the cheating coalition case, Alice and Bob only have access to their own input and their share of the entangled state and are only allowed one simultaneous round of communication. The main result of [BCF + 11] is that if Alice and Bob can win the game with arbitrarily many rounds of communication, then they can also win it with a single simultaneous round, provided that they are sufficiently entangled.

The main family of protocols we will consider corresponding to games denoted by G(n, U) where n refers to the number of qubits involved in the protocol and U is a set of n-qubit unitaries. The protocol G(n, U) consists of the following phases:

1. Preparation Phase:

(a) The verifier V 0 chooses an n-qubit unitary operator U ∈ R U and an n-bit string

x = (x 1 , . . . , x n ) ∈ R {0, 1} n . V 0 prepares |ψ = U |x , where |x = n i=1 |x i is a computational basis state.
(b) V 0 sends x and U to V 1 through some secure authenticated classical channel.

Execution Phase:

(a) V 0 sends the n qubit quantum state |ψ to prover P at time 0. V 1 sends the unitary U to P at time τ = 0.

(b) The prover P receives both |ψ and U at time τ = 1.

(c) After receiving |ψ and U , the honest prover P computes U † |ψ and measures it in computational basis, obtaining some outcome string y. P then sends back y to both V 0 and V 1 .

3. Verification Phase:

(a) The prover P wins the game if V 0 and V 1 receive the same string y at time τ = 2, and if the Hamming distance between x and y is less than ηn: d H (x, y) ≤ ηn.

In the literature, this family is often considered in the single qubit case, for instance with U = {id, H} where H is the Hadamard gate [START_REF] Chandran | Position based cryptography[END_REF], [BCF + 11], [START_REF] Ribeiro | A tight lower bound for the bb84-states quantum-position-verification protocol[END_REF]. Then it makes sense to repeat the protocol n times in order to build some statistics. Here, we are interested in the most general scenario and consider n-qubit gates. For such protocols, we show that there exists a trade-off between the complexity of the protocol for the honest prover and the resources needed to break the protocol for a coalition of cheaters.

Attacks strategies against position verification protocols

The attack strategies we consider have the following structure:

1. Alice and Bob initially share a (possibly entangled) initial bipartite state ρ AB of dimension to be specified later. Typically, ρ AB consists of many EPR pairs.

2. Alice intercepts the communication from V 0 , namely a quantum register ρ C (where C stands for challenge), as well as some classical information.

Bob intercepts the classical communication from

V 1 .
4. Depending on the classical information they received, Alice and Bob perform respectively a quantum measurement on their respective registers, AC and B.

5.

They forward all the classical information as well as the outcomes of the measurement to their partner.

6. Finally, upon receiving this information, they prepare and send their response to the verifiers.

The main question of interest is to decide how the dimension of ρ AB , and more particularly the entanglement of this state, scales with the parameters of the position verification protocol. This scenario allows us to see the cheating procedure as a distributed task, or game, where Alice and Bob are asked questions (possibly consisting of a quantum state), are allowed a single round of communication and are required to output some specific answer. They win the game if they fool the verifiers. We will give explicit attacks that may be efficient in the following practically relevant cases: (1) if U ⊆ C k (n), that is if the unitaries all belong to some low level k of the Clifford hierarchy, (2) if the unitaries in U can all be implemented with a quantum circuit with a fixed layout.

We note that these two cases correspond to protocols that appear to be practical for a honest prover. Indeed, gates in a low level of the Clifford Hierarchy are much easier to implement fault tolerantly than arbitrary gates. Moreover, if the quantum states are photonic states, and the honest prover uses integrated photonics to implement the unitaries in U, a fairly reasonable choice in practice, then it makes sense to fix some layout, that is an optical circuit consisting of single or 2-qubit gates for instance, and to obtain the family U by changing the value of the single and 2-qubit gates.

Attacks based on the Clifford hierarchy

The Clifford Hierarchy introduced in [GC99] is an infinite hierarchy of sets

C 1 (n) ⊂ C 2 (n) ⊂ • • • ⊂ C k (n) • • • of n-qubit
unitaries where C 1 (n) = P n corresponds to the Pauli group (on n qubits), and the higher levels are defined recursively by:

U ∈ C k+1 (n) if and only if U σU † ∈ C k (n) for all σ ∈ C 1 (n).
When n is clear from context, we simply write C k instead of C k (n) for the k th level of the Clifford hierarchy for n-qubit gates. It should be noted that the first two levels of the hierarchy are groups, namely the Pauli and the Clifford groups, whereas none of the higher levels are groups.

The gates from C 1 and C 2 can be "easily" implemented fault-tolerantly [START_REF] Gottesman | Stabilizer codes and quantum error correction[END_REF]. However, it is well known that they do not form a universal set for quantum computation. One therefore requires at least one gate from C 3 to obtain a universal set of gates. Not surprisingly, gates from C 3 or higher levels are usually much harder to implement faulttolerantly.

Let us first define the Clifford complexity of a family U of unitaries.

Definition 19. Let U be a set of n-qubit unitaries. We define the Clifford complexity of the set U, denoted by CC[U], to be the minimum number of EPR pairs that Alice and Bob must share to perfectly win the game G(n, U).

We obtain the following upper bound for the Clifford complexity of the k th level of the Clifford hierarchy, C k (n) [START_REF] Chakraborty | Practical position-based quantum cryptography[END_REF].

Theorem 20.

CC[C

1 (n)] = 0, CC[C 1 (n)] ≤ n, CC[C k (n)] ≤ 4n 4 n(k-2) for k ≥ 2.
(2.1)

Protocols with fixed layout circuit unitaries

The attack mentioned above is general and works for any n-qubit gate in some given level of the Clifford hierarchy. In the context of position verification protocols, however, the interesting set of gates U from which the unitary to be implemented is chosen, is often more restricted. Indeed, for the protocol to be practical, a honest prover should be able to implement the unitaries reasonably efficiently. For this reason, it is interesting to consider unitaries described by quantum circuits. In a practical scenario, where the quantum states given to Alice are photonic qubits, it makes sense to consider photonic implementations for the quantum circuit, and therefore to consider unitaries with a fixed layout for the quantum circuit, and adjustable single and two-qubit gates. This is typically the case for experimental implementations based on integrated photonics [START_REF] Jeremy | Photonic quantum technologies[END_REF].

For this reason, we define U L to be the set of unitaries described by a fixed layout L, and a specific unitary U ∈ U is then described by giving the value of each single or two-qubit gate in the layout. For a quantum circuit based on linear optics, the layout L corresponds to the position of the phase-shifters and beamsplitters, and the unitary is given by the specific values of the phase-shifts and transmission of the beamsplitters.

We obtain the following upper bound for the Clifford complexity of any layout, as a function of its depth and size [START_REF] Chakraborty | Practical position-based quantum cryptography[END_REF].

Theorem 21. Let L be the layout of an n-qubit quantum circuit of depth d where each layer consists of gates in

C k i . Then CC[U L ] ≤ 4 n d i=1 (k i -2) × (4n) d . (2.2)
In conclusion, we have established a connection between several well-studied quantum information processing tasks and position-based quantum cryptography. It was previously known that there exists some efficient attack when the verifiers choose the challenge unitary from Clifford group. In [START_REF] Chakraborty | Practical position-based quantum cryptography[END_REF], we showed that this remains true if the unitaries are chosen from a set that is easily implementable, a natural requirement for the protocol to be practical for a honest prover.

Chapter 3

Towards quantum fault-tolerance

In this chapter, we move away from cryptography and focus on quantum information processing tasks. We illustrate this broad theme through three topics: (i) a study of the effect of experimental imperfections on Boson Sampling, a non-universal model of quantum computing that has attracted a lot of attention in the community recently; (ii) a proposal for a family of quantum LDPC codes with an efficient decoding algorithm; and (iii) new quantum algorithms for the cryptanalysis of symmetric cryptosystems.

Error analysis for Boson Sampling

While quantum computers are widely believed to provide speed-ups over classical computers in theory, it remains an outstanding experimental challenge to provide hard evidence for such a speed-up. The BosonSampling problem, recently introduced by Aaronson and Arkhipov [START_REF] Aaronson | The computational complexity of linear optics[END_REF], makes a step in that direction: while being provably intractable on a classical computer (in its exact version) unless the Polynomial Hierarchy collapses to the third level, it can be efficiently solved with current linear optics technology (see Refs [BFRK + 13], [TDH + 13], [SMH + 13], [COR + 13] for recent experimental demonstrations).

Boson Sampling is a simple generalization of the two-photon Hong-Ou-Mandel effect, well-known in quantum optics [START_REF] Hong | Measurement of subpicosecond time intervals between two photons by interference[END_REF], to larger optical interferometers. Indeed, to an arbitrary unitary matrix U ∈ U(m), one can associate an interferometer consisting of beamsplitters and phase-shifters acting on m optical modes, which maps the annihilation operators a in = (a out 1 , . . . , a out m ) of the inputs modes to those, a out = (a out 1 , . . . , a out m ), of the output modes via the relation a out = U a in . Given such an interferometer corresponding to the unitary U , the Boson Sampling experiment consists in inputing the state |1, 1, . . . , 1, 0, 0, . . . , 0 containing a single photon in the first n modes, and the vacuum in the remaining m -n modes, and observing the photon number statistics in the output modes. Scheel [START_REF] Scheel | Permanents in linear optical networks[END_REF] showed that the probability of observing a sequence s = (s 1 , . . . , s m ) where s k photons are detected in the k th output mode by conservation of the photon number) is given by

P U ( s) = |Per(U s )| 2 s 1 ! • • • s m ! , (3.1)
where Per is the permanent and U s is the n × n matrix obtained from U by discarding all but the n first columns of U BS and then, for all k ∈ {1, . . . , m}, taking s k copies of the k th row of U . With these notations, we can define the BosonSampling problem:

BosonSampling(m, n)

Input: a unitary matrix U , drawn from the Haar measure on U(m),

Output: a sample s drawn from the distribution P U .

As we mentioned, it is straightforward to solve this problem (approximately) with linear optics: the idea is that the unitary U can be decomposed in the product of a polynomial number of 2 × 2 unitaries corresponding to beamsplitters [START_REF] Reck | Experimental realization of any discrete unitary operator[END_REF]. Then one simply needs to process the state |1 ⊗n |0 ⊗(m-n) through the corresponding optical network and count the number of photons in each output mode (see Fig. 3.1).

The catch here is that due to unavoidable experimental imperfections, one cannot hope to solve the problem exactly, but only approximately. Classical hardness of the approximate version of the problem is still believed to hold but depends on two mathematical conjectures saying that the permanent of random Gaussian matrices is not too concentrated around its expected value, and that approximating the permanent of a random Gaussian matrix is a P-complete problem (see Ref. [START_REF] Aaronson | The computational complexity of linear optics[END_REF] for details). If both conjectures hold, in order to provide evidence for quantum superiority, one still needs to perform an experiment solving the approximate version of the BosonSampling problem. This means that the various sources of errors in the experiment should not alter the output distribution too much compared to p U . Various sources of imperfection can be considered: (i) single photons not perfectly indistinguishable; (ii) losses; (iii) imperfect detection efficiency; (iv) beamsplitters and phase shifters not implementing exactly the desired transformation. Note that the effect of losses, imperfect detection and imperfect sources sending vacuum with a nonzero probability can be treated similarly (provided that these imperfections are invariant under a permutation of the modes). According to Refs [START_REF] Peter | Error tolerance of the bosonsampling model for linear optics quantum computing[END_REF], [START_REF] Peter P Rohde | Optical quantum computing with photons of arbitrarily low fidelity and purity[END_REF], the lossy variant of BosonSampling remains a hard problem classically, provided the losses are not too large: one can then use postselection to recover the original problem, and this postselection can be implemented efficiency is the number of single photons is on the order of 20 to 30.

In a work with Raúl Garciá-Patrón [LGP15], we focus on the impact of an imperfect calibration of the optical elements, leading to implementing an interferometer slightly different from the desired one. We therefore assume that the rest of the implementation is ideal: perfect photon sources, no losses, perfect detection. The question we ask is how accurate should the implementation of U be in order for the sampled distribution to be reasonably close to the ideal one? If this requirement cannot be met, then one will have to make the scheme fault-tolerant in order to solve the approximate version of BosonSampling, thereby losing one of the most appealing features of the scheme, namely the simplicity of its experimental implementation.

Our main result is that in order for the implementation to provide a reasonably good output distribution, the average fidelity of the elementary gates should scale at least like 1 -O(1/n 2 ). This result indicates that the faulty implementation might not be the main experimental concern for implementations where n ≈ 30, which should be sufficient to establish quantum superiority.

Model of noise and results

Using the algorithm of Ref. [START_REF] Reck | Experimental realization of any discrete unitary operator[END_REF], the unitary can be written U = U 1 • • • U N where N = m(m-1)/2 is the number of beamsplitters on Fig. 3.1. We consider a model of noise where each beamsplitter U k is replaced by a beamsplitter Φ(U k ) acting on the same two modes, where Φ : U(2) → U(2) is a random map acting identically and independently on each beamsplitter. The map Φ we use is such that Φ(U k )Φ(U † k ) = exp(iεh k ), where ε ≥ 0 controls the noise intensity, and h k is a 2 × 2 random Hermitian matrix drawn from the Gaussian Unitary Ensemble, i.e., h k =

α k γ k γ * k β k with α k , β k ∼ N (0, 1) R and γ k ∼ N (0, 1/2) C
. With this convention, the average fidelity of a beamsplitter is 1 -ε 2 . Denoting by Φ(U ) := Φ(U 1 ) • • • Φ(U N ) the unitary that is implemented in the lab, our goal is to study the trace distance between the ideal distribution and the real one, that is

E U E Φ P U -P Φ(U ) 1 ,
where we take the expectation over the Haar measure for U and over the noise Φ. Unfortunately, this quantity is really difficult to handle because it is the sum of an exponential number of exponentially small terms. Our solution around this problem consists in studying the implementation of the unitary U followed by that of U † (see Fig. 3.2): for a perfect implementation (ε = 0), this optical network implements the identity map, and

E U E Φ P U † U -P Φ(U † )Φ(U ) 1 = E U E Φ 2(1-p 1 ) = 2 1 -E U E Φ |Per([Φ(U ) • Φ(U † )] n×n )| 2 ,
where [A] n×n is the n × n upper left minor of A.

Our main result is:

Theorem 22. In the relevant regime where the number of modes m scales quadratically with n,

E U E Φ P U † U -P Φ(U † )Φ(U ) 1 = Ω(n 2 ε 2 ). (3.2)
Moreover, we conjecture that the bound is tight in the regime where n 2 ε 2 1. The proof of the theorem follows this strategy:

• the matrix Φ(U ) • Φ(U † ) can be written as exp(iεH N ) where H N is the N th element of a random walk on Hermitian matrices,

• using the Baker-Campbell-Haussdorff formula, one can write

H N = N k=1 Φ(U † n ) • • • Φ(U † k )h k Φ(U k ) • • • Φ(U N ),
• the permanent of the n × n upper left minor of e iεH N can be linked to E

x (1 m - Π n )H N Π n x 2
, where x = (e iθ 1 , . . . , e iθm ) is a random vector with θ k chosen uniformly from [0, 2π], and Π n is the projector of the subspace spanned by the first n vectors of the canonical basis of C m ,

• the quantity E

x E U E Φ (1 m -Π n )H N Π n
x 2 can be analyzed using two matrix concentration bounds due to Tropp [START_REF] Tropp | User-friendly tail bounds for sums of random matrices[END_REF]: the randomness linked to the noise Φ is dealt with a Gaussian matrix series while the randomness of the BosonSampling unitary is dealt with a matrix Chernoff bound.

One surprising aspect of our result is that the dependence of the noise on the parameters is not too bad: naively, one could have expected the error P U † U -P Φ(U † )Φ(U ) 1 to scale with nm, which is basically the number of relevant gates in an implementation (note indeed that all the gates which only act on vacuum in Fig. 3.1 do not affect the results). While we only have proven a lower bound on the error, we believe our analysis to be tight in the regime where n 2 ε 2 1. For reasonable values of n and m, for instance n ∼ 30 and m ∼ 1000, one expects the impact of imperfect calibration of the beamsplitters and phase-shifters to remain negligible (i.e., on the order of a few percents) if the fidelity of each elementary gate is typically on the order of 0.999. While certainly challenging, we do not expect such numbers to be a real problem in any forthcoming Boson Sampling experiment.

Quantum Expander Codes

We now move to the question of quantum error correcting codes, which definitely needs to be addressed if we ever want to build a large scale universal quantum computer.

In collaboration with Jean-Pierre Tillich and Gilles Zémor, we obtained in [START_REF] Leverrier | Quantum expander codes[END_REF] an efficient decoding algorithm for constant rate quantum hypergraph product LDPC codes which provably corrects adversarial errors of weight proportional to the code minimum distance, or equivalently to the square-root of the blocklength. The algorithm runs in time linear in the number of qubits, which makes its performance the strongest to date for linear-time decoding of quantum codes. The algorithm relies on expanding properties, not of the quantum code's factor graph directly, but of the factor graph of the original classical code it is constructed from.

Quantum LDPC and CSS codes

A quantum CSS code is a particular instance of a quantum stabilizer code, and can be defined by two classical binary linear codes C X and C Z in the ambient space F n 2 , with the property that C ⊥ X ⊂ C Z and C ⊥ Z ⊂ C X . In other words, the classical codes C X and C Z come together with respective parity-check matrices H X and H Z such that the linear space R X = C ⊥ X generated by the rows of H X is orthogonal to the row space R Z = C ⊥ Z of H Z , where orthogonality is with respect to the standard inner product. An error pattern is defined as a couple (e X , e Z ), where e X and e Z are both binary vectors. The decoder is given the pair of syndromes σ X = H X e T X and σ Z = H Z e T Z and decoding succeeds if it outputs, not necessarily the initial error pattern (e X , e Z ), but a couple of the form (e X + f X , e Z + f Z ) where f X ∈ R Z and f Z ∈ R X . See [START_REF] Gottesman | Stabilizer codes and quantum error correction[END_REF] for the equivalence with the stabilizer formalism and a detailed introduction to quantum coding.

If efficient quantum computing is to be achieved, it will come with a strong errorcorrecting component, that will involve very fast decoders, probably in not much more than linear time in the blocklength n. The likeliest candidates for this task are quantum LDPC codes: in the CSS case, an LDPC code is simply a code whose above paritycheck matrices H X and H Z have row and column weights bounded from above by a constant. Among recent developments, the recent paper [START_REF] Gottesman | Fault-tolerant quantum computation with constant overhead[END_REF] has shown how fault tolerant quantum computation with constant multiple overhead can be obtained, and quantum LDPC codes are an essential component of the scheme, making them possibly even more appealing.

It is natural to hope that the success of classical LDPC codes, both in terms of performance and of decoding efficiency, can eventually be matched in the quantum setting. This agenda involves two major difficulties, however. The first one is that coming up with intrinsically good constructions of quantum LDPC codes is in itself a challenge. In particular the random constructions that can be so effective in the classical case do not work at all in the quantum case. Indeed if one chooses randomly a sparse parity-check matrix H X , then, precisely since this gives a good classical code, there are no low-weight codewords in the dual of the row-space of H X and therefore an appropriate matrix H Z does not exist. Presently, the known constructions of families of quantum LDPC codes that come with constant rates and minimum distances that grow with the qubit length can be reduced to essentially three constructions. The first consists of quantum codes based on tilings of two-dimensional hyperbolic manifolds (surfaces) that generalise Kitaev's toric code and originate in [START_REF] Michael H Freedman | Z2-systolic freedom and quantum codes[END_REF]. The minimum distance of these codes grows as log n, where n is the qubit length. A recent generalisation of this approach to 4dimensional hyperbolic geometry [START_REF] Guth | Quantum error correcting codes and 4-dimensional arithmetic hyperbolic manifolds[END_REF] yields minimum distances that behave as n ε with ε ∈ [0.2, 0.3] [Mur16]. Finally, the construction [START_REF] Tillich | Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength[END_REF] yields codes of constant rate with minimum distances that grow as n 1/2 . These codes are perhaps the closest to classical LDPC codes in spirit, since they are constructed by taking a properly defined product of a classical LDPC code with itself. We note that all known constructions of quantum codes, even if they are allowed to have vanishing rate, fail to significantly break the n 1/2 barrier for the minimum distance and it is an intriguing open question as to whether there exist asymptotically good quantum LDPC codes (i.e., with constant rate and minimum distance linear in n). We also make the side remark that Gottesman [START_REF] Gottesman | Fault-tolerant quantum computation with constant overhead[END_REF] requires, for the purpose of fault-tolerant quantum computation, constant rate LDPC codes with good minimum distance properties that should behave well under some sort of adversarial error setting.

The second difficulty in attempting to match the achievements of classical LDPC coding, is to devise efficient decoding algorithms. The vast majority of decoding algorithms developed for classical LDPC codes rely on iterative techniques whose ultimate goal is to take decisions on individual bits. A straightforward transposition to the quantum setting of this strategy would consist in trying to recover the bits of e X and e Z by decoding the LDPC codes C X and C Z . The problem with this approach is that the classical LDPC codes C X and C Z are somewhat non-standard in that they have by construction bounded minimum distance. Indeed, C X has minimum distance at most equal to the smallest row weight of H Z since C ⊥ Z ⊂ C X and by definition C ⊥ Z is generated by the rows of H Z . Such a decoder for C X is doomed to fail because it is fooled by any error that spans only half the weight of a row of H Z [START_REF] Poulin | On the iterative decoding of sparse quantum codes[END_REF]. In other words, such decoding algorithms can not have vanishing error probability.

The way to overcome this problem is really to look for the most likely error modulo the stabilizer group. However this also implies that bit-oriented decoding strategies are mostly pointless, there is here no "correct value" for a single bit of e X or e Z which can always be just as well 0 or 1. Decoding quantum LDPC codes requires therefore additional elements to the classical toolkit.

Decoding quantum LDPC codes seems to be easier in one case, namely for the surface codes mentioned above. This is due to the fact that the underlying classical codes C X and C Z are cycle codes of graphs: full decoding, which is NP-hard in general for linear codes, can be achieved for cycle codes of graphs in polynomial time (with the help of Edmonds' weighted matching algorithm [START_REF] Edmonds | Paths, trees, and flowers[END_REF]), and this strategy (which does not really qualify as a local technique) yields a decoding scheme for the quantum code that achieves vanishing error-probability for random errors. Unfortunately, this technique does not extend to other classes of LDPC codes, and in an adversarial setting is limited to correcting at most log n errors, since the minimum distance of surface codes of constant rate can never surpass a logarithm of the qubit length [START_REF] Delfosse | Tradeoffs for reliable quantum information storage in surface codes and color codes[END_REF].

An alternative decoding algorithm was recently proposed [START_REF] Matthew | Decoding in hyperbolic spaces: quantum LDPC codes with linear rate and efficient error correction[END_REF] for the 4-dimensional hyperbolic codes of Guth and Lubotzky that is devised to work in a probabilistic setting and for which its adversarial performance is unclear. The third class of constant rate quantum codes with growing minimum distance, namely the codes [START_REF] Tillich | Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength[END_REF], had no known decoding algorithm to go with it and our goal in [START_REF] Leverrier | Quantum expander codes[END_REF] was to tackle this very problem.

Results and implications

We devised a decoding algorithm for the product codes [START_REF] Tillich | Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength[END_REF] that runs in linear time and decodes an arbitrary pattern of errors of any weight up to a constant fraction of the minimum distance, i.e., cn 1/2 for some constant c > 0. Our decoding algorithm is inspired by that of Sipser and Spielman [START_REF] Sipser | Expander Codes[END_REF] which applies to classical LDPC codes whose Tanner graph is an expander graph. The quantum codes under consideration here are products (in a well-defined sense) of a classical LDPC code C with itself, and we take the original code C to be an expander code. The resulting Tanner graphs of the two classical codes C X and C Z that make up the quantum code are not strictly speaking expander graphs, but they retain enough expanding structure from the original code for a decoding algorithm to work. Arguably, this is the first time that an import from classical LDPC coding theory succeeds in decoding a quantum LDPC code from a non-constant number of errors in an adversarial setting. There are some twists to the original Sipser-Spielman decoding scheme however, since it guesses values of individual bits and we have pointed out that this strategy cannot carry through to the quantum setting. The solution is to work with generators rather than qubits: the generators are the row vectors of H X and H Z . At each iteration, the decoding algorithm looks for a pattern of qubits inside the support of a single generator that will decrease the syndrome weight.

Our results also have some significance in the area of local testability. Locally Testable Codes (LTC) play a fundamental role in complexity theory: they have the property that code membership can be verified by querying only a few bits of a word [START_REF] Goldreich | Short locally testable codes and proofs: A survey in two parts[END_REF]. More precisely, the number of constraints not satisfied by a word should be proportional to the distance of the word from the code. Given their importance, it is natural to ask whether a quantum version of LTC exists, and to investigate their consequences for the burgeoning field of quantum Hamiltonian complexity, which studies quantum satisfaction problems [START_REF] Gharibian | Quantum Hamiltonian complexity[END_REF].

Quantum LTC were recently defined in [START_REF] Aharonov | Quantum locally testable codes[END_REF], and these hypothetical objects are mainly characterized by their soundness (or robustness) R(d), i.e., the probability that an error at distance d from the code violates a randomly chosen constraint. Ideally we would like to have this probability greater than some constant ε > 0 for d linear in the length n of the code. Note that a recent preprint of Hastings [START_REF] Hastings | Quantum codes from high-dimensional manifolds[END_REF] exhibits codes which are almost local and have soundness inverse logarithmic in n. While we do not exhibit such quantum LTC here, we construct codes which are robust for errors at distance to the code of order √ n, meaning that they violate a number of constraints which is linear in the distance. Reaching beyond the regime of moderate weight errors appears to be much harder since it is well-known that the random expander codes at the heart of our construction are not locally testable [START_REF] Ben-Sasson | Some 3CNF properties are hard to test[END_REF]. Interestingly, for our construction, better expansion translates into greater robustness. This should be seen in contrast to results in Ref. [START_REF] Aharonov | Commuting local Hamiltonians on expanders, locally testable quantum codes, and the qPCP conjecture[END_REF], [START_REF] Aharonov | Quantum locally testable codes[END_REF], where good expansion (admittedly not of the same graph) appears to hurt the local testability of the quantum codes. We also remark that in the very recent result of [START_REF] Eldar | Local hamiltonians whose ground states are hard to approximate[END_REF], quantum codes are constructed by applying [START_REF] Tillich | Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength[END_REF] to classical LTC, which leads to an alternative form of robustness where errors with small syndrome weight correspond to highly entangled states.

Open questions

We have exhibited a linear-time decoding algorithm that corrects up to Ω(n 1/2 ) adversarial quantum errors over n qubits. While this is the largest such asymptotic quantity to date, one would hope to break this barrier and eventually achieve correction of Ω(n) errors. If one were to do this with quantum LDPC codes, this would imply obtaining the elusive proof of existence of low-density codes with a minimum distance scaling linearly in the number of qubits.

Kovalev and Pryadko have shown [START_REF] Alexey | Fault tolerance of quantum lowdensity parity check codes with sublinear distance scaling[END_REF] that the codes of [START_REF] Tillich | Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength[END_REF] have the potential to correct number of random depolarizing errors that scales linearly in n, with a vanishing probability of decoding error. This is without decoding complexity limitations however, and a natural question is whether the ideas of the present paper can extend to decoding Ω(n) random errors in linear or quasi-linear time.

Quantum cryptanalysis of symmetric cryptosystems

In this last section, I move away from questions related to dealing with errors in quantum information processing to ask about possible applications of quantum computers. One of the best-known such applications is Shor's factoring algorithm [START_REF] Shor | Algorithms for quantum computation: Discrete logarithms and factoring[END_REF] which would break most of the cryptography currently deployed. Very broadly, there are two main approaches to encrypt information transiting on the internet: public key cryptography which is based on the hardness of certain mathematical problems such as factoring (in the case of RSA) or discrete-logarithm, both broken using Shor's algorithm if a universal quantum computer is available, and symmetric cryptography where the users exploit a short secret key to encrypt long messages. Intuitively, symmetric cryptography protocols are much less structured than RSA, and the best attack is believed to be a brute-force search of the secret key, which might be say 256-bit long. For this reason, quantum computers are expected to have limited impact on symmetric cryptography: the common wisdom is that the only possible speedup comes from Grover's search algorithm [START_REF] Lov | A fast quantum mechanical algorithm for database search[END_REF], which provides a quadratic advantage compared to classical attacks [START_REF] Daniel | Post-Quantum Cryptography, Third International Workshop[END_REF]. In particular, doubling the key length should be sufficient to restore the appropriate level of security. This picture turns out however, to be a little bit too simplistic, as we illustrated in two recent papers written in collaboration with Marc Kaplan, Gaëtan Leurent and María Naya-Plasencia [START_REF] Kaplan | Breaking symmetric cryptosystems using quantum period finding[END_REF], [START_REF] Kaplan | Quantum differential and linear cryptanalysis[END_REF].

Our most striking result is that Simon's algorithm [START_REF] Daniel R Simon | On the power of quantum computation[END_REF], which is the main subroutine of Shor's algorithm, can lead to devastating attacks against many widely used modes of operation for authentication and authenticated encryption [START_REF] Kaplan | Breaking symmetric cryptosystems using quantum period finding[END_REF]. Simon's algorithm provides an exponential speedup for an apparently rather contrived problem involving finding the period of a boolean function. What is remarkable is that instances of this very problem occur in the context of symmetric cryptography with block ciphers, which correspond to permutations of {0, 1} n parameterized by a secret key k. If the block cipher is assumed to be secure, it means that the only possible attack to recover the key is a brute-force search over the key space. The size of the key is typically equal to the block length, for instance 256 bits. A mode of operation is an algorithm describing how such a block cipher can be used repeatedly to securely transform a message larger than the block size. It turns out that in many cases, depending how successive blocks are processed, a periodic boolean function can appear in the description of the mode of operation. Moreover, knowing the period of the function is sufficient to compromise the security of the whole scheme. Classically, this is not a problem since one requires Ω(2 n/2 ) queries to the block cipher of length n (seen as a black box) in order to recover the period. If one has a quantum access to the oracle, however, Simon's algorithm kicks in and allows the malicious party to recover the period with O(n) queries, which shows that the overall security of the scheme is quite compromised.

This "fully quantum" model of attacks where an adversary can perform quantum queries to the encryption device has been studied in the literature under the names of superposition attacks [START_REF] Damgård | Superposition attacks on cryptographic protocols[END_REF], quantum chosen message attacks [START_REF] Boneh | Secure signatures and chosen ciphertext security in a quantum computing world[END_REF] or quantum security [START_REF] Zhandry | How to construct quantum random functions[END_REF]. Of course, this model is not at all realistic, and even if quantum computers were available today, our result would not imply that all these modes of operations are broken. The model is very strong since it says that if one queries the algorithm with a superposition of quantum inputs, then the output is the superposition of the outputs. More precisely, if the oracle returns O k (x) for the input x, where k is the secret key, then the quantum oracle is assumed to prepare the state 1 2 n/2

x |x |O k (x) when queried with the uniform superposition 1 2 n/2

x |x |0 . It is rather unclear how to query a physical device in such a quantum manner, and quite hard to imagine that there exists a way to prevent decoherence to ensure that this superposition is indeed prepared. This is certainly true but there are at least two reasons for caring about such a model. First, in the future, assuming that quantum computers exist (which is a prerequisite for this study in the first place), it will make sense to design encryption schemes that can deal with quantum messages. In that case, our results show that the schemes currently deployed are vulnerable against quantum attacks relying on Simon's algorithm. The second reason why this model makes sense is that coming up with natural models of attacks that would be intermediate between the "all-classical" model and the "fully-quantum" model is nontrivial. How should one describe the behaviour of an encryption circuit when it is probed quantumly? It seems that requiring that full decoherence takes place immediately leads to a very weak model. Allowing the superposition to be preserved throughout is certainly unrealistic, but leads to a very clean model and security in this model certainly implies security in all other possible attack models one might want to consider. Let us finally point out that certain constructions of message authenticated codes are known to remain secure in that model [START_REF] Boneh | Quantum-secure message authentication codes[END_REF].

Our second result deals with "quantizing" well-known cryptanalysis techniques that have been developed against block ciphers [START_REF] Kaplan | Quantum differential and linear cryptanalysis[END_REF]. These are clever techniques that sometimes allow to recover the key without exploring the whole key space. One such example is differential cryptanalysis [START_REF] Biham | Differential cryptanalysis of des-like cryptosystems[END_REF]. These techniques are very useful for the design of new cryptosystems. Indeed, many block ciphers consist of applying many "rounds" of a simple transformation. The security of the cipher usually increases with the number of rounds, but of course, so is its complexity. For this reason, it is crucial to be able to choose the appropriate compromise between security and complexity. This is where cryptanalysis techniques come into play: they allow one to test the security of toy cryptosystems with a small number of rounds, and choose the number of rounds of the final design appropriately. In our project, we considered two models of quantum attacks: one similar to the fully-quantum model described above where one can query the oracle in superposition, and a second one where all queries are classical but the adversary has access to a quantum computer to process this classical data. Our techniques rely on the framework of quantum walks and we often obtain a quadratic speed-up compared to classical attacks, but not always. In fact, the situation is rather nuanced and the speed-up we obtain depend on the specific variants of the attacks that are considered. In particular, picking the best classical attack and applying a quadratic speed-up is not the right way to analyse the security of block ciphers in a world where quantum computers exist.

The conclusion of this work is that the claim that the only impact of quantum computing to the cryptanalysis of symmetric cryptography is restricted to the use of Grover's algorithm is not justified. For instance, in some models, it is possible to obtain an exponential speed-up over the best classical attacks, which is much more problematic than the quadratic speed-up promised by Grover. A difficulty here in contrast to the case of public key cryptography is that the security model matters a lot: how should one model that an adversary has access to a universal quantum computer? The fully quantum model is certainly very strong, but presents the advantage of encompassing all reasonable attack models. The question is then to develop cryptosystems that remain secure in that model. Some already exist for some specific functionalities and it seems worthwhile investigating this problem further.

Conclusion

We end by mentioning some open problems that seem worth studying in the coming years:

• on continuous-variable quantum cryptography: our recent results on Gaussian de Finetti theorem unveiled a duality between the groups U (n) and SU (p, q) acting on the n(p + q)-mode Hilbert space F p,q,n . While we exclusively focused on the symmetric subspace F U (n) p,q,n because of its natural application to cryptography, it is tempting to investigate this duality further. In particular, the Schur-Weyl duality between U (d) and the symmetric group S n acting on (C d ) ⊗n is a powerful tool in the context of quantum information, with more applications that the symmetric subspace. For this reason, it would be interesting to better understand the duality between U (n) and SU (p, q) beyond the study of F U (n) p,q,n .

• on relativistic cryptography: a natural follow-up of our work on bit commitment is to consider quantum cheating strategies. While we can prove the security of this protocol against quantum adversaries in the single-round case, which leads for instance to zero-knowledge proofs for NP, our proof techniques currently don't extend to several rounds. For this reason, we only obtain arbitrarily long commitment times when restricting adversaries to performing classical strategies, and it is a major open question to understand what is the power of entangled strategies in this context.

• on quantum error correcting codes: a natural follow-up question on our work on quantum expander codes is to investigate the behaviour of our efficient decoding algorithm against random errors. In particular, is there a finite value p 0 > 0 such that the decoder corrects all errors with high probability for the depolarizing channel of parameter p ≤ p 0 ? If true, this would have important applications in the theory of quantum fault-tolerance computation as such codes would reduce the overhead imposed by a fault-tolerant construction. A second question of great interest is to better understand whether good quantum LDPC codes exist, i.e. codes with constant rate and linear minimum distance. Right now, the best minimum distance for quantum LDPC codes scales like n 1/2 log 1/4 n [FML02] while some codes are conjectured to achieve a minimum distance of n 1-ε for any ε > 0 [START_REF] Hastings | Quantum codes from high-dimensional manifolds[END_REF].

  10) where dz := n k=1 2 i=1 dz k,i and dz := n k=1 2 j=1 dz k,j denote the Lebesgue measures on C 2n and C 2n , respectively, and |z|

Figure 2 . 1 -

 21 Figure 2.1 -The 16 events and 12 measurements of the CHSH scenario, B 2,2,2

2.

  Commit phase (round 1): B 1 sends b 1 to A 1 , who returns y 1 = a 1 + c * b 1 where c ∈ F 2 is the committed bit. 3. Sustain phase: at round j ≤ k, active Bob sends b j ∈ F Q to active Alice, who returns y j = a j + b j * a j-1 . 4. Reveal phase: A 1 reveals d and a k to B 1 . B 1 computes recursively α 0 = c and α i+1 = y i+1 -b i+1 * α i and checks that α k = a k . If this is the case, Alice has successfully revealed the bit c.

Figure 2 . 2 -

 22 Figure 2.2 -Description of the F Q protocol.

Figure 3

 3 Figure3.1 -Implementation of the Boson Sampling experiment, following the scheme of Ref.[START_REF] Reck | Experimental realization of any discrete unitary operator[END_REF], with input modes on the left and output modes on the right. In general, one would need both phase-shifters and beamsplitters. Here, for simplicity, we consider beamsplitters with complex entries. In other words, phase-shifters are absorbed in the beamsplitters.

Figure 3

 3 Figure 3.2 -Implementation of the unitary U followed by the unitary U † . A perfect implementation should leave the input state unchanged.

  One can also model imperfect preparation and measurement 1.2. A CV QKD PROTOCOL WITH HETERODYNE DETECTION Input: Alice and Bob have access to a quantum channel N A→B : A → B where A = A [n]and B [n] are comprised of n quantum systems. In practice, the channel will be an optical fiber. Alice sends the n-mode state ρ x through the quantum channel N and Bob receives the output state ρ x B = N (ρ x ).

	State Preparation: Alice chooses a random string x = (x 1 , • • • , x n ) ∈ R 2n where x k ∼ N (0, σ 2 ) and prepares the n-mode quantum state ρ x := n k=1 |x 2k + ix 2k+1 , where |α is the coherent state centered on α ∈ C, i.e., |α := e -|α| 2 /2 ∞ i=0 α i √ i! |i .
	State Distribution: Measurement: Bob measures the n optical modes corresponding to the output state
	with heterodyne detection and stores his measurement outcomes in a string y ∈
	R 2n .

Table 1

 1

	.1 -Prepare and Measure version of the CV QKD protocol with Gaussian mod-
	ulation of coherent states and heterodyne detection
	along the lines of [JKJDL12], [LBGP + 07], but we will assume here for simplicity that
	the devices behave perfectly. Another standard assumption in the CV QKD literature is
	that the eavesdropper cannot tamper with the Local Oscillator used for the measurement.
	This assumption might appear unjustified at first glance, which prompted some recent
	research on the development of local generation of the local oscillator at Bob's station
	[SBC + 15], [QLP + 15].

In fact, a proof that the sets LO ∞ (H) and Q(H) are not equal was found by Miguel Navascués before this formalism had been set up.

Acknowledgements