Uncertainty relations for multiple measurements with applications

Uncertainty relations express the fundamental incompatibility of certain observables in quantum mechanics. Far from just being puzzling constraints on our ability to know the state of a quantum system, uncertainty relations are at the heart of why some classically impossible cryptographic primitives become possible when quantum communication is allowed. This thesis is concerned with strong notions of uncertainty relations and their applications in quantum information theory.One operational manifestation of such uncertainty relations is a purely quantum effect referred to as information locking. A locking scheme can be viewed as a cryptographic protocol in which a uniformly random n-bit message is encoded in a quantum system using a classical key of size much smaller than n. Without the key, no measurement of this quantum state can extract more than a negligible amount of information about the message, in which case the message is said to be "locked". Furthermore, knowing the key, it is possible to recover, that is "unlock", the message. We give new efficient constructions of bases satisfying strong uncertainty relations leading to the first explicit construction of an informationlocking scheme. We also give several other applications of our uncertainty relations both to cryptographic and communication tasks.In addition, we define objects called QC-extractors, that can be seen as strong uncertainty relations that hold against quantum adversaries. We provide several constructions of QC-extractors, and use them to prove the security of cryptographic protocols for two-party computations based on the sole assumption that the parties' storage device is limited in transmitting quantum information. In doing so, we resolve a central question in the so-called noisy-storage model by relating security to the quantum capacity of storage devices.Les relations d'incertitude expriment l'incompatibilité de certaines observables en mécanique quantique. Les relations d'incertitude sont utiles pour comprendre pourquoi certaines primitives cryptographiques impossibles dans le monde classique deviennent possibles avec de la communication quantique. Cette thèseétudie des notions fortes de relations d'incertitude et leurs applications à la théorie de l'information quantique.Une manifestation opérationnelle de telles relations d'incertitude est un effet purement quantique appelé verrouillage d'information. Un système de verrouillage peut être considéré comme un protocole cryptographique dans lequel un message aléatoire composé de n bits est encodé dans un système quantique en utilisant une clé classique de taille beaucoup plus petite que n. Sans la clé, aucune mesure sur cet état quantique ne peut extraire plus qu'une quantité négligeable d'information sur le message, auquel cas le message est "verrouillé". Par ailleurs, connaissant la clé, il est possible de récupérer ou "déverrouiller" le message. Nous proposons de nouvelles constructions efficaces de bases vérifiant de fortes relations d'incertitude conduisant à la première construction explicite d'un système de verrouillage. Nous exposons également plusieurs autres applications de nos relations d'incertitude à des tâches cryptographiques et des tâches de communication.Nous définissons également des objets appelés QC-extracteurs, qui peuventêtre considérés comme de fortes relations d'incertitude qui tiennent contre des adversaires quantiques. Nous fournissons plusieurs constructions deQC-extracteurs, que nous utilisons pour prouver la sécurité de protocoles cryptographiques pour le calcul sécurisé à deux joueurs en supposant uniquement que la mémoire des joueurs soit limitée en ce qui concerne la transmission d'information quantique. Ce faisant, nous résolvons une question centrale dans le modèle de mémoire bruitée en mettant en relation la sécurité et la capacité quantique de la mémoire