Cryptographic digital signatures provide authentication to communicating parties over communication networks. They are integral asymmetric primitives in cryptography. The current digital signature infrastructure adopts schemes that rely on the hardness of finding discrete logarithms and factoring in finite groups. Given the recent advances in physics which point towards the eventual construction of large scale quantum computers, these hard problems will be solved in polynomial time using Shor’s algorithm. Hence, there is a clear need to migrate the cryptographic infrastructure to post-quantum secure alternatives. Such an initiative is demonstrated by the PQCRYPTO project and the current Post-Quantum Cryptography (PQC) standardization competition run by the National Institute of Standards and Technology (NIST). This dissertation considers hash-based digital signature schemes. Such algorithms rely on simple security notions such as preimage, and weak and strong collision resistances of hash functions. These notions are well-understood and their security against quantum computers has been well-analyzed. However, existing hash-based signature schemes have large signature sizes and high computational costs. Moreover, the signature size increases with the number of messages to be signed by a key pair. The goal of this work is to develop hash-based digital signature schemes to overcome the aforementioned limitations. First, FORS, the underlying few-time signature scheme of the NIST PQC alternate candidate SPHINCS+ is analyzed against adaptive chosen message attacks, and DFORS, a few-time signature scheme with adaptive chosen message security, is proposed. Second, a new variant of SPHINCS+ is introduced that improves the computational cost and security level. Security analysis for the new variant is presented. In addition, the hash-based group digital signature schemes, Group Merkle (GM) and Dynamic Group Merkle (DGM), are studied and their security is analyzed. Group Merkle Multi-Treem (GMMT) is proposed to solve some of the limitations of the GM and DGM hash-based group signature schemes. / Graduate

No description available.

No description available.

Hash-based signature schemes are a class of post-quantum algorithms that usually consist of hash-trees built upon OTS solutions. These schemes have small key sizes, eficient processing and are simple to implement, while their security properties rely basically on the pre-image or collision resistance of the their underlying hash function. Despite such advantages, however, they have relatively large signature sizes compared to traditional signature algorithms. One way of tackling this issue is to reduce the sizes of their underlying OTS algorithms. Besides that, in applications where signature verifications are done much more frequently than signature generation (e.g. trusted software distribution), it is desirable that signature verification has less overhead than signature generation. In this work, two contributions are presented to tackle these issues. The first one is a probabilistic technique that, with negligible processing overhead, allows reductions in the underlying OTS signature sizes; namely, up to 12.5% average size reduction can be achieved depending on the w parameter chosen for the signature (however, for w = 4 the reduction is only 0.2%). The second contribution is a novel OTS scheme which has all advantages of W-OTS and W-OTS+ and yet has much faster signature verification times at the cost of slightly slower signature generation times. / Esquemas de assinaturas baseadas em hash são uma classe de algoritmos pós-quânticos que basicamente consistem em árvores de hash construídas em cima de soluções de assinaturas unitárias (OTS). Tais esquemas possuem tamanhos pequenos de chaves, processamento eficiente e são simples de se implementar, enquanto que a segurança desses esquemas baseia-se na resistência à pré-imagem ou à colisão das funções de hash utilizadas. Apesar dessas vantagens, eles possuem tamanhos de assinaturas relativamente grandes comparados aos algoritmos tradicionais de assinatura. Nesse caso, uma forma de lidar com essa questão é reduzir os tamanhos de assinatura das OTS utilizadas. Além disso, em aplicações em que se faz muito mais verificações de assinatura do que gerações de assinatura, é desejável que a vericação seja significativamente mais rápida do que a geração. Nesse trabalho, duas contribuições são apresentadas para mitigar os problemas acima mencionados. A primeira é uma técnica probabilística que permite a redução do tamanho das assinaturas nas OTS utilizadas com custo adicional de processamento desprezível, isto é, pode-se alcançar uma redução média de até 12.5% dependendo do valor de w escolhido para a assinatura (no entanto, para w = 4 a redução é de apenas 0.2%). A segunda contribuição é um esquema inovador de assinatura digital que possui todas as vantagens do W-OTS e do W-OTS+, além de possuir verificação bem mais rápida do que estes em troca de uma geração de assinatura um pouco mais lenta.

In 2001, Boneh, Lynn, and Shacham presented a pairing-based signature scheme known as the BLS signature scheme. In 2003, Boneh, Gentry, Lynn, and Shacham presented the first aggregate signature scheme called the BGLS aggregate signature scheme. The BGLS scheme allows for N users with N signatures to combine their signatures into a single signature. The size of the resulting signature is independent of N. The BGLS signature scheme enjoys roughly the same level of security as the BLS scheme. In 2005, Waters presented a pairing-based signature scheme which does not assume the existence of random oracles. In 2007, Lu, Ostrovsky, Sahai, Shacham, and Waters presented the LOSSW aggregate signature scheme which does not assume the existence of random oracles. The BLS, BGLS, Waters, and LOSSW authors each chose to work with a restricted class of pairings. In each scheme, it is clear that the scheme extend to arbitrary pairings. We present the schemes in their full generality, explore variations of the schemes, and discuss optimizations that can be made when using specific pairings. Each of the schemes we discuss is secure assuming that the computational Diffie-Hellman (CDH) assumption holds. We improve on the security reduction for a variation of the BGLS signature scheme which allows for some restrictions of the BGLS signature scheme can be dropped and provides a stronger guarantee of security. We show that the BGLS scheme can be modified to reduce public-key size in presence of a certifying authority, when a certain type of pairing is used. We show that patient-free bit-compression can be applied to each of the scheme with a few modifications.

In 2001, Boneh, Lynn, and Shacham presented a pairing-based signature scheme known as the BLS signature scheme. In 2003, Boneh, Gentry, Lynn, and Shacham presented the first aggregate signature scheme called the BGLS aggregate signature scheme. The BGLS scheme allows for N users with N signatures to combine their signatures into a single signature. The size of the resulting signature is independent of N. The BGLS signature scheme enjoys roughly the same level of security as the BLS scheme. In 2005, Waters presented a pairing-based signature scheme which does not assume the existence of random oracles. In 2007, Lu, Ostrovsky, Sahai, Shacham, and Waters presented the LOSSW aggregate signature scheme which does not assume the existence of random oracles. The BLS, BGLS, Waters, and LOSSW authors each chose to work with a restricted class of pairings. In each scheme, it is clear that the scheme extend to arbitrary pairings. We present the schemes in their full generality, explore variations of the schemes, and discuss optimizations that can be made when using specific pairings. Each of the schemes we discuss is secure assuming that the computational Diffie-Hellman (CDH) assumption holds. We improve on the security reduction for a variation of the BGLS signature scheme which allows for some restrictions of the BGLS signature scheme can be dropped and provides a stronger guarantee of security. We show that the BGLS scheme can be modified to reduce public-key size in presence of a certifying authority, when a certain type of pairing is used. We show that patient-free bit-compression can be applied to each of the scheme with a few modifications.

The thesis briefly describes the digital signatures and basic methods (RSA, DSA, ECDSA) for the creation and verification of the digital signature. The method of group signatures designed by Boneh, Boyen and Shacham (BBS) is described in more details as well as the method designed by Bonen and Shacham (BS). The thesis further explores related issue of the implementation of batch signing and verification for the above mentioned methods and their practical application, particularly for systems Vehicular ad-hod network (VANET) and cloud storage in the field of forensic IT. The purpose of the thesis is to determine which of the methods BBS and BS is more suitable for these systems in terms of computational complexity. For this reason, the author created the program for the comparison of methods BBS and BS. The programme compares the time consumption of the methods for signing and verification of incoming messages. The results of the measurement are summarized in the conclusion along with the justification why the particular methods are suitable for the systems.

O crescimento acelerado de negócios voltado para Internet aumenta significativamente a necessidade por mecanismos que possam garantir a confidencialidade dos dados, fornecendo ferramentas para autenticidade e irretratabilidade dos usuários em qualquer meio de comunicação, mesmo em equipamentos que possuem recursos computacionais limitados, como um telefone celular, por exemplo. Este trabalho apresenta um esquema de criptografia que utiliza os dados pessoais para geração de chave e cifração, chamado Criptografia Baseada na Identidade, sem necessidade de um certificado digital. São apresentados diversos modelos de cifração, assinatura, acordo de chaves, bem como principais características, diferenças operacionais e respectivos aspectos relevantes de segurança. Algumas aplicabilidades como busca de dados cifrados, por exemplo, são implementadas, para melhor entendimento das operações e fases envolvidas. Os comparativos de custos computacionais das operações envolvidas destacam o esquema de assinatura de Barreto et al. (2005) e esquema de acordo de chave Mc- Cullagh e Barreto (2004b). São descritos também os pré-requisitos de um ambiente criptográfico baseado na identidade, o qual permite realizar as operações de cifração, assinatura e acordo de chaves com menor custo computacional possível. / The accelerated growth of Internet-based business increase significantly the need for mechanisms that can guarantee the data confidentiality, providing tools for authenticity and non-repudiation users in any medium of communication, even with computer resources becoming increasingly scarce, eg into a cell phone. This paper describes an encryption scheme that uses personal data for key generation and encryption, called the Identity Based Encryption, without need for a digital certificate. Various encryption schemes, signature, key agreement are shown, and its main characteristics, operational differences and their respective relevant aspects of security. Some aplicabilities such as encrypted data search, for example, are implemented, for better understanding of the operations and stages involved. The comparative computataional costs of operations highlight the Barreto et al. (2005) signature scheme and McCullagh e Barreto (2004b) key agreement scheme. They are also described, the prerequisites of an Identity-based cryptography environment, which allows to perform the operations of encryption, signing and key agreement with lower computational cost possible.

O crescimento acelerado de negócios voltado para Internet aumenta significativamente a necessidade por mecanismos que possam garantir a confidencialidade dos dados, fornecendo ferramentas para autenticidade e irretratabilidade dos usuários em qualquer meio de comunicação, mesmo em equipamentos que possuem recursos computacionais limitados, como um telefone celular, por exemplo. Este trabalho apresenta um esquema de criptografia que utiliza os dados pessoais para geração de chave e cifração, chamado Criptografia Baseada na Identidade, sem necessidade de um certificado digital. São apresentados diversos modelos de cifração, assinatura, acordo de chaves, bem como principais características, diferenças operacionais e respectivos aspectos relevantes de segurança. Algumas aplicabilidades como busca de dados cifrados, por exemplo, são implementadas, para melhor entendimento das operações e fases envolvidas. Os comparativos de custos computacionais das operações envolvidas destacam o esquema de assinatura de Barreto et al. (2005) e esquema de acordo de chave Mc- Cullagh e Barreto (2004b). São descritos também os pré-requisitos de um ambiente criptográfico baseado na identidade, o qual permite realizar as operações de cifração, assinatura e acordo de chaves com menor custo computacional possível. / The accelerated growth of Internet-based business increase significantly the need for mechanisms that can guarantee the data confidentiality, providing tools for authenticity and non-repudiation users in any medium of communication, even with computer resources becoming increasingly scarce, eg into a cell phone. This paper describes an encryption scheme that uses personal data for key generation and encryption, called the Identity Based Encryption, without need for a digital certificate. Various encryption schemes, signature, key agreement are shown, and its main characteristics, operational differences and their respective relevant aspects of security. Some aplicabilities such as encrypted data search, for example, are implemented, for better understanding of the operations and stages involved. The comparative computataional costs of operations highlight the Barreto et al. (2005) signature scheme and McCullagh e Barreto (2004b) key agreement scheme. They are also described, the prerequisites of an Identity-based cryptography environment, which allows to perform the operations of encryption, signing and key agreement with lower computational cost possible.

Online/offline signature schemes are useful in many situations, and two such scenarios are considered in this dissertation: bursty server authentication and embedded device authentication. In this dissertation, new techniques for online/offline signing are introduced, those are applied in a variety of ways for creating online/offline signature schemes, and five different online/offline signature schemes that are proved secure under a variety of models and assumptions are proposed. Two of the proposed five schemes have the best offline or best online performance of any currently known technique, and are particularly well-suited for the scenarios that are considered in this dissertation. To determine if the proposed schemes provide the expected practical improvements, a series of experiments were conducted comparing the proposed schemes with each other and with other state-of-the-art schemes in this area, both on a desktop class computer, and under AVR Studio, a simulation platform for an 8-bit processor that is popular for embedded systems. Under AVR Studio, the proposed SGE scheme using a typical key size for the embedded device authentication scenario, can complete the offline phase in about 24 seconds and then produce a signature (the online phase) in 15 milliseconds, which is the best offline performance of any known signature scheme that has been proven secure in the standard model. In the tests on a desktop class computer, the proposed SGS scheme, which has the best online performance and is designed for the bursty server authentication scenario, generated 469,109 signatures per second, and the Schnorr scheme (the next best scheme in terms of online performance) generated only 223,548 signatures. The experimental results demonstrate that the SGE and SGS schemes are the most efficient techniques for embedded device authentication and bursty server authentication, respectively.