Microsoft SEAL e o surgimento da criptografia homomórfica

Embora a criptografia homomórfica completa (FHE) tenha sido originalmente alcançada em 2009, ela está começando a receber mais atenção agora que o poder de computação alcançou suas demandas computacionais; no entanto, o objetivo da criptografia homomórfica remonta a uma década.

Uma pesquisa superficial encontrará várias definições para ele. Este é o mais direto e sucinto:

Uma forma de criptografia que permite a computação em textos cifrados gerando um resultado criptografado que, quando descriptografado, corresponde ao resultado das operações como se tivessem sido executadas em texto simples.

— Massimo Bertaccini ( Algoritmos de Criptografia )

Considere essa afirmação por um momento. A criptografia homomórfica permite que as operações sejam executadas em valores criptografados de forma que os resultados descriptografados produzam o resultado das operações como se fossem executadas nos valores não criptografados originais. A menção mais antiga que encontrei é On Data Banks and Privacy Homomorphisms (1978), na qual os autores estão tentando impedir que dados financeiros confidenciais armazenados em um sistema local sejam acessados por programadores de sistema usando um serviço remoto de compartilhamento de tempo.

Dados financeiros confidenciais são armazenados no banco de dados. Os serviços de compartilhamento de tempo que calculam os dados não implementam segurança adequada. Os programadores do sistema têm acesso aos dados financeiros. O papel afirma:

Use um homomorfismo de privacidade especial para criptografar seus dados para que o computador de time-share possa operar nos dados sem a necessidade de descriptografá-los primeiro.

Em outras palavras, desejo excluir o processamento dos meus dados sem ceder o acesso a eles.

Em outras palavras, function(A, B) = function (A , B ) onde A  and B são valores criptografados de A e B, respectivamente. Isso permite que terceiros calculem dados criptografados e forneçam os resultados sem ter conhecimento do valor original. Com o RSA, dois valores criptografados com a mesma chave podem ser multiplicados e o produto pode ser descriptografado gerando o produto dos valores criptografados.

Obtenha 5_6 usando RSA(5)_ RSA(6):

1. RSA(5) = (5^17) mod 3233 = 3096

2. RSA(6) = (6^17) mod 3233 = 824

3. 3096*824 = 254864

4. RSA^-1(254864) = 254864^2753 (mod 3233) = 30

5. 5*6 = 30

   
   

No entanto, isso não funciona para adição. RSA é um esquema de Criptografia Parcialmente Homomórfica (PHE), pois suporta apenas a multiplicação. A linha do tempo abaixo mostra a progressão dos esquemas (PHE) até a Criptografia Algo Homomórfica (SHWE), que permite combinações limitadas de adição e multiplicação. Essas operações podem ser repetidas até cinco vezes antes de chegar a um resultado inválido. Então veio o primeiro esquema FHE de Craig Gentry , que permitia adição e multiplicação repetidas sem perda de fidelidade.

Bibliotecas de criptografia homomórfica

Desde 2009, esquemas e bibliotecas de FHE proliferaram.

O Microsoft SEAL (Simple Encrypted Arithmetic Library) é desenvolvido em C++ 17 junto com um wrapper C#. Originalmente lançado em 2015, ainda está em desenvolvimento ativo. O repositório do github inclui exemplos detalhados de C# que devem ser explorados se você estiver interessado em se aprofundar.

Esses esquemas são suportados pelo SEAL e incluem operações homomórficas para adição, divisão, subtração e exponenciação, mas não divisão.

• Brakerski-Gentry-Vaikuntanathan (BGV)/Fan-Vercauteren (BFV)

  
  

  • Números inteiros (longos)

  • Use se a precisão for um requisito

  • A computação é mais lenta que CKKS

  • Valores criptografados com BGV podem ser usados com valores criptografados com BFV

  • Valores criptografados com BGV/BVF não podem ser usados com valores criptografados com CKKS

  • Revisitando esquemas de criptografia homomórfica para campos finitos

    
    

• Cheon-Kim-Kim-Song (CKKS)

  
  

  • Pontos flutuantes (duplo)
  • Use se a precisão não for necessária
  • Valores criptografados com CKKS não podem ser usados com valores criptografados com BGV/BFV
  • A computação é mais rápida que BFV/BGF

Criptografia e Computação com Microsoft SEAL

Esses exemplos usam o pacote Microsoft.Research.SEALNet Nuget e o esquema CKKS. Rastreadores de saúde, como FitBit e AppleHeath, exigem abrir mão de um pouco de privacidade. Eles coletam informações pessoais como o número de passos e geocoordenadas dos movimentos do usuário, frequência cardíaca e outras estatísticas vitais. Com criptografia homomórfica, esses agregadores de métricas de saúde ainda podem operar em nossos dados sem ter acesso aos dados brutos.

Neste exemplo simples, o cliente envia métricas de execução, incluindo distância e tempo. O servidor agrega os dados criptografados e calcula a velocidade média.

Para começar, uma chave pública é criada pelo cliente e compartilhada com o servidor. Ele é usado para criptografar dados e também para executar operações aritméticas em dados criptografados. Tanto o cliente quanto o servidor usam um Encryptor. O cliente gera e retém uma chave privada usada para descriptografia usada pelo apropriadamente chamado Decryptor .

Uma parte maliciosa que intercepta os dados pode usar a chave pública nos dados criptografados e devolvê-la ao chamador falsificando o servidor. O servidor deve assinar o resultado e o cliente deve verificar a assinatura para garantir que ela está sendo devolvida por uma parte confiável.

 using Microsoft.Research.SEAL; protected SEALContext _context; private KeyGenerator _keyGenerator; private Encryptor _encryptor; private Decryptor _decryptor; protected IFitnessTrackerApiClient _apiClient; . . . _context = SEALUtils.GetContext(_config.Value.PolyModulusDegree, this.SchemeType); _keyGenerator = new KeyGenerator(_context); _keyGenerator.CreatePublicKey(out PublicKey publicKey); _keyGenerator.CreateRelinKeys(out RelinKeys relinKeys); _encryptor = new Encryptor(_context, _publicKey); _decryptor = new Decryptor(_context, _keyGenerator.SecretKey); . . . PublicKeyModelCKKS keyModelCKKS = new( SEALUtils.KeyToBase64String(_publicKey), SEALUtils.KeyToBase64String(relinKeys)); await _apiClient.SendPublicKeyCKKSAsync(keyModelCKKS);

As chaves de relinearização são passadas do cliente para o servidor. De acordo com o Microsoft SEAL, eles não têm nenhum significado semântico além de reduzir o tamanho do texto cifrado após uma operação de multiplicação.

Na linha de comando, o usuário insere o tempo e a distância.

Cada valor é codificado para PlainText, depois criptografado para Ciphertext e finalmente codificado para base64 antes de enviá-lo ao servidor.

 using Microsoft.Research.SEAL; var plaintext = new Plaintext(); _encoder.Encode(value, _scale, plaintext); var ciphertext = new Ciphertext(); _encryptor.Encrypt(value, ciphertext); using (var ms = new MemoryStream()) { ciphertext.Save(ms); return Convert.ToBase64String(ms.ToArray()); }

Como os esquemas de criptografia homomórfica não suportam divisão (CKKS não é exceção), o cliente precisa dar uma ajuda ao servidor. A fórmula da velocidade é:

• distância/tempo

  
  

Outra forma de escrever é,

• distância * (1/tempo)

  
  

Assim, o cliente envia:

 RunItemCKKS metricsRequest = new( EncryptBase64(runItem.Distance), EncryptBase64(runItem.Time), EncryptBase64(1 / runItem.Time)); await _apiClient.AddNewRunningDistanceCKKSAsync(metricsRequest);

O servidor executa uma função de inicialização semelhante criando um SEALContext usando apenas a chave pública e as chaves de relinearização e, em seguida, processa a solicitação:

 var distance = SEALUtils.BuildCiphertextFromBase64String(request.Distance, _sealContext); var time = SEALUtils.BuildCiphertextFromBase64String(request.Time, _sealContext); var timeReciprocal = SEALUtils.BuildCiphertextFromBase64String(request.TimeReciprocal, _sealContext); Ciphertext speed = new(); _evaluator.Multiply(distance, timeReciprocal, speed); _evaluator.RelinearizeInplace(speed, _relinKeys); _runListCKKS.Add(new EncryptedRunInfoCKKS(distance, time, speed));

Um recíproco do tempo é usado para calcular a velocidade da execução enviada e o método RelinearizeInplace reduz o tamanho do texto cifrado resultante . Distância, tempo e velocidade são salvos em uma lista na memória.

O método GetMetrics agrega a lista e retorna:

• número total de execuções

• distância total

• tempo total

• velocidade média

  
  

   public SummaryItemCKKS GetMetrics() { int count = _runListCKKS.Count; var totalDistanceCKKS = SumEncryptedValues(_runListCKKS.Select(m => m.Distance)); var totalTimeCKKS = SumEncryptedValues(_runListCKKS.Select(m => m.Time)); var totalSpeed = SumEncryptedValues(_runListCKKS.Select(m => m.Speed)); . . . protected Ciphertext SumEncryptedValues(IEnumerable<Ciphertext> encryptedData) { . . . Ciphertext encTotal = new(); _evaluator.AddMany(encryptedData, encTotal); return encTotal; . . . }

  
  

Para obter a velocidade média, é usado o recíproco da contagem, portanto, em vez de usar:

(soma da velocidade)/número ou corridas que usamos:

(soma da velocidade) * (1/número de execuções)

Como o servidor controla o número de envios de execução, o número total de execuções não é um valor criptografado. Esse valor não criptografado pode ser convertido em texto simples e usado em uma operação executada em texto cifrado. Embora este seja um exemplo simples, vale a pena observar as implicações. O servidor pode fornecer valores adicionais usados em dados criptografados, permitindo que provedores terceirizados apliquem dados proprietários a cálculos contra dados criptografados fornecidos pelo cliente.

No exemplo abaixo, a contagem total é convertida em um recíproco e adicionada a uma List<double>. As operações CKKS esperam valores de lista criptografados, mesmo que a lista contenha apenas um único valor. Assim, o List<double> é codificado para um PlainText . O MultiplyPlainInplace multiplica totalSpeed por (1/número de execuções), resultando na velocidade média. Para economizar espaço, o resultado é aplicado ao totalSpeed Ciphertext e as chaves de relinearização reduzem o tamanho da saída.

 Plaintext encodedCountReciprocal = new(); List<double> averagePaceList = new(); double runCountReciprocal = 1 / (double)count; averagePaceList.Add(runCountReciprocal); _encoder.Encode(averagePaceList, _scale, encodedCountReciprocal); _evaluator.MultiplyPlainInplace(totalSpeed, encodedCountReciprocal); _evaluator.RelinearizeInplace(totalSpeed, _relinKeys);

Os valores são codificados em base64, retornados e descriptografados no cliente. O cliente executa a etapa adicional de converter o texto simples descriptografado em List<double> .

 var payload = Convert.FromBase64String(encryptedDistanceText); using var ms = new MemoryStream(payload); var ciphertext = new Ciphertext(); ciphertext.Load(_context, ms); var decryptedText = new Plaintext(); _decryptor.Decrypt(cypherText, decryptedText); List<double> distanceList = new(); _encoder.Decode(decryptedText, distanceList);

O envio dos valores a seguir gera os totais e o ritmo médio calculados por um serviço que tabulou o total e a média sem descriptografar os dados enviados do cliente.

O servidor calcula os dados e retorna o total de corridas, distância, tempo e ritmo sem descriptografar nenhum dos dados enviados.

Resumo

O Microsoft SEAL é um projeto da Microsoft Research e não está pronto para um aplicativo de produção. Todas as classes implementam IDisposable e usaram recursos não gerenciados. O código de produção precisaria proteger contra um vazamento de memória. A classe SEALContext não segue o princípio de responsabilidade única. Inclui métodos para BGV/BVF e CKKS. Além disso, CKKS suporta operações vetoriais, mas não adição vetorial. Uma única List<double> pode ser criptografada em um único CipherText , mas não há como somar os valores em um único CipherText. Isso pode ser feito com rotação de vetor , mas essa é uma solução abaixo do ideal.

Este exemplo de código do Fitness Tracker é uma introdução simples a um tópico complexo. Há uma série de casos de uso atraentes com uma lógica mais envolvente:

• Detecção de marcador genético

• Proteção de modelo biométrico

• Monitoramento humano seguro para envelhecimento no local

• Detecção de fraude de cartão de crédito

  
  

A criptografia homomórfica tem sido amplamente utilizada na academia e em protótipos. As aplicações práticas têm sido limitadas pelo poder computacional exigido pelos esquemas de criptografia homomórfica. A aceleração da GPU e os processadores ASIC continuarão a corroer essa barreira. A Intel está desenvolvendo o FHE Hardware Accelerator , desenvolvido especificamente para esquemas de criptografia homomórfica, em colaboração com a Microsoft e a DARPA. A NASDAQ também está financiando um projeto de P&D usando criptografia homomórfica com aprendizado de máquina para detecção de fraudes. A comunidade FHE.org é um excelente recurso para os desenvolvimentos mais atuais neste espaço. Possui um servidor Discord ativo.

Todos os exemplos de código neste artigo estão disponíveis em johniwasz/microsoft-seal-samples . Para obter um exemplo mais detalhado do Microsoft SEAL, consulte estes exemplos de .NET .

Também publicado aqui.