Practical homomorphic encryption over the integers for secure computation in the cloud

Acar, A., Aksu, H., Uluagac, A.S., Conti, M.: A survey on homomorphic encryption schemes: theory and implementation. ACM Comput. Surv. 51(4), 79:1–79:35 (2018). https://doi.org/10.1145/3214303 Aggarwal, N., Gupta, C., Sharma, I.: Fully homomorphic symmetric scheme without bootstrapping. In: Proceedings of 2014 International Conference on Cloud Computing and Internet of Things (CCIOT 2014), pp. 14–17 (2014). https://doi.org/10.1109/CCIOT.2014.7062497 Aguilar-Melchor, C., Killijian, M.O., Lefebvre, C., Lepoint, T., Ricosset, T.: A Comparison of open-source homomorphic libraries with multi-precision plaintext moduli (2016). WHEAT 2016. https://wheat2016.lip6.fr/ricosset.pdf Amazon Web Services, Inc.: Amazon EMR (2018). http://aws.amazon.com/elasticmapreduce/ Aumasson, J.P.: On the pseudo-random generator ISAAC. Cryptology ePrint Archive, Report 2006/438 (2006). https://eprint.iacr.org/2006/438 Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A Concrete security treatment of symmetric encryption. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS 1997), pp. 394–403. IEEE (1997). https://doi.org/10.1109/SFCS.1997.646128 Bellare, M., Desai, A., Pointcheval, D., Rogaway, P.: Relations among notions of security for public-key encryption schemes. In: Proceedings of the 18th Annual Cryptology Conference (CRYPTO 1998), pp. 26–45. Springer (1998). https://doi.org/10.1007/BFb0055718 Bellare, M., Hoang, V.T., Rogaway, P.: Foundations of garbled circuits. In: Proceedings of the 2012 ACM Conference on Computer and Communications Security (CCS 2012), pp. 784–796. ACM (2012). https://doi.org/10.1145/2382196.2382279 Bellare, M., Rogaway, P.: Introduction to modern cryptography. Lecture Notes (2005) Berlekamp, E.R.: Factoring polynomials over large finite fields. Math. Comput. 24(111), 713–735 (1970) Bernstein, D.J.: Post-Quantum Cryptography, Chap. Introduction to Post-quantum Cryptography, pp. 1–14. Springer, Berlin (2009). https://doi.org/10.1007/978-3-540-88702-7_1 Bogos, S., Gaspoz, J., Vaudenay, S.: Cryptanalysis of a homomorphic encryption scheme. Cryptology ePrint Archive, Report 2016/775 (2016). https://eprint.iacr.org/2016/775 Bogos, S., Gaspoz, J., Vaudenay, S.: Cryptanalysis of a homomorphic encryption scheme. Cryptogr. Commun. 10(1), 27–39 (2018). https://doi.org/10.1007/s12095-017-0243-8 Boneh, D., Shoup, V.: A Graduate Course in Applied Cryptography. Draft 0.2 (2015) Bonte, C., Bootland, C., Bos, J.W., Castryck, W., Iliashenko, I., Vercauteren, F.: Faster Homomorphic function evaluation using non-integral base encoding. Cryptology ePrint Archive, Report 2017/333 (2017). https://eprint.iacr.org/2017/333 Bos, J.W., Castryck, W., Iliashenko, I., Vercauteren, F.: Privacy-friendly forecasting for the smart grid using homomorphic encryption and the group method of data handling. Cryptology ePrint Archive, Report 2016/1117 (2016). https://eprint.iacr.org/2016/1117 Brakerski, Z.: Fully homomorphic encryption without modulus switching from classical GapSVP. In: Safavi-Naini, R., Canetti, R. (eds.) Proceedings of the 32nd Annual Cryptology Conference (CRYPTO 2012), pp. 868–886. Springer (2012). https://doi.org/10.1007/978-3-642-32009-5_50 Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Proceedings of the 3rd Conference on Innovations in Theoretical Computer Science (ITCS 2012), pp. 309–325. ACM (2012). https://doi.org/10.1145/2090236.2090262 Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011), pp. 97–106. IEEE (2011). https://doi.org/10.1109/FOCS.2011.12 Brakerski, Z., Vaikuntanathan, V.: Fully homomorphic encryption from ring-LWE and security for key dependent messages. In: Rogaway, P. (ed.) Proceedings of the 31st Annual Cryptology Conference (CRYPTO 2011), pp. 505–524. Springer (2011). https://doi.org/10.1007/978-3-642-22792-9_29 Catalano, D., Fiore, D.: Boosting linearly-homomorphic encryption to evaluate degree-2 functions on encrypted data. Cryptology ePrint Archive, Report 2014/813 (2014). https://eprint.iacr.org/2014/813 Catalano, D., Fiore, D.: Using linearly-homomorphic encryption to evaluate degree-2 functions on encrypted data. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security (CCS 2015), pp. 1518–1529. ACM (2015). https://doi.org/10.1145/2810103.2813624 Chen, L., Ben, H., Huang, J.: An encryption depth optimization scheme for fully homomorphic encryption. In: Proceedings of the 2014 International Conference on Identification, Information and Knowledge in the Internet of Things (IIKI 2014), pp. 137–141. IEEE (2014). https://doi.org/10.1109/IIKI.2014.35 Chen, Y., Nguyen, P.Q.: Faster algorithms for approximate common divisors: breaking fully-homomorphic-encryption challenges over the integers. In: D. Pointcheval, T. Johansson (eds.) Proceedings of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2012), pp. 502–519. Springer (2012). https://doi.org/10.1007/978-3-642-29011-4_30 Cheon, J.H., Coron, J., 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.) Proceedings of the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2013), pp. 315–335. Springer (2013). https://doi.org/10.1007/978-3-642-38348-9_20 Cheon, J.H., Kim, J., Lee, M.S., Yun, A.: CRT-based fully homomorphic encryption over the integers. Inf. Sci. 310, 149–162 (2015). https://doi.org/10.1016/j.ins.2015.03.019 Cheon, J.H., Stehlé, D.: Fully homomophic encryption over the integers revisited. In: Oswald, E., Fischlin, M. (eds.) Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2015), Part I, pp. 513–536. Springer (2015). https://doi.org/10.1007/978-3-662-46800-5_20 Cohn, H., Heninger, N.: Approximate common divisors via lattices. In: Proceedings of the 10th Algorithmic Number Theory Symposium (ANTS-X), vol. 1, pp. 271–293. Mathematical Sciences Publishers (2012). https://doi.org/10.2140/obs.2013.1.271 Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Cryptol. 10(4), 233–260 (1997). https://doi.org/10.1007/s001459900030 Coron, J., Lepoint, T., Tibouchi, M.: Scale-invariant fully homomorphic encryption over the integers. In: Krawczyk, H. (ed.) Proceedings of the 17th International Conference on Practice and Theory in Public-Key Cryptography (PKC 2014), pp. 311–328. Springer (2014). https://doi.org/10.1007/978-3-642-54631-0_18 Coron, J., Mandal, A., Naccache, D., Tibouchi, M.: Fully homomorphic encryption over the integers with shorter public keys. In: Rogaway, P. (ed.) Proceedings of the 31st Annual Cryptology Conference (CRYPTO 2011), pp. 487–504. Springer (2011). https://doi.org/10.1007/978-3-642-22792-9_28 Coron, J., Naccache, D., Tibouchi, M.: Public key compression and modulus switching for fully homomorphic encryption over the integers. In: Pointcheval, D., Johansson, T. (eds.) Proceedings of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2012), pp. 446–464. Springer (2012). https://doi.org/10.1007/978-3-642-29011-4_27 CryptoExperts: FV-NFLib. https://github.com/CryptoExperts/FV-NFLlib Dautelle, J.M.: JScience (2014). http://jscience.org van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Proceedings of the 29th Annual International Conference on Theory and Applications of Cryptographic Techniques (EUROCRYPT 2010), pp. 24–43. Springer (2010). https://doi.org/10.1007/978-3-642-13190-5_2 van Dijk, M., Juels, A.: On the impossibility of cryptography alone for privacy-preserving cloud computing. In: Proceedings of the 5th USENIX Workshop on Hot Topics in Security (HotSec 2010), pp. 1–8. USENIX Association (2010). https://www.usenix.org/legacy/events/hotsec10/tech/full_papers/vanDijk.pdf Ducas, L., Micciancio, D.: FHEW: Bootstrapping homomorphic encryption in less than a second. In: Oswald, E. , Fischlin, M. (eds.) Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2015), Part I, pp. 617–640. Springer (2015). https://doi.org/10.1007/978-3-662-46800-5_24 Ducas, L., Micciancio, D.: FHEW (2017). https://github.com/lducas/FHEW Dyer, J., Dyer, M., Xu, J.: Practical Homomorphic Encryption Over the Integers for Secure Computation in the Cloud. In: O’Neill, M. (ed.) Proceedings of the 16th IMA International Conference on Cryptography and Coding (IMACC 2017), Lecture Notes in Computer Science, vol. 10655, pp. 44–76. Springer (2017). https://doi.org/10.1007/978-3-319-71045-7_3 ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 31(4), 469–472 (1985). https://doi.org/10.1109/TIT.1985.1057074 Erkin, Z., Franz, M., Guajardo, J., Katzenbeisser, S., Lagendijk, I., Toft, T.: Privacy-preserving face recognition. In: Goldberg, I., Atallah, M.J. (eds.) Proceedings of the 9th International Symposium on Privacy Enhancing Technologies (PETS 2009), pp. 235–253. Springer (2009). https://doi.org/10.1007/978-3-642-03168-7_14 Fan, J., Vercauteren, F.: Somewhat Practical Fully Homomorphic Encryption. Cryptology ePrint Archive, Report 2012/144 (2012). https://eprint.iacr.org/2012/144 Galbraith, S.D., Gebregiyorgis, S.W., Murphy, S.: Algorithms for the approximate common divisor problem. LMS J. Comput. Math. 19(A), 58–72 (2016). https://doi.org/10.1112/S1461157016000218 Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC 2009), pp. 169–178. ACM (2009). https://doi.org/10.1145/1536414.1536440 Goldreich, O., Micali, S., Wigderson, A.: How to play ANY mental game. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC 1987), pp. 218–229. ACM (1987). https://doi.org/10.1145/28395.28420 Goldwasser, S., Kalai, Y., Popa, R.A., Vaikuntanathan, V., Zeldovich, N.: Reusable garbled circuits and succinct functional encryption. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC 2013), pp. 555–564. ACM (2013). https://doi.org/10.1145/2488608.2488678 Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270–299 (1984). https://doi.org/10.1016/0022-0000(84)90070-9 Halevi, S., Shoup, V.: HELib. https://github.com/shaih/HElib Halevi, S., Shoup, V.: Bootstrapping for HELib. In: Oswald, E., Fischlin, M. (eds.) Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2015), pp. 641–670. Springer (2015). https://doi.org/10.1007/978-3-662-46800-5_25 Howgrave-Graham, N.: Approximate integer common divisors. In: Revised Papers from the International Conference on Cryptography and Lattices (CaLC 2001), pp. 51–66. Springer (2001). https://doi.org/10.1007/3-540-44670-2_6 Hrubeš, P., Yehudayoff, A.: Arithmetic complexity in algebraic extensions. Theory Comput. 7, 119–129 (2011) Jenkins, B.: ISAAC: a fast cryptographic random number generator (1996). http://burtleburtle.net/bob/rand/isaacafa.html Joye, M., Libert, B.: Efficient cryptosystems from \(2^k\)-th power residue symbols. In: Proceedings of the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2013), pp. 76–92. Springer (2013). https://doi.org/10.1007/978-3-642-38348-9_5 Kipnis, A., Hibshoosh, E.: Efficient methods for practical fully homomorphic symmetric-key encrypton, randomization and verification. Cryptology ePrint Archive, Report 2012/637 (2012). https://eprint.iacr.org/2012/637 Kleinjung, T., Aoki, K., Franke, J., Lenstra, A.K., Thomé, E., Bos, J.W., Gaudry, P., Kruppa, A., Montgomery, P.L., Osvik, D.A., Te Riele, H., Timofeev, A., Zimmermann, P.: Factorization of a 768-bit RSA Modulus. In: Proceedings of the 30th Annual Cryptology Conference (CRYPTO 2010), pp. 333–350. Springer (2010). https://doi.org/10.1007/978-3-642-14623-7_18 Laine, K., Chen, H., Player, R., Wernsing, J., Naehrig, M., Dowlin, N., Cetin, G., Xia, S., Rindal, P.: Simple Encrypted Arithmetic Library—SEAL (2017). https://sealcrypto.codeplex.com/ Lauter, K., Naehrig, M., Vaikuntanathan, V.: Can homomorphic encryption be practical? In: Proceedings of the 3rd ACM Workshop on Cloud Computing Security Workshop (CCSW 2011), pp. 113–124. ACM (2011). https://doi.org/10.1145/2046660.2046682 Massey, J.L.: Guessing and entropy. In: Proceedings of 1994 IEEE International Symposium on Information Theory (ISIT 1994), p. 204. IEEE (1994). https://doi.org/10.1109/ISIT.1994.394764 Microsoft: HDInsight (2018). http://azure.microsoft.com/en-gb/services/hdinsight/ Microsoft: Microsoft Azure for Research (2018). https://www.microsoft.com/en-us/research/academic-program/microsoft-azure-for-research/ Moshkovitz, D.: An Alternative Proof of the Schwartz–Zippel Lemma. In: Electronic Colloquium on Computational Complexity (ECCC), p. 96 (2010) Nuida, K., Kurosawa, K.: (Batch) Fully homomorphic encryption over integers for non-binary message spaces. Cryptology ePrint Archive, Report 2014/777 (2014). https://eprint.iacr.org/2014/777 Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) Proceedings of the 18th International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT 1999), pp. 223–238. Springer (1999). https://doi.org/10.1007/3-540-48910-X_16 Pisa, P.S., Abdalla, M., Duarte, O.C.M.B.: Somewhat homomorphic encryption scheme for arithmetic operations on large integers. In: Proceedings of the 2012 Global Information Infrastructure and Networking Symposium (GIIS 2012), pp. 1–8. IEEE (2012). https://doi.org/10.1109/GIIS.2012.6466769 Popa, R.A., Redfield, C., Zeldovich, N., Balakrishnan, H.: CryptDB: Protecting Confidentiality with Encrypted Query Processing. In: Proceedings of the 23rd ACM Symposium on Operating Systems Principles (SOSP 2011), pp. 85–100. ACM (2011). https://doi.org/10.1145/2043556.2043566 Rabin, M.O.: Digitalized signatures and public-key functions as intractable as factorization. Technical Report MIT/LCS/TR-212, MIT (1979) Ramaiah, Y.G., Kumari, G.V.: Efficient public key homomorphic encryption over integer plaintexts. In: Proceedings of the 2012 International Conference on Information Security and Intelligent Control, pp. 123–128 (2012). https://doi.org/10.1109/ISIC.2012.6449723 Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005), pp. 84–93. ACM (2005). https://doi.org/10.1145/1060590.1060603 Ricosset, T.: HElib-MP. https://github.com/tricosset/HElib-MP Rivest, R.L., Adleman, L., Dertouzos, M.L.: On data banks and privacy homomorphisms. Found. Secure Comput. 4(11), 169–180 (1978) Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978). https://doi.org/10.1145/359340.359342 Schafer, R.D.: An Introduction to Nonassociative Algebras, vol. 22. Dover, Mineola (1966) Scharle, T.W.: Axiomatization of propositional calculus with sheffer functors. Notre Dame J. Formal Logic 6(3), 209–217 (1965). https://doi.org/10.1305/ndjfl/1093958259 Smart, N.P., Vercauteren, F.: Fully homomorphic encryption with relatively small key and ciphertext sizes. In: Proceedings of the 13th International Conference on Practice and Theory in Public Key Cryptography (PKC 2010), pp. 420–443. Springer (2010). https://doi.org/10.1007/978-3-642-13013-7_25 Smart, N.P., Vercauteren, F.: Fully homomorphic SIMD operations. Des. Codes Cryptogr. 71(1), 57–81 (2014). https://doi.org/10.1007/s10623-012-9720-4 Stephen, J.J., Savvides, S., Seidel, R., Eugster, P.: Practical confidentiality preserving big data analysis. In: Proceedings of the 6th USENIX Workshop on Hot Topics in Cloud Computing (HotCloud 14). USENIX Association (2014). https://www.usenix.org/conference/hotcloud14/workshop-program/presentation/stephen Tetali, S.D., Lesani, M., Majumdar, R., Millstein, T.: MrCrypt: static analysis for secure cloud computations. In: Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages & Applications (OOPSLA 2013), pp. 271–286. ACM (2013). https://doi.org/10.1145/2509136.2509554 Thomson, I.: Microsoft researchers smash homomorphic encryption speed barrier. The Register (2016). https://www.theregister.co.uk/2016/02/09/researchers_break_homomorphic_encryption/ Varia, M., Yakoubov, S., Yang, Y.: HETest: A homomorphic encryption testing framework. Cryptology ePrint Archive, Report 2015/416 (2015). https://eprint.iacr.org/2015/416 Vivek, S.: Homomorphic encryption API software library. http://heat-h2020-project.blogspot.co.uk/2017/02/homomorphic-encryption-api-software.html Vizár, D., Vaudenay, S.: Cryptanalysis of chosen symmetric homomorphic schemes. Stud. Sci. Math. Hung. 52(2), 288–306 (2015). https://doi.org/10.1556/012.2015.52.2.1311 Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach. Springer, Berlin (1999) Wang, D., Guo, B., Shen, Y., Cheng, S.J., Lin, Y.H.: A faster fully homomorphic encryption scheme in big data. In: Proceedings of the 2017 IEEE 2nd International Conference on Big Data Analysis (ICBDA 2017), pp. 345–349 (2017). https://doi.org/10.1109/ICBDA.2017.8078836 Yu, A., Lai, W.L., Payor, J.: Efficient integer vector homomorphic encryption (2015). https://courses.csail.mit.edu/6.857/2015/files/yu-lai-payor.pdf Zhou, H., Wornell, G.: Efficient homomorphic encryption on integer vectors and its applications. In: Proceedings of the 2014 Information Theory and Applications Workshop (ITA 2014), pp. 1–9. IEEE (2014). https://doi.org/10.1109/ITA.2014.6804228