PAC to the Future: Zero-Knowledge Proofs of PAC Private Systems

1. O Problema

Com o aumento da dependência de dados sensíveis de usuários para treinar modelos de aprendizado de máquina em larga escala (como LLMs), surgiram preocupações críticas sobre a privacidade e a falta de confiança em sistemas proprietários e baseados em nuvem.

• Limitações das Técnicas Atuais: Técnicas tradicionais, como a Privacidade Diferencial (DP), muitas vezes resultam em uma degradação significativa da utilidade dos dados ao garantir privacidade forte, especialmente em conjuntos de dados pequenos ou complexos.
• O Desafio da Verificabilidade: Embora existam métodos para computação em dados criptografados (como FHE ou MPC), eles não garantem necessariamente que o provedor de serviços (cloud) esteja executando o algoritmo corretamente ou aplicando o ruído de privacidade conforme prometido. O usuário precisa confiar cegamente no provedor.
• A Lacuna: Não existia um mecanismo eficiente para provar, sem revelar dados brutos ou parâmetros proprietários, que um sistema de privacidade (especificamente baseado em ruído) foi aplicado corretamente em um ambiente de computação terceirizada.

2. Metodologia

O artigo propõe um framework que combina Privacidade PAC (Probably Approximately Correct) com Provas de Conhecimento Zero (ZKPs), especificamente utilizando zk-STARKs em um ambiente não interativo.

Conceitos Fundamentais

• Privacidade PAC: Diferente da DP, que adiciona ruído baseado em limites globais de sensibilidade, a Privacidade PAC analisa o mecanismo de processamento (caixa preta) e determina automaticamente a quantidade mínima de ruído necessária para proteger os dados, mantendo uma melhor relação entre privacidade e utilidade.
• zk-STARKs: O trabalho utiliza Zero-Knowledge Scalable, Transparent Arguments of Knowledge. Eles são escolhidos por serem:
  • Transparentes: Não exigem configuração confiável (trusted setup).
  • Seguros contra Computadores Quânticos: Baseados em funções hash resistentes a colisões.
  • Não Interativos: Permitem a geração de provas verificáveis publicamente.

Fluxo do Sistema

O sistema opera em um ambiente de "prova" (Prover) e "verificação" (Verifier):

1. Geração de Ruído (Determinística): O provedor calcula uma matriz de covariância ($\Sigma$) para o ruído gaussiano necessário, baseada no mecanismo $M$ e nos dados. Para não revelar $\Sigma$, o provedor calcula seu hash $h(\Sigma)$ dentro de um circuito ZK e envia apenas o hash e a prova de que o hash corresponde a uma matriz calculada corretamente.
2. Computação Privada: O provedor executa o mecanismo $M$ (ex: K-means, SVM) sobre os dados de entrada $X$ e adiciona o ruído $B$ (gerado deterministicamente a partir de uma semente secreta $s$ e da matriz $\Sigma$).
3. Prova de Integridade: O provedor gera uma prova ZK atestando que:
   • O ruído aplicado corresponde à distribuição definida por $\Sigma$.
   • O resultado $M(X) + B$ foi calculado corretamente.
   • Nenhuma informação sobre $X$ ou os parâmetros de ruído foi vazada.

Adaptações para ZK (RISC-Zero)

Para funcionar em ambientes de prova (como o framework RISC-Zero), os algoritmos de aprendizado de máquina sofreram adaptações críticas:

• Laços Determinísticos: Laços while que dependem da entrada foram substituídos por iterações fixas (número de épocas pré-definido).
• Tamanho Fixo de Dados: Estruturas de dados variáveis (como listas de pontos atribuídos a um centróide) foram padronizadas para tamanhos fixos, usando booleanos para indicar validade, garantindo que o circuito aritmético tenha tamanho constante independentemente da entrada.
• Gerenciamento de Aleatoriedade: Como o ambiente de prova é determinístico, a semente de aleatoriedade para o ruído é fornecida pelo Verificador, mas o Provedor prova que a usou corretamente.

3. Contribuições Chave

1. Framework End-to-End: Apresentação do primeiro framework que integra Privacidade PAC com provas ZK não interativas (zk-STARKs) para computação terceirizada.
2. Verificabilidade de Ruído: Capacidade de provar que o ruído de privacidade foi gerado e aplicado corretamente sem revelar os parâmetros do ruído ou os dados brutos.
3. Implementação Prática: Adaptação bem-sucedida de algoritmos complexos (K-means, SVM e consultas estatísticas de banco de dados) para o ambiente de circuito aritmético do RISC-Zero.
4. Segurança Pós-Quântica: Uso de zk-STARKs garante que as provas permaneçam seguras mesmo contra adversários com computadores quânticos.

4. Resultados Experimentais

Os autores implementaram e avaliaram o sistema no framework RISC-Zero utilizando três mecanismos:

• K-means: O tempo de execução (medido em ciclos do processador RISC simulado) mostrou um crescimento afim (linear) em relação ao número de amostras e ao número de clusters ($K$). Isso confirma a previsibilidade do overhead computacional.
• SVM (Máquinas de Vetor de Suporte): Também apresentou comportamento afim geral, embora com flutuações devido a operações intensivas de memória e uso de cache no circuito ZK.
• Estatísticas de Banco de Dados: Consultas filtradas (médias, medianas) sobre dados privados demonstraram a viabilidade do método para operações de banco de dados.

Desempenho: O overhead computacional para a geração das provas é gerenciável para aplicações de pequena a média escala. O sistema mantém a utilidade dos dados (quase equivalente ao texto plano) enquanto oferece garantias de privacidade verificáveis.

5. Significado e Conclusão

Este trabalho é pioneiro ao resolver o dilema da "confiança" em sistemas de privacidade de caixa preta.

• Mudança de Paradigma: Permite que usuários de serviços em nuvem verifiquem matematicamente que seus dados foram protegidos conforme prometido, sem precisar confiar na integridade moral do provedor de serviços.
• Superioridade sobre DP: Ao utilizar PAC Privacy, o sistema evita a perda excessiva de utilidade associada à Privacidade Diferencial tradicional, especialmente em cenários onde a adição de ruído massivo tornaria os dados inúteis.
• Aplicabilidade Futura: A combinação de PAC com ZKPs abre caminho para mercados de dados e serviços de IA onde a privacidade e a integridade computacional são auditáveis publicamente, fortalecendo a confiança em ecossistemas de computação descentralizados e em nuvem.

Em resumo, o artigo demonstra que é possível ter privacidade verificável e integridade computacional simultaneamente em sistemas de aprendizado de máquina, utilizando provas criptográficas modernas para garantir que o "ruído" de privacidade não é apenas uma promessa, mas uma realidade matematicamente comprovada.