HEAAN
HEAAN (Homomorphic Encryption for Arithmetic of Approximate Numbers) is an open source homomorphic encryption (HE) library which implements an approximate HE scheme proposed by Cheon, Kim, Kim and Song (CKKS). The first version of HEAAN was published on GitHub on 15 May 2016, and later a new version of HEAAN with a bootstrapping algorithm was released. Currently, the latest version is Version 2.1. CKKS plaintext space. Unlike other HE schemes, the CKKS scheme supports approximate arithmetics over complex numbers (hence, real numbers). More precisely, the plaintext space of the CKKS scheme is formula_1 for some power-of-two integer  formula_2. To deal with the complex plaintext vector efficiently, Cheon et al. proposed plaintext encoding/decoding methods which exploits a ring isomorphism formula_3. Encoding method. Given a plaintext vector formula_4 and a scaling factor formula_5, the plaintext vector is encoded as a polynomial formula_6 by computing formula_7 where formula_8 denotes the coefficient-wise rounding function. Decoding method. Given a message polynomial formula_9 and a scaling factor formula_5, the message polynomial is decoded to a complex vector formula_11 by computing formula_12. Here the scaling factor formula_13 enables us to control the encoding/decoding error which is occurred by the rounding process . Namely, one can obtain the approximate equation formula_14 by controlling formula_15 where formula_16 and formula_17 denote the encoding and decoding algorithm, respectively. From the ring-isomorphic property of the mapping formula_3, for formula_19 and formula_20, the following hold: where formula_23 denotes the Hadamard product of the same-length vectors. These properties guarantee the approximate correctness of the computations in the encoded state when the scaling factor formula_24 is chosen appropriately. Algorithms. The CKKS scheme basically consists of those algorithms: key Generation, encryption, decryption, homomorphic addition and multiplication, and rescaling. For a positive integer formula_25, let formula_26 be the quotient ring  of formula_27 modulo formula_25. Let formula_29, formula_30 and formula_31 be distributions over formula_32 which output polynomials with small coefficients. These distributions, the initial modulus formula_33, and the ring dimension formula_34 are predetermined before the key generation phase. Key generation. The key generation algorithm is following: Encryption. The encryption algorithm is following: Decryption. The decryption algorithm is following: The decryption outputs an approximate value of the original message, i.e., formula_50, and the approximation error is determined by the choice of distributions formula_51. When considering homomorphic operations, the evaluation errors are also included in the approximation error. Basic homomorphic operations, addition and  multiplication, are done as follows. Homomorphic addition. The homomorphic addition algorithm is following: The correctness holds as formula_56. Homomorphic multiplication. The homomorphic multiplication algorithm is following: The correctness holds as formula_63. Note that the approximation error (on the message) exponentially grows up on the number of homomorphic multiplications. To overcome this problem, most of HE schemes usually use a modulus-switching technique which was introduced by Brakerski, Gentry and Vaikuntanathan. In case of HEAAN, the modulus-switching procedure is called rescaling. The Rescaling algorithm is very simple compared to Brakerski-Gentry-Vaikuntanathan's original algorithm. Applying the rescaling algorithm after  a homomomorphic multiplication, the approximation error grows linearly, not exponentially. Rescaling. The rescaling algorithm is following: The total procedure of the CKKS scheme is as following: Each plaintext vector formula_67 which consists of complex (or real) numbers is firstly encoded as a polynomial formula_9 by the encoding method, and then encrypted as a ciphertext formula_69. After several homomorphic operations, the resulting ciphertext is decrypted as a polynomial formula_70 and then decoded as a plaintext vector formula_71 which is the final output. Security. The IND-CPA security of the CKKS scheme is based on the hardness assumption of the ring learning  with errors (RLWE) problem, the ring variant of very promising lattice-based hard problem Learning with errors (LWE). Currently the best known attacks for RLWE over a power-of-two cyclotomic ring are general LWE attacks such as dual attack and primal attack. The bit security of the CKKS scheme based on known attacks was estimated by Albrecht's LWE estimator. Library. Version 1.0, 1.1 and 2.1 have been released so far. Version 1.0 is the first implementation of the CKKS scheme without bootstrapping. In the second version, the bootstrapping algorithm was attached so that users are able to address  large-scale homomorphic computations. In Version 2.1, currently the latest version, the multiplication of ring elements in formula_72 was accelerated by utilizing fast Fourier transform (FFT)-optimized number theoretic transform (NTT) implementation.