Provas de Segurança e Reduções em Esquemas de Reticulados

Uma prova de segurança de um esquema criptográfico é um argumento matemático formal que mostra que quebrar o esquema implica resolver um problema difícil subjacente. A prova não garante segurança absoluta; ela mostra que qualquer adversário eficiente contra o esquema pode ser convertido em um algoritmo eficiente para resolver o problema difícil. Se o problema difícil for intratável, o esquema será seguro.

A prova seminal de Regev, de 2005, mostra que um algoritmo de tempo polinomial que resolve o LWE decisório pode ser usado para resolver o GapSVP (Problema do Vetor Mais Curto com Intervalo) no pior caso em reticulados de n dimensões. A redução é quântica: ela usa um procedimento de amostragem quântica para converter um algoritmo que resolve LWE em um algoritmo que resolve problemas de reticulados. Isso significa que o LWE é pelo menos tão difícil quanto os problemas de reticulados no pior caso sob computação quântica.

A redução de Regev não é precisa: os fatores polinomiais da redução fazem com que o nível de segurança garantido pela prova seja um pouco mais fraco do que sugerem os melhores ataques conhecidos. Para a seleção prática de parâmetros, os criptógrafos usam a segurança concreta fornecida pelos melhores ataques conhecidos (por meio do estimador de reticulados), em vez do limite teórico da redução, pois a redução é conservadora.

Um esquema de criptografia baseado em LWE é provado IND-CPA (indistinguibilidade sob ataque de texto simples escolhido) por meio de um argumento híbrido. A prova mostra que um distinguidor IND-CPA implica um distinguidor de LWE. No primeiro híbrido, o texto cifrado real é substituído por uma sequência aleatória uniforme; a indistinguibilidade decorre da hipótese do LWE. Isso fornece uma prova de segurança clara para a criptografia básica baseada em reticulados.

A segurança IND-CPA não é suficiente para os mecanismos de encapsulamento de chaves usados em TLS: eles precisam de segurança IND-CCA2 (segurança contra ataque de texto cifrado escolhido). A transformação de Fujisaki-Okamoto (FO) converte qualquer esquema IND-CPA em um KEM IND-CCA2 no Modelo do Oráculo Aleatório (ROM). O ML-KEM aplica uma variante da transformação FO à criptografia subjacente baseada em LWE modular, fornecendo a segurança CCA2 necessária para a implantação no mundo real.

O Modelo do Oráculo Aleatório (ROM) modela as funções de resumo como funções verdadeiramente aleatórias. Muitas provas de segurança, incluindo as da transformação FO, exigem o ROM. Na prática, funções de resumo como SHA-3 não são oráculos aleatórios verdadeiros, portanto as provas no ROM não garantem segurança no modelo padrão. No entanto, as provas no ROM são amplamente aceitas na comunidade criptográfica como evidências fortes de segurança.

Uma prova no modelo padrão não faz nenhuma idealização sobre as funções de resumo e é estritamente mais forte do que uma prova no ROM. A maioria dos esquemas práticos baseados em reticulados usa provas no ROM porque as provas CCA2 no modelo padrão para KEMs baseados em reticulados são muito mais complexas e produzem parâmetros concretos piores. O NIST aceitou as provas baseadas no ROM para o ML-KEM, considerando-as suficientes para os níveis de segurança pretendidos.

A prova de segurança do ML-KEM ocorre em duas etapas. Primeiro, mostra-se que a criptografia subjacente baseada em LWE modular é segura IND-CPA sob a hipótese M-LWE. Segundo, a transformação de Fujisaki-Okamoto (especificamente, as transformações T e U usadas no Kyber) eleva essa segurança para IND-CCA2 no ROM quântico (QROM), que trata de adversários que consultam o oráculo aleatório em superposição.

O estimador de reticulados de Albrecht, Player e Scott é a ferramenta padrão para calcular a segurança concreta de esquemas baseados em LWE. Ele modela o custo dos melhores ataques conhecidos a reticulados (BKZ com peneiramento ou enumeração) e produz a segurança estimada em bits para determinados parâmetros (n, q, sigma). A ferramenta é atualizada regularmente à medida que novos algoritmos e modelos de custo de hardware são publicados.

O algoritmo Block Korkine-Zolotarev (BKZ) é o melhor algoritmo prático de redução de reticulados. O BKZ com tamanho de bloco beta encontra vetores curtos com complexidade de aproximadamente 2^{0.292*beta} operações de portas, usando os melhores algoritmos de peneiramento. Para o ML-KEM-768, a segurança clássica estimada é de aproximadamente 180 bits e a segurança quântica, de aproximadamente 164 bits, muito acima da meta de 192 bits.

As provas de segurança assintóticas mostram que um esquema é seguro para parâmetros suficientemente grandes, mas não especificam o que significa "suficientemente grande" na prática. A análise de segurança concreta preenche essa lacuna estimando o custo real do melhor ataque para os parâmetros escolhidos. A padronização pós-quântica depende fortemente da análise de segurança concreta, com parâmetros escolhidos para resistir a ataques em hardware quântico previsto ao longo de um horizonte de 30 anos.

Qual transformação é usada para elevar a criptografia baseada em reticulados de IND-CPA para segurança IND-CCA2 no ML-KEM?

As provas de segurança de esquemas baseados em reticulados reduzem a segurança do esquema à dificuldade do LWE ou do SVP. A redução de Regev garante que o LWE é pelo menos tão difícil quanto os problemas de reticulados no pior caso. A transformação de Fujisaki-Okamoto eleva IND-CPA para IND-CCA2 no ROM. A segurança concreta é avaliada com o estimador de reticulados usando modelos de complexidade do BKZ. As lacunas de precisão das reduções fazem com que os parâmetros práticos dependam das estimativas de custo dos ataques, e não apenas dos limites das reduções.