Resumo Técnico: HE-DAP

Declaração do Problema

A criptografia homomórfica (HE) permite análises preservadoras de privacidade em dados criptografados, mas sofre com uma alta sobrecarga computacional. Um gargalo crítico em cargas de trabalho estatísticas e de aprendizado de máquina é o cálculo da raiz quadrada inversa ($1/\sqrt{a}$), uma operação fundamental necessária para funções como normalização de escore-Z, assimetria (skewness), curtose e o coeficiente de correlação de Pearson.

Métodos de estado da arte existentes, como PP-STAT [13] e HEaaN-STAT [24], dependem de configurações de parâmetros fixos para o cálculo da raiz quadrada inversa. Essas configurações normalmente envolvem um grau específico para a aproximação por polinômio de Chebyshev (usado para inicializar o método de Newton) e um número fixo de iterações de Newton-Raphson. Os autores identificam uma falha fundamental nesta abordagem estática: os custos computacionais relativos das duas principais operações de HE — avaliação de polinômio de Chebyshev e bootstrapping (gerenciamento de ruído) — variam drasticamente (em até 6$\times$) entre diferentes bibliotecas de HE (ex: Lattigo vs. HEaaN) e ambientes de hardware (CPU vs. GPU).

Consequentemente, uma configuração otimizada para um ambiente (ex: Lattigo em CPU, onde o bootstrapping é lento e polinômios de alto grau são preferidos) torna-se subótima ou ineficiente em outro (ex: HEaaN-GPU, onde o bootstrapping é rápido e a avaliação de polinômios é o gargalo). Essa dependência ambiental torna os frameworks existentes não generalizáveis e ineficientes quando implantados em sistemas heterogêneos.

Metodologia: HE-DAP

Para abordar isso, os autores propõem o HE-DAP (Otimização Dinâmica de Parâmetros Adaptativa baseada em Criptografia Homomórfica), um framework cross-platform que determina automaticamente os parâmetros ideais para o cálculo da raiz quadrada inversa com base no ambiente de execução específico.

Mecanismo Central

O HE-DAP opera durante uma etapa de provisionamento (antes do processamento de dados real) para perfilar as características de desempenho do servidor alvo. Ele seleciona dinamicamente três parâmetros fundamentais para o algoritmo CryptoInvSqrt:

1. $d$: O grau da aproximação do polinômio de Chebyshev.
2. $c$: Um indicador binário para Pre-Bootstrapping (aplicar bootstrapping ao texto cifrado de entrada antes do cálculo da raiz quadrada inversa).
3. $i$: O número de iterações de Newton-Raphson.

Fluxo de Trabalho Algorítmico

1. Perfilamento (Profiling): O HE-DAP avalia todos os níveis possíveis de texto cifrado de entrada ($l$) variando de $l_{BTS} + 1$ a $l_{max}$.
2. Exploração do Espaço de Busca: Para cada nível, ele testa combinações de graus de polinômio ($d$), indicadores de Pre-BTS ($c$) e contagens de iteração ($i$).
   • Se o nível de entrada for insuficiente para a profundidade do polinômio, ele considera o Pre-BTS ($c=1$).
   • Se o nível for suficiente, ele prossegue sem o Pre-BTS ($c=0$).
3. Critério de Otimização: Para cada combinação, o sistema mede o Erro Relativo Médio (MRE) e o tempo de execução (runtime). Ele identifica a contagem de iteração ($i$) ideal que satisfaz um limite de MRE alvo.
4. Seleção de Parâmetros: O framework registra duas tuplas ideais para cada nível:
   • Orientada à Precisão (Accuracy-Oriented): Minimiza o tempo de execução sujeito a uma restrição rigorosa de MRE.
   • Orientada à Velocidade (Speed-Oriented): Minimiza o tempo de execução independentemente do MRE (útil para aplicações que toleram erros maiores).
5. Aplicação em Tempo de Execução: Durante a análise estatística real, o servidor utiliza os parâmetros ideais pré-computados correspondentes ao nível atual do texto cifrado, eliminando a necessidade de ajuste manual ou padrões fixos e subótimos.

Principais Contribuições

1. Framework HE-DAP: A introdução de um novo otimizador adaptativo que configura automaticamente a operação de raiz quadrada inversa para diversas bibliotecas de HE e hardware, afastando-se de parâmetros estáticos e específicos de ambiente.
2. Ganhos de Desempenho: Demonstração de que o HE-DAP acelera significativamente o cálculo central da raiz quadrada inversa. No ambiente HEaaN-GPU, ele alcança um aceleração de até 2,35$\times$ sobre a configuração fixa do PP-STAT, mantendo alta precisão numérica (MRE $\le 3,1 \times 10^{-8}$).
3. Avaliação Abrangente: Uma avaliação rigorosa em três cenários distintos (Lattigo, HEaaN-CPU e HEaaN-GPU) e quatro medidas estatísticas principais (escore-Z, assimetria, curtose, correlação de Pearson). Os resultados confirmam que o HE-DAP descobre consistentemente configurações ideais tanto para ambientes CPU quanto GPU.
4. Código Aberto: O lançamento da implementação completa do HE-DAP para garantir a reprodutibilidade.

Resultados Experimentais

Os autores avaliaram o HE-DAP contra o PP-STAT (baseado em Lattigo) e o HEaaN-STAT (baseado em GPU) usando o esquema CKKS.

• Desempenho da Raiz Quadrada Inversa:

  • HEaaN-GPU: O HE-DAP acelerou o PP-STAT em 2,35$\times$ no nível 12 e 1,79$\times$ no nível 7 (orientado à precisão) em comparação com a configuração fixa do PP-STAT. Comparado ao HEaaN-STAT, alcançou um tempo de execução até 2,15$\times$ mais rápido com menor MRE.
  • HEaaN-CPU: Alcançou um aumento de velocidade de 2,18$\times$ sobre o PP-STAT no nível 12.
  • Lattigo: Alcançou um aumento de velocidade de 1,96$\times$ sobre o PP-STAT no nível 11, reduzindo simultaneamente o MRE em 79$\times$ em comparação com o baseline do PP-STAT.

• Análise Estatística de Ponta a Ponta (End-to-End):

  • A aplicação do HE-DAP a medidas estatísticas (ZNorm, Skew, Kurt, PCC) em conjuntos de dados do mundo real (UCI Adult e Medical Cost Insurance) resultou em aceleração consistente.
  • No conjunto de dados Adult, o HE-DAP reduziu o tempo de execução em 42%–44% em comparação com o PP-STAT, mantendo um MRE semelhante.
  • No conjunto de dados Insurance, as reduções de tempo de execução chegaram a 44,6%.

• Análise de Trade-off: O modo "Orientado à Velocidade" permitiu uma aceleração ainda maior (até 6,34$\times$ sobre o HEaaN-STAT em GPU) ao custo de um MRE maior, demonstrando a flexibilidade do framework para diferentes requisitos de aplicação.

Significância e Alegações

O artigo afirma que o HE-DAP demonstra que a otimização de parâmetros baseada em princípios pode tornar as análises estatísticas preservadoras de privacidade práticas em escala. Ao automatizar a adaptação a ambientes de execução heterogêneos, o HE-DAP resolve a ineficiência causada por parâmetros fixos em frameworks existentes.

Os autores enfatizam que sua abordagem é consciente do ambiente (environment-aware), reconhecendo que o equilíbrio ideal entre avaliação de polinômio e bootstrapping não é universal, mas depende da biblioteca de HE e do hardware específicos. Ao navegar dinamicamente por esse trade-off, o HE-DAP garante que o bloco fundamental da análise estatística (raiz quadrada inversa) seja executado com máxima eficiência, aumentando assim o desempenho de fluxos de trabalho estatísticos complexos de ponta a ponta, sem comprometer as garantias de privacidade da Criptografia Homomórfica.

O artigo conclui que, embora a fase de provisionamento (busca de parâmetros) incorra em um custo de tempo (particularmente em bibliotecas de CPU como Lattigo), este é um custo de configuração única que gera benefícios de desempenho significativos e sustentados durante a fase de processamento de dados real. Sugere-se como trabalho futuro reduzir esse tempo de exploração utilizando proxies mensuráveis de desempenho em vez de uma avaliação exaustiva.