| Peer-Reviewed

Fully Homomorphic Public-Key Encryption Against Ciphertext Square Attack with Two Ciphertexts

Received: 12 July 2018     Accepted: 4 September 2018     Published: 8 October 2018
Views:       Downloads:
Abstract

A fully homomorphic public-key encryption (FHPKE) is the important cryptosystem as the basic scheme for the cloud computing. Since Gentry discovered in 2009 the first fully homomorphic encryption scheme, some fully homomorphic encryption schemes were proposed. In the systems proposed until now the bootstrapping process is the main bottleneck and the large complexity for computing the ciphertext is required. The existence of an efficient fully homomorphic cryptosystem would have great practical implications in the outsourcing of private computations, for instance, in the context of cloud computing. In recent year Yagisawa proposed fully homomorphic encryptions without bootstrapping which have the weak point in the enciphering function or not immune from “ciphertext square attack” which is the attack proposed in this article. In this article, a new FHPKE against “ciphertext square attack” is proposed which does not need the bootstrapping and does not require the large complexity for enciphering. The scheme has the following features; (a) its security bases on computational difficulty to solve the multivariate algebraic equations of high degrees; (b) it requires two ciphertexts corresponding to a plaintext. We describe concretely how to construct the proposed system over octonion ring. It is shown that proposed system is immune from “ciphertext square attack”, “m and -m attack” and the Gröbner basis attacks and the complexity to encipher and decipher is not large.

Published in International Journal of Information and Communication Sciences (Volume 3, Issue 2)
DOI 10.11648/j.ijics.20180302.15
Page(s) 50-65
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2018. Published by Science Publishing Group

Keywords

Two Ciphertexts, Ciphertext Square Attack, Fully Homomorphic Public-Key Encryption, Multivariate Algebraic Equation, Gröbner Basis, Non-associative Ring

References
[1] Craig Gentry. Fully Homomorphic Encryption Using Ideal Lattices.In the 41st ACM Symposium on Theory of Computing (STOC), 2009.
[2] Craig Gentry, A Fully Homomorphic Encryption Scheme, 2009. Available at http://crypto.stanford.edu/craig/craig-thesis.pdf.
[3] 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. Retrieved 2010-03-18.
[4] Damien Stehle; Ron Steinfeld (2010-05-19). "Faster Fully Homomorphic Encryption" (PDF). International Association for Cryptologic Research. Retrieved 2010-09-15.
[5] JS Coron, A Mandal, D Naccache, M Tibouchi ,” Fully homomorphic encryption over the integers with shorter public keys”, Advances in Cryptology–CRYPTO 2011, 487-504.
[6] Halevi, Shai. "An Implementation of homomorphic encryption". Retrieved 30 April 2013. Available at https://github.com/shaih/HElib .
[7] Nuida and Kurosawa,”(Batch) Fully Homomorphic Encryption over Integers for Non-Binary Message Spaces”, Cryptology ePrint Archive, Report 2014/777, 2014. http://eprint.iacr.org/.
[8] Masahiro, Y. (2015). Fully Homomorphic Encryption without bootstrapping. Saarbrücken/Germany: LAP LAMBERT Academic Publishing.
[9] Masahiro Yagisawa,” Fully Homomorphic Encryption without bootstrapping”, Cryptology ePrint Archive, Report 2015/474, 2015. http://eprint.iacr.org/.
[10] Yongge Wang,” Notes on Two Fully Homomorphic Encryption Schemes Without Bootstrapping”, Cryptology ePrint Archive, Report 2015/519, 2015. http://eprint.iacr.org/.
[11] Masahiro Yagisawa,” FHE with Recursive Ciphertext”, Cryptology ePrint Archive, Report 2017/198, 2017. http://eprint.iacr.org/.
[12] Masahiro Yagisawa,” Improved Fully Homomorphic Encryption without Bootstrapping”, Cryptology ePrint Archive, Report 2017/763, 2017. http://eprint.iacr.org/.
[13] Masahiro Yagisawa,” Fully homomorphic public-key encryption with small ciphertext size”, Cryptology ePrint Archive, Report 2018/088, 2018. http://eprint.iacr.org/.
[14] Shigeo Tsujii , Kohtaro Tadaki , Masahito Gotaishi ,Ryo Fujita ,and Masao Kasahara ,"Proposal Integrated MPKC:PPS—STS Enhanced Perturbed Piece in Hand Method—," IEICE Tech. Rep.ISEC2009-27,SITE2009-19,ICSS2009-41(2009-07),July 2009.
[15] T. Matsumoto, and H. Imai, “Public quadratic polynomial-tuples for efficient signature verification and message-encryption,” Lecture Notes in Computer Science on Advances in Cryptology-EUROCRYPT’88, pp.419–453, New York, NY, USA, 1988, Springer-Verlag New York, Inc.
[16] S. Tsujii, K. Tadaki, and R. Fujita, “Piece in hand concept for enhancing the security of multivariate type public key cryptosystems: Public key without containing all the information of secret key,” Cryptology ePrint Archive, Report 2004/366, 2004.
[17] C.Wolf, and B. Preneel, “Taxonomy of public key schemes based on the problem of multivariate quadratic equations,” Cryptology ePrint Archive, Report 2005/077, 2005, http://eprint.iacr.org/.
[18] M. Bardet, J. C. Faugere, and B. Salvy, "On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations," Proceeding of the International Conference on Polynomial System Solving (ICPSS2004), pp.71-75, November 2004.
[19] John H. Conway, Derek A. Smith co-authored, translated by Syuuji Yamada, "On Quaternions and Octonions " Baifuukan Publication Center, Tokyo, .2006.
Cite This Article
  • APA Style

    Masahiro Yagisawa. (2018). Fully Homomorphic Public-Key Encryption Against Ciphertext Square Attack with Two Ciphertexts. International Journal of Information and Communication Sciences, 3(2), 50-65. https://doi.org/10.11648/j.ijics.20180302.15

    Copy | Download

    ACS Style

    Masahiro Yagisawa. Fully Homomorphic Public-Key Encryption Against Ciphertext Square Attack with Two Ciphertexts. Int. J. Inf. Commun. Sci. 2018, 3(2), 50-65. doi: 10.11648/j.ijics.20180302.15

    Copy | Download

    AMA Style

    Masahiro Yagisawa. Fully Homomorphic Public-Key Encryption Against Ciphertext Square Attack with Two Ciphertexts. Int J Inf Commun Sci. 2018;3(2):50-65. doi: 10.11648/j.ijics.20180302.15

    Copy | Download

  • @article{10.11648/j.ijics.20180302.15,
      author = {Masahiro Yagisawa},
      title = {Fully Homomorphic Public-Key Encryption Against Ciphertext Square Attack with Two Ciphertexts},
      journal = {International Journal of Information and Communication Sciences},
      volume = {3},
      number = {2},
      pages = {50-65},
      doi = {10.11648/j.ijics.20180302.15},
      url = {https://doi.org/10.11648/j.ijics.20180302.15},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ijics.20180302.15},
      abstract = {A fully homomorphic public-key encryption (FHPKE) is the important cryptosystem as the basic scheme for the cloud computing. Since Gentry discovered in 2009 the first fully homomorphic encryption scheme, some fully homomorphic encryption schemes were proposed. In the systems proposed until now the bootstrapping process is the main bottleneck and the large complexity for computing the ciphertext is required. The existence of an efficient fully homomorphic cryptosystem would have great practical implications in the outsourcing of private computations, for instance, in the context of cloud computing. In recent year Yagisawa proposed fully homomorphic encryptions without bootstrapping which have the weak point in the enciphering function or not immune from “ciphertext square attack” which is the attack proposed in this article. In this article, a new FHPKE against “ciphertext square attack” is proposed which does not need the bootstrapping and does not require the large complexity for enciphering. The scheme has the following features; (a) its security bases on computational difficulty to solve the multivariate algebraic equations of high degrees; (b) it requires two ciphertexts corresponding to a plaintext. We describe concretely how to construct the proposed system over octonion ring. It is shown that proposed system is immune from “ciphertext square attack”, “m and -m attack” and the Gröbner basis attacks and the complexity to encipher and decipher is not large.},
     year = {2018}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - Fully Homomorphic Public-Key Encryption Against Ciphertext Square Attack with Two Ciphertexts
    AU  - Masahiro Yagisawa
    Y1  - 2018/10/08
    PY  - 2018
    N1  - https://doi.org/10.11648/j.ijics.20180302.15
    DO  - 10.11648/j.ijics.20180302.15
    T2  - International Journal of Information and Communication Sciences
    JF  - International Journal of Information and Communication Sciences
    JO  - International Journal of Information and Communication Sciences
    SP  - 50
    EP  - 65
    PB  - Science Publishing Group
    SN  - 2575-1719
    UR  - https://doi.org/10.11648/j.ijics.20180302.15
    AB  - A fully homomorphic public-key encryption (FHPKE) is the important cryptosystem as the basic scheme for the cloud computing. Since Gentry discovered in 2009 the first fully homomorphic encryption scheme, some fully homomorphic encryption schemes were proposed. In the systems proposed until now the bootstrapping process is the main bottleneck and the large complexity for computing the ciphertext is required. The existence of an efficient fully homomorphic cryptosystem would have great practical implications in the outsourcing of private computations, for instance, in the context of cloud computing. In recent year Yagisawa proposed fully homomorphic encryptions without bootstrapping which have the weak point in the enciphering function or not immune from “ciphertext square attack” which is the attack proposed in this article. In this article, a new FHPKE against “ciphertext square attack” is proposed which does not need the bootstrapping and does not require the large complexity for enciphering. The scheme has the following features; (a) its security bases on computational difficulty to solve the multivariate algebraic equations of high degrees; (b) it requires two ciphertexts corresponding to a plaintext. We describe concretely how to construct the proposed system over octonion ring. It is shown that proposed system is immune from “ciphertext square attack”, “m and -m attack” and the Gröbner basis attacks and the complexity to encipher and decipher is not large.
    VL  - 3
    IS  - 2
    ER  - 

    Copy | Download

Author Information
  • Yokohama-shi, Kanagawa-ken, Japan

  • Sections