Resumo Técnico: Como o Conhecimento da Distribuição de Consultas Quebra Consultas de Intervalo Multidimensionais Criptografadas

Declaração do Problema

O artigo aborda a vulnerabilidade de consultas de intervalo multidimensionais criptografadas em esquemas de Criptografia Pesquisável (SE). Embora a SE permita buscas eficientes sobre dados criptografados, ela inevitavelmente vaza informações através de padrões de acesso (quais registros são recuperados) e padrões de consulta. Ataques anteriores de abuso de vazamento em bancos de dados multidimensionais enfrentaram limitações significativas:

1. Limitações de Saída: Ataques de última geração (SOTA) (por exemplo, Even Less [40], Remin [34]) tipicamente produzem um embedding de grafo representando apenas a topologia dos dados (relações de vizinhança relativas) em vez de coordenadas de texto plano concretas. Para obter coordenadas, esses ataques requerem transformações post-hoc (rotação, escala, translação) que são impossíveis para um atacante real executar sem conhecer a verdade fundamental (ground truth).
2. Modelos de Ameaça Irrealistas: Algumas variantes (por exemplo, Remin+) alcançam a reconstrução de coordenadas, mas dependem da suposição irrealista de que um atacante pode injetar registros de texto plano escolhidos adversarialmente no banco de dados para servir como pontos de ancoragem.
3. Falta de Garantias: Ataques multidimensionais anteriores carecem de garantias teóricas rigorosas quanto ao número de consultas necessárias, parametrização ótima ou qualidade no pior caso da reconstrução.

Os autores postulam que o conhecimento da distribuição de consultas (a distribuição estatística das consultas emitidas pelos usuários), combinado com o vazamento de padrões de acesso, é suficiente para quebrar esses esquemas com garantias prováveis, sem necessidade de injeção de dados ou transformações post-hoc.

Metodologia: LAMa

Os autores introduzem o LAMa (Abuso de Vazamento via Correspondência), um framework de três componentes que reconstrói coordenadas de texto plano em dimensões arbitrárias revisitando e formalizando o conceito de correspondência de frequência.

Conceito Central

O ataque baseia-se na observação de que, se um atacante conhece a distribuição de consultas ($QD$), ele pode pré-calcular a probabilidade teórica de que qualquer valor específico de texto plano (ou conjunto de valores) seja recuperado por uma consulta aleatória. Ao observar a frequência empírica com que registros criptografados são recuperados do servidor, o atacante pode corresponder essas frequências às probabilidades pré-calculadas para inferir os valores de texto plano subjacentes.

Componentes do Framework

1. Seletor: Determina quais subconjuntos de registros criptografados analisar. O artigo propõe uma estratégia universal, $T_{2k}$, que seleciona todas as interseções de até $2k$ registros (onde $k$ é o número de dimensões). Os autores provam que esse tamanho específico de subconjunto é necessário e suficiente para restringir o espaço de reconstrução ao seu limite teórico de informação.
2. Tradutor: Converte as observações de correspondência de frequência em uma fórmula de Programação por Restrições (CP). Ele identifica todas as atribuições candidatas de texto plano que satisfazem as frequências observadas (dentro de uma aproximação $\epsilon$) e codifica a exclusividade mútua e a consistência simultânea dessas atribuições em uma fórmula lógica.
3. Resolvedor: Resolve a fórmula CP para encontrar atribuições satisfatórias de valores aos registros criptografados. O resolvedor pode enumerar todas as soluções válidas, garantindo que o banco de dados verdadeiro esteja entre elas no limite.

Garantias Teóricas

O artigo fornece as primeiras garantias rigorosas para correspondência de frequência multidimensional:

• Optimalidade: O seletor $T_{2k}$ garante que o conjunto de reconstruções possíveis seja exatamente o Espaço de Reconstrução ($RS_{QD}(DB)$), definido como o conjunto de todos os bancos de dados indistinguíveis do banco de dados verdadeiro sob a distribuição de consultas dada e o perfil de vazamento.
• Complexidade de Consulta: Usando a teoria da dimensão VC, os autores derivam limites sobre o número de consultas observadas necessárias para aproximar as frequências de recuperação dentro de um erro $\epsilon$ com confiança $1-\delta$.
• Qualidade de Saída: O artigo propõe duas estratégias para selecionar uma única saída do espaço de reconstrução: o Diâmetro (pessimista, limite do pior caso) e o Centróide (otimista, localização média). Ele fornece limites formais sobre o erro de reconstrução para essas estratégias.

Análise da Distribuição de Consultas

Os autores investigam quais distribuições de consultas maximizam a incerteza de reconstrução. Eles provam que uma distribuição "padrão ouro" que tornaria a reconstrução impossível (tornando todos os bancos de dados indistinguíveis) não pode existir para distribuições de consultas expressivas. No entanto, eles constroem uma distribuição específica (via Algoritmo 2) que equaliza as probabilidades de recuperação para todos os pares de valores com a mesma distância $L_1$. Sob essa distribuição, o atacante pode recuperar apenas distâncias entre pares, não coordenadas absolutas, expandindo efetivamente o espaço de reconstrução para seu máximo teórico para aquela configuração.

Contribuições Principais

1. Reconstrução no Nível de Coordenadas sem Injeção: O LAMa é o primeiro ataque a reconstruir coordenadas de texto plano concretas em dimensões arbitrárias sem exigir injeção de dados ou transformações geométricas post-hoc.
2. Garantias Rigorosas: O trabalho estabelece as primeiras garantias formais para correspondência de frequência multidimensional, cobrindo complexidade de consulta, parametrização ótima ($T_{2k}$) e qualidade de saída no pior caso.
3. Caracterização dos Limites de Reconstrução: O artigo define o espaço de reconstrução para ataques baseados em distribuição de consultas e constrói uma distribuição de consultas específica que maximiza a incerteza mantendo-se expressiva.
4. Desempenho Empírico Superior: Experimentos demonstram que o LAMa supera consistentemente os ataques SOTA (Even Less, Remin, Remin+) em termos de precisão de reconstrução (Erro Quadrático Médio) e tamanho do espaço de soluções.

Resultados Experimentais

Os autores avaliaram o LAMa em conjuntos de dados do mundo real (Spitz, Califórnia, Xangai, Amsterdã, Manhattan, Paris) e grades sintéticas sob várias distribuições de consultas (Uniforme, Gaussiana, Beta).

• Caso Ideal: Quando as frequências são exatas, o LAMa alcança MSE = 0 (reconstrução perfeita) em todos os conjuntos de dados. Em contraste, os ataques SOTA produzem milhares de soluções com MSE significativamente maior, frequentemente falhando em recuperar a topologia ou coordenadas corretas sem transformação manual.
• Caso Realista: Com observação parcial de consultas (10-30% das consultas), o erro de reconstrução do LAMa diminui monotonicamente à medida que mais consultas são observadas. Os ataques SOTA não mostram melhoria consistente com o aumento do volume de consultas e mantêm alta variância.
• Qualidade de Saída: As estratégias de centróide e diâmetro do LAMa produzem limites de erro significativamente menores do que os métodos SOTA, mesmo quando os métodos SOTA têm a vantagem da injeção de texto plano (Remin+).
• Altas Dimensões: O LAMa reconstrói com sucesso dados em dimensões de 2 a 6 com baixo erro, enquanto as bases de código SOTA eram limitadas em sua capacidade de lidar com dimensões mais altas.

Significado e Alegações

O artigo afirma que a correspondência de frequência, anteriormente considerada uma técnica folclórica limitada a uma dimensão, é uma base principial e poderosa para a criptanálise de vazamento multidimensional quando combinada com o conhecimento da distribuição de consultas.

Os autores enfatizam que seu trabalho:

• Quebra a Barreira "Apenas Topologia": Diferentemente de ataques anteriores de alta dimensão que recuperam apenas a estrutura relativa, o LAMa recupera coordenadas absolutas.
• Opera sob Modelos de Ameaça Mais Fracos: Não exige a capacidade irrealista de injetar dados no banco de dados da vítima.
• Fornece Limites de Segurança Prováveis: Ao definir o espaço de reconstrução e provar a optimalidade do seletor $T_{2k}$, o artigo estabelece os limites teóricos do que é possível recuperar, mostrando que, embora a reconstrução perfeita seja frequentemente alcançável, distribuições de consultas específicas podem limitar o atacante a recuperar apenas distâncias relativas.

O trabalho conclui que o conhecimento da distribuição de consultas é uma vulnerabilidade crítica para consultas de intervalo multidimensionais criptografadas, tornando as técnicas atuais de supressão de vazamento insuficientes contra ataques de correspondência de frequência que são tanto conceitualmente simples quanto rigorosamente garantidos.