⚛️ quantum physics

Quantum Multi-Party Threshold Private Set Intersection with Explicit Cardinality Testing

Este artigo propõe um protocolo quântico de interseção de conjuntos privados com limiar multipartidário e cardinalidade explícita, o qual utiliza uma construção de fóton único baseada em rotação e primitivas criptográficas para permitir que um terceiro realize medições sem interpretar os resultados, revelando de forma segura apenas se o tamanho da interseção atende a um limiar.

Autores originais: Zixian Gong, Kun Tian, Yi Zhang, Fengxia Liu

Publicado 2026-06-29

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Zixian Gong, Kun Tian, Yi Zhang, Fengxia Liu

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 um grupo de amigos que cada um tem uma lista secreta de filmes favoritos. Eles querem saber: "Todos nós concordamos com pelo menos três filmes?"

Se a resposta for sim, eles querem ver a lista desses três filmes.
Se a resposta for não, eles não querem saber de nada — nem mesmo quantos filmes eles realmente tiveram em comum.

Este é o problema da Interseção de Conjuntos Privada com Limiar (TPSI - Threshold Private Set Intersection). O artigo propõe uma nova maneira de resolver isso usando Mecânica Quântica (especificamente, fótons individuais de luz) e matemática astuta, garantindo que mesmo a pessoa que executa o experimento não possa trapacear ou espiar os segredos.

Aqui está como a solução do artigo funciona, dividida em conceitos simples:

1. O Problema dos Métodos Antigos

Em tentativas quânticas anteriores, o grupo dependia de um "Árbitro" (chamado de Terceira Parte ou TP) para contar as correspondências.

A Falha: O Árbitro contaria as correspondências, compararia esse número com o limiar (ex: "É 3?") e então decidiria o que dizer ao grupo.
O Risco: Isso significava que o Árbitro via o número exato de correspondências. Se o grupo tivesse apenas 2 correspondências, o Árbitro sabia disso. Mas o grupo queria saber apenas se eles tinham o suficiente (3 ou mais), não a contagem exata. É como perguntar a um juiz: "O réu é culpado?", mas o juiz primeiro precisa escrever uma biografia completa do crime antes de responder.

2. A Nova Solução: O "Árbitro de Vendas nos Olhos"

Os autores criaram um protocolo onde o Árbitro realiza as medições, mas está de vendas nos olhos em relação ao significado dos resultados.

A Configuração: O Código Secreto

Antes de começar o experimento, os amigos (participantes) concordam em um código secreto entre si. Eles também misturam suas listas de filmes reais com algumas listas falsas de "decoy" (âncoras) que o Árbitro não conhece.

A Chave de Ocultação: Eles embaralham as posições de seus filmes usando uma chave secreta. Para o Árbitro, as listas parecem ruído aleatório.
A Inversão (The Flip): Eles concordam em uma "inversão" secreta (como um aperto de mão secreto) que altera o significado dos resultados. Se uma luz fica "Ligada", ela pode significar "Desligada" dependendo desta inversão secreta.

A Dança Quântica (A Rotação)

O experimento usa fótons (partículas de luz) como mensageiros.

O Árbitro prepara uma linha de fótons e os envia para o primeiro amigo.
O Amigo 1 olha para sua lista secreta. Se ele tiver um filme específico em uma determinada posição, ele dá ao fóton um pequeno "giro" (uma rotação). Se não tiver, ele o deixa como está. Ele também adiciona uma rotação de "máscara" secreta que apenas ele e o Árbitro conhecem.
A Corrente: Os fótons viajam para o Amigo 2, depois para o Amigo 3, e assim por diante. Cada amigo adiciona seu próprio giro baseado em sua lista secreta.
O Retorno: Os fótons retornam ao Árbitro.

A Magia dos "Rótulos Escondidos"

Quando os fótons retornam, o Árbitro remove suas próprias máscaras e mede a luz.

O Resultado: O Árbitro vê um padrão de luz "Igual" ou "Oposto".
A Pegadinha: Devido à "inversão" secreta acordada pelos amigos, o Árbitro não consegue entender o que o padrão significa. Um resultado "Igual" pode significar "Correspondência" ou "Não Correspondência", dependendo de um bit secreto que apenas os amigos conhecem. O Árbitro tem os dados, mas eles parecem um monte de bobagens para ele.

3. A Verificação Final: O "Voto Cego"

Agora, os amigos e o Árbitro precisam decidir: "Atingimos o limiar?" sem que o Árito aprenda a contagem exata.

O Truque Matemático (OLE): Eles usam uma ferramenta criptográfica chamada Avaliação Linear Oblíqua (OLE). Pense nisso como uma calculadora segura onde o Árbitro insere seus números "bobos" e os amigos inserem suas "chaves secretas".
O Circuito Garbled (Garbled Circuit): Eles executam um pequeno programa de computador trancado (um circuito garbled). Este programa soma os números internamente.
A Saída: O programa gera apenas um bit: 1 (Sim, temos correspondências suficientes) ou 0 (Não, não temos o suficiente).
- Se a resposta for 1, os amigos revelam a chave secreta para decodificar o padrão de "bobagens" do Árbitro, e eles veem os filmes correspondentes.
- Se a resposta for 0, eles jogam tudo fora. O Árbitro nunca aprende o número exato de correspondências, apenas que não era alto o suficiente.

4. Por que isso é Seguro (Segurança)

O artigo prova três pontos principais de segurança:

Sem Bisbilhoteiros (Eavesdroppers): Se um espião tentar interceptar os fótons, as luzes de "decoy" (que o espião não conhece) mudarão, alertando a todos que a linha foi interceptada.
O Árbitro é Honesto, mas Curioso: Mesmo que o Árbitro tente trapacear ou usar truques quânticos avançados para adivinhar os segredos, a matemática garante que ele não consiga distinguir as correspondências reais do ruído. Ele é verdadeiramente cego ao significado dos dados.
Os Amigos Não Podem Trapacear uns aos Outros: Mesmo que dois amigos se unam para espionar o terceiro, eles não podem descobrir a lista do terceiro amigo devido às máscaras secretas e à forma como os fótons são rotacionados.

5. A Prova do "Modelo de Brinquedo" (Toy Model)

Para mostrar que isso realmente funciona, os autores construíram uma pequena simulação usando o simulador de computador quântico da IBM (Qiskit).

Eles simularam 3 amigos com listas pequenas.
Eles adicionaram "ruído" (simulando imperfeições do mundo real).
O Resultado: O sistema identificou corretamente que os amigos tinham 2 filmes em comum (o que estava abaixo do limiar de 3 deles). O sistema disse "Não", e os amigos não aprenderam nada.
Eles então mostraram que, se tivessem 3 correspondências, o sistema diria corretamente "Sim" e revelaria a lista.

Resumo

Este artigo introduz um protocolo de PSI de Limiar Multi-Parte Quântica.

Objetivo: Revelar um segredo compartilhado apenas se o grupo for grande o suficiente.
Inovação: Ele separa o ato de medir (feito por um Árbitro) do ato de interpretar (feito pelo grupo).
Mecanismo: Utiliza fótons rotacionados e "inversões" secretas para criar "rótulos escondidos" que o Árbitro não consegue ler, garantindo que a contagem exata de correspondências permaneça privada.
Resultado: O grupo aprende apenas um simples "Sim/Não" sobre o limiar e, somente se for "Sim", eles veem os itens compartilhados.

Resumo Técnico: Interseção de Conjuntos Privados com Limiar Multipartidária Quântica com Teste de Cardinalidade Explícito

Enunciado do Problema
A Interseção de Conjuntos Privados (PSI) permite que as partes computem a interseção de seus conjuntos privados sem revelar elementos não pertencentes à interseção. A PSI com Limiar (TPSI) estende isso, revelando a interseção apenas se sua cardinalidade atingir ou exceder um limiar público $\tau$ . Embora existam protocolos de TPSI clássicos, os protocolos de TPSI quânticos existentes (ex: [MSD+24, LZY+26, WLS+26]) dependem tipicamente de um Terceiro Parte (TP) para realizar as medições finais e interpretar os resultados. Nesses esquemas, o TP recupera a cardinalidade exata da interseção e então a compara com $\tau$ . Essa abordagem desvia do paradigma ideal de TPSI, pois expõe a estatística exata da cardinalidade ao TP, em vez de revelar apenas o predicado de um bit $\mathbb{1}[|\bigcap X_i| \ge \tau]$ . Isso cria uma incompatibilidade de funcionalidade e uma concentração de autoridade onde o TP atua tanto como provedor de recursos quânticos quanto como intérprete semântico dos dados privados.

Metodologia
Os autores propõem um protocolo de MP-QTPSI (Multi-Party Quantum TPSI) que desacopla o papel de medição do papel de interpretação semântica. O protocolo envolve $n$ participantes ( $P_1, \dots, P_n$ ) e um TP semi-honesto.

Fase Quântica (Construção de Rótulo Oculto):
- Configuração (Setup): Os participantes estabelecem uma chave mestra via um Acordo de Chave de Conferência Quântica (QCKA) livre de TP para derivar uma chave de ocultação de posição $k$ , um vetor de inversão de rótulo oculto $\mathbf{b}$ e shares de rotação $\Delta_i$ . O TP e cada participante estabelecem chaves bilateris para máscaras de rotação $T_i$ .
- Codificação: Os participantes aumentam seus conjuntos com conjuntos de âncora positivos e aplicam um mapeamento de ocultação de posição $x \mapsto kx \mod M$ . Eles codificam seus conjuntos em vetores indicadores $Y_i$ .
- Interação: O TP prepara sequências de fótons únicos e aplica uma rotação de cegamento inicial. As sequências atravessam os participantes sequencialmente. Cada participante $P_i$ aplica uma rotação baseada em seus dados ($0$ ou $\pi/n$ ), sua máscara bilateral $T_i$ e seu share de rotação $\Delta_i$ .
- Medição: O TP remove suas máscaras conhecidas e mede as sequências. Devido às rotações agregadas correlacionadas, os resultados da medição são determinísticos apenas para posições onde todos os participantes detêm o elemento (interseção) ou nenhum detém (não-interseção), mas o significado semântico desses resultados (qual rótulo corresponde à "interseção") é cegado pelo vetor de inversão oculta $\mathbf{b}$ . O TP obtém vetores indicadores de rótulo oculto $z_S$ (iguais) e $z_O$ (opostos), mas não pode interpretá-los sem informações do lado do participante.
Fase Clássica (Teste de Cardinalidade):
- Teste de Consistência Mascarado: O protocolo converte as medições ocultas em um teste de consistência de rótulo mascarado. Os participantes detêm rótulos de referência $\rho$ e máscaras de seleção para domínios reais e de âncora.
- Avaliação Linear Oblíqua (OLE): O TP e os participantes usam OPI (Produto Interno Oblíquo) baseado em OLE para computar shares aditivos das contagens de consistência (inconsistências $d_{\mathcal{R}}$ e $d_{\mathcal{A}}$ ) sem revelar os vetores uns aos outros.
- Decisão de Limiar: Um circuito garbled de baixo peso avalia o predicado $\text{flag} = 1 \iff (d_{\mathcal{A}} = 0) \land (d_{\mathcal{R}} \le |\mathcal{R}| - \tau)$ . Isso produz apenas o resultado booleano, garantindo que a cardinalidade exata nunca seja revelada ao TP.
- Reconstrução: Se $\text{flag}=1$ , o TP transmite os vetores ocultos, e os participantes usam seus rótulos de referência e a chave inversa $k^{-1}$ para reconstruir a interseção.

Principais Contribuições

Teste de Cardinalidade Explícito: O protocolo é o primeiro TPSI quântico a aderir estritamente ao paradigma de teste de cardinalidade, produzindo apenas o predicado de limiar $\mathbb{1}[|\bigcap X_i| \ge \tau]$ sem revelar a cardinalidade exata ao TP.
Design Quântico de Rótulo Oculto: Ao utilizar rotações agregadas correlacionadas do lado do participante e um vetor de inversão oculta, o protocolo garante que os resultados de medição do TP sejam semanticamente cegados. O TP atua meramente como uma parte de medição, incapaz de mapear resultados para elementos específicos de conjuntos ou para a cardinalidade.
Segurança Contra Colusão e TP: O protocolo prova segurança contra espiões externos (via fótons de decoy) o TP semi-honesto (que não aprende nem os conjuntos nem a cardinalidade) e participantes coludidos (que não podem inferir os conjuntos de outros devido às máscaras bilaterais e rotações de cegamento desconhecidas).
Detecção de Violação (Tamper Detection): A inclusão de conjuntos de âncora ocultos permite uma verificação de consistência ( $d_{\mathcal{A}}=0$ ) que pode detectar se o TP modifica os vetores de medição reportados.

Resultados

Corretude: Provas teóricas demonstram que o protocolo codifica corretamente o padrão de interseção e que o subprotocolo clássico avalia corretamente a condição de limiar.
Simulação: Os autores implementaram a fase quântica na plataforma IBM Qiskit usando um modelo simplificado ( $n=3$ , tamanho do domínio 8). A simulação incluiu erros de depolarização, amortecimento de fase e de leitura. Os resultados da simulação ruidosa (Tabela 3) aproximaram-se das probabilidades teóricas, passando com sucesso no teste de âncora e no teste de limiar para reconstruir a interseção correta $\{1, 3\}$ .
Complexidade: O custo de comunicação quântica é $\mathcal{O}(n(\ell M + \delta))$ , e o custo computacional é similar, onde $M$ é o tamanho do domínio aumentado, $\ell$ é o número de repetições e $\delta$ é o número de decoys.

Significância e Alegações
O artigo afirma que sua principal significância reside na resolução da "lacuna de funcionalidade" nos protocolos de TPSI quânticos existentes. Ao separar o papel de medição quântica do papel de interpretação semântica, o protocolo proposto alinha-se com a definição ideal de TPSI clássico, onde a decisão de limiar é um predicado direto e não um passo de pós-processamento sobre estatísticas reveladas. Os autores enfatizam que sua construção depende apenas de rotações de fóton único e de um passo de pós-processamento clássico leve (OLE e circuitos garbled), evitando a complexidade da Criptografia Homomórfica Quântica (QHE) usada em outros trabalhos recentes. Eles afirmam que este design oferece uma abordagem mais preservadora de privacidade para ambientes multipartidários onde o TP não deve aprender o tamanho da interseção. O artigo conclui observando que o framework é flexível e poderia potencialmente ser estendido para limiares baseados em razão ou pesos, embora atualmente opere sob um modelo de TP semi-honesto.