- Criptografia totalmente homomórfica (FHE) é uma tecnologia que permite realizar operações sobre dados em estado criptografado, sem precisar descriptografá-los
- Atualmente, a FHE ainda tem limitações como baixa viabilidade prática, queda de velocidade de processamento de 1.000x a 10.000x e aumento de armazenamento de 40x a 1.000x
- Mas, recentemente, os algoritmos de FHE vêm alcançando melhorias de velocidade de 8x por ano, e em breve podem entrar em uma faixa prática em áreas como computação em nuvem, inferência de LLM e smart contracts em blockchain
- Se a FHE se tornar amplamente difundida, isso impulsionará uma mudança industrial em que a privacidade dos dados será o padrão em todo o ambiente computacional
- Aborda de forma abrangente criptografia baseada em reticulados, LWE, bootstrapping e outros conceitos centrais, além da evolução histórica dos algoritmos de FHE, exemplos reais de implementação e tendências de melhoria de desempenho
Introdução: o que é criptografia totalmente homomórfica
- A criptografia totalmente homomórfica (Fully Homomorphic Encryption, FHE) é uma abordagem que permite operações arbitrárias sobre textos cifrados sem descriptografia, tornando possível executar computação diretamente sobre dados criptografados
- Ou seja, o servidor pode calcular e devolver perguntas e resultados sem conhecer o texto em claro
- Essa tecnologia já está sendo adotada na prática em vários sistemas do mundo real
O potencial e os limites da FHE: a "Lei de Moore da FHE"
- A FHE pode manter os dados continuamente criptografados na rede, tornando possível uma privacidade total que bloqueia na origem o risco de vazamento de dados
- Mesmo assim, a razão de ainda haver muitas restrições para adoção prática é a queda drástica de desempenho: operações sobre texto cifrado são de 1.000 a 10.000 vezes mais lentas do que sobre texto em claro, e o armazenamento também aumenta em cerca de 40 a 1.000 vezes
- Isso se assemelha ao início da internet nos anos 1990
- No entanto, recentemente a FHE vem ficando 8 vezes mais rápida a cada ano, e a expectativa é que em breve entre em vários domínios práticos
Ponto crítico: a viabilidade prática da FHE está próxima
- Se esse ritmo de avanço acelerado continuar, no futuro a FHE poderá se tornar prática em áreas como:
- computação em nuvem criptografada
- inferência de LLM criptografada
- smart contracts de blockchain com garantia de sigilo
- Essa mudança pode abalar profundamente o modelo de negócios da internet baseado na coleta de dados dos usuários
- Com a FHE, espera-se uma transição essencial de uma internet em que "vigilância é o padrão" para uma internet em que "privacidade é o padrão"
O calcanhar de Aquiles da segurança de dados e a solução da FHE
- Os dados passam por 3 estados (armazenamento, transmissão e uso), e o estado "em uso" costuma ser descriptografado, tornando-se uma vulnerabilidade de segurança
- Nuvem, insiders, hackers e CPUs vulneráveis: todos podem acessar dados em texto claro na memória
- Grandes incidentes de vazamento de dados também ocorrem, em sua maioria, durante o estado "em uso" ou "em armazenamento"
- A FHE mantém os dados criptografados durante todo o ciclo de vida, eliminando essa vulnerabilidade pela raiz
Definição de computação com privacidade total
- Em um ambiente ideal, os dados permanecem criptografados durante o armazenamento, a transmissão e o uso (processamento)
- Por exemplo, o servidor nunca vê a pergunta em texto claro; ele recebe uma pergunta criptografada e devolve apenas um resultado criptografado
- Somente o usuário pode descriptografar esse resultado
Como a FHE funciona: estrutura matemática e conceitos
- "Homomórfica" baseia-se em transformações matemáticas que preservam a mesma estrutura, de forma semelhante, por exemplo, à transformada de Fourier
- A FHE transforma bidirecionalmente entre o espaço de texto em claro e o espaço de texto cifrado, de modo que descriptografar o resultado de uma operação sobre o texto cifrado equivale exatamente ao resultado da operação sobre o texto em claro
- Nessas transformações, usam-se principalmente criptografia baseada em reticulados e LWE (Learning With Errors)
- A criptografia baseada em reticulados lida com problemas vetoriais em dimensões extremamente altas e é considerada difícil até mesmo para computadores quânticos resolverem (resistência quântica)
- LWE é o problema de inverter um sistema linear com ruído misturado, o que o torna, na prática, indecifrável
Gerenciamento de ruído e bootstrapping
- Na FHE, à medida que as operações se acumulam, o ruído dentro do texto cifrado aumenta
- Em operações de soma, ele cresce linearmente; em multiplicações, cresce geometricamente, levando por fim à impossibilidade de descriptografar
- A tecnologia central para resolver isso é o bootstrapping, uma técnica que recriptografa o texto cifrado com uma 'nova chave pública' e redefine o ruído para um nível controlado
- Esse processo é o gargalo de desempenho dos sistemas FHE, mas vem melhorando rapidamente a cada ano
Outros componentes centrais da FHE
- relinearization: processo que resolve o problema do aumento do grau da chave para 2 após a multiplicação, trazendo-o de volta para grau 1
- modulus switching: técnica que reduz o módulo do texto cifrado para gerenciar o ruído
Além disso, várias outras técnicas continuam sendo propostas conforme os algoritmos evoluem
Classificação dos esquemas de criptografia homomórfica (HE) e exemplo em Python
- Criptografia parcialmente homomórfica (Partial HE): suporta apenas uma operação (por exemplo, a cifra de Paillier suporta apenas soma)
- Criptografia somewhat homomorphic (Somewhat HE): suporta soma e multiplicação, mas com limite no número de multiplicações repetidas
- Criptografia totalmente homomórfica (FHE): suporta soma e multiplicação sem limite; garante completude de Turing
Por meio de um exemplo da cifra de Paillier implementado em Python, é possível experimentar intuitivamente a homomorfia parcial
História do desenvolvimento da FHE e a "Lei de Moore da FHE"
- 1978: surge pela primeira vez o conceito de "isomorfismo homomórfico de privacidade"
- 2009: primeira realização de FHE por Craig Gentry (tese de doutorado)
- 2011: primeira implementação, levando 30 minutos por bit (extremamente lenta)
- Desde 2013: bootstrapping reduzido para o nível de alguns ms
- 2017: suporte a aproximação em ponto flutuante com CKKS e afins, iniciando a adoção séria em ML/AI
Os algoritmos de FHE vêm melhorando 8x por ano desde 2011, saindo de um overhead inicial de 10¹⁰x para algo em torno de 10³~10⁴x recentemente
Artigos recentes reduziram o throughput de multiplicação em FHE em 1.000x e a latência em 10x, e, combinados com aceleração por hardware, ainda há margem para mais de 1.000x de ganho adicional
Um futuro em que a criptografia é o padrão
- Grandes vazamentos de dados são uma realidade inevitável
- Se, com FHE, o servidor puder apenas operar sobre dados criptografados sem ter a chave de descriptografia, isso se tornará um novo padrão de proteção de privacidade
- Ainda não é totalmente prática em todas as áreas, mas melhora em velocidade de forma impressionante a cada ano
- Combinada com a crescente demanda por privacidade dos usuários e o endurecimento das regulações, a previsão é que a FHE acabe se tornando padrão na maior parte da computação em nuvem
- A computação da internet do futuro evoluirá em um estado sempre criptografado
Anos 2010: HTTPS como padrão
Daqui para frente: espera-se a chegada de uma era em que FHE será o padrão
Referências e materiais adicionais
- FHE Reference Library: compilação abrangente de materiais acadêmicos
- Tese de doutorado de Craig Gentry de 2009: ponto de partida da FHE
- Vitalik Buterin: análise aprofundada de FHE
- Comunidade: FHE.org (hub voltado a desenvolvedores)
- GitHub: awesome-he: coleção de projetos relacionados à criptografia homomórfica
1 comentários
Comentários do Hacker News
Vou falar partindo do pressuposto de que gosto muito de FHE e de criptografia. Dizem que o FHE está ficando cada vez mais rápido, mas enquanto depender de bootstrapping não vai conseguir alcançar a velocidade de operações em texto puro. O overhead de mais de cerca de 1000x causado pelo bootstrapping é fundamentalmente inevitável, e quando perceberam que não dava para torná-lo mais rápido, começou-se a falar em aceleração por hardware. Mas isso não é fácil numa época em que todo o poder computacional está sendo consumido por LLMs. Se pensar em quantas vezes o custo por token subiria ao usar FHE, a menos que fique bem abaixo de 1000x, na prática quase não há viabilidade. Para privacidade, confidential computing é por enquanto a única alternativa prática. Não gosto da parte de ter de confiar no hardware, mas é o melhor que temos
Existe um motivo ainda mais fundamental pelo qual é difícil usar FHE para computação arbitrária. Certos tipos de operação ficam anormalmente mais complexos no texto cifrado do que no texto puro. No caso de busca em banco de dados, em texto puro é O(log n), mas ao buscar com chave criptografada vira O(n). Por isso, uma busca no Google totalmente homomórfica é basicamente inviável. Já inferência de DNN totalmente homomórfica pode ser diferente
Mesmo sem bootstrapping, FHE não pode ser tão rápido quanto operações em texto puro. O texto cifrado é cerca de 1000 vezes maior que o texto puro. Isso significa necessidade muito maior de largura de banda de memória e de computação. Não dá para fechar essa diferença
Fico pensando se não existe um nicho específico que realmente queira privacidade verificável, mesmo que o custo computacional aumente 1000x. Não seria um mercado do tamanho do Dropbox, mas imagino que exista algum espaço
Lembro da época em que tudo era placa de expansão PCIe. GPU também era assim, e havia aceleradores especializados como coprocessadores matemáticos. Hoje está tudo integrado em hardware de uso geral, mais barato e conveniente, mas isso não faz tão bem quanto chips de silício otimizados para funções específicas. Por isso, defendo usar placas dedicadas para AI/ML em vez de depender de GPU. A arquitetura se sobrepõe em parte, mas placas de IA baseadas em GPU acabam aceitando várias perdas. Na minha visão, o verdadeiro acelerador de IA é hardware dedicado em soquetes SXM modernos. Mas soquete SXM só existe em servidor e não custa barato
Reconheço a febre dos LLMs, mas fico curioso se realmente não há outros usos bons para FHE. Por exemplo, talvez dê para hospedar no servidor um algoritmo de trading que não exija alta velocidade usando FHE, garantindo segurança
O motivo de o FHE ser importante é que hoje empresas às vezes são obrigadas, sob pressão do governo, a quebrar a criptografia de determinados alvos. O FHE permite que a empresa diga com tranquilidade: "nós jamais conseguimos ver o texto puro". Em papéis de carrier de rede isso já é parcialmente possível com E2E encryption e afins, mas ainda não é possível quando os dados precisam ser processados em texto puro. Privacidade é um direito humano básico. O poder do governo deveria operar apenas de forma muito limitada sobre atividades democráticas como voto, arte, imprensa e expressão
Mesmo que FHE permita computação arbitrária, a maioria dos serviços existe para fornecer dados específicos. Se o Google quisesse garantir segurança para minha consulta, teria de criptografar todo o índice de busca, o que é inviável na prática. Também do ponto de vista de negócios, fora de áreas muito pequenas de alta confiança e alto risco, quase não há incentivo para adotar serviços baseados em FHE
Pelo que sei, basta criptografar apenas os dados sensíveis (por exemplo, meus dados bancários). A própria função a ser calculada não precisa ser criptografada; ela pode ser usada em conjunto com dados públicos
No fim, do ponto de vista das grandes empresas, elas precisam olhar diretamente para os dados ou consultas do usuário para monetizar, então não têm motivação habitual para adotar FHE. Em bancos e finanças pode ser interessante, mas fora disso não se sabe quando será adotado
A parte do incentivo está correta. Mas a primeira parte é diferente. Consulta privada a um banco de dados em texto puro já é possível há alguns anos. Só que isso exige um pré-processamento bem complexo do banco de dados puro, ou, no pior caso, uma varredura linear do banco inteiro
Apresentam o spiralwiki.com como exemplo de implementação de um mecanismo de busca totalmente privado com FHE. O servidor não tem como saber qual artigo da Wikipédia o usuário está lendo spiralwiki.com
Do "lado do cliente", talvez haja pessoas dispostas a pagar por um serviço que proteja os dados de forma perfeita como o FHE, mas na prática seria extremamente caro e teria pouquíssimos assinantes. Fazendo as contas sob a premissa de um custo computacional dezenas de vezes maior que o atual, mesmo que um substituto do Google focado em privacidade custasse US$ 100 por ano, seria difícil atrair muitos assinantes. Quanto mais o custo sobe, menos assinantes haveria. Existem alternativas como o Tor, que, embora não sejam perfeitas, oferecem bastante proteção de graça. Não é que HE seja inútil, mas sim que só uma minoria muito pequena aceitaria pagar esse custo
Mencionam a possibilidade de a internet mudar de um modelo em que "a vigilância é o padrão" para um em que "a privacidade é o padrão". Eu também venho difundindo tecnologias de privacidade há muito tempo, inclusive criando assinaturas digitais. Mas é preciso olhar para a realidade em que Hacker News ou Facebook detêm a identidade de todos. Isso acontece porque é fácil demais e dá dinheiro. O FHE também é uma tecnologia que "as pessoas querem, mas que na prática não se espalha rápido nem amplamente". Em muitos casos, considera-se que o jeito atual já funciona bem o suficiente por causa do overhead operacional e da complexidade
Quando eu colocava algo como assinaturas digitais no fim dos e-mails, a única reação era "o que é isso?". Fico curioso se alguém já teve experiência em convencer usuários comuns a aderirem à criptografia no cliente
Há a opinião de que, quando FHE e IA se combinarem, a IA pode absorver parte do peso da complexidade, e isso talvez gere uma combinação realmente matadora para adoção ampla
Na prática, acho que não há motivo para empresas adotarem uma solução parecida com um serviço FHE, usando 1.000.000x mais computação, sendo muito mais difícil de depurar e ainda sem poder analisar padrões de uso
Começar a discussão com o exemplo do Google pode gerar mal-entendidos. Normalmente, quando se fala "Google", pensa-se em "busca na web", mas o FHE descrito no documento pode não se encaixar nesse contexto porque toda a entrada precisa ser criptografada com uma única chave. O índice de busca do Google tem vários TB, e criptografar tudo isso com uma chave específica parece impossível. Ou seja, FHE só é útil quando o usuário controla toda a entrada. A referência ao Google confunde
Em casos como o CallerID da Apple, talvez não seja necessário criptografar o banco de dados inteiro para cada usuário pesquisa da Apple sobre criptografia homomórfica / busca com preservação de privacidade da Apple
Um serviço homomórfico nem precisa saber antecipadamente a chave de criptografia. Esse é justamente o ponto. Como exemplo de criptografia muito simples, apresentam uma estrutura em que é possível obter o resultado da soma de textos cifrados sem definir a chave. Se isso for estendido para cifras mais fortes e operações mais complexas, dá para implementar uma variedade enorme de funções
Quando se fala em Google, não se pensa só em busca; também há Gmail, Google Docs e muitos outros serviços ligados a dados pessoais. Quem só pensa em busca provavelmente nem vai ler a matéria relacionada
Acho difícil que o FHE seja introduzido de imediato em computação de uso geral ou serviços de internet. Provavelmente isso só será possível depois de muitas gerações adicionais da lei de Moore. Mas já pode haver áreas em que o FHE começou a brilhar: smart contracts, finanças e saúde, onde a complexidade é menor, mas o nível de segurança e confiança exigido é muito alto. Considera-se que, recentemente, graças à lei de Moore e à otimização de software, a curva começou a se inclinar em direção à viabilidade prática. Mencionam como exemplo o trabalho de hardware e DevTools da Zama
Um git com E2EE já foi desenvolvido. Perguntei à pessoa que o criou se era possível resolver exigências no servidor como branches protegidos ou impedir force push, mas se o cliente for malicioso não havia grande solução. Fico curioso se isso algum dia vai evoluir para um GitHub com E2EE link relacionado no Hacker News
Quando ouço o discurso de que a velocidade do FHE continuará melhorando, lembro de um antigo problema matemático sobre velocidade média. Por exemplo: se você percorre 1 milha subindo a 15 mph, a que velocidade precisa descer a próxima milha para que a média nas 2 milhas seja 30 mph? O ritmo de melhora do passado não garante a possibilidade futura. Isso não é um limite físico, mas algorítmico
E se a descida fosse um precipício? Considerando uma velocidade terminal do carro em torno de 200 a 300 mph, talvez dê até para calcular que 1 milha em queda livre poderia ser percorrida em 15 segundos. Para manter média de 30 mph nas 2 milhas, o total teria de levar 4 minutos, então a velocidade na subida teria de ser ajustada ao tempo restante, mas na prática isso seria inviável por várias variáveis
Fazendo a conta rigorosamente, bastaria atingir 41 mph na descida para que a média total fosse 30 mph. Isso sai assim se assumir arredondamento numérico ou erro de medição na própria pergunta