💻 computer science

Efficient Fuzzy Private Set Intersection from Secret-shared OPRF

Este trabalho propõe protocolos eficientes de Interseção Privada de Conjuntos Difusos (FPSI) para métricas de distância $L_p$ , baseados em operações de chave simétrica e uma OPRF com saída compartilhada secretamente, que alcançam complexidade linear e superam significativamente os métodos existentes em velocidade e custo de comunicação.

Autores originais: Xinpeng Yang, Meng Hao, Chenkai Weng, Robert H. Deng, Yonggang Wen, Tianwei Zhang

Publicado 2026-04-17

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Xinpeng Yang, Meng Hao, Chenkai Weng, Robert H. Deng, 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

Imagine que você tem uma lista secreta de endereços de casas (o Remetente) e seu vizinho tem outra lista secreta de endereços (o Receptor). Vocês querem descobrir quais casas estão próximas uma da outra, mas sem revelar nenhum endereço para o outro. Se vocês apenas mostrassem as listas, todos saberiam onde vocês moram.

Este é o problema do Fuzzy Private Set Intersection (FPSI) ou "Interseção Privada de Conjuntos Difusos". O termo "difuso" é importante aqui: em vez de procurar endereços idênticos (o mesmo número na mesma rua), vocês querem saber se as casas estão a uma distância pequena uma da outra (por exemplo, dentro de 100 metros), mesmo que os números ou nomes das ruas sejam ligeiramente diferentes.

O artigo que você enviou apresenta uma nova e muito mais rápida maneira de fazer isso. Vamos usar analogias para entender como eles resolveram o problema:

1. O Problema Antigo: A "Fábrica de Chaves" Lenta

Antes deste trabalho, para fazer essa comparação de forma segura, as pessoas usavam criptografia muito pesada, como se estivessem usando chaves de ferro maciço para abrir cada porta.

A analogia: Imagine tentar comparar duas listas de endereços, mas para cada comparação, você precisava forjar uma chave de ferro nova, carimbar com cera, e enviar por correio aéreo. Funciona, mas é extremamente lento e caro.
O resultado: Os sistemas antigos eram tão lentos que, se você tivesse muitas casas (milhões de dados) ou se a distância permitida fosse grande, o sistema travava.

2. A Solução Nova: O "Sistema de Códigos Compartilhados"

Os autores criaram um novo método que usa "chaves de papel" (operações simétricas), que são muito mais rápidas e leves. Eles introduziram três ideias principais:

A. O "Código Secreto Dividido" (so-OPPRF)

Imagine que o Remetente e o Receptor têm um livro de códigos, mas ninguém pode ver o livro inteiro sozinho.

Como funciona: Eles usam um truque matemático onde o resultado de uma comparação é dividido em duas metades. O Remetente tem a metade A e o Receptor tem a metade B.
A mágica: Sozinhos, as metades parecem apenas rabiscos aleatórios. Mas, quando somadas, elas revelam a resposta: "Sim, essas duas casas estão próximas" ou "Não, estão longe". Isso permite que eles comparem dados sem nunca mostrar os dados reais.

B. O "Mapa de Vizinhança" (Fuzzy Mapping)

Para não ter que comparar todas as casas de uma lista com todas as casas da outra (o que seria como tentar encontrar uma agulha em um palheiro comparando cada palha com cada agulha), eles criam um sistema de "IDs de vizinhança".

A analogia: Imagine que cada casa é pintada de uma cor específica baseada em sua localização. Se duas casas estão perto, elas recebem a mesma cor.
O problema antigo: Se a área de "perto" fosse muito grande, a cor vazava informações (ex: "Ah, se você tem essa cor, você deve estar perto da Rua X").
A solução deles: Eles usam o "Código Secreto Dividido" para garantir que, mesmo que as cores sejam as mesmas, ninguém saiba qual cor específica corresponde a qual rua, apenas que "nós temos cores compatíveis".

C. O "Filtro de Prefixos" (Prefix Optimization)

Eles perceberam que, se a distância permitida for muito grande (ex: comparar casas em toda a cidade, não apenas no quarteirão), o sistema ainda ficava lento.

A analogia: Em vez de escrever o endereço completo "Rua das Flores, 123, Apartamento 4B" para comparar, eles usam apenas os primeiros bits do endereço (ex: "Rua das Flores").
O truque: Eles quebram o intervalo de distância em "pedaços" (prefixos) e só comparam esses pedaços. É como procurar um livro em uma biblioteca: em vez de ler todos os títulos, você vai direto ao corredor "F", depois ao livro "Fa", e só então verifica o título completo. Isso torna a busca logarítmica (muito mais rápida) em vez de linear.

3. Os Resultados: De "Caminhão" para "Fórmula 1"

Os autores testaram seu sistema e os resultados foram impressionantes:

Velocidade: O novo sistema é 12 a 145 vezes mais rápido que os melhores sistemas anteriores. É a diferença entre dirigir um caminhão de carga e uma Ferrari.
Comunicação: Eles enviaram 3 a 8 vezes menos dados pela rede. É como enviar um e-mail de texto em vez de anexar um filme inteiro.
Escalabilidade: Funciona bem mesmo com milhões de dados e em dimensões complexas (como reconhecimento facial ou impressões digitais, onde os dados têm muitas "coordenadas").

Resumo Final

Imagine que você e seu amigo querem saber se vocês têm amigos em comum que moram no mesmo bairro, sem revelar onde vocês moram ou quem são seus amigos.

Antes: Vocês escreviam todos os endereços em papel, selavam em caixas de chumbo, e trocavam as caixas. Levava dias.
Agora (Este Artigo): Vocês usam um sistema de códigos secretos divididos e um mapa de cores. Vocês trocam apenas pequenos bilhetes coloridos. Em segundos, descobrem quem mora perto, sem nunca revelar os endereços reais.

Por que isso importa?
Isso permite que hospitais, bancos e governos comparem dados sensíveis (como registros médicos ou transações financeiras) para encontrar padrões ou fraudes, garantindo que a privacidade dos cidadãos seja mantida e que o processo não trave os computadores. É um avanço enorme para a privacidade na era dos "Big Data".

1. Problema

O Private Set Intersection (PSI) permite que duas partes (um remetente e um receptor) calculem a interseção de seus conjuntos sem revelar informações além dos elementos comuns. No entanto, em aplicações do mundo real como autenticação biométrica (impressões digitais, reconhecimento facial), os dados raramente são idênticos devido a variações ambientais ou ruído na extração de características.

O Fuzzy PSI (FPSI) estende o PSI para permitir que o receptor aprenda os itens do remetente que estão "próximos" (dentro de uma distância $\delta$ ) de algum item no conjunto do receptor, sob uma métrica de distância específica (como $L_p$ ).

Desafios Atuais:

Protocolos existentes para métricas $L_p$ (onde $p \in [1, \infty]$ ) frequentemente dependem de criptografia homomórfica aditiva (AHE) cara (ex: ElGamal, Paillier), resultando em baixa eficiência prática.
Outras soluções apresentam complexidade exponencial em relação à dimensão dos elementos ( $d$ ) ou dependem de complexidades super-lineares, tornando-as inviáveis para conjuntos de dados de alta dimensão ou grandes.
A complexidade de comunicação e computação muitas vezes escala linearmente com o limiar de distância $\delta$ , o que é problemático para $\delta$ grandes.

2. Metodologia

Os autores propõem um novo protocolo de FPSI eficiente que substitui operações de chave pública caras por operações de chave simétrica leves. A abordagem é baseada em três pilares principais:

A. Novo Bloco Construtivo: so-OPPRF

O núcleo da proposta é o Oblivious Programmable PRF with Secret-shared Outputs (so-OPPRF).

É uma variação do PRF programável onde o resultado não é revelado a nenhuma das partes individualmente, mas sim dividido em shares (partes secretas) entre o remetente e o receptor.
É construído combinando um Oblivious Key-Value Store (OKVS) com um OPRF de saída compartilhada (so-OPRF).
Isso permite que o remetente programe pontos específicos do PRF sem revelar os valores programados ao receptor, mantendo a privacidade e a eficiência.

B. Mapeamento Fuzzy Modular

O protocolo utiliza um paradigma de duas fases:

Mapeamento Fuzzy (Coarse Mapping): As partes atribuem identificadores (IDs) aos seus elementos. Se dois elementos estão dentro da distância $\delta$ $δ$ , eles recebem o mesmo ID.
- Utiliza mapeamento local e global baseado em PRFs.
- Para evitar vazamento de informação sobre intervalos parciais (um problema em soluções anteriores), o protocolo usa si-OPRF (OPRF com entradas compartilhadas) para combinar os mapeamentos locais das duas partes de forma segura.
Filtragem Refinada: Para pares com o mesmo ID, verifica-se a distância exata para eliminar falsos positivos.
- Utiliza o so-OPPRF para calcular secretamente a distância (ou sua potência $p$ ) entre os elementos.
- Para $L_\infty$ , usa-se um teste de igualdade privada (PEQT) para verificar se a soma dos shares é zero.
- Para $L_p$ ( $p < \infty$ ), converte-se os resultados do PRF para aritmética (B2A) e usa-se um teste de intervalo privado para verificar se a distância total é $\le \delta$ .

C. Otimização com Prefixos

Para lidar com limiares de distância ( $\delta$ ) grandes, os autores incorporam técnicas de representação de prefixo.

Em vez de programar todo o intervalo $[q - \delta, q + \delta]$ no so-OPPRF (o que custaria $O(\delta)$ ), o remetente programa apenas $O(\log \delta)$ prefixos que cobrem o intervalo.
Isso reduz a complexidade de comunicação e computação de linear em relação a $\delta$ para logarítmica ( $O(\log \delta)$ ).

3. Principais Contribuições

Introdução do so-OPPRF: Um novo primitivo criptográfico que permite avaliações de PRF programáveis com saídas compartilhadas, útil independentemente do contexto de FPSI.
Protocolos de FPSI Eficientes: Proposta de protocolos para métricas $L_p$ ( $p \in [1, \infty]$ ) com complexidade linear no tamanho dos conjuntos ( $m, n$ ), na dimensão ( $d$ ) e no limiar ( $\delta$ ), baseados quase exclusivamente em operações de chave simétrica.
Otimização Logarítmica: Integração de técnicas de prefixo para reduzir a dependência de $\delta$ para $O(\log \delta)$ , tornando o protocolo escalável para grandes limiares.
Análise de Segurança: Prova de segurança no modelo semi-honesto, garantindo que nenhuma informação extra além da interseção fuzzy seja revelada.

4. Resultados Experimentais

Os autores implementaram os protocolos em C++ e compararam com os estados da arte (Gao et al., ASIACRYPT'24 e Dang et al., CCS'25), que utilizam AHE.

Desempenho Geral: Os protocolos propostos superam consistentemente as soluções existentes em todos os cenários.
Aceleração de Tempo:
- Comparado a Gao et al.: Aceleração de 12x a 145x.
- Comparado a Dang et al.: Aceleração de 9x a 80x.
Redução de Comunicação:
- Comparado a Gao et al.: Redução de 3x a 8x.
- Comparado a Dang et al.: Redução de 5x a 19x.
Cenários Específicos:
- Para $\delta$ pequenos, a versão sem prefixo é mais rápida.
- Para $\delta$ grandes (ex: 1024), a versão com prefixo reduz o custo de comunicação em até 11x em comparação à versão sem prefixo, mantendo o tempo de execução competitivo.
Métricas: Os resultados foram validados para distâncias $L_\infty$ , $L_1$ e $L_2$ , mostrando que o overhead para $L_1$ e $L_2$ é mínimo em comparação com $L_\infty$ .

5. Significância

Este trabalho representa um avanço significativo na área de privacidade de dados e criptografia aplicada:

Viabilidade Prática: Ao eliminar a dependência de criptografia homomórfica pesada, torna o FPSI viável para aplicações em tempo real e de grande escala, como sistemas de autenticação biométrica e análise de dados médicos.
Eficiência Teórica e Prática: Alcança complexidade linear (e logarítmica com prefixos) em todos os parâmetros críticos, superando as limitações de complexidade exponencial ou super-linear de trabalhos anteriores.
Novos Primitivos: A introdução do so-OPPRF abre caminho para novas construções criptográficas que exigem compartilhamento de saídas de funções pseudoaleatórias, um bloco de construção que pode ser útil em outros protocolos de Computação Multipartidária Segura (MPC).

Em resumo, o artigo resolve o dilema entre segurança, privacidade e eficiência no contexto de interseção de conjuntos fuzzy, oferecendo uma solução que é tanto teoricamente robusta quanto praticamente superior às alternativas atuais.