Homomorphic Encryption Schemes

In this section, we explain the basics of HE theory. Then, we present notable PHE, SWHE and FHE schemes. For each scheme, we also give a brief description of the scheme. An encryption scheme is called homomorphic over an operation * if it supports the following equation:

                                 E(m₁) * E(m₂) = E(m₁ * m₂), ∀m₁,m₂ ∈ M,                                      Where E is the encryption algorithm and M is the set of all possible messages.

An HE scheme is primarily characterized by four operations: KeyGen, Enc, Dec, and Eval. KeyGen is the operation, which generates a secret and public key pair for the asymmetric version of HE or a single key for the symmetric version. Enc is the operation which converts the plaintext into ciphertext. Dec is the process of getting plaintext back. However, Eval is an HE-specific operation, which takes ciphertexts as input and outputs a ciphertext corresponding to a functioned plaintext. Eval performs the function f() over the ciphertexts (c1,c2) without seeing the messages (m1,m2). Eval takes ciphertexts as input and outputs evaluated ciphertexts. The most crucial point in this homomorphic encryption is that the format of the ciphertexts after an evaluation process must be preserved in order to be decrypted correctly. In addition, the size of the ciphertext should also be constant to support unlimited number of operations. Otherwise, the increase in the ciphertext size will require more resources and this will limit the number of operations. Of all HE schemes in the literature, PHE schemes support Eval function for only either addition or multiplication, SWHE schemes support for only limited number of operations or some limited circuits(e.g., branching programs) while FHE schemes supports the evaluation of arbitrary functions(e.g., searching, sorting, max, min, etc.) with unlimited number of times over ciphertexts. The well-known PHE, SWHE, and FHE schemes are explained in the following sections with a greater detail. The interest in the area of HE significantly increased after the work of Gentry [Gentry2009] in2009. Here, we start with the PHE schemes, which are the first stepping stones for FHE schemes.