Experiments with the Plaintext Space in Gentry’S Somewhat Homomorphic Scheme

Mikuš, Michal

doi:10.2478/v10127-012-0044-6

Abstract

In this paper we propose an improvement of the implementation of the original Gentry-Halevi somewhat homomorphic scheme. We suggest to choose a bigger plaintext space, by changing the underlying ideal from I = (2) to I = (p) for some bigger prime p. Our analysis shows that bigger plaintext space will improve the homomorphic computation of the somewhat homomorphic scheme while it only slightly increases the complexity of the key generation procedure. The encryption and decryption functions have the same complexity. We provide also some experimental computations that support the analysis.

References

[1] AJTAI, M.-DWORK, C.: A public key cryptosystems with worst-case/average-case equivalence, in: Proc. of the 29th Annual ACM Symp. on Theory of Comput.-STOC ’97 (F. T. Leighton and P. Shor, eds.), El Paso, TX, USA, 1997, ACM, New York, NY, pp. 284-293.10.1145/258533.258604
Search in Google Scholar
[2] AHITUV, N.-LAPID, Y.-NEUMANN, S.: Processing encrypted data, Commun. ACM 30 (1987), 770-780.
Search in Google Scholar
[3] ARMKNECHT, F.-SADEGHI, A.: A new approach for algebraically homomorphic encryption, Cryptology ePrint Archive, Report 2008/422, 2008, http://eprint.iacr.org/2008/422.
Search in Google Scholar
[4] BAO, F.: Cryptanalysis of a provable secure additive and multiplicative privacy homo-morphism, in: Internat. Workshop on Coding and Cryptography-WCC ’03, Versailles, France, 2003, pp. 43-49.
Search in Google Scholar
[5] BONEH, D.-GOH, J.-NISSIM, K.: Evaluating 2-DNF formulas on ciphertexts, in: Theory of Cryptography, The 2nd Theory of Cryptography Conf.-TCC ’05 (J. Kilian, ed.), Cambridge, MA, USA, 2005, Lecture Notes in Comput. Sci., Vol. 3378, Springer, Berlin, 2005, pp. 325-342.
Search in Google Scholar
[6] CHUNSHENG, G.: New fully homomorphic encryption over the integers, Cryptology ePrint Archive, Report 2011/118, 2011, http://eprint.iacr.org/2011/118.
Search in Google Scholar
[7] VAN DIJK, M.-GENTRY, C.-HALEVI, S.-VAIKUNTANATHAN, V.: Fully homo-morphic encryption over the integers, in: Advances in Cryptology-EUROCRYPT ’10 (H. Gilbert, ed.), Lecture Notes in Comput. Sci., Vol. 6110, Springer, Berlin, 2010, pp. 24-43.
Search in Google Scholar
[8] GENTRY, C.: Fully homomorphic encryption using ideal lattices, in: Proc. of the 41st Annual ACM Symposium on Theory of Computing-STOC ’09, Bethesda, USA, 2009, ACM, New York, 2009, pp. 169-178.10.1145/1536414.1536440
Search in Google Scholar
[9] GENTRY, C.: A Fully Homomorphic Encryption Scheme. Dissertation Thesis, Standford University, Standford, 2009, http://crypto.stanford.edu/craig/.
Search in Google Scholar
[10] GOLDREICH, O.-GOLDWASSER, S.-HALEVI, S.: Public key cryptosystems from lattice reduction problems, in: Advances in Cryptology-CRYPTO ’97, The 17th Annual Internat. Cryptology Conf. (B. Kaliski, Jr., ed.), Santa Barbara, CA, USA, 1997, Lecture Notes in Comput. Sci., Vol. 1294, Springer, Berlin, 1997, pp. 112-131.
Search in Google Scholar
[11] GENTRY, C.-HALEVI, S.: Implementing Gentry’s fully-homomorphic encryption scheme, Cryptology ePrint Archive, Report 2010/520, 2010, http://eprint.iacr.org/2010/520.
Search in Google Scholar
[12] LOFTUS, C.-MAY, A.-SMART, N. P.-VERCAUTEREN, F.: On CCA-secure fully homomorphic encryption, Cryptology ePrint Archive, Report 2010/560, 2010, http://eprint.iacr.org/2010/560.
Search in Google Scholar
[13] LYUBASHEVSKY,V.-MICCIANCIO,D.: On bounded distance decoding, unique shortest vectors, and the minimum distance problem, in: Adv. in Cryptology-CRYPTO ’09, The 29th Annual Internat. Cryptology Conf. (S. Halevi, ed.), Santa Barbara, CA, USA, 2009, Lecture Notes in Comput. Sci., Vol. 5677, Springer, Berlin, 2009, pp. 577-594.
Search in Google Scholar
[14] MICCIANCIO, D.: Improving lattice based cryptosystems using the Hermite normal form, in: Cryptography and Lattices, The 1st Internat. Conf.-CaLC ’01 (J. H. Silverman, ed.), Providence, RI, USA, 2001, Lecture Notes in Comput. Sci., Vol. 2146, Springer, Berlin, 2001, pp. 126-145.
Search in Google Scholar
[15] MELCHOR, C.-GABORIT, P.-HERRANZ, J.: Additively homomorphic encryption with t-operand multiplications, Cryptology ePrint Archive, Report 2008/378, 2008, http://eprint.iacr.org/2008/378.
Search in Google Scholar
[16] RIVEST, R.-ADLEMAN, L.-DERTOUZOS, M.: On data banks and privacy homo-morphisms, in: Foundations of Secure Computation (R. DeMillo et al., eds.), Academic Press, New York, 1978, pp. 169-180.
Search in Google Scholar
[17] SMART, N. P.-VERCAUTEREN, F.: Fully homomorphic encryption with relatively small key and ciphertext sizes, Cryptology ePrint Archive, Report 2009/571, 2009, http://eprint.iacr.org/2009/571.
Search in Google Scholar

Experiments with the Plaintext Space in Gentry’S Somewhat Homomorphic Scheme

Abstract

Paradigm

My account