An exploration of approximation chains

Abstract

La théorie de l'information à coup unique vise à étudier les tâches de communication et de traitement de l'information pour des états et des processus généraux avec une structure minimale. Une telle généralité est cruciale pour analyser les tâches de communication avec des ressources limitées et la sécurité des protocoles cryptographiques. Dans le régime asymptotique pour les tâches d'information avec une structure i.i.d. (indépendante et identiquement distribuée), les taux sont typiquement caractérisés par l'entropie de von Neumann et ses dérivées. Dans le régime à coup unique, une multitude d'entropies différentes sont nécessaires à cette fin. L'une des plus importantes est la min-entropie lisse, qui caractérise les taux des protocoles cryptographiques. Contrairement à l'entropie de von Neumann, le comportement de la min-entropie lisse est souvent contre-intuitif. Les outils de décomposition de la min-entropie lisse sont également assez restrictifs, rendant difficile l'analyse des structures qui émergent naturellement en théorie de l'information. Une telle structure, que nous appelons une chaîne d'approximation, constitue le thème central de cette thèse. Pour un état ρA1nB, nous appelons une séquence d'états (σA1kB(k))k=1n une chaîne d'approximation de ρ si pour chaque k, ρA1kB≈ϵσA1kB(k). Ces structures émergent fréquemment lors de l'incorporation d'approximations dans les identités entropiques, l'étude des imperfections et le développement de preuves de sécurité. Alors que l'entropie de von Neumann de ρ peut être facilement exprimée en termes d'entropies des états de sa chaîne d'approximation, il n'est généralement pas possible de le faire avec la min-entropie lisse. Dans cette thèse, nous développons des techniques pour établir des bornes entropiques avec des chaînes d'approximation et les appliquons à des scénarios cryptographiques. Notre travail commence par considérer l'un des cas les plus simples d'une telle chaîne, où les registres de ρ sont presque indépendants les uns des autres, et culmine avec l'établissement d'une règle de chaînage universelle pour la min-entropie lisse, qui permet de borner celle-ci en termes des entropies des états d'une chaîne d'approximation. De plus, nous prouvons deux versions approximatives du théorème d'accumulation d'entropie (EAT), qui est un outil important pour borner la min-entropie lisse d'un état produit par un processus séquentiel. La première utilise des approximations des canaux utilisés dans le processus EAT, tandis que la seconde, appelée EAT approximatif non-structuré, relâche significativement la structure séquentielle requise sur l'état. Nous mettons en valeur ces outils en les utilisant pour résoudre deux problèmes cryptographiques importants. Tout d'abord, nous prouvons la sécurité de la distribution quantique de clés (QKD) avec des corrélations à la source, qui sont des corrélations indésirables entre les rounds du protocole survenant en raison des imperfections de la source. Ces corrélations ont été un défi persistant pour la QKD. Nous fournissons une méthode simple et générale pour réduire la sécurité d'un protocole QKD avec ces corrélations à un protocole sans ces dernières. Notre deuxième application majeure est la preuve de la sécurité de la distribution quantique de clés device-independent (DIQKD) parallèle. En adaptant les techniques de répétition parallèle des jeux non-locaux, nous construisons une chaîne d'approximation structurée pour la sortie du protocole. L'application du EAT approximatif non-structuré à cette chaîne fournit alors une preuve de sécurité pour le protocole. One-shot information theory aims to study communication and information processing tasks for general states and processes under minimal structure. Such generality is crucial for analysing communication tasks with limited resources and the security of cryptographic protocols. In the asymptotic regime for information tasks with an i.i.d. (independent and identically distributed) structure, the rates are typically characterised by the von Neumann entropy and its derivatives. In the one-shot regime, a multitude of different entropies are required for this purpose. One of the most important among these is the smooth min-entropy, which characterises the rates of cryptographic protocols. In contrast to the von Neumann entropy, the behaviour of the smooth min-entropy is often unintuitive. Tools for decomposing the smooth min-entropy are also quite restrictive, making it challenging to analyse structures that naturally arise in information theory. One such structure, which we call an approximation chain, forms the central theme of this thesis. For a state ρA1nB, we term a sequence of states (σA1kB(k))k=1n an approximation chain of ρ if for each k, ρA1kB≈ϵσA1kB(k). These structures frequently emerge when incorporating approximations in entropic identities, studying imperfections, and developing security proofs. While the von Neumann entropy of ρ can be readily expressed in terms of the entropies of its approximation chain states, it is generally not possible to do so with the smooth min-entropy. In this thesis, we develop techniques for establishing entropic bounds with approximation chains and apply these to cryptographic scenarios. Our work begins by considering one of the simplest cases of such a chain, whereby the registers of ρ are almost independent of one another, and culminates in establishing a universal chain rule for the smooth min-entropy, which enables one to bound the smooth min-entropy for a state in terms of entropies of its approximation chain. Furthermore, we prove two approximate versions of the entropy accumulation theorem (EAT), which is an important tool for bounding the smooth min-entropy of a state produced by a sequential process. The first enables approximations to the channels used in the EAT process, while the second, termed the unstructured approximate EAT, significantly relaxes the sequential structure required on the state. We showcase these tools by using them to solve two significant cryptographic problems. First, we prove the security of quantum key distribution (QKD) under source correlations, which are undesired correlations among states across independent QKD rounds arising due to source imperfections. These correlations have been a persistent challenge for QKD. We provide a simple and general method to reduce the security for a QKD protocol with these correlations to one without. Our second major application is proving the security of parallel device-independent quantum key distribution (DIQKD). By adapting techniques from the parallel repetition of non-local games, we construct a structured approximation chain for the protocol output. Applying the unstructured approximate EAT to this chain then yields a proof of security for the protocol.