Quando se pensa em criptografia, os primeiros usos que vêm à mente são a criptografia em repouso e a criptografia durante o transporte. O primeiro permite armazenar alguns dados em discos rígidos criptografados, dispositivos removíveis ou até mesmo bancos de dados em nuvem e oferece a garantia de que apenas o proprietário legítimo pode ver ou editar o conteúdo em texto simples. A criptografia durante o transporte garante que os dados transmitidos pela Internet sejam acessíveis apenas pelos destinatários designados, mesmo que passem por roteadores ou canais públicos. Ambos os cenários dependem da criptografia, com a garantia adicional de integridade de que os dados também não foram adulterados por um atacante malicioso no meio. Isso é conhecido como criptografia autenticada: uma vez que os dados são criptografados, ninguém na cadeia pode inferir qualquer bit de dados (confidencialidade) e ninguém pode alterar o texto cifrado sem que seja detectado (integridade/autenticidade).

Alguns casos de uso colaborativo exigem que algum processamento não trivial seja permitido mesmo em textos cifrados. Este é o domínio das técnicas de preservação da privacidade, ou criptografia em uso, sendo a criptografia totalmente homomórfica (FHE) uma delas. Um exemplo é a votação eletrônica na nuvem: os eleitores podem, por exemplo, criptografar sua cédula, então alguma entidade no meio agrediria todas as cédulas para contar o número de votos, e apenas o resultado final seria publicado. Infelizmente, com a criptografia autenticada, a entidade no meio precisaria descriptografar todas as cédulas para realizar tal cálculo, e veria os votos individuais no claro, o que é bastante complicado. Poderíamos, em tese, embaralhar as cédulas (alguns protocolos de votação eletrônica realmente dependem disso), mas, ao contrário das cédulas de papel, os mecanismos criptográficos tradicionais que garantem a integridade também tornam muito mais difícil desvincular uma cédula criptografada da identidade de seu remetente. Em um esquema de votação eletrônica, pode-se adicionar uma parede de hardware em torno da entidade que conta os votos. Este é, por exemplo, o objetivo de enclaves de execução confiáveis. Tais enclaves tornariam muito mais difícil para um invasor interagir com a entidade. Mas então uma falha no hardware pode vazar a chave de descriptografia e, ao contrário dos erros de software, as vulnerabilidades de design de hardware não podem ser corrigidas facilmente.

Para lidar com este e outros casos de uso semelhantes, podemos fazer uso da Criptografia Homomórfica Completa (FHE). FHE é uma forma especial de criptografia que permite calcular uma função sobre os textos cifrados sem descriptografá-los e obter uma criptografia da saída da função diretamente.

Na maioria das vezes, a função f a ser avaliada é pública, portanto, a sequência de etapas de processamento para converter uma criptografia de f(x) é de conhecimento público e pode ser realizada na nuvem sem envolver nenhum segredo.

Esta figura representa os 3 cenários para votação eletrônica: na imagem mais à esquerda, uma entidade confiável embaralha e descriptografa os votos individuais antes de publicar sua adição. Devemos confiar na entidade que realiza o cálculo para preservar a privacidade do eleitor e contar os votos corretamente. Na imagem central, é usado um Enclave Confiável, confiável para fornecer garantias de integridade e privacidade, para realizar o mesmo cálculo. Na imagem à direita, é usada a criptografia homomórfica: os votos criptografados podem ser adicionados (publicamente) antes que o resultado seja descriptografado. E( ) significa a operação de criptografia, enquanto D( ) denota descriptografia.

A EHC também é compacta, o que significa que o tamanho em bits do texto cifrado de saída e o esforço para decifrá-lo dependem apenas do número de bits no resultado do texto simples. Isso não depende da cadeia de computações que foi aplicada. Isso exclui criptossistemas não compactos triviais que simplesmente concatenariam o texto cifrado de entrada de x com o código fonte de f e deixariam o destinatário fazer todo o trabalho decifrando x e depois aplicando f.

A terceirização do FHE é frequentemente apresentada como uma alternativa às enclaves seguros, com base na dificuldade de um problema matemático em vez de barreiras práticas. Portanto, o FHE é completamente invulnerável a ataques passivos de canal lateral, ou outras corrupções do host em nuvem. Imagine que alguém precise terceirizar algum cálculo, mas os dados são realmente sensíveis. Essa pessoa provavelmente hesitaria em usar um VM em nuvem se outra pessoa pudesse ter privilégios de root na máquina. Eles também hesitariam em executá-lo em um enclave como SGX, sabendo que a CPU e a memória dos hosts em nuvem são constantemente monitoradas quanto a carga, energia, temperatura. Talvez algumas informações possam ser extraídas dessas medições. Essa pessoa pode ser tranquilizada pela promessa do FHE de que extrair qualquer bit de informação requer a quebra de um problema matemático pós-quântico, independentemente de qualquer tipo de medição que poderíamos reunir.

Se a confidencialidade fornecida pelo esquema impede um atacante de ler qualquer bit de informação sem a chave secreta, a maleabilidade universal da FHE permite, por outro lado, que um atacante inverta qualquer bit que seja computado: em um circuito, isso seria equivalente a ataques ativos de canal lateral, onde o atacante recebe um feixe de laser mágico que pode direcionar qualquer bit. Pode parecer muito assustador no início, mas na FHE esses ataques correspondem a execuções desonestas das operações homomórficas. Eles podem ser evitados adicionando replicação ou redundâncias na computação.

FHE é frequentemente apresentado de forma de chave pública. Há:

1. Uma chave de descriptografia: Esta é a chave-mestra do criptossistema, a partir da qual todas as outras chaves podem ser derivadas. A chave de descriptografia é tipicamente gerada localmente e nunca transmitida, e a única pessoa que pode descriptografar um texto cifrado de criptografia homomórfica completa é o proprietário da chave de descriptografia.
2. Uma chave de criptografia: No modo de chave pública, quando a parte que fornece o texto cifrado inicial não é o proprietário da chave de descriptografia, esta chave de tamanho médio geralmente consiste em criptografias aleatórias de zero. Como o FHE suporta funções afins, isso é suficiente para criptografar qualquer mensagem.
3. Uma chave de avaliação: Esta chave deve ser dada a qualquer parte que avaliará uma função em textos cifrados. Esta chave também é segura para ser publicada ou transmitida como qualquer chave pública. O tamanho da chave de avaliação varia de vazio a muito grande, dependendo se a função a ser avaliada é linear ou arbitrária.

O proprietário da chave de descriptografia é o proprietário do segredo mais sensível do criptossistema. Essa pessoa é responsável por garantir que a cadeia de operações homomórficas executadas seja legítima e que o texto cifrado final seja seguro para descriptografar e, em seguida, descriptografar o resultado em texto simples. Se operações maliciosas forem introduzidas na cadeia, a chave de descriptografia poderá ser potencialmente vazada durante a descriptografia. Felizmente, as operações homomórficas podem ser feitas publicamente e verificadas.

Cenários de FHE

Nesta seção, descrevemos alguns cenários em que a Criptografia Homomórfica Completa pode ser usada, bem como alguns prós e contras de cada configuração.

Modo de terceirização

Nesta figura, o símbolo da chave laranja simboliza a chave de descriptografia (e seu proprietário). Os textos cifrados FHE são representados por fechaduras da mesma cor que a chave de descriptografia. As partes que contribuem com dados privados são representadas por um cilindro: aqui, apenas Alice contribui com dados privados. No lado de Bob, a função de avaliação e a chave de avaliação são públicas, e a computação, representada por uma caixa verde, pode ser feita de forma determinística. Todos podem refazer a computação e detectar se o texto cifrado de saída alegado está incorreto.

Este é historicamente o primeiro caso de uso que foi publicado para FHE. O objetivo é transformar a computação em nuvem em uma computação privada análoga a um enclave seguro, mas baseada em segurança criptográfica em vez de segurança de hardware. Nesse cenário, Alice possui alguns dados privados, mas tem capacidades de computação limitadas. Bob imita uma instância em nuvem com muito mais poder de computação. Bob não contribui com nenhum dado privado adicional. Alice pode terceirizar uma computação criptografando as entradas, Bob então avalia a função desejada (pública) de forma homomórfica e envia o resultado criptografado de volta para Alice.

Com as atuais capacidades de hardware, o modo de terceirização ainda é um pouco lento para ser usado em plena generalidade na prática - normalmente podemos contar com um fator de sobrecarga de tempo de execução de 1 milhão e uma sobrecarga de memória de 1 mil em casos de uso não lineares. No entanto, o hardware FHE está sendo desenvolvido atualmente para reduzir essa diferença, assim como o Gate.Projeto DPRIVE da DarpaouCryptoLight.

Atualmente, o modo de terceirização é utilizado na prática para casos de uso de PIR (Recuperação de Informação Privada), onde um servidor (Bob) possui um grande banco de dados público, um cliente (Alice) emite uma consulta e o índice que é consultado deve permanecer privado. Esses esquemas de PIR se beneficiam muito da linearidade e compacidade das operações criptografadas homomórficas, enquanto a pequena profundidade multiplicativa dos circuitos mantém os custos computacionais dentro de limites razoáveis.

Essa tabela resume os prós e contras do modo de terceirização.

Modo de Computação de Duas Partes

Esta figura usa a mesma codificação de cores como antes. Desta vez, Bob contribui para o cálculo com alguns dados privados. O cálculo no lado de Bob não é mais publicamente verificável, simbolizado por uma caixa vermelha, este modo deve ser restrito a casos de uso honestos, mas curiosos.

Nessa nova configuração, a única diferença é que Bob contribui para o cálculo com alguns dados privados. Nesse caso, a EHF é uma boa solução de computação de duas partes, com comunicação mínima e fornece garantias sólidas no lado do pesquisador: Bob não aprende nada sobre os dados de Alice e Alice aprende o resultado do cálculo.

Uma aplicação potencial para esse cenário seria o problema dos milionários, onde Alice e Bob são dois milionários que querem saber quem é mais rico sem revelar sua riqueza para a outra parte. Soluções para esse problema são usadas em aplicações de comércio eletrônico.

Modo de Agregação

Esta é uma refinamento do modo de terceirização, onde os dados de muitos participantes podem ser agregados de forma compacta (no sentido de que a saída não cresce com a quantidade de participantes) e de maneira publicamente verificável. Os usos típicos incluem aprendizado federado e voto eletrônico.

Modo Cliente-Servidor

Essa configuração é um refinamento do modo de cálculo de duas partes, onde a parte de cálculo agora fornece um serviço de cálculo seguro para vários clientes, que têm sua própria chave secreta. A criptografia homomórfica completa pode, por exemplo, ser usada como um serviço de previsão de modelo privado (por exemplo, um serviço de ML com um modelo privado e entradas): o servidor possui o modelo privado (privado, mas em texto simples) e cada cliente possui seus próprios dados e gostaria de executar uma previsão. Como resultado, cada cliente obtém sua própria previsão criptografada, com sua própria chave secreta.

Como a criptografia homomórfica garante que a função calculada é legítima?

É sempre mais fácil usar a criptografia homomórfica em cenários colaborativos onde cada participante tem um incentivo para seguir o protocolo honestamente. A criptografia homomórfica pode, por exemplo, ser usada para calcular estatísticas entre duas entidades jurídicas do mesmo grupo em dois países diferentes: regulamentações como o GDPR permitem que algumas estatísticas sejam publicadas, mas impedem geralmente a coleta de todos os dados individuais em um único local. Nesse caso, usar a criptografia homomórfica é possível e todos os participantes têm incentivo para seguir o protocolo honestamente. Em um cenário não colaborativo, a maneira mais fácil de garantir que a função relevante tenha sido calculada é introduzir redundância. Por exemplo, nos cenários de terceirização e agregação, os cálculos homomórficos são completamente públicos e podem ser tornados determinísticos. Desde que duas ou mais entidades independentes acabem com o mesmo texto cifrado de saída, o cálculo está correto e o resultado pode ser descriptografado com segurança. Quanto mais redundância, maior a confiança que podemos ter no resultado, o que é, é claro, uma troca com a eficiência.

Além disso, quando a parte de computação garante um resultado FHE assinando digitalmente os textos cifrados de entrada e saída, todos podem refazer a mesma computação FHE e verificar se a prova é válida. Qualquer tentativa de fraude pela parte de computação FHE pode ser publicamente detectada e associada a um certificado publicamente verificável que expõe a fraude e o fraudador - chamamos esse modelo de modelo de segurança encoberta forte.

Assinaturas totalmente homomórficassão outra forma de verificar a correção de um cálculo, sem a necessidade de um verificador independente, mas geralmente requer muito mais recursos.

Como o FHE garante que o destinatário final decripta apenas o resultado final e não as variáveis intermediárias?

A maneira mais fácil de fazer isso é garantir que o proprietário da chave de descriptografia não tenha acesso a nenhum texto cifrado intermediário.

No cenário de duas partes, ou no de cliente-servidor, Alice criptografa a entrada, Bob realiza o cálculo sobre os textos cifrados e transmite a saída criptografada de volta para Alice, fica claro que Alice só será capaz de descriptografar o resultado, ela não tem acesso a nenhuma outra variável.

Em um cenário de agregação em nuvem, como a votação eletrônica onde muitos participantes enviam cédulas criptografadas em uma nuvem comum, outra técnica é usada: a chave de descriptografia geralmente não é fornecida a um único destinatário, mas sim compartilhada em segredo entre diferentes membros de uma autoridade de descriptografia. Nesse caso, a descriptografia só pode ser acionada em um texto cifrado específico executando um cálculo multipartidário que envolve comunicação online entre os membros da autoridade. Se um membro se recusar a descriptografar um texto cifrado, a descriptografia será impossível. Isso garante que apenas os textos cifrados acordados por todos os membros da autoridade possam ser descriptografados.

Os Blocos de Construção da Encriptação Homomórfica

Existem três tipos de criptografia homomórfica: criptografia homomórfica parcial (PHE), criptografia homomórfica nivelada (LHE) e criptografia homomórfica completa (FHE). A criptografia homomórfica parcial permite apenas o cálculo de um conjunto restrito de funções (por exemplo, apenas uma soma, apenas funções lineares, apenas funções bilineares), enquanto a criptografia homomórfica nivelada e completa podem avaliar circuitos arbitrários, ou seja, funções cujos fluxos de controle são independentes de dados. Para LHE, os parâmetros criptográficos dependem da função e aumentam com a complexidade do circuito, resultando em textos cifrados e chaves maiores. Os esquemas FHE permitem, para um conjunto de parâmetros dados, e assim para um determinado tamanho de chave e texto cifrado, avaliar qualquer função que possa ser representada como um circuito com portas aritméticas ou binárias. Ou seja, ao contrário de LHE, mesmo que o circuito a ser avaliado cresça cada vez mais, os parâmetros do esquema (e chaves e textos cifrados) não aumentam.

Em outras palavras, quando a pergunta é se um determinado circuito de texto simples pode ser executado homomorficamente e a que custo (em sobrecarga de tempo e memória), a criptografia homomórfica parcial (PHE) pode responder que não à pergunta. A criptografia homomórfica limitada (LHE) responde que sim, mas pode definir um custo arbitrariamente alto para circuitos complexos. A criptografia homomórfica completa (FHE) também responde que sim e, além disso, fornece as chaves, algoritmos de criptografia e decodificação e como avaliar homomorficamente um conjunto universal de Gates antes mesmo de especificar o circuito de texto simples. Portanto, a FHE é o único modo que garante que a memória e o tempo de execução da avaliação homomórfica permaneçam proporcionais ao circuito de texto simples original. Para fazer isso, todos os esquemas de FHE conhecidos hoje lidam com textos cifrados ruidosos que ficam cada vez mais ruidosos à medida que as computações são feitas. Para evitar que o ruído transborde para a computação realizada e leve a erros de decodificação, esses esquemas realizam regularmente uma operação bastante custosa chamada inicialização, que reduz o ruído a um nível gerenciável. Mais informações sobre os detalhes específicos de cada tipo de esquema, sobre a inicialização e sobre como minimizar o ruído e outros custos com compiladores FHE, no segundo post desta série!

Disclaimer：

1. Este artigo é republicado a partir de [cryptographycaffe], Todos os direitos autorais pertencem ao autor original [Nicolas Gama e Sandra Guasch]. Se houver objeções a esta reimpressão, entre em contato com o Aprenda Gateequipe e eles vão lidar com isso prontamente.
2. Isenção de responsabilidade: As opiniões expressas neste artigo são exclusivamente do autor e não constituem qualquer conselho de investimento.
3. As traduções do artigo para outros idiomas são feitas pela equipe Gate Learn. A menos que mencionado, copiar, distribuir ou plagiar os artigos traduzidos é proibido.