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. 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 permissions@acm.org.  In ancient Greek, the term (homos) was used to mean "same," while (morphe) was used for "shape" (Liddell and Scott 1896). Then the term homomorphism was coined and used in different areas. In abstract algebra, homomorphism is defined as a map preserving all the algebraic structures between the domain and range of an algebraic set (Malik et al. 2007 ). The map is simply a function, i.e., an operation, that takes the inputs from the set of domains and outputs an element in the range (e.g., addition, multiplication). In the cryptography field, homomorphism is used as an encryption type. Homomorphic Encryption (HE) is a kind of encryption scheme that allows a third party (e.g., cloud, service provider) to perform certain computable functions on the encrypted data while preserving the features of the function and format of the encrypted data. Indeed, this homomorphic encryption corresponds to a mapping in the abstract algebra. As an example for an additively HE scheme, for sample messages m 1 and m 2 , one can obtain E (m 1 + m 2 ) by using E (m 1 ) and E (m 2 ) without knowing m 1 and m 2 explicitly, where E denotes the encryption function. Normally, encryption is a crucial mechanism to preserve the privacy of any sensitive information. However, the conventional encryption schemes cannot work on the encrypted data without decrypting it first. In other words, the users have to sacrifice their privacy to make use of cloud services such as file storing, sharing, and collaboration. Moreover, untrusted servers, providers, and popular cloud operators can keep physically identifying elements of users long after users end the relationship with the services (McMillan 2013 ). This is a major privacy concern for users. In fact, it would be perfect if there existed a scheme that would not restrict the operations to be computed on the encrypted data while it would be still encrypted. From a historical perspective in cryptology, the term homomorphism was used for the first time by Rivest et al. (1978a) in 1978 as a possible solution to the computing without decrypting problem. This given basis in Rivest et al. (1978a) has led to numerous attempts by researchers around the world to design such a homomorphic scheme with a large set of operations. In this work, the primary motivation is to survey the HE schemes focusing on the most recent improvements in this field, including partially, somewhat, and fully HE schemes. A simple motivational HE example for a sample cloud application is illustrated in Figure 1 . In this scenario, the client, C, first encrypts his or her private data (Step 1), then sends the encrypted data to the cloud servers, S, (Step 2). When the client wants to perform a function (i.e., query), f (), over his or her own data, he or she sends the function to the server (Step 3). The server performs a homomorphic operation over the encrypted data using the Eval function, i.e., computes f () blindfolded (Step 4) and returns the encrypted result to the client (Step 5). Finally, the client recovers the data with his or her own secret key and obtains f (m) (Step 6). As seen in this simple example, the homomorphic operation, Eval (), at the server side does not require the private key of the client and allows various operations such as addition and multiplication on the encrypted client data. An early attempt to compute functions/operations on encrypted data is Yao's garbled circuit 1 study (Yao 1982) . Yao proposed a two-party communication protocol as a solution to the
A comprehensive survey of partial, somewhat, and fully HE schemes is presented in REF .
A Survey on Homomorphic Encryption Schemes: Theory and Implementation
CSUR
Computer Science