Resumo Técnico: NFSA: Agregação Não-Segura de Encaminhamento com Um Servidor via Compartilhamento de Segredos de Duas Camadas

1. Declaração do Problema

O Aprendizado Federado (FL) permite o treinamento colaborativo de modelos mantendo os dados locais, mas a transmissão de atualizações de modelos (gradientes) ainda apresenta riscos de privacidade. Protocolos de agregação segura são necessários para garantir que o servidor aprenda apenas o modelo agregado, e não as entradas individuais dos usuários.

Os protocolos de agregação segura baseados em servidor existentes enfrentam dois desafios primários, particularmente em cenários de dispositivos cruzados (cross-device):

1. Abandono de Usuário (Dropout) e Encaminhamento de Chaves: Para lidar com o abandono de usuários, os protocolos frequentemente utilizam o Compartilhamento de Segredos (SS) de limiar (threshold), como o SS de Shamir, onde os usuários compartilham chaves secretas com "detentores" (outros usuários ou comitês). Em configurações de servidor único, os usuários não podem se comunicar diretamente; assim, o servidor deve encaminhar essas partes secretas. Esse encaminhamento introduz uma sobrecarga de comunicação significativa ($O(NM)$ por rodada, onde $N$ é o número de usuários e $M$ é o número de detentores) e riscos de segurança, pois o servidor deve ser confiável para não manipular ou aprender as partes secretas encaminhadas (frequentamente exigindo Criptografia Autenticada).
2. Eficiência de Comunicação: Parâmetros de modelos de alta dimensão e um grande número de usuários criam gargalos de largura de banda. Esquemas de agregação "one-shot" recentes usando Funções Pseudoaleatórias Homomórficas de Chave (KhPRF) reduzem as rodadas de interação, mas sofrem com "expansão de texto cifrado". O Almost KhPRF (baseado em LWR/LWE) introduz ruído proporcional ao número de usuários, necessitando de espaço extra nas atualizações do modelo para evitar interferências, o que aumenta o volume total de comunicação ($O(RN \log N)$).

2. Metodologia

O artigo propõe o NFSA (Agregação Não-Segura de Encaminhamento), um protocolo projetado para um cenário de FL de servidor único que elimina a necessidade de o servidor encaminhar dados secretos e reduz a sobrecarga de comunicação através de um novo método de codificação.

2.1 Compartilhamento de Segredos de Duas Camadas (TLSS)

Para abordar o problema de encaminhamento, os autores introduzem o TLSS, que combina duas camadas de compartilhamento de segredos para permitir a agregação segura sem o retransmissão de partes sensíveis pelo servidor:

• Camada 1 (SS de Limiar): Utiliza o Compartilhamento de Segredos de Shamir para lidar com o abandono de usuários. O segredo de um usuário (ex: uma chave KhPRF) é dividido em partes $s_m$ distribuídas a $M$ detentores.
• Camada 2 (SS Aditivo com PRF): Em vez de enviar $s_m$ diretamente ao servidor para encaminhamento, o usuário divide $s_m$ em duas partes aditivas: $s_m = s_{m}^{A1} + s_{m}^{A2} \mod p$.
  • $s_{m}^{A1}$ é gerado usando uma Função Pseudoaleatória (PRF) chaveada por uma chave compartilhada pré-negociada $\kappa_{d,m}$ entre o usuário e o detentor $P_m$.
  • $s_{m}^{A2}$ é computado como $s_m - s_{m}^{A1} \mod p$.
  • O usuário envia apenas $s_{m}^{A2}$ ao servidor.
  • O servidor envia uma tag ao detentor $P_m$, que computa $s_{m}^{A1}$ usando sua chave compartilhada e a envia de volta ao servidor.
  • O servidor reconstrói $s_m = s_{m}^{A1} + s_{m}^{A2}$ e prossegue com a reconstrução de Shamir.
• Resultado: O servidor nunca encaminha partes secretas entre usuários e detentores, eliminando a sobrecarga de encaminhamento $O(NM)$ e a necessidade de Criptografia Autenticada nas partes secretas.

2.2 Codificação CRT para Almost KhPRF

Para abordar a expansão de comunicação causada pelo ruído do almost KhPRF, os autores propõem um novo método de codificação baseado no Teorema do Resto Chinês (CRT):

• Problema: Métodos existentes mascaram entradas $x_i$ como $y_i = \Delta x_i - F(k_i, \tau)$. Para decodificar corretamente, $\Delta$ deve ser maior que o número de usuários $n$, aumentando o comprimento de bits de cada elemento em $\log_2(n+1)$.
• Solução: Os autores agrupam (pack) $d_c$ elementos do vetor de entrada em um único inteiro usando CRT.
  • Elementos de entrada são estendidos para módulos primos distintos $p_i$.
  • Estes são combinados em um único elemento em $\mathbb{Z}_{p_c}$ (onde $p_c = \prod p_i$).
  • A agregação mascarada é realizada nesses elementos agrupados.
• Benefício: Isso reduz o número de chamadas de KhPRF por um fator de $d_c$ e reduz significativamente o volume total de comunicação ao evitar a expansão por elemento do $\Delta$.

2.3 O Protocolo NFSA

O protocolo opera em duas fases:

1. Fase Offline: Usuários e decodificadores (detentores) realizam um Acordo de Chaves (KA) para estabelecer chaves compartilhadas. Esta fase é sem estado (stateless) e realizada uma única vez.
2. Fase Online (One-Shot):
   • Mascaramento: Cada usuário gera uma chave KhPRF, compartilha-a via TLSS (enviando apenas partes aditivas ao servidor) e mascara sua atualização de modelo usando o almost KhPRF empacotado via CRT.
   • Desmascaramento: Os decodificadores computam a soma de suas partes aditivas (aproveitando a homomorfia do TLSS) e as enviam ao servidor. O servidor reconstrói a chave KhPRF global, gera a máscara global e desmascara o texto cifrado agregado para recuperar a atualização do modelo.

3. Principais Contribuições

1. Esquema TLSS: Um novo esquema de compartilhamento de segredos de duas camadas que elimina a necessidade de um servidor encaminhar partes secretas em FL de servidor único. Ele reduz a sobrecarga de comunicação para o compartilhamento de chaves e remove a exigência de criptografia autenticada nos dados encaminhados.
2. Codificação CRT para Almost KhPRF: Um novo método de codificação de entrada que utiliza o Teorema do Resto Chinês para agrupar múltiplas entradas. Isso reduz o número de chamadas de KhPRF e mitiga o problema de expansão da atualização do modelo causado pelo ruído do almost KhPRF, diminuindo tanto a sobrecarga computacional quanto a de comunicação.
3. Protocolo NFSA: Um protocolo de agregação segura compacto e "one-shot" que combina TLSS e codificação CRT. Ele suporta a agregação de dados de alta dimensão com um único servidor e sem intermediação de dados.

4. Resultados Experimentais

Os autores implementaram o protocolo em Python e o compararam com o esquema OPA de última geração (que utiliza SS de Shamir e KhPRF sem TLSS ou empacotamento CRT).

• Desempenho do TLSS: Comparado ao SS de Shamir tradicional com encaminhamento, o TLSS reduziu a sobrecarga de comunicação dos detentores em aproximadamente 57% e o tempo de computação em 95% (para módulo de 64 bits) ao compartilhar segredos com 50 detentores. A sobrecarga total foi significativamente menor devido à eliminação do encaminhamento pelo servidor.
• Desempenho da Codificação CRT: O uso de empacotamento CRT ($d_c=4$) reduziu o tempo de mascaramento do usuário em 3,72$\times$ e o tráfego de comunicação em 1,40$\times$ em comparação ao OPA.
• Desempenho End-to-End do NFSA:
  • Sobrecarga do Usuário: Para 100 usuários, o NFSA melhorou a eficiência de comunicação em quase 100 vezes (especificamente para a comunicação do decodificador) e reduziu o tempo de computação do usuário em 51% a 75% (dependendo do comprimento da entrada).
  • Sobrecarga do Servidor: O tempo de computação do servidor foi reduzido em aproximadamente 50%, e o tráfego de comunicação do servidor foi reduzido em 25% em relação ao OPA.
  • Sobrecarga do Decodificador: A comunicação do decodificador foi reduzida de ~19MB (OPA) para ~0,19MB (NFSA), uma redução de quase 100 vezes.

5. Significância e Alegações

O artigo afirma que o NFSA aborda o gargalo crítico do encaminhamento pelo servidor na agregação segura. Ao desacoplar o processo de compartilhamento de segredos do papel de retransmissão do servidor, ele reduz significativamente a superfície de ataque e os custos de comunicação. A integração da codificação CRT otimiza ainda mais a eficiência do almost KhPRF, tornando-o viável para modelos de FL de alta dimensão.

Os autores posicionam o NFSA como uma solução altamente eficiente para ambientes semi-honestos. Eles reconhecem que, embora o OPA ofereça garantias mais fortes em ambientes maliciosos (via mecanismos de verificação como SCRAPE e ZKP), o NFSA alcança uma eficiência superior no modelo semi-honesto. O trabalho sugere que o NFSA é escalável e prático para aplicações de FL do mundo real, embora trabalhos futuros sejam necessários para estender sua verificabilidade para ambientes maliciosos e refinar a verificação das entradas empacotadas via CRT.