Criptografia homomórfica - Homomorphic encryption

Criptografia homomórfica
Assinatura de anel.svg
Em geral
Derivado de Aprendizagem de anel com erros
Relacionado a

A criptografia homomórfica é uma forma de criptografia que permite aos usuários realizar cálculos em seus dados criptografados sem primeiro descriptografá-los. Esses cálculos resultantes são deixados em uma forma criptografada que, quando descriptografada, resulta em uma saída idêntica à produzida se as operações tivessem sido realizadas nos dados não criptografados. A criptografia homomórfica pode ser usada para armazenamento e computação terceirizados que preservam a privacidade . Isso permite que os dados sejam criptografados e terceirizados para ambientes comerciais em nuvem para processamento, tudo isso enquanto criptografados.

Para dados confidenciais, como informações de saúde, a criptografia homomórfica pode ser usada para habilitar novos serviços, removendo as barreiras de privacidade que inibem o compartilhamento de dados ou aumentando a segurança dos serviços existentes. Por exemplo, a análise preditiva em saúde pode ser difícil de aplicar por meio de um provedor de serviços terceirizado devido a questões de privacidade de dados médicos , mas se o provedor de serviços de análise preditiva puder operar com dados criptografados, essas preocupações com a privacidade serão reduzidas. Além disso, mesmo que o sistema do provedor de serviço seja comprometido, os dados permanecerão seguros.

Descrição

A criptografia homomórfica é uma forma de criptografia com uma capacidade de avaliação adicional para computação em dados criptografados sem acesso à chave secreta . O resultado de tal cálculo permanece criptografado. A criptografia homomórfica pode ser vista como uma extensão da criptografia de chave pública . Homomórfico refere-se ao homomorfismo na álgebra: as funções de criptografia e descriptografia podem ser pensadas como homomorfismos entre texto simples e espaços de texto cifrado.

A criptografia homomórfica inclui vários tipos de esquemas de criptografia que podem realizar diferentes classes de cálculos sobre dados criptografados. Os cálculos são representados como circuitos booleanos ou aritméticos. Alguns tipos comuns de criptografia homomórfica são parcialmente homomórfica, um tanto homomórfica, totalmente homomórfica nivelada e criptografia totalmente homomórfica:

  • A criptografia parcialmente homomórfica engloba esquemas que suportam a avaliação de circuitos que consistem em apenas um tipo de porta, por exemplo, adição ou multiplicação.
  • Esquemas de criptografia um tanto homomórficos podem avaliar dois tipos de portas, mas apenas para um subconjunto de circuitos.
  • A criptografia nivelada totalmente homomórfica suporta a avaliação de circuitos arbitrários compostos de vários tipos de portas de profundidade limitada (pré-determinada).
  • A criptografia totalmente homomórfica (FHE) permite a avaliação de circuitos arbitrários compostos de vários tipos de portas de profundidade ilimitada e é a noção mais forte de criptografia homomórfica.

Para a maioria dos esquemas de criptografia homomórfica, a profundidade multiplicativa dos circuitos é a principal limitação prática na realização de cálculos sobre dados criptografados. Os esquemas de criptografia homomórfica são inerentemente maleáveis . Em termos de maleabilidade, os esquemas de criptografia homomórficos têm propriedades de segurança mais fracas do que os esquemas não homomórficos.

História

Esquemas de criptografia homomórfica foram desenvolvidos usando diferentes abordagens. Especificamente, esquemas de criptografia totalmente homomórficos são frequentemente agrupados em gerações correspondentes à abordagem subjacente.

Pré-FHE

O problema de construir um esquema de criptografia totalmente homomórfico foi proposto pela primeira vez em 1978, um ano após a publicação do esquema RSA. Por mais de 30 anos, não estava claro se existia uma solução. Durante esse período, os resultados parciais incluíram os seguintes esquemas:

FHE de primeira geração

Craig Gentry , usando criptografia baseada em rede , descreveu a primeira construção plausível para um esquema de criptografia totalmente homomórfico. O esquema de Gentry suporta operações de adição e multiplicação em textos cifrados, a partir dos quais é possível construir circuitos para realizar computação arbitrária. A construção começa a partir de um esquema de criptografia um tanto homomórfico , que se limita a avaliar polinômios de baixo grau sobre dados criptografados; é limitado porque cada texto cifrado é barulhento em algum sentido, e esse ruído aumenta à medida que se adiciona e multiplica os textos cifrados, até que finalmente o ruído torna o texto cifrado resultante indecifrável.

Gentry então mostra como modificar ligeiramente esse esquema para torná-lo inicializável , ou seja, capaz de avaliar seu próprio circuito de descriptografia e, em seguida, pelo menos mais uma operação. Finalmente, ele mostra que qualquer esquema de criptografia um tanto homomórfico que pode ser inicializado pode ser convertido em uma criptografia totalmente homomórfica por meio de uma auto-incorporação recursiva. Para o esquema "ruidoso" de Gentry, o procedimento de bootstrapping efetivamente "atualiza" o texto cifrado aplicando-lhe o procedimento de descriptografia homomorficamente, obtendo assim um novo texto cifrado que criptografa o mesmo valor de antes, mas tem menos ruído. Ao "atualizar" o texto cifrado periodicamente sempre que o ruído fica muito grande, é possível calcular um número arbitrário de adições e multiplicações sem aumentar muito o ruído.

Gentry baseou a segurança de seu esquema na dureza assumida de dois problemas: certos problemas de pior caso sobre redes ideais e o problema da soma de subconjuntos esparsos (ou de baixo peso). Ph.D. de Gentry tese fornece detalhes adicionais. A implementação Gentry-Halevi do criptossistema original de Gentry relatou um tempo de cerca de 30 minutos por operação de bit básica. O extenso trabalho de design e implementação nos anos subsequentes melhorou essas implementações iniciais por meio do desempenho do tempo de execução de muitas ordens de magnitude.

Em 2010, Marten van Dijk, Craig Gentry , Shai Halevi e Vinod Vaikuntanathan apresentaram um segundo esquema de criptografia totalmente homomórfico, que usa muitas das ferramentas de construção de Gentry, mas que não requer redes ideais . Em vez disso, eles mostram que o componente um tanto homomórfico do esquema baseado em rede ideal de Gentry pode ser substituído por um esquema um tanto homomórfico muito simples que usa inteiros. O esquema é, portanto, conceitualmente mais simples do que o esquema de rede ideal de Gentry, mas tem propriedades semelhantes no que diz respeito a operações homomórficas e eficiência. O componente um tanto homomórfico no trabalho de Van Dijk et al. é semelhante a um esquema de criptografia proposto por Levieil e Naccache em 2008, e também a um que foi proposto por Bram Cohen em 1998.

O método de Cohen não é nem mesmo aditivamente homomórfico, entretanto. O esquema Levieil – Naccache suporta apenas adições, mas pode ser modificado para suportar também um pequeno número de multiplicações. Muitos refinamentos e otimizações do esquema de Van Dijk et al. foram propostas em uma sequência de obras de Jean-Sébastien Coron, Tancrède Lepoint, Avradip Mandal, David Naccache e Mehdi Tibouchi. Alguns desses trabalhos incluíram também implementações dos esquemas resultantes.

FHE de segunda geração

Os criptosistemas homomórficos desta geração são derivados de técnicas desenvolvidas a partir de 2011-2012 por Zvika Brakerski, Craig Gentry , Vinod Vaikuntanathan e outros. Essas inovações levaram ao desenvolvimento de criptosistemas um tanto mais eficientes e totalmente homomórficos. Esses incluem:

  • O esquema Brakerski-Gentry-Vaikuntanathan (BGV, 2011), com base nas técnicas de Brakerski-Vaikuntanathan;
  • O esquema baseado em NTRU de Lopez-Alt, Tromer e Vaikuntanathan (LTV, 2012);
  • O esquema de Brakerski / Fan-Vercauteren (BFV, 2012), baseado no criptossistema invariante de escala de Brakerski ;
  • O esquema baseado em NTRU por Bos, Lauter, Loftus e Naehrig (BLLN, 2013), baseado no LTV e no criptossistema invariante de escala de Brakerski;

A segurança da maioria desses esquemas é baseada na dureza do problema (Ring) Learning With Errors (RLWE), exceto para os esquemas LTV e BLLN que dependem de uma variante sobrecarregada do problema computacional NTRU . Esta variante NTRU foi posteriormente mostrada vulnerável a ataques de rede de subcampo, razão pela qual esses dois esquemas não são mais usados ​​na prática.

Todos os criptosistemas de segunda geração ainda seguem o projeto básico da construção original de Gentry, ou seja, eles primeiro constroem um criptosistema um tanto homomórfico e depois o convertem em um criptosistema totalmente homomórfico usando bootstrapping.

Uma característica distintiva dos criptossistemas de segunda geração é que todos eles apresentam um crescimento muito mais lento do ruído durante os cálculos homomórficos. Otimizações adicionais por Craig Gentry , Shai Halevi e Nigel Smart resultaram em sistemas criptográficos com complexidade assintótica quase ideal: A execução de operações em dados criptografados com parâmetro de segurança tem complexidade de apenas . Essas otimizações se baseiam nas técnicas Smart-Vercauteren, que permitem compactar muitos valores de texto simples em um único texto cifrado e operar em todos esses valores de texto simples de maneira SIMD . Muitos dos avanços nesses criptossistemas de segunda geração também foram transferidos para o criptossistema através de números inteiros.

Outra característica distintiva dos esquemas de segunda geração é que eles são eficientes o suficiente para muitos aplicativos, mesmo sem invocar a inicialização, em vez de operar no modo FHE nivelado.

FHE de terceira geração

Em 2013, Craig Gentry , Amit Sahai e Brent Waters (GSW) propuseram uma nova técnica para construir esquemas de FHE que evita uma etapa de "relinearização" cara na multiplicação homomórfica. Zvika Brakerski e Vinod Vaikuntanathan observaram que, para certos tipos de circuitos, o criptosistema GSW apresenta uma taxa de crescimento de ruído ainda mais lenta e, portanto, melhor eficiência e segurança mais forte. Jacob Alperin-Sheriff e Chris Peikert descreveram uma técnica de bootstrap muito eficiente com base nessa observação.

Essas técnicas foram melhoradas para desenvolver variantes de anel eficientes do criptossistema GSW: FHEW (2014) e TFHE (2016). O esquema FHEW foi o primeiro a mostrar que, ao atualizar os textos cifrados após cada operação, é possível reduzir o tempo de bootstrap para uma fração de segundo. FHEW introduziu um novo método para calcular portas booleanas em dados criptografados que simplifica muito a inicialização e implementou uma variante do procedimento de inicialização. A eficiência do FHEW foi ainda melhorada pelo esquema TFHE, que implementa uma variante em anel do procedimento de bootstrapping usando um método semelhante ao do FHEW.

FHE de quarta geração

O esquema CKKS oferece suporte a operações de arredondamento eficientes em estado criptografado. A operação de arredondamento controla o aumento do ruído na multiplicação criptografada, o que reduz o número de bootstrap em um circuito. No Crypto2018, o CKKS é focado como uma solução para aprendizado de máquina criptografado. Isso se deve a uma característica do esquema CKKS que criptografa valores aproximados em vez de valores exatos. Quando os computadores armazenam dados com valores reais, eles se lembram de valores aproximados com bits longos e significativos, não exatamente de valores reais. O esquema CKKS é construído para lidar de forma eficiente com os erros decorrentes das aproximações. O esquema é familiar ao aprendizado de máquina, que possui ruídos inerentes à sua estrutura.

Um artigo de 2020 de Baiyu Li e Daniele Micciancio discute ataques passivos contra CKKS, sugerindo que a definição IND-CPA padrão pode não ser suficiente em cenários onde os resultados de descriptografia são compartilhados. Os autores aplicam o ataque a quatro modernas bibliotecas de criptografia homomórfica (HEAAN, SEAL, HElib e PALISADE) e relatam que é possível recuperar a chave secreta dos resultados de descriptografia em várias configurações de parâmetros. Os autores também propõem estratégias de mitigação para esses ataques e incluem uma Divulgação Responsável no artigo, sugerindo que as bibliotecas de criptografia homomórfica já implementaram mitigações para os ataques antes que o artigo se tornasse publicamente disponível. Mais informações sobre as estratégias de mitigação implementadas nas bibliotecas de criptografia homomórfica também foram publicadas.

Criptossistemas parcialmente homomórficos

Nos exemplos a seguir, a notação é usada para denotar a criptografia da mensagem .

RSA não acolchoado

Se a chave pública RSA tiver módulo e expoente de criptografia , a criptografia de uma mensagem será fornecida por . A propriedade homomórfica é então

ElGamal

No criptosistema ElGamal , em um grupo cíclico de ordem com gerador , se a chave pública for , onde , e for a chave secreta, então a criptografia de uma mensagem é , para alguns aleatórios . A propriedade homomórfica é então

Goldwasser – Micali

No criptosistema Goldwasser-Micali , se a chave pública é o módulo e o não-resíduo quadrático , então a criptografia de um bit é , para alguns, aleatória . A propriedade homomórfica é então

onde denota módulo de adição 2, (ou seja, exclusivo ou ).

Benaloh

No criptosistema Benaloh , se a chave pública é o módulo e a base com um tamanho de bloco de , então a criptografia de uma mensagem é , para alguns, aleatória . A propriedade homomórfica é então

Paillier

No criptosistema Paillier , se a chave pública é o módulo e a base , então a criptografia de uma mensagem é , para alguns, aleatória . A propriedade homomórfica é então

Outros criptosistemas parcialmente homomórficos

Criptografia totalmente homomórfica

Um criptosistema que suporta computação arbitrária em textos cifrados é conhecido como criptografia totalmente homomórfica (FHE). Tal esquema permite a construção de programas para qualquer funcionalidade desejável, que podem ser executados em entradas criptografadas para produzir uma criptografia do resultado. Uma vez que tal programa nunca precisa descriptografar suas entradas, ele pode ser executado por uma parte não confiável sem revelar suas entradas e estado interno. Criptossistemas totalmente homomórficos têm grandes implicações práticas na terceirização de computações privadas, por exemplo, no contexto da computação em nuvem .

Implementações

Uma lista de bibliotecas FHE de código aberto que implementam esquemas FHE de segunda e / ou terceira geração é fornecida abaixo. Uma lista atualizada de implementações de criptografia homomórfica também é mantida pela comunidade no GitHub .

Existem várias implementações de código aberto de esquemas de criptografia totalmente homomórficos de segunda e terceira geração. As implementações do esquema FHE de segunda geração normalmente operam no modo FHE nivelado (embora o bootstrapping ainda esteja disponível em algumas bibliotecas) e oferecem suporte ao empacotamento de dados do tipo SIMD eficiente ; eles são normalmente usados ​​para calcular números inteiros criptografados ou números reais / complexos. Implementações de esquema FHE de terceira geração geralmente inicializam após cada operação de porta booleana, mas têm suporte limitado para compactação e cálculos aritméticos eficientes; eles são normalmente usados ​​para calcular circuitos booleanos em bits criptografados. A escolha de usar um esquema de segunda geração vs. terceira geração depende dos tipos de dados de entrada e do cálculo desejado.

Bibliotecas FHE
Nome Desenvolvedor BGV CKKS BFV FHEW CKKS Bootstrapping TFHE Descrição
HElib IBM sim sim Não Não Não Não Esquema BGV com as otimizações GHS.
Microsoft SEAL Microsoft Não sim sim Não Não Não
PALIÇADA Consórcio de empreiteiros e acadêmicos de defesa financiados pela DARPA: Instituto de Tecnologia de Nova Jersey , Duality Technologies , Raytheon BBN Technologies , MIT , Universidade da Califórnia, San Diego e outros. sim sim sim sim Não sim Biblioteca de criptografia de rede de propósito geral.
HEAAN Universidade Nacional de Seul Não sim Não Não sim Não
FHEW Leo Ducas e Daniele Micciancio Não Não Não sim Não Não
TFHE Ilaria Chillotti, Nicolas Gama, Mariya Georgieva e Malika Izabachene Não Não Não Não Não sim
FV-NFLlib CryptoExperts Não Não sim Não Não Não
NuFHE NuCypher Não Não Não Não Não sim Fornece uma implementação de GPU do TFHE.
Lattigo EPFL-LDS Não sim sim Não sim Não Implementação no Go junto com suas variantes distribuídas , permitindo computação segura de várias partes .
Estruturas FHE
Nome Desenvolvedor FHEW TFHE Helib SELO PALIÇADA
E3 Laboratório do MoMA na NYU em Abu Dhabi sim sim sim sim sim
OVELHA Instituto Alan Turing Não sim sim sim sim

estandardização

Um padrão da comunidade para criptografia homomórfica é mantido pelo grupo HomomorphicEncryption.org , um consórcio aberto da indústria / governo / academia cofundado em 2017 pela Microsoft , IBM e Duality Technologies . O documento padrão atual inclui especificações de parâmetros seguros para RLWE.

Veja também

Referências

links externos