Resumo: Um esquema de assinatura digital é uma importante ferramenta para a criptografia de chave pública e uma tecnologia essencial para prover autenticidade, integridade e irretratabilidade. Assinaturas digitais são utilizadas em muitas aplicações práticas, tais como: eCommerce, eGovernment, distribuição de software, autenticação de usuários, dentre outras aplicações. Os esquemas de assinaturas digitais mais utilizados nos dias de hoje são o RSA, o DSA, o ECDSA e o EdDSA. Estes esquemas não são imunes aos computadores quânticos, pois sua segurança depende da dificuldade de fatorar grandes números inteiros e calcular logaritmos discretos. O esquema de assinatura digital de Merkle e suas variantes são baseados em funções de resumo e são considerados resistentes aos computadores quânticos. Estes esquemas são candidatos promissores a esquemas de assinaturas digitais com segurança quântica e têm sido objeto de esforços para padronização. Neste trabalho, apresenta-se uma implementação otimizada em software de duas propostas de padrão para o esquema digital de Merkle usando um conjunto de instruções AVX2 nos processadores Haswell e Skylake. A implementação utiliza várias técnicas de otimização para acelerar a função de resumo subjacente, o que se resulta em um melhor desempenho nos algoritmos de geração de chaves, assinatura e verificação. A implementação utilizou os parâmetros selecionados pelas propostas do LMS e do XMSS. Os desempenhos das implementações foram medidos em um processador Haswell (Intel Core i7-4770K de 3,4 GHz) e Skylake (Intel Core i7-6700K de 4,2 GHz). Em particular, a operação de assinatura do esquema XMSS, usando SHA-256 no processador Skylake, pode ser calculada em 3.884.005 ciclos (1.031 assinaturas por segundo) para o nível de segurança de 128 bits (contra ataques quânticos), usando uma árvore de altura 60 com 12 camadas. Para o LMS, a mesma operação requer 1.287.778 ciclos (3.115 assinaturas por segundo). As chaves de assinaturas do XMSS e do LMS têm o mesmo tamanho, porém, no LMS, a chave privada é menor do que no XMSS, enquanto a chave pública é maior do que no XMSS. Os resultados indicam que ambas as propostas para esquemas de assinaturas baseadas em funções de resumo, LMS e XMSS, têm alto desempenho usando uma implementação vetorial nos modernos processadores da Intel Ver menos

Abstract: A digital signature scheme is a relevant tool for public key cryptography and an essential technology to provide authenticity, integrity, and non-repudiation of data. Digital signatures are used in many practical applications, such as eCommerce, eGovernment, software distribution, user authentication, and various other applications. The digital signature algorithms that are used in practice today are RSA, DSA, ECDSA and EdDSA. They are not quantum immune since their security relies on the difficulty of factoring large composite integers and computing discrete logarithms. The Merkle digital signature scheme (and its variants) is based on hash functions and is considered secure against quantum computing. Merkle-based schemes are promising candidates for providing digital signature schemes in the quantum scenario, and for that reason, these schemes have been proposed for standardization. In this work, we present an optimized software implementation of two standard proposals of hash-based signatures using a set of AVX2 instructions on Haswell and Skylake processors. The implementation uses various optimization techniques to speed up the underlying hash function evaluation, and consequently, the algorithms for key generation, signature, and verification process. The implementation use the parameters specified in the proposals LMS and XMSS. The performance of the implementation results was measured in a modern Haswell processor (Intel Core i7-4770K 3,4 GHz) and Skylake (Intel Core i7-6700K 4,2 GHz). In particular, the signature operation in XMSS scheme, using SHA-256 in the Skylake processor, can be calculated in 3,884,005 cycles (1,031 signatures per second) for a 128-bit security level (against quantum attacks) using a tree of height 60 and 12 layers. For the LMS, signature operation requires 1,287,778 cycles (3,115 signatures per second). Both XMSS and LMS signature keys are equal in size, however, in the LMS, the private key is smaller than XMSS, while the public key is larger than XMSS. The results indicate that both proposals LMS and XMSS for signature schemes based on hash functions have high performance using a vector implementation on recent Intel processors Ver menos