💻 computer science

Efficient Fuzzy PSI under One-Sided Assumptions

Este artigo introduz os primeiros protocolos de interseção de conjuntos privados difusos concretamente eficientes para distâncias $L_p$ gerais sob suposições unilaterais, aproveitando primitivas de chave simétrica leves e técnicas de trie de prefixo para alcançar complexidade $O(\log \delta)$ e superar significativamente os trabalhos anteriores de estado da arte tanto em velocidade de computação quanto em overhead de comunicação.

Autores originais: Xinpeng Yang, Meng Hao, Yanxue Jia, Chenkai Weng, Yonggang Wen, Tianwei Zhang

Publicado 2026-08-19

📖 7 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Xinpeng Yang, Meng Hao, Yanxue Jia, Chenkai Weng, Yonggang Wen, Tianwei Zhang

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

Na era digital, duas organizações frequentemente precisam encontrar um meio-termo sem revelar todos os seus segredos uma à outra. Imagine um hospital detendo uma lista de pacientes com uma condição específica e um instituto de pesquisa detendo uma lista de voluntários. Eles querem saber quais voluntários também são pacientes, mas nenhum dos lados quer entregar sua lista completa, pois isso exporia dados privados de todos os outros no registro. Protocolos de computador padrão podem resolver esse problema de correspondência exatamente de forma eficiente, mas eles falham quando os dados são ligeiramente desorganizados. No mundo real, nomes são escritos incorretamente, localizações estão ligeiramente erradas e escaneamentos biométricos variam de um dia para o outro. Se o registro do hospital diz "John Smith" e o registro do voluntário diz "Jon Smyth", um sistema padrão não vê uma correspondência, embora sejam a mesma pessoa. É aqui que entra a correspondência "difusa" (fuzzy matching), um método projetado para encontrar essas conexões aproximadas. No entanto, fazer isso de forma segura é incrivelmente difícil. Se o sistema tentar comparar cada possível variação de cada nome contra cada outra variação, a quantidade de dados trocados torna-se tão massiva que o processo trava, ou exige uma maquinaria matemática tão pesada que se torna impraticável para o uso cotidiano.

Uma equipe de pesquisadores desenvolveu agora uma nova maneira de realizar essa correspondência difusa que é ao mesmo tempo rápida e leve. O trabalho deles foca em um cenário onde apenas uma das duas partes precisa seguir regras estritas sobre como seus dados são organizados, enquanto a outra parte pode ter dados em qualquer ordem caótica. Tentativas anteriores de resolver este problema sob tais condições relaxadas dependiam de ferramentas criptográficas pesadas e lentas ou exigiam que ambas as partes tivessem dados perfeitamente organizados, o que raramente acontece na realidade. O novo método, criado por Xinpeng Yang e colegas de instituições em Singapura e nos Estados Unidos, alcança o mesmo objetivo usando apenas blocos de construção simples e rápidos. Eles conseguiram reduzir o tempo e os dados necessários para essas comparações por margens massivas, tornando a correspondência aproximada segura viável pela primeira vez em muitos cenários do mundo real.

O cerne da conquista reside em como os pesquisadores lidam com a "distância" entre os pontos de dados. Neste contexto, a distância é uma medida de quão diferentes são duas peças de informação, como quantos caracteres diferem entre dois nomes ou quão longe estão duas coordenadas de GPS. O objetivo é encontrar pares onde essa distância seja menor do que um limite específico. Os pesquisadores perceberam que os métodos anteriores tentavam verificar cada variação possível de um ponto de dado, o que criava um espaço de busca que crescia explosivamente à medida que a diferença permitida aumentava. Para corrigir isso, eles introduziram uma técnica que atua como um filtro inteligente. Em vez de verificar todas as possibilidades, o sistema organiza os dados em uma estrutura do tipo árvore que permite pular enormes blocos de informações irrelevantes instantaneamente. Essa mudança reduziu o esforço computacional de um nível que crescia exponencialmente com o tamanho da busca para um nível que cresce apenas logaritmicamente. Em termos práticos, isso significa que mesmo que a diferença permitida entre os pontos de dados seja dobrada ou triplicada, o tempo necessário para executar a verificação mal aumenta.

A equipe testou seus novos protocolos contra os melhores métodos existentes atualmente. Os resultados foram dramáticos. Quando comparado a um protocolo recente de 2024, o novo sistema rodou até 239 vezes mais rápido e usou até 20 vezes menos largura de banda de comunicação. Contra um método de 2025, a aceleração atingiu 518 vezes, com uma redução de 63 vezes na transferência de dados. Em uma comparação específica contra outra construção de 2025, o novo sistema foi quase 5.000 vezes mais rápido e exigiu 282 vezes menos comunicação. Esses números não foram apenas teóricos; os pesquisadores implementaram o sistema completo e realizaram experimentos extensos em uma ampla gama de tamanhos e configurações de dados. Eles confirmaram que sua abordagem funciona independentemente de quem possui os dados organizados, o remetente ou o destinatário, e que suporta vários tipos de medições de distância, não apenas as simples.

Uma inovação fundamental em seu trabalho foi a capacidade de lidar com suposições de "um lado só". Em muitos sistemas seguros anteriores, ambas as partes tinham que concordar com regras estritas, como garantir que seus pontos de dados estivessem espaçados o suficiente para evitar confusão. Isso é frequentemente impossível na vida real, onde os dados chegam em aglomerados ou padrões aleatórios. O novo método exige apenas que um lado tenha um conjunto de dados um tanto organizado, enquanto o outro lado pode ter dados completamente arbitrários e desordenados. Essa flexibilidade torna a tecnologia aplicável a cenários como rastreamento de contatos ou serviços baseados em localização, onde uma entidade pode ter um banco de dados estruturado de locais conhecidos enquanto a outra tem um fluxo de entradas de usuários não estruturadas. Ao confiar exclusivamente em técnicas de chave simétrica leves — essencialmente ferramentas de criptografia padrão que são rápidas e eficientes — os pesquisadores evitaram as operações matemáticas pesadas e lentas que anteriormente atrasavam esforços semelhantes.

Os pesquisadores também exploraram como tornar o sistema ainda mais eficiente quando os dados são esparsos, ou seja, quando os pontos estão espalhados em vez de agrupados. Nesses casos, eles descobriram que trocar os papéis das duas partes no processo de correspondência poderia equilibrar ainda mais a carga de trabalho e melhorar o desempenho. Essa adaptabilidade sugere que o sistema pode ser ajustado para diferentes tipos de aplicações sem a necessidade de um redesenho completo. O trabalho demonstra que é possível construir sistemas seguros e que preservam a privacidade que não são apenas teoricamente sólidos, mas também praticamente rápidos o suficiente para implantação no mundo real.

As implicações deste trabalho estendem-se além da velocidade. Ao tornar a correspondência difusa eficiente, os pesquisadores abriram as portas para aplicações de privacidade mais sofisticadas. Organizações que há muito tempo evitavam o compartilhamento de dados por medo de vazamentos de privacidade ou porque o processo de correspondência era muito lento agora podem considerar a colaboração segura. Seja para cruzar registros de pacientes para pesquisa médica, verificar identidades de usuários sem expor modelos biométricos ou encontrar itens semelhantes em grandes catálogos sem revelar o conteúdo do catálogo, a barreira de entrada foi significativamente reduzida. O estudo prova que, com a abordagem algorítmica correta, o equilíbrio entre privacidade e desempenho pode ser resolvido, permitindo que os dados fluam de forma segura, mesmo quando são imperfeitos ou ruidosos.

No fim, o artigo apresenta uma solução concreta para um problema que persiste há anos: como encontrar correspondências aproximadas em dados privados sem sacrificar a velocidade ou exigir condições irreais. Os pesquisadores não apenas propuseram uma nova ideia; eles a construíram, testaram e mostraram que ela supera tudo o que veio antes por ordens de magnitude. O trabalho deles é um testemunho do poder de refinar a lógica subjacente de um problema, em vez de apenas tentar jogar mais poder de computação sobre ele. Para o observador curioso, o resultado é um sistema que parece menos uma máquina pesada e desajeitada e mais uma ferramenta precisa e eficiente, pronta para ser usada no mundo imperfeito e desordenado dos dados reais.

Resumo Técnico: PSI Difuso Eficiente sob Assunções Unilaterais

Definição do Problema

A Interseção de Conjuntos Privada Difusa (Fuzzy Private Set Intersection - PSI) permite que duas partes, um remetente e um receptor, identifiquem elementos em seus respectivos conjuntos de entrada que possuem correspondências aproximadas. Especificamente, dado um limiar de distância $\delta$ e uma métrica $dist(\cdot, \cdot)$ , o receptor aprende todos os elementos do remetente $\mathbf{q}$ para os quais existe um elemento do receptor $\mathbf{w}$ tal que $dist(\mathbf{q}, \mathbf{w}) \le \delta$ .

Embora o PSI padrão tenha apresentado progressos significativos, o PSI difuso enfrenta um compromisso entre eficiência e a força das assunções subjacentes. As construções existentes para distâncias $L_p$ gerais ( $p \in [1, \infty]$ ) tipicamente se dividem em duas categorias:

Assunções bilaterais: Protocolos que exigem que os dados de ambas as partes satisfaçam fortes separações geométricas (ex: pontos são separados entre si por $2\delta$ ou $4\delta$ ). Estes são eficientes, mas muitas vezes irreais para dados ruidosos do mundo real.
Assunções unilaterais: Protocolos onde apenas uma das partes deve satisfazer restrições de separação, permitindo que a outra parte possua entradas arbitrárias. No entanto, as soluções unilaterais existentes ou dependem de primitivas criptográficas pesadas (ex: Criptografia Homomórfica Aditiva) ou incorrem em um overhead assintótico substancial no limiar $\delta$ (ex: $O(\delta)$ ou $O((\log \delta)^d)$ ).

O desafio central abordado é construir protocolos de fuzzy PSI concretamente eficientes para distâncias $L_p$ gerais sob assunções unilaterais fracas, baseando-se exclusivamente em primitivas de chave simétrica leves.

Metodologia

Os autores propõem um framework construído sobre Funções Pseudoaleatórias Programáveis com Segredo Compartilhado (so-OPPRF) e Hashing Espacial, potencializados por técnicas de Prefix Trie.

1. Primitivas de Correspondência Difusa Multi-Ponto

Para lidar com entradas arbitrárias de uma parte sem vazamento de informações, o artigo introduz dois protocolos de correspondência difusa multi-ponto sem assunções:

Correspondência 1-para- $n$ (Receptor possui pontos arbitrários): O remetente programa uma so-OPPRF com intervalos ao redor de seu ponto único. Para evitar que o receptor infira a distribuição de entrada do remetente através de colisões em partes agregadas (um problema de vazamento em trabalhos anteriores), os autores introduzem a Randomização Condicional à Igualdade (EqRand). Esta primitiva re-randomiza as partes secretas para entradas não correspondentes enquanto preserva a soma correta para entradas correspondentes, garantindo a privacidade mesmo quando múltiplos pontos do receptor mapeiam para o mesmo intervalo programado.
Correspondência $m$ -para-1 (Remetente possui pontos arbitrários): Os papéis são invertidos. O receptor programa a so-OPPRF com intervalos ao redor de seu ponto único. O remetente avalia a função em seus múltiplos pontos. Como o receptor não reconstrói valores agregados do lado do remetente, o problema de vazamento é evitado naturalmente, e a EqRand não é necessária.

2. Fuzzy PSI sob Assunções Unilaterais

Baseando-se nas primitivas acima, os autores constroem protocolos completos de $m$ -para- $n$ fuzzy PSI sob duas assunções unilaterais específicas:

Assunção de Célula Única (Unique Cell): Cada célula espacial (de lado $2\delta$ ) contém no máximo um ponto da parte restrita.
Assunção de Bloco Único (Unique Block - Mais esparsa): Cada célula espacial intersecta com no máximo uma bola $L_\infty$ da parte restrita.

O protocolo utiliza hashing espacial para particionar o espaço. A parte restrita programa a so-OPPRF com chaves derivadas de seus pontos e identificadores de células, garantindo a ausência de colisões. A outra parte avalia a função em seus pontos e células vizinhas. O uso de so-OPPRF garante que as saídas sejam compartilhadas por segredo, impedindo que qualquer uma das partes aprenda os dados brutos da outra.

3. Otimização por Prefix Trie

Para abordar a complexidade linear ou superlinear de escala com $\delta$ encontrada em trabalhos anteriores, os autores incorporam técnicas de Prefix Trie.

Mecanismo: Em vez de enumerar todos os pontos em um intervalo $[w - \delta, w + \delta]$ (o que leva $O(\delta)$ ), o intervalo é codificado em $O(\log \delta)$ nós de prefixo usando o algoritmo PxTrie.
Filtragem Dimensão a Dimensão: Trabalhos anteriores exigiam a avaliação de todas as combinações de prefixos através de $d$ dimensões, levando a uma complexidade de $O((\log \delta)^d)$ . Os autores introduzem uma primitiva de Seleção Condicional (ConSel) que filtra os prefixos dimensão por dimensão. Como no máximo um prefixo por dimensão pode corresponder ao alvo, o espaço de busca é reduzido de $O((\log \delta)^d)$ para $O(d \cdot \log \delta)$ .
Resultado: Isso alcança uma complexidade de $O(\log \delta)$ em relação ao limiar $\delta$ para distâncias $L_p$ gerais, uma melhoria significativa em relação aos limites anteriores de $O((\log \delta)^d)$ ou $O(\delta)$ .

4. Lidando com Distâncias $L_p$ Gerais

Para distâncias $L_p$ ( $p > 1$ ), o protocolo codifica a potência $p$ -ésima da contribuição de distância por dimensão ( $|t|^p$ ) nos valores da so-OPPRF. As partes então realizam computação multipartidária segura (adição e multiplicação) para agregar essas partes e verificar se a distância total está dentro do limiar $\delta^p$ .

Principais Contribuições

Primeiro Fuzzy PSI Unilateral Eficiente para $L_p$ Geral: O artigo apresenta os primeiros protocolos concretamente eficientes para distâncias $L_p \in [1, \infty]$ gerais sob assunções unilaterais, baseando-se exclusivamente em primitivas de chave simétrica (so-OPPRF, OKVS, silent OT).
Complexidade Logarítmica em $\delta$ : Ao integrar de forma não trivial técnicas de prefix trie com um mecanismo de filtragem dimensão a dimensão, os protocolos alcançam uma complexidade de $O(\log \delta)$ na distância do limiar, superando as complexidades de $O((\log \delta)^d)$ ou $O(\delta)$ de trabalhos de estado da arte.
Suporte a Assunções Flexíveis: O framework suporta tanto configurações do lado do Remetente quanto do lado do Receptor, bem como as assunções de Célula Única e Bloco Único. A assunção de Bloco Único permite novas otimizações ao inverter os papéis de programação e avaliação para explorar o menor custo de programação versus avaliação da so-OPPRF.
Avaliação Abrangente: Os autores implementaram os protocolos e os compararam com trabalhos de estado da arte (van Baarsen & Pu [31], Dang et al. [10], Bui et al. [6], etc.).

Resultados Experimentais

A avaliação foi conduzida em um servidor com um processador AMD EPYC 9554. Os resultados demonstram melhorias significativas tanto em comunicação quanto em computação:

Contra van Baarsen e Pu (EUROCRYPT'24): Até 239 $\times$ mais rápido em computação e até 20 $\times$ menos comunicação.
Contra Dang et al. (CCS'25): Até 518 $\times$ de aceleração e redução de 63 $\times$ na comunicação.
Contra Bui et al. (ASIACRYPT'25): Até 4818 $\times$ mais rápido em computação e até 282 $\times$ menos comunicação.

As variantes otimizadas por prefixo (Ours-Px) mostram desempenho superior em comunicação para grandes $\delta$ e altas dimensões, enquanto as variantes não otimizadas (Ours) são altamente competitivas para limiares menores devido ao menor overhead computacional.

Significância e Alegações

O artigo afirma resolver o compromisso de longa data entre a força das assunções geométricas e a eficiência dos protocolos de fuzzy PSI. Ao demonstrar que o fuzzy PSI para $L_p$ geral pode ser alcançado sob assunções unilaterais fracas usando apenas primitivas de chave simétrica leves, este trabalho torna o fuzzy PSI mais aplicável a cenários do mundo real onde os dados são ruidosos e assunções de separação estrita não podem ser garantidas.

Os autores enfatizam que seus protocolos superam significativamente os trabalhos anteriores sob assunções comparáveis, alcançando ordens de magnitude de melhoria em eficiência. A introdução do mecanismo de filtragem dimensão a dimensão via prefix tries é destacada como uma inovação técnica fundamental que quebra a dependência exponencial da dimensionalidade no parâmetro do limiar, tornando os protocolos escaláveis para dados de alta dimensão e grandes limiares de correspondência.