O QC-MDPC McEliece foi considerado um dos mais promissores esquemas criptográficos de chave pública que oferecem segurança contra ataques por computadores quânticos. O tamanho das chaves públicas do QC-MDPC McEliece é competitivo com o das chaves do RSA, e o esquema tem uma redução de segurança aparentemente forte. Por três anos, o esquema não sofreu ataques críticos, até que na Asiacrypt de 2016 Guo, Johansson, e Stankovski mostraram um ataque de reação contra o QC-MDPC McEliece que explora um aspecto não considerado em sua redução de segurança: a probabilidade de o algoritmo de decriptação falhar é menor quando a chave secreta e o vetor usado para encriptar a mensagem compartilham certas propriedades, chamadas de espectros. Dessa forma, um atacante pode, ao detectar falhas de decriptação, obter informação sobre o espectro, que será usada para reconstruir a chave secreta. Guo et al. apresentaram um algoritmo para a reconstrução da chave a partir do espectro recuperado, para o qual é possível apontar três problemas. O primeiro é que seu algoritmo não é eficiente quando o espectro da chave não foi recuperado quase completamente, o que resulta em o atacante ter que enviar um grande número de testes de decriptação à portadora da chave secreta. O segundo problema é que o desempenho de seu algoritmo não escala bem para níveis de segurança mais altos. O terceiro e último problema é que, por ser baseado numa busca em profundidade, seu algoritmo não pode ser paralelizado trivialmente. Para aumentar a eficiência do ataque, dois novos algoritmos de reconstrução são propostos neste trabalho. Estes algoritmos são mais eficientes, usam menos informação sobre a chave secreta, e podem ser paralelizados trivialmente. O primeiro algoritmo é probabilístico e tem complexidade assintótica ligeiramente melhor do que a do original. Entretanto, o desempenho do algoritmo probabilístico piora rapidamente, embora mais lentamente do que o algoritmo de Guo et al., conforme a quantidade de informação sobre o espectro diminui. O segundo algoritmo explora uma relação linear entre os blocos da chave secreta. Este é mais eficiente, tanto assintoticamente quanto na prática, que os dois outros algoritmos, e é eficiente mesmo com 50% menos informação sobre o espectro do que o necessário para o algoritmo original. Isso permite que o atacante encontre a chave secreta fazendo apenas em torno de 20% do número de testes necessários pelo algoritmo de Guo\'s et al., considerando-se o nível de segurança de 80 bits. O desempenho de ambos os algoritmos são analisados e comparados com o do algoritmo original, e as análises são feitas tanto para a complexidade teórica quanto para o desempenho na prática, considerando a implementação dos algoritmos em linguagem C. / The QC-MDPC McEliece scheme was considered one of the most promising public key encryption schemes for efficient post-quantum secure encryption. As a variant of the McEliece scheme, it is based on the syndrome decoding problem, an NP-hard problem from Coding Theory. The key sizes are competitive with the ones of the widely used RSA cryptosystem, and it came with an apparently strong security reduction. For three years, the scheme has not suffered major threats, until the end of 2016, when Guo, Johansson, and Stankovski presented at Asiacrypt a reaction attack on the QC-MDPC that exploits one aspect that was not considered in the security reduction: the probability of a decoding failure to occur is lower when the secret key and the error used for encryption share certain properties, which they called spectrums. By detecting decoding failures, the attacker can obtain information on the spectrum of the secret key and then use this information to reconstruct the key. Guo et al. presented an algorithm for key reconstruction for which we can point three weaknesses. The first one is that it cannot deal efficiently with partial information on the spectrum of the secret key, resulting in the attacker having to send a great number of decoding trials. The second one is that it does not scale well for higher security levels. The third one is that the algorithm, which is based on a depth-first search, cannot be trivially parallelized. To improve the efficiency of the attack, we propose two different key reconstruction algorithms that are more efficient, use less information on the secret key, and can be trivially parallelized. The first algorithm, which is a simple probabilistic extension of Guo\'s et al. algorithm, is more efficient and runs increasingly faster, for higher security levels, than the original one. However, for security levels higher than 80 bits, the probabilistic algorithm cannot run efficiently without too much information on the spectrum of the secret key, even though it needs less information than the original algorithm. The second algorithm is based on a linear relation between the blocks of the secret key. It can run efficiently with around 50% less information than needed by Guo\'s et al. key reconstruction algorithm. This makes it possible for an attacker to recover the secret key sending approximately 20% of the of the number of decoding trials needed by Guo\'s et al. algorithm, for the security level of 80 bits. The performance of each presented algorithm is analyzed and compared with that of the original one. The analysis are made theoretically, considering a probabilistic analysis of the algorithms, and in practice, considering the corresponding implementations in C language.

Reticulados têm sido aplicados de diferentes maneiras em criptografia. Inicialmente utilizados para a destruição de criptossistemas, eles foram posteriormente aplicados na construção de novos esquemas, incluindo criptossistemas assimétricos, esquemas de assinatura cega e os primeiros métodos para encriptação completamente homomórfica. Contudo, seu desempenho ainda é proibitivamente lenta em muitos casos. Neste trabalho, expandimos técnicas originalmente desenvolvidas para encriptação homomórfica, tornando-as mais genéricas e aplicando-as no esquema GGH-YK-M, um esquema de encriptação de chave pública, e no esquema LMSV, a única construção homomórfica que não sucumbiu a ataques de recuperação de chaves IND-CCA1 até o momento. Em nossos testes, reduzimos o tamanho das chaves do GGH-YK-M em uma ordem de complexidade, especificamente, de O(n2 lg n) para O(n lg n), onde n é um parâmetro público do esquema. A nova técnica também atinge processamento mais rápido em todas as operações envolvidas em um criptossistema assimétrico, isto é, geração de chaves, encriptação e decriptação. A melhora mais significativa é na geração de chaves, que se torna mais de 3 ordens de magnitude mais rápida que resultados anteriores, enquanto a encriptação se torna por volta de 2 ordens de magnitude mais rápida. Para decriptação, nossa implementação é dez vezes mais rápida que a literatura. Também mostramos que é possível aumentar a segurança do esquema LMSV contra os ataques quânticos de recuperação de chaves recentemente publicados pela agência britânica GCHQ. Isso é feito através da adoção de reticulados não-ciclotômicos baseados em anéis polinomiais irredutíveis quase-circulantes. Em nossa implementação, o desempenho da encriptação é virtualmente idêntico, e a decriptação torna-se ligeiramente inferior, um pequeno preço a se pagar pelo aumento de segurança. A geração de chaves, porém, é muito mais lenta, devido à necessidade de se utilizar um método mais genérico e caro. A existência de métodos dedicados altamente eficientes para a geração de chaves nesta variante mais segura do LMSV permanece como um problema em aberto. / Lattices have been applied in many different ways in cryptography. Firstly used for the destruction of cryptosystems, they were later applied in the construction of new schemes, including asymmetric cryptosystems, blind signature schemes and the first methods for fully homomorphic encryption. Nonetheless, performance is still prohibitively slow in many cases. In this work, we expand techniques originally devised for homomorphic encryption, making them more general and applying them to the GGH-YK-M cryptosystem, a lattice-based public-key cryptosystem, and to the LMSV scheme, the only known homomorphic scheme that has not succumbed to INDCCA1 key recovery attacks to this date. In our tests, we reduce public key bandwidth occupation of GGH-YK-M by an order of complexity, specifically, from O(n2 lg n) down to O(n lg n) bits, where n is a public parameter of the scheme. The new technique also attains faster processing in all operations involved in an asymmetric cryptosystem, that is, key generation, encryption, and decryption. The most significant improvement in performance is in key generation, which becomes more than 3 orders of magnitude faster than previous results, while encryption becomes about 2 orders of magnitude faster. For decryption, our implementation is ten times faster than the literature. We also show that it is possible to improve security of LMSV against the quantum key recovery attacks recently published by British GCHQ.We do so by adopting non-cyclotomic lattices based on nearly-circulant irreducible polynomial rings. In our implementation, performance of encryption remains virtually the same, and decryption becomes slightly worse, a small price to pay for the improved security. Key generation, however, is much slower, due to the fact that it is necessary to use a more generic and expensive method. The existence of highly effcient dedicated methods for key generation of this secure variant of LMSV remains as an open problem.

Ocorre atualmente um movimento de aumento da importância que a manutenção da segurança da informação vem adquirindo em redes de informação de crítica. Ao longo das últimas décadas a utilização de ferramentas criptográficas, especialmente aquelas baseadas em problemas de díficil solução computacional, foram suficientes para garantir a segurança dos sistemas de comunicação. Contudo, o desenvolvimento da nova técnica de processamento de informação conhecida como computação quântica e os resultados téoricos e experimentais apresentados por esta mostram que é possível inviabilizar alguns dos sistemas de criptografia atuais amplamente utilizados. A existência de tal vulnerabilidade representa um fator crítico em redes em que falhas de segurança da informação podem estar associadas a riscos de segurança física. Uma alternativa para os métodos criptográficos atuais consiste na utilização de sistemas quânticos na obtenção de um método criptográfico, o que se conhece como criptografia quântica. Este novo paradigma tem seu fundamento resistente mesmo na presença de capacidade tecnológica ilimitada, incluindo o cenário com disponibilidade de computação quântica. Este trabalho tem como objetivo levantar os impactos que o desenvolvimento da computação quântica têm sobre a segurança dos atuais sistemas criptográficos, apresentar e desenvolver alternativas de protocolos de criptografia quântica disponíveis, e realizar um estudo de caso por meio da avaliação da utilização de criptografia quântica no contexto da Aeronautical Telecommunication Network (ATN). Isto é feito por meio do desenvolvimento de um ambiente de simulacão que permite avaliar o comportamento de um protocolo de criptografia quântica em um cenário em um ambiente com requisitos de missão crítica, como é o caso da ATN. / The importance of security maintenance in critical information networks has been rising in recent times. Over the past decades, the utilization of cryptography tools, mainly those based on computationally intractable problems, was enough to ensure the security of communications systems. The development of the new information processing technique known as quantum computation and the theoretical and experimental results showed by this approach demonstrated that could be possible to cripple the current widely used cryptography techniques. This vulnerability represents a critical issue for networks where a security fault could be associated to a safety fault. An alternative for the current cryptography methods consists in the utilization of quantum systems to obtain a new cryptographic method. The new paradigm presented by this approach has solid principles even in the presence of unlimited computational capacity, including the scenario with availability of quantum computation. The aim of this work is the assessment of impacts that the development of quantum computation has over the current cryptographic methods security, the presentation and development of alternatives based on quantum cryptography protocols, and the development of a case study using the case of Aeronautical Telecommunication Network (ATN). This aim is reached by means of the development of a simulation environment that allows the evaluation of a quantum cryptography protocol behavior in an environment with mission critical requirements, like the ATN case.

La cryptographie à base de réseaux euclidiens est un domaine prometteur pour la construction de primitives cryptographiques post-quantiques. Un problème fondamental, lié aux réseaux, est le problème du plus court vecteur (ou SVP, pour Shortest Vector Problem). Ce problème est supposé être difficile à résoudre même avec un ordinateur quantique. Afin d’améliorer l’efficacité des protocoles cryptographiques, on peut utiliser des réseaux structurés, comme par exemple des réseaux idéaux ou des réseaux modules (qui sont une généralisation des réseaux idéaux). La sécurité de la plupart des schémas utilisant des réseaux structurés dépend de la difficulté du problème SVP dans des réseaux modules, mais un petit nombre de schémas peuvent également être impactés par SVP dans des réseaux idéaux. La principale construction pouvant être impactée par SVP dans des réseaux idéaux est la fonction multilinéaire GGH13. Cette fonction multilinéaire est principalement utilisée aujourd’hui pour construire des obfuscateurs de programmes, c’est-à-dire des fonctions qui prennent en entrée le code d’un programme et renvoie le code d’un programme équivalent (calculant la même fonction), mais qui doit cacher la façon dont le programme fonctionne.Dans cette thèse, nous nous intéressons dans un premier temps au problème SVP dans les réseaux idéaux et modules. Nous présentons un premier algorithme qui, après un pre-calcul exponentiel, permet de trouver des vecteurs courts dans des réseaux idéaux plus rapidement que le meilleur algorithme connu pour des réseaux arbitraires. Nous présentons ensuite un algorithme pour les réseaux modules de rang 2, également plus efficace que le meilleur algorithme connu pour des réseaux arbitraires, à condition d’avoir accès à un oracle résolvant le problème du plus proche vecteur dans un réseau fixé. Le pré-calcul exponentiel et l’oracle pour le problème du plus proche vecteurs rendent ces deux algorithmes inutilisables en pratique.Dans un second temps, nous nous intéressons à la fonction GGH13 ainsi qu’aux obfuscateurs qui l’utilisent. Nous étudions d’abord l’impact des attaques statistiques sur la fonction GGH13 et ses variantes. Nous nous intéressons ensuite à la sécurité des obfuscateurs utilisant la fonction GGH13 et proposons une attaque quantique contre plusieurs de ces obfuscateurs. Cette attaque quantique utilise entre autres un algorithme calculant un vecteur court dans un réseau idéal dépendant d’un paramètre secret de la fonction GGH13. / Lattice-based cryptography is a promising area for constructing cryptographic primitives that are plausibly secure even in the presence of quantum computers. A fundamental problem related to lattices is the shortest vector problem (or SVP), which asks to find a shortest non-zero vector in a lattice. This problem is believed to be intractable, even quantumly. Structured lattices, for example ideal lattices or module lattices (the latter being a generalization of the former), are often used to improve the efficiency of lattice-based primitives. The security of most of the schemes based on structured lattices is related to SVP in module lattices, and a very small number of schemes can also be impacted by SVP in ideal lattices.In this thesis, we first focus on the problem of finding short vectors in ideal and module lattices.We propose an algorithm which, after some exponential pre-computation, performs better on ideal lattices than the best known algorithm for arbitrary lattices. We also present an algorithm to find short vectors in rank 2 modules, provided that we have access to some oracle solving the closest vector problem in a fixed lattice. The exponential pre-processing time and the oracle call make these two algorithms unusable in practice.The main scheme whose security might be impacted by SVP in ideal lattices is the GGH13multilinear map. This protocol is mainly used today to construct program obfuscators, which should render the code of a program unintelligible, while preserving its functionality. In a second part of this thesis, we focus on the GGH13 map and its application to obfuscation. We first study the impact of statistical attacks on the GGH13 map and on its variants. We then study the security of obfuscators based on the GGH13 map and propose a quantum attack against multiple such obfuscators. This quantum attack uses as a subroutine an algorithm to find a short vector in an ideal lattice related to a secret element of the GGH13 map.

Quantum communication promises to outperform its classical counterparts and enable protocols previously impossible. Specifically, quantum key distribution (QKD) allows a cryptographic key to be shared between distant parties with provable security. Much work has been performed on theoretical and experi- mental aspects of QKD, and the push is on to make it commercially viable and integrable with existing technologies. To this end I have performed simulations and experiments on QKD and other quantum protocols in regimes previously unexplored. The first experiment involves QKD via distributed entanglement through the standard telecommunications optical fibre network. I show that entanglement is preserved, even when the photons used are a shorter wavelength than the design of the optical fibre calls for. This surprising result is then used to demonstrate QKD over installed optical fibre, even with co-propagating classical traffic. Because the quantum and classical signals are sufficiently separated in wavelength, little cross-talk is observed, leading to high compatibility between this type of QKD and existing telecommunications infrastructure. Secondly, I demonstrate the key components of fully-modulated decoy-state QKD over the highest-loss channel to date, using a novel photon source based on weak coherent (laser) pulses. This system has application in a satellite uplink of QKD, which would enable worldwide secure communication. The uplink allows the complex quantum source to be kept on the ground while only simple receivers are in space, but suffers from high link loss due to atmospheric turbulence, necessitating the use of specific photon detectors and highly tailored photon pulses. My results could be applied in a near term satellite mission.

Three quantum cryptographic protocols of multiuser quantum networks with embedded authentication, allowing quantum key distribution or quantum direct communication, are discussed in this work. The security of the protocols against different types of attacks is analysed with a focus on various impersonation attacks and the man-in-the-middle attack. On the basis of the security analyses several improvements are suggested and implemented in order to adjust the investigated vulnerabilities. Furthermore, the impact of the eavesdropping test procedure on impersonation attacks is outlined. The framework of a general eavesdropping test is proposed to provide additional protection against security risks in impersonation attacks. / In der Diplomarbeit werden drei verschiedene quantenkryptographische Protokolle mit dem Schwerpunkt auf authentifizierten Quantennetzwerken analysiert. Die Sicherheit der Protokolle gegenüber verschiedenen Angriffen wird untersucht, wobei der Fokus auf kompletten Personifikationsattacken („impersonation attacks“) liegt. Auf Basis der Sicherheitsanalyse und den Netzwerkanforderungen werden entsprechende Verbesserungen vorgeschlagen. Um die Gefahr von Personifikationen realistisch abschätzen zu können, wird außerdem der Einfluss des Testablaufs analysiert. Um zusätzlichen Schutz gegen Personifikationsattacken zu gewährleisten, werden die Rahmenbedingungen für eine allgemeine Testspezifikation festgelegt.

Mutually unbiased bases is an important topic in the recent quantum system researches. Although there is much work in this area, many problems related to mutually unbiased bases are still open. For example, constructing a complete set of mutually unbiased bases in the Hilbert spaces with composite dimensions has not been achieved yet. This thesis defines a weaker concept than mutually unbiased bases in the Hilbert spaces with composite dimensions. We call this concept, weak mutually unbiased bases. There is a duality between such bases and the geometry of the phase space Zd × Zd, where d is the phase space dimension. To show this duality we study the properties of lines through the origin in Zd × Zd, then we explain the correspondence between the properties of these lines and the properties of the weak mutually unbiased bases. We give an explicit construction of a complete set of weak mutually unbiased bases in the Hilbert space Hd, where d is odd and d = p1p2; p1, p2 are prime numbers. We apply the concept of weak mutually unbiased bases in the context of quantum tomography and quantum cryptography.

Τα Αποτυπώματα αποτελούν μια κομψή και αποτελεσματική λύση στο Πρόβλημα της Ισότητας στην Πολυπλοκότητα Επικοινωνίας. Τα Κβαντικά τους αντίστοιχα είναι ένα παράδειγμα της εκθετικής μείωσης στο κόστος επικοινωνίας που είναι εφικτή όταν χρησιμοποιείται κβαντική αντί για κλασσική πληροφορία. Το πλεονέκτημα αυτό οδήγησε σε αρκετά χρόνια έρευνας με ενδιαφέροντα αποτελέσματα. Επιπλέον, πρόσφατες δημοσιεύσεις υποδεικνύουν αποδοτικούς τρόπους για πειραματική υλοποίηση των Κβαντικών Αποτυπωμάτων. Τέλος, τα Κβαντικά Αποτυπώματα αποδεικνύονται ισχυρά εργαλεία στο χώρο της Κβαντικής Κρυπτογραφίας, επειδή διαθέτουν δυνατότητα αξιόπιστης απόκρυψης πληροφορίας. Σε αυτήν την εργασία εξετάζουμε τα Κβαντικά Αποτυπώματα στο πλαίσιο της Κβαντικής Κρυπτογραφίας και διερευνούμε τη χρήση τους για την κατασκευή πειραματικώς υλοποιήσιμων Κβαντικών Χρημάτων. / Fingerprints provide an elegant and cost-e ective solution to the Equality Problem in communication complexity. Their quantum counterpart is one example where an exponential gap exists between classical and quantum communication cost. Moreover, recent publications have proposed e cient ways to construct and work with quantum ngerprints in practice. Apart from the savings in communication cost, quantum ngerprints have an additional, inherent feature, namely the ability to hide information, which renders them a perfect candidate for Quantum Cryptography. This thesis reviews quantum ngerprints both as a communication complexity asset as well as a crypto-primitive and investigates the use of Quantum Fingerprinting to implement experimentally feasible Quantum Money schemes. We propose a public-key Quantum Money scheme comprising Quantum Fingerprints as well as an experimental implementation of it, feasible with current technology.

Quantum communication promises to outperform its classical counterparts and enable protocols previously impossible. Specifically, quantum key distribution (QKD) allows a cryptographic key to be shared between distant parties with provable security. Much work has been performed on theoretical and experi- mental aspects of QKD, and the push is on to make it commercially viable and integrable with existing technologies. To this end I have performed simulations and experiments on QKD and other quantum protocols in regimes previously unexplored. The first experiment involves QKD via distributed entanglement through the standard telecommunications optical fibre network. I show that entanglement is preserved, even when the photons used are a shorter wavelength than the design of the optical fibre calls for. This surprising result is then used to demonstrate QKD over installed optical fibre, even with co-propagating classical traffic. Because the quantum and classical signals are sufficiently separated in wavelength, little cross-talk is observed, leading to high compatibility between this type of QKD and existing telecommunications infrastructure. Secondly, I demonstrate the key components of fully-modulated decoy-state QKD over the highest-loss channel to date, using a novel photon source based on weak coherent (laser) pulses. This system has application in a satellite uplink of QKD, which would enable worldwide secure communication. The uplink allows the complex quantum source to be kept on the ground while only simple receivers are in space, but suffers from high link loss due to atmospheric turbulence, necessitating the use of specific photon detectors and highly tailored photon pulses. My results could be applied in a near term satellite mission.

The idea to assimilate classical information theory with quantum mechanics resulted in the creation of a new field in physics known as quantum information. One of the first papers in this new field occurred in the early 1970's when Stephen Wiesner wrote the seminal manuscript titled: "Conjugate Coding". However, its importance wasn't imme- diately recognized and wasn't published until 1983. The 1980's and 1990's saw a number of important papers published in quantum information leading to the subfields of quantum cryptography, quantum teleportation, quantum entanglement, distinguishability of quantum states, and quantum cloning. It was also during the 1980's, that a new model of computing, known as quantum computation, was beginning to emerge. It offered the possibility of solving certain problems faster than a classical computer by exploiting various properties of quantum mechanics. Research in this field was undoubtedly stimulated by a well known talk given by Richard Feynman in 1981 at MIT on quantum simulations. Both quantum information and quantum computation were initially developed with quantum discrete variables in mind. However, over the course of the last decade, there has been a significant increase in using quantum continuous variables. This thesis will focus on the topic of quantum information and quantum computation using continuous variables. Specifically, we will theoretically consider the cloning of continuous-variable entanglement, the distinguishability of Gaussian states, new continuous-variable quantum cryptography protocols and finally, the universality of quantum computation using continuous-variable cluster states.