Crash Course em Criptografia Homomórfica

A ideia deste post é prover uma linha do tempo alto nível do surgimento e evolução da criptografia homomórfica, conceitos iniciais, principais pontos de destaque, sem se aprofundar na matemática e formalidade do tema neste momento. Servindo como uma síntese da história dessa área de estudo.

Conceituação e Primeiros Passos

A possibilidade de realizar computação utilizando dados cifrados foi concebida em 1978 e publicada no artigo On Data Banks and Privacy Homomorphisms, escrito por parte dos autores do RSA. Eles introduzem o conceito de Homomorfismo de Privacidade (Privacy Homomorfism), referindo-se a um subconjunto especial de funções criptográficas que permitem a operação sobre dados cifrados.

São explorados no artigo exemplos de operações que poderiam ser utilizadas sobre dados cifrados, e apresentados esquemas onde já poderíamos utilizar essas operações, sendo o RSA um exemplo de esquema com homomorfismo multiplicativo.

Isso era possível, pois um texto cifrado pelo RSA tem a forma:

c = m^e \pmod{n} \\

Onde:

\begin{aligned} m:\quad &\text{A mensagem em texto claro.}\\ e:\quad & \text{Expoente público.}\\ n:\quad & \text{Módulo, faz parte da chave pública.}\\ c:\quad & \text{Criptograma da mensagem m.} \\ E:\quad & \text{Função de encriptação} \end{aligned}

Dessa forma, sejam as mensagem $m_1$ e $m_2$ :

\begin{aligned} c_1 &= m_1^e \pmod{n} \\ c_2 &= m_2^e \pmod{n} \end{aligned}

O produto de suas cifras resulta na cifra da multiplicação de suas mensagens:

\begin{aligned} c_1 \cdot c_2 \equiv (m_1^e) \cdot (m_2^e) &\equiv (m_1 \cdot m_2)^e \pmod{n} \\ \therefore \quad c_1 \cdot c_2 &= E(m_1 \cdot m_2) \pmod{n} \end{aligned}

Partially Homomorphic Encryption

Pelo exemplo apresentado anterior, podemos perceber que estamos limitados na variedade de operações que podemos realizar utilizando um esquema, e essa foi a realidade por algum tempo com os esquemas chamados Partially Homomorphic Encryption, que permitiam soma ou multiplicação, mas não ambas ilimitadamente.

Como exemplo para a múltiplicação temos o RSA e o ElGamal. Para adição temos o Goldwasser-Micaeli que permitia a operação XOR, com expansão significativa do tamanho do texto cifrado, e Paillier, que permite a adição de textos cifrados, e a multiplicação de um texto cifrado por um escalar(texto claro).

Somewhat Homomorphic Encryption

Existiram alguns esquemas que implementaram ambas as operações, adição e múltiplicação, mas com um número limitado de operações, como o BGN (Boneh-Goh-Nissim), baseado em Grupos Bilineares (Paired-base Cryptography). Ele permitia somente uma única multiplicação sobre os valores encriptados, e uma profundidade arbitrária para adição. Esquemas que possuem essa limitação na profundidade dos circuitos que podem computar pertencem ao grupo Somewhat Homomorphic Encryption.

Primeira Geração de Criptografia Totalmente Homomórfica

Para um esquema ser considerado totalmente homomórfico (Fully Homomorphic Encryption), ele precisa conseguir realizar um conjunto de funções que seja funcionalmente completo (e.g.: $\{\text{XOR}, \text{AND}\}$ ). Portanto, as duas funções básicas para tal são a adição e multiplicação binárias, sendo elas, respectivamente, isomorfas ao XOR e AND booleanos.

Bootstrap the Bootstrapping

Craig Gentry publicou em 2009, quando ainda era doutorando em Stanford, sua tese intitulada Fully Homomorphic Encryption Using Ideal Lattices. Ele adotou um sistema de criptografia baseada em reticulados (lattice-based cryptography), já existente, mas que possuia um problema com ruído (noise), pela aritmética não ser exata, um pequeno termo de erro aleatório que é introduzido durante a encriptação para garantir a segurança. Dessa forma, ao realizarmos as operações:

Adição: Ao somar texto cifrados, seus ruídos são somados, crescendo de forma linear.
Multiplicação: Ao multiplicar textos cifrados multiplica seus ruídos, tendo assim um crescimento exponencial.

O problema é que se o ruído crescer mais do que o teto definido no sistema, é impossível decifrar o texto cifrado, causando erros de decodificação, e tornando o esquema em Somewhat Homomorphic (SHE).

Para solucionar este problema, o artigo inovou apresentando a técnica de Bootstrapping. Irei falar mais sobre este tema em outro post, mas simplificando, é uma forma de reiniciar o ruído acumulado no texto cifrado. Tranformando a criptografia homomórfica em uma realidade matemática construível, mas ainda ineficiente no momento, podendo levar cerca de 30 minutos para a conclusão de uma única porta lógica.

DGHV

Houve também, em 2010, a publicação do paper Fully Homomorphic Encryption over the Integers apresentando o esquema DGHV, onde a estrutura de reticulado foi substituída por inteiros. A função de encriptação era dada por:

\begin{align} c = E(m) = pq + 2r + m \end{align}

Sendo $m$ a mensagem, $p$ a chave publica, e $q, r$ inteiros escolhidos aleatoriamente em um intervalo prescrito, sendo $2r < p/2$ em valores absolutos. O objetivo principal deste trabalho era demonstrar a possibilidade de obter FHE com conceitos simples, sem a necessidade da utilização de reticulados ideais.

Segunda Geração

Em 2010 o artigo On Ideal Lattices and Learning with Errors Over Rings introduziu o problema do Ring Learning With Errors (RLWE), uma variante em anéis do Learning With Errors (LWE), juntamente com outras técnicas para gerenciamento de ruído mais sofisticadas.

O RLWE se consolidou como um problema chave devido a sua eficiência, pois enquanto o LWE opera com vetores sobre inteiros, o RLWE opera com polinômios em anéis ciclotômicos (e.g.: $R_q = \mathbb{Z}_q[X]/(X^N + 1)$ ). Dessa forma, ele permite o empacotamento de múltiplos valores de textos claros em um único texto cifrado, representado pelo polinômio. Essa junção permite a utilização de operações SIMD (Single-instruction Multiple-data), de forma que uma única operação homomórfica é aplicada simultaneamente em múltiplos slots de dados.

Essa evolução aumentou o throughput da FHE ordens de magnitude.

BGV (Brakerski-Gentry-Vaikuntanathan)

O esquema foi apresentado pelos pesquisadores em 2011 no artigo Fully Homomorphic Encryption without Bootstrapping, e representou uma evolução para a área. Ele introduziu uma técnica de gerenciamento de ruído chamada Troca de Módulo (Modulus Switching), onde um texto cifrado módulo q, ao ter seu ruído aumentado significativamente, é convertido para ser um texto cifrado módulo $q'$ , $q' < q$ . Assim a magnitude do ruído é diminuído por um fator $q'/q$ .

BFV (Brakerski/Fan-Vercauteren)

Proposto em 2012 no artigo Somewhat Practical Fully Homomorphic Encryption, ele é uma variante do BGV onde gerenciamento do ruído ocorre pela própria estrutura aritmética do esquema, mantendo o módulo do texto cifrado constante durante as operações homomórficas.

Ambos os esquemas suportam aritmética exata de inteiros, e possuem a necessidade de relinearização, onde em uma multiplicação de dois textos cifrados resulta em um trio, que precisam ser relinearizados, sendo essa uma operação custosa computacionalmente.

Terceira Geração

GSW (Gentry-Sahai-Waters)

Um esquema baseado em autovetores aproximados (approximate eigenvectors). Com essa nova abordagem, foi possível eliminar a necessidade de relinearização. O ruído cresce de forma assimétrica, mas o tamanho dos textos cifrados (matrizes quadradas) é significativamente maior, limitando seu uso em certos casos de uso.

FHEW e TFHE

Com avanços significativos na diminuição do tempo de boostrapping, temos o FHEW (Fastest Homomorphic Encryption in the West) em 2014, e o TFHE (Torus FHE) em 2016 que realizavam o boostrapping em milissegundos. Essa nova geração tornou viável a avaliação de circuitos booleanos arbitrários, dessa forma, podendo representar qualquer programa de computador (Pois todo programa pode ser representado por um circuito booleano).

Quarta Geração

Com as gerações anteriores focando na otimização dos cálculos na aritmética exata, essa geração marca uma mudança de paradigma ao introduzir a aritmética aproximada. Tendo como uma das principais inovações a reinterpretação do ruído criptográfico.

CKKS (Cheon-Kim-Kim-Song)

O esquema foi proposto em 2016 no artigo Homomorphic Encryption for Arithmetic of approximate Numbers, também conhecido como HEAAN, e introduziu o conceito de Criptografia Homomórfica Aproximada. Ele trata o ruído criptográfico do RLWE como parte do erro numérico de aproximação inerente à computação com ponto flutuante (como um erro de arredondamento). Ele permite que o ruído afete somente os bits menos significativos da mensagem decifrada. Para obter seus resultados, uma técnica de encoding que utiliza a inversa do Canonical Embedding mapeia vetores de números complexos $(\mathbb{C}^{N/2})$ em polinômios de coeficientes inteiros do anel RLWE, aplicando um escalonamento e arredondamento para discretização.

Os avanços obtidos habilitaram a aplicação da criptografia homomórfica em diversas áreas que possuem uma sinergia com cálculos de ponto flutuante, como aplicações de Machine Learning, Redes Neurais, análise de dados genômicos, etc; o CKKS criou o padrão para o que se tornaria o Privacy-Preserving Machine Learning (PPML) baseado em Criptografia Homomórfica.

Avanços paralelos

CHIMERA

Com o objetivo de utilizar as especializações de cada esquema, o CHIMERA é uma abordagem híbrida que nos permite transformar o texto cifrado entre os esquemas TFHE, BFV e CKKS. Ele obtém esse resultado com o mapeamento dos espaços de mensagens de cada esquema para uma nova estrutura comum, baseada em Torus $(\mathbb{T} = \mathbb{R} / \mathbb{Z})$ , o que permite a transformação sem a necessidade de decifragem.

Bibliotecas

Existem diversas opções de implementações do esquemas mais importantes disponíveis em bibliotecas open-source, como a OpenFHE, que é a sucessora que unificou diversos projetos anteriormente isolados e a opção mais completa até o momento, e a MicrosoftSEAL, que foca nos esquemas BGV e CKKS. Essas bibliotecas são bases robustas para qualquer desenvolvedor, ou pesquisador, que queria utilizar a criptografia homomórfica sem a necessidade de implementar todas a matemática do zero.

Aceleração de Hardware

Embora os esquemas homomórficos tenham sido otimizados drasticamente nos últimos anos, eles ainda possuem custos proibitivos para algumas aplicações práticas, como 23 min para a execução da ResNet-20 em CPU, exemplificado no artigo do CraterLake. Por esse motivo, existem estudos de técnicas de aceleração de Hardware utilizando GPU, FPGA, ou implementando ASICs, como o Intel HERACLES que utiliza uma arquitetura near-memory com unidades interconectadas voltadas ao processamento de polinômios de anel (Ring Polynomials) nativamente. Ele foi desenvolvido sobre o programa DPRIVE da DARPA.

Acho que já deu para termos uma pequena noção sobre parte do passado da criptografia homomórfica, e entendermos um pouco sobre o presente da área. Para os interessados em um aprofundamento na área, recomendo olharem o Awesome Homomorphic Encryption, uma lista contendo materiais diversificados sobre a área.

References