×
Marinelli, Franca; Aragona, Riccardo; Marcolla, Chiara; Sala, Massimiliano

Some security bounds for the key sizes of DGHV scheme. (English) Zbl 1315.94091

Appl. Algebra Eng. Commun. Comput. 25, No. 5, 383-392 (2014).
Summary: The correctness in decrypting a ciphertext after some operations in the DGVH scheme (after van Dijk, Gentry, Halevi, Vaikuntanathan) [M. van Dijk et al., Eurocrypt 2010, Lect. Notes Comput. Sci. 6110, 24–43 (2010; Zbl 1279.94130)] depends heavily on the dimension of the secret key. In this paper we compute two bounds on the size of the secret key for the DGHV scheme to decrypt correctly a ciphertext after a fixed number of additions and a fixed number of multiplication. Moreover we improve the original bound on the dimension of the secret key for a general circuit.

Cited in 1 Document

MSC:

94A60 Cryptography

Keywords:

public-key cryptography; fully homomorphic encryption; somewhat homomorphic encryption; DGVH scheme

Citations:

Zbl 1279.94130

Software:

fhe
Cite Review PDF
Full Text: DOI Link

References:

[1] Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pp. 309-325. ACM (2012) · Zbl 1347.68120
[2] Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science—FOCS 2011, pp. 97-106. IEEE Computer Society, Los Alamitos (2011) · Zbl 1292.94038
[3] Brakerski, Z., Vaikuntanathan, V.: Fully homomorphic encryption from ring-LWE and security for key dependent messages. In: Advances in cryptology—CRYPTO 2011, Lecture Notes in Computer Science, vol. 6841, pp. 505-524. Springer, Heidelberg (2011) · Zbl 1290.94051
[4] Cheon, J.H., Coron, J.S., Kim, J., Lee, M.S., Lepoint, T., Tibouchi, M., Yun, A.: Batch fully homomorphic encryption over the integers. In: Advances in Cryptology-EUROCRYPT 2013, pp. 315-335. Springer, Heidelberg (2013) · Zbl 1306.94040
[5] Coron, J.S., Mandal, A., Naccache, D., Tibouchi, M.: Fully homomorphic encryption over the integers with shorter public keys. In: Advances in Cryptology—CRYPTO 2011, Lecture Notes in Computer Science, vol. 6841, pp. 487-504. Springer, Heidelberg (2011) · Zbl 1290.94059
[6] Dijk, M.v., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Advances in Cryptology—EUROCRYPT 2010, Lecture Notes in Computer Science, vol. 6110, pp. 24-43. Springer, Berlin (2010) · Zbl 1279.94130
[7] Gentry, C.: A Fully Homomorphic Encryption Scheme. Ph.D. thesis, Stanford University (2009) · Zbl 1304.94059
[8] Gentry, C.: Computing arbitrary functions of encrypted data. Commun. ACM 53(3), 97-105 (2010). doi:10.1145/1666420.1666444 · Zbl 1315.94074 · doi:10.1145/1666420.1666444
[9] Gentry, C., Halevi, S.: Implementing Gentry’s fully-homomorphic encryption scheme. In: Advances in Cryptology—EUROCRYPT 2011, Lecture Notes in Computer Science, vol. 6632, pp. 129-148. Springer, Heidelberg (2011) · Zbl 1281.94026
[10] Gentry, C., Halevi, S., Smart, N.P.: Fully homomorphic encryption with polylog overhead. In: Advances in Cryptology—EUROCRYPT 2012, Lecture Notes in Computer Science, vol. 7237, pp. 465-482. Springer, Heidelberg (2012) · Zbl 1297.94071
[11] Naehrig, M., Lauter, K., Vaikuntanathan, V.: Can homomorphic encryption be practical? In: Proceedings of the 3rd ACM Workshop on Cloud Computing Security Workshop, pp. 113-124. ACM (2011)
[12] Silverberg, A.: Fully homomorphic encryption for mathematicians. IACR Cryptol. ePrint Arch. 2013, 250 (2013) · Zbl 1297.94103
[13] Smart, N.P., Vercauteren, F.: Fully homomorphic encryption with relatively small key and ciphertext sizes. In: Public Key Cryptography—PKC 2010, Lecture Notes in Computer Science, vol. 6056, pp. 420-443. Springer, Berlin (2010) · Zbl 1281.94055
[14] Vaikuntanathan, V.: Computing blindfolded: new developments in fully homomorphic encryption. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science—FOCS 2011, pp. 5-16. IEEE Computer Society, Los Alamitos, CA (2011) · Zbl 1292.94145
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.