Secure and efficient software implementation of QC-MDPC code-based cryptography
Resumo
A expectativa do surgimento de computadores quânticos impulsiona uma transição semprecedentes na área de criptografia de chave pública. Algoritmos convencionais, represen-tados principalmente por criptografia baseada em curvas elípticas e pelo RSA,são vulneráveis a ataques utilizando computadores quânticos e, portanto, precisarão sersubstituídos. Criptosistemas baseados em códigos corretores de erros são consideradosalguns 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 tamanhosde chave, enquanto mantêm as propriedades de segurança desejadas. Seu desempenho,no entanto, ainda precisa ser melhorado para atingir um nível competitivo.Este trabalho tem ênfase na otimização do desempenho dos criptosistemas baseadosem código QC-MDPC através de melhorias em suas implementações e algoritmos. Primei-ramente, é apresentada uma nova versão aprimorada do mecanismo de encapsulamento dechaves da QcBits, uma implementação em tempo constante do Criptosistema Nieder-reiter utilizando códigos QC-MDPC. Nesta versão, os parâmetros da implementaçãoforam atualizados para atender ao nível de segurança quântica de 128 bits, alguns dosprincipais algoritmos foram substituídos para evitar o uso de instruções mais lentas, ocódigo foi inteiramente vetorizado utilizando o conjunto de instruções AVX 512 e ou-tras pequenas melhorias foram introduzidas. Comparando com o atual estado-da-artepara códigos QC-MDPC, a implementação BIKE, a implementação apresentada nestetrabalho executa 1,9 vezes mais rápido ao decriptar mensagens.Em seguida, foca-se na otimização de desempenho dos sistemas criptográficos baseadosem códigos QC-MDPC por meio da inserção de uma taxa de falhas configurável em seusprocedimentos aritméticos. São apresentados algoritmos com execução em tempo cons-tante que aceitam uma taxa de falhas configurável para multiplicação e inversão sobrepolinô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), amultiplicaçã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 es-parsa ingênua em tempo constante. O algoritmo de inversão, baseado no algoritmo deWuet al., é 2 vezes mais rápido que o original e 12 vezes mais rápido que o algoritmode inversão de Itoh e Tsujii utilizando o mesmo polinômio de módulo (x32749−1). Aoinserir esses algoritmos na versão aprimorada da QcBits, atingiu-se uma aceleração de 1,9na 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 executaa decriptação uniforme 2,7 vezes mais rápida. Além disso, as técnicas aqui apresentadastambém podem ser aplicadas à BIKE, abrindo novas possibilidades de melhorias paracriptosistemas QC-MDPC.
