A criptografia de chave pública é uma área do conhecimento sujeita que é tema de intensa atividade contemporânea de pesquisa. Novos protocolos, primitivas e ataques são propostos com frequência, com semelhanças e diferenças mútuas que podem ser mais ou menos evidentes. Algumas primitivas criptográficas de chave pública mostram-se extremamente férteis em termos de flexibilidade, eficiência e segurança. Duas vertentes que se enquadram nesta categoria são os emparelhamentos e os reticulados. Por possuírem semelhanças em suas funcionalidades a despeito de possuírem naturezas completamente díspares, além de exibirem uma versatilidade rara em toda a área de criptografia de chave pública, alguns autores propuseram chamar os reticulados de os novos emparelhamentos, conforme a ordem cronológica em que essas primitivas passaram a atrair interesse mais vívido de pesquisa. Neste cenário, um estudo comparativo entre elas é de razoável interesse, em particular sobre vantagens e desvantagens que o estado da arte revela sobre a eficiência de cada uma delas. A pesquisa aqui relatada contempla esse estudo, e contribui técnicas de implementação eficiente de emparelhamentos (com ênfase no uso de coordenadas afins, pouco exploradas na literatura), novos parâmetros para a construção de reticulados compactos (na forma das chamadas álgebras discretas de Rojo) e uma técnica inovadora para instanciar reticulados na prática (especificamente, um algoritmo simples e natural para amostrar vetores normalmente distribuídos nos reticulados comumente adotados em sistemas criptográficos). / Public key cryptography is an area of knowledge undergoing intense research at present. New protocols, primitives and attacks are often proposed, with mutual similarities and differences that may be more or less evident. Some public key cryptographic primitives tend to be extremely prolific in terms of flexibility, efficiency and security. Two trends that fit this category are pairings and lattices. Because of their similar functionalities despite their completely disparate nature, and because of their rare versatility within the whole area of public key cryptography, some authors proposed to call lattices \"the new pairings,\" according to the chronological order by which these primitives began to attract more vivid research interest. In this scenario, a comparative study between them is of reasonable interest, in particular on the advantages and disadvantages that the state of the art reveals about the efficiency of each one. The research reported herein addresses this study, and also contributes efficient pairing implementation techniques (focusing on affine coordinates, which are scarcely explored in literature), new parameters for building compact lattices (in the form of the so-called discrete Rojo algebras) and an innovative technique to instantiate lattices in practical (specifically, a simple and natural algorithm for sampling normally distributed vectors in the lattices that are commonly adopted in cryptographic systems).

A criptografia é uma ciência que tem especial destaque no mundo moderno, evidenciando a necessidade em pesquisar algoritmos e técnicas para seu aperfeiçoamento. Apesar das soluções atualmente empregadas serem baseadas em problemas suficientemente seguros, se comparados ao poderio computacional necessário para resolvê-los, seu emprego futuro é questionado. Pesquisas demonstram potencial vulnerabilidade destes sistemas, caso tenhamos à disposição computadores quânticos sendo utilizados para fraudá-los. Alternativas têm sido estudadas e o criptossistema proposto por Robert J. McElice se mostra como uma das mais interessantes, visto sua versão convencional, baseada em códigos de Goppa, ter a segurança até o momento inafetada, inclusive se levado em conta a disponibilidade de tecnologia quântica. Entretanto, tal solução sofria com o tamanho de suas grandes chaves criptográficas, representando um entrave para sua aplicação na prática. Objetivando minimizar esta deficiência, neste trabalho, propomos a classe de códigos de Goppa quase-diádicos, que admitem uma matriz de paridade ou matriz geradora com representação muito compacta, produzindo chaves do tipo McEliece que são até um fator t = O(n) menores que as chaves genéricas, em notação que omite fatores logarítmicos, produzidas a partir de códigos de Goppa de comprimento n, para a correção de t erros em característica 2. No caso binário, essa família também mantém a capacidade de corrigir o número total projetado de erros em vez de apenas a metade; esta propriedade falta a todas as tentativas anteriores de construção de códigos compactos para fins de criptografia, incluindo (BERGER et al., 2009). Além disso, a complexidade de todas as operações criptográficas típicas torna-se O(n). Esta proposta foi submetida e selecionada para publicação e apresentação no XVI Workshop Selected Areas in Cryptography (SAC2009), ocorrido entre 13 e 14 de Agosto de 2009, em Calgary, Alberta, Canadá, de referência bibliográfica (MISOCZKI; BARRETO, 2009). Este evento foi realizado em cooperação com a International Association for Cryptologic Research (IACR) e teve seus artigos publicados pela Springer em Lecture Notes in Computer Science, volume 5867. / Cryptography is a science that is especially prominent in the modern world, highlighting the need to find algorithms and techniques for its improvement. Despite the fact that solutions currently used are based on problems that are sufficiently secure, if compared to the computing power needed to solve them, their future use is questioned. Researches demonstrated the potential vulnerability of these systems, if quantum computers are used to defraud them. Alternatives have been studied and the cryptosystem proposed by Robert J. McElice has been considered as one of the most interesting, since its conventional version, based on Goppa codes, has the security so far unaffected, even if taken into account the availability of quantum technology. However, this solution suffered with the large size of their cryptographic keys, an obstacle to its implementation in practice. Aiming to minimize this shortcoming, in this paper, we propose the class of quasidyadic Goppa codes, which admits a generator or parity-check matrix with very compact representation, producing McEliece keys that are up to a factor t = O(n) lower than the generic keys, in notation which omits logarithmic factors, produced from Goppa codes of length n, to correct t errors in characteristic 2. In the binary case, this family also retains the ability to correct the projected total number of errors, rather than just half; this property lacks in all previous attempts to build compact code for encryption, including (BERGER et al., 2009). Moreover, the complexity of all typical cryptographic operations becomes O(n). This proposal was submitted and selected for publication and presentation in the XVI Workshop Selected Areas in Cryptography (SAC2009), occurred in August, 13th and 14th, 2009, in Calgary, Alberta, Canada, with bibliographic reference (MISOCZKI; BARRETO, 2009). This event was held in cooperation with the International Association for Cryptologic Research (IACR) and had his papers published by Springer in Lecture Notes in Computer Science, volume 5867.

A criptografia é uma ciência que tem especial destaque no mundo moderno, evidenciando a necessidade em pesquisar algoritmos e técnicas para seu aperfeiçoamento. Apesar das soluções atualmente empregadas serem baseadas em problemas suficientemente seguros, se comparados ao poderio computacional necessário para resolvê-los, seu emprego futuro é questionado. Pesquisas demonstram potencial vulnerabilidade destes sistemas, caso tenhamos à disposição computadores quânticos sendo utilizados para fraudá-los. Alternativas têm sido estudadas e o criptossistema proposto por Robert J. McElice se mostra como uma das mais interessantes, visto sua versão convencional, baseada em códigos de Goppa, ter a segurança até o momento inafetada, inclusive se levado em conta a disponibilidade de tecnologia quântica. Entretanto, tal solução sofria com o tamanho de suas grandes chaves criptográficas, representando um entrave para sua aplicação na prática. Objetivando minimizar esta deficiência, neste trabalho, propomos a classe de códigos de Goppa quase-diádicos, que admitem uma matriz de paridade ou matriz geradora com representação muito compacta, produzindo chaves do tipo McEliece que são até um fator t = O(n) menores que as chaves genéricas, em notação que omite fatores logarítmicos, produzidas a partir de códigos de Goppa de comprimento n, para a correção de t erros em característica 2. No caso binário, essa família também mantém a capacidade de corrigir o número total projetado de erros em vez de apenas a metade; esta propriedade falta a todas as tentativas anteriores de construção de códigos compactos para fins de criptografia, incluindo (BERGER et al., 2009). Além disso, a complexidade de todas as operações criptográficas típicas torna-se O(n). Esta proposta foi submetida e selecionada para publicação e apresentação no XVI Workshop Selected Areas in Cryptography (SAC2009), ocorrido entre 13 e 14 de Agosto de 2009, em Calgary, Alberta, Canadá, de referência bibliográfica (MISOCZKI; BARRETO, 2009). Este evento foi realizado em cooperação com a International Association for Cryptologic Research (IACR) e teve seus artigos publicados pela Springer em Lecture Notes in Computer Science, volume 5867. / Cryptography is a science that is especially prominent in the modern world, highlighting the need to find algorithms and techniques for its improvement. Despite the fact that solutions currently used are based on problems that are sufficiently secure, if compared to the computing power needed to solve them, their future use is questioned. Researches demonstrated the potential vulnerability of these systems, if quantum computers are used to defraud them. Alternatives have been studied and the cryptosystem proposed by Robert J. McElice has been considered as one of the most interesting, since its conventional version, based on Goppa codes, has the security so far unaffected, even if taken into account the availability of quantum technology. However, this solution suffered with the large size of their cryptographic keys, an obstacle to its implementation in practice. Aiming to minimize this shortcoming, in this paper, we propose the class of quasidyadic Goppa codes, which admits a generator or parity-check matrix with very compact representation, producing McEliece keys that are up to a factor t = O(n) lower than the generic keys, in notation which omits logarithmic factors, produced from Goppa codes of length n, to correct t errors in characteristic 2. In the binary case, this family also retains the ability to correct the projected total number of errors, rather than just half; this property lacks in all previous attempts to build compact code for encryption, including (BERGER et al., 2009). Moreover, the complexity of all typical cryptographic operations becomes O(n). This proposal was submitted and selected for publication and presentation in the XVI Workshop Selected Areas in Cryptography (SAC2009), occurred in August, 13th and 14th, 2009, in Calgary, Alberta, Canada, with bibliographic reference (MISOCZKI; BARRETO, 2009). This event was held in cooperation with the International Association for Cryptologic Research (IACR) and had his papers published by Springer in Lecture Notes in Computer Science, volume 5867.

Block ciphers are widely used building blocks for secure communication systems; their purpose is to ensure confidentiality of the data exchanged through such systems, while achieving high performance. In this context, a variety of aspects must be taken into account. Primarily, they must be secure. The security of a block cipher is usually assessed by testing its resistance against known attacks. However as attacks may exist that are currently unknown, generic security proofs are also tried to be obtained. On the other hand, another attack methodology is also worth considering. Contrary to the others, it aims at the implementation of the algorithm rather than the cipher itself. It is known as side-channel analysis. Finally, performance of a block cipher in terms of throughput is very important as well. More than any other cryptographic primitive, block ciphers allow a tradeoff to be made between security and performance. In this thesis, contributions are given regarding these various topics. In the first part of the thesis, we deal with two particular types of attacks, namely the square attack and key schedule cryptanalysis. We also consider security proofs in the so-called Luby-Rackoff model, which deals with adversaries having unbounded computation capabilities. More precisely, we are interested in the Misty structure, when the round functions are assumed to be involutions. The second part of the thesis is devoted to design and implementation aspects. First, we present a fault attack on substitution-permutation networks, which requires as few as two faulty ciphertexts to retrieve the key. We also study the security of DeKaRT, which is an algorithm intended to protect smart cards against probing attacks. Finally we present the design of ICEBERG, a block cipher deliberately oriented towards good performance in hardware, and give an adequate analysis of its security.

Chaotic systems have been studied for the past few decades because of its complex behaviour given simple governing ordinary differential equations. In the field of cryptology, several methods have been proposed for the use of chaos in cryptosystems. In this work, a method for harnessing the beneficial behaviour of chaos was proposed for use in RFID authentication and encryption. In order to make an accurate estimation of necessary hardware resources required, a complete hardware implementation was designed using a Xilinx Virtex 6 FPGA. The results showed that only 470 Xilinx Virtex slices were required, which is significantly less than other RFID authentication methods based on AES block cipher. The total number of clock cycles required per encryption of a 288-bit plaintext was 57 clock cycles. This efficiency level is many times higher than other AES methods for RFID application. Based on a carrier frequency of 13.56Mhz, which is the standard frequency of common encryption enabled passive RFID tags such as ISO-15693, a data throughput of 5.538Kb/s was achieved. As the strength of the proposed RFID authentication and encryption scheme is based on the problem of predicting chaotic systems, it was important to ensure that chaotic behaviour is maintained in this discretized version of Lorenz dynamical system. As a result, key boundaries and fourth order Runge Kutta approximation time step values that are unique for this new mean of chaos utilization were discovered. The result is a computationally efficient and cryptographically complex new RFID authentication scheme that can be readily adopted in current RFID standards such as ISO-14443 and ISO-15693. A proof of security by the analysis of time series data obtained from the hardware FPGA design is also presented. This is to ensure that my proposed method does not exhibit short periodic cycles, has an even probabilistic distribution and builds on the beneficial chaotic properties of the continuous version of Lorenz dynamical system.

Chaotic systems have been studied for the past few decades because of its complex behaviour given simple governing ordinary differential equations. In the field of cryptology, several methods have been proposed for the use of chaos in cryptosystems. In this work, a method for harnessing the beneficial behaviour of chaos was proposed for use in RFID authentication and encryption. In order to make an accurate estimation of necessary hardware resources required, a complete hardware implementation was designed using a Xilinx Virtex 6 FPGA. The results showed that only 470 Xilinx Virtex slices were required, which is significantly less than other RFID authentication methods based on AES block cipher. The total number of clock cycles required per encryption of a 288-bit plaintext was 57 clock cycles. This efficiency level is many times higher than other AES methods for RFID application. Based on a carrier frequency of 13.56Mhz, which is the standard frequency of common encryption enabled passive RFID tags such as ISO-15693, a data throughput of 5.538Kb/s was achieved. As the strength of the proposed RFID authentication and encryption scheme is based on the problem of predicting chaotic systems, it was important to ensure that chaotic behaviour is maintained in this discretized version of Lorenz dynamical system. As a result, key boundaries and fourth order Runge Kutta approximation time step values that are unique for this new mean of chaos utilization were discovered. The result is a computationally efficient and cryptographically complex new RFID authentication scheme that can be readily adopted in current RFID standards such as ISO-14443 and ISO-15693. A proof of security by the analysis of time series data obtained from the hardware FPGA design is also presented. This is to ensure that my proposed method does not exhibit short periodic cycles, has an even probabilistic distribution and builds on the beneficial chaotic properties of the continuous version of Lorenz dynamical system.

Computing discrete logarithms is a long-standing algorithmic problem, whose hardness forms the basis for numerous current public-key cryptosystems. In the case of finite fields of small characteristic, however, there has been tremendous progress recently, by which the complexity of the discrete logarithm problem (DLP) is considerably reduced. This habilitation thesis on the DLP in such fields deals with two principal aspects. On one hand, we develop and investigate novel efficient algorithms for computing discrete logarithms, where the complexity analysis relies on heuristic assumptions. In particular, we show that logarithms of factor base elements can be computed in polynomial time, and we discuss practical impacts of the new methods on the security of pairing-based cryptosystems. While a heuristic running time analysis of algorithms is common practice for concrete security estimations, this approach is insufficient from a mathematical perspective. Therefore, on the other hand, we focus on provable complexity results, for which we modify the algorithms so that any heuristics are avoided and a rigorous analysis becomes possible. We prove that for any prime field there exist infinitely many extension fields in which the DLP can be solved in quasi-polynomial time. Despite the two aspects looking rather independent from each other, it turns out, as illustrated in this thesis, that progress regarding practical algorithms and record computations can lead to advances on the theoretical running time analysis -- and the other way around. / Die Berechnung von diskreten Logarithmen ist ein eingehend untersuchtes algorithmisches Problem, dessen Schwierigkeit zahlreiche Anwendungen in der heutigen Public-Key-Kryptographie besitzt. Für endliche Körper kleiner Charakteristik sind jedoch kürzlich erhebliche Fortschritte erzielt worden, welche die Komplexität des diskreten Logarithmusproblems (DLP) in diesem Szenario drastisch reduzieren. Diese Habilitationsschrift erörtert zwei grundsätzliche Aspekte beim DLP in Körpern kleiner Charakteristik. Es werden einerseits neuartige, erheblich effizientere Algorithmen zur Berechnung von diskreten Logarithmen entwickelt und untersucht, wobei die Laufzeitanalyse auf heuristischen Annahmen beruht. Unter anderem wird gezeigt, dass Logarithmen von Elementen der Faktorbasis in polynomieller Zeit berechnet werden können, und welche praktischen Auswirkungen die neuen Verfahren auf die Sicherheit paarungsbasierter Kryptosysteme haben. Während heuristische Laufzeitabschätzungen von Algorithmen für die konkrete Sicherheitsanalyse üblich sind, so erscheint diese Vorgehensweise aus mathematischer Sicht unzulänglich. Der Aspekt der beweisbaren Komplexität für DLP-Algorithmen konzentriert sich deshalb darauf, modifizierte Algorithmen zu entwickeln, die jegliche heuristische Annahme vermeiden und dessen Laufzeit rigoros gezeigt werden kann. Es wird bewiesen, dass für jeden Primkörper unendlich viele Erweiterungskörper existieren, für die das DLP in quasi-polynomieller Zeit gelöst werden kann. Obwohl die beiden Aspekte weitgehend unabhängig voneinander erscheinen mögen, so zeigt sich, wie in dieser Schrift illustriert wird, dass Fortschritte bei praktischen Algorithmen und Rekordberechnungen auch zu Fortentwicklungen bei theoretischen Laufzeitabschätzungen führen -- und umgekehrt.

A descoberta do algoritmo de Shor, para a fatoração de inteiros em tempo polinomial, motivou esforços rumo a implementação de um computador quântico. Ele é capaz de quebrar os principais criptossistemas de chave pública usados hoje (RSA e baseados em curvas elípticas). Estes fornecem diversos serviços de segurança, tais como confidencialidade e integridade dos dados e autenticação da fonte, além de possibilitar a distribuição de uma chave simétrica de sessão. Para quebrar estes criptossistemas, um computador quântico grande (2000 qubits) é necessário. Todavia, alternativas começaram a ser investigadas. As primeiras respostas vieram da própria mecânica quântica. Apesar das propriedades interessantes encontradas na criptografia quântica, um criptossistema completo parece inatingível, principalmente devido as assinaturas digitais, essenciais para a autenticação. Foram então propostos criptossitemas baseadas em problemas puramente clássicos que (acredita-se) não são tratáveis por computadores quânticos, que são chamadas de pós-quânticas. Estes sistemas ainda sofrem da falta de praticidade, seja devido ao tamanho das chaves ou ao tempo de processamento. Dentre os criptossistemas pós-quânticos, destacam-se o McEliece e o Niederreiter. Por si só, nenhum deles prevê assinaturas digitais, no entanto, as assinaturas CFS foram propostas, complementandos. Ainda que computadores quânticos de propósito geral estejam longe de nossa realidade, é possível imaginar um circuito quântico pequeno e dedicado. A melhoria trazida por ele seria a diferença necessária para tornar essas assinaturas práticas em um cenário legitimamente pós-quântico. Neste trabalho, uma arquitetura híbrida quântica/clássica é proposta para acelerar algoritmos criptográficos pós-quânticos. Dois coprocessadores quânticos, implementando a busca de Grover, são propostos: um para auxiliar o processo de decodificação de códigos de Goppa, no contexto do criptossistema McEliece; outro para auxiliar na busca por síndromes decodificáveis, no contexto das assinaturas CFS. Os resultados mostram que em alguns casos, o uso de um coprocessador quântico permite ganhos de até 99; 7% no tamanho da chave e até 76; 2% em tempo de processamento. Por se tratar de um circuito específico, realizando uma função bem específica, é possível manter um tamanho compacto (300 qubits, dependendo do que é acelerado), mostrando adicionalmente que, caso computadores quânticos venham a existir, eles viabilizarão os criptossistemas pós-quânticos antes de quebrar os criptossistemas pré-quânticos. Adicionalmente, algumas tecnologias de implementação de computadores quânticos são estudadas, com especial enfoque na óptica linear e nas tecnologias baseadas em silício. Este estudo busca avaliar a viabilidade destas tecnologias como potenciais candidatas à construção de um computador quântico completo e de caráter pessoal. / The discovery of the Shor algorithm, which allows polynomial time factoring of integers, motivated efforts towards the implementation of a quantum computer. It is capable of breaking the main current public key cryptosystems used today (RSA and those based on elliptic curves). Those provide a set of security services, such as data confidentiality and integrity and source authentication, and also the distribution of a symmetric session key. To break those cryptosystem, a large quantum computer (2000 qubits) is needed. Nevertheless, cryptographers have started to look for alternatives. Some of which came from quantum mechanics itself. Despite some interesting properties found on quantum cryptography, a complete cryptosystem seems intangible, specially because of digital signatures, necessary to achieve authentication. Cryptosystems based on purely classical problems which are (believed) not treatable by quantum computers, called post-quantum, have them been proposed. Those systems still lacks of practicality, either because of the key size or the processing time. Among those post-quantum cryptosystems, specially the code based ones, the highlights are the McEliece and the Niederreiter cryptosystems. Per se, none of these provides digital signatures, but, the CFS signatures have been proposed, as a complement to them. Even if general purpose quantum computers are still far from our reality, it is possible to imagine a small dedicated quantum circuit. The benefits brought by it could make the deference to allow those signatures, in a truly post-quantum scenario. In this work, a quantum/classical hybrid architecture is proposed to accelerate post-quantum cryptographic algorithms. Two quantum coprocessors, implementing the Grover search, are proposed: one to assist the decoding process of Goppa codes, in the context of the McEliece and Niederreiter cryptosystems; another to assist the search for decodable syndromes, in the context of the CFS digital signatures. The results show that, for some cases, the use of the quantum coprocessor allows up to 99; 7% reduction in the key size and up to 76; 2% acceleration in the processing time. As a specific circuit, dealing with a well defined function, it is possible to keep a small size (300 qubits), depending on what is accelerated), showing that, if quantum computers come to existence, they will make post-quantum cryptosystems practical before breaking the current cryptosystems. Additionally, some implementation technologies of quantum computers are studied, in particular linear optics and silicon based technologies. This study aims to evaluate the feasibility of those technologies as potential candidates to the construction of a complete and personal quantum computer.

Trading card games (TCG) are distinct from traditional card games mainly because, in the former, the cards are not shared among players in a match. Instead, users play with the cards they own (e.g., that have been purchased or traded with other players), which correspond to a subset of all cards produced by the game provider. Even though most computer-based TCGs rely on a trusted third-party (TTP) for preventing cheating during trades, allowing them to securely do so in the absence of such entity, as in a Peer-to-Peer (P2P) scenario, remains a challenging task. Potential solutions for this challenge can be based on e-cash protocols, but not without adaptations, as those scenarios display different requirements: for example, TCGs should allow users to play with the cards under their possession, not only to be able to pass those cards over as with digital coins. In this work, we present and discuss the security requirements for allowing cards to be traded in TCGs and how they relate to e-cash. We then propose a concrete and efficient TTP-free protocol for trading cards in a privacy-preserving manner. The construction is based on a secure transferable e-cash protocol and on a P-signature scheme converted to the asymmetric pairing setting. According to our experimental results, the proposed protocol is quite efficient for use in practice: an entire deck is stored in less than 5 MB, while it takes a few seconds to be prepared for a match; the verification of the cards, on its turn, takes less time than an usual match, and can be performed in background while the game is played. / Jogos de cartas colecionáveis (TCG, do inglês Trading Card Game) diferem de jogos de cartas tradicionais principalmente porque as cartas não são compartilhadas em uma partida. Especificamente, os jogadores usam suas próprias cartas (obtidas, e.g., por meio de compra ou troca com outros jogadores), as quais correspondem a um subconjunto de todas as cartas criadas pelo produtor do jogo. Embora a maioria dos TCGs digitais atuais dependam de um terceiro confiável (TTP, do ingês Trusted Third-Party) para prevenir trapaças durante trocas, permitir que os jogadores troquem cartas de maneira segura sem tal entidade, como é o caso em um cenário peer-to-peer (P2P), ainda é uma tarefa desafiadora. Possíveis soluções para esse desafio podem ser baseadas em protocolos de moeda eletrônica, mas não sem adaptações decorrentes dos requisitos diferentes de cada cenário: por exemplo, TCGs devem permitir que usuários joguem com as suas cartas, não apenas que passem-nas adiante como ocorre com moedas eletrônicas. Neste trabalho, são apresentados e discutidos os principais requisitos de segurança para trocas de cartas TCGs e como eles se relacionam com moedas eletrônicas. Também é proposto um protocolo eficiente que permite trocas de cartas sem a necessidade de um TTP e com suporte a privacidade. A construção usa como base um protocolo seguro de moeda eletrônica e um protocolo de assinatura-P adaptado para utilizar emparelhamentos assimétricos, mais seguros que os simétricos. De acordo com os experimentos realizados, o protocolo proposto é bastante eficiente para uso na prática: são necessários apenas 5 MB para armazenar um baralho inteiro, enquanto a preparação do mesmo leva apenas alguns segundos; a verificação das cartas, por sua vez, é mais rápida que a duração comum de uma partida e pode ser executada em plano de fundo, durante a própria partida.

A descoberta do algoritmo de Shor, para a fatoração de inteiros em tempo polinomial, motivou esforços rumo a implementação de um computador quântico. Ele é capaz de quebrar os principais criptossistemas de chave pública usados hoje (RSA e baseados em curvas elípticas). Estes fornecem diversos serviços de segurança, tais como confidencialidade e integridade dos dados e autenticação da fonte, além de possibilitar a distribuição de uma chave simétrica de sessão. Para quebrar estes criptossistemas, um computador quântico grande (2000 qubits) é necessário. Todavia, alternativas começaram a ser investigadas. As primeiras respostas vieram da própria mecânica quântica. Apesar das propriedades interessantes encontradas na criptografia quântica, um criptossistema completo parece inatingível, principalmente devido as assinaturas digitais, essenciais para a autenticação. Foram então propostos criptossitemas baseadas em problemas puramente clássicos que (acredita-se) não são tratáveis por computadores quânticos, que são chamadas de pós-quânticas. Estes sistemas ainda sofrem da falta de praticidade, seja devido ao tamanho das chaves ou ao tempo de processamento. Dentre os criptossistemas pós-quânticos, destacam-se o McEliece e o Niederreiter. Por si só, nenhum deles prevê assinaturas digitais, no entanto, as assinaturas CFS foram propostas, complementandos. Ainda que computadores quânticos de propósito geral estejam longe de nossa realidade, é possível imaginar um circuito quântico pequeno e dedicado. A melhoria trazida por ele seria a diferença necessária para tornar essas assinaturas práticas em um cenário legitimamente pós-quântico. Neste trabalho, uma arquitetura híbrida quântica/clássica é proposta para acelerar algoritmos criptográficos pós-quânticos. Dois coprocessadores quânticos, implementando a busca de Grover, são propostos: um para auxiliar o processo de decodificação de códigos de Goppa, no contexto do criptossistema McEliece; outro para auxiliar na busca por síndromes decodificáveis, no contexto das assinaturas CFS. Os resultados mostram que em alguns casos, o uso de um coprocessador quântico permite ganhos de até 99; 7% no tamanho da chave e até 76; 2% em tempo de processamento. Por se tratar de um circuito específico, realizando uma função bem específica, é possível manter um tamanho compacto (300 qubits, dependendo do que é acelerado), mostrando adicionalmente que, caso computadores quânticos venham a existir, eles viabilizarão os criptossistemas pós-quânticos antes de quebrar os criptossistemas pré-quânticos. Adicionalmente, algumas tecnologias de implementação de computadores quânticos são estudadas, com especial enfoque na óptica linear e nas tecnologias baseadas em silício. Este estudo busca avaliar a viabilidade destas tecnologias como potenciais candidatas à construção de um computador quântico completo e de caráter pessoal. / The discovery of the Shor algorithm, which allows polynomial time factoring of integers, motivated efforts towards the implementation of a quantum computer. It is capable of breaking the main current public key cryptosystems used today (RSA and those based on elliptic curves). Those provide a set of security services, such as data confidentiality and integrity and source authentication, and also the distribution of a symmetric session key. To break those cryptosystem, a large quantum computer (2000 qubits) is needed. Nevertheless, cryptographers have started to look for alternatives. Some of which came from quantum mechanics itself. Despite some interesting properties found on quantum cryptography, a complete cryptosystem seems intangible, specially because of digital signatures, necessary to achieve authentication. Cryptosystems based on purely classical problems which are (believed) not treatable by quantum computers, called post-quantum, have them been proposed. Those systems still lacks of practicality, either because of the key size or the processing time. Among those post-quantum cryptosystems, specially the code based ones, the highlights are the McEliece and the Niederreiter cryptosystems. Per se, none of these provides digital signatures, but, the CFS signatures have been proposed, as a complement to them. Even if general purpose quantum computers are still far from our reality, it is possible to imagine a small dedicated quantum circuit. The benefits brought by it could make the deference to allow those signatures, in a truly post-quantum scenario. In this work, a quantum/classical hybrid architecture is proposed to accelerate post-quantum cryptographic algorithms. Two quantum coprocessors, implementing the Grover search, are proposed: one to assist the decoding process of Goppa codes, in the context of the McEliece and Niederreiter cryptosystems; another to assist the search for decodable syndromes, in the context of the CFS digital signatures. The results show that, for some cases, the use of the quantum coprocessor allows up to 99; 7% reduction in the key size and up to 76; 2% acceleration in the processing time. As a specific circuit, dealing with a well defined function, it is possible to keep a small size (300 qubits), depending on what is accelerated), showing that, if quantum computers come to existence, they will make post-quantum cryptosystems practical before breaking the current cryptosystems. Additionally, some implementation technologies of quantum computers are studied, in particular linear optics and silicon based technologies. This study aims to evaluate the feasibility of those technologies as potential candidates to the construction of a complete and personal quantum computer.