Encriptação homomórfica

Encriptação homomórfica, ou cifra homomórfica, é uma forma de encriptação que dá possibilidade a tipos específicos de computação serem realizados com texto cifrado, a fim de se obter um resultado encriptado que é o texto cifrado do resultado das operações realizadas no texto simples. Por exemplo, uma pessoa poderia somar dois números encriptados e outra pessoa poderia desencriptar o resultado sem que nenhuma delas consiga descobrir o valor dos números individualmente. A propriedade homomórfica de vários sistemas criptográficos pode ser usada para criar sistemas de votação seguros, funções hash resistentes a colisão, esquemas de recuperação privada de informação e permitir que se use computação em nuvem garantindo a confidencialidade dos dados processados.

Existem alguns sistemas criptográficos parcialmente homomórficos eficientes e dois completamente homomórficos, porém menos eficientes. Embora um sistema criptográfico que seja despropositadamente homomórfico possa estar sujeito a ataques em sua base, se tratado com cuidado, o homomorfismo pode também ser utilizado para realizar computações de modo seguro.

Sistemas criptográficos parcialmente homomórficos

Nos exemplos a seguir, a notação ${\mathcal {E}}(x)$ é utilizada para denotar a encriptação da mensagem $x$.

Unpadded RSA

Se a chave pública RSA é módulo $m$ e tem expoente $e$, então a encriptação da mensagem $x$ é dada por ${\mathcal {E}}(x)=x^{e}\;{\bmod {\;}}m$. A propriedade homomórfica é, então

${\mathcal {E}}(x_{1})\cdot {\mathcal {E}}(x_{2})=x_{1}^{e}x_{2}^{e}\;{\bmod {\;}}m=(x_{1}x_{2})^{e}\;{\bmod {\;}}m={\mathcal {E}}(x_{1}\cdot x_{2})$

ElGamal

No sistema criptográfico ElGamal, em um grupo G, se a chave pública é $(G,q,g,h)$, em que $h=g^{x}$ e $x$ é a chave secreta, então a encriptação da mensagem $m$ é ${\mathcal {E}}(m)=(g^{r},m\cdot h^{r})$, para algum aleatório $r\in \{0,\ldots ,q-1\}$. A propriedade homomórfica é, então

${\mathcal {E}}(x_{1})\cdot {\mathcal {E}}(x_{2})=(g^{r_{1}},x_{1}\cdot h^{r_{1}})(g^{r_{2}},x_{2}\cdot h^{r_{2}})=(g^{r_{1}+r_{2}},(x_{1}\cdot x_{2})h^{r_{1}+r_{2}})={\mathcal {E}}(x_{1}\cdot x_{2})$

Goldwasser-Micali

No sistema criptográfico Goldwasser-Micali, se a chave pública é módulo $m$ e o resíduo não-quadrático é $x$, então a encriptação do bit $b$ é ${\mathcal {E}}(b)=x^{b}r^{2}\;{\bmod {\;}}m$, para algum aleatório $r\in \{0,\ldots ,m-1\}$. A propriedade homomórfica é, então

${\mathcal {E}}(b_{1})\cdot {\mathcal {E}}(b_{2})=x^{b_{1}}r_{1}^{2}x^{b_{2}}r_{2}^{2}=x^{b_{1}+b_{2}}(r_{1}r_{2})^{2}={\mathcal {E}}(b_{1}\oplus b_{2})$, em que $\oplus$ denota adição modulo 2, (i.e. ou-exclusivo)

Benaloh

No sistema criptográfico Benaloh, se a chave pública é módulo $m$ e a base $g$ com um tamanho de bloco $c$, então a encriptação da mensagem $x$ é ${\mathcal {E}}(x)=g^{x}r^{c}\;{\bmod {\;}}m$, para algum aleatório $r\in \{0,\ldots ,m-1\}$. A propriedade homomórfica é, então

${\mathcal {E}}(x_{1})\cdot {\mathcal {E}}(x_{2})=(g^{x_{1}}r_{1}^{c})(g^{x_{2}}r_{2}^{c})=g^{x_{1}+x_{2}}(r_{1}r_{2})^{c}={\mathcal {E}}(x_{1}+x_{2}\;{\bmod {\;}}c)$

Paillier

No sistema criptográfico Paillier, se a chave pública é módulo $m$ e a base é $g$, então a encriptação da mensagem $x$ é ${\mathcal {E}}(x)=g^{x}r^{m}\;{\bmod {\;}}m^{2}$, para algum aleatório $r\in \{0,\ldots ,m-1\}$. A propriedade homomórfica é, então

${\mathcal {E}}(x_{1})\cdot {\mathcal {E}}(x_{2})=(g^{x_{1}}r_{1}^{m})(g^{x_{2}}r_{2}^{m})=g^{x_{1}+x_{2}}(r_{1}r_{2})^{m}={\mathcal {E}}(x_{1}+x_{2}\;{\bmod {\;}}m)$

Outros sistemas criptográficos parcialmente homomórficos

• Sistema criptográfico Okamoto–Uchiyama
• Sistema criptográfico Naccache–Stern
• Sistema criptográfico Damgård–Jurik
• Sistema criptográfico Boneh–Goh–Nissim

Encriptação completamente homomórfica

Os exemplos listados acima dão suporte à computação homomórfica em apenas uma operação (adição ou multiplicação) em textos simples. Um sistema criptográfico que dá suporte tanto a adição quanto a multiplicação (com isso preservando a estrutura de anéis de texto simples) é conhecido como encriptação completamente homomórfica (ECH) e é bem mais poderosa. Usando tal esquema, qualquer circuito pode ser avaliado homomorficamente, permitindo a construção de programas que podem rodar com as encriptações de suas entradas para produzir uma encriptação de sua saída. Como tais programas nunca desencriptam suas entradas, eles podem ser utilizados por terceiros não confiáveis sem revelar sua entrada e estado interno. A existência de um sistema criptográfico completamente homomórfico e eficiente teria uma grande implicação prática na terceirização de computação privada, como no contexto de computação em nuvem.

A parte "homomórfica" de um ECH pode também ser descrita em termos da teoria das categorias. Se C é uma categoria na qual os objetos são números inteiros (i.e. fluxos finitos de dados) e os morfismos são funções computáveis, então (idealmente) um ECH eleva uma função de encriptação de um functor de C para ele mesmo.

A utilidade da ECH foi reconhecida há bastante tempo. O problema de se construir tal esquema foi primeiramente proposto com um ano do desenvolvimento do RSA. Uma solução se provou mais elusiva; por mais de 30 anos não estava claro se ECH era realmente possível. Nesse período, o melhor resultado havia sido do sistema criptográfico Boneh-Goh-Nissim, que dá suporte a avaliações de um número ilimitado de adições, porém no máximo uma multiplicação.

Craig Gentry, utilizando criptografia baseada em reticulados, demonstrou o primeiro CHE, como anunciado pela IBM em 25 de junho de 2009. Seu esquema dá suporte a avaliações de circuitos com profundidades arbitrárias. Sua construção começa a partir de uma encriptação homomórfica com limite de profundidade (chamada de somewhat homomorphic ou limitadamente homomórfica), utilizando reticulados ideais que são limitados a avaliar polinômios de graus baixos sobre dados encriptados. Os reticulados são limitados porque cada cifrotexto tem ruídos que crescem à medida que são feitas somas e multiplicações, até que o ruído torna o cifrotexto resultante indecifrável. Gendry, então, mostra como modificar esse esquema de modo a tornar possível bootstrapping. Em particular, ele mostra que modificando um pouco o esquema limitadamente homomórfico, pode-se avaliar seu próprio circuito de desencriptação, uma propriedade auto-referencial. Finalmente, ele mostra que qualquer esquema limitadamente homomórfico que permita bootstrapping pode ser convertido em uma ECH através de uma encorporação recursiva. No caso particular do esquema limitadamente homomórfico baseado em reticulados ideais de Gentry, o procedimento de bootstrapping efetivamente "atualiza" o cifrotexto de forma a reduzir seu ruído associado, a fim de utilizá-lo em mais adições e multiplicações sem resultar num cifrotexto indecifrável. Gentry baseou a segurança de seu esquema na dificuldade aparente de se resolverem dois problemas: alguns cenários de pior caso sobre reticulados ideais e o problema da soma de subconjuntos esparsos.

Quanto a desempenho, cifrotextos no esquema de Gendry permanecem compactos no sentido de que seus comprimentos não dependem da complexidade da função avaliada sobre os dados encriptados. O tempo computacional depende apenas linearmente do número de operações realizadas. Entretanto, esse esquema é impraticável para muitas aplicações porque o tamanho do cifrotexto e o tempo computacional crescem significativamente à medida que o nível de segurança aumenta. Para se obter 2^k de segurança contra ataques conhecidos, o tempo computacional e o tamanho do cifrotexto são polinômios de altos graus em k. Recentemente, Stehle e Steinfeld reduziram a dependência em k substancialmente. Eles apresentaram otimizações que permitem que a computação seja quasi-k^3.5 por porta booleana da função sendo avaliada.

A tese de Ph.D. de Gentry provê detalhes adicionais. Ele também publicou um resumo da construção de van Dijk et al. (descrita abaixo) na edição de março de 2010 de Comunicações da ACM.

Em 2009, Marten van Dijk, Craig Gentry, Shai Halevi e Vinod Vaikuntanathan apresentaram um segundo ECH, que usa muitas das ferramentas da construção de Gentry mas não requer reticulados ideais. Em vez disso, eles mostraram que um componente limitadamente homomórfico do esquema baseado em reticulados ideais de Gentry pode ser substituído por um esquema limitadamente homomórfico, mais simples, que utiliza números inteiros. Esse esquema é, então, conceituamente mais simples do que o esquema de reticulados de Gentry mas tem propriedades similares em relação às operações homomórficas e a eficiência. O componente limitadamente homomórfico no trabalho de van Dijk et al. é similar ao esquema de encriptação proposto por Levieil e Naccache em 2008, e também ao que foi proposto por Bram Cohen em 1998. O método de Cohen não é aditivamente homomórfico, entretanto. O esquema Levieil-Naccache é aditivamente homomórfico e pode ser modificado para dar suporte também a um número pequeno de multiplicações.

Em 2010, Nigel P. Smart e Frederik Vercauteren apresentaram uma melhoria ao esquema de Gentry através de chaves e cifrotextos menores, mas que ainda não são completamente práticos. No Eurocrypt 2010, Craig Gentry e Shai Halevi apresentaram uma implementação funcional de um ECH (i.e. o procedimento completo do bootstrapping) com avaliações de desempenho.

Também em 2010, Riggio e Sicari apresentaram uma aplicação prática da encriptação homomórfica para um sensor híbrido sem fio/rede de malha. O sistema permite que backhauls transparentes de múltiplos saltos realizem análises estatísticas de diferentes tipos de dados (temperatura, umidade etc.) vindos de uma RSSF, ao mesmo tempo provendo encriptação fim-a-fim e autenticação salto-a-salto.

Recentemente, Coron, Naccache and Tibouchi propuseram uma técnica que permite reduzir o tamanho da chave pública do esquema de van Dijk et al. para 600 KB.

Ligações Externas

• Homomorphic encryption em Cryptology Pointers
• The Homomorphic Encryption Project
• The Open Source hcrypt Project
• American Scientist article Sept 2012