O que é Criptografia Homomórfica?

Dados criptografados são processados sem serem decifrados
Autor: Pedro Filho /20 set 2010

Imagine a solução definitiva da criptografia: você poder responder a uma pergunta sem saber a própria pergunta.

De forma mais simples, suponha que alguém pense em dois números e, em seguida, peça a outra pessoa para somar ou multiplicar os dois, sem que essa pessoa saiba quais são os dois números.
Isso já é possível desde que a pessoa receba um código criptografado dos dois números – mesmo não conhecendo a senha para decifrá-los.

A técnica tornará possível, por exemplo, que uma empresa envie seus dados criptografados para processamento em um computador de terceiros, sem correr o risco de que seus dados sejam lidos.

Computação em dados criptografadosO último passo para transformar essa possibilidade técnica em uma realidade prática foi dado por Nigel Smart, da Universidade de Bristol, no Reino Unido, e Frederik Vercauteren, da Universidade Católica de Leuven, na Bélgica.

Os dois pesquisadores acabam de dar um passo importante rumo a um sistema totalmente prático que permita computar dados criptografados sem precisar decifrá-los.

“Nosso sistema permite que os cálculos sejam executados em dados criptografados, o que poderá permitir a criação de sistemas nos quais você armazena os dados remotamente de uma forma segura e ainda é capaz de acessá-los,” diz Smart.

Segundo o pesquisador, quando totalmente desenvolvido, o trabalho terá um impacto muito abrangente, em áreas tão diversas como o acesso a banco de dados, leilões eletrônicos e até urnas eletrônicas.

Um sistema assim será ideal também para acessar prontuários médicos durante pesquisas científicas. Os pesquisadores poderão executar cálculos estatísticos sobre ocorrências de enfermidades sem a necessidade de revelar informações sobre os pacientes individuais.

Criptografia homomórfica

Em outro exemplo, imagine uma pessoa que está participando de um leilão online, mas não quer o leiloeiro saiba sua oferta para não incentivar lances mais altos. Lances criptografados poderão ser enviados para o leiloeiro e, em seguida, usando um esquema totalmente homomórfico, o leiloeiro poderá saber quem ganhou e qual foi a proposta vencedora mesmo sem conhecer os demais lances.

Por quase 30 anos esse tem sido o sonho da criptografia: chegar a um esquema que permita “somar” e “multiplicar” mensagens cifradas – o chamado esquema totalmente homomórfico.Tão logo seja possível somar e multiplicar, torna-se possível realizar qualquer outra função.

Ao longo dos anos, foram propostos vários esquemas de criptografia nesse caminho, que possuem as operações de soma ou de multiplicação, mas nunca as duas.

Operações em textos cifrados

Craig Gentry
Em 2009, Craig Gentry, então na Universidade de Stanford e ligado à IBM, sugeriu o primeiro esquema capaz de tanto somar quanto multiplicar mensagens cifradas.

Contudo, embora seja uma descoberta teórica surpreendente, o sistema de Gentry não é prático.

Agora, Smart e Vercauteren descobriram uma maneira de simplificar o sistema de Gentry, tornando-o um pouco mais prático.

Embora ainda não seja eficiente o suficiente para ser usado no dia-a-dia, a realização é um passo importante nesse sentido, mostrando que a criptografia homomórfica é bem mais do que uma curiosidade técnica.

Bibliografia:
Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes

Site Inovação Tecnologica

Leia Também: As dez tecnologias para transformar o nosso mundo – quinta-feira, 28 de abril de 2011
Split-Key Encryption Technology – 8/04/2014

Tipos de criptografia: descubra as mais importantes para a sua empresa. Ouça

Tipos de criptografia: conheça os 10 mais usados e como funciona cada um Ouça

 Segundo a Wikipedia…

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 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.^[7] 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^[8] 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. ^[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. 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,^[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]

Referências – Fonte Wikipedia

1.  Ron Rivest (29 de outubro de 2002). «Lecture Notes 15: Voting, Homomorphic Encryption» (PDF)
2. ↑ Daniele Micciancio (1 de março de 2010). «A First Glimpse of Cryptography’s Holy Grail». Association for Computing Machinery. p. 96. Consultado em 17 de março de 2010
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 (25 de junho de 2009). «IBM touts encryption innovation». Computer World. Consultado em 14 de julho de 2009
7. ↑ Damien Stehle; Ron Steinfeld (19 de maio de 2010). «Faster Fully Homomorphic Encryption» (PDF). International Association for Cryptologic Research. Consultado em 15 de setembro de 2010
8. ↑ Craig Gentry. «A Fully Homomorphic Encryption Scheme (Ph.D. thesis)» (PDF)
9. ↑ Craig Gentry. «Computing Arbitrary Functions of Encrypted Data» (PDF). Association for Computing Machinery
10. ↑ Marten van Dijk; Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan (11 de dezembro de 2009). «Fully Homomorphic Encryption over the Integers» (PDF). International Association for Cryptologic Research. Consultado em 18 de março de 2010
11. ↑ «Cryptographic Test Correction»
12. ↑ Bram Cohen. «Simple Public Key Encryption» ^{[ligação inativa]}
13. ↑ News report http://www.info.unicaen.fr/M2-AMI/articles-2009-2010/smart.pdf Arquivado em 23 de julho de 2012, no Wayback Machine. paper] pdf slides Arquivado em 13 de junho de 2014, no Wayback Machine.
14. ↑ Craig Gentry; Shai Halevi. «A Working Implementation of Fully Homomorphic Encryption» (PDF)
15. ↑ Roberto Riggio; Sabrina Sicari. «Secure Aggregation in Hybrid Mesh/Sensor Networks» (PDF). Consultado em 3 de março de 2014. Arquivado do original(PDF) em 28 de março de 2012
16. ↑ Jean-Sébastien Coron; David Naccache, Mehdi Tibouchi. «Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers» (PDF)