30 mar 2022
14:00 Defesa de Doutorado Integralmente a distancia
Tema
Contribuições Teóricas e Práticas para Criptografia Baseada no Problema Ring-LWE: Mergulhos Torcidos e Transformada Discreta de Galois
Aluno
Jheyne Nayara Ortiz
Orientador / Docente
Orientador: Ricardo Dahab/ Coorientador: Diego de Freitas Aranha
Breve resumo
Diversos trabalhos têm caracterizado instâncias fracas do problema LWE sobre anéis (Ring-LWE) explorando vulnerabilidades provenientes de estruturas algébricas. Apesar dessas instâncias fracas não serem englobadas pelos teoremas de pior caso, permitir a instanciação de outros anéis aumenta o escopo de aplicações possíveis e favorece a diversificação de hipóteses de segurança. A primeira parte desta tese é dedicada a estender o problema Ring-LWE na Criptografia Baseada em Reticulados para incluir reticulados algébricos construídos através de mergulhos torcidos. Primeiramente, uma nova classe de problemas, intitulada Twisted Ring-LWE, é definida substituindo o mergulho canônico por uma versão extendida. A segurança do problema Twisted Ring-LWE é demonstrada através de uma redução computacional do Ring-LWE para o Twisted Ring-LWE nas variantes de busca e decisão. Além disso, demonstra-se que o fator de torção não interfere nos fatores de aproximação nas redução de pior caso para caso médio. Assim, o Twisted Ring-LWE mantém a segurança consolidada do Ring-LWE e aumenta o escopo de reticulados algébricos que podem ser considerados para aplicações de criptografia. Depois disso, essa tese foca na construção algébrica do reticulado Zn através de mergulhos torcidos. Assim, apresenta-se como amostrar eficientemente de distribuições Gaussianas esféricas e como conectar instâncias do Twisted Ring-LWE construídas sobre corpos de números distintos. Por fim, um criptossistema de chave pública é modificado para incorporar mergulhos torcidos, culminando em uma discussão de como suas principais sub-rotinas podem ser executadas.
A segunda parte desta tese compreende uma análise do uso da Transformada Discreta de Galois (DGT) para multiplicação polinomial em anéis ciclotômicos com condutor potência de dois. A DGT é comparada com técnicas usadas por candidatos na segunda rodada do projeto de padronização do NIST intitulado Post-Quantum Cryptography na arquitetura x64. Conclui-se que a DGT não apresenta melhora no desempenho se comparada às formulações da Transformada Numérica (NTT). Além disso, o algoritmo four-step de Bailey, originalmente formulado sobre a Transformada Rápida de Fourier, é modificado para acelerar a DGT para um esquema de encriptação homomórfica em GPUs. A nova formulação recursiva da DGT resulta em uma multiplicação homomórfica 3,6 vezes mais rápida do que o estado da arte. Um experimento posterior indicou que a DGT recursiva induz uma melhora de, aproximadamente, 15% na multiplicação homomórfica se comparada com uma abordagem equivalente da NTT.
Banca examinadora
Titulares:
| Ricardo Dahab | IC/UNICAMP |
| Julio Cesar López Hernández | IC/UNICAMP |
| Sueli Irene Rodrigues Costa | IMECC/UNICAMP |
| Daniel Nelson Panario Rodríguez | Carleton University |
| Rafael Misoczki |
Suplentes:
| Flávio Keidi Miyazawa | IC/UNICAMP |
| Marco Aurélio Amaral Henriques | FEEC/UNICAMP |
| Routo Terada | IME/USP |