Encriptação homomórfica

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Encriptação homomórfica é uma forma de encriptação que dá possibilidade a tipos específicos de computação serem realizados com cifrotexto, a fim de se obter um resultado encriptado que é o cifrotexto do resultado das operações realizadas no purotexto. 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,[1] 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[editar | editar código-fonte]

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

Unpadded RSA[editar | editar código-fonte]

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_1x_2)^e \;\bmod\; m = \mathcal{E}(x_1 \cdot x_2)

ElGamal[editar | editar código-fonte]

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[editar | editar código-fonte]

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_1r_2)^2 = \mathcal{E}(b_1 \oplus b_2), em que \oplus denota adição modulo 2, (i.e. ou-exclusivo)

Benaloh[editar | editar código-fonte]

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_1r_2)^c = \mathcal{E}(x_1 + x_2 \;\bmod\; c )

Paillier[editar | editar código-fonte]

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_1r_2)^m = \mathcal{E}( x_1 + x_2 \;\bmod\; m)

Outros sistemas criptográficos parcialmente homomórficos[editar | editar código-fonte]

Encriptação completamente homomórfica[editar | editar código-fonte]

Os exemplos listados acima dão suporte à computação homomórfica em apenas uma operação (adição ou multiplicação) em purotextos. Um sistema criptográfico que dá suporte tanto a adição quanto a multiplicação (com isso preservando a estrutura de anéis de purotextos) é 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.[2]

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.[3] 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,[4] utilizando criptografia baseada em reticulados, demonstrou o primeiro CHE, como anunciado pela IBM em 25 de junho de 2009.[5] [6] 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 2k 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.[7] Eles apresentaram otimizações que permitem que a computação seja quasi-k3.5 por porta booleana da função sendo avaliada.

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

Em 2009, Marten van Dijk, Craig Gentry, Shai Halevi e Vinod Vaikuntanathan apresentaram um segundo ECH,[10] que usa muitas das ferramentas da construção de Gentry mas não requer reticulados ideais. Ao invés 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,[11] e também ao que foi proposto por Bram Cohen em 1998.[12] 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.[13] 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.[14]

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.[15]

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.[16]

Referências[editar | editar código-fonte]

  1. Ron Rivest (2002-10-29). Lecture Notes 15: Voting, Homomorphic Encryption.
  2. Daniele Micciancio (2010-03-01). A First Glimpse of Cryptography's Holy Grail. Association for Computing Machinery. Página visitada em 2010-03-17.
  3. R. L. Rivest, L. Adleman, and M. L. Dertouzos. On data banks and privacy homomorphisms. In Foundations of Secure Computation, 1978.
  4. Craig Gentry. Fully Homomorphic Encryption Using Ideal Lattices. In the 41st ACM Symposium on Theory of Computing (STOC), 2009.[ligação inativa]
  5. http://www-03.ibm.com/press/us/en/pressrelease/27840.wss
  6. Michael Cooney (2009-06-25). IBM touts encryption innovation. Computer World. Página visitada em 2009-07-14.
  7. Damien Stehle; Ron Steinfeld (2010-05-19). Faster Fully Homomorphic Encryption (PDF). International Association for Cryptologic Research. Página visitada em 2010-09-15.
  8. Craig Gentry. A Fully Homomorphic Encryption Scheme (Ph.D. thesis) (PDF).
  9. Craig Gentry. Computing Arbitrary Functions of Encrypted Data. Association for Computing Machinery.
  10. Marten van Dijk; Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan (2009-12-11). Fully Homomorphic Encryption over the Integers (PDF). International Association for Cryptologic Research. Página visitada em 2010-03-18.
  11. Cryptographic Test Correction.
  12. Bram Cohen. Simple Public Key Encryption.
  13. News report http://www.info.unicaen.fr/M2-AMI/articles-2009-2010/smart.pdf paper] pdf slides
  14. Craig Gentry. A Working Implementation of Fully Homomorphic Encryption (PDF).
  15. Roberto Riggio. Secure Aggregation in Hybrid Mesh/Sensor Networks (PDF).
  16. Jean-Sébastien Coron; David Naccache, Mehdi Tibouchi. Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers (PDF).

Ligações Externas[editar | editar código-fonte]