Plausible Deniability in Fully Homomorphic Computation

Resumo Técnico: Negação Plausível em Computação Totalmente Homomórfica (PD-FHC)

1. Definição do Problema

A terceirização de computação para provedores de nuvem não confiáveis expõe os usuários a duas ameaças distintas que as tecnologias existentes não conseguem abordar simultaneamente:

1. Privacidade Computacional: Proteger os dados de provedores honestos-mas-curiosos (abordado por Criptografia Totalmente Homomórfica (FHE) e Ambientes de Execução Confiáveis (TEEs)).
2. Negação Plausível: A capacidade de negar credivelmente a existência ou a intenção de uma computação quando coagido por um adversário poderoso.

As soluções atuais possuem lacunas críticas:

• FHE: Embora oculte os valores dos dados, a transmissão de criptogramas é conspícua. Um adversário coercitivo pode exigir as chaves de decriptação, e o mero uso de FHE confirma que uma computação privada está ocorrendo.
• TEEs: Produzem logs de atestação que servem como prova indeniável de execução. Além disso, são vulneráveis a vazamentos de canais laterais (side-channel).
• Computação Multipartidária Segura (MPC): Embora seja robusta contra a revelação da parte de um único participante, ela não permite que os participantes neguem que a computação ocorreu ou que substituam uma computação diferente.
• Criptografia/Armazenamento Deniável: Abordam dados estáticos (mensagens ou arquivos), mas não se estendem à intenção computacional dinâmica.

O artigo identifica uma lacuna onde um usuário precisa terceirizar uma computação Booleana enquanto mantém a capacidade de negar o que foi computado e, para um observador externo, que uma computação ocorreu de fato.

2. Metodologia

Os autores propõem o PD-FHC, um framework que incorpora computações Booleanas em um meio de cobertura (especificamente imagens RGB) usando portas Fredkin e esteganografia de Bit Menos Significativo (LSB).

Mecanismo Central:

• Fiação Compartilhada, Semântica Variável: O framework utiliza uma fiação única e fixa de portas Fredkin universais. Uma porta Fredkin é uma porta reversível de 3 entradas/3 saídas onde um bit de controle determina se os dois bits de dados são trocados.
  • Se o bit de controle for 0, a porta atua como uma passagem direta (pass-through).
  • Se o bit de controle for 1, a porta troca os bits de dados.
  • Ao definir os bits de controle via dados incorporados, a mesma fiação física pode implementar diferentes funções lógicas (ex: AND, OR, NOT, ou circuitos complexos) em diferentes localizações.
• Incorporação em Múltiplas Localizações: O usuário (Alice) incorpora um circuito "real" e $L-1$ circuitos "isca" nos LSBs de uma imagem.
  • Circuito Real: Incorporado em um conjunto de posições secretas $\Lambda_{j^*}$.
  • Circuitos Isca: Incorporados em outros conjuntos de posições disjuntas $\Lambda_j$.
  • Bits de Preenchimento (Fill Bits): Todas as posições de LSB restantes são preenchidas com bits extraídos de uma distribuição específica $\pi$.
• Processamento Uniforme: O provedor de nuvem (Carol) recebe a imagem e a especificação de fiação ($C_{obf}$). Ela aplica a porta Fredkin uniformemente a cada posição de pixel em paralelo. Ela não sabe quais posições contêm dados reais, dados isca ou ruído de preenchimento.
• Resposta à Coerção: Se coagida, Alice revela os conjuntos de posições, entradas e saídas para um circuito isca. Como a fiação é idêntica e o circuito isca produz resultados verificáveis consistentes com a saída da nuvem, o adversário não consegue distinguir a isca da computação real.

Fundamentos Teóricos:

• Meio de Computação Deniável (DCM): Um framework abstrato que define um meio com posições de bits endereçáveis, capacidades de leitura/escrita e uma família de portas que se aplica uniformemente.
• Condição de Marginais Correspondentes (Matched-Marginal Condition): Para segurança de informação teórica, os bits nas posições reais, posições isca e posições de preenchimento devem ser extraídos da mesma lei de probabilidade por posição $\pi$. Sob esta condição, o plano de LSB é "permutável" (exchangeable), o que significa que a distribuição estatística da imagem é invariante à permutação das posições.

3. Principais Contribuições

1. Framework Abstrato: Definição de um Meio de Computação Deniável (DCM) e de um Esquema de Computação Deniável (DCS) que separam o modelo de segurança de meios de cobertura específicos (ex: imagens, áudio, pacotes).
2. Formalização do Modelo de Ameaça: Um modelo de duas fases distinguindo entre:
   • Nuvem Honesta-mas-Curiosa (HBC): Preocupada com a privacidade computacional (ocultar os dados).
   • Adversário Coercitivo: Preocupado com a negação plausível (ocultar a existência e a intenção da computação).
   • Os autores definem novos jogos de coerção de múltiplas rodadas medindo a "distinção de existência" (o adversário pode provar que circuitos ocultos existem?) e a "descoberta de circuito" (o adversário pode identificar o circuito real entre as iscas reveladas?).
3. Instanciação Baseada em Imagem: Uma implementação concreta usando imagens RGB e portas Fredkin.
   • Prova de Privacidade de Posição: Sob a condição de marginais correspondentes, o artigo prova que o provedor de nuvem obtém vantagem zero (informacionalmente) em localizar as posições do circuito real em comparação com uma tentativa de adivinhação aleatória, independentemente da distribuição $\pi$.
   • Ocultação Parcial de Circuito: A fiação é visível, mas a semântica da porta é oculta. O artigo prova que, sem o conhecimento dos bits de controle, a fiação não revela nada sobre qual função está sendo computada.
4. Implementação e Benchmarking: Uma implementação em Python testada em tamanhos de circuito (5–302 portas) e dimensões de imagem ($128^2$ a $512^2$).

4. Resultados

• Garantias de Segurança:
  • Privacidade Computacional: A nuvem não aprende nada sobre os valores secretos dos dados ou a função específica computada, desde que a família de portas preserve a distribuição estatística das posições não secretas (uma propriedade que as portas Fredkin satisfazem via permutação de bits).
  • Ocultação de Existência: Sob a condição de marginais correspondentes, a vantagem de existência é exatamente zero. Um adversário não pode distinguir entre uma imagem contendo apenas bits de preenchimento e uma que contém circuitos ocultos.
  • Descoberta de Circuito: A vantagem de identificar o circuito real entre as iscas não reveladas é limitada pela plausibilidade semântica das iscas e pelo vazamento de canal lateral. O vetor de posição e de fiação contribui com zero para a vantagem do adversário.
• Desempenho: A implementação mostra desempenho competitivo com o TFHE (uma biblioteca líder de FHE) para circuitos Booleanos, enquanto fornece a denegabilidade que o FHE não pode oferecer.
• Imperceptibilidade Visual: A modificação dos LSBs resulta em um deslocamento máximo de $\pm 1$ por canal, resultando em PSNR > 50 dB, tornando as mudanças visualmente imperceptíveis.

5. Significância e Alegações

O artigo afirma ser o primeiro framework a satisfazer simultaneamente a privacidade computacional, a ocultação de existência (contra observadores externos) e a ocultação parcial de circuito (contra o provedor de nuvem).

Alegações Modestas e Limitações:

• Escopo da Plausibilidade do Cobertor: Os autores afirmam explicitamente que o PD-FHC não funciona para qualquer imagem (ex: fotos de férias). O serviço de cobertura deve legitimamente esperar entradas de LSB de alta entropia (ex: dithering, injeção de ruído ou processamento de domínio criptográfico). Se o serviço declarado espera imagens naturais, o plano de LSB uniforme necessário para a segurança torna-se detectável.
• Restrições de Entrada Real: A garantia de vantagem zero de informação teórica ocorre exatamente apenas se os bits de entrada reais do usuário também seguirem a mesma distribuição $\pi$ que os bits isca e de preenchimento. Para entradas reais estruturadas, a vantagem é limitada pela distância estatística ($\Delta$) entre a distribuição de entrada real e $\pi$.
• Plausibilidade Semântica: A segurança contra a descoberta de circuitos depende da $\epsilon$-plausibilidade dos circuitos isca. O artigo admite que construir iscas semanticamente críveis (ex: uma verificação de brilho versus um hash criptográfico) é uma tarefa manual e específica de domínio, e ainda não automatizada.
• Ataques Ativos: O framework assume uma nuvem honesta-mas-curiosa e observadores externos passivos. Não protege contra atacantes ativos que possam modificar a imagem ou recusar-se a computar.
• Sem Ofuscação Criptográfica: O artigo evita explicitamente alegar ofuscação de circuito criptográfica (que está sujeita a resultados de impossibilidade). A "ofuscação" é puramente esteganográfica, baseando-se nos bits de controle ocultos para variar a semântica das portas.

Em resumo, o PD-FHC oferece uma abordagem inovadora para a terceirização de computação onde o usuário pode negar credivelmente a intenção específica da computação ao apresentar uma função alternativa verificável que é indistinguível da real sob coerção, desde que as condições estatísticas do meio de cobertura sejam atendidas.