Postquantum preimage chameleon hash functions for digital signatures

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Ciência da Computação, Florianópolis, 2021.Postquantum Preimage Chameleon Hash Functions for Digital SignaturesResumo: Funções de hash camaleão são funções hash (ou funções de resumo criptográfico) com um segredo associado (seu \"trapdoor\") que permite o cálculo de sua primeira ou segunda pré-imagem somente para aqueles que o conhecem. Essa dissertação apresenta uma revisão sobre diferentes construções de hash camaleão e suas aplicações, em especial para o uso de assinaturas digitais. Também propomos uma nova construção de assinatura com uma prova de segurança no modelo do oráculo aleatório, adaptável para adversários clássicos e pós-quânticos. Apresentamos também resultados de sua implementação. A assinatura proposta tem uma propriedade nova de que um par formado pela mensagem e sua assinatura armazena qualquer dado arbitrário que seja escolhido durante a geração de chaves, o qual pode ser revelado computando um hash da mensagem e sua assinatura. Isso pode ser usado para construir assinaturas digitais mais amigáveis ao usuário e ligar um par de chaves a dados biométricos de seu proprietário. Nossa construção também se destaca por ser a primeira assinatura baseada em hash camaleão provada segura neste modelo específico de segurança.Abstract: Chameleon hash functions are hash functions with an associated trapdoor that allows for first or second preimage computation. Without the knowledge of this trapdoor, the chameleon hash is collision-resistant like usual hash functions. This thesis presents a review about different constructions of chameleon hash functions and some applications. We review previous uses of chameleon hash functions to build digital signature schemes and propose a novel construction, secure against adaptive chosen message attacks, even against quantum attackers. A security proof in the random oracle model is presented together with results about the scheme implementation. The new proposed signature scheme has an interesting property that a pair composed of a message and a valid signature can encode any arbitrary data chosen during key generation. This encoded data is revealed computing the hash of the message and signature and can be used to create more user-friendly signatures and link the keys to its owner's biometric data. This signature is also notable for being the first signature scheme based on a chameleon hash function proven secure in this specific security model