A software implementation of FALCON on the ARM architecture [recurso eletrônico] = Uma implementação em software do algoritmo FALCON na plataforma ARM
Caio Teixeira
DISSERTAÇÃO
Inglês
T/UNICAMP T235s
[Uma implementação em software do algoritmo FALCON na plataforma ARM]
Campinas, SP : [s.n.], 2023.
1 recurso online (62 p.) : il., digital, arquivo PDF.
Orientadores: Julio César López Hernández, Ricardo Dahab
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Resumo: O estudo e a criação de esquemas de assinatura digital são uma subárea da Criptografia que tem um papel importante nas comunicações digitais: eles possibilitam tanto a autenticação quanto a verificação da integridade dos dados enviados. No entanto, os esquemas criptográficos mais difundidos...
Ver mais
Resumo: O estudo e a criação de esquemas de assinatura digital são uma subárea da Criptografia que tem um papel importante nas comunicações digitais: eles possibilitam tanto a autenticação quanto a verificação da integridade dos dados enviados. No entanto, os esquemas criptográficos mais difundidos hoje em dia estão sob ataque, devido a um algoritmo quântico capaz de resolver seus problemas matemáticos subjacentes em tempo polinomial e, com isso, minar sua segurança. Isso inclui todos os padrões clássicos de assinaturas digitais: RSA, DSA e ECDSA. Portanto, esquemas baseados em problemas matemáticos para os quais não se conhece, nem se espera encontrar, algoritmos quânticos capazes de resolvê-los em tempo polinomial tem sido propostos, criando uma subárea chamada "criptografia pós-quântica". Um destes esquemas é o esquema de assinaturas digitais pós-quântico baseado em reticulados FALCON, recentemente padronizado pelo NIST. FALCON é projetado para minimizar o custo de comunicação do sistema; isto é, os tamanhos das chaves públicas e das assinaturas, que são enviadas entre as partes. Mesmo assim, esquemas pós-quânticos são, em geral, expressivamente mais lentos que suas contrapartes clássicas, e FALCON não é uma exceção. Sem uma implementação cuidadosa, o custo de trocar um esquema clássico por um pós-quântico pode ser inviável para algumas aplicações práticas. Tendo isto em vista, nesta dissertação, apresentamos uma implementação otimizada para o FALCON, tendo como alvo a arquitetura ARMv8-A. Esta arquitetura é muito difundida entre dispositivos mobile e IoT, e sua fatia de mercado entre computadores pessoais e servidores vem crescendo. Apesar de sua relevância, poucas implementações do FALCON voltadas para ARMv8-A estão presentes na literatura, enquanto arquiteturas como Intel ou ARMv8-M, o perfil voltado para microcontroladores da ARMv8, tem recebido muito mais atenção. Começamos nosso trabalho descrevendo os algoritmos e técnicas usado pelo FALCON em detalhe, destacando os desafios de implementação e oportunidades de otimização que as seguem. Então, usamos as várias ferramentas presentes na plataforma, como instruções "Single Input, Multiple Data" (SIMD) e instruções criptográficas especializadas, e descrevemos diversas técnicas que aumentam a velocidade do esquema na arquitetura ARMv8-A. Por fim, medimos o desempenho da nossa implementação em três plataformas diferentes, focando em seus melhores núcleos disponíveis: Cortex-A57 para placas de desenvolvimento NVIDIA Jetson Nano; Cortex-X2 para dispositivos mobile Samsung Galaxy S22; e Apple M1, o System-on-Chip presente nos modelos M1 da linha de laptops MacBook da Apple. Também comparamos nossos resultados com a implementação de referência disponibilizada pelos autores do FALCON, alcançando velocidades até 79% maiores para geração de assinaturas, e até 61% maiores para verificação das mesmas
Ver menos
Abstract: The study and design of digital signature schemes is a subfield of cryptography that plays an important role in digital communications: they provide means for both authentication and integrity verification of exchanged data. However, the most widespread cryptographic schemes nowadays are...
Ver mais
Abstract: The study and design of digital signature schemes is a subfield of cryptography that plays an important role in digital communications: they provide means for both authentication and integrity verification of exchanged data. However, the most widespread cryptographic schemes nowadays are under attack, due to quantum algorithms capable of solving their underlying mathematical problems in polynomial time, therefore undermining their security. This includes all classical digital signature standards: RSA, DSA and ECDSA. Thus, schemes based on mathematical problems for which no quantum algorithm is known or expected to be able to solve efficiently have been proposed, creating a subfield called "post-quantum cryptography". One such post-quantum scheme is the lattice-based digital signature scheme FALCON, recently standardized by NIST. FALCON is designed to minimize the communication cost of the system; that is, the size of both public keys and signatures, which are exchanged between parties. Even so, post-quantum schemes are, in general, noticeably slower to compute than their classical counterparts, and FALCON is no exception. Without careful implementation, the cost of switching from a classical scheme to a post-quantum one may not be viable for some practical applications. Therefore, in this thesis, we present an optimized implementation of FALCON targeting the ARMv8-A architecture. This architecture is widespread among mobile and IoT devices, and is rising in market share among personal computers and servers. Despite its relevance, few implementations of FALCON targeting ARMv8-A are present in the literature, while architectures such as Intel and ARMv8-M, the microcontroller-centric profile of ARMv8, have received much more attention. We begin our work describing the algorithms and techniques used by FALCON in detail, highlighting the implementation challenges and optimization opportunities that arise. Then, we leverage many tools present in the platform, such as "Single Input, Multiple Data" (SIMD) instructions and specialized cryptographic instructions, and describe several techniques to speed up the scheme in the ARMv8-A architecture. Finally, we benchmark our results across three different platforms, focusing on their best available core: Cortex-A57 for NVIDIA Jetson Nano development boards; Cortex-X2 for Samsung Galaxy S22 mobile devices; and Apple M1, the System-on-Chip featured on M1 models of Apple's MacBook line of laptops. We also compare our results with the published reference implementation by the authors of FALCON, achieving up to 79% higher speeds for signature generation, and up to 61% higher for their verification
Ver menos
Requisitos do sistema: Software para leitura de arquivo em PDF
A software implementation of FALCON on the ARM architecture [recurso eletrônico] = Uma implementação em software do algoritmo FALCON na plataforma ARM
Caio Teixeira
A software implementation of FALCON on the ARM architecture [recurso eletrônico] = Uma implementação em software do algoritmo FALCON na plataforma ARM
Caio Teixeira