💻 computer science

Fuzzy PSI from Symmetric Primitives with Exact Logarithmic Dependence on Distance Threshold

Este artigo apresenta novos protocolos de Interseção de Conjuntos Privados Difusos (FPSI) para distâncias $L_p$ gerais que alcançam dependência logarítmica ótima em relação ao limiar de distância $\delta$ utilizando apenas transferência oblíqua e primitivas de chave simétrica, eliminando assim a necessidade de criptografia homomórfica dispendiosa enquanto supera significativamente as soluções de estado da arte em tempo de execução e comunicação.

Autores originais: Cong Zhang, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Yu Chen, Anyu Wang, Xiaoyun Wang

Publicado 2026-06-16

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Cong Zhang, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Yu Chen, Anyu Wang, Xiaoyun Wang

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine duas pessoas, Alice e Bob, que querem descobrir se possuem itens "semelhantes" em suas respectivas coleções sem mostrar um ao outro suas listas inteiras.

O Problema: Em um jogo padrão, eles apenas combinariam itens que são exatamente iguais (por exemplo, ambos têm uma "Maçã Vermelha").
A Reviravolta (PSI Difuso/Fuzzy PSI): Neste novo jogo, eles querem combinar itens que sejam próximos o suficiente. Por exemplo, se Alice tem uma "Maçã Vermelha" e Bob tem uma "Maçã Vermelha Levemente Machucada", eles devem contar como uma combinação. A regra é: "Se a diferença entre nossos itens for menor que uma distância específica (vamos chamá-la de Limiar/Threshold), nós combinamos."

O desafio é fazer isso de forma segura. Alice não deve aprender a lista inteira de Bob, e Bob não deve aprender a lista inteira de Alice. Eles só querem saber quais itens são próximos o suficiente.

O Jeito Antigo: A Busca Lenta e Cara

Métodos anteriores para este jogo de "Correspondência Difusa" tinham dois grandes problemas:

A Armadilha "Linear": Se o limiar de "proximidade" fosse grande (digamos, 100 unidades), os computadores tinham que verificar 100 possibilidades diferentes para cada item. Era como procurar uma agulha em um palheiro verificando cada palha, uma por uma. Quanto maior o limiar, mais lento ficava.
O Problema da "Maquinaria Pesada": Para fazer isso funcionar de forma segura, os métodos antigos usavam ferramentas criptográficas muito pesadas e lentas (como a Criptografia Homomórfica Aditiva). Pense nisso como tentar enviar uma mensagem secreta usando um caminhão enorme e gastador de combustível quando uma bicicleta seria suficiente.

A Nova Descoberta: O Atalho do "Prefixo"

Este artigo introduz uma nova maneira de jogar o jogo que é rápida, leve e inteligente.

1. A Analogia do "Código Postal" (Prefixos)

Em vez de verificar cada número em um intervalo (como verificar se um número é 10, 11, 12... até 100), os autores usam um truque chamado Prefixos.

Imagine que você está procurando uma casa em uma cidade.

Jeito Antigo: Você bate em todas as portas do bairro para ver se o residente é seu amigo.
Novo Jeito: Você olha o Código Postal. Se seu amigo mora no "10001", você só precisa verificar casas com esse prefixo. Você não precisa verificar a cidade inteira.

Os autores perceberam que qualquer "intervalo" de números (o limfer/threshold) pode ser decomposto em apenas alguns "Códigos Postais" (prefixos).

A Magia: O tempo que leva para verificar esses prefixos não cresce com o tamanho do limiar; ele cresce logaritmicamente.
- Se o limiar dobra, o trabalho aumenta apenas um pouco.
- Se o limiar fica 100 vezes maior, o trabalho apenas dobra.
- Analogia: É como encontrar um livro em uma biblioteca. Verificar cada livro leva uma eternidade. Verificar a etiqueta da prateleira (prefixo) leva segundos, não importa quantos livros haja na prateleira.

2. Ferramentas "Leves" (Primitivas Simétricas)

Os autores substituíram os "caminhões" pesados (criptografia cara) por "bicicletas" (primitivas de chave simétrica e Transferência Oblívia).

Transferência Oblívia (OT): Imagine um garçom que pode lhe dar um de dois itens secretos do menu sem que você saiba qual escolheu, e sem que o garçom saiba qual você queria. Os autores usam isso para trocar informações de forma segura sem revelar a lista inteira.
O Resultado: O sistema deles é construído inteiramente a partir dessas ferramentas leves e rápidas.

Os Dois Cenários: Quartos Pequenos vs. Grandes Salões

O artigo oferece duas estratégias diferentes dependendo de quão "lotados" estão os dados (dimensionalidade):

Cenário A: Baixas Dimensões (A Suposição do "Apartamento")

O Cenário: Pense em uma sala pequena onde as pessoas estão paradas longe umas das outras (pelo menos 2x a distância do limiar).
A Estratégia: Eles usam Hashing Espacial. Imagine dividir a sala em uma grade de azulejos. Se duas pessoas estiverem próximas, elas devem estar no mesmo azulejo ou em azulejos vizinhos. O protocolo verifica apenas esses azulejos específicos.
A Inovação: Eles combinaram este sistema de grade com o novo atalho de "Prefixo" e uma ferramenta especial de "Verificação de Igualdade" (chamada ECSS). Isso permite que encontrem correspondências instantaneamente sem verificar cada par.

Cenário B: Altas Dimensões (A Suposição do "Armazém Separado")

O Cenário: Pense em um armazém massivo e multidimensional. Em altas dimensões, dividir o espaço em uma grade cria muitos azulejos vazios (a "maldição da dimensionalidade").
A Estratégia: Eles usam Geração de ID Distribuída. Em vez de uma grade, eles dão a cada item um "cartão de identidade" único baseado em sua localização.
A Inovação: Eles criaram uma nova maneira de gerar esses IDs de forma segura usando o truque do "Prefixo". Mesmo em um armazém gigante, eles podem gerar esses IDs de modo que, se dois itens estiverem próximos, seus IDs coincidirão, sem revelar as localizações reais dos itens.

A "Receita Secreta": Soma Condicional de Igualdade

A essência da invenção deles é uma nova ferramenta matemática chamada Soma Condicional de Igualdade (ECSS).

Como funciona: Imagine que Alice e Bob tenham uma lista de números. Eles querem somar os números apenas se uma condição específica for atendida (ex: "Somente some os números se os prefixos coincidirem").
A Magia: Eles podem fazer essa adição de forma segura sem que nenhuma das partes revele seus números. Se os prefixos não coincidirem, o resultado é apenas ruído aleatório. Se eles coincidirem, o resultado é a soma correta. Isso permite que eles verifiquem a proximidade dos itens sem nunca ver os valores reais.

Os Resultados: Um Aumento Massivo de Velocidade

Os autores construíram uma versão funcional de seu sistema e o testaram contra os melhores métodos existentes.

Velocidade: O sistema deles é até 43,7 vezes mais rápido que o melhor método anterior.
Uso de Dados: Ele utiliza até 31,3 vezes menos dados para serem enviados pela rede.
Escalabilidade: Enquanto outros sistemas falharam (ficaram sem memória) quando os conjuntos de dados ficaram muito grandes, o sistema deles continuou funcionando perfeitamente.

Resumo

Em suma, este artigo resolve o problema da "Correspondência Difusa" ao:

Substituir a criptografia lenta e pesada por ferramentas rápidas e leves.
Usar "Prefixos" (como Códigos Postais) para transformar uma busca linear lenta em uma busca logarítmica rápida.
Criar novas ferramentas de "Soma Secreta" que permitem que duas partes verifiquem a proximidade sem revelar seus segredos.

O resultado é um sistema que pode encontrar itens "semelhantes" em conjuntos de dados privados e massivos quase instantaneamente, tornando a correspondência de dados preservando a privacidade prática pela primeira vez em grande escala.

Resumo Técnico: FPSI Difuso a partir de Primitivas Simétricas com Dependência Logarítmica Exata em relação ao Limiar de Distância

Definição do Problema
A Interseção de Conjuntos Privada Difusa (Fuzzy Private Set Intersection - FPSI) permite que um remetente com um conjunto de vetores de $d$ dimensões $Q$ e um receptor com um conjunto $W$ identifiquem itens $q \in Q$ de modo que exista um $w \in W$ com $\text{dist}(q, w) \le \delta$ , sem revelar informações adicionais. Embora o PSI padrão tenha alcançado alta eficiência, os protocolos de FPSI existentes enfrentam gargalos teóricos e práticos significativos. Trabalhos anteriores tipicamente exibem escalonamento linear com o limiar de distância $\delta$ (ou seja, $O(\delta)$ ), ou alcançam dependência polilogarítmica apenas para distâncias $L_\infty$ . Protocolos que suportam distâncias de Minkowski gerais ( $L_p$ para $p \in [1, \infty]$ ) com dependência logarítmica em $\delta$ dependeram ou de Criptografia Homomórfica Aditiva (AHE) dispendiosa ou sofreram com falhas de segurança e termos de complexidade exponencial na dimensão $d$ . O objetivo é alcançar uma dependência logarítmica exata em $\delta$ para distâncias $L_p$ gerais usando apenas primitivas de chave simétrica eficientes.

Metodologia e Técnicas Principais
Os autores propõem novos protocolos de FPSI construídos inteiramente a partir de Transferência Oblíqua (OT) e primitivas de chave simétrica, evitando operações de chave pública como AHE. A construção baseia-se em dois pressupostos principais: o pressuposto apart (adequado para configurações de baixa dimensão) e o pressuposto separate (adequado para configurações de alta dimensão).

Representação de Prefixo e Teste de Intervalo:
A inovação central substitui a enumeração de todos os inteiros em um intervalo $[q_k - \delta, q_k + \delta]$ (que custa $O(\delta)$ ) por uma representação de prefixo usando $O(\log \delta)$ prefixos. Isso reduz o custo de teste de intervalo para $O(\log \delta)$ por dimensão.
Soma Condicional de Igualdade / Compartilhamento de Produto Interno Condicional de Igualdade (ECSS/ECIPS):
Para lidar com a interação necessária pelo emparelhamento de prefixos sem revelar a entrada do remetente ou incorrer em overhead exponencial, os autores introduzem duas novas primitivas criptográficas:
- Compartilhamento de Soma Condicional de Igualdade (ECSS): Usado para distância $L_\infty$ . Permite que as partes computem uma soma de valores condicional a um emparelhamento de igualdade entre vetores de entrada, fornecendo shares secretos do resultado.
- Compartilhamento de Produto Interno Condicional de Igualdade (ECIPS): Usado para distâncias $L_p$ gerais. Computa um produto interno condicional à igualdade, permitindo o cálculo de $|w_k - q_k|^p$ via expansão binomial sem revelar os termos específicos.
  Ambas as primitivas são implementadas eficientemente usando OT, PRFs Programáveis Oblíquas (OPPRF) e protocolos Permute+Share (PS).
Lidando com Múltiplos Elementos:
- Baixa Dimensão ( $L_\infty$ e $L_p$ ): Os protocolos utilizam hashing espacial (células de grade) combinados com hashing Cuckoo para reduzir o número de comparações par a par. Os autores introduzem otimizações usando OPRF compartilhado (sOPRF) para eliminar a necessidade de valores fictícios em bins vazios, ocultando assim as posições de hashing do remetente e removendo a necessidade de etapas de permutação global em certas configurações.
- Alta Dimensão ( $L_\infty$ e $L_p$ ): Para evitar o custo exponencial $O(2^d)$ do hashing espacial, os autores empregam um protocolo de Geração de ID Distribuído (dIDG). Este protocolo gera IDs únicos para elementos de tal forma que elementos próximos compartilham um ID. Os autores identificam falhas de segurança em construções dIDG anteriores (especificamente em [DZL25]) relacionadas ao vazamento de colisão e propõem um dIDG seguro baseado em chave simétrica usando sOPRF e ECSS.

Principais Contribuições

Novas Primitivas: A introdução de ECSS e ECIPS, que permitem o emparelhamento difuso eficiente com dependência logarítmica exata em $\delta$ usando apenas primitivas simétricas.
Complexidade Ótima: Os primeiros protocolos de FPSI para distâncias $L_p \in [1, \infty]$ gerais que alcançam complexidade estritamente logarítmica $O(d \log \delta)$ em relação ao limiar $\delta$ . Isso é teoricamente ótimo, pois distinguir valores em um intervalo de comprimento $O(\delta)$ requer $\Omega(\log \delta)$ bits de informação.
Segurança e Eficiência: Os protocolos eliminam a dependência de AHE, substituindo-a por operações de OT e chave simétrica. Os autores também identificam e corrigem vulnerabilidades de segurança em protocolos baseados em prefixo recentes (ex: [DZL25]) que sofriam de reuso de máscara e vazamento de colisão.
Construções Escaláveis: Construções separadas para cenários de baixa dimensão (usando hashing espacial) e alta dimensão (usando dIDG), ambas alcançando complexidade assintótica ótima.

Resultados Experimentais
Os autores implementaram seus protocolos e os compararam com trabalhos de ponta ([GQL+24], [DZL25], [BGMP25]).

Desempenho: Os novos protocolos superam significativamente a arte anterior. Em configurações de baixa dimensão, eles alcançam até 43,7× mais rapidez no tempo de execução e 31,3× menor overhead de comunicação.
Escalabilidade: Enquanto trabalhos anteriores como [GQL+24] e [DZL25] encontraram estouro de memória em tamanhos de conjunto de $2^{16}$ em configurações de alta dimensão, os protocolos propostos executaram com sucesso sob as mesmas configurações.
Dependência do Limiar: Os experimentos confirmam que os custos de tempo de execução e comunicação escalam logaritmicamente com $\delta$ , contrastando com o escalonamento linear observado em protocolos de dependência linear anteriores.

Significância
O artigo reivindica um avanço teórico no escalonamento de limiar ótimo para FPSI, demonstrando que a dependência logarítmica exata em $\delta$ é alcançável para distâncias $L_p$ gerais sem o uso de criptografia de chave pública dispendiosa. Praticamente, isso avança a viabilidade de aplicações escaláveis de FPSI em domínios que exigem emparelhamento difuso, como correspondência de sequências genômicas, recuperação de imagens similares e detecção de credenciais comprometidas, ao remover os gargalos de eficiência associados ao limiar de distância e à dimensionalidade.