Amostragem gaussiana eficiente para a construção de sistemas criptográficos pós-quânticos baseados em reticulados.

• Ano de defesa: 2023
• Autor(a) principal: Barbado Junior, Marcio
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: Amostragem gaussiana discreta; Aprendizado com erros em anel; Central limit theorem; Criptologia; Cryptology; Discrete Gaussian sampling; Fast Walsh-Hadamard transform; Ring learning with erros; Teorema central do limite; Transformada rápida de Walsh-Hadamard
• Link de acesso: https://www.teses.usp.br/teses/disponiveis/3/3141/tde-03012024-114312/

Com o avanço da computação quântica, a segurança computacional de esquemas criptográficos assimétricos clássicos amplamente utilizados, como os baseados em problemas de fatoração de inteiros e logaritmo discreto, encontra-se sob ameaça. Por essa razão, pesquisadores na área de criptografia têm buscado esquemas alternativos resistentes a ataques quânticos. Nesse cenário, abordagens criptográficas tais quais as baseadas em teoria de reticulados, que até então eram menos usadas por serem consideradas computacionalmente custosas, recuperam a atenção dos criptógrafos, e passam a figurar como opções viáveis. Este trabalho tem como objetivo contribuir para consolidar essa retomada na adoção da abordagem baseada em reticulados. Especificamente, tem-se como alvo a formulação do problema de aprendizado com erros em anel (ring learning with errors), aqui usada para a produção de erro, o que propicia a criação de chaves criptográficas supostamente mais seguras. As referidas chaves são formadas como polinômios de coeficientes produzidos através de amostragem, realizada em uma função de probabilidade associada a uma distribuição gaussiana. A construção de amostradores dessa natureza é parte da maioria dos projetos criptográficos baseados em reticulados, e frequentemente representa duas barreiras principais: um gargalo de eficiência, e um risco de vazamento de informação devido a ataques de canal colateral baseados em temporização. Procura-se reduzir a barreira de ineficiência através de técnicas para a aceleração da convergência do teorema central do limite durante as criações de distribuições normais, e também através do emprego da transformada rápida de WalshHadamard para a geração de valores aleatórios. Já o vazamento de informação por ataques de temporização tem seu risco atenuado pela implementação (em software) da primitiva como um gerador de números aleatórios com rotinas isócronas. Métricas estatísticas clássicas empregadas mostram os benefícios do esquema e sua adequação, quando comparado a uma amostragem gaussiana discreta baseada na tabela de distribuição acumulada, aqui considerado o método de referência, dada a sua adoção em diversos esquemas criptográficos baseados em reticulados. Testes com até 223 amostras são conduzidos, e os resultados são favoráveis ao amostrador aqui apresentado.