No description available.

We investigate weak coin flipping, a fundamental cryptographic primitive where two distrustful parties need to remotely establish a shared random bit. A cheating party can try to bias the output bit towards a preferred value. For weak coin flipping the parties have known opposite preferred values. By a weak coin flipping protocol with bias ϵ we mean that neither player can force the outcome towards their preferred value with probability more than 1/2+ϵ. While it is known that classically, ϵ=1/2 (the worst possible), Mochon showed in 2007 that quantumly, weak coin flipping can be performed with arbitrarily small bias (near perfect). His non-constructive proof used the so-called point game formalism—a series of equivalent reductions which were introduced by Kitaev to study coin-flipping. He constructed point games with bias ϵ(k)=1/(4k+2) to prove the existence. The best known explicit protocol, however, had bias approaching ϵ(1)=1/6 (also due to Mochon, 2005). In the present work, we try to make the non-constructive part of the proof constructive, to wit, we make three main contributions towards the conversion of point-games into explicit protocols. First, we propose a framework—TIPG-to-Explicit-protocol Framework (TEF)—which simplifies the task of constructing explicit protocols. We use this framework to construct a protocol with bias ϵ(2)=1/10. We then give the exact formulae for the unitaries corresponding to the point-games due to Mochon, allowing us to describe (almost) perfect coin flipping protocols analytically, i.e. with bias ϵ(k) for arbitrarily large k. Finally, we introduce an algorithm we call the Elliptic Monotone Align (EMA) algorithm. This algorithm, together with TEF, lets us convert any point-game into an explicit protocol numerically. We conclude by giving another analytic construction of unitaries for Mochon's games using the ellipsoid picture introduced for the EMA algorithm. / Nous étudions le weak coin flipping, une primitive cryptographique fondamentale où deux parties méfiantes doivent établir à distance un bit aléatoire partagé. Un tricheur peut essayer de biaiser le bit de sortie vers une valeur préférée. Pour le weak coin flipping, les parties ont des valeurs préférées opposées. Par un protocole de weak coin flipping avec biais ϵ, nous entendons qu'aucun des deux joueurs ne peut forcer le résultat vers sa valeur préférée avec une probabilité supérieure à 1/2+ϵ. Alors que l'on sait que classiquement, ϵ=1/2 (le pire possible), Mochon a montré en 2007 qu'un weak coin flipping quantique peut être effectué avec un biais arbitrairement faible (presque parfait). Sa preuve non constructive a utilisé le formalisme dit du jeu de points (point games)—une série de réductions équivalentes qui ont été introduites par Kitaev pour étudier le coin flipping. Il a construit des jeux de points avec un biais ϵ(k)=1/(4k+2) pour en prouver l'existence. Le protocole explicite le plus connu, cependant, avait un biais approchant ϵ(1)=1/6 (également dû à Mochon, 2005). Dans le présent travail, nous essayons de rendre la partie non constructive de la preuve constructive, c'est-à-dire que nous apportons trois contributions principales à la conversion des jeux de points en protocoles explicites. Premièrement, nous proposons un cadre—TIPG-to-Explicit-protocol Framework (TEF)—qui simplifie la tâche de construction de protocoles explicites. Nous utilisons ce cadre pour construire un protocole avec un biais ϵ(2)=1/10. Nous donnons ensuite les formules exactes des unitaires correspondant aux jeux de points dus à Mochon, ce qui nous permet de décrire analytiquement des protocoles de coin flipping (presque) parfaits, c'est-à-dire avec un biais ϵ(k) pour un k arbitrairement grand. Enfin, nous introduisons un algorithme que nous appelons le Elliptic Monotone Align (EMA) Algorithm. Cet algorithme, associé à TEF, nous permet de convertir numériquement tout jeu de points en un protocole explicite. Nous concluons en donnant une autre construction analytique des unitaires pour les jeux de Mochon en utilisant l'image ellipsoïdale introduite pour l'algorithme EMA. / Doctorat en Sciences de l'ingénieur et technologie / info:eu-repo/semantics/nonPublished

This dissertation studies two different aspects of two-player interaction in the model of quantum communication and quantum computation.First, we study two cryptographic primitives, that are used as basic blocks to construct sophisticated cryptographic protocols between two players, e.g. identification protocols. The first primitive is ''quantum bit commitment''. This primitive cannot be done in an unconditionally secure way. However, security can be obtained by restraining the power of the two players. We study this primitive when the two players can only create quantum Gaussian states and perform Gaussian operations. These operations are a subset of what is allowed by quantum physics, and plays a central role in quantum optics. Hence, it is an accurate model of communication through optical fibers. We show that unfortunately this restriction does not allow secure bit commitment. The proof of this result is based on the notion of ''intrinsic purification'' that we introduce to circumvent the use of Uhlman's theorem when the quantum states are Gaussian. We then examine a weaker primitive, ''quantum weak coin flipping'', in the standard model of quantum computation. Mochon has showed that there exists such a protocol with arbitrarily small bias. We give a clear and meaningful interpretation of his proof. That allows us to present a drastically shorter and simplified proof.The second part of the dissertation deals with different methods of proving lower bounds on the quantum query complexity. This is a very important model in quantum complexity in which numerous results have been proved. In this model, an algorithm has restricted access to the input: it can only query individual bits. We consider a generalization of the standard model, where an algorithm does not compute a classical function, but generates a quantum state. This generalization allows us to compare the strength of the different methods used to prove lower bounds in this model. We first prove that the ''multiplicative adversary method'' is stronger than the ''additive adversary method''. We then show a reduction from the ''polynomial method'' to the multiplicative adversary method. Hence, we prove that the multiplicative adversary method is the strongest one. Adversary methods are usually difficult to use since they involve the computation of norms of matrices with very large size. We show how studying the symmetries of a problem can largely simplify these computations. Last, using these principles we prove the tight lower bound of the INDEX-ERASURE problem. This a quantum state generation problem that has links with the famous GRAPH-ISOMORPHISM problem.

Cette thèse étudie deux aspects d'interaction entre deux joueurs dans le modèle du calcul et de la communication quantique.<p><p>Premièrement, elle étudie deux primitives cryptographiques quantiques, des briques de base pour construire des protocoles cryptographiques complexes entre deux joueurs, comme par exemple un protocole d'identification.<p><p>La première primitive est la "mise en gage quantique". Cette primitive ne peut pas être réalisée de manière inconditionnellement sûre, mais il est possible d'avoir une sécurité lorsque les deux parties sont soumises à certaines contraintes additionnelles. Nous étudions cette primitive dans le cas où les deux joueurs sont limités à l'utilisation d'états et d'opérations gaussiennes, un sous-ensemble de la physique quantique central en optique, donc parfaitement adapté pour la communication via fibres optiques. Nous montrons que cette restriction ne permet malheureusement pas la réalisation de la mise en gage sûre. Pour parvenir à ce résultat, nous introduisons la notion de purification intrinsèque, qui permet de contourner l'utilisation du théorème de Uhlman, en particulier dans le cas gaussien.<p><p>Nous examinons ensuite une primitive cryptographique plus faible, le "tirage faible à pile ou face", dans le modèle standard du calcul quantique. Carlos Mochon a donné une preuve d'existence d'un tel protocole avec un biais arbitrairement petit. Nous donnons une interprétation claire de sa preuve, ce qui nous permet de la simplifier et de la raccourcir grandement.<p><p>La seconde partie de cette thèse concerne l'étude de méthodes pour prouver des bornes inférieures dans le modèle de la complexité en requête. Il s'agit d'un modèle de complexité central en calcul quantique dans lequel de nombreux résultats majeurs ont été obtenus. Dans ce modèle, un algorithme ne peut accéder à l'entrée uniquement qu'en effectuant des requêtes sur chacune des variables de l'entrée. Nous considérons une extension de ce modèle dans lequel un algorithme ne calcule pas une fonction, mais doit générer un état quantique.<p><p>Cette généralisation nous permet de comparer les différentes méthodes pour prouver des bornes inférieures dans ce modèle. Nous montrons d'abord que la méthode par adversaire ``multiplicative" est plus forte que la méthode ``additive". Nous montrons ensuite une réduction de la méthode polynomiale à la méthode multiplicative, ce qui permet de conclure à la supériorité de la méthode par adversaire multiplicative sur toutes les autres méthodes.<p><p>Les méthodes par adversaires sont en revanche souvent difficiles à utiliser car elles nécessitent le calcul de normes de matrices de très grandes tailles. Nous montrons comment l'étude des symétries d'un problème simplifie grandement ces calculs.<p><p>Enfin, nous appliquons ces formules pour prouver la borne inférieure optimale du problème Index-Erasure, un problème de génération d'état quantique lié au célèbre problème Isomorphisme-de-Graphes. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

L'avènement de l'informatique quantique permet de réétudier les primitives cryptographiques avec une sécurité inconditionnelle, c'est à dire sécurisé même contre des adversaires tout puissants. En 1984, Bennett et Brassard ont construit un protocole quantique de distribution de clé. Dans ce protocole, deux joueurs Alice et Bob coopèrent pour partager une clé secrète inconnue d'une tierce personne Eve. Ce protocole a une sécurité inconditionnelle et n'a pasd'équivalent classique.Dans ma thèse, j'ai étudié les primitives cryptographiques à deux joueurs où ces joueurs ne se font pas confiance. J'étudie principalement le pile ou face quantique et la mise-en-gage quantique de bit. En informatique classique, ces primitivessont réalisables uniquement avec des hypothèses calculatoires, c'est-à-dire en supposant la difficulté d'un problème donné. Des protocoles quantiques ont été construits pour ces primitives où un adversaire peut tricher avec une probabilité constante strictement inférieure à 1, ce qui reste impossible classiquement. Néanmoins, Lo et Chau ont montré l'impossibilité de créer ces primitives parfaitement même en utilisant l'informatique quantique. Il reste donc à déterminer quelles sont les limites physiques de ces primitives.Dans une première partie, je construis un protocole quantique de pile ou face où chaque joueur peut tricher avec probabilité au plus 1/racine(2) + eps pour tout eps > 0. Ce résultat complète un résultat de Kitaev qui dit que dans un jeu de pile ou face quantique, un joueur peut toujours tricher avec probabilité au moins 1/racine(2). J'ai également construit un protocole de mise-en-gage de bit quantique optimal où un joueur peut tricher avec probabilité au plus 0,739 + eps pour tout eps > 0 puis ai montré que ce protocole est en fait optimal. Finalement, j'ai dérivé des bornes inférieures et supérieures pour une autre primitive: la transmission inconsciente, qui est une primitive universelle.Dans une deuxième partie, j'intègre certains aspects pratiques dans ces protocoles. Parfois les appareils de mesure ne donnent aucun résultat, ce sont les pertes dans la mesure. Je construis un protocole de lancer de pièce quantique tolérant aux pertes avec une probabilité de tricher de 0,859. Ensuite, j'étudie le modèle dispositif-indépendant où on ne suppose plus rien sur les appareils de mesure et de création d'état quantique.Finalement, dans une troisième partie, j'étudie ces primitives cryptographiques avec un sécurité computationnelle. En particulier, je fais le lien entre la mise en gage de bit quantique et les protocoles zero-knowledge quantiques. / Quantum computing allows us to revisit the study of quantum cryptographic primitives with information theoretic security. In 1984, Bennett and Brassard presented a protocol of quantum key distribution. In this protocol, Alice and Bob cooperate in order to share a common secret key k, which has to be unknown for a third party that has access to the communication channel. They showed how to perform this task quantumly with an information theoretic security; which is impossible classically.In my thesis, I study cryptographic primitives with two players that do not trust each other. I study mainly coin flipping and bit commitment. Classically, both these primitives are impossible classically with information theoretic security. Quantum protocols for these primitives where constructed where cheating players could cheat with probability stricly smaller than 1. However, Lo, Chau and Mayers showed that these primitives are impossible to achieve perfectly even quantumly if one requires information theoretic security. I study to what extent imperfect protocols can be done in this setting.In the first part, I construct a quantum coin flipping protocol with cheating probabitlity of 1/root(2) + eps for any eps > 0. This completes a result by Kitaev who showed that in any quantum coin flipping protocol, one of the players can cheat with probability at least 1/root(2). I also constructed a quantum bit commitment protocol with cheating probability 0.739 + eps for any eps > 0 and showed that this protocol is essentially optimal. I also derived some upper and lower bounds for quantum oblivious transfer, which is a universal cryptographic primitive.In the second part, I study some practical aspects related to these primitives. I take into account losses than can occur when measuring a quantum state. I construct a Quantum Coin Flipping and Quantum Bit Commitment protocols which are loss-tolerant and have cheating probabilities of 0.859. I also construct these primitives in the device independent model, where the players do not trust their quantum device. Finally, in the third part, I study these cryptographic primitives with information theoretic security. More precisely, I study the relationship between computational quantum bit commitment and quantum zero-knowledge protocols.

Cette thèse étudie deux aspects d'interaction entre deux joueurs dans le modèle du calcul et de la communication quantique.Premièrement, elle étudie deux primitives cryptographiques quantiques, des briques de base pour construire des protocoles cryptographiques complexes entre deux joueurs, comme par exemple un protocole d'identification. La première primitive est la ``mise en gage quantique". Cette primitive ne peut pas être réalisée de manière inconditionnellement sûre, mais il possible d'avoir une sécurité lorsque les deux parties sont soumis à certaines contraintes additionnelles. Nous étudions cette primitive dans le cas où les deux joueurs sont limités à l'utilisation d'états et d'opération gaussiennes, un sous-ensemble de la physique quantique central en optique, donc parfaitement adapté pour la communication via fibres optiques. Nous montrons que cette restriction ne permet malheureusement pas la réalisation de la mise en gage sûre. Pour parvenir à ce résultat, nous introduisons la notion de purification intrinsèque, qui permet de contourner l'utilisation du théorème de Uhlman, en particulier dans le cas gaussien. Nous examinons ensuite une primitive cryptographique plus faible, le ``tirage faible à pile ou face'', dans le modèle standard du calcul quantique. Carlos Mochon a donné une preuve d'existence d'un tel protocole avec un biais arbitrairement petit. Nous donnons une interprétation claire de sa preuve, ce qui nous permet de la simplifier et de la raccourcir grandement.La seconde partie de cette thèse concerne l'étude de méthodes pour prouver des bornes inférieures dans le modèle de la complexité en requête. Il s'agit d'un modèle de complexité central en calcul quantique dans lequel de nombreux résultats majeurs ont été obtenus. Dans ce modèle, un algorithme ne peut accéder à l'entrée uniquement en effectuant des requêtes sur chacun des bits de l'entrée. Nous considérons une extension de ce modèle dans lequel un algorithme ne calcule pas une fonction, mais doit générer un état quantique. Cette généralisation nous permet de comparer les différentes méthodes pour prouver des bornes inférieures dans ce modèle. Nous montrons d'abord que la méthode par adversaire ``multiplicative" est plus forte que la méthode ``additive". Nous montrons ensuite une réduction de la méthode polynomiale à la méthode multiplicative, ce qui permet de conclure à la supériorité de la méthode par adversaire multiplicative sur toutes les autres méthodes. Les méthodes par adversaires sont en revanche souvent difficiles à utiliser car elles nécessite le calcul de normes de matrices de très grandes tailles. Nous montrons comment l'étude des symétries d'un problème simplifie grandement ces calculs. Enfin, nous appliquons ces formules pour prouver la borne inférieure optimale du problème INDEX-ERASURE un problème de génération d'état quantique lié au célèbre problème GRAPH-ISOMORPHISM. / This dissertation studies two different aspects of two-player interaction in the model of quantum communication and quantum computation.First, we study two cryptographic primitives, that are used as basic blocks to construct sophisticated cryptographic protocols between two players, e.g. identification protocols. The first primitive is ``quantum bit commitment''. This primitive cannot be done in an unconditionally secure way. However, security can be obtained by restraining the power of the two players. We study this primitive when the two players can only create quantum Gaussian states and perform Gaussian operations. These operations are a subset of what is allowed by quantum physics, and plays a central role in quantum optics. Hence, it is an accurate model of communication through optical fibers. We show that unfortunately this restriction does not allow secure bit commitment. The proof of this result is based on the notion of ``intrinsic purification'' that we introduce to circumvent the use of Uhlman's theorem when the quantum states are Gaussian. We then examine a weaker primitive, ``quantum weak coin flipping'', in the standard model of quantum computation. Mochon has showed that there exists such a protocol with arbitrarily small bias. We give a clear and meaningful interpretation of his proof. That allows us to present a drastically shorter and simplified proof.The second part of the dissertation deals with different methods of proving lower bounds on the quantum query complexity. This is a very important model in quantum complexity in which numerous results have been proved. In this model, an algorithm has restricted access to the input: it can only query individual bits. We consider a generalization of the standard model, where an algorithm does not compute a classical function, but generates a quantum state. This generalization allows us to compare the strength of the different methods used to prove lower bounds in this model. We first prove that the ``multiplicative adversary method'' is stronger than the ``additive adversary method''. We then show a reduction from the ``polynomial method'' to the multiplicative adversary method. Hence, we prove that the multiplicative adversary method is the strongest one. Adversary methods are usually difficult to use since they involve the computation of norms of matrices with very large size. We show how studying the symmetries of a problem can largely simplify these computations. Last, using these principles we prove the tight lower bound of the INDEX-ERASURE problem. This a quantum state generation problem that has links with the famous GRAPH-ISOMORPHISM problem.