Análise da complexidade dos algoritmos de Criptografia Homomórfica
DOI:
https://doi.org/10.5902/2179460X87825Palavras-chave:
Criptografia Parcialmente Homomórfica, Complexidade computational, Privacidade, SegurançaResumo
A Criptografia Parcialmente Homomórfica é importante para a preservação da privacidade no processamento de qualquer informação sensível. Este trabalho apresenta esquemas de Criptografia Parcialmente Homomórfica aplicados a inteiros, os quais suportam apenas uma operação homomórfica, seja aditiva ou multiplicativa. Realizamos a análise das complexidades de tempo computacional associadas às operações de cifragem, decifragem, cálculo do homomorfismo e possíveis ataques a cada esquema. Além disso, comparamos os esquemas estudados, detalhando seus algoritmos e destacando suas principais características de eficiência e segurança.
Downloads
Referências
Acar, A., Aksu, H., Uluagac, A. S., & Conti, M. (2018). A survey on homomorphic encryption schemes: Theory and implementation. ACM Comput. Surv., 51(4), 79:1–79:35. DOI: https://doi.org/10.1145/3214303
Borges, F., Lara, P., & Portugal, R. (2017). Parallel algorithms for modular multi-exponentiation. Applied Mathematics and Computation, 292, 406–416. DOI: https://doi.org/10.1016/j.amc.2016.07.036
Borges, F., Portugal, F. & Lara, S. (2007). Autenticaç˜ao e o problema do logaritmo discreto. Revista H´ıfen, 31(59/60), 106–111. http://revistaseletronicas.pucrs.br/fo/ojs/index.php/hifen/article/view/3884.
Clarkson, J. B. (1994). Dense probabilistic encryption. In Proceedings of the Workshop on Selected Areas of Cryptography. (pp. 120-128). Clarkson University.
Damg˚ard, I., & Jurik, M. (2001). A generalisation, a simplication and some applications of paillier’s probabilistic public-key system. In Kim, K., editor, Public Key Cryptography. (pp. 119-136). Springer Berlin Heidelberg. DOI: https://doi.org/10.1007/3-540-44586-2_9
Elgamal, T. (1985). A public key cryptosystem and a signature scheme based on discrete logarithms. In Goos, G. Hartmanis, J., editor, Proceedings of CRYPTO 84 on Advances in Cryptology. (pp. 469 - 472). Springer-Verlag. DOI: https://doi.org/10.1109/TIT.1985.1057074
Fousse, L., Lafourcade, P., & Alnuaimi, M (2011). Benaloh’s dense probabilistic encryption revisited. In Vaudenay, S., & Petit, C., editor, Progress in Cryptology – AFRICACRYPT 2011. (pp. 348-362). Springer Berlin Heidelberg. DOI: https://doi.org/10.1007/978-3-642-21969-6_22
Goldwasser, S. & Micali, S. (1982). Probabilistic encryption & how to play mental poker keeping secret all partial information. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing. (pp. 365–377). Association for Computing Machinery. DOI: https://doi.org/10.1145/800070.802212
Halevi, S. (2017). Homomorphic encryption. In Lindell, Y., editor, Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich. (pp. 219–276). Springer International Publishing. https://doi.org/10.1007/978-3-319-57048-8 5. DOI: https://doi.org/10.1007/978-3-319-57048-8
Kawachi, A., Tanaka, K., & Xagawa, K. (2007). Multi-bit cryptosystems based on lattice problems. In Okamoto, T., & Wang, X., editor, Public Key Cryptography – PKC 2007. (pp. 315-329). Springer Berlin Heidelberg. DOI: https://doi.org/10.1007/978-3-540-71677-8_21
Lara, P., & Borges, F. (2008). O algoritmo de fatoração gnfs. In Congresso Nacional de Matem´atica Aplicada e Computacional. Coordenaç˜ao de Sistemas e Redes. http://www.sbmac.org.br/eventos/cnmac/xxxi cnmac/PDF/316.pdf.
Naccache, D. & Stern, J. (1998). A new public key cryptosystem based on higher residues. In Liu, P., Basin, D. A., & Feng, D., editor, Proceedings of the 5th ACM Conference on Computer and Communications Security. (pp. 59–66). Association for Computing Machinery. DOI: https://doi.org/10.1145/288090.288106
Okamoto, T. & Uchiyama, S. (1998). A new public-key cryptosystem as secure as factoring. In Nyberg, K., editor, Advances in Cryptology — EUROCRYPT 98. (pp. 308-318). Springer Berlin Heidelberg. DOI: https://doi.org/10.1007/BFb0054135
Paillier, P. (1999). Public-key cryptosystems based on composite degree residuosity classes. In Stern, J., editor, Advances in Cryptology — EUROCRYPT ’99. (pp.223–238). Springer Berlin Heidelberg. DOI: https://doi.org/10.1007/3-540-48910-X_16
Pandey, G. (2014). A guide to general number field sieve for integer factorization. Investigations in Mathematical Sciences, 4, 83–98.
Pereira, D., Aranha, M., & Borges, F. (2019). HTTPS Keys in the Mediterranean. In 2019 II Workshop on Metrology for Industry 4.0 and IoT (MetroInd4.0IoT). (pp. 449–454). IEEE. DOI: https://doi.org/10.1109/METROI4.2019.8792830
Rivest, R. L., Adleman, L. & Dertouzos, M. L. (1978). On data banks and privacy homomorphisms. In DeMillo, R. A., editor, Foundations of Secure Computation. (pp.169-180). Academia Press.
Rivest, R. L., Shamir, A. & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM, 21(2), 120–126. DOI: https://doi.org/10.1145/359340.359342
Teske, E. (1998). Speeding up pollard’s rho method for computing discrete logarithms. In Buhler, J. P., editor, Algorithmic Number Theory. (pp. 541-554). Springer Berlin Heidelberg. DOI: https://doi.org/10.1007/BFb0054891
Publicado
Como Citar
Edição
Seção
Licença
Copyright (c) 2025 Ciência e Natura
Este trabalho está licenciado sob uma licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Para acessar a DECLARAÇÃO DE ORIGINALIDADE E EXCLUSIVIDADE E CESSÃO DE DIREITOS AUTORAIS clique aqui.
Diretrizes Éticas para Publicação de Revistas
A revista Ciência e Natura está empenhada em garantir a ética na publicação e na qualidade dos artigos.
A conformidade com padrões de comportamento ético é, portanto, esperada de todas as partes envolvidas: Autores, Editores e Revisores.
Em particular,
Autores: Os Autores devem apresentar uma discussão objetiva sobre a importância do trabalho de pesquisa, bem como detalhes e referências suficientes para permitir que outros reproduzam as experiências. Declarações fraudulentas ou intencionalmente incorretas constituem comportamento antiético e são inaceitáveis. Artigos de Revisão também devem ser objetivos, abrangentes e relatos precisos do estado da arte. Os Autores devem assegurar que seu trabalho é uma obra totalmente original, e se o trabalho e / ou palavras de outros têm sido utilizadas, isso tem sido devidamente reconhecido. O plágio em todas as suas formas constitui um comportamento publicitário não ético e é inaceitável. Submeter o mesmo manuscrito a mais de um jornal simultaneamente constitui um comportamento publicitário não ético e é inaceitável. Os Autores não devem submeter artigos que descrevam essencialmente a mesma pesquisa a mais de uma revista. O Autor correspondente deve garantir que haja um consenso total de todos os Co-autores na aprovação da versão final do artigo e sua submissão para publicação.
Editores: Os Editores devem avaliar manuscritos exclusivamente com base no seu mérito acadêmico. Um Editor não deve usar informações não publicadas na própria pesquisa do Editor sem o consentimento expresso por escrito do Autor. Os Editores devem tomar medidas de resposta razoável quando tiverem sido apresentadas queixas éticas relativas a um manuscrito submetido ou publicado.
Revisores: Todos os manuscritos recebidos para revisão devem ser tratados como documentos confidenciais. As informações ou ideias privilegiadas obtidas através da análise por pares devem ser mantidas confidenciais e não utilizadas para vantagens pessoais. As revisões devem ser conduzidas objetivamente e as observações devem ser formuladas claramente com argumentos de apoio, de modo que os Autores possam usá-los para melhorar o artigo. Qualquer Revisor selecionado que se sinta desqualificado para rever a pesquisa relatada em um manuscrito ou sabe que sua rápida revisão será impossível deve notificar o Editor e desculpar-se do processo de revisão. Os Revisores não devem considerar manuscritos nos quais tenham conflitos de interesse resultantes de relacionamentos ou conexões competitivas, colaborativas ou outras conexões com qualquer dos autores, empresas ou instituições conectadas aos documentos.
