Modification to Fully Homomorphic Modified Rivest Scheme

Este documento descreve o Esquema Rivest Modificado Completamente Homomórfico (FHMRS), identifica uma vulnerabilidade de segurança nele e propõe uma modificação (mFHMRS) para mitigar tal problema.

O essencial

Imagine que você tem um cofre super seguro onde pode fazer contas (somar e multiplicar) com segredos, sem nunca precisar abri-lo para ver o que tem dentro. Isso é o que chamamos de Criptografia Homomórfica.

O documento que você enviou descreve uma evolução desse cofre. Vamos explicar como funciona, qual era o problema e como eles o consertaram, usando analogias do dia a dia.

1. O Cenário Original: O "Cofre Rivest" (FHMRS)

Imagine que você quer enviar uma mensagem secreta (digamos, um número) para um amigo.

• O Processo: Você coloca o número em um cofre (criptografa). Para isso, você usa uma chave secreta (números primos) e adiciona um pouco de "ruído" ou "barulho" (um número aleatório) para esconder o valor real.
• A Mágica: O seu amigo recebe o cofre fechado. Ele pode somar ou multiplicar o conteúdo de vários cofres sem abri-los.
• O Resultado: Quando ele finalmente abre o cofre (descriptografa), o resultado da conta feita lá dentro é o correto, como se ele tivesse feito a conta com os números originais.

O Problema:
Os autores descobriram que esse cofre original tinha uma falha de segurança. Era como se, ao fazer muitas multiplicações, o "ruído" que você adicionou para esconder o segredo ficasse tão grande e previsível que um espião poderia deduzir a chave secreta.

A Analogia do Espião:
Imagine que você esconde um bilhete dentro de uma caixa de sapatos cheia de areia (o ruído).

• No sistema original, se você tivesse várias caixas e soubesse o que havia dentro de uma delas (o texto claro), o espião poderia pegar a areia de fora e, usando matemática simples (o Máximo Divisor Comum), descobrir exatamente qual era o tamanho da caixa de areia original.
• Uma vez que ele descobre o tamanho da caixa de areia, ele descobre a chave para abrir todas as outras caixas. O sistema "quebrava" se o espião tivesse apenas um par de "caixa fechada + bilhete aberto".

2. A Solução: O "Cofre Rivest Modificado" (mFHMRS)

Para consertar isso, os autores criaram uma versão melhorada (mFHMRS). Eles mudaram a forma como o cofre é construído.

A Nova Estratégia: O Quebra-Cabeça de Múltiplas Caixas

Em vez de usar apenas duas fechaduras (dois números primos), o novo sistema usa muitas fechaduras (vários números primos) e divide a informação em várias partes.

1. Mais Camadas de Segurança: Imagine que, em vez de colocar o segredo em uma única caixa de sapatos, você coloca pedaços dele em 5, 10 ou mais caixas diferentes. Cada caixa tem uma fechadura diferente.
2. O Ruído Inteligente: Eles aumentaram o tamanho do "ruído" (a areia) e garantiram que ele seja grande o suficiente para que, mesmo que o espião saiba o que está dentro de uma caixa, ele não consiga deduzir o tamanho da areia das outras caixas.
3. A Regra de Ouro: O segredo é que o tamanho da "areia" (o número aleatório) deve ser maior que o tamanho das fechaduras individuais, mas menor que o tamanho total do cofre. Isso cria um equilíbrio matemático onde o espião fica preso.

Como funciona na prática (Simplificado):

• Criptografia: Você pega seu segredo, adiciona um pouco de "areia" e divide em vários pedaços. Cada pedaço é colocado em uma caixa diferente com uma fechadura diferente.
• Cálculo: O amigo pode somar ou multiplicar os conteúdos dessas várias caixas ao mesmo tempo.
• Descriptografia: Para ler o resultado, ele junta todas as caixas (usando uma técnica matemática antiga chamada Teorema Chinês do Resto, que é como montar um quebra-cabeça) e remove a "areia" no final.

3. Por que o Espião não consegue mais quebrar?

O documento analisa vários tipos de ataques que um hacker poderia tentar:

• Ataque de Força Bruta (Chutar todas as chaves): Com o novo sistema, o número de combinações possíveis de chaves é tão gigantesco (como tentar adivinhar um átomo específico em todo o universo) que levaria bilhões de anos para um computador tentar todas.
• Ataque de Lattice (Rede Matemática): Hackers usam redes complexas de matemática para tentar encontrar o caminho mais curto até o segredo. O novo sistema foi desenhado para que o "caminho mais curto" ainda seja muito longo e confuso, tornando essa técnica inútil.
• Ataque de Texto Conhecido (O problema original): Como explicado antes, o espião não consegue mais deduzir a chave mesmo sabendo o conteúdo de algumas caixas, porque a matemática do novo sistema "esconde" a relação entre o ruído e a chave de forma muito mais eficiente.

Resumo Final

Pense no FHMRS original como um cofre que, se você soubesse o que tinha dentro de um compartimento, poderia adivinhar a chave mestra.

O mFHMRS (Modificado) é como transformar esse cofre em um labirinto gigante com centenas de portas. Mesmo que você saiba o que tem em uma sala, as paredes são tão altas e os caminhos tão complexos que você nunca consegue encontrar a saída (a chave secreta).

A lição principal: A segurança não vem apenas de esconder o segredo, mas de garantir que, mesmo que parte da informação vaze, a matemática por trás seja tão complexa que seja impossível reconstruir o resto. Os autores provaram que seu novo sistema é matematicamente robusto contra os melhores truques de hackers atuais.

Resumo técnico

Resumo Técnico: Modificação ao Esquema Rivest Modificado de Homomorfismo Total (mFHMRS)

1. Problema Identificado

O documento aborda uma vulnerabilidade crítica de segurança no Esquema Rivest Modificado de Homomorfismo Total (FHMRS) original, proposto anteriormente pelos mesmos autores. O problema central é a vulnerabilidade a um Ataque de Texto Plano Conhecido (Known-Plaintext Attack - KPA) quando o esquema suporta homomorfismo multiplicativo.

• Mecanismo do Ataque: No FHMRS original, o texto cifrado é gerado como $c = (m + g \cdot u) \pmod p$ e $(m + g \cdot u) \pmod q$. Devido às restrições de tamanho dos parâmetros para garantir a correção da decodificação, a redução modular por $p$ e $q$ muitas vezes não altera o valor $(m + g \cdot u)$.
• Consequência: Se um atacante possui pares de (texto plano, texto cifrado), ele pode calcular $c - m = g \cdot u$. Ao obter dois ou mais pares, o atacante pode calcular o Máximo Divisor Comum (GCD) de $(c_1 - m_1)$ e $(c_2 - m_2)$, revelando diretamente o parâmetro secreto $u$. Uma vez que $u$ é conhecido, a segurança do esquema é totalmente comprometida.

2. Metodologia Proposta (mFHMRS)

Os autores propõem uma modificação ao esquema original, denominada mFHMRS, para mitigar o ataque de texto plano conhecido e fortalecer a resistência contra ataques de base de retículo (lattice-based) e equações lineares.

Principais Alterações no Esquema:

• Geração de Chaves (KeyGen):
  • Em vez de dois primos ($p, q$), o esquema agora utiliza $N+S$ primos ($p_1, p_2, ..., p_{N+S}$) de tamanho igual, onde $N$ é o número de multiplicações consecutivas suportadas e $S$ é um parâmetro de segurança adicional.
  • O módulo $n$ é definido como o produto de todos os primos: $n = p_1 \times p_2 \times ... \times p_{N+S}$.
  • O parâmetro secreto $u$ é mantido, mas com restrições de tamanho mais rigorosas ($u > p_i$).
• Criptografia (Encrypt):
  • O texto cifrado torna-se uma tupla de $N+S$ componentes: $c_i = (c_{i1}, c_{i2}, ..., c_{i(N+S)})$.
  • Cada componente é calculado como $c_{ij} = (m_i + g_i \cdot u) \pmod{p_j}$, onde $g_i$ é um número aleatório gerado por um CSPRNG.
  • A criptografia baseia-se no Teorema Chinês do Resto (CRT) para dividir a mensagem em "shares" (partes).
• Propriedades Homomórficas:
  • O esquema mantém a capacidade de realizar adição, subtração, multiplicação e operações com constantes diretamente sobre os textos cifrados.
  • As operações são realizadas componente a componente na tupla de texto cifrado.
• Decifração (Decrypt):
  • Utiliza o Teorema Chinês do Resto para reconstruir o valor $(m + g \cdot u)$ a partir das partes $c_{ij}$.
  • Aplica uma redução modular por $u$ para recuperar a mensagem original $m$.

Restrições de Parâmetros de Segurança:
Para garantir a segurança e a correção, os autores definem desigualdades rigorosas para os tamanhos em bits dos parâmetros ($l_p, l_u, l_g$):

• $l_p \geq \lambda$ (para evitar adivinhação de primos).
• $l_p \leq (l_u + l_g + 1)$ (para mitigar ataques de retículo).
• $l_u > l_p$ (para garantir que a diferença entre os valores de $k$ seja imprevisível).
• $l_g \geq \lambda/4$ (para resistir a ataques baseados em resolução de equações lineares).

3. Contribuições Chave

1. Identificação Formal da Vulnerabilidade: O papel demonstra matematicamente como o FHMRS original falha sob um ataque de texto plano conhecido devido à falta de redução modular efetiva nos primos originais.
2. Proposta de mFHMRS: Introdução de um esquema baseado em múltiplos primos ($N+S$) que dilui a informação e impede a extração direta de $u$ via GCD.
3. Análise de Segurança Rigorosa: O documento fornece uma análise detalhada de resistência contra quatro vetores de ataque principais:
   • Ataque de Força Bruta: Demonstra que o espaço de chaves é suficientemente grande (ex: complexidade de $2^{490}$ para um cenário específico).
   • Ataque Baseado em Retículo (LLL): Mostra que a construção de retículos para encontrar vetores curtos (como $g_0$ ou $p_1$) falha devido ao tamanho dos erros e à relação entre os parâmetros $l_u, l_g$ e $l_p$.
   • Ataque por Equações Lineares: Demonstra que, com $l_g$ adequado e $u > p_i$, a resolução de sistemas lineares para encontrar $u$ e $p_i$ torna-se computacionalmente inviável.
   • Ataque de Texto Plano Conhecido (KPA): Prova que a modificação impede o cálculo do GCD para revelar $u$, pois o texto cifrado não revela mais o valor exato de $(m + g \cdot u)$.

4. Resultados e Desempenho

• Correção: O esquema mFHMRS garante a correção da decifração desde que o tamanho do produto após $N$ multiplicações e $A$ adições permaneça menor que $n$ (o produto dos primos) e que o resultado final seja menor que $u$.
• Custo Computacional:
  • O tamanho do texto cifrado aumenta linearmente com o número de componentes ($N+S$).
  • Exemplo 1: Para 1 multiplicação ($N=1$) e $S=2$, com primos de 128 bits, o tamanho máximo do texto cifrado é de 384 bits.
  • Exemplo 2: Para 14 multiplicações ($N=14$) e $S=5$, com primos de 180 bits, o tamanho máximo do texto cifrado é de 3420 bits.
• Complexidade de Ataque: A análise mostra que ataques de força bruta e baseados em retículo exigem complexidades exponenciais que superam os limites de segurança padrão (ex: 128 bits de segurança) quando os parâmetros são configurados conforme as diretrizes do papel.

5. Significância

Este trabalho é significativo no campo da criptografia de Homomorfismo Total (FHE) por oferecer uma solução prática para um esquema simétrico baseado em primos que foi anteriormente considerado inseguro.

• Viabilidade de Esquemas Simétricos: Demonstra que é possível corrigir falhas em esquemas baseados em CRT (Teorema Chinês do Resto) sem recorrer a estruturas de chave pública mais complexas e pesadas (como LWE ou RLWE), mantendo a eficiência relativa de esquemas simétricos.
• Segurança Comprovada: A análise fornece limites teóricos claros para a seleção de parâmetros, permitindo que implementações futuras evitem as armadilhas que levaram à quebra do esquema original.
• Aplicabilidade: O esquema é adequado para cenários onde a computação em dados criptografados é necessária, oferecendo um equilíbrio entre segurança e sobrecarga de tamanho de dados, desde que os parâmetros de segurança sejam estritamente seguidos.

Em resumo, o papel transforma o FHMRS de um esquema vulnerável em uma proposta robusta (mFHMRS) através da expansão do número de primos secretos e do ajuste cuidadoso das relações de tamanho entre os parâmetros, garantindo resistência contra os principais vetores de ataque conhecidos na literatura atual.