EVENTO
GRAFOS DE RAMANUJAN APLICADOS EM CRIPTOGRAFIA
Tipo de evento: Exame de Qualificação
Neste trabalho, estudamos as aplicações dos grafos de Ramanujan em criptografia, tanto de uma perspectiva clássica quanto pós-quântica. [Charles et al. 2009] propuseram o uso de grafos de isogenia para curvas elípticas supersingulares em criptografia. Estes grafos são exemplos de grafos de Ramanujan, isto é, grafos de expansão ótima. Para [Costache et al. 2018], estes grafos são importantes para a criptografia porque é difícil encontrar passeios neles, razão para o NIST (National Institute of Standards and Technology) considerá-los para padronização na competição de criptografia pós-quântica. Sob a perspectiva clássica, [Stănică 2007] afirmou que o grafo de Cayley associado à função bent é sempre um grafo de Ramanujan. Porém, o AES (Advanced Encryption Standard), uma cifra de bloco baseada na cifra de Rijndael e adotado como padrão de criptografia pelo governo dos EUA (ver [Daemen and Rijmen 2002]), usa uma S-Box que não é bent. O AES usa substituição (S-Box) para alcançar a confusão proposta por [Shannon 1949]. Uma S-Box com boas propriedades criptográficas pode garantir que a cifra resista contra uma variedade de métodos de criptoanálise [Cui et al. 2011]. Segundo [Carlet 2011], uma S-Box criptograficamente forte deve ter pelo menos valores ótimos nas seguintes propriedades: não linearidade (NL > 100), uniformidade diferencial (2 6) e grau algébrico (AD 4). Neste estudo, propomos uma relação entre o grafo de Ramanujan e a matriz da transformação afim que constitui a transformação SubBytes do AES. Esta matriz é binária, denotada por (0,1)-matriz, não singular e está associada a S-Box. Para isso, consideramos esta matriz de ordem 8, para o caso de uma chave de 256 bits, e a identificamos como uma matriz de adjacência de um multigrafo de Ramanujan. Muitos trabalhos, como, por exemplo, [Deva Sinha and Arya 2012], realizaram buscas em um total da ordem de 1018 (0,1)-matrizes não singulares para a construção de S-Boxes, sem a garantia de valores ótimos para as propriedades citadas anteriormente. No entanto, a relação proposta reduziu a busca para uma quantidade inferior a 1011 (0,1)-matrizes não singulares para construir S-Boxes com pelo menos NL > 100, como primeiro resultado*. Sendo assim, os grafos de Ramanujan demonstram um grande potencial para futuros estudos tanto para funções Booleanas (caso da S-Box) quanto para grafos de isogenia (ver [Belleza e Borges 2018]).RESUMO: Neste trabalho, estudamos as aplicações dos grafos de Ramanujan em criptografia, tanto de uma perspectiva clássica quanto pós-quântica. [Charles et al. 2009] propuseram o uso de grafos de isogenia para curvas elípticas supersingulares em criptografia. Estes grafos são exemplos de grafos de Ramanujan, isto é, grafos de expansão ótima. Para [Costache et al. 2018], estes grafos são importantes para a criptografia porque é difícil encontrar passeios neles, razão para o NIST (National Institute of Standards and Technology) considerá-los para padronização na competição de criptografia pós-quântica. Sob a perspectiva clássica, [Stănică 2007] afirmou que o grafo de Cayley associado à função bent é sempre um grafo de Ramanujan. Porém, o AES (Advanced Encryption Standard), uma cifra de bloco baseada na cifra de Rijndael e adotado como padrão de criptografia pelo governo dos EUA (ver [Daemen and Rijmen 2002]), usa uma S-Box que não é bent. O AES usa substituição (S-Box) para alcançar a confusão proposta por [Shannon 1949]. Uma S-Box com boas propriedades criptográficas pode garantir que a cifra resista contra uma variedade de métodos de criptoanálise [Cui et al. 2011]. Segundo [Carlet 2011], uma S-Box criptograficamente forte deve ter pelo menos valores ótimos nas seguintes propriedades: não linearidade (NL > 100), uniformidade diferencial (2 6) e grau algébrico (AD 4). Neste estudo, propomos uma relação entre o grafo de Ramanujan e a matriz da transformação afim que constitui a transformação SubBytes do AES. Esta matriz é binária, denotada por (0,1)-matriz, não singular e está associada a S-Box. Para isso, consideramos esta matriz de ordem 8, para o caso de uma chave de 256 bits, e a identificamos como uma matriz de adjacência de um multigrafo de Ramanujan. Muitos trabalhos, como, por exemplo, [Deva Sinha and Arya 2012], realizaram buscas em um total da ordem de 1018 (0,1)-matrizes não singulares para a construção de S-Boxes, sem a garantia de valores ótimos para as propriedades citadas anteriormente. No entanto, a relação proposta reduziu a busca para uma quantidade inferior a 1011 (0,1)-matrizes não singulares para construir S-Boxes com pelo menos NL > 100, como primeiro resultado*. Sendo assim, os grafos de Ramanujan demonstram um grande potencial para futuros estudos tanto para funções Booleanas (caso da S-Box) quanto para grafos de isogenia (ver [Belleza e Borges 2018]).* Submetido como artigo completo para o SBSeg 2019.BIBLIOGRAFIA: Carlet, C. (2011). On known and new differentially uniform functions. In Parampalli, U. and Hawkes, P., editors, Information Security and Privacy , pages 115, Berlin, Heidelberg. Springer Berlin HeidelbergCharles, D. X., Lauter, K. E., and Goren, E. Z. (2009). Cryptographic hash functions from expander graphs. Journal of Cryptology, 22(1):93113.Costache, A., Feigon, B., Lauter, K. E., Massierer, M., and Puskás, A. (2018). Ramanujan graphs in cryptography. IACR Cryptology ePrint Archive , 2018:593.Cui, J., Huang, L., Zhong, H., Chang, C., and Yang, W. (2011). An improved AES S-box and its performance analysis. International Journal of Innovative Computing, Information and Control , 7:22912302.Daemen, J. and Rijmen, V. (2002). The Design of Rijndael. Springer-Verlag, Berlin, Heidelberg.Deva Sinha, S. and Arya, C. (2012). Algebraic construction and cryptographic properties of Rijndael substitution box. Defence Science Journal, 62:3237.Shannon, C. E. (1949). Communication theory of secrecy systems. The Bell System Technical Journal, 28(4):656715.Stănică, P. (2007). Graph eigenvalues and walsh spectrum of Boolean functions. Integers: Electronic Journal of Combinatorial Number Theory, 7(2).Belleza, M. P.; Borges, F. Avaliação de Segurança em Curvas Elípticas Usando o Corpo dos Números p-ádicos. In: IV WORKSHOP SOBRE REGULAÇÃO, AVALIAÇÃO DA CONFORMIDADE, TESTES E PADRÕES DE SEGURANÇA, 2018, Rio de Janeiro. Anais eletrônicos... Campinas, GALOÁ, 2019. Disponível em:
Data Início: 29/08/2019 Hora: 10:00 Data Fim: 29/08/2019 Hora: 13:00
Local: LNCC - Laboratório Nacional de Computação Ciêntifica - Auditorio A
Aluno: Marcio Prudêncio Belleza - Laboratório Nacional de Computação Científica - LNCC
Orientador: Fábio Borges de Oliveira - Laboratório Nacional de Computação Científica - LNCC
Participante Banca Examinadora: Bruno Richard Schulze - Laboratório Nacional de Computação Científica - LNCC Luis Antonio Kowada - Universidade Federal Fluminense - UFF Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
Suplente Banca Examinadora: Jack Baczynski - Laboratório Nacional de Computação Científica - LNCC
