Interpretação do Algoritmo PQC - FALCON

Em 1994, Peter Shor concebeu um algoritmo capaz de resolver o Problema da Factorização de Inteiros e o Problema dos Logaritmos Discretos em tempo polinomial utilizando um computador quântico, o que constitui uma enorme ameaça para o mundo dos sistemas clássicos de chave pública, como o RSA e o ECC. Felizmente, nessa altura, os computadores quânticos ainda não tinham surgido. No entanto, com o desenvolvimento da tecnologia quântica, esta ameaça está cada vez mais próxima. Em 2016, o NIST lançou um convite à apresentação de propostas de normas PQC (criptografia pós-quântica) para resistir à ameaça da quântica. O FALCON é um algoritmo de assinatura apresentado ao NIST PQC. Em 2022, o NIST anunciou quatro candidatos PQC para padronização, e o FALCON é um deles. Conforme declarado pelo NIST, o FALCON será padronizado, pois pode haver casos de uso para os quais as assinaturas do Dilithium (outro algoritmo de assinatura PQC que foi padronizado pelo NIST) são muito grandes. De acordo com o NIST, a edição preliminar da norma FALCON será publicada no final de 2024 e a edição final estará disponível em 2025.

Wo que é o FALCON?

FALCON é o acrónimo de "fast Fourier lattice-based compact signatures over NTRU". Trata-se de um algoritmo de assinatura digital resistente ao quantum. É utilizado para detetar modificações não autorizadas nos dados e autenticar a identidade do signatário. As assinaturas geradas pelo FALCON podem servir como evidência para provar que o signatário alegado assinou efetivamente o documento. Esta propriedade é conhecida como "não-repúdio", o que significa que o signatário não pode mais tarde negar ter assinado o documento.

Como funciona o FALCON?

O FALCON é uma instanciação da estrutura teórica descrita por Gentry, Peikert e Vaikuntanathan para a construção de esquemas de assinatura baseados em treliças hash-and-sign. Esta estrutura requer dois ingredientes: uma classe de redes criptográficas e um amostrador de alçapão. O esquema de assinatura FALCON escolhe redes NTRU e amostragem rápida de Fourier. Em poucas palavras, o esquema de assinatura FALCON pode ser descrito da seguinte forma:

FALCON = estrutura GPV + redes NTRU + amostragem rápida de Fourier

Wpor que é que o FALCON faz bem?

Em comparação com outros algoritmos de assinatura PQC, o FALCON caracteriza-se pela sua compacidade, flexibilidade e rapidez de verificação.

Em primeiro lugar, o principal princípio de design do FALCON é a compactação, que minimiza a soma do tamanho da chave pública e do tamanho da assinatura. De facto, no nível I de segurança, o comprimento da chave pública do FALCON é de 897 bytes, que é menor que o do Dilithium em 415 bytes. E o comprimento da assinatura do FALCON é de 666 bytes, o que é menor que o do Dilithium em 1754 bytes. 

Além disso, o FALCON é flexível. Por um lado, ele pode ser transformado em um esquema IBE (Identity-Based Encryption), cujo desempenho é ordens de magnitude mais rápido do que IBEs baseados em emparelhamento. Por outro lado, o FALCON também pode ser transformado num esquema de assinatura em anel.

Por último, mas não menos importante, o desempenho do FALCON na verificação de assinaturas é bom, sendo mais rápido do que o Dilithium.

Parâmetros de FALCON

O FALCON especifica dois conjuntos de parâmetros que abordam os níveis de segurança I e V definidos pelo NIST, conforme a tabela a seguir:

Onde é que o FALCON ser utilizado?

O FALCON foi integrado em muitas bibliotecas de software de criptografia, como o OQS (abreviação de Open Quantum Safe), que é um projeto que visa apoiar a transição para a criptografia quântica-resistente, e foi integrado na biblioteca OpenSSL, amplamente utilizada. Com sua flexibilidade, o FALCON pode ser usado nos seguintes casos:

Sobre a WATCHDATA

Coincidentemente, no mesmo ano em que Peter Shor concebeu o algoritmo de Shor, 1994, foi fundada a Watchdata. A empresa começou a desenvolver soluções de segurança da informação baseadas em sistemas de criptografia de chave pública. Tirando partido da sua experiência em algoritmos criptográficos, segurança digital e sistemas operativos de chips seguros, as soluções de produtos da Watchdata fornecem autenticação de identidade e segurança de transacções para milhares de milhões de utilizadores em todo o mundo. Acompanhamos de perto o desenvolvimento de algoritmos criptográficos pós-quânticos, planeamos ativamente o futuro e monitorizamos de perto as tendências de investigação e desenvolvimento padrão. Isto garante que as nossas futuras concepções de produtos podem enfrentar os desafios de segurança da era da computação quântica, fornecendo aos clientes um suporte de ponta para algoritmos resistentes à quântica para construir um sistema robusto de proteção da segurança digital.