O que é encriptação homomórfica?

A criptografia homomórfica (HE) permite realizar computações diretamente sobre dados criptografados, produzindo um resultado criptografado que, quando descriptografado, é igual ao resultado de realizar as mesmas operações sobre o texto claro. «Calcule sobre o texto cifrado sem descriptografar.»

Imagine colocar números dentro de uma caixa trancada com luvas especiais embutidas nas laterais. É possível manipular os números através das luvas (adicionar, multiplicar) sem nunca abrir a caixa. Somente o proprietário da chave pode ver o resultado ao destrancar a caixa.

A criptografia homomórfica parcial permite um tipo de operação sem limite: RSA (de livro-texto) é homomórfica multiplicativa: Enc(m1)*Enc(m2) = Enc(m1*m2). Paillier é homomórfica aditiva: Enc(m1)*Enc(m2) = Enc(m1+m2). Usada em votação eletrônica e recuperação privada de informações.

A criptografia homomórfica limitada permite adição e multiplicação, mas apenas durante um número limitado de multiplicações (profundidade do circuito). O ruído cresce a cada multiplicação; depois de um limiar, a descriptografia falha. Primeira construção de Gentry (2009).

A criptografia homomórfica completa permite computações arbitrárias (qualquer circuito booleano ou aritmético) sobre dados criptografados. Gentry (2009) mostrou que FHE é possível por meio da «reinicialização» — avaliando homomorficamente o circuito de descriptografia para atualizar o texto cifrado e zerar o ruído.

A maioria dos esquemas de HE é baseada em reticulados (BGV, BFV, CKKS). A criptografia adiciona ruído ao texto cifrado. Adição: o ruído cresce aditivamente. Multiplicação: o ruído cresce multiplicativamente. Reinicialização: descriptografa homomorficamente o texto cifrado, restaurando o ruído ao nível inicial. A reinicialização é dispendiosa.

O FHE ainda é 10^6 vezes mais lento que a computação em texto claro. Criptografar um único inteiro de 32 bits requer kilobytes de texto cifrado. A reinicialização leva segundos por porta. O FHE prático é direcionado a cargas de trabalho específicas: inferência de aprendizado de máquina, consultas a bancos de dados e análise genômica.

A maioria dos esquemas de HE baseia-se no problema difícil do Aprendizado com Erros (LWE) ou do LWE em anel (RLWE), que se acredita ser resistente a ataques quânticos. Romper o HE exige resolver o RLWE — não existe nenhum algoritmo quântico conhecido que ofereça um ganho significativo de velocidade contra ele.

SEAL (Microsoft, compatível com BFV/CKKS), HEAAN (Universidade Nacional de Seul, CKKS), OpenFHE (código aberto, BGV/BFV/CKKS/FHEW/TFHE), HElib (IBM, BGV). Todas são bibliotecas de nível de pesquisa; implantações em produção são raras e específicas de cada domínio.

Genômica médica: consultar um banco de dados de genes sem revelar seu genoma. Inferência de aprendizado de máquina criptografada: a nuvem executa uma rede neural sobre seus dados sem visualizá-los. Análise privada: agregar estatísticas sobre dados criptografados de usuários. Computação de riscos financeiros sobre carteiras confidenciais.

HE: uma única parte computa sobre dados criptografados por outra parte. MPC: várias partes computam conjuntamente sem revelar suas entradas umas às outras. Híbrido: use HE para o pré-processamento offline e MPC para protocolos interativos. Compromissos: HE = alta latência; MPC = sobrecarga de comunicação.

Qual é a principal limitação da Criptografia Homomórfica Parcial (SHE)?

A Criptografia Homomórfica permite computar sobre textos cifrados. O PHE é compatível com uma operação; o SHE é compatível com uma profundidade limitada; o FHE é compatível com circuitos arbitrários por meio da reinicialização. Baseia-se nos problemas difíceis LWE/RLWE. Próximo: os fundamentos matemáticos do LWE.