Secure and Parallel Determinant Computation for Large-Scale Matrices in Edge Environments

Resumo Técnico: Cálculo Determinante Seguro e Paralelo para Matrizes de Grande Escala em Ambientes de Borda

Declaração do Problema
A rápida adoção da Internet das Coisas (IoT) e da computação de borda criou uma demanda por frameworks escaláveis e energeticamente eficientes para lidar com tarefas computacionais intensivas. O Cálculo de Determinante de Matriz (MDC) é uma operação crítica em sistemas de controle, criptografia e aprendizado de máquina. No entanto, algoritmos tradicionais, como a decomposição LU, possuem complexidade computacional cúbica de $O(n^3)$, tornando-os impraticáveis para matrizes de grande escala em ambientes de borda com recursos limitados. Além disso, técnicas existentes de terceirização segura, incluindo criptografia homomórfica e computação multipartidária segura (SMPC), introduzem sobrecarga computacional significativa que limita a aplicabilidade em tempo real. Embora existam algumas soluções paralelas, elas frequentemente enfrentam desafios de escalabilidade, dependendo tipicamente de modelos fixos de dois servidores que não utilizam eficientemente recursos de borda distribuídos ou lidam com dimensões de matriz não divisíveis sem preenchimento excessivo.

Metodologia
O artigo propõe o framework Cálculo Determinante Paralelo Seguro (SPDC), projetado para permitir MDC com preservação de privacidade através de um número arbitrário ($N$) de servidores de borda não confiáveis. O framework opera por meio de três protocolos principais: o Protocolo de Ofuscação de Matriz com Preservação de Privacidade (PMOP), o Protocolo de Cálculo Paralelo Seguro (SPCP) e o Protocolo de Recuperação e Verificação de Resultados (RRVP).

1. Distorção de Elementos Compostos (CED): Para garantir privacidade, o framework emprega um método de criptografia leve combinando duas técnicas:

   • Ofuscação Elementar (EWO): Os elementos da matriz são transformados via Divisão Elementar (EWD) ou Multiplicação Elementar (EWM) usando um vetor de mascaramento secreto derivado de uma semente criptográfica.
   • Teorema de Rotação Panth (PRT): Uma transformação geométrica inovadora que rotaciona a estrutura da matriz (por 90°, 180° ou 270°) com base na semente. O PRT garante que o valor absoluto do determinante permaneça invariante (ou mude de sinal de forma previsível) independentemente do tamanho da matriz módulo 4, ocultando assim padrões estruturais sem alterar as propriedades fundamentais do determinante.

2. Decomposição LU Paralela: O framework generaliza o modelo de decomposição LU paralela para suportar $N \geq 2$ servidores.

   • Aumento de Matriz: Para lidar com matrizes cujas dimensões não são divisíveis uniformemente por $N$, aplica-se uma técnica de aumento que preserva o determinante. Isso estende o tamanho da matriz minimamente para garantir particionamento equilibrado sem alterar o determinante.
   • Comunicação Unidirecional: O algoritmo utiliza um padrão de comunicação escalonada e unidirecional. Cada servidor transmite resultados intermediários apenas para seu sucessor imediato a jusante. Isso elimina a necessidade de comunicação de difusão, reduzindo a sobrecarga de coordenação e permitindo que servidores a jusante iniciem cálculos assim que os dados necessários forem recebidos.

3. Verificação e Recuperação:

   • Autenticação: Para verificar a integridade do resultado com carga mínima no cliente, o artigo introduz dois algoritmos de autenticação leves, Q2 (probabilístico, baseado em escalar usando um vetor aleatório) e Q3 (determinístico, baseado em escalar usando elementos diagonais). Estes substituem métodos de saída vetorial, reduzindo a carga computacional. Um limiar $\epsilon(N)$ é introduzido para contabilizar discrepâncias de ponto flutuante em ambientes de múltiplos servidores.
   • Descriptografia: O cliente recupera o determinante original usando a semente e os componentes LU verificados, aplicando um fator de correção baseado no ângulo de rotação e no método de ofuscação utilizados.

Contribuições Principais

• Arquitetura Escalável de N Servidores: Diferentemente de trabalhos anteriores limitados a dois servidores, o SPDC suporta um número arbitrário de servidores de borda não confiáveis, melhorando a utilização de recursos e a escalabilidade.
• Mecanismo de Ofuscação Inovador: A integração do Teorema de Rotação Panth (PRT) com a Ofuscação Elementar fornece garantias robustas de privacidade, ocultando tanto os valores numéricos quanto a estrutura da matriz, enquanto preserva as propriedades do determinante.
• Verificação Eficiente: A introdução de algoritmos de autenticação baseados em escalar (Q2 e Q3) reduz significativamente a sobrecarga computacional para o cliente em comparação com métodos de verificação baseados em vetores existentes.
• Manuseio Flexível de Matrizes: O framework suporta matrizes quadradas de tamanhos pares e ímpares, aplicando extensão de dimensão apenas quando estritamente necessário para particionamento, minimizando assim cálculos redundantes.

Resultados e Análise de Desempenho
O artigo apresenta uma avaliação teórica de desempenho em vez de testes experimentais.

• Sobrecarga Computacional: O protocolo proposto demonstra a menor complexidade geral nas etapas de Geração de Semente, Geração de Chave, Criptografia, Autenticação e Descriptografia em comparação com protocolos de última geração (por exemplo, Lei et al., Fu et al., Liu et al., Gao et al.).
• Escalabilidade: A complexidade do cálculo paralelo é reduzida de $O(n^3)$ para aproximadamente $O(n^2)$ ao distribuir cargas de trabalho entre $N$ servidores.
• Segurança: O framework fornece indistinguibilidade contra adversários tentando inferir a matriz ou o determinante originais. É resiliente à colusão, pois o padrão de comunicação unidirecional e a criptografia distribuída impedem que qualquer subconjunto de servidores reconstrua os dados originais sem a semente secreta do cliente.
• Adequação à Implantação: O framework é explicitamente projetado para ambientes de borda, suportando dispositivos com recursos limitados e configurações heterogêneas de servidores, ao contrário de soluções anteriores centradas na nuvem ou de topologia fixa.

Significado
O artigo afirma que o framework SPDC aborda desafios críticos no MDC seguro e com preservação de privacidade para sistemas distribuídos assistidos por borda. Ao combinar eficiência, escalabilidade e mecanismos robustos de privacidade, oferece uma solução prática para cálculos seguros em tempo real. O framework elimina o compromisso entre segurança e desempenho frequentemente encontrado em criptografia homomórfica ou SMPC, tornando-o bem adequado para aplicações em IoT, sistemas de controle e aprendizado de máquina, onde operações de matriz de grande escala devem ser realizadas com segurança em infraestrutura distribuída não confiável. Os autores posicionam este trabalho como um novo marco para terceirização de determinante prática, eficiente e segura em cenários de computação distribuída de grande escala.