💻 computer science

SafeStats: Efficient 2PC Protocols for Data Statistic-Related Functions

O SafeStats é um kit de ferramentas de computação de duas partes segura e eficiente, adaptado para análise estatística, que otimiza a contagem de frequência, ordenação e funções matemáticas não lineares por meio de protocolos especializados, alcançando acelerações significativas e reduções de comunicação em comparação com bibliotecas de propósito geral.

Autores originais: Tanren Liu, Xianjia Meng, Yang Liu, Xin Kang, Chenhui You, Yong Zeng, Zhuo Ma

Publicado 2026-07-29

📖 7 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Tanren Liu, Xianjia Meng, Yang Liu, Xin Kang, Chenhui You, Yong Zeng, Zhuo Ma

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ê e um amigo estão tentando resolver um mistério juntos, mas ambos têm uma regra estrita: vocês nunca podem mostrar suas pistas privadas um ao outro. Talvez estejam comparando suas contas bancárias para ver quem tem mais dinheiro sem revelar os números reais, ou verificando se seus registros médicos coincidem com um padrão de doença específico sem expor seu histórico de saúde. Este é o mundo da Computação de Dois Partes Segura (2PC). Pense nisso como uma sala trancada e mágica onde duas pessoas podem misturar seus ingredientes secretos para assar um bolo (o resultado) sem que ninguém deixe o outro espiar dentro de sua própria despensa. Por muito tempo, cientistas construíram ferramentas incríveis para ajudar com matemática simples nessa sala trancada, como somar ou multiplicar números secretos. Mas quando se trata de tarefas mais complexas — como ordenar uma lista de idades secretas ou contar quantas pessoas se encaixam em categorias específicas — as ferramentas antigas eram lentas, desajeitadas e muitas vezes caras demais para serem usadas na vida real.

Entra o SAFESTATS, um novo conjunto de ferramentas projetado por pesquisadores liderados por Tanren Liu e sua equipe para tornar esses mistérios estatísticos muito mais fáceis de resolver. Se os métodos antigos eram como tentar ordenar um baralho comparando cada carta com todas as outras uma por uma, o SAFESTATS é como ter um assistente superinteligente que pode ordenar o baralho inteiro em um único e rápido movimento. A equipe percebeu que a maioria das tarefas estatísticas se resume a três trabalhos principais: contar com que frequência as coisas aparecem, ordená-las em ordem e realizar alguma matemática não linear complicada. Ao inventar atalhos inteligentes para esses três trabalhos, eles criaram um sistema que é significativamente mais rápido e exige muito menos "conversa" (comunicação) entre os dois guardiões dos segredos. Em testes, seu novo método foi até 20 vezes mais rápido que tentativas anteriores para certas tarefas, provando que você pode fazer análise de dados complexos em informações privadas sem esperar uma eternidade pela resposta.

Os Três Truques Mágicos do SAFESTATS

Os pesquisadores começaram analisando um programa de planilha padrão (como o Microsoft Excel) para ver o que as pessoas realmente fazem quando analisam dados. Eles descobriram que quase tudo — seja encontrar o número "mais comum" (a Moda), o número "do meio" (a Mediana) ou executar um teste de Qui-Quadrado — depende de apenas três blocos de construção fundamentais. O SAFESTATS reinventou esses três blocos para funcionar de forma secreta e eficiente.

1. O Truque do "Deslocamento" para Contagem
Imagine que você tem uma fileira de 100 caixas vazias e quer contar quantas vezes um número secreto, digamos "7", aparece em uma lista de dados. O modo antigo era perguntar: "Este número é 7?" para cada item da lista. Se você tivesse um milhão de itens, teria que fazer um milhão de perguntas, o que leva uma eternidade.
O SAFESTUS usa um truque de "deslocamento" em vez disso. Imagine que você tem um único interruptante de luz que está ligado, e todos os outros interruptores estão desligados. Se o seu número secreto for 7, você simplesmente desliza essa luz "ligada" sete posições para a direita. Agora, a luz está na 7ª caixa. Você faz isso para cada item em sua lista secreta, mas faz de uma forma que ninguém saiba em qual caixa você está movendo a luz. Finalmente, você apenas soma todas as luzes em cada caixa. Se a 7ª caixa tiver 50 luzes, você sabe que o número 7 apareceu 50 vezes. Este método de "deslizar" é incrivelmente rápido porque evita as perguntas lentas e repetitivas de "É igual?". A equipe descobriu que essa abordagem tornou a contagem de 4 a quase 8 vezes mais rápida e reduziu a quantidade de dados trocados entre as duas partes em uma margem semelhante.

2. O Truque do "Balde" para Ordenação
Ordenar dados secretos costuma ser um pesadelo porque exige comparar números para ver qual é maior. Mas e se você não precisar comparar? O SAFESTATS usa um método chamado "Ordenação por Contagem" (Counting Sort), que é perfeito quando os números que você está ordenando não são enormes (como ordenar idades de 0 a 100, em vez de ordenar números aleatórios gigantescos).
Pense nisso como um correio com 100 compartimentos de correspondência. Em vez de perguntar "Esta carta é para o compartimento 5 ou 6?", você apenas deixa cair a carta no compartimento que corresponde ao seu número. O SAFESTATS faz isso secretamente. Eles usam um protocolo especial de "indicador de segmento". Imagine que você tem uma lista secreta de números. Em vez de ordená-los um por um, o sistema cria um "mapo" que diz: "Todos os 5 vão para este intervalo específico da lista final". Ele então coloca todos os 5 naquele intervalo de uma só vez. Isso evita a necessidade de comparações secretas lentas. Para conjuntos de dados com intervalos pequenos de valores, este novo método foi encontrado como sendo de 3,4 a 20,5 vezes mais rápido que os melhores métodos existentes, e reduziu os custos de comunicação em até 7,6 vezes.

3. O Truque da "Bisseção" para Matemática Difícil
Algumas fórmulas estatísticas envolvem matemática complexa, como raízes quadradas ou logaritmos, que são difíceis de calcular secretamente. A maneira usual de fazer isso é primeiro reduzir o número a um tamanho gerenciável (como dar zoom para fora em um mapa) e depois adivinhar a resposta com uma fórmula polinomial. A parte lenta era descobrir o quanto de zoom para fora fazer.
O método antigo era como verificar uma página de um livro por vez para encontrar uma palavra específica. O SAFESTATS usa um método de "bisseção", que é como jogar "Adivinhe o Número". Em vez de verificar cada página, você divide o livro ao meio, verifica se a palavra está na primeira ou na segunda metade e, então, divide essa metade novamente. Você continua cortando o espaço de busca pela metade até encontrar exatamente onde o número precisa ser ajustado. Essa abordagem de "dividir para conquistar" reduziu o tempo necessário para essas funções matemáticas de 1,2 a -1,7 vezes e também economizou tempo de comunicação.

Colocando Tudo Junto: O Teste de Qui-Quadrado

Para provar que seu conjunto de ferramentas funciona, os pesquisadores testaram o SAFESTATS em 14 diferentes cenários estatísticos do mundo real. Um exemplo de destaque foi o teste de Qui-Quadrado, um método comum usado para ver se duas coisas estão relacionadas (como se usar uma camisa vermelha afeta sua sorte).
Quando tentaram executar este teste usando as ferramentas antigas de uso geral, o processo foi lento e comunicativo. Mas quando usaram o SAFESTATS, os resultados foram impressionantes: o teste rodou 1,5 vezes mais rápido e a quantidade de dados que as duas partes tinham que enviar e receber foi reduzida em 4,2 vezes.

O artigo não apenas reivindica esses resultados; eles realmente construíram o sistema e rodaram os números. Eles mostraram que, ao focar especificamente nas necessidades da análise estatística — em vez de tentar criar uma ferramenta de "uso geral" — eles puderam criar uma maneira muito mais eficiente de manter os dados privados enquanto ainda obtemos as respostas de que precisamos. É um lembrete de que, às vezes, a melhor maneira de resolver um problema não é construir um martelo maior, mas sim inventar uma chave de fenda melhor.

Resumo Técnico: SAFESTATS

Declaração do Problema

A análise estatística em conjuntos de dados sensíveis (ex: registros médicos, transações financeiras) é crítica para a tomada de decisões, mas levanta preocupações significativas de privacidade. Embora a Computação de Dois Partes Segura (2PC) tenha avançado significativamente em primitivas de baixo nível (adição, multiplicação) e aplicações de aprendizado de máquina, ela permanece ineficiente para funções estatísticas específicas. As abordagens existentes tipicamente tentam reproduzir operações estatísticas (ex: Mediana, Rank, Moda) compondo diretamente primitivas de 2PC de propósito geral. Essa composição "ingênua" leva a um overhead proibitivo; por exemplo, computar uma função de Rank sobre $2^{12}$ elementos pode levar mais de 18 minutos, mesmo com protocolos de estado da arte. Os principais gargalos são a dependência de testes de igualdade seguros caros, comparações seguras e profundidades de circuito sequenciais que não escalam bem para tarefas estatísticas envolvendo grandes conjuntos de dados com domínios de características enumeráveis pequenos.

Metodologia

Os autores propõem o SAFESTATS, um toolkit seguro adaptado para análise estatística em 2PC. O processo de desenvolvimento envolveu a análise da biblioteca estatística do Microsoft Excel para identificar que a maioria das operações estatísticas depende de três blocos fundamentais: contagem de frequência, ordenação e funções matemáticas não lineares. O SAFESTATS introduz protocolos de 2PC especializados e eficientes para cada um desses blocos, evitando primitivas de propósito geral sempre que possível.

1. Contagem de Frequência Segura (Estratégia Baseada em Deslocamento)

Métodos tradicionais computam a frequência realizando $m$ testes de igualdade para cada elemento de entrada, resultando em $O(m\ell)$ invocações de Transferência Oblíqua (OT).

Inovação: O SAFESTATS observa que o resultado de verificar se uma entrada $x$ é igual a qualquer valor $v \in [0, m-1]$ forma um vetor unitário booleano $\vec{e}_x$ . Em vez de construir isso via $m$ testes de igualdade, o protocolo trata $\vec{e}_x$ como uma versão deslocada para a direita de um vetor unitário base $\vec{e}_0$ pelo offset $x$ .
Mecanismo: O protocolo utiliza uma estratégia de deslocamento segura baseada em Avaliação de Deslocamento de Vetor Aleatório por Transferência Oblíqua ( $F_{RVOSE}$ ). Ele substitui $m$ testes de igualdade por uma única operação de deslocamento de vetor.
Otimização: Para casos onde a frequência da moda excede $n/2$ , os autores introduzem uma otimização baseada no Teorema Chinês do Resto (CRT). Isso decompõe o grande domínio de características em subdomínios menores e coprimos, permitindo a construção de vetores de frequência mais curtos e a reconstrução local da moda.

2. Ordenação Segura (Baseada em Contagem com Indicadores de Segmento)

Ordenações seguras de propósito geral (ex: baseadas em comparação segura) sofrem com alta profundidade de circuito e rodadas de comunicação, dominadas pelo custo da comparação segura.

Inovação: O SAFESTATS propõe uma ordenação baseada em contagem segura que elimina a necessidade de comparações seguras.
Mecanismo: O protocolo consiste na construção do vetor de frequência (usando o método acima) e inserção de elementos. Para a inserção, ele introduz um protocolo de indicador de segmento seguro. Este protocolo gera um vetor com partilha secreta que é 1 sobre um intervalo específico $[a, b]$ e 0 em outros lugares.
Eficiência: Ao usar o indicador de segmento, todos os elementos com o mesmo valor podem ser inseridos no vetor de saída via uma única multiplicação elemento a elemento, alcançando profundidade de circuito constante ( $O(1)$ ) para a fase de inserção. Isso reduz a complexidade de OT de $O(n \log n \log(nm))$ para $O(n(m + \log m))$ .
Caso Especial (Percentis): Reconhecendo que percentis não exigem ordenação completa, os autores reformulam o problema como um problema de teste de intervalo. Ao verificar qual intervalo do vetor de soma de prefixos da frequência contém o rank alvo $k$ , eles evitam a ordenação completa, otimizando ainda mais o desempenho para domínios de características pequenos.

3. Funções Matemáticas Não Lineares Seguras (Redução de Intervalo por Bisseção)

A avaliação segura de funções não lineares (ex: logaritmo, raiz quadrada) tipicamente segue um paradigma de "reduzir-então-aproximar", onde o custo mais significativo é a redução de intervalo (identificação do Bit Mais Significativo Não Nulo, MSNZ).

Inovação: Protocolos existentes identificam o bit MSNZ via uma varredura linear e sequencial de dígitos, exigindo $O(d)$ rodadas de comunicação.
Mecanismo: O SAFESTATS introduz um protocolo de redução de intervalo baseado em bisseção. Em vez de escanear sequencialmente, o protocolo particiona recursivamente a entrada e seleciona a metade não nula em cada etapa.
Eficiência: Isso reduz as rodadas de comunicação para identificação de MSNZ de $O(d)$ para $O(\log d)$ , diminuindo significativamente a latência para a avaliação de funções não lineares.

Principais Contribuições

Função de Contagem Segura: Um protocolo de contagem de frequência baseado em deslocamento que reduz as invocações de OT de $O(m\ell)$ para $O(\log m)$ , com uma variante baseada em CRT para cálculo de moda.
Função de Ordenação Segura: Um protocolo de ordenação baseada em contagem utilizando um mecanismo de indicador de segmento seguro para alcançar rodadas de comunicação constantes e evitar comparações seguras, além de uma abordagem de teste de intervalo para percentis.
Funções Não Lineares Seguras: Um protocolo de identificação de MSNZ baseado em bisseção que reduz as rodadas de comunicação de $O(n)$ para $O(\log n)$ , juntamente com uma análise de intervalos de aproximação polinomial para compressão de intervalo.
Implementação e Avaliação: Uma implementação completa do SAFESTATS testada contra 14 casos estatísticos comuns (incluindo Moda, Mediana, Rank, teste Qui-Quadrado, etc.) e comparada com bibliotecas de 2PC de propósito geral (ex: EzPC).

Resultados

Os autores implementaram o SAFESTATS e o testaram em 14 casos de análise estatística. Os resultados demonstram melhorias consistentes sobre as linhas de base que utilizam diretamente primitivas de 2PC de propósito geral:

Teste Qui-Quadrado: Alcançou um aumento de velocidade de tempo de execução de 1.5 $\times$ e uma redução de comunicação de 4.2 $\times$ .
Contagem de Frequência: Alcançou melhoria de tempo de execução de 4.0–7.9 $\times$ e melhoria de comunicação de 3.1–8.6 $\times$ comparado a métodos baseados em igualdade.
Ordenação Segura: Alcançou aumento de velocidade de tempo de execução de 3.4–20.5 $\times$ e redução de comunicação de 1.3–7.6 $\times$ comparado a métodos de ordenação anteriores baseados em comparação (para cenários onde $m \le \log_2 n$ ).
Funções Não Lineares: Alcançou redução de tempo de execução de 1.2–1.7 $\times$ e redução de comunicação de 1.15–1.16 $\times$ comparado ao trabalho atual.

Significância

O artigo afirma que o SAFESTATS fornece um toolkit prático e eficiente para análise estatística preservando a privacidade, abordando uma lacuna onde as soluções de 2PC existentes são lentas demais para aplicações estatísticas do mundo real. Ao decompor operações estatísticas em três funções principais e projetar protocolos especializados para cada uma, o SAFESTATS reduz significativamente o overhead computacional e de comunicação associado à análise estatística segura. O trabalho é formalmente provado seguro no framework de Composição Universal (UC) contra adversários de meio-honesto (semi-honest). Os autores enfatizam que sua abordagem torna a análise estatística segura viável para aplicações envolvendo grandes conjuntos de dados com domínios de características pequenos, como analisar a relação entre níveis de renda e escolaridade.