Somewhat/fully homomorphic encryption: implementation progresses and challenges. (English) Zbl 1365.94407

El Hajji, Said (ed.) et al., Codes, cryptology and information security. Second international conference, C2SI 2017, Rabat, Morocco, April 10–12, 2017. Proceedings – in honor of Claude Carlet. Cham: Springer (ISBN 978-3-319-55588-1/pbk; 978-3-319-55589-8/ebook). Lecture Notes in Computer Science 10194, 68-82 (2017).
Summary: The proposed article aims, for readers, to learn about the existing efforts to secure and implement somewhat/fully homomorphic encryption ((S/F)HE) schemes and the problems to be tackled in order to progress toward their adoption. For that purpose, the article provides, at first, a brief introduction regarding (S/F)HE. Then, it focuses on some practical issues related to the adoption of (S/F)HE schemes, i.e. the security parameters, the existing implementations and their limitations, and the management of the huge complexity caused by homomorphic calculation. These issues are analyzed with the help of recent related work published in the literature, and with the experience gained by the authors through their experiments.
For the entire collection see [Zbl 1357.68009].


94A60 Cryptography
Full Text: DOI Link


[1] Albrecht, M., Bai, S., Ducas, L.: A subfield lattice attack on overstretched ntru assumptions: cryptanalysis of some fhe and graded encoding schemes. Cryptology ePrint Archive, Report 2016/127 (2016) · Zbl 1351.94019
[2] Aguilar-Melchor, C., Fau, S., Fontaine, C., Gogniat, G., Sirdey, R.: Recent advances in homomorphic encryption: a possible future for signal processing in the encrypted domain. IEEE Sig. Process. Mag. 30(2), 108–117 (2013)
[3] Melchor, C.A., Gaborit, P., Herranz, J.: Additively homomorphic encryption with d-operand multiplications. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 138–154. Springer, Heidelberg (2010). doi: 10.1007/978-3-642-14623-7_8 · Zbl 1280.94083
[4] Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptology 9(3), 169–203 (2015) · Zbl 1352.94023
[5] Albrecht, M.R., Rechberger, C., Schneider, T., Tiessen, T., Zohner, M.: Ciphers for MPC and FHE. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 430–454. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-46800-5_17 · Zbl 1370.94477
[6] Bajard, J.-C., Eynard, J., Hasan, A., Zucca, V.: A full RNS variant of FV like somewhat homomorphic encryption schemes. Cryptology ePrint Archive, Report 2016/510 (2016). http://eprint.iacr.org/2016/510 · Zbl 1418.94029
[7] Boneh, D., Goh, E.-J., Nissim, K.: Evaluating 2-DNF formulas on ciphertexts. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 325–341. Springer, Heidelberg (2005). doi: 10.1007/978-3-540-30576-7_18 · Zbl 1079.94534
[8] Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (leveled) fully homomorphic encryption without bootstrapping. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference - ITCS 2012, pp. 309–325. ACM (2012) · Zbl 1347.68120
[9] Bos, J.W., Lauter, K., Loftus, J., Naehrig, M.: Improved security for a ring-based fully homomorphic encryption scheme. In: Stam, M. (ed.) IMACC 2013. LNCS, vol. 8308, pp. 45–64. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-45239-0_4 · Zbl 1317.94088
[10] Barreto, P.S.L.M., Naehrig, M.: Pairing-friendly elliptic curves of prime order. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 319–331. Springer, Heidelberg (2006). doi: 10.1007/11693383_22 · Zbl 1151.94479
[11] Boneh, D.: The decision Diffie-Hellman problem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 48–63. Springer, Heidelberg (1998). doi: 10.1007/BFb0054851 · Zbl 1067.94523
[12] Bianchi, T., Piva, A., Barni, M.: On the implementation of the discrete Fourier transform in the encrypted domain. IEEE Trans. Inf. Forensics Secur. 4(1), 86–97 (2009)
[13] Brakerski, Z.: Fully homomorphic encryption without modulus switching from classical GapSVP. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 868–886. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-32009-5_50 · Zbl 1296.94091
[14] Brenner, M.: Hcrypt project. http://www.hcrypt.com
[15] Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (Standard) LWE. In: Proceedings of FOCS, pp. 97–106 (2011) · Zbl 1292.94038
[16] Brakerski, Z., Vaikuntanathan, V.: Lattice-based fhe as secure as pke. In: Proceedings of the 5th Conference on Innovations in Theoretical Computer Science - ITCS 2014, pp. 1–12. ACM (2014) · Zbl 1364.94528
[17] Canteaut, A., Carpov, S., Fontaine, C., Lepoint, T., Naya-Plasencia, M., Paillier, P., Sirdey, R.: Stream ciphers: a practical solution for efficient homomorphic-ciphertext compression. In: Peyrin, T. (ed.) FSE 2016. LNCS, vol. 9783, pp. 313–333. Springer, Heidelberg (2016). doi: 10.1007/978-3-662-52993-5_16 · Zbl 1387.94071
[18] 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: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 315–335. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-38348-9_20 · Zbl 1306.94040
[19] Carpov, S., Dubrulle, P., Sirdey, R.: Armadillo: a compilation chain for privacy preserving applications. In: Proceedings of the 3rd International Workshop on Security in Cloud Computing, pp. 13–19. ACM (2015)
[20] Catalano, D., Fiore, D.: Using linearly-homomorphic encryption to evaluate degree-2 functions on encrypted data. In: Ray, I., Li, N., Kruegel, C. (eds.) Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA, 12–16 October, pp. 1518–1529. ACM (2015)
[21] Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: Faster fully homomorphic encryption: bootstrapping in less than 0.1 seconds. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 3–33. Springer, Heidelberg (2016). doi: 10.1007/978-3-662-53887-6_1 · Zbl 1384.94044
[22] Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: A homomorphic LWE based e-voting scheme. In: Takagi, T. (ed.) PQCrypto 2016. LNCS, vol. 9606, pp. 245–265. Springer, Cham (2016). doi: 10.1007/978-3-319-29360-8_16 · Zbl 1405.81024
[23] Cao, X., Moore, C., O’Neill, M., Hanley, N., O’Sullivan, E.: High-speed fully homomorphic encryption over the integers. In: Böhme, R., Brenner, M., Moore, T., Smith, M. (eds.) FC 2014. LNCS, vol. 8438. Springer, Heidelberg (2014). doi: 10.1007/978-3-662-44774-1_14 · Zbl 06491630
[24] Coron, J.-S., Naccache, D., Tibouchi, M.: Public key compression and modulus switching for fully homomorphic encryption over the integers. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 446–464. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-29011-4_27 · Zbl 1297.94062
[25] Coron, J.-S.: An implementation of the DGHV fully homomorphic scheme. https://github.com/coron/fhe
[26] CryptoExperts: FV-NFLlib (2016). https://github.com/CryptoExperts/FV-NFLlib
[27] Dowlin, N., Gilad-Bachrach, R., Laine, K., Lauter, K., Naehrig, M., Wernsing, J.: Manual for using homomorphic encryption for bioinformatics. Technical report MSR-TR-2015-87, November 2015
[28] Doröz, Y., Yin, H., Sunar, B.: Homomorphic AES evaluation using NTRU. IACR Cryptology ePrint Archive 2014:39 (2014)
[29] Dinur, I., Liu, Y., Meier, W., Wang, Q.: Optimized interpolation attacks on LowMC. IACR Cryptology ePrint Archive 2015:418 (2015) · Zbl 1382.94092
[30] Duval, S., Lallemand, V., Rotella, Y.: Cryptanalysis of the FLIP family of stream ciphers. IACR Cryptology ePrint Archive (271) (2016) · Zbl 1384.94059
[31] Doroz, Y., Ozturk, E., Sunar, B.: Evaluating the hardware performance of a million-bit multiplier. In: Proceedings of Euromicro Conference on Digital System Design – DSD 2013 (2013)
[32] Doröz, Y., Sunar, B.: Flattening ntru for evaluation key free homomorphic encryption. Cryptology ePrint Archive, Report 2016/315 (2016)
[33] Doröz, Y., Shahverdi, A., Eisenbarth, T., Sunar, B.: Toward practical homomorphic evaluation of block ciphers using prince. In: Böhme, R., Brenner, M., Moore, T., Smith, M. (eds.) FC 2014. LNCS, vol. 8438, pp. 208–220. Springer, Heidelberg (2014). doi: 10.1007/978-3-662-44774-1_17 · Zbl 06491633
[34] ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theor. 31(4), 469–472 (1985) · Zbl 0571.94014
[35] Fontaine, C., Galand, F.: A survey of homomorphic encryption for nonspecialists. EURASIP J. Inf. Secur. 2007(1), 1–15 (2007) · Zbl 05735518
[36] Fouque, P.-A., Hadjibeyli, B., Kirchner, P.: Homomorphic evaluation of lattice-based symmetric encryption schemes. In: Dinh, T.N., Thai, M.T. (eds.) COCOON 2016. LNCS, vol. 9797, pp. 269–280. Springer, Cham (2016). doi: 10.1007/978-3-319-42634-1_22 · Zbl 1394.94931
[37] Freeman, D.M.: Converting pairing-based cryptosystems from composite-order groups to prime-order groups. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 44–61. Springer, Heidelberg (2010). doi: 10.1007/978-3-642-13190-5_3 · Zbl 1279.94074
[38] Fau, S., Sirdey, R., Fontaine, C., Aguilar-Melchor, C., Gogniat, G.: Towards practical program execution over fully homomorphic encryption schemes. In: Eighth International Conference on P2P, Parallel, Grid, Cloud and Internet Computing (3PGCIC), pp. 284–290. IEEE (2013)
[39] Fan, J., Vercauteren, F.: Somewhat practical fully homomorphic encryption. IACR Cryptology ePrint Archive 2012:144 (2012)
[40] Gentry, C.: A fully homomorphic encryption scheme. Ph.D. thesis, Stanford University (2009) · Zbl 1304.94059
[41] Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC, vol. 9, pp. 169–178 (2009) · Zbl 1304.94059
[42] Gentry, C., Halevi, S.: Fully homomorphic encryption without squashing using depth-3 arithmetic circuits. In: IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011), pp. 107–109. IEEE (2011) · Zbl 1292.94066
[43] Gentry, C., Halevi, S., Smart, N.P.: Fully homomorphic encryption with polylog overhead. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 465–482. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-29011-4_28 · Zbl 1297.94071
[44] Gentry, C., Halevi, S., Smart, N.P.: Homomorphic evaluation of the AES circuit. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 850–867. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-32009-5_49 · Zbl 1296.94117
[45] Graepel, T., Lauter, K., Naehrig, M.: ML confidential: machine learning on encrypted data. In: Kwon, T., Lee, M.-K., Kwon, D. (eds.) ICISC 2012. LNCS, vol. 7839, pp. 1–21. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-37682-5_1 · Zbl 1293.68110
[46] Gentry, C., Sahai, A., Waters, B.: Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 75–92. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-40041-4_5 · Zbl 1310.94148
[47] Halevi, S.: HElib. https://github.com/shaih/HElib
[48] Herbert, V., Fontaine, C.: Software Implementation of 2-Depth Pairing-based Homomorphic Encryption Scheme, Cryptology ePrint Archive, Report 2017/091 (2017). http://eprint.iacr.org/2017/091
[49] Kirchner, P., Fouque, P.-A.: Comparison between subfield and straightforward attacks on NTRU. Cryptology ePrint Archive, 2016/717 (2016)
[50] Khedr, A., Gulak, G., Vaikuntanathan, V.: SHIELD: scalable homomorphic implementation of encrypted data-classifiers. IEEE Trans. Comput. PP(99), 1 (2015) · Zbl 1360.68435
[51] Laine, K., Chen, H., Player, R.: Simple encrypted arithmetic library - seal (v2.1). Technical report, September 2016
[52] Lepoint, T.: A proof-of-concept implementation of the homomorphic evaluation of SIMON using FV and YASHE. https://github.com/tlepoint/homomorphic-simon · Zbl 1318.94071
[53] Lauter, K., López-Alt, A., Naehrig, M.: Private computation on encrypted genomic data. In: Aranha, D.F., Menezes, A. (eds.) LATINCRYPT 2014. LNCS, vol. 8895, pp. 3–27. Springer, Cham (2015). doi: 10.1007/978-3-319-16295-9_1 · Zbl 1378.94053
[54] Lepoint, T., Naehrig, M.: A comparison of the homomorphic encryption schemes FV and YASHE. In: Pointcheval, D., Vergnaud, D. (eds.) AFRICACRYPT 2014. LNCS, vol. 8469, pp. 318–335. Springer, Cham (2014). doi: 10.1007/978-3-319-06734-6_20 · Zbl 1318.94071
[55] Migliore, V., Bonnoron, G., Fontaine, C.: Determination and exploration of practical parameters for the latest somewhat homomorphic encryption (SHE) schemes. Working paper or preprint, October 2016
[56] Méaux, P., Journault, A., Standaert, F.-X., Carlet, C.: Towards stream ciphers for efficient FHE with low-noise ciphertexts. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 311–343. Springer, Heidelberg (2016). doi: 10.1007/978-3-662-49890-3_13 · Zbl 1384.94086
[57] Migliore, V., Real, M.M., Lapotre, V., Tisserand, A., Fontaine, C., Gogniat, G.: Hardware/software co-design of an accelerator for FV homomorphic encryption scheme using Karatsuba algorithm. IEEE Trans. Comput. (2017, accepted) · Zbl 1390.94850
[58] Naehrig, M., Lauter, K.E., Vaikuntanathan, V.: Can homomorphic encryption be practical? In: ACM CCSW, pp. 113–124. ACM (2011)
[59] Naehrig, M., Niederhagen, R., Schwabe, P.: New software speed records for cryptographic pairings. In: Abdalla, M., Barreto, P.S.L.M. (eds.) LATINCRYPT 2010. LNCS, vol. 6212, pp. 109–123. Springer, Heidelberg (2010). doi: 10.1007/978-3-642-14712-8_7 · Zbl 1285.94084
[60] Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999). doi: 10.1007/3-540-48910-X_16 · Zbl 0933.94027
[61] Peikert, C.: How (not) to instantiate ring-LWE. In: Zikas, V., Prisco, R. (eds.) SCN 2016. LNCS, vol. 9841, pp. 411–430. Springer, Cham (2016). doi: 10.1007/978-3-319-44618-9_22 · Zbl 1421.94066
[62] Pöppelmann, T., Naehrig, M., Putnam, A., Macias, A.: Accelerating homomorphic evaluation on reconfigurable hardware. In: Güneysu, T., Handschuh, H. (eds.) CHES 2015. LNCS, vol. 9293, pp. 143–163. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-48324-4_8 · Zbl 1380.94116
[63] Paindavoine, M., Vialla, B.: Minimizing the number of bootstrappings in fully homomorphic encryption. In: Dunkelman, O., Keliher, L. (eds.) SAC 2015. LNCS, vol. 9566, pp. 25–43. Springer, Cham (2016). doi: 10.1007/978-3-319-31301-6_2 · Zbl 1339.94057
[64] Rechberger, C.: The FHEMPCZK-Cipher Zoo. Presented at the FSE Rump Session (2016)
[65] Solinas, J.A.: Generalized mersenne prime. In: van Tilborg, H.C.A., Jajodia, S. (eds.) Encyclopedia of Cryptography and Security, pp. 509–510. Springer, New York (2011)
[66] Sinha Roy, S., Järvinen, K., Vercauteren, F., Dimitrov, V., Verbauwhede, I.: Modular hardware architecture for somewhat homomorphic function evaluation. In: Güneysu, T., Handschuh, H. (eds.) CHES 2015. LNCS, vol. 9293, pp. 164–184. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-48324-4_9 · Zbl 1380.94125
[67] Smart, N.P., Vercauteren, F.: Fully homomorphic encryption with relatively small key and ciphertext sizes. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 420–443. Springer, Heidelberg (2010). doi: 10.1007/978-3-642-13013-7_25 · Zbl 1281.94055
[68] Smart, N.P., Vercauteren, F.: Fully homomorphic simd operations. Des. Codes Crypt. 71(1), 57–81 (2014) · Zbl 1323.94140
[69] van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 24–43. Springer, Heidelberg (2010). doi: 10.1007/978-3-642-13190-5_2 · Zbl 1279.94130
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.