Defesa de Mestrado de Antonio Carlos Guimarães Junior

Título do Trabalho
Secure and efficient implementation of QC-MDPC code-based cryptography
Candidato(a)
Antonio Carlos Guimarães Junior
Nível
Mestrado
Data
Add to Calender 2019-03-19 00:00:00 2019-03-19 00:00:00 Defesa de Mestrado de Antonio Carlos Guimarães Junior Secure and efficient implementation of QC-MDPC code-based cryptography Sala 85 do IC 2 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
14:00
Local
Sala 85 do IC 2
Orientador(a)
Diego de Freitas Aranha
Banca Examinadora

* Titulares

Unidade/Instituição

Edson Borin

IC/UNICAMP

Marcos Antonio Simplicio Junior

POLI/USP

Julio Cesar Lopez Hernandez

IC/UNICAMP

 

* Suplentes

Unidade/Instituição

Ricardo Dahab

IC/UNICAMP

Rafael Misoczki

Intel Labs

Resumo

A expectativa do surgimento de computadores quânticos impulsiona uma transição sem precedentes na área de criptografia de chave pública. Algoritmos convencionais, representados principalmente por criptografia baseada em curvas elípticas e pelo esquema de encriptação RSA, são vulneráveis a ataques utilizando computadores quânticos e, portanto, precisarão ser substituídos. Criptosistemas baseados em códigos corretores de erros são considerados alguns dos candidatos mais promissores para substituí-los em esquemas de encriptação. Entre as famílias de códigos, os códigos QC-MDPC alcançam os menores tamanhos de chave, enquanto mantêm as propriedades de segurança desejadas. Seu desempenho, no entanto, ainda precisa ser melhorado para atingir um nível de desempenho competitivo.

Este trabalho foca na otimização do desempenho dos criptosistemas baseados em código QC-MDPC através de melhorias em suas implementações e algoritmos. Primeiramente, é apresentada uma nova versão aprimorada do mecanismo de encapsulamento de chaves da QcBits, uma implementação em tempo constante do Criptosistema Niederreiter utilizando códigos QC-MDPC. Nesta versão, os parâmetros da implementação foram atualizados para atender ao nível de segurança quântica de 128 bits, alguns dos principais algoritmos foram substituídos para evitar o uso de instruções mais lentas, o código foi inteiramente vetorizado utilizando o conjunto de instruções AVX 512 e outras pequenas melhorias foram introduzidas. Comparando com o atual estado-da-arte para códigos QC-MDPC, a implementação BIKE, a implementação apresentada neste trabalho executa 1.9 vezes mais rápido ao decriptar mensagens.

Em seguida, foca-se na otimização de desempenho dos sistemas criptográficos baseados em códigos QC-MDPC por meio da inserção de uma taxa de falhas configurável em seus procedimentos aritméticos. São apresentados algoritmos com execução em tempo constante que aceitam uma taxa de falhas configurável para multiplicação e inversão sobre polinômios binários, as duas sub-rotinas mais caras utilizadas nas implementações QC-MDPC. Usando uma taxa de falhas negligível comparada ao nível de segurança ($2^{-128}$), a multiplicação é 2 vezes mais rápida que a multiplicação utilizada pela biblioteca NTL em polinômios esparsos e 1.6 vezes mais rápida que uma multiplicação polinomial esparsa ingênua em tempo constante. O algoritmo de inversão, baseado no algoritmo de Wu et al., é 2 vezes mais rápido que o original e 12 vezes mais rápido que o algoritmo de inversão de Itoh e Tsujii utilizando o mesmo polinômio de módulo ($x^{32749} - 1$). Ao inserir esses algoritmos na versão aprimorada da QcBits, atingiu-se uma aceleração de 1,9 na geração de chaves e de até 1,4 na decriptação.

Comparando com a BIKE, a versão final da QcBits apresentada neste trabalho executa a decriptação uniforme 2,7 vezes mais rápido. Além disso, as técnicas aqui apresentadas também podem ser aplicadas à BIKE, abrindo novas possibilidades de melhorias para criptosistemas QC-MDPC.