Criptografia Homomórfica para iniciantes - um guia prático (Parte 1)
Primeiro vou passar por cima do básico da criptografia homomórfica, seguido de uma breve visão geral das bibliotecas de criptografia homomórfica de código aberto que estão atualmente disponíveis, depois terminarei com um tutorial sobre como usar uma dessas bibliotecas (ou seja, PALISADE). Para este guia, estou assumindo um passado em criptografia básica, álgebra abstrata e C++.
Uma breve introdução à criptografia homomórfica
O conceito de criptografia homomórfica foi introduzido em [1], dos quais dois dos autores são Ronald L. Rivest e Len Alderman. O R e o A na criptografia RSA.
O exemplo mais popular para o uso de criptografia homomórfica é quando um proprietário de dados quer enviar dados até a nuvem para processamento, mas não confia em um provedor de serviços com seus dados. Usando um esquema de criptografia homomórfica, o proprietário de dados criptografa seus dados e os envia para o servidor. O servidor executa os cálculos relevantes sobre os dados sem nunca descriptografá-los e envia os resultados criptografados para o proprietário de dados. O proprietário de dados é o único capaz de descriptografar os resultados, já que eles sozinhos têm a chave secreta.
Até agora, o esquema de criptografia homomórfica mais eficiente ao realizar as mesmas operações em múltiplos textos cifrados ao mesmo tempo é o esquema Brakerski-Gentry-Vaikuntanathan (BGV) [11]. Os esquemas Brakerski/Fan-Vercauteren (BFV) [2, 3] e Os esquemas Cheon-Kim-Kim-Song (CKKS) [4] dividem o segundo lugar para eficiência. O BGV, no entanto, é mais difícil de usar. Estes são todos esquemas criptográficos baseados em treliças dependentes da dureza do problema de Aprendizagem de Anel com Erros (RLWE), o que (pelo menos por enquanto) significa que eles são seguros para o quantum. Para uma excelente introdução de lattices e o problema difícil em que a RLWE se baseia (ou seja, o problema do vetor mais curto) veja estas duas palestras do professor do MIT Vinod Vaikuntanathan:
https://simons.berkeley.edu/talks/vinod-vaikuntanathan-2015-05-18a
BGV, BFV e CKKS são aditivamente e multiplicativamente homomórficos (ou seja, você pode realizar tanto adição quanto multiplicação dentro do domínio criptografado). Sem divisão. Sem expor um número por um criptografado. Sem operações não-polinômias. Na BGV e BFV, os cálculos só podem ser realizados em inteiros. No CKKS, os cálculos podem ser realizados em números complexos com precisão limitada.
Uma captura é que você não pode executar cálculos ilimitados dentro do domínio criptografado sem correr em dois problemas:
Edição 1: No BGV e BFV, você tem que acompanhar o que é chamado de módulo de texto simples p. Simplificando, imagine que você tem p=9 e que você faz enc(4) + enc(8) = enc(3) (mod 9). Quando você descriptografar enc(3), se você não fosse cuidadoso, você não teria como saber se o resultado real era realmente destinado a ser 3, 12, 21, …
Problema 2: Em ambos os esquemas, você tem que ter certeza de que não ultrapasse o limiar de ruído, acima do qual seus valores não farão mais sentido. A dureza do RLWE baseia-se em adicionar uma pequena quantidade de erro a um ponto em uma rede, de tal forma que é difícil determinar a qual ponto esse erro foi originalmente adicionado. Para obter mais informações sobre o crescimento do ruído no CKKS, consulte as páginas 12 e 22 de [4]. As informações sobre o crescimento do ruído no BFV estão espalhadas por [3]. A razão pela qual o BGV é mais difícil de usar do que o BFV e o CKKS é que os níveis de ruído precisam ser acompanhados a cada passo do algoritmo.
O ruído pode ser tratado usando bootstrapping, famosamente introduzido por Craig Gentry como o primeiro método que permite que cálculos ilimitados sejam feitos no domínio criptografado [5]. A criptografia homomórfica sem um limite superior no número de cálculos que podem ser realizados é chamada de criptografia totalmente homomórfica (FHE), em oposição à criptografia um tanto homomórfica (SHE). Se alguém pedir, posso explicar bootstrapping em outro post.
Uma vez que bootstrapping é uma operação cara, é melhor evitar usá-lo a menos que você realmente precisa. O que o BFV e o CKKS usam para permitir que multiplicações de múltiplos textos cifrados sejam realizadas é a técnica de redução de erros invariantes explicada em [2].
Enquanto as adições de textos cifrados podem ser realizadas quase indiscriminadamente (dentro da razão), multiplicar dois textos cifrados juntos aumenta o ruído mais. Para que [2] o método invariante de escala funcione, você já precisa saber quantas multiplicações você vai realizar quando estiver gerando os parâmetros criptográficos. Sempre que possível, você deve optar por multiplicar textos cifrados com textos simples ou adicionar textos cifrados com textos simples, já que operações com textos simples dificilmente afetam o crescimento do ruído.
Se você está planejando executar as mesmas operações em vários textos cifrados, você deve considerar o uso do método SIMD (Single-Instruction-Multiple-Data), com base no Teorema do Restante Chinês, descrito em [9,10]. Essa otimização deve ser implementada em qualquer biblioteca de criptografia homomórfica que valha seu sal.
Ufa… essas são a maioria das restrições dentro das quais você terá que trabalhar para escrever código usando HE. Para obter informações mais claras sobre o esquema BFV, consulte [8].
Bibliotecas de Criptografia Homomórfica
Existem cinco bibliotecas de criptografia homomórfica de código aberto que ouvi coisas boas sobre:
Destes cinco, eu usei pessoalmente PALISADE, SEAL e HElib. Todos os três implementam o esquema BFV. SEAL e HElib também implementam CKKS.
PALISADE é um projeto financiado pela DARPA e IARPA (anteriormente financiado pela NSA também). Foi desenvolvido e é apoiado por uma equipe soberbamente talentosa no New Jersey Institute of Technology (Gerard Ryan, Professor Yuriy Polyakov, e Professor Kurt Rohloff).
O SEAL foi desenvolvido pelo Microsoft Research Cryptography Research Group.
HElib foi desenvolvido por Shai Halevi e Victor Shoup, ambos figuras estimadas na comunidade criptográfica. A biblioteca, no entanto, tem menos suporte do que o PALISADE e o SEAL.
O TFHE implementa um esquema mais rápido que o BGV para operações individuais, mas que não pode fazer uso do método SIMD mencionado acima.
PALISADE, HElib e SEAL podem ser usados livremente em aplicativos comerciais, com cada um usando uma licença NJIT, licença Apache v2.0 e licença MIT, respectivamente.
Um tutorial sobre PALISADE
Primeiro, clone o repo e, em seguida, configure o ambiente no Linux (o Windows não é mais suportado). A melhor maneira de aprender a usar qualquer uma das bibliotecas de criptografia homomórfica é olhar para os exemplos (PALISADE\src\pke\demo). Para PALISADE, o esquema que você deseja usar é chamado de BFVrns. BFV e BVG não são tão eficientes e o esquema LTV não é seguro.
Estaremos gerando um criptoistema de chave pública que permite adição e multiplicação dentro do domínio criptografado.
Para gerar os parâmetros de criptografia e salvá-los, você pode usar o seguinte código, que você pode essencialmente encontrar dentro das demonstrações PALISADE:
usint plaintextModulus = 536903681;
double sigma = 3.2;
size_t batchSize = 8;
SecurityLevel securityLevel = HEStd_128_classic;
////////////////////////////////////////////////////////////
// Parameter generation
////////////////////////////////////////////////////////////
EncodingParams encodingParams(new EncodingParamsImpl(plaintextModulus, batchSize));
//Set Crypto Parameters
// # of evalMults = 3 (first 3) is used to support the multiplication of 7 ciphertexts, i.e., ceiling{log2{7}}
// Max depth is set to 3 (second 3) to generate homomorphic evaluation multiplication keys for s^2 and s^3
CryptoContext<DCRTPoly> cc = CryptoContextFactory<DCRTPoly>::genCryptoContextBFVrns(encodingParams, securityLevel, sigma, 0, 3, 0, OPTIMIZED, 3);
// enable features that you wish to use
cc->Enable(ENCRYPTION);
cc->Enable(SHE);
// Generating a secret-public keypair
LPKeyPair<DCRTPoly> kp = cc->KeyGen();
if( !kp.good() ) {
std::cout << "Key generation failed!" << std::endl;
exit(1);
}
usint m = cc->GetCryptoParameters()->GetElementParams()->GetCyclotomicOrder();
PackedEncoding::SetParams(m, encodingParams);
Observe que quanto maior o módulo de texto simples, mais tempo os cálculos levarão dentro do domínio criptografado.
Você pode imprimir os parâmetros que foram gerados:
cout << *cc->GetCryptoParameters()->GetEncodingParams() << endl;
cout << *cc->GetCryptoParameters()->GetElementParams() << endl;
Você pode determinar quão seguros são seus parâmetros, comparando-os com os sugeridos no Padrão de Criptografia Homomórfica [8]. Os parâmetros gerados pelo código acima nos dão segurança de 128 bits, o que significa que seria necessário cerca de 2¹²⁸ computações a fim de quebrar a chave secreta.
Em seguida, você precisará gerar chaves para avaliar operações de adição e multiplicação:
cc->EvalSumKeyGen(kp.secretKey);
cc->EvalMultKeyGen(kp.secretKey);
Sempre que possível, você vai querer usar o método SIMD mencionado anteriormente. No PALISADE, você pode fazê-lo criando um vetor com os números que deseja operar, embalando esses números em um Plaintext e criptografando esse Plaintext:
vector<uint64_t> v1 = { 0, 4, 6, 2, 5 };
vector<uint64_t> v2 = { 1, 6, 3, 5, 2 };
// Convert the vectors into plaintext representation
Plaintext PT1 = cc->MakePackedPlaintext(v1);
Plaintext PT2 = cc->MakePackedPlaintext(v2);
Ciphertext<DCRTPoly> CT1;
Ciphertext<DCRTPoly> CT2;
// Convert the plaintext representations into a ciphertexts by encrypted them using the public key
CT1 = cc->Encrypt(kp.publicKey, PT1);
CT2 = cc->Encrypt(kp.publicKey, PT2);
// Evaluate the component-wise multiplication of the two ciphertexts
// product should be equal to { 0, 24, 18, 10, 10 }
//Thank you to Christian Grigis for pointing out the typo in the original file which incorrectly stated that the result should be { 1, 24, 18, 10, 10 }
Ciphertext<DCRTPoly> product = cc->EvalMult(CT1, CT2);
// Evaluate the component-wise sum of the two ciphertexts
// sum should be equal to { 1, 10, 9, 7, 7 }
Ciphertext<DCRTPoly> sum = cc->EvalAdd(CT1, CT2);
// Evaluate the inner product of the ciphertexts -- note that batchSize should be a power of 2
Ciphertext<DCRTPoly> innerProduct = cc->EvalInnerProduct(CT1, CT2, batchSize);
Lembre-se que estamos trabalhando com um anel polinômial. CT1 deve ser interpretado como os coeficientes criptografados do polinomial 0xii + 4x³ + 6x² + 2x + 5 e CT2 como os coeficientes criptografados de 1xii + 6x³ + 3x² + 5x + 2. A soma desses dois textos cifrados pode ser vista como a soma de dois polinômions dentro do domínio criptografado, resultando em 1x0 + 10x³ + 9x² +7x + 7. Considerando que sua multiplicação em termos de componentes resulta em 0xi + 24x³ + 18x² +10x + 10. Se tivéssemos usado MakeCoeffPackedPlaintext(v1) e MakeCoeffPackedPlaintext(v2) em vez de MakePackedPlaintext(v1) e MakePackedPlaintext(v2), multiplicar CT1 por CT2 teria resultado em um texto cifrado representando os coeficientes de 4x⁷+30x⁶+50x⁵+55x3+74x³+37x²+29x+10.
Para descriptografar e ver o resultado do produto interno:
Plaintext result;
cc->Decrypt(kp.secretKey, innerProduct, &result);
printf("Inner product is equal to %d", int(result->GetPackedValue()[0]));
Se alguém tiver um pedido especial para o que eu deveria incluir na parte 2 deste tutorial (seja teórico ou prático), sinta-se livre para me enviar uma mensagem no pthaine AT cs DOT toronto DOT edu.
Agradecimentos
Sou tremendamente grato à equipe do PALISADE por sua atenção às perguntas sobre sua biblioteca e ao Dr. Shai Halevi por suas sugestões sobre como melhorar a versão original deste post.
Referências
- [1] Rivest, R. L., Adleman, L., & Dertouzos, M. L. (1978). Sobre bancos de dados e homomorfismos de privacidade. Fundamentos da computação segura, 4(11), 169-180.
- [2] Brakerski, Z. (2012). Criptografia totalmente homomórfica sem modulus switching do GapSVP clássico. Em Avanços em criptografia-cripto 2012 (pp. 868-886). Springer, Berlim, Heidelberg.
- [3] Fan, J., & Vercauteren, F. (2012). Criptografia totalmente homomórfica. IACR Cryptology ePrint Archive, 2012, 144.
- [4] Cheon, J. H., Kim, A., Kim, M., & Song, Y. (2017, dezembro). Criptografia homomórfica para aritmética de números aproximados. Em Conferência Internacional sobre a Teoria e Aplicação de Criptologia e Segurança da Informação (pp. 409-437). Springer, Cham.
- [5] Gentry, C., & Boneh, D. (2009). Um esquema de criptografia totalmente homomórfico (Vol. 20, No09). Stanford: Universidade de Stanford.
- [6] Brakerski, Z., Gentry, C., & Vaikuntanathan, V. (2014). (Nivelado) criptografia totalmente homomórfica sem bootstrapping. ACM Transactions on Computation Theory (TOCT), 6(3), 13.
- [7] Smart, N. P., & Vercauteren, F. (2014). Operações simd totalmente homomórficas. Desenhos, códigos e criptografia, 71(1), 57-81.
- [8] Albrecht, M.; Chase, M.; Chen, H.; Ding, J.; Goldwasser, S.; Gorbunov, S.; Hoffstein, J.; Lauter, K.; Lokam, S.; Micciancio, D.; Moody, D.; Morrison, T.; Sahai, A.; e Vaikuntanathan, V. 2018. Padrão de segurança de criptografia homomórfica. Relatório técnico, HomomorphicEncryption.org, Cambridge MA. Gentry, Craig, Shai Halevi e Nigel P. Smart. “Criptografia totalmente homomórfica com sobrecarga de polílog.” Conferência Internacional Anual sobre a Teoria e Aplicações de Técnicas Criptográficas. Springer, Berlim, Heidelberg, 2012.
- [10] Smart, Nigel P., e Frederik Vercauteren. “Operações simd totalmente homomórficas.” Desenhos, códigos e criptografia 71.1 (2014): 57-81.
- [11] Brakerski, Zvika, Craig Gentry e Vinod Vaikuntanathan. “(Nivelado) criptografia totalmente homomórfica sem bootstrapping.” ACM Transactions on Computation Theory (TOCT) 6.3.
Apêndice
Se você planeja reutilizar suas chaves, você pode serializá-las e armazená-las em arquivos de texto:
string storagePathStr = ".";
Serialized pubK, privK, emKeys, esKeys;
if (kp.publicKey->Serialize(&pubK)) {
if (!SerializableHelper::WriteSerializationToFile(pubK, storagePathStr + "encryption_info_pubK.txt")) {
cerr << "Error writing serialization of public key to " + storagePathStr + " /encryption_info_pubK.txt" << endl;
return 0;
}
}
else {
cerr << "Error serializing public key" << endl;
return 0;
}
if (kp.secretKey->Serialize(&privK)) {
if (!SerializableHelper::WriteSerializationToFile(privK, storagePathStr + "/encryption_info_priK.txt")) {
cerr << "Error writing serialization of public key to " + storagePathStr + "/encryption_info_priK.txt" << endl;
return 0;
}
}
else {
cerr << "Error serializing private key" << endl;
return 0;
}
if (cc->SerializeEvalMultKey(&emKeys)) {
if (!SerializableHelper::WriteSerializationToFile(emKeys, storagePathStr + "/key-eval-mult.txt")) {
cerr << "Error writing serialization of the eval mult keys to " + storagePathStr + "/key-eval-mult.txt" << endl;
return 0;
}
}
else {
cerr << "Error serializing eval mult keys" << endl;
return 0;
}
if (cc->SerializeEvalSumKey(&esKeys)) {
if (!SerializableHelper::WriteSerializationToFile(esKeys, storagePathStr + "/key-eval-sum.txt")) {
cerr << "Error writing serialization of the eval sum keys to " + storagePathStr + "/key-eval-sum.txt" << endl;
return 0;
}
}
else {
cerr << "Error serializing eval sum keys" << endl;
return 0;
}
Você pode recuperar todas as suas chaves, parâmetros e criptocontexto da seguinte forma:
string secretKeyStoragePath = storagePathStr;
secretKeyStoragePath += "/encryption_info_priK.txt";
string publicKeyStoragePath = storagePathStr;
publicKeyStoragePath += "/encryption_info_pubK.txt";
Serialized serializedPublicKey, serializedSecretKey;
// Retrieving secret key
const char *skFile = secretKeyStoragePath.c_str();
FILE* secretKeyFile = fopen(skFile, "r");
if (secretKeyFile == 0)
printf("failed to open %s\n", secretKeyStoragePath.c_str());
char readBufferSK[65536];
FileReadStream sSK(secretKeyFile, readBufferSK, sizeof(readBufferSK));
serializedSecretKey.ParseStream(sSK);
fclose(secretKeyFile);
// Retrieving public key
const char *pkFile = publicKeyStoragePath.c_str();
FILE* publicKeyFile = fopen(pkFile, "r");
char readBufferPK[65536];
FileReadStream sPK(publicKeyFile, readBufferPK, sizeof(readBufferPK));
if (publicKeyFile == 0)
printf("failed to open %s\n", publicKeyStoragePath.c_str());
serializedPublicKey.ParseStream(sPK);
fclose(publicKeyFile);
// Deserializing the secret key and retriving parameters
cc = CryptoContextFactory<DCRTPoly>::DeserializeAndCreateContext(privK);
const auto encodingParams = cc->GetCryptoParameters()->GetEncodingParams();
const auto elementParams = cc->GetCryptoParameters()->GetElementParams();
usint m = elementParams->GetCyclotomicOrder();
PackedEncoding::SetParams(m, encodingParams);
// Deserializing Crypto Keys
LPPrivateKey<DCRTPoly> sk = cc->deserializeSecretKey(serializedSecretKey);
LPPublicKey<DCRTPoly> pk = cc->deserializePublicKey(serializedPublicKey);
if (!sk) {
cerr << "Could not deserialize secret key" << endl;
return 0;
}
if (!pk) {
cerr << "Could not deserialize public key" << endl;
return 0;
}
// Retrieving evaluation keys for multiplication and addition
Serialized ccEmk;
if (!SerializableHelper::ReadSerializationFromFile(storagePathStr + "/key-eval-mult.txt", &ccEmk)) {
cerr << "I cannot read serialization from " << storagePathStr << "/key-eval-mult.txt" << endl;
return 0;
}
Serialized ccEsk;
if (!SerializableHelper::ReadSerializationFromFile(storagePathStr + "/key-eval-sum.txt", &ccEsk)) {
cerr << "I cannot read serialization from " << storagePathStr << "/key-eval-sum.txt" << endl;
return 0;
}
// Deserializing eval keys
cc->DeserializeEvalMultKey(ccEmk);
cc->DeserializeEvalSumKey(ccEsk);
Autor: Patrícia Thaine