POKEx: Performance analysis of POKE-key exchange and SIDH-variants

Imagine que a internet é uma cidade gigante e movimentada onde todos enviam cartas secretas uns aos outros. Para manter essas cartas seguras contra ladrões, usamos "fechaduras" chamadas criptografia. Por décadas, as melhores fechaduras foram feitas usando problemas matemáticos que são fáceis de fazer em um sentido, mas incrivelmente difíceis de desfazer, como misturar cores de tinta. No entanto, cientistas estão preocupados que, no futuro, computadores superpoderosos (chamados computadores quânticos) possam desfazer essas fechaduras instantaneamente, deixando nossos segredos totalmente expostos. Para impedir isso, pesquisadores estão construindo novas fechaduras baseadas em um ramo estranho e belo da matemática chamado "isogenia". Pense nas isogenias como um tipo especial de ponte que conecta diferentes formas (curvas matemáticas). O segredo da fechadura é o caminho específico que você percorre através da ponte. Por muito tempo, o design de ponte mais popular foi chamado de SIDH. Ele era famoso porque as fechaduras eram minúsculas e rápidas, tornando-o um forte candidato para proteger nosso futuro mundo digital.

Mas então, em 2023, uma dupla de pesquisadores descobriu um truque astuto para quebrar a ponte SIDH. Eles descobriram que os designers da ponte deixaram acidentalmente um mapa do caminho visível para qualquer pessoa que olhasse, permitindo descobrir a rota secreta em segundos. Isso foi um grande golpe, pois significou que a fechadura mais promissora "à prova de quântica" estava, na verdade, quebrada. Desde então, cientistas têm tentado freneticamente construir novas pontes que escondam melhor o mapa. Alguns tentaram cobrir o mapa com um cobertor (mascaramento), enquanto outros tentaram construir a ponte com materiais diferentes. A grande questão permanecia: Podemos construir uma ponte que seja tanto inquebrável quanto rápida o suficiente para usar no mundo real?

Este artigo, intitulado "POKEx", entra nesse canteiro de obras caótico para testar um novo e brilhante design de ponte chamado POKÉ. Os autores, Hyeonhak Kim e Suhri Kim, decidiram transformar o método de criptografia POKÉ em um sistema completo de troca de chaves (que eles chamam de POKEx) e colocá-lo para correr contra os outros principais concorrentes que tentam consertar a ponte SIDH quebrada. Eles não apenas adivinharam; eles construíram versões funcionais desses sistemas e os cronometraram em um computador poderoso. Sua principal descoberta é que o POKEx é atualmente o mais rápido e eficiente de todas as pontes baseadas em isogenia. Em seus testes, ele foi cerca de 21 vezes mais rápido que a próxima melhor alternativa (terSIDH) e quase 65 vezes mais rápido que outro design popular (CSIDH). Embora ainda seja mais lento que alguns outros tipos de fechaduras à prova de quântica, sua velocidade e tamanho minúsculo o tornam um candidato muito promissor para o futuro, oferecendo uma maneira de manter nossos segredos digitais seguros sem desacelerar a internet.

A História da Ponte Quebrada e a Nova Solução

Para entender por que este artigo é importante, primeiro precisamos olhar para o problema da "ponte". No mundo da criptografia, uma "troca de chave" é como duas pessoas concordando em uma senha secreta sem nunca dizê-la em voz alta. Por muito tempo, o sistema SIDH foi o protagonista. Ele usava curvas elípticas supersingulares — pense nelas como formas complexas e onduladas em um universo matemático. A magia do SIDH era que ele usava "pontos de torção", que são como marcos específicos nessas curvas, para construir a ponte. O sistema era tão eficiente que possuía chaves pequenas (o equivalente digital a uma fechadura pequena e leve) e era muito rápido.

No entanto, a ponte SIDH tinha uma falha fatal. Para construir a ponte, o sistema precisava publicar algumas informações sobre os marcos (pontos de torção) que utilizava. Em 2023, Castryck e Decru descobriram uma maneira de usar esses marcos publicados, combinados com um truque matemático astuto chamado "Kani's glue-and-split" (colagem e divisão de Kani), para reconstruir o caminho secreto. Era como deixar um rastro de migalhas de pão que levava diretamente ao tesouro. Assim que esse ataque foi descoberto, o SIDH foi considerado quebrado e removido da lista de candidatos para o futuro da segurança da internet.

A Corrida para Consertar a Ponte

Após a queda do SIDH, a comunidade de criptografia não desistiu. Eles começaram a construir novas pontes para substituí-lo. Alguns tentaram esconder os marcos cobrindo-os com ruído aleatório (um método chamado M-SIDH). Outros tentaram mudar completamente a forma da ponte usando "orientação artificial" (terSIDH). Também havia o CSIDH, um tipo diferente de ponte que não foi afetado pelo mesmo ataque, mas que tinha seus próprios problemas de velocidade.

O problema era que essas novas pontes eram ou muito lentas ou muito grandes. Cobrir os marcos com ruído exigia números muito maiores para permanecer seguro, o que tornava as fechaduras pesadas e lentas de usar. Mudar a forma da ponte (terSIDH) ajudou, mas ainda apresentava variações de velocidade que poderiam ser perigosas. A comunidade precisava de uma solução que fosse ao mesmo tempo segura e rápida.

Entra o POKEx: O Demônio da Velocidade

É aqui que o novo herói do artigo, o POKEx, entra em cena. O POKEx é baseado em um esquema chamado POKÉ, que foi proposto recentemente por Basso e Maino. Os autores deste artigo pegaram o POKÉ e o transformaram em um sistema completo de troca de chaves, com todos os passos necessários para gerar chaves e trocar segredos com segurança.

O ingrediente secreto do POKEx é como ele lida com os "marcos". Em vez de usar apenas caminhos unidimensionais como o antigo SIDH, o POKEx usa uma "representação bidimensional". Imagine tentar atravessar um rio. O SIDH era como caminhar sobre uma única tábua. Se alguém visse onde você pisou, poderia descobrir seu caminho. O POKEx, no entanto, é como caminhar em uma grade de tábuas onde você pode se mover em duas direções ao mesmo tempo. Isso torna o caminho muito mais difícil de adivinhar. Além disso, o POKEx utiliza um tipo especial de campo matemático (um número primo da forma $2^a3^b5^c-1$) que permite cálculos muito rápidos, ao contrário das outras novas pontes que tiveram que usar números muito maiores e mais lentos.

O Grande Confronto: O Que Dizem os Números

Os autores não apenas falaram sobre o POKEx; eles o colocaram à prova. Eles construíram um software para rodar o POKEx ao lado dos outros principais concorrentes: M-SIDH, terSIDH e CSIDH. Eles configuraram todos para o mesmo nível de segurança (nível de segurança NIST 1, que é o padrão para proteger dados governamentais ultrassecretos) e cronometraram quanto tempo levava para trocar uma chave.

Os resultados foram impressionantes.

• M-SIDH foi o mais lento do grupo, levando quase 190 segundos para fazer o que o POKEx fez em uma fração de segundo. Os autores observaram que isso torna o M-SIDH impraticável para uso no mundo real.
• terSIDH foi muito mais rápido que o M-SIDH, mas ainda levou cerca de 6,5 segundos.
• CSIDH levou cerca de 20 segundos.
• POKEx, no entanto, terminou o trabalho em apenas 306,95 milissegundos (cerca de 0,3 segundos).

Para colocar em perspectiva, o POKEx foi 21,21 vezes mais rápido que o terSIDH e 64,97 vezes mais rápido que o CSIDH. Isso faz do POKEx o atual campeão da troca de chaves baseada em isogenia.

É Perfeito?

O artigo é cuidadoso ao não chamar isso de uma solução "perfeita". Embora o POKEx seja o mais rápido entre as pontes de isogenia, ele ainda é muito mais lento do que outros tipos de fechaduras à prova de quântica, como o ML-KEM (que levou apenas 0,10 milissegundo no teste). No entanto, os autores apontam um compromisso crucial. O ML-KEM é rápido, mas suas "fechaduras" (chaves públicas e textos cifrados) são enormes, ocupando muito espaço na internet. O POKEx, por outro lado, tem chaves muito pequenas (apenas 324 bytes para a chave pública), o que significa que usa menos largura de banda. Em um mundo onde a velocidade da internet e os limites de dados importam, esse tamanho pequeno é uma vantagem massiva.

A Conclusão

Este artigo mostra que, embora a antiga ponte SIDH esteja quebrada, o caminho para uma nova ponte segura está aberto. O POKEx é atualmente o candidato mais promissor na família das isogenias, ofereando uma combinação rara de alta velocidade e tamanho reduzido. Ele prova que podemos construir fechaduras resistentes ao quântico que não atrasam nossas vidas digitais. Embora ainda precise de mais trabalho para alcançar a velocidade de outros métodos à prova de quântica, sua eficiência sugere que ele pode se tornar uma ferramenta vital para manter nossa internet futura segura, especialmente em situações onde economizar espaço de dados é tão importante quanto economizar tempo.