Analysis of the complexity of Homomorphic Encryption algorithms
DOI:
https://doi.org/10.5902/2179460X87825Keywords:
Partially Homomorphic Cryptography, Computational complexity, Privacy, SecurityAbstract
Partially Homomorphic Cryptography plays a crucial role in preserving privacy during the processing of sensitive information. This work presents partially homomorphic encryption schemes applied to integers, which support only one homomorphic operation, either additive or multiplicative. We analyze the computational time complexities associated with encryption, decryption, homomorphic computation, and potential attacks on each scheme. Additionally, we compare the studied schemes, detailing their algorithms and highlighting their key efficiency and security characteristics.
Downloads
References
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
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Ciência e Natura
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
To access the DECLARATION AND TRANSFER OF COPYRIGHT AUTHOR’S DECLARATION AND COPYRIGHT LICENSE click here.
Ethical Guidelines for Journal Publication
The Ciência e Natura journal is committed to ensuring ethics in publication and quality of articles.
Conformance to standards of ethical behavior is therefore expected of all parties involved: Authors, Editors, Reviewers, and the Publisher.
In particular,
Authors: Authors should present an objective discussion of the significance of research work as well as sufficient detail and references to permit others to replicate the experiments. Fraudulent or knowingly inaccurate statements constitute unethical behavior and are unacceptable. Review Articles should also be objective, comprehensive, and accurate accounts of the state of the art. The Authors should ensure that their work is entirely original works, and if the work and/or words of others have been used, this has been appropriately acknowledged. Plagiarism in all its forms constitutes unethical publishing behavior and is unacceptable. Submitting the same manuscript to more than one journal concurrently constitutes unethical publishing behavior and is unacceptable. Authors should not submit articles describing essentially the same research to more than one journal. The corresponding Author should ensure that there is a full consensus of all Co-authors in approving the final version of the paper and its submission for publication.
Editors: Editors should evaluate manuscripts exclusively on the basis of their academic merit. An Editor must not use unpublished information in the editor's own research without the express written consent of the Author. Editors should take reasonable responsive measures when ethical complaints have been presented concerning a submitted manuscript or published paper.
Reviewers: Any manuscripts received for review must be treated as confidential documents. Privileged information or ideas obtained through peer review must be kept confidential and not used for personal advantage. Reviewers should be conducted objectively, and observations should be formulated clearly with supporting arguments, so that Authors can use them for improving the paper. Any selected Reviewer who feels unqualified to review the research reported in a manuscript or knows that its prompt review will be impossible should notify the Editor and excuse himself from the review process. Reviewers should not consider manuscripts in which they have conflicts of interest resulting from competitive, collaborative, or other relationships or connections with any of the authors, companies, or institutions connected to the papers.
