Scheme Construction:

For a specific (η bits) odd positive integer p, we use the following distribution over γ –bit inte-gers:

Dγ,ρ (ρ) = {choose q ←Z ∩ [0, 2^γ/p ), r ← Z ∩(-2^ρ, 2^ρ): output x = pq + r}

KeyGen(λ): The secret key is an oddη–bit integer:

                 P ← (2Z + 1) ∩ [2^n-1, 2^η).

For the public key, sample xi← D γ,p for I = 0,…….., τ. Relabel so that x0 is the largest. Restart

unless x0 is odd and  rp(x0) is even. The public key pk= ‹ x0, x1,……. xτ ›.

Encrypt (pk, m∊{0,1}) and a random integer r in (-2^ρ,2^ρ’), and output

                                                c ← [m + 2r + 2 Ʃ _i∊S x_i] _x0                                                                            

Evaluate (pk, C,c1,c2,…….,ct): Given the (binary) circuit C with t inputs, and t ciphertexts ci, apply the (integer) addition and multiplication gates of C to the cipher-texts, performing all the operations over the integers, and return the resulting integer.

Decrypt (sk, c): Output m’←(c mod p) mod2.

Remark: Decryption can also be written as: m’←[c-⌊c/p˥]2.

Homomorphic properties:

The homomorphic properties of the asymmetric scheme is interpreted as the symmetric one

basic symmetric scheme:

The secret key is odd integer, chosen from some interval p∊ [2^n-1 , 2ⁿ] where n is the bit length of the secret key. The cipher-text of a plain-text m∊ {0,1} is given by:

                                    c = Encrypt (p, m) = pq + 2r + m                                                                               

Where the integers q, r are chosen randomly in some other intervals, such that 2r is smaller than p/2 in absolute value. In this scheme, the cipher-text is an integer whose residue mod p has the same parity of the plaintext m.

                                   Decrypt (p, m) = (c mod p) mod 2r                                                                             

The decryption works as long as the noise r is much smaller than p.

                                    m’ ←[ c- ⌊c/p˥ ]2                                                                                                         

2) Homomorphic behavior: Suppose that we have two plain-texts m1,m2, with two ciphertextsrespectively c₁ = pq₁ + 2r₁ + m₁, c₂ = pq₂ + 2r₂ + m₂ .

a) Addition:

                                          c₁+ c₂= p(q₁+ q₂) + 2(r₁+ r₂) + m₁+ m₂                                                                     

Decryption works as long as 2(r₁ + r₂) ∊ [-p/2, p/2].

b) Multiplication:

    c₁ × c₂ = p(pq₁q₂ + 2r₂q₁ + q₁m₂ + 2q₂r₁ + m₁q₂) + 2(2r₁r₂ + m₂r₁ + m₁r₂) + m₁m₂                                     

Decryption works as long as 2(2r₁r₂ + m₂r₁ + m₂r₂) ∊ [-p/2, p/2]

The DGHV (Dijk-Gentry-Halevi-Vaikutanathan) which is an asymmetric encryption scheme based on the computation over real integers. The basic DGHV scheme provides the homomorphic behavior for a limited circuit depth. Bootstrapping is a technique introduced the literature to make the scheme fully homomorphic and supports unlimited circuit depth. 

To obtain a practical and applicable FHE scheme, one of the crucialsteps is taken by showing the construction of an FHE scheme from NTRU Encrypt, which is an old encryption scheme proposed by Hoffstein, Pipher, and Silvermanin in [Hoffstein et al. 1998]. Specifically, how to obtain a multi-key FHE from the NTRUEncrypt (called NTRU) was shown by [López-Alt et al. 2012]. NTRU encryption scheme is one of earliest attempts based on lattice problems. Compared with RSA and GGH cryptosystems, NTRU improves the efficiency significantly in both hardware and software implementations.

Learning with Error (LWE) is considered as one of the hardestproblems to solve in practical time for even post-quantum algorithms. First, it was introduced by Oded Regev as an extension of “learning from parity with error” problem [Regev 2009]. Regev reduced the hardness of worst-case lattice problems like SVP to LWE problems, which means that if one can find an algorithm that can solve LWE problem in an efficient time, the same algorithm will also solve the SVP problem in an efficient time. Since then, it is one of the most attractive and promising topics for post-quantum cryptology with its relatively small ciphertext size. Lyubashevsky et al. suggested another significant improvement on the LWE problem which may lead to new applications by introducing ring-LWE (RLWE) problem [Lyubashevsky et al. 2013]. The RLWE problem is an algebraic variant of LWE, which is more efficient for practical applications with strong security proofs. They proved that the RLWE problems are reducible to worst-case problems on ideal lattices, which is hard for polynomial-time quantum algorithms.

In 2010, one year after Gentry’s original scheme,another SWHEscheme is presented in [Van Dijk et al. 2010] which suggests Gentry’s ingenious bootstrapping method in order to obtain an FHE scheme. The proposed scheme is over integers and the hardness of the scheme is based on the Approximate Greatest Common Divisor (AGCD) problems [Galbraith et al. 2016]. AGCD problems try to recover p from the given set of x_i = pq_i + r_i. The primary motivation behind the scheme is its conceptual simplicity. A symmetric version of the scheme is probably one of the simplest schemes.

Bootstrapping is basically “recrypting” procedure to get a “fresh” ciphertextfro-m the noisy ciphertext corresponding to the same plaintext. A scheme is called bootstrappable if it can evaluate its own decryption algorithm circuit [Gentry 2009]. First, the ciphertext is transformed into a bootstrappable ciphertext using squashing. Then, by applying bootstrapping procedure, one gets a “fresh” ciphertext

Gentry’s bootstrapping technique is allowed only for the decryption algorithms withsmall depth. Therefore, he used some “tweaks” to reduce the decryption algorithm’s complexity. This method is called squashing and works as follows: First, choose a set of vectors, whose sum equals to the multiplicative inverse of the secret key ((Bj^sk)^-1). If the ciphertext is multiplied by the elements of this set, the polynomial degree of the circuit is reduced to the level that the scheme can handle. The ciphertext is now “bootstrappable”. Nonetheless, the hardness of the recovering the secret key is now based on the assumption of Sparse Subset Sum Problem (SSSP) [Hoffstein et al. 2008]. This basically adds another assumption to the provable security of the scheme.

Gentry’s first FHE scheme in his PhD thesis [Gentry2009] is a GGH-type of encryption scheme, where GGH (Goldreich-Goldwasser-Halevi) is an asymmetric cryptosystem based on lattices.

An encryption scheme is called Fully Homomorphic Encryption (FHE) scheme if it allows an unlimited number of evaluation operations on the encrypted data and resulting output is within the ciphertext space. After almost 30 years from the introduction of privacy homomorphism concept [Rivest et al. 1978a], Gentry presented the first feasible proposal in his seminal PhD thesis to a long term open problem, which is obtaining an FHE scheme [Gentry 2009]. Gentry’s proposed scheme gives not only an FHE scheme, but also a general framework to obtain an FHE scheme. Hence, a lot of researchers have attempted to design a secure and practical FHE scheme after Gentry’s work.

Although Gentry’s proposed ideal lattice-based FHE scheme [Gentry 2009] is very promising, it also had a lot of bottlenecks such as its computational cost in terms of applicability in real life and some of its advanced mathematical concepts make it complex and hard to implement. Therefore, many new schemes and optimization have followed his work in order to address aforementioned bottlenecks. The security of new approaches to obtain a new FHE scheme is mostly based on the hard problems on lattices.