A Survey on Homomorphic Encryption Schemes: Theory and Implementation: ACM Computing Surveys: Vol 51, No 4
FHE FHE implementation FHE survey Fully homomorphic encryption PHE SWHE homomorphic encryption partially homomorphic encryption somewhat homomorphic encryption
FL https: orcid.org FL View Profile Italy View Profile Abbas Acar Hidayet Aksu A. Selcuk Uluagac Mauro Conti UluagacA. Selcuk
Legacy encryption systems depend on sharing a key (public or private) among the peers
involved in exchanging an encrypted message. However, this approach poses privacy
concerns. The users or service providers with the key have exclusive rights on the
...
/pb-assets/head-metadata/apple-touch-icon-1574252172393.png
ACM Computing Surveys
survey

Public Access

A Survey on Homomorphic Encryption Schemes: Theory and Implementation

Abstract

Legacy encryption systems depend on sharing a key (public or private) among the peers involved in exchanging an encrypted message. However, this approach poses privacy concerns. The users or service providers with the key have exclusive rights on the data. Especially with popular cloud services, control over the privacy of the sensitive data is lost. Even when the keys are not shared, the encrypted material is shared with a third party that does not necessarily need to access the content. Moreover, untrusted servers, providers, and cloud operators can keep identifying elements of users long after users end the relationship with the services. Indeed, Homomorphic Encryption (HE), a special kind of encryption scheme, can address these concerns as it allows any third party to operate on the encrypted data without decrypting it in advance. Although this extremely useful feature of the HE scheme has been known for over 30 years, the first plausible and achievable Fully Homomorphic Encryption (FHE) scheme, which allows any computable function to perform on the encrypted data, was introduced by Craig Gentry in 2009. Even though this was a major achievement, different implementations so far demonstrated that FHE still needs to be improved significantly to be practical on every platform. Therefore, this survey focuses on HE and FHE schemes. First, we present the basics of HE and the details of the well-known Partially Homomorphic Encryption (PHE) and Somewhat Homomorphic Encryption (SWHE), which are important pillars for achieving FHE. Then, the main FHE families, which have become the base for the other follow-up FHE schemes, are presented. Furthermore, the implementations and recent improvements in Gentry-type FHE schemes are also surveyed. Finally, further research directions are discussed. This survey is intended to give a clear knowledge and foundation to researchers and practitioners interested in knowing, applying, and extending the state-of-the-art HE, PHE, SWHE, and FHE systems.

References

[1]

Nitesh Aggarwal, Cp Gupta, and Iti Sharma. 2014. Fully homomorphic symmetric scheme without bootstrapping. In 2014 International Conference on Cloud Computing and Internet of Things (CCIOT’14). IEEE, 14--17.

[2]

Carlos Aguilar-Melchor, Simon Fau, Caroline Fontaine, Guy Gogniat, and Renaud Sirdey. 2013. Recent advances in homomorphic encryption: A possible future for signal processing in the encrypted domain. IEEE Signal Processing Magazine 30, 2 (2013), 108--117.

[3]

S. Sobitha Ahila and K. L. Shunmuganathan. 2014. State Of art in homomorphic encryption schemes. International Journal of Engineering Research and Applications 4, 2 (2014), 37--43.

[4]

Miklós Ajtai. 1996. Generating hard instances of lattice problems. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing. ACM, 99--108.

[5]

Martin Albrecht, Shi Bai, and Léo Ducas. 2016. A subfield lattice attack on overstretched NTRU assumptions. In Annual Cryptology Conference. Springer, 153--178.

[6]

Martin Albrecht, Pooya Farshim, Jean-Charles Faugere, and Ludovic Perret. 2011. Polly cracker, revisited. Advances in Cryptology (ASIACRYPT’11), 179--196.

[7]

Martin R. Albrecht. 2017. On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 103--129.

[8]

Martin R. Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen, and Michael Zohner. 2015. Ciphers for MPC and FHE. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 430--454.

[9]

Jacob Alperin-Sheriff and Chris Peikert. 2013. Practical bootstrapping in quasilinear time. In Advances in Cryptology (CRYPTO’13). Springer, 1--20.

[10]

Jacob Alperin-Sheriff and Chris Peikert. 2014. Faster bootstrapping with polynomial error. In Advances in Cryptology (CRYPTO’14). Springer, 297--314.

[11]

Frederik Armknecht, Colin Boyd, Christopher Carr, Kristian Gjøsteen, Angela Jäschke, Christian A. Reuter, and Martin Strand. 2015. A guide to fully homomorphic encryption. IACR Cryptology ePrint Archive 2015 (2015), 1192.

[12]

Frederik Armknecht, Stefan Katzenbeisser, and Andreas Peter. 2013. Group homomorphic encryption: Characterizations, impossibility results, and applications. Designs, Codes and Cryptography 67, 2 (2013), 209--232.

[13]

Josh Benaloh. 1994. Dense probabilistic encryption. In Proceedings of the Workshop on Selected Areas of Cryptography. 120--128.

[14]

Josh Daniel Cohen Benaloh. 1987. Verifiable Secret-Ballot Elections. Yale University, Department of Computer Science.

[15]

Dan Boneh, Eu-Jin Goh, and Kobbi Nissim. 2005. Evaluating 2-DNF formulas on ciphertexts. In Theory of Cryptography. Springer, 325--341.

[16]

Joppe W. Bos, Kristin Lauter, Jake Loftus, and Michael Naehrig. 2013. Improved security for a ring-based fully homomorphic encryption scheme. In Cryptography and Coding. Springer, 45--64.

[17]

Zvika Brakerski. 2012. Fully homomorphic encryption without modulus switching from classical GapSVP. In Advances in Cryptology (CRYPTO’12). Springer, 868--886.

[18]

Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. 2011. Fully homomorphic encryption without bootstrapping. Cryptology ePrint Archive, Report 2011/277. Retrieved from http://eprint.iacr.org/.

[19]

Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. 2014. (Leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory 6, 3, Article 13 (July 2014), 36 pages.

[20]

Zvika Brakerski and Vinod Vaikuntanathan. 2011. Fully homomorphic encryption from ring-LWE and security for key dependent messages. In Advances in Cryptology (CRYPTO’11). Springer, 505--524.

[21]

Zvika Brakerski and Vinod Vaikuntanathan. 2014a. Efficient fully homomorphic encryption from (standard) LWE. SIAM Journal on Computing 43, 2 (2014), 831--871.

[22]

Zvika Brakerski and Vinod Vaikuntanathan. 2014b. Lattice-based FHE as secure as PKE. In Proceedings of the 5th Conference on Innovations in Theoretical Computer Science. ACM, 1--12.

[23]

Xiaolin Cao, Ciara Moore, Máire O’Neill, Elizabeth O’Sullivan, and Neil Hanley. 2013. Accelerating fully homomorphic encryption over the integers with super-size hardware multiplier and modular reduction. IACR Cryptology ePrint Archive 2013 (2013), 616.

[24]

Xiaolin Cao, Ciara Moore, Máire O’Neill, Neil Hanley, and Elizabeth OSullivan. 2014. High-speed fully homomorphic encryption over the integers. In Financial Cryptography and Data Security. Springer, 169--180.

[25]

Henry Carter, Benjamin Mood, Patrick Traynor, and Kevin Butler. 2013. Secure outsourced garbled circuit evaluation for mobile devices. Journal of Computer Security 24, 2 (2013), 137--180.

[26]

Henry Carter, Benjamin Mood, Patrick Traynor, and Kevin Butler. 2015. Outsourcing secure two-party computation as a black box. Security and Communication Networks 9, 14 (2015), 2261--2275.

[27]

Donald Donglong Chen, Nele Mentens, Frederik Vercauteren, Sujoy Sinha Roy, Ray C. C. Cheung, Derek Pao, and Ingrid Verbauwhede. 2015. High-speed polynomial multiplication architecture for ring-LWE and SHE cryptosystems. IEEE Transactions on Circuits and Systems I: Regular Papers, 62, 1 (2015), 157--166.

[28]

Hao Chen, Kim Laine, and Rachel Player. 2017. Simple Encrypted Arithmetic Library. Retrieved from https://www.microsoft.com/en-us/research/wp-content/uploads/2017/06/sealmanual_v2.2.pdf (accessed September 2017).

[29]

Liquan Chen, Hongmei Ben, and Jie Huang. 2014. An encryption depth optimization scheme for fully homomorphic encryption. In 2014 International Conference on Identification, Information and Knowledge in the Internet of Things (IIKI’14). IEEE, 137--141.

[30]

Yuanmi Chen and Phong Q. Nguyen. 2012. Faster algorithms for approximate common divisors: Breaking fully-homomorphic-encryption challenges over the integers. In Advances in Cryptology (EUROCRYPT’12). Springer, 502--519.

[31]

Zhigang Chen, Jian Wang, ZengNian Zhang, and Song Xinxia. 2014. A fully homomorphic encryption scheme with better key size. Communications, China 11, 9 (2014), 82--92.

[32]

Jung Hee Cheon, Jean-Sébastien Coron, Jinsu Kim, Moon Sung Lee, Tancrède Lepoint, Mehdi Tibouchi, and Aaram Yun. 2013. Batch fully homomorphic encryption over the integers. In Advances in Cryptology (EUROCRYPT’13). Springer, 315--335.

[33]

Jung Hee Cheon, Hyunsook Hong, Moon Sung Lee, and Hansol Ryu. 2016. The polynomial approximate common divisor problem and its application to the fully homomorphic encryption. Information Sciences 326 (2016), 41--58.

[34]

Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. 2016. Homomorphic encryption for arithmetic of approximate numbers (HEANN). Retrieved from https://github.com/kimandrik/HEAAN (accessed September 2017).

[35]

Jung Hee Cheon, Woo-Hwan Kim, and Hyun Soo Nam. 2006. Known-plaintext cryptanalysis of the domingo-ferrer algebraic privacy homomorphism scheme. Information Processing Letters 97, 3 (2006), 118--123.

[36]

Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. 2016. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. In Advances in Cryptology (ASIACRYPT’16): 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part I 22. Springer, 3--33.

[37]

Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. 2017. TFHE: Fast fully homomorphic encryption library over the Torus. Retrieved from https://github.com/tfhe/tfhe (accessed September 2017).

[38]

Su-Jeong Choi, Simon R. Blackburn, and Peter R. Wild. 2007. Cryptanalysis of a homomorphic public-key cryptosystem over a finite group. Journal of Mathematical Cryptology 1, 4 (2007), 351.

[39]

Ashish Choudhury, Jake Loftus, Emmanuela Orsini, Arpita Patra, and Nigel P. Smart. 2013. Between a rock and a hard place: Interpolating between MPC and FHE. In Advances in Cryptology (ASIACRYPT’13). Springer, 221--240.

[40]

Michael Clear and Ciarán McGoldrick. 2014. Bootstrappable identity-based fully homomorphic encryption. In Cryptology and Network Security. Springer, 1--19.

[41]

Michael Clear and Ciarán McGoldrick. 2015. Multi-identity and multi-key leveled FHE from learning with errors. In Annual Cryptology Conference. Springer, 630--656.

[42]

Michael Clear and Ciarán McGoldrick. 2016. Attribute-based fully homomorphic encryption with a bounded number of inputs. In International Conference on Cryptology in Africa. Springer, 307--324.

[43]

Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi. 2013. Batch fully homomorphic encryption over the integers. Cryptology ePrint Archive, Report 2013/036. Retrieved from http://eprint.iacr.org/.

[44]

Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi. 2014. Scale-invariant fully homomorphic encryption over the integers. In Public-Key Cryptography (PKC’14). Springer, 311--328.

[45]

Jean-Sébastien Coron, Avradip Mandal, David Naccache, and Mehdi Tibouchi. 2011. Fully homomorphic encryption over the integers with shorter public keys. In Advances in Cryptology (CRYPTO’11). Springer, 487--504.

[46]

Jean-Sébastien Coron, David Naccache, and Mehdi Tibouchi. 2012. Public key compression and modulus switching for fully homomorphic encryption over the integers. In Advances in Cryptology (EUROCRYPT’12). Springer, 446--464.

[47]

David Bruce Cousins, John Golusky, Kurt Rohloff, and Daniel Sumorok. 2014. An FPGA co-processor implementation of Homomorphic Encryption. In 2014 IEEE High Performance Extreme Computing Conference (HPEC’14). IEEE, 1--6.

[48]

David Bruce Cousins, Kathrin Rohloff, Chris Peikert, and Richard Schantz. 2012. An update on SIPHER (scalable implementation of primitives for homomorphic encryption) FPGA implementation using Simulink. In 2012 IEEE Conference on High Performance Extreme Computing (HPEC’12). IEEE, 1--5.

[49]

Ronald Cramer, Rosario Gennaro, and Berry Schoenmakers. 1997. A secure and optimally efficient multi-authority election scheme. Transactions on Emerging Telecommunications Technologies 8, 5 (1997), 481--490.

[50]

Wei Dai, Yarkın Doröz, and Berk Sunar. 2014. Accelerating NTRU based homomorphic encryption using GPUs. In 2014 IEEE High Performance Extreme Computing Conference (HPEC’14). IEEE, 1--6.

[51]

Wei Dai, Yarkın Doröz, and Berk Sunar. 2015. Accelerating SWHE based PIRs using GPUs. In International Conference on Financial Cryptography and Data Security. Springer, 160--171.

[52]

Wei Dai, Yarkın Doröz, and Berk Sunar. 2017. cuHE: Homomorphic and fast. Retrieved from https://github.com/vernamlab/cuHE (accessed September 2017).

[53]

Ivan Damgård and Mads Jurik. 2001. A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system. In Public Key Cryptography. Springer, 119--136.

[54]

Ivan Damgård, Valerio Pastro, Nigel Smart, and Sarah Zakarias. 2012. Multiparty computation from somewhat homomorphic encryption. In Advances in Cryptology (CRYPTO’12). Springer, 643--662.

[55]

Ivan Damgård, Antigoni Polychroniadou, and Vanishree Rao. 2016. Adaptively secure multi-party computation from LWE (via equivocal FHE). In Public-Key Cryptography (PKC’16). Springer, 208--233.

[56]

Whitfield Diffie and Martin E. Hellman. 1976. New directions in cryptography. IEEE Transactions on Information Theory 22, 6 (1976), 644--654.

[57]

Josep Domingo-Ferrer. 2002. A provably secure additive and multiplicative privacy homomorphism. In Information Security. Springer, 471--483.

[58]

Yarkın Doröz, Yin Hu, and Berk Sunar. 2014. Homomorphic AES evaluation using NTRU. IACR Cryptology ePrint Archive 2014 (2014), 39.

[59]

Yarkın Doröz, Erdinç Öztürk, Erkay Savaş, and Berk Sunar. 2015b. Accelerating LTV based homomorphic encryption in reconfigurable hardware. In Cryptographic Hardware and Embedded Systems (CHES’15). Springer, 185--204.

[60]

Yarkın Doröz, Erdinç Öztürk, and Berk Sunar. 2013. Evaluating the hardware performance of a million-bit multiplier. In 2013 Euromicro Conference on Digital System Design (DSD’13). IEEE, 955--962.

[61]

Yarkın Doröz, Erdinç Öztürk, and Berk Sunar. 2015a. Accelerating fully homomorphic encryption in hardware. IEEE Transactions on on Computers 64, 6 (2015), 1509--1521.

[62]

Yarkın Doröz, Aria Shahverdi, Thomas Eisenbarth, and Berk Sunar. 2014. Toward practical homomorphic evaluation of block ciphers using prince. In Financial Cryptography and Data Security. Springer, 208--220.

[63]

Yarkin Doröz and Berk Sunar. 2016. Flattening NTRU for evaluation key free homomorphic encryption. IACR Cryptology ePrint Archive 2016 (2016), 315.

[64]

Léo Ducas and Daniele Micciancio. 2014. A fully homomorphic encryption library. Retrieved from https://github.com/lducas/FHEW (accessed December 2015).

[65]

Léo Ducas and Daniele Micciancio. 2015. FHEW: Bootstrapping homomorphic encryption in less than a second. In Advances in Cryptology (EUROCRYPT’15). Springer, 617--640.

[66]

Taher ElGamal. 1985. A public key cryptosystem and a signature scheme based on discrete logarithms. In Advances in Cryptology. Springer, 10--18.

[67]

Junfeng Fan and Frederik Vercauteren. 2012a. Somewhat practical fully homomorphic encryption. IACR Cryptology ePrint Archive 2012 (2012), 144.

[68]

Junfeng Fan and Frederik Vercauteren. 2012b. Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, Report 2012/144. (2012). Retrieved from http://eprint.iacr.org/2012/144.

[69]

Michael Fellows and Neal Koblitz. 1994. Combinatorial cryptosystems galore&tilde; Contemporary Mathematics 168 (1994), 51--51.

[70]

Caroline Fontaine and Fabien Galand. 2007. A survey of homomorphic encryption for nonspecialists. EURASIP Journal on Information Security 2007 (2007), 15.

[71]

Matteo Frigo and Steven G. Johnson. 2005. The design and implementation of FFTW3. Proceedings of the IEEE 93, 2 (2005), 216--231. Special issue on “Program Generation, Optimization, and Platform Adaptation.”

[72]

Steven D. Galbraith. 2002. Elliptic curve paillier schemes. Journal of Cryptology 15, 2 (2002), 129--138.

[73]

Steven D. Galbraith, Shishay W. Gebregiyorgis, and Sean Murphy. 2016. Algorithms for the approximate common divisor problem. LMS Journal of Computation and Mathematics 19, A (2016), 58--72.

[74]

Craig Gentry. 2009. A Fully Homomorphic Encryption Scheme. Ph.D. Dissertation. Stanford University.

[75]

Craig Gentry. 2010. Toward basing fully homomorphic encryption on worst-case hardness. In Advances in Cryptology (CRYPTO’10). Springer, 116--137.

[76]

Craig Gentry. 2012. Personal communication.

[77]

Craig Gentry. 2014. Computing on the edge of chaos: Structure and randomness in encrypted computation. In Electronic Colloquium on Computational Complexity (ECCC’14), Vol. 21. 106.

[78]

Craig Gentry and Shai Halevi. 2011. Implementing gentrys fully-homomorphic encryption scheme. In Advances in Cryptology (EUROCRYPT’11). Springer, 129--148.

[79]

Craig Gentry, Shai Halevi, Chris Peikert, and Nigel P. Smart. 2012. Ring switching in BGV-style homomorphic encryption. In Security and Cryptography for Networks. Springer, 19--37.

[80]

Craig Gentry, Shai Halevi, and Nigel P. Smart. 2012. Homomorphic evaluation of the AES circuit. In Advances in Cryptology (CRYPTO’12). Springer, 850--867.

[81]

Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. 2010. A simple BGN-type cryptosystem from LWE. In Advances in Cryptology (EUROCRYPT’10). Springer, 506--522.

[82]

Craig Gentry, Amit Sahai, and Brent Waters. 2013. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. In Advances in Cryptology (CRYPTO’13). Springer, 75--92.

[83]

Kristian Gjøsteen. 2004. Subgroup membership problems and public key cryptosystems. PhD thesis, Norwegian University of Science and Technology.

[84]

Oded Goldreich, Shafi Goldwasser, and Shai Halevi. 1997. Public-key cryptosystems from lattice reduction problems. In Advances in Cryptology (CRYPTO’97). Springer, 112--131.

[85]

Shafi Goldwasser and Silvio Micali. 1982. Probabilistic encryption 8 how to play mental poker keeping secret all partial information. In Proceedings of the 14th Annual ACM Symposium on Theory of Computing. ACM, 365--377.

[86]

Dima Grigoriev and Ilia Ponomarenko. 2006. Homomorphic public-key cryptosystems and encrypting boolean circuits. Applicable Algebra in Engineering, Communication and Computing 17, 3--4 (2006), 239--255.

[87]

Shai Halevi and Nalini K. Ratha. 2011. Public challenges for fully-homomorphic encryption. Retrieved from http://researcher.watson.ibm.com/researcher/view_group.php?id&equal;1548 (accessed March 2016).

[88]

Shai Halevi and Victor Shoup. 2013a. Design and implementation of a homomorphic-encryption library. IBM Research (Manuscript).

[89]

Shai Halevi and Victor Shoup. 2013b. An implementation of homomorphic encryption. Retrieved from https://github.com/shaih/HElib (accessed December 2015).

[90]

Shai Halevi and Victor Shoup. 2014. Algorithms in helib. In Advances in Cryptology (CRYPTO’14). Springer, 554--571.

[91]

Shai Halevi and Victor Shoup. 2015. Bootstrapping for helib. In Advances in Cryptology (EUROCRYPT’15). Springer, 641--670.

[92]

Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. 1998. NTRU: A ring-based public key cryptosystem. In Algorithmic Number Theory. Springer, 267--288.

[93]

Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman, and Joseph H. Silverman. 2008. An Introduction to Mathematical Cryptography. Vol. 1. Springer.

[94]

Darko Hrestak and Stjepan Picek. 2014. Homomorphic encryption in the cloud. In 2014 37th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO’14). IEEE, 1400--1404.

[95]

Josep Domingo i Ferrer. 1996. A new privacy homomorphism and applications. Information Processing Letters 60, 5 (1996), 277--282.

[96]

Yuval Ishai and Anat Paskin. 2007. Evaluating branching programs on encrypted data. In Theory of Cryptography. Springer, 575--594.

[97]

Tibor Jager. 2012. The Generic Composite Residuosity Problem. Vieweg+Teubner Verlag, Wiesbaden, 49--56.

[98]

Burt Kaliski. 2005. Quadratic Residuosity Problem. Springer US, Boston, MA, 493--493.

[99]

Akinori Kawachi, Keisuke Tanaka, and Keita Xagawa. 2007. Multi-bit cryptosystems based on lattice problems. In Public Key Cryptography (PKC’07). Springer, 315--329.

[100]

Kevin S. McC. 1990. The discrete logarithm problem. Cryptology and Computational Number Theory 42 (1990), 49.

[101]

Jinsu Kim, Moon Sung Lee, Aaram Yun, and Jung Hee Cheon. 2013. CRT-based fully homomorphic encryption over the integers. IACR Cryptology ePrint Archive 2013 (2013), 57.

[102]

Eyal Kushilevitz and Rafail Ostrovsky. 1997. Replication is not needed: Single database, computationally-private information retrieval. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science. IEEE, 364.

[103]

Kim Laine, Hao Chen, and Rachel Player. 2017. Simple encrypted arithmetic library. Retrieved from https://sealcrypto.codeplex.com/ (accessed September 2017).

[104]

Van-Ly Le. 2003. Polly Two-a Public Key Cryptosystem Based on Polly Cracker. Ph.D. Dissertation. Ruhr University Bochum, Germany.

[105]

Moon Sung Lee. 2011. On the sparse subset sum problem from Gentry-Halevi’s implementation of fully homomorphic encryption. IACR Cryptology ePrint Archive 2011 (2011), 567.

[106]

Moon Sung Lee, Yongje Lee, Jung Hee Cheon, and Yunheung Paek. 2015. Accelerating bootstrapping in FHEW using GPUs. In 2015 IEEE 26th International Conference on Application-Specific Systems, Architectures and Processors (ASAP’15). IEEE, 128--135.

[107]

Arjen Klaas Lenstra, Hendrik Willem Lenstra, and László Lovász. 1982. Factoring polynomials with rational coefficients. Mathematische Annalen 261, 4 (1982), 515--534.

[108]

Tancrède Lepoint and Michael Naehrig. 2014. A comparison of the homomorphic encryption schemes FV and YASHE. In Progress in Cryptology (AFRICACRYPT’14). Springer, 318--335.

[109]

Françoise Levy-dit Vehel, Maria Grazia Marinari, Ludovic Perret, and Carlo Traverso. 2009. A survey on polly cracker systems. In Gröbner Bases, Coding, and Cryptography. Springer, 285--305.

[110]

Françoise Levy-dit Vehel and Ludovic Perret. 2004. A Polly cracker system based on satisfiability. Coding, Cryptography and Combinatorics, Progress in Computer Science and Applied Logic, vol. 23. Birkhäuser, Basel, 177--192.

[111]

Henry George Liddell and Robert Scott. 1896. An Intermediate Greek-English Lexicon: Founded upon the Seventh Edition of Liddell and Scott’s Greek-English Lexicon. Harper 8 Brothers.

[112]

Bingxin Liu and Huapeng Wu. 2015. Efficient architecture and implementation for NTRUEncrypt system. In 2015 IEEE 58th International Midwest Symposium on Circuits and Systems (MWSCAS’15). IEEE, 1--4.

[113]

Dongxi Liu. 2015. Practical fully homomorphic encryption without noise reduction. IACR Cryptology ePrint Archive 2015 (2015), 468.

[114]

Jake Loftus, Alexander May, Nigel P. Smart, and Frederik Vercauteren. 2011. On CCA-secure somewhat homomorphic encryption. In Selected Areas in Cryptography. Springer, 55--72.

[115]

Adriana López-Alt, Eran Tromer, and Vinod Vaikuntanathan. 2012. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing. ACM, 1219--1234.

[116]

Fujitsu Laboratories Ltd. 2013. Fujitsu develops world’s first homomorphic encryption technology that enables statistical calculations and biometric authentication. August 5, 2013. Retrieved from http://www.fujitsu.com/global/about/resources/news/press-releases/2013/0828-01.html.

[117]

Vadim Lyubashevsky, Chris Peikert, and Oded Regev. 2013. On ideal lattices and learning with errors over rings. Journal of the ACM (JACM) 60, 6 (2013), 43.

[118]

D. S. Malik, John N. Mordeson, and M. K. Sen. 2007. Fundamentals of abstract algebra. McGraw-Hill.

[119]

Robert McMillan. 2013. Apple finally reveals how long Siri keeps your data. April 2013. Retrieved from http://www.wired.com/2013/04/siri-two-years/.

[120]

Carlos Aguilar Melchor, Guilhem Castagnos, and Philippe Gaborit. 2008. Lattice-based homomorphic encryption of vector spaces. In IEEE International Symposium on Information Theory, 2008 (ISIT’08). IEEE, 1858--1862.

[121]

Carlos Aguilar Melchor, Philippe Gaborit, and Javier Herranz. 2010. Additively homomorphic encryption with d-operand multiplications. In Advances in Cryptology (CRYPTO’10). Springer, 138--154.

[122]

Silvia Mella and Ruggero Susella. 2013. On the homomorphic computation of symmetric cryptographic primitives. In Cryptography and Coding. Springer, 28--44.

[123]

Daniele Micciancio and Oded Regev. 2009. Lattice-based cryptography. In Post-Quantum Cryptography. Springer, 147--191.

[124]

Michal Mikuš. 2012. Experiments with the plaintext space in Gentry’s somewhat homomorphic scheme. Tatra Mountains Mathematical Publications 53, 1 (2012), 147--154.

[125]

Hermann Minkowski. 1968. Geometrie Der Zahlen. Vol. 40.

[126]

Peter L. Montgomery. 1994. A survey of modern integer factorization algorithms. CWI Quarterly 7, 4 (1994), 337--366.

[127]

Benjamin Mood, Debayan Gupta, Kevin Butler, and Joan Feigenbaum. 2014. Reuse it or lose it: More efficient secure computation through reuse of encrypted values. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. ACM, 582--596.

[128]

Ciara Moore, Neil Hanley, John McAllister, Máire O’Neill, Elizabeth O’Sullivan, and Xiaolin Cao. 2013. Targeting FPGA DSP slices for a large integer multiplier for integer based FHE. In Financial Cryptography and Data Security. Springer, 226--237.

[129]

Ciara Moore, Maire O’Neill, Neil Hanley, and Elizabeth O’Sullivan. 2014a. Accelerating integer-based fully homomorphic encryption using Comba multiplication. In 2014 IEEE Workshop on Signal Processing Systems (SiPS’14). IEEE, 1--6.

[130]

Ciara Moore, Maire O’Neill, Elizabeth O’Sullivan, Yarkın Doröz, and Berk Sunar. 2014b. Practical homomorphic encryption: A survey. In 2014 IEEE International Symposium on Circuits and Systems (ISCAS’14). IEEE, 2792--2795.

[131]

Gary L. Mullen and Peter Jau-Shyong Shiue. 1994. Finite Fields: Theory, Applications, and Algorithms. Vol. 168. American Mathematical Society.

[132]

David Naccache and Jacques Stern. 1998. A new public key cryptosystem based on higher residues. In Proceedings of the 5th ACM Conference on Computer and Communications Security. ACM, 59--66.

[133]

Michael Naehrig, Kristin Lauter, and Vinod Vaikuntanathan. 2011. Can homomorphic encryption be practical? In Proceedings of the 3rd ACM Workshop on Cloud Computing Security Workshop. ACM, 113--124.

[134]

Koji Nuida. 2014. A simple framework for noise-free construction of fully homomorphic encryption from a special class of non-commutative groups. IACR Cryptology ePrint Archive 2014 (2014), 97.

[135]

Koji Nuida and Kaoru Kurosawa. 2015. (Batch) fully homomorphic encryption over integers for non-binary message spaces. In Advances in Cryptology (EUROCRYPT’15). Springer, 537--555.

[136]

Naoki Ogura, Go Yamamoto, Tetsutaro Kobayashi, and Shigenori Uchiyama. 2010. An improvement of key generation algorithm for Gentrys homomorphic encryption scheme. In Advances in Information and Computer Security. Springer, 70--83.

[137]

Tatsuaki Okamoto and Shigenori Uchiyama. 1998. A new public-key cryptosystem as secure as factoring. In Advances in Cryptology (EUROCRYPT’98). Springer, 308--318.

[138]

E. Öztürk, Yarkın Doröz, Berk Sunar, and E. Savaş. 2015. Accelerating somewhat homomorphic evaluation u Using FPGAs. Technical Report. Cryptology ePrint Archive, Report 2015/294.

[139]

Pascal Paillier. 1999. Public-key cryptosystems based on composite degree residuosity classes. In Advances in Cryptology (Eurocrypt’99). Springer, 223--238.

[140]

Payal V. Parmar, Shraddha B. Padhar, Shafika N. Patel, Niyatee I. Bhatt, and Rutvij H. Jhaveri. 2014. Survey of various homomorphic encryption algorithms and schemes. International Journal of Computer Applications 91, 8 (2014).

[141]

Chris Peikert. 2015. A decade of lattice cryptography. Technical Report. Cryptology ePrint Archive, Report 2015/939.

[142]

Henning Perl, Michael Brenner, and Matthew Smith. 2011a. An implementation of the fully homomorphic smart-Vercauteren cryptosystem. Retrieved from https://github.com/hcrypt-project/libScarab (accessed December 2015).

[143]

Henning Perl, Michael Brenner, and Matthew Smith. 2011b. Poster: An implementation of the fully homomorphic smart-Vercauteren crypto-system. In Proceedings of the 18th ACM Conference on Computer and Communications Security. ACM, 837--840.

[144]

Pedro Silveira Pisa, Michel Abdalla, and Otto Carlos Duarte. 2012. Somewhat homomorphic encryption scheme for arithmetic operations on large integers. In 2012 Global Information Infrastructure and Networking Symposium (GIIS’12). IEEE, 1--8.

[145]

Thomas Pöppelmann, Michael Naehrig, Andrew Putnam, and Adrian Macias. 2015. Accelerating homomorphic evaluation on reconfigurable hardware. In Cryptographic Hardware and Embedded Systems (CHES’15). Springer, 143--163.

[146]

Sriram N. Premnath and Zygmunt J. Haas. 2014. A practical, secure, and verifiable cloud computing for mobile systems. Procedia Computer Science 34 (2014), 474--483.

[147]

Y. Govinda Ramaiah and G. Vijaya Kumari. 2012a. Efficient public key homomorphic encryption over integer plaintexts. In 2012 International Conference on Information Security and Intelligence Control (ISIC’12). IEEE, 123--128.

[148]

Y. Govinda Ramaiah and G. Vijaya Kumari. 2012b. Towards practical homomorphic encryption with efficient public key generation. International Journal on Network Security 3, 4 (2012), 10.

[149]

Oded Regev. 2006. Lattice-based cryptography. In Advances in Cryptology (CRYPTO’06). Springer, 131--141.

[150]

Oded Regev. 2009. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM) 56, 6 (2009), 34.

[151]

Ronald L. Rivest, Len Adleman, and Michael L. Dertouzos. 1978a. On data banks and privacy homomorphisms. Foundations of Secure Computation 4, 11 (1978), 169--180.

[152]

Ronald L. Rivest, Adi Shamir, and Len Adleman. 1978b. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM 21, 2 (1978), 120--126.

[153]

Kurt Rohloff. 2017. The PALISADE lattice cryptography library. Retrieved from https://git.njit.edu/palisade/PALISADE (accessed September 2017).

[154]

Kurt Rohloff and David Bruce Cousins. 2014. A scalable implementation of fully homomorphic encryption built on NTRU. In Financial Cryptography and Data Security. Springer, 221--234.

[155]

Ron Rothblum. 2011. Homomorphic encryption: From private-key to public-key. In Theory of Cryptography. Springer, 219--234.

[156]

Sujoy Sinha Roy, Kimmo Järvinen, Frederik Vercauteren, Vassil Dimitrov, and Ingrid Verbauwhede. 2015. Modular hardware architecture for somewhat homomorphic function evaluation. In International Workshop on Cryptographic Hardware and Embedded Systems. Springer, Berlin, Heidelberg, 164--184.

[157]

T. Sander, A. Young, and M. Yung. 1999. Non-interactive cryptocomputing for NC1. In 40th Annual Symposium on Foundations of Computer Science, 1999. 554--566.

[158]

Peter Scholl and Nigel P. Smart. 2011. Improved key generation for Gentry’s fully homomorphic encryption Scheme. In Cryptography and Coding. Springer, 10--22.

[159]

Jaydip Sen. 2013. Homomorphic encryption: Theory 8 applications. arXiv Preprint arXiv:1305.5886 (2013).

[160]

Alice Silverberg. 2013. Fully homomorphic encryption for mathematicians. Women in Numbers 2: Research Directions in Number Theory 606 (2013), 111.

[161]

N. P. Smart and F. Vercauteren. 2011. Fully homomorphic SIMD operations. Cryptology ePrint Archive, Report 2011/133. (2011). Retrieved from http://eprint.iacr.org/.

[162]

Nigel P. Smart and Frederik Vercauteren. 2010. Fully homomorphic encryption with relatively small key and ciphertext sizes. In Public Key Cryptography (PKC’10). Springer, 420--443.

[163]

Nigel P. Smart and Frederik Vercauteren. 2014. Fully homomorphic SIMD operations. Designs, Codes and Cryptography 71, 1 (2014), 57--81.

[164]

Damien Stehlé and Ron Steinfeld. 2010. Faster fully homomorphic encryption. In Advances in Cryptology (ASIACRYPT’10). Springer, 377--394.

[165]

Damien Stehlé and Ron Steinfeld. 2011. Making NTRU as secure as worst-case problems over ideal lattices. In Advances in Cryptology (EUROCRYPT’11). Springer, 27--47.

[166]

Rainer Steinwandt. 2010. A ciphertext-only attack on Polly Two. Applicable Algebra in Engineering, Communication and Computing 21, 2 (2010), 85--92.

[167]

Rainer Steinwandt and Willi Geiselmann. 2002. Cryptanalysis of Polly cracker. IEEE Transactions on Information Theory 48, 11 (2002), 2990--2991.

[168]

Zhou Tanping, Yang Xiaoyuan, Zhang Wei, and Wu Liqiang. 2015. Efficient fully homomorphic encryption with circularly secure key switching process. In International Journal of High Performance Computing and Networking 9, 5--6 (2015), 417--422.

[169]

Vinod Vaikuntanathan. 2011. Computing blindfolded: New developments in fully homomorphic encryption. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS’11). IEEE, 5--16.

[170]

Marten Van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. 2010. Fully homomorphic encryption over the integers. In Advances in Cryptology (EUROCRYPT’10). Springer, 24--43.

[171]

Le Van Ly. 2006. Polly two: A new algebraic polynomial-based public-key scheme. Applicable Algebra in Engineering, Communication and Computing 17, 3 (2006), 267--283.

[172]

David Wagner. 2003. Cryptanalysis of an algebraic privacy homomorphism. In Information Security. Springer, 234--239.

[173]

Fuqun Wang, Kunpeng Wang, and Bao Li. 2015a. An efficient leveled identity-based FHE. In Network and System Security. Springer, 303--315.

[174]

Fuqun Wang, Kunpeng Wang, and Bao Li. 2015b. LWE-based FHE with better parameters. In Advances in Information and Computer Security. Springer, 175--192.

[175]

Wei Wang, Zhilu Chen, and Xinming Huang. 2014. Accelerating leveled fully homomorphic encryption using GPU. In 2014 IEEE International Symposium on Circuits and Systems (ISCAS’14). IEEE, 2800--2803.

[176]

Wei Wang, Yin Hu, Lianmu Chen, Xinming Huang, and Berk Sunar. 2015. Exploring the feasibility of fully homomorphic encryption. IEEE Transactions on Computers 64, 3 (2015), 698--706.

[177]

Wei Wang and Xinming Huang. 2013. FPGA implementation of a large-number multiplier for fully homomorphic encryption. In 2013 IEEE International Symposium on Circuits and Systems (ISCAS’13). IEEE, 2589--2592.

[178]

Wei Wang, Xinming Huang, Niall Emmart, and Charles Weems. 2014. VLSI design of a large-number multiplier for fully homomorphic encryption. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 22, 9 (2014), 1879--1887.

[179]

Yongge Wang. Notes on two fully homomorphic encryption schemes without bootstrapping. Technical Report. Cryptology ePrint Archive, Report 2015/519, 2015. http://eprint.iacr.org.

[180]

David J. Wu. 2015. Fully homomorphic encryption: Cryptography’s holy grail. XRDS: Crossroads, The ACM Magazine for Students 21, 3 (2015), 24--29.

[181]

Ting Wu, Hui Wang, and You-Ping Liu. 2012. Optimizations of Brakerski’s fully homomorphic encryption scheme. In 2012 2nd International Conference on Computer Science and Network Technology (ICCSNT’12). IEEE, 2000--2005.

[182]

Masahiro Yagisawa. 2015. Fully homomorphic encryption without bootstrapping. IACR Cryptology ePrint Archive 2015 (2015), 474.

[183]

Hao-Miao Yang, Qi Xia, Xiao-fen Wang, and Dian-hua Tang. 2012. A new somewhat homomorphic encryption scheme over integers. In 2012 International Conference on Computer Distributed Control and Intelligent Environmental Monitoring (CDCIEM’12). IEEE, 61--64.

[184]

Andrew Chi-Chih Yao. 1982. Protocols for secure computations. In FOCS, Vol. 82. 160--164.

[185]

Xiaojun Zhang, Chunxiang Xu, Chunhua Jin, Run Xie, and Jining Zhao. 2014. Efficient fully homomorphic encryption from RLWE with an extension to a threshold encryption scheme. Future Generation Computer Systems 36 (2014), 180--186.

[186]

Zhenfei Zhang. 2014. Revisiting fully homomorphic encryption schemes and their cryptographic primitives. PhD thesis, University of Wollongong.

[187]

Yuliang Zheng, Tsutomu Matsumoto, and Hideki Imai. 1988. Cryptographic Applications of 7th-Residuosity Problem with 7 an Odd Integer. Yokohama National University, Japan.

Cited By

View all

Alsumayt AAlshammari MAlfawaer ZAl-Wesabi FEl-Haggar NAljameel SAlbassam SAlGhareeb SAlghamdi NAldossary NEfficient security level in wireless sensor networks (WSNs) using four-factors authentication over the Internet of Things (IoT)PeerJ Computer Science10.7717/peerj-cs.209110(e2091)

Choi GCha WLee SShin SSurvey of Medical Applications of Federated LearningHealthcare Informatics Research10.4258/hir.2024.30.1.330:1(3-15)

Kumar SSingh SGupta BPsannis KWu JHomomorphic Encryption in Smart City Applications for Balancing Privacy and UtilityInnovations in Modern Cryptography10.4018/979-8-3693-5330-1.ch010(241-269)

Show More Cited By

Index Terms

A Survey on Homomorphic Encryption Schemes: Theory and Implementation

Information systems

Data management systems

Data structures

Data layout

Data encryption

Security and privacy

Cryptography

Social and professional topics

Computing / technology policy

Computer crime

Theory of computation

Computational complexity and cryptography

Recommendations

On the CCA-1 security of somewhat homomorphic encryption over the integers

ISPEC'12: Proceedings of the 8th international conference on Information Security Practice and Experience

The notion of fully homomorphic encryption is very important since it enables many important applications, such as the cloud computing scenario. In EUROCRYPT 2010, van Dijk, Gentry, Halevi and Vaikuntanathan proposed an interesting fully homomorphic ...

Efficient fully homomorphic encryption with circularly secure key switching process

Fully homomorphic encryption (FHE) has important applications in cloud computing. However, almost all fully homomorphic encryption schemes share two common flaws that they all use large-scale secret keys and some operations are inefficient. In this paper,...

A Hybrid Scheme of Public-Key Encryption and Somewhat Homomorphic Encryption

We introduce a hybrid homomorphic encryption that combines public-key encryption (PKE) and somewhat homomorphic encryption (SHE) to reduce the storage requirements of most somewhat or fully homomorphic encryption (FHE) applications. In this model, ...

Information & Contributors

Information

Published In

765 pages

ISSN:0360-0300

EISSN:1557-7341

DOI:10.1145/3236632

Editor:

Sartaj Sahni

Department of Computer and Information Science and Engineering / University of Florida / Gainesville, FL 32611

Issue’s Table of Contents

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2018

Accepted: 01 April 2018

Revised: 01 March 2018

Received: 01 July 2016

Published in CSUR Volume 51, Issue 4

Permissions

Request permissions for this article.

Check for updates

Author Tags

FHE

FHE implementation

FHE survey

Fully homomorphic encryption

PHE

SWHE

homomorphic encryption

partially homomorphic encryption

somewhat homomorphic encryption

Qualifiers

Survey

Research

Refereed

Funding Sources

National Science Foundation

European Commission

NSF-CNS

EU TagItSmart! Project

EU-India REACH Project

Cisco University Research Program Fund and Silicon Valley Community Foundation

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

630

Total Citations

View Citations

20,812

Total Downloads

Downloads (Last 12 months)7,011

Downloads (Last 6 weeks)663

Other Metrics

Citations

Cited By

View all

Alsumayt AAlshammari MAlfawaer ZAl-Wesabi FEl-Haggar NAljameel SAlbassam SAlGhareeb SAlghamdi NAldossary NEfficient security level in wireless sensor networks (WSNs) using four-factors authentication over the Internet of Things (IoT)PeerJ Computer Science10.7717/peerj-cs.209110(e2091)

Choi GCha WLee SShin SSurvey of Medical Applications of Federated LearningHealthcare Informatics Research10.4258/hir.2024.30.1.330:1(3-15)

Kumar SSingh SGupta BPsannis KWu JHomomorphic Encryption in Smart City Applications for Balancing Privacy and UtilityInnovations in Modern Cryptography10.4018/979-8-3693-5330-1.ch010(241-269)

Rahaman MArya VOrozco SPappachan PSecure Multi-Party Computation (SMPC) Protocols and PrivacyInnovations in Modern Cryptography10.4018/979-8-3693-5330-1.ch008(190-214)

Ishtaiwi AAl Khaldy MAl-Qerem AAldweesh AAlmomani AArtificial Intelligence in Cryptographic EvolutionInnovations in Modern Cryptography10.4018/979-8-3693-5330-1.ch002(31-54)

Menandas J. JChristo MEffective Implementation of the Database Primitive Functions Through Homomorphic Encryption Over CloudMachine Learning and Cryptographic Solutions for Data Protection and Network Security10.4018/979-8-3693-4159-9.ch020(332-353)

Khan SPrivacy-Preserving Computing in the Healthcare Using Federated LearningAI-Driven Marketing Research and Data Analytics10.4018/979-8-3693-2165-2.ch015(263-280)

Jain NCherukuri AKamalov FRevisiting Fully Homomorphic Encryption Schemes for Privacy-Preserving ComputingEmerging Technologies and Security in Cloud Computing10.4018/979-8-3693-2081-5.ch012(276-294)

Shen CZhang WZhou TZhang LA Security-Enhanced Federated Learning Scheme Based on Homomorphic Encryption and Secret SharingMathematics10.3390/math1213199312:13(1993)

Arzovs AJudvaitis JNesenbergs KSelavo LDistributed Learning in the IoT–Edge–Cloud ContinuumMachine Learning and Knowledge Extraction10.3390/make60100156:1(283-315)

Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Sign in

Full Access

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Copied!

Copying failed.

Share on social media

Affiliations

Abbas Acar

Florida International University, USA, Miami, FL

Hidayet Aksu

Florida International University, USA, Miami, FL

A. Selcuk Uluagac

Florida International University, USA, Miami, FL

Mauro Conti

University of Padua, Padua, Italy

Request permissions Authors Info & Affiliations