Orientador: Ricardo Dahab / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-22T11:38:01Z (GMT). No. of bitstreams: 1 OnikiChiquito_Izumi_M.pdf: 3419663 bytes, checksum: 5f621e251ebc62429a85ff141091f7f5 (MD5) Previous issue date: 2012 / Resumo: Na área de Segurança da Informação, controle de acesso diz respeito á habilidade de permitir ou negar a utilização de determinados recursos, sejam eles informações, dispositivos, serviços etc., por parte de um indivíduo. Protocolos de identificação correspondem a algoritmos criptográficos que permitem verificar, com certo grau de confiança, se a alegação de um indivíduo a respeito de sua identidade é verdadeira. Dessa forma, pode-se prover acesso controlado e conceder privilégios de utilização de recursos somente a entidades ou indivíduos cuja identidade tenha sido comprovada. Algoritmos baseados em reticulados, de uma forma geral, têm despertado particular interesse em aplicações criptográficas, devido à sua provável resistência a ataques empregando computadores quânticos, ao contrário dos criptossistemas baseados em problemas da Teoria dos Números. Por esse motivo, nos _últimos anos, tem-se buscado desenvolver protocolos de identificação cuja segurança esteja relacionada a problemas envolvendo reticulados. Neste trabalho, foram abordadas as principais propostas recentes de protocolos de identificação baseados em reticulados. Além da apresentação dos algoritmos, é feita uma análise comparativa entre protocolos selecionados, incorporando dados experimentais de execução. A etapa de implementação aqui apresentada tem também como finalidade suprir a ausência de resultados experimentais para essa categoria de protocolos, no sentido de iniciar um processo de validação para uso dos algoritmos em aplicações práticas. Questões como possibilidades de otimização e expectativas para o futuro da área também são discutidas / Abstract: One of the main concerns of the field of Information Security is access control, which refers to the restriction of access to several kinds of resources, such as data, places, devices, services and others. Identification schemes are cryptographic algorithms that allow verifying with some level of certainty if an identity claim is legitimate. Therefore, such schemes make possible to provide access control and grant privileges only to authorized individuals whose identities have been previously verified. Lattice-based algorithms are particularly interesting as the cryptography community believes them to remain secure even to quantum computers attacks, as opposite to some cryptosystems used today based on Number Theory problems. For this reason, identification schemes based on lattices have received growing attention lately. In this work, we address the main recent developments of lattice-based identification schemes. After introducing the algorithms, we make a comparative analysis of the selected schemes, using experimental data collected from our own implementation of the algorithms. The implementation phase also aims to help validating these schemes for practical use, since to this date there were practically no experimental results available. Other issues, like optimization possibilities and the future of the area, are also addressed in this work / Mestrado / Ciência da Computação / Mestra em Ciência da Computação

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.

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.

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.

Atualmente, podemos perceber que uma grande dependência dos sistemas desenvolvidos sob a seara da criptografia foi instaurada em todos nós. Principalmente no tocante dos sistemas criptográficos de chave pública, que são vastamente utilizados na Internet. No entanto, a criptografia de chave pública viu-se ameaçada e começou a investigar novas fontes de problemas para seus sistemas quando Shor em 1997 desenvolveu um algoritmo de tempo polinomial para fatorar inteiros e para calcular o logaritmo discreto em um computador quântico. Neste contexto, Patarin propõe a função alçapão HFE (Hidden Field Equations), uma trapdoor baseada nos Problemas MQ (Multivariate Quadratic) e IP (Isomorfismo de Polinômios). Tais problemas não são afetados pelo algoritmo de Shor, além disto o Problema MQ foi demonstrado por Patarin e Goubin como sendo NP-completo. Apesar do HFE ter sua versão básica quebrada, ele apresenta variações -- obtidas através de modificadores genéricos -- resistentes aos principais ataques da atualidade. O Quartz -- esquema de assinatura digital baseado no HFEv-, com escolha especial de parâmetros -- é um bom exemplo desta resistência a ataques algébricos que visem a recuperação da chave privada, pois até hoje permanece seguro. Além de também se destacar por gerar assinaturas curtas. Todavia, Joux e Martinet -- baseados em axiomas do Ataque pelo Paradoxo de Aniversário -- provaram que o Quartz é maleável, demonstrando que caso o adversário possua um par (mensagem, assinatura) válido, ele conseguirá obter uma segunda assinatura com 2^(50) computações e 2^(50) chamadas ao oráculo de assinatura, logo muito abaixo dos padrões de segurança atuais que são de, no mínimo, 2^(112). Desta forma, baseado no Quartz, apresentamos um novo esquema de assinatura digital resistente a ataques adaptativos de mensagem escolhida que realizem chamadas ao oráculo aleatório, com um nível de segurança estimado em 2^(112). Nosso criptossistema proporciona, ainda, um ganho de eficiência no algoritmo de verificação de assinatura e na inicialização dos vetores que serão utilizados pelos algoritmos de assinatura e verificação. Além de, também, disponibilizarmos uma implementação do Quartz Original e do Quartz Aprimorado, na linguagem de programação Java. / Today, we can see that a large dependence of the systems developed under the cryptography was introduced in all of us. Especially in terms of public key cryptosystems, which are widely used on the Internet. However, public key cryptography was threatened and began to investigate new sources of problems for their systems when Shor in 1997 developed a polynomial time algorithm for factoring integers and to compute the discrete logarithm in a quantum computer. In this context, Patarin proposed Hidden Field Equations (HFE), a trapdoor based on MQ (Multivariate Quadratic) and IP (Isomorphism of Polynomials) problems. Such problems are not affected by the Shor algorithm, moreover MQ Problem was demonstrate by Patarin and Goubin as NP-complete. Despite the basic HFE has broken, it varies secure, obtained by generic modification. The Quartz -- digital signature scheme based on HFEv-, with special choice of parameters -- is a good example of this resistance to algebraic attacks aimed at the recovery of the private key, because even today remains secure. Furthermore, it also generates short signatures. However, Joux and Martinet -- based on axioms of Birthday Paradox Attack -- proved that Quartz is malleable, showing that if the adversary has a pair (message, signature) valid, he can get a second signature with 2^(50) computations and 2^(50) calls to the signing oracle, so far the current security standards that are at least 2^(112). Thus, based on Quartz, we present a new digital signature scheme, achieving the adaptive chosen message attacks that make calls to the random oracle, with a secure level estimated at 2^(112). Our cryptosystem also provides an efficiency gain in signature verification algorithm and initialization vectors that will be used for signing and verification algorithms. Further we provide an implementation of Original Quartz and Enhanced Quartz in the Java programming language.

Atualmente, podemos perceber que uma grande dependência dos sistemas desenvolvidos sob a seara da criptografia foi instaurada em todos nós. Principalmente no tocante dos sistemas criptográficos de chave pública, que são vastamente utilizados na Internet. No entanto, a criptografia de chave pública viu-se ameaçada e começou a investigar novas fontes de problemas para seus sistemas quando Shor em 1997 desenvolveu um algoritmo de tempo polinomial para fatorar inteiros e para calcular o logaritmo discreto em um computador quântico. Neste contexto, Patarin propõe a função alçapão HFE (Hidden Field Equations), uma trapdoor baseada nos Problemas MQ (Multivariate Quadratic) e IP (Isomorfismo de Polinômios). Tais problemas não são afetados pelo algoritmo de Shor, além disto o Problema MQ foi demonstrado por Patarin e Goubin como sendo NP-completo. Apesar do HFE ter sua versão básica quebrada, ele apresenta variações -- obtidas através de modificadores genéricos -- resistentes aos principais ataques da atualidade. O Quartz -- esquema de assinatura digital baseado no HFEv-, com escolha especial de parâmetros -- é um bom exemplo desta resistência a ataques algébricos que visem a recuperação da chave privada, pois até hoje permanece seguro. Além de também se destacar por gerar assinaturas curtas. Todavia, Joux e Martinet -- baseados em axiomas do Ataque pelo Paradoxo de Aniversário -- provaram que o Quartz é maleável, demonstrando que caso o adversário possua um par (mensagem, assinatura) válido, ele conseguirá obter uma segunda assinatura com 2^(50) computações e 2^(50) chamadas ao oráculo de assinatura, logo muito abaixo dos padrões de segurança atuais que são de, no mínimo, 2^(112). Desta forma, baseado no Quartz, apresentamos um novo esquema de assinatura digital resistente a ataques adaptativos de mensagem escolhida que realizem chamadas ao oráculo aleatório, com um nível de segurança estimado em 2^(112). Nosso criptossistema proporciona, ainda, um ganho de eficiência no algoritmo de verificação de assinatura e na inicialização dos vetores que serão utilizados pelos algoritmos de assinatura e verificação. Além de, também, disponibilizarmos uma implementação do Quartz Original e do Quartz Aprimorado, na linguagem de programação Java. / Today, we can see that a large dependence of the systems developed under the cryptography was introduced in all of us. Especially in terms of public key cryptosystems, which are widely used on the Internet. However, public key cryptography was threatened and began to investigate new sources of problems for their systems when Shor in 1997 developed a polynomial time algorithm for factoring integers and to compute the discrete logarithm in a quantum computer. In this context, Patarin proposed Hidden Field Equations (HFE), a trapdoor based on MQ (Multivariate Quadratic) and IP (Isomorphism of Polynomials) problems. Such problems are not affected by the Shor algorithm, moreover MQ Problem was demonstrate by Patarin and Goubin as NP-complete. Despite the basic HFE has broken, it varies secure, obtained by generic modification. The Quartz -- digital signature scheme based on HFEv-, with special choice of parameters -- is a good example of this resistance to algebraic attacks aimed at the recovery of the private key, because even today remains secure. Furthermore, it also generates short signatures. However, Joux and Martinet -- based on axioms of Birthday Paradox Attack -- proved that Quartz is malleable, showing that if the adversary has a pair (message, signature) valid, he can get a second signature with 2^(50) computations and 2^(50) calls to the signing oracle, so far the current security standards that are at least 2^(112). Thus, based on Quartz, we present a new digital signature scheme, achieving the adaptive chosen message attacks that make calls to the random oracle, with a secure level estimated at 2^(112). Our cryptosystem also provides an efficiency gain in signature verification algorithm and initialization vectors that will be used for signing and verification algorithms. Further we provide an implementation of Original Quartz and Enhanced Quartz in the Java programming language.

Os sistemas criptográficos de chave pública amplamente utilizados hoje em dia tem sua segurança baseada na suposição da intratabilidade dos problemas de fatoração de inteiros e do logaritmo discreto, sendo que ambos foram demonstrados inseguros sob o advento dos computadores quânticos. Sistemas criptográficos baseados em Multivariáveis Quadráticas (MQ) utilizam como base o problema MQ, que consiste em resolver um sistema de equações polinomiais multivariáveis quadráticas sobre um corpo finito. O problema MQ foi provado como sendo NP-completo e até hoje não se conhece algoritmo, nem mesmo quântico, de tempo polinomial que possa resolver o problema, fazendo com que sistemas criptográficos baseados nesta primitiva mereçam ser investigados e desenvolvidos como reais candidatos a proverem nossa criptografia pós-quântica. Durante a CRYPTO\'2011 Sakumoto, Shirai e Hiwatari introduziram dois novos protocolos de identificação baseados em polinômios multivariáveis quadráticos, os quais chamamos de MQID-3 e MQID-5, e que em especial e pela primeira vez, tem sua segurança reduzida apenas ao problema MQ. Baseados nestas propostas iremos apresentar uma versão aprimorada do protocolo MQID-3 na qual teremos uma redução da comunicação necessária em aproximadamente 9%. / The public-key cryptography widely used nowadays have their security based on the assumption of the intractability of the problems of integer factorization and discrete logarithm, both of which were proven unsafe in the advent of quantum computers. Cryptographic systems based on Multivariate Quadratic polynomials (MQ) are based on the MQ problem, which consists in solve a system of multivariate quadratic polynomials over a finite field. The MQ problem has been proven NP-complete and so far no polynomial time algorithm is known, not even quantum, which would resolve this problem, making worthwhile to be investigated and developed as a real candidate to provide post-quantum cryptography. In CRYPTO\'2011 Sakumoto, Shirai and Hiwatari introduced two new identification protocols based on multivariate quadratic polynomials, which we call MQID-3 and MQID-5, in particular, for the first time, their security is based only on the MQ problem. Using these proposals, we will present an improved version of the protocol MQID-3 that reduces communication by approximately 9%.

The conventional digital signature schemes widely used today may have their security threatened with the possibility of the rising of a large quantum computer. Moreover, such schemes are not entirely suitable for utilization on very constrained-resource platforms. Therefore, there is a need to look at alternatives that present reasonable security in the medium and long term, in addition to attaining acceptable performance when few resources are available. This work provides more efficient multivariate and hash-based post-quantum digital signatures and targets the deployment in scenarios like Internet of Things and Wireless Sensor Networks where the typical devices are very resource-constrained. In the context of multivariable quadratic digital signatures we describe a new technique that attempts to minimize the main drawbacks of these schemes, the large key sizes. The new technique explores certain structures compact matrix rings. Some of the analyzed matrix rings are not secure (one of the attacks runs in polynomial time). Other less compact matrix rings are investigated and they apparently do not suffer a polynomial time attack, but unfortunately are still far from deployment on very constrained platforms. On the other hand, this work describes a method for hash-based signatures providing a 2/3 reduction of the signature sizes in the Merkle-Winternitz multi-time signature scheme. In fact, the signature sizes constitute the main bottleneck of these schemes. The improvement also leads to a 2/3 reduction in the run times (key generation, signing and verifying) and in energy consumption for all these operations on an AVR ATmega128L microcontroller, typically found in Wireless Sensor Networks. This result is much more promising for the deployment in an IoT scenario. / Os esquemas convencionais de assinatura digital mais usados na atualidade têm sua segurança ameaçada com a possibilidade da construção de um computador quântico de grande porte. Ademias, tais esquemas não têm se mostrado completamente adequados para uso em plataformas com recursos computacionais extremamente escassos. Surge então a necessidade da busca por alternativas que satisfaçam as condições de segurança a médio e longo prazo, além de apresentarem desempenho razoável quando poucos recursos computacionais estão disponíveis. Este trabalho obtém assinaturas digitais pós-quânticas multivariadas quadráticas e baseadas em hash mais eficientes e tem o intuito de torna-las práticas em cenários como Internet das Coisas e Redes de Sensores Sem Fio (RSSF), caracterizados por apresentarem dispositivos com recursos computacionais limitados. No contexto de assinaturas multivariadas quadráticas, descreve-se uma nova técnica que tenta minimizar o principal gargalo desses esquemas, o grande tamanho de chaves. A nova técnica explora certos anéis matriciais com estrutura compacta. Mostra-se que alguns dos anéis analisados não são seguros (um dos ataques apresenta tempo polinomial), enquanto outros anéis menos compactos aparentam não sofrer ataque polinomial, mas infelizmente ainda não são adequados para uso em dispositivos muito restritos. Por outro lado, descreve-se um método para obter assinaturas digitais baseadas em hash que fornece redução das assinaturas para 2/3 do tamanho original do esquema multi-time Merkle-Winternitz. De fato, o tamanho das assinaturas constitui o principal gargalo desses esquemas, A melhoria também acarreta uma redução em 2/3 nos tempos de execução (geração de chave, geração de assinaturas e verificação de assinatura) e no consumo de energia para essas operações quando executadas em um microcontrolador AVR tipicamente usado em Redes de Sensores Sem Fio, o AT-mega 128L. Este resultado torna-se promissor para implantação de assinaturas baseadas em hash no cenário de Internet das Coisas.

The conventional digital signature schemes widely used today may have their security threatened with the possibility of the rising of a large quantum computer. Moreover, such schemes are not entirely suitable for utilization on very constrained-resource platforms. Therefore, there is a need to look at alternatives that present reasonable security in the medium and long term, in addition to attaining acceptable performance when few resources are available. This work provides more efficient multivariate and hash-based post-quantum digital signatures and targets the deployment in scenarios like Internet of Things and Wireless Sensor Networks where the typical devices are very resource-constrained. In the context of multivariable quadratic digital signatures we describe a new technique that attempts to minimize the main drawbacks of these schemes, the large key sizes. The new technique explores certain structures compact matrix rings. Some of the analyzed matrix rings are not secure (one of the attacks runs in polynomial time). Other less compact matrix rings are investigated and they apparently do not suffer a polynomial time attack, but unfortunately are still far from deployment on very constrained platforms. On the other hand, this work describes a method for hash-based signatures providing a 2/3 reduction of the signature sizes in the Merkle-Winternitz multi-time signature scheme. In fact, the signature sizes constitute the main bottleneck of these schemes. The improvement also leads to a 2/3 reduction in the run times (key generation, signing and verifying) and in energy consumption for all these operations on an AVR ATmega128L microcontroller, typically found in Wireless Sensor Networks. This result is much more promising for the deployment in an IoT scenario. / Os esquemas convencionais de assinatura digital mais usados na atualidade têm sua segurança ameaçada com a possibilidade da construção de um computador quântico de grande porte. Ademias, tais esquemas não têm se mostrado completamente adequados para uso em plataformas com recursos computacionais extremamente escassos. Surge então a necessidade da busca por alternativas que satisfaçam as condições de segurança a médio e longo prazo, além de apresentarem desempenho razoável quando poucos recursos computacionais estão disponíveis. Este trabalho obtém assinaturas digitais pós-quânticas multivariadas quadráticas e baseadas em hash mais eficientes e tem o intuito de torna-las práticas em cenários como Internet das Coisas e Redes de Sensores Sem Fio (RSSF), caracterizados por apresentarem dispositivos com recursos computacionais limitados. No contexto de assinaturas multivariadas quadráticas, descreve-se uma nova técnica que tenta minimizar o principal gargalo desses esquemas, o grande tamanho de chaves. A nova técnica explora certos anéis matriciais com estrutura compacta. Mostra-se que alguns dos anéis analisados não são seguros (um dos ataques apresenta tempo polinomial), enquanto outros anéis menos compactos aparentam não sofrer ataque polinomial, mas infelizmente ainda não são adequados para uso em dispositivos muito restritos. Por outro lado, descreve-se um método para obter assinaturas digitais baseadas em hash que fornece redução das assinaturas para 2/3 do tamanho original do esquema multi-time Merkle-Winternitz. De fato, o tamanho das assinaturas constitui o principal gargalo desses esquemas, A melhoria também acarreta uma redução em 2/3 nos tempos de execução (geração de chave, geração de assinaturas e verificação de assinatura) e no consumo de energia para essas operações quando executadas em um microcontrolador AVR tipicamente usado em Redes de Sensores Sem Fio, o AT-mega 128L. Este resultado torna-se promissor para implantação de assinaturas baseadas em hash no cenário de Internet das Coisas.