Fiz o curso CS355 (Criptografia Avançada) em Stanford há algum tempo. Fomos ensinados por três alunos de doutorado de Dan, Dima Kogan, Florian Tramer e Saba Eskandarian. Cada um dos três professores doutores tem características próprias e as suas direções de investigação também são muito diferentes. Dima se concentra na tecnologia de proteção de privacidade PIR (Private Information Retri), Florian se concentra na pesquisa de ML e blockchain e Saba se concentra na prova de conhecimento zero.
O curso CS355 cobre quase todo o conteúdo da área de criptografia desde os tempos antigos até o presente. Da primeira função unidirecional (função unidirecional), às equações elípticas (ECC) e emparelhamento e, finalmente, a alguns dos mais populares MPC, conhecimento zero, recuperação de informações privadas (PIR), algoritmos totalmente homomórficos, etc. nos últimos anos. Como a aula terminou há dois dias, organizei uma série de anotações enquanto o conteúdo do conhecimento ainda estava na minha memória superficial. O conteúdo do curso é muito interessante, compartilharei o resto do conteúdo com vocês mais tarde, quando tiver tempo ~
Nesta edição, falaremos sobre a recentemente popular criptografia totalmente homomórfica (FHE) e a tecnologia de criptografia baseada em rede que a acompanha.
O que é criptografia totalmente homomórfica?
Acredito que muitos amigos já ouviram falar do nome Criptografia Totalmente Homomórfica (FHE). Nos últimos anos, tem havido cada vez mais tópicos sobre proteção da privacidade pessoal, e uma série de tecnologias de aplicação de criptografia, incluindo a criptografia homomórfica, também foram amplamente popularizadas.
Para entender melhor este tópico, gostaria de apresentar brevemente a definição de criptografia totalmente homomórfica.
Revisão do sistema de criptografia
Antes de começarmos, vamos revisar o sistema de criptografia mais tradicional.
Todos nós sabemos que se você deseja construir um sistema de criptografia, muitas vezes precisa de uma chave. Por meio dessa chave, podemos criptografar as informações do texto simples em texto cifrado em uma extremidade e, em seguida, usar a chave para alterar o texto cifrado de volta à sua aparência original na outra extremidade. Sem esta Chave, seria difícil que outras pessoas soubessem quais informações passamos.
A ilustração acima mostra basicamente o panorama geral de todos os sistemas de criptografia comuns. Todos os sistemas de criptografia, se usarmos um método de descrição mais formal, sem dúvida fazem três coisas:
Amigos que sabem algo sobre algoritmos de criptografia certamente conhecerão os comuns. algoritmos de criptografia, como AES, RSA, etc. Todos também devem saber que, de modo geral, os sistemas de criptografia são divididos em dois tipos: sistemas de criptografia simétrica e sistemas de criptografia assimétrica. As três etapas que descrevemos aqui são aplicáveis a qualquer sistema de criptografia. Se for simétrico, a chave usada para criptografia e descriptografia é a mesma. Se for um sistema assimétrico, a chave pública será usada para criptografia e uma chave privada diferente será usada para descriptografia.
Na pesquisa em criptografia, sempre que vemos a definição de um novo sistema, muitas vezes temos que indicar as propriedades que o sistema deveria ter.
O principal significado da segurança semântica é que um observador não consegue distinguir entre duas mensagens criptografadas. Portanto, se um invasor espionar a rede e vir as informações criptografadas que envio, desde que o sistema de criptografia que utilizo seja semanticamente seguro, posso ter certeza de que o invasor não poderá obter nenhuma informação sobre o conteúdo criptografado do texto cifrado.
Depois de satisfazer as duas propriedades acima, um sistema de criptografia torna-se sólido.
Depois de entender do que se trata o sistema de criptografia, podemos prestar atenção a esse texto cifrado que se parece com um código ilegível gerado aleatoriamente. Todos sabemos que não obteremos nenhuma informação apenas olhando o próprio texto cifrado. Mas isso significa que se não houver chave e apenas texto cifrado, não poderemos fazer nada?
Todos nós sabemos a resposta: na verdade não.
Para esta propriedade chamamos de homomorfismo aditivo. Isso significa que o texto cifrado criptografado mantém uma relação algébrica sutil com o texto original anterior. Se somarmos o texto cifrado, podemos obter o novo texto cifrado que é criptografado somando o texto original. Da mesma forma, pode-se concluir que também existem algoritmos de criptografia aditivamente homomórficos. Podemos multiplicar o texto cifrado gerado por um algoritmo multiplicativamente homomórfico e então obter o texto cifrado correspondente ao resultado da multiplicação dos textos originais. Em todo o processo, não precisamos saber nenhuma informação relacionada à chave, apenas combinamos o texto cifrado que se parece com um código ilegível aleatório.
Por exemplo: Sistema de votação anônima
A seguir, vamos dar um exemplo para descrever vividamente a praticidade da criptografia homomórfica.
Todos nós sabemos como é a votação online – se o chefe de uma empresa quiser iniciar uma onda de votação, escolha se a empresa deve adotar o sistema 996. Em seguida, o chefe pode pedir ao departamento de TI para configurar um servidor e permitir que os funcionários enviem suas escolhas: vote 0 para significar que não querem, e vote 1 para significar que querem. Após o período final de votação, o chefe pode somar todos os votos. Se o total final de todos os votos ultrapassar a metade do número de funcionários, a empresa começará com 996.
Este mecanismo de votação parece muito simples, mas há uma grande questão de privacidade: se o chefe quer que todos os funcionários sejam 996, mas ele apenas inicia deliberadamente essa votação para pescar a aplicação da lei para ver qual funcionário não está disposto a fazer horas extras, então o chefe pode silenciosamente Ele confiou a seu irmão mais novo para espionar a Internet, registrar as escolhas enviadas por cada funcionário e, finalmente, ver quem votou 0. Como resultado, os funcionários ficam com muito medo e não ousam expressar seus sentimentos.
Se pudermos usar um algoritmo de criptografia homomórfica aditiva, esse problema poderá ser facilmente resolvido.
Claro, este sistema ainda está muito incompleto, por exemplo, o departamento de TI pode ajudar diretamente o chefe a descriptografar os votos de todos e registrá-los em um documento. Existem outras ferramentas criptográficas que podem nos ajudar a resolver este problema. Por questões de espaço, nenhuma explicação adicional será dada aqui.
Mas neste ponto, deveríamos ser capazes de sentir o poder do algoritmo de criptografia homomórfica. Podemos entender desta forma: através do algoritmo de criptografia homomórfica, os usuários podem realizar algum tipo de computação proxy segura (Secure Delegated Computation) com um servidor remoto não confiável (nuvem). Os usuários podem usar a tecnologia de criptografia homomórfica para criptografar suas entradas privadas confidenciais e confiá-las à nuvem.Em seguida, a nuvem pode realizar um certo grau de cálculo nos dados criptografados e, finalmente, obter o resultado criptografado que o usuário deseja e devolvê-lo ao nuvem.usuário. Finalmente, o usuário pode usar a chave de descriptografia para abrir o resultado. Durante todo o acordo, a parte delegada (a nuvem) nunca consegue ver nenhuma informação útil relacionada à entrada privada.
### Classificação de sistemas de criptografia homomórfica
Depois de compreender aproximadamente as duas propriedades homomórficas mais básicas, outros conceitos tornam-se muito fáceis de entender. De uma perspectiva sistemática, os sistemas de criptografia homomórfica são divididos aproximadamente em quatro categorias: homomorfismo parcial, homomorfismo aproximado, homomorfismo completo de séries finitas e homomorfismo completo.
A seguir, vamos dar uma olhada nas definições específicas de cada categoria.
Criptografia Parcialmente Homomórfica
O estágio mais elementar da criptografia homomórfica é chamado de criptografia parcialmente homomórfica, que é definida como o texto cifrado que possui apenas uma propriedade homomórfica. Este estágio inclui os dois modos de homomorfismo aditivo e homomorfismo multiplicativo que descrevemos acima.
Obtemos o texto cifrado correspondente à multiplicação dessas duas mensagens! Esta é a propriedade do homomorfismo multiplicativo.Podemos continuar a sobrepor novos textos cifrados sobre este texto cifrado, para que possamos obter qualquer multiplicação entre textos cifrados.
Criptografia homomórfica aproximada (criptografia um tanto homomórfica)
Como dissemos no parágrafo anterior, se quisermos multiplicar as entradas privadas e obter uma combinação linear entre elas, um algoritmo simples de criptografia parcialmente homomórfica (RSA, ElGamal) não pode ser concluído. Portanto, precisamos passar para a próxima fase.
O próximo estágio da criptografia parcialmente homomórfica é a criptografia aproximadamente homomórfica, que está um passo mais perto da criptografia totalmente homomórfica que queremos alcançar. Se tivermos um algoritmo de criptografia aproximadamente homomórfico, poderemos calcular adição e multiplicação no texto cifrado ao mesmo tempo. No entanto, deve-se notar que, como este estágio é aproximadamente homomórfico (um pouco homomórfico), o número de adições e multiplicações que podem ser feitas é muito limitado, e a função F que pode ser calculada também está dentro de um intervalo limitado.
Não há muitos exemplos comuns de criptografia aproximadamente homomórfica neste estágio. Se dissermos o exemplo mais bem compreendido, deveria ser o algoritmo de criptografia de grupo cíclico baseado no emparelhamento.
Acima discutimos brevemente o algoritmo de criptografia ElGamal baseado em grupos cíclicos comuns. Todos sabemos que este algoritmo é aditivamente homomórfico, o que significa que pode obter combinações lineares entre textos cifrados arbitrários. Na verdade, em alguns grupos cíclicos especiais, também podemos encontrar algumas propriedades fracas de homomorfismo multiplicativo.
Esta limitação prova que o sistema é aproximadamente homomórfico, uma vez que não podemos calcular a função F de lógica e profundidade arbitrárias.
Criptografia homomórfica totalmente nivelada
Depois de alcançar o próximo estágio, estamos um passo mais perto do objetivo do homomorfismo completo.
Este estágio é chamado de criptografia totalmente homomórfica de série finita. Nesta fase, já podemos realizar qualquer combinação de adição e multiplicação no texto cifrado sem qualquer limitação no número de vezes.
Criptografia Totalmente Homomórfica (FHE)
Depois de muitas ligações, finalmente chegamos à criptografia totalmente homomórfica (FHE) que estamos esperando para ver.
Como o nome diz, um sistema de criptografia totalmente homomórfico não tem restrições aos métodos de cálculo. Podemos combinar arbitrariamente textos cifrados para formar novos textos cifrados sem chave, e o novo texto cifrado, independentemente da complexidade computacional, pode ser perfeitamente restaurado ao texto original.
Quando chegamos a este estágio, o cálculo do agente seguro mencionado anteriormente torna-se viável. Se conseguirmos encontrar um sistema de criptografia totalmente homomórfico mais eficiente, poderemos fazer proxy com segurança de todos os cálculos locais para a nuvem sem vazar nenhum dado!
Definição de sistema de criptografia totalmente homomórfico
Antes de iniciar a discussão da história dos sistemas totalmente homomórficos abaixo, podemos definir sistematicamente a definição formal de sistemas totalmente homomórficos. Um sistema de criptografia totalmente homomórfico possui um total de quatro algoritmos:
## Revisão histórica da criptografia totalmente homomórfica
Antes de começar a aprender como o algoritmo de criptografia totalmente homomórfica é implementado, podemos também dar uma olhada em como surgiu o conceito de criptografia totalmente homomórfica.
O conceito de FHE (totalmente homomórfico) foi proposto no final da década de 1970. Em 1978, Rivest, Adleman e Dertouzos, vários grandes nomes da criptografia, mencionaram pela primeira vez em seu artigo On Data Banks and Privacy Homomorphisms a ideia de um sistema que pode realizar certos cálculos no texto cifrado e operar indiretamente no texto original. Mais tarde, essa ideia foi resumida e denominada criptografia totalmente homomórfica.
Percebe-se que o conceito de criptografia totalmente homomórfica já é proposto há muito tempo. Surpreendentemente, em 1976, dois anos antes da publicação do artigo, o protocolo de troca de chaves Diffle-Hellman acabara de ser proposto! Isto mostra que a imaginação dos especialistas em criptografia ainda é muito rica.
Quando o conceito de FHE foi proposto, toda a comunidade acadêmica foi movida por ele e iniciou uma busca de décadas, tentando encontrar um algoritmo perfeito com propriedades totalmente homomórficas. Mas ao longo das últimas décadas, as pessoas tentaram todas as opções imagináveis, mas não conseguem encontrar uma opção que satisfaça todas as condições de ser totalmente homomórfica e cuja segurança possa ser facilmente comprovada.
Até 2009, o PhD Craig Gentry, que estudava em Stanford, de repente teve uma ideia e superou as dificuldades do algoritmo FHE. Em sua tese de doutorado, ele apresentou pela primeira vez um sistema de criptografia totalmente homomórfico razoável e seguro! Este sistema é baseado na suposição de rede ideal. O sistema totalmente homomórfico proposto por Gentry09 é frequentemente chamado de sistema de criptografia totalmente homomórfico de primeira geração.
No artigo de Gentry, ele também mencionou um conceito crucial chamado Bootstrapping. Bootstrapping é uma técnica especial de processamento de texto cifrado que, após o processamento, pode "atualizar" um texto cifrado com ruído próximo ao valor crítico em um novo texto cifrado com ruído muito baixo. Através do Bootstrapping, o ruído de um sistema em série finita nunca pode exceder o valor crítico, tornando-se assim um sistema totalmente homomórfico. Desta forma, podemos calcular homomorficamente F de qualquer tamanho.
Após o grande avanço de Gentry, todo o círculo criptográfico caiu na loucura novamente, e todos começaram a lutar para encontrar um sistema totalmente homomórfico mais eficiente e versátil baseado nas ideias propostas por Gentry.
Em 2011, dois grandes nomes, Brakerski e Vaikuntanathan, propuseram um novo sistema de criptografia totalmente homomórfico, baseado em Aprendizagem com Erros (LWE), outra suposição da criptografia em rede. No mesmo ano, Brakerski, Gentry e Vaikuntanathan completaram o sistema e publicaram-no oficialmente. O sistema totalmente homomórfico que eles inventaram é chamado, abreviadamente, de sistema BGV. O sistema BGV é um sistema de criptografia homomórfica de nível limitado, mas pode ser transformado em um sistema totalmente homomórfico através do Bootstrapping. Comparado com o sistema proposto por Gentry09, o sistema BGV utiliza uma suposição de LWE mais realista. De modo geral, chamamos o sistema BGV de sistema de criptografia totalmente homomórfico de segunda geração.
Em 2013, Gentry voltou. Gentry, Sahai e Waters lançaram um novo sistema de criptografia GSW totalmente homomórfico. O sistema GSW é semelhante ao BGV por possuir séries finitas com propriedades totalmente homomórficas. É baseado na suposição LWE mais simples e pode ser totalmente homomórfico por meio de Bootstrapping. Geralmente nos referimos ao sistema GSW como o sistema de criptografia totalmente homomórfico de terceira geração.
Depois de 2013, a criptosfera basicamente floresceu. Com base no sistema original totalmente homomórfico de três gerações, surgiram vários novos projetos, dedicados a otimizar e acelerar a eficiência operacional dos sistemas BGV e GSW. A IBM desenvolveu uma biblioteca de computação HElib de código aberto totalmente homomórfica baseada no sistema BGV e a transplantou com sucesso para as principais plataformas móveis. Ao mesmo tempo, há outro projeto de código aberto TFHE que também merece destaque. TFHE é baseado no sistema GSW, com diversas otimizações e acelerações adicionadas, e hoje é muito famoso.
Além de desenvolver bibliotecas tradicionais totalmente homomórficas, muitas equipes também estão estudando como acelerar melhor o cálculo de algoritmos de criptografia totalmente homomórficos por meio de hardware heterogêneo, como GPU, FPGA e ASIC. Por exemplo, cuFHE é um conhecido sistema de criptografia totalmente homomórfico baseado em CUDA e acelerado por GPU.
Da perspectiva de hoje, já se passaram 11 anos desde que Gentry bateu à porta do sistema totalmente homomórfico. Hoje em dia, a pesquisa sobre FHE está crescendo na indústria e muitas pessoas estão estudando sistemas totalmente homomórficos sob diferentes perspectivas e requisitos de aplicação. Até hoje, já temos uma variedade de métodos viáveis de implementação do FHE, mas o que todos ainda buscam é a eficiência da operação do sistema FHE. Tomando como exemplo a atual biblioteca FHE de última geração, o cálculo homomórfico de alguma lógica relativamente simples em uma plataforma móvel pode levar pelo menos dezenas de milissegundos e até dezenas de segundos. Essas unidades de tempo são extremamente lentas para sistemas de computador.
Como fazer com que o sistema FHE funcione de forma mais eficiente em plataformas heterogêneas ainda é um mistério sem solução. Se esse problema for resolvido, converter todos os cálculos do computador para totalmente homomórficos e fazer com que os agentes realizem cálculos em nuvens de terceiros será um futuro fácil.
A relação entre FHE e MPC
Antes de encerrar o artigo, gostaria de acrescentar algumas palavras sobre a relação entre FHE e MPC. MPC significa Secure Multi-Party Computation, que é computação multipartidária confiável. Geralmente significa que várias partes têm suas próprias entradas privadas e não querem divulgá-las a terceiros, mas desejam usar suas próprias entradas para calcular uma função F em conjunto e compartilhar os resultados do cálculo.
MPC é na verdade um campo muito conhecido e estudado há muito tempo. Desde que o criptógrafo Yao Qizhi lançou seus circuitos ilegíveis no século passado, o campo do MPC ganhou amplo reconhecimento e houve muitos avanços. Agora já temos muitas bibliotecas MPC que podem ser utilizadas, e elas também apresentam certa eficiência operacional.
Amigos que conhecem o MPC podem ter muitas perguntas depois de ver a difícil história dos sistemas de criptografia totalmente homomórficos: Por que a criptografia totalmente homomórfica não pode ser substituída diretamente por um protocolo MPC?
Na verdade, um protocolo MPC pode substituir completamente um protocolo FHE. Precisamos apenas usar o usuário e a entrada privada como parte de um protocolo e, em seguida, usar o servidor de computação proxy remoto como outra parte, que atenda às condições para a execução do protocolo MPC. Somente por meio de certas interações, a computação proxy pode ser realizado.E o servidor não pode ver a entrada privada.
Mas há um ponto muito importante que negligenciamos: como o MPC é interativo, o usuário e o servidor precisam calcular e se comunicar juntos para completar o protocolo. Isto entra em conflito com o requisito mais fundamental da computação de agentes FHE. Se o usuário precisa ficar online o tempo todo para concluir o contrato e também pagar parte do poder computacional, então na verdade o cálculo não é "proxy" de forma alguma, e ambas as partes estão apenas fazendo mais cálculos por uma questão de segurança da informação . Isto também explica porque o campo do MPC fez grandes avanços, mas o campo do FHE ainda é desconhecido, porque os dois sistemas resolvem problemas completamente diferentes.
## Próxima parada: sistema de criptografia GSW totalmente homomórfico
Vendo isso, todos devem ter um conhecimento profundo do sistema de criptografia totalmente homomórfico.
Na próxima parada, podemos aprender sobre o sistema de criptografia totalmente homomórfica GSW mencionado acima. Embora esta seja a terceira geração de sistemas totalmente homomórficos, penso que entre os três sistemas de Gentry09, BGV e GSW, o GSW é aquele com menos suposições, a estrutura mais simples e mais fácil de entender. E agora existem muitas bibliotecas de código aberto (como TFHE) construídas com base no sistema GSW.
Por questões de espaço, encerraremos este artigo aqui. No próximo artigo, podemos primeiro aprender o básico do sistema GSW: o sistema de criptografia baseado em rede e o problema LWE. Uma vez compreendido o problema do LWE, o problema que o GSW resolve torna-se muito claro.
Ver original
Esta página pode conter conteúdos de terceiros, que são fornecidos apenas para fins informativos (sem representações/garantias) e não devem ser considerados como uma aprovação dos seus pontos de vista pela Gate, nem como aconselhamento financeiro ou profissional. Consulte a Declaração de exoneração de responsabilidade para obter mais informações.
Uma exploração preliminar da criptografia totalmente homomórfica: a definição e revisão histórica do FHE
Autor: Steven Yue
Fiz o curso CS355 (Criptografia Avançada) em Stanford há algum tempo. Fomos ensinados por três alunos de doutorado de Dan, Dima Kogan, Florian Tramer e Saba Eskandarian. Cada um dos três professores doutores tem características próprias e as suas direções de investigação também são muito diferentes. Dima se concentra na tecnologia de proteção de privacidade PIR (Private Information Retri), Florian se concentra na pesquisa de ML e blockchain e Saba se concentra na prova de conhecimento zero.
O curso CS355 cobre quase todo o conteúdo da área de criptografia desde os tempos antigos até o presente. Da primeira função unidirecional (função unidirecional), às equações elípticas (ECC) e emparelhamento e, finalmente, a alguns dos mais populares MPC, conhecimento zero, recuperação de informações privadas (PIR), algoritmos totalmente homomórficos, etc. nos últimos anos. Como a aula terminou há dois dias, organizei uma série de anotações enquanto o conteúdo do conhecimento ainda estava na minha memória superficial. O conteúdo do curso é muito interessante, compartilharei o resto do conteúdo com vocês mais tarde, quando tiver tempo ~
Nesta edição, falaremos sobre a recentemente popular criptografia totalmente homomórfica (FHE) e a tecnologia de criptografia baseada em rede que a acompanha.
O que é criptografia totalmente homomórfica?
Acredito que muitos amigos já ouviram falar do nome Criptografia Totalmente Homomórfica (FHE). Nos últimos anos, tem havido cada vez mais tópicos sobre proteção da privacidade pessoal, e uma série de tecnologias de aplicação de criptografia, incluindo a criptografia homomórfica, também foram amplamente popularizadas.
Para entender melhor este tópico, gostaria de apresentar brevemente a definição de criptografia totalmente homomórfica.
Revisão do sistema de criptografia
Antes de começarmos, vamos revisar o sistema de criptografia mais tradicional.
Todos nós sabemos que se você deseja construir um sistema de criptografia, muitas vezes precisa de uma chave. Por meio dessa chave, podemos criptografar as informações do texto simples em texto cifrado em uma extremidade e, em seguida, usar a chave para alterar o texto cifrado de volta à sua aparência original na outra extremidade. Sem esta Chave, seria difícil que outras pessoas soubessem quais informações passamos.
Na pesquisa em criptografia, sempre que vemos a definição de um novo sistema, muitas vezes temos que indicar as propriedades que o sistema deveria ter.
O principal significado da segurança semântica é que um observador não consegue distinguir entre duas mensagens criptografadas. Portanto, se um invasor espionar a rede e vir as informações criptografadas que envio, desde que o sistema de criptografia que utilizo seja semanticamente seguro, posso ter certeza de que o invasor não poderá obter nenhuma informação sobre o conteúdo criptografado do texto cifrado.
Depois de satisfazer as duas propriedades acima, um sistema de criptografia torna-se sólido.
Depois de entender do que se trata o sistema de criptografia, podemos prestar atenção a esse texto cifrado que se parece com um código ilegível gerado aleatoriamente. Todos sabemos que não obteremos nenhuma informação apenas olhando o próprio texto cifrado. Mas isso significa que se não houver chave e apenas texto cifrado, não poderemos fazer nada?
Todos nós sabemos a resposta: na verdade não.
Para esta propriedade chamamos de homomorfismo aditivo. Isso significa que o texto cifrado criptografado mantém uma relação algébrica sutil com o texto original anterior. Se somarmos o texto cifrado, podemos obter o novo texto cifrado que é criptografado somando o texto original. Da mesma forma, pode-se concluir que também existem algoritmos de criptografia aditivamente homomórficos. Podemos multiplicar o texto cifrado gerado por um algoritmo multiplicativamente homomórfico e então obter o texto cifrado correspondente ao resultado da multiplicação dos textos originais. Em todo o processo, não precisamos saber nenhuma informação relacionada à chave, apenas combinamos o texto cifrado que se parece com um código ilegível aleatório.
Por exemplo: Sistema de votação anônima
A seguir, vamos dar um exemplo para descrever vividamente a praticidade da criptografia homomórfica.
Todos nós sabemos como é a votação online – se o chefe de uma empresa quiser iniciar uma onda de votação, escolha se a empresa deve adotar o sistema 996. Em seguida, o chefe pode pedir ao departamento de TI para configurar um servidor e permitir que os funcionários enviem suas escolhas: vote 0 para significar que não querem, e vote 1 para significar que querem. Após o período final de votação, o chefe pode somar todos os votos. Se o total final de todos os votos ultrapassar a metade do número de funcionários, a empresa começará com 996.
Este mecanismo de votação parece muito simples, mas há uma grande questão de privacidade: se o chefe quer que todos os funcionários sejam 996, mas ele apenas inicia deliberadamente essa votação para pescar a aplicação da lei para ver qual funcionário não está disposto a fazer horas extras, então o chefe pode silenciosamente Ele confiou a seu irmão mais novo para espionar a Internet, registrar as escolhas enviadas por cada funcionário e, finalmente, ver quem votou 0. Como resultado, os funcionários ficam com muito medo e não ousam expressar seus sentimentos.
Se pudermos usar um algoritmo de criptografia homomórfica aditiva, esse problema poderá ser facilmente resolvido.
Claro, este sistema ainda está muito incompleto, por exemplo, o departamento de TI pode ajudar diretamente o chefe a descriptografar os votos de todos e registrá-los em um documento. Existem outras ferramentas criptográficas que podem nos ajudar a resolver este problema. Por questões de espaço, nenhuma explicação adicional será dada aqui.
Mas neste ponto, deveríamos ser capazes de sentir o poder do algoritmo de criptografia homomórfica. Podemos entender desta forma: através do algoritmo de criptografia homomórfica, os usuários podem realizar algum tipo de computação proxy segura (Secure Delegated Computation) com um servidor remoto não confiável (nuvem). Os usuários podem usar a tecnologia de criptografia homomórfica para criptografar suas entradas privadas confidenciais e confiá-las à nuvem.Em seguida, a nuvem pode realizar um certo grau de cálculo nos dados criptografados e, finalmente, obter o resultado criptografado que o usuário deseja e devolvê-lo ao nuvem.usuário. Finalmente, o usuário pode usar a chave de descriptografia para abrir o resultado. Durante todo o acordo, a parte delegada (a nuvem) nunca consegue ver nenhuma informação útil relacionada à entrada privada.
Depois de compreender aproximadamente as duas propriedades homomórficas mais básicas, outros conceitos tornam-se muito fáceis de entender. De uma perspectiva sistemática, os sistemas de criptografia homomórfica são divididos aproximadamente em quatro categorias: homomorfismo parcial, homomorfismo aproximado, homomorfismo completo de séries finitas e homomorfismo completo.
A seguir, vamos dar uma olhada nas definições específicas de cada categoria.
Criptografia Parcialmente Homomórfica
O estágio mais elementar da criptografia homomórfica é chamado de criptografia parcialmente homomórfica, que é definida como o texto cifrado que possui apenas uma propriedade homomórfica. Este estágio inclui os dois modos de homomorfismo aditivo e homomorfismo multiplicativo que descrevemos acima.
Obtemos o texto cifrado correspondente à multiplicação dessas duas mensagens! Esta é a propriedade do homomorfismo multiplicativo.Podemos continuar a sobrepor novos textos cifrados sobre este texto cifrado, para que possamos obter qualquer multiplicação entre textos cifrados.
Criptografia homomórfica aproximada (criptografia um tanto homomórfica)
Como dissemos no parágrafo anterior, se quisermos multiplicar as entradas privadas e obter uma combinação linear entre elas, um algoritmo simples de criptografia parcialmente homomórfica (RSA, ElGamal) não pode ser concluído. Portanto, precisamos passar para a próxima fase.
O próximo estágio da criptografia parcialmente homomórfica é a criptografia aproximadamente homomórfica, que está um passo mais perto da criptografia totalmente homomórfica que queremos alcançar. Se tivermos um algoritmo de criptografia aproximadamente homomórfico, poderemos calcular adição e multiplicação no texto cifrado ao mesmo tempo. No entanto, deve-se notar que, como este estágio é aproximadamente homomórfico (um pouco homomórfico), o número de adições e multiplicações que podem ser feitas é muito limitado, e a função F que pode ser calculada também está dentro de um intervalo limitado.
Não há muitos exemplos comuns de criptografia aproximadamente homomórfica neste estágio. Se dissermos o exemplo mais bem compreendido, deveria ser o algoritmo de criptografia de grupo cíclico baseado no emparelhamento.
Acima discutimos brevemente o algoritmo de criptografia ElGamal baseado em grupos cíclicos comuns. Todos sabemos que este algoritmo é aditivamente homomórfico, o que significa que pode obter combinações lineares entre textos cifrados arbitrários. Na verdade, em alguns grupos cíclicos especiais, também podemos encontrar algumas propriedades fracas de homomorfismo multiplicativo.
Esta limitação prova que o sistema é aproximadamente homomórfico, uma vez que não podemos calcular a função F de lógica e profundidade arbitrárias.
Criptografia homomórfica totalmente nivelada
Depois de alcançar o próximo estágio, estamos um passo mais perto do objetivo do homomorfismo completo.
Este estágio é chamado de criptografia totalmente homomórfica de série finita. Nesta fase, já podemos realizar qualquer combinação de adição e multiplicação no texto cifrado sem qualquer limitação no número de vezes.
Criptografia Totalmente Homomórfica (FHE)
Depois de muitas ligações, finalmente chegamos à criptografia totalmente homomórfica (FHE) que estamos esperando para ver.
Como o nome diz, um sistema de criptografia totalmente homomórfico não tem restrições aos métodos de cálculo. Podemos combinar arbitrariamente textos cifrados para formar novos textos cifrados sem chave, e o novo texto cifrado, independentemente da complexidade computacional, pode ser perfeitamente restaurado ao texto original.
Quando chegamos a este estágio, o cálculo do agente seguro mencionado anteriormente torna-se viável. Se conseguirmos encontrar um sistema de criptografia totalmente homomórfico mais eficiente, poderemos fazer proxy com segurança de todos os cálculos locais para a nuvem sem vazar nenhum dado!
Definição de sistema de criptografia totalmente homomórfico
Antes de iniciar a discussão da história dos sistemas totalmente homomórficos abaixo, podemos definir sistematicamente a definição formal de sistemas totalmente homomórficos. Um sistema de criptografia totalmente homomórfico possui um total de quatro algoritmos:
Antes de começar a aprender como o algoritmo de criptografia totalmente homomórfica é implementado, podemos também dar uma olhada em como surgiu o conceito de criptografia totalmente homomórfica.
O conceito de FHE (totalmente homomórfico) foi proposto no final da década de 1970. Em 1978, Rivest, Adleman e Dertouzos, vários grandes nomes da criptografia, mencionaram pela primeira vez em seu artigo On Data Banks and Privacy Homomorphisms a ideia de um sistema que pode realizar certos cálculos no texto cifrado e operar indiretamente no texto original. Mais tarde, essa ideia foi resumida e denominada criptografia totalmente homomórfica.
Percebe-se que o conceito de criptografia totalmente homomórfica já é proposto há muito tempo. Surpreendentemente, em 1976, dois anos antes da publicação do artigo, o protocolo de troca de chaves Diffle-Hellman acabara de ser proposto! Isto mostra que a imaginação dos especialistas em criptografia ainda é muito rica.
Quando o conceito de FHE foi proposto, toda a comunidade acadêmica foi movida por ele e iniciou uma busca de décadas, tentando encontrar um algoritmo perfeito com propriedades totalmente homomórficas. Mas ao longo das últimas décadas, as pessoas tentaram todas as opções imagináveis, mas não conseguem encontrar uma opção que satisfaça todas as condições de ser totalmente homomórfica e cuja segurança possa ser facilmente comprovada.
Até 2009, o PhD Craig Gentry, que estudava em Stanford, de repente teve uma ideia e superou as dificuldades do algoritmo FHE. Em sua tese de doutorado, ele apresentou pela primeira vez um sistema de criptografia totalmente homomórfico razoável e seguro! Este sistema é baseado na suposição de rede ideal. O sistema totalmente homomórfico proposto por Gentry09 é frequentemente chamado de sistema de criptografia totalmente homomórfico de primeira geração.
No artigo de Gentry, ele também mencionou um conceito crucial chamado Bootstrapping. Bootstrapping é uma técnica especial de processamento de texto cifrado que, após o processamento, pode "atualizar" um texto cifrado com ruído próximo ao valor crítico em um novo texto cifrado com ruído muito baixo. Através do Bootstrapping, o ruído de um sistema em série finita nunca pode exceder o valor crítico, tornando-se assim um sistema totalmente homomórfico. Desta forma, podemos calcular homomorficamente F de qualquer tamanho.
Após o grande avanço de Gentry, todo o círculo criptográfico caiu na loucura novamente, e todos começaram a lutar para encontrar um sistema totalmente homomórfico mais eficiente e versátil baseado nas ideias propostas por Gentry.
Em 2011, dois grandes nomes, Brakerski e Vaikuntanathan, propuseram um novo sistema de criptografia totalmente homomórfico, baseado em Aprendizagem com Erros (LWE), outra suposição da criptografia em rede. No mesmo ano, Brakerski, Gentry e Vaikuntanathan completaram o sistema e publicaram-no oficialmente. O sistema totalmente homomórfico que eles inventaram é chamado, abreviadamente, de sistema BGV. O sistema BGV é um sistema de criptografia homomórfica de nível limitado, mas pode ser transformado em um sistema totalmente homomórfico através do Bootstrapping. Comparado com o sistema proposto por Gentry09, o sistema BGV utiliza uma suposição de LWE mais realista. De modo geral, chamamos o sistema BGV de sistema de criptografia totalmente homomórfico de segunda geração.
Em 2013, Gentry voltou. Gentry, Sahai e Waters lançaram um novo sistema de criptografia GSW totalmente homomórfico. O sistema GSW é semelhante ao BGV por possuir séries finitas com propriedades totalmente homomórficas. É baseado na suposição LWE mais simples e pode ser totalmente homomórfico por meio de Bootstrapping. Geralmente nos referimos ao sistema GSW como o sistema de criptografia totalmente homomórfico de terceira geração.
Depois de 2013, a criptosfera basicamente floresceu. Com base no sistema original totalmente homomórfico de três gerações, surgiram vários novos projetos, dedicados a otimizar e acelerar a eficiência operacional dos sistemas BGV e GSW. A IBM desenvolveu uma biblioteca de computação HElib de código aberto totalmente homomórfica baseada no sistema BGV e a transplantou com sucesso para as principais plataformas móveis. Ao mesmo tempo, há outro projeto de código aberto TFHE que também merece destaque. TFHE é baseado no sistema GSW, com diversas otimizações e acelerações adicionadas, e hoje é muito famoso.
Além de desenvolver bibliotecas tradicionais totalmente homomórficas, muitas equipes também estão estudando como acelerar melhor o cálculo de algoritmos de criptografia totalmente homomórficos por meio de hardware heterogêneo, como GPU, FPGA e ASIC. Por exemplo, cuFHE é um conhecido sistema de criptografia totalmente homomórfico baseado em CUDA e acelerado por GPU.
Da perspectiva de hoje, já se passaram 11 anos desde que Gentry bateu à porta do sistema totalmente homomórfico. Hoje em dia, a pesquisa sobre FHE está crescendo na indústria e muitas pessoas estão estudando sistemas totalmente homomórficos sob diferentes perspectivas e requisitos de aplicação. Até hoje, já temos uma variedade de métodos viáveis de implementação do FHE, mas o que todos ainda buscam é a eficiência da operação do sistema FHE. Tomando como exemplo a atual biblioteca FHE de última geração, o cálculo homomórfico de alguma lógica relativamente simples em uma plataforma móvel pode levar pelo menos dezenas de milissegundos e até dezenas de segundos. Essas unidades de tempo são extremamente lentas para sistemas de computador.
Como fazer com que o sistema FHE funcione de forma mais eficiente em plataformas heterogêneas ainda é um mistério sem solução. Se esse problema for resolvido, converter todos os cálculos do computador para totalmente homomórficos e fazer com que os agentes realizem cálculos em nuvens de terceiros será um futuro fácil.
A relação entre FHE e MPC
Antes de encerrar o artigo, gostaria de acrescentar algumas palavras sobre a relação entre FHE e MPC. MPC significa Secure Multi-Party Computation, que é computação multipartidária confiável. Geralmente significa que várias partes têm suas próprias entradas privadas e não querem divulgá-las a terceiros, mas desejam usar suas próprias entradas para calcular uma função F em conjunto e compartilhar os resultados do cálculo.
MPC é na verdade um campo muito conhecido e estudado há muito tempo. Desde que o criptógrafo Yao Qizhi lançou seus circuitos ilegíveis no século passado, o campo do MPC ganhou amplo reconhecimento e houve muitos avanços. Agora já temos muitas bibliotecas MPC que podem ser utilizadas, e elas também apresentam certa eficiência operacional.
Amigos que conhecem o MPC podem ter muitas perguntas depois de ver a difícil história dos sistemas de criptografia totalmente homomórficos: Por que a criptografia totalmente homomórfica não pode ser substituída diretamente por um protocolo MPC?
Na verdade, um protocolo MPC pode substituir completamente um protocolo FHE. Precisamos apenas usar o usuário e a entrada privada como parte de um protocolo e, em seguida, usar o servidor de computação proxy remoto como outra parte, que atenda às condições para a execução do protocolo MPC. Somente por meio de certas interações, a computação proxy pode ser realizado.E o servidor não pode ver a entrada privada.
Mas há um ponto muito importante que negligenciamos: como o MPC é interativo, o usuário e o servidor precisam calcular e se comunicar juntos para completar o protocolo. Isto entra em conflito com o requisito mais fundamental da computação de agentes FHE. Se o usuário precisa ficar online o tempo todo para concluir o contrato e também pagar parte do poder computacional, então na verdade o cálculo não é "proxy" de forma alguma, e ambas as partes estão apenas fazendo mais cálculos por uma questão de segurança da informação . Isto também explica porque o campo do MPC fez grandes avanços, mas o campo do FHE ainda é desconhecido, porque os dois sistemas resolvem problemas completamente diferentes.
Vendo isso, todos devem ter um conhecimento profundo do sistema de criptografia totalmente homomórfico.
Na próxima parada, podemos aprender sobre o sistema de criptografia totalmente homomórfica GSW mencionado acima. Embora esta seja a terceira geração de sistemas totalmente homomórficos, penso que entre os três sistemas de Gentry09, BGV e GSW, o GSW é aquele com menos suposições, a estrutura mais simples e mais fácil de entender. E agora existem muitas bibliotecas de código aberto (como TFHE) construídas com base no sistema GSW.
Por questões de espaço, encerraremos este artigo aqui. No próximo artigo, podemos primeiro aprender o básico do sistema GSW: o sistema de criptografia baseado em rede e o problema LWE. Uma vez compreendido o problema do LWE, o problema que o GSW resolve torna-se muito claro.