Key Agreement Against Quantum Adversaries

Key agreement is a cryptographic scenario between two legitimate parties, who need to establish a common secret key over a public authenticated channel, and an eavesdropper who intercepts all their messages in order to learn the secret. We consider query complexity in which we count only the number of evaluations (queries) of a given black-box function, and classical communication channels. Ralph Merkle provided the first unclassified scheme for secure communications over insecure channels. When legitimate parties are willing to ask O(N) queries for some parameter N, any classical eavesdropper needs Omega(N^2) queries before being able to learn their secret, which is is optimal. However, a quantum eavesdropper can break this scheme in O(N) queries. Furthermore, it was conjectured that any scheme, in which legitimate parties are classical, could be broken in O(N) quantum queries. In this thesis, we introduce protocols à la Merkle that fall into two categories. When legitimate parties are restricted to use classical computers, we offer the first secure classical scheme. It requires Omega(N^{13/12}) queries of a quantum eavesdropper to learn the secret. We give another protocol having security of Omega(N^{7/6}) queries. Furthermore, for any k>= 2, we introduce a classical protocol in which legitimate parties establish a secret in O(N) queries while the optimal quantum eavesdropping strategy requires Theta(N^{1/2+k/{k+1}}) queries, approaching Theta(N^{3/2}) when k increases. When legitimate parties are provided with quantum computers, we present two quantum protocols improving on the best known scheme before this work. Furthermore, for any k>= 2, we give a quantum protocol in which legitimate parties establish a secret in O(N) queries while the optimal quantum eavesdropping strategy requires Theta(N^{1+{k}/{k+1}})} queries, approaching Theta(N^{2}) when k increases.

Multi-Prover and parallel repetition in non-classical interactive games

Depuis l’introduction de la mécanique quantique, plusieurs mystères de la nature ont trouvé leurs explications. De plus en plus, les concepts de la mécanique quantique se sont entremêlés avec d’autres de la théorie de la complexité du calcul. De nouvelles idées et solutions ont été découvertes et élaborées dans le but de résoudre ces problèmes informatiques. En particulier, la mécanique quantique a secoué plusieurs preuves de sécurité de protocoles classiques. Dans ce m´emoire, nous faisons un étalage de résultats récents de l’implication de la mécanique quantique sur la complexité du calcul, et cela plus précisément dans le cas de classes avec interaction. Nous présentons ces travaux de recherches avec la nomenclature des jeux à information imparfaite avec coopération. Nous exposons les différences entre les théories classiques, quantiques et non-signalantes et les démontrons par l’exemple du jeu à cycle impair. Nous centralisons notre attention autour de deux grands thèmes : l’effet sur un jeu de l’ajout de joueurs et de la répétition parallèle. Nous observons que l’effet de ces modifications a des conséquences très différentes en fonction de la théorie physique considérée.

Les niveaux et les facteurs déterminants de la mortalité infantile en Nouvelle-France et au début du Régime Anglais (1621-1779)

A l’époque de la Nouvelle-France, il n’était pas rare que des enfants de moins d’un an décèdent. Les parents acceptaient avec sagesse et résignation le décès de leurs enfants. Telle était la volonté du Tout-Puissant. Grâce au Registre de la Population du Québec Ancien (R.P.Q.A.) élaboré par le Programme de Recherche en Démographie Historique (P.R.D.H), l’ampleur de la mortalité infantile a pu être mesurée selon plusieurs critères, quelques facteurs déterminants examinés ainsi qu’une composante intergénérationnelle identifiée. Couvrant pour la première fois la totalité de l’existence de la colonie, nos résultats confirment l’importance de la mortalité des enfants aux XVIIe et XVIIIe siècles (entre 140 et 260‰ avant correction pour le sous-enregistrement des décès). Des disparités tangibles ont été constatées entre les sexes, selon le lieu de naissance ainsi que selon la catégorie professionnelle à laquelle appartient le père de l’enfant. L’inégalité des probabilités de survie des tout-petits reflète l’iniquité physiologique entre les genres, avec une surmortalité masculine de l’ordre de 20%, et l’influence de l’environnement dans lequel vit la famille : les petits de la ville de Québec décédaient en moyenne 1,5 à 1,2 fois plus que les petits des campagnes. Montréal, véritable hécatombe pour l’instant inexpliquée, perdait 50% de ses enfants avant l’âge d’un an, ce qui représente 1,9 fois plus de décès infantiles que ceux des enfants de la campagne, qui jouissent malgré tout des bienfaits de leur environnement. Les effets délétères de l’usage de la mise en nourrice, qui touche plus de la moitié des enfants des classes aisées citadines, ravagent leur descendance de plus en plus profondément. L’examen de la mortalité infantile sous ses composantes endogène et exogène révèle que la mortalité de causes exogènes explique au moins 70% de tous les décès infantiles. La récurrence des maladies infectieuses, l’absence d’hygiène personnelle, l’insalubrité des villes constituaient autant de dangers pour les enfants. Dans une perspective davantage familiale et intergénérationnelle où l’enfant est partie intégrante d’une fratrie, des risques significatifs ont été obtenus pour plusieurs caractéristiques déterminantes. Les mères de moins de 20 ans ou de plus de 30 ans, les enfants de rang de naissance supérieur à 8, un intervalle intergénésique inférieur à 21 mois ou avoir son aîné décédé accroissent les risques de décéder avant le premier anniversaire de l’ordre de 10 à 70%, parce que le destin d’un enfant n’est pas indépendant des caractéristiques de sa mère ou de sa fratrie. Nous avons aussi constaté une relation positive entre la mortalité infantile expérimentée par une mère et celle de ses filles. La distribution observée des filles ayant perdu au moins 40% de leurs enfants au même titre que leur mère est 1,3 à 1,9 fois plus grande que celle attendue pour les filles ayant eu 9 enfants et moins ou 10 enfants et plus. Il existerait une transmission intergénérationnelle de la mortalité infantile même lorsqu’on contrôle pour la période et la taille de la famille.

Etudes ab initio des effets de la température sur le spectre optique des semi-conducteurs

Thèse réalisée en cotutelle avec l'Université Catholique de Louvain (Belgique)

From Classical to Quantum Secret Sharing

Dans ce mémoire, nous nous pencherons tout particulièrement sur une primitive cryptographique connue sous le nom de partage de secret. Nous explorerons autant le domaine classique que le domaine quantique de ces primitives, couronnant notre étude par la présentation d’un nouveau protocole de partage de secret quantique nécessitant un nombre minimal de parts quantiques c.-à-d. une seule part quantique par participant. L’ouverture de notre étude se fera par la présentation dans le chapitre préliminaire d’un survol des notions mathématiques sous-jacentes à la théorie de l’information quantique ayant pour but primaire d’établir la notation utilisée dans ce manuscrit, ainsi que la présentation d’un précis des propriétés mathématique de l’état de Greenberger-Horne-Zeilinger (GHZ) fréquemment utilisé dans les domaines quantiques de la cryptographie et des jeux de la communication. Mais, comme nous l’avons mentionné plus haut, c’est le domaine cryptographique qui restera le point focal de cette étude. Dans le second chapitre, nous nous intéresserons à la théorie des codes correcteurs d’erreurs classiques et quantiques qui seront à leur tour d’extrême importances lors de l’introduction de la théorie quantique du partage de secret dans le chapitre suivant. Dans la première partie du troisième chapitre, nous nous concentrerons sur le domaine classique du partage de secret en présentant un cadre théorique général portant sur la construction de ces primitives illustrant tout au long les concepts introduits par des exemples présentés pour leurs intérêts autant historiques que pédagogiques. Ceci préparera le chemin pour notre exposé sur la théorie quantique du partage de secret qui sera le focus de la seconde partie de ce même chapitre. Nous présenterons alors les théorèmes et définitions les plus généraux connus à date portant sur la construction de ces primitives en portant un intérêt particulier au partage quantique à seuil. Nous montrerons le lien étroit entre la théorie quantique des codes correcteurs d’erreurs et celle du partage de secret. Ce lien est si étroit que l’on considère les codes correcteurs d’erreurs quantiques étaient de plus proches analogues aux partages de secrets quantiques que ne leur étaient les codes de partage de secrets classiques. Finalement, nous présenterons un de nos trois résultats parus dans A. Broadbent, P.-R. Chouha, A. Tapp (2009); un protocole sécuritaire et minimal de partage de secret quantique a seuil (les deux autres résultats dont nous traiterons pas ici portent sur la complexité de la communication et sur la simulation classique de l’état de GHZ).

The decoupling approach to quantum information theory

La théorie de l'information quantique étudie les limites fondamentales qu'imposent les lois de la physique sur les tâches de traitement de données comme la compression et la transmission de données sur un canal bruité. Cette thèse présente des techniques générales permettant de résoudre plusieurs problèmes fondamentaux de la théorie de l'information quantique dans un seul et même cadre. Le théorème central de cette thèse énonce l'existence d'un protocole permettant de transmettre des données quantiques que le receveur connaît déjà partiellement à l'aide d'une seule utilisation d'un canal quantique bruité. Ce théorème a de plus comme corollaires immédiats plusieurs théorèmes centraux de la théorie de l'information quantique. Les chapitres suivants utilisent ce théorème pour prouver l'existence de nouveaux protocoles pour deux autres types de canaux quantiques, soit les canaux de diffusion quantiques et les canaux quantiques avec information supplémentaire fournie au transmetteur. Ces protocoles traitent aussi de la transmission de données quantiques partiellement connues du receveur à l'aide d'une seule utilisation du canal, et ont comme corollaires des versions asymptotiques avec et sans intrication auxiliaire. Les versions asymptotiques avec intrication auxiliaire peuvent, dans les deux cas, être considérées comme des versions quantiques des meilleurs théorèmes de codage connus pour les versions classiques de ces problèmes. Le dernier chapitre traite d'un phénomène purement quantique appelé verrouillage: il est possible d'encoder un message classique dans un état quantique de sorte qu'en lui enlevant un sous-système de taille logarithmique par rapport à sa taille totale, on puisse s'assurer qu'aucune mesure ne puisse avoir de corrélation significative avec le message. Le message se trouve donc «verrouillé» par une clé de taille logarithmique. Cette thèse présente le premier protocole de verrouillage dont le critère de succès est que la distance trace entre la distribution jointe du message et du résultat de la mesure et le produit de leur marginales soit suffisamment petite.